Java threads deadlock example

Question

I have been trying to read The Art of Multiprocessor Programming by Herlihy and Shavit. In the second chapter they motivate Peterson's algorithm with two incorrect lock implementations. I was trying to understand the problem with the LockTwo class and ended with the following code which deadlocks. A sample output is given after the code where the threads don't print all the values from 1 to 100 before deadlock. For deadlock to occur in either thread, the while(victim ==i){} has to run forever. But if both threads are running this loop then one of them has to exit because victim cannot be 0 and 1 at the same time. Am I missing something cache-related?

class Counter
{
    private int value;
    private int maxValue;
    public Counter(int value, int maxValue)
    {
        this.value = value;
        this.maxValue = maxValue;
    }

    public int getValue()
    {
        return value;
    }

    public int getMaxValue()
    {
        return maxValue;
    }

    public void incrementValue()
    {
        value++;
    }
}

class ThreadID 
{
  private static volatile int nextID = 0;
  private static ThreadLocalID threadID = new ThreadLocalID();

  public static int get() 
  {
    return threadID.get();
  }

  public static void reset() 
  {
    nextID = 0;
  }

  private static class ThreadLocalID extends ThreadLocal<Integer> 
  {
    protected synchronized Integer initialValue() 
    {
      return nextID++;
    }
  }
}

class IncrementThread implements Runnable
{
    private static Counter c = new Counter(0,100);
    private static LockTwo lock2 = new LockTwo();
    public IncrementThread()
    {
    }

    public void run()
    {
        int j = ThreadID.get();
        String m = "Thread ID " + j;
        //System.out.println(m);                        
        while(c.getValue() < c.getMaxValue())
        {
            lock2.lock();
            c.incrementValue();
            String s = "Value in counter is " + c.getValue() + " in thread " + j;
            System.out.println(s);                        
            lock2.unlock();
        }
    }
}

interface Lock
{
    public void lock();
    public void unlock();
}


class LockTwo implements Lock
{
    private int victim;
    public LockTwo() {};
    public void lock()
    {
        int i = ThreadID.get();
        victim = i;
        System.out.println("Trying to acquire lock in thread " + i +" with victim " + victim);
        while(victim == i) {} 
        System.out.println("Lock acquired in thread " + i + " with victim " + victim);
    }

    public void unlock()
    {
        int i = ThreadID.get();
        //victim = i;
        System.out.println("Lock released in thread " + i + " with victim " + victim);
    }
}

public class SharedCounter
{
    public static void main(String[] args) throws InterruptedException
    {
        Thread thread[] = new Thread[2];
        for (int i = 0; i < thread.length; i++)
        {
            thread[i] = new Thread(new IncrementThread());
            thread[i].start();
        }
    }
}

Sample output $java SharedCounter

Trying to acquire lock in thread 0 with victim 1
Trying to acquire lock in thread 1 with victim 1
Lock acquired in thread 0 with victim 1
Value in counter is 1 in thread 0
Lock released in thread 0 with victim 1
Trying to acquire lock in thread 0 with victim 0
Lock acquired in thread 1 with victim 0
Value in counter is 2 in thread 1
Lock released in thread 1 with victim 0
Trying to acquire lock in thread 1 with victim 1
Lock acquired in thread 0 with victim 1
Value in counter is 3 in thread 0
Lock released in thread 0 with victim 1
Trying to acquire lock in thread 0 with victim 0

Answer 1

I suspect the problem is that victim is not volatile.
Variables in java can be cached locally to the thread.

This means each thread has it's own view of victim, each with it's own id.
I.e. Thread 0 has victim == 0 and Thread1 has victim == 1

Using volatile tells the jvm that the variable will be used across threads and that it should not be cached.