Пример тупика потоков Java

Question

Я пытался прочитать Искусство многопроцессорного программирования Херлихи и Шавита. Во второй главе они мотивируют алгоритм Петерсона двумя неверными реализациями блокировок. Я пытался понять проблему с классом LockTwo и закончил со следующим кодом, который блокирует. Пример вывода приведен после кода, где потоки не выводят все значения от 1 до 100 до взаимоблокировки. Чтобы тупик возник в любом потоке, while(victim ==i){} должен работать вечно. Но если оба потока запускают этот цикл, то один из них должен выйти, потому что victim не может быть 0 и 1 одновременно. Я что-то упустил из-за кеша?

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();
        }
    }
}

Пример вывода $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

Я подозреваю, что проблема в том, что victim не является энергозависимым.
Переменные в java могут локально кэшироваться в потоке.

Это означает, что каждый поток имеет свое собственное представление о жертве, каждый со своим собственным идентификатором.
То есть Тема 0 имеет victim == 0, а тема 1 имеет victim == 1

Использование volatile указывает jvm, что переменная будет использоваться в потоках и что она не должна кэшироваться.

Answer 2

Этот ответ основан на ответе Джима и связанных с ним комментариях.

Если проблема связана с отсутствием ключевого слова volatile, потоки должны сразу же зайти в тупик, они никогда не смогутувеличить счетчик.- sarva

Это неверно, нет способа гарантировать, что записанное значение будет распространяться на другие потоки.

Кстати, реализация LockTwo в ArtofMPимеет ключевое слово volatile, связанное с victim, но исправления требуют, чтобы это ключевое слово было удалено.- sarva

Это только потому, что согласованность с другими алгоритмами представлена ​​в той же главе.В прагме 2.3.1 говорится, что victim, label и т. Д. Должны быть объявлены на практике volatile, но тогда victim объявляется volatile на рисунке 2.5 в любом случае.

Если я добавлю ключевое слово volatile к victim, то в самом конце возникает тупик, когда один поток завершает выполнение, увеличивая счетчик до 100, а другой поток ожидает в while(victim == i) {} без изменения значенияжертвы.- Сарва

Это поведение, которое вы хотите.Рассмотрим однопотоковую программу, поэтому следующие строки из вашей программы не имеют смысла:

victim = i;
while (victim == i) {}

Без дополнительного потока это будет бесконечный цикл.

Мы можем получитьпо существу эквивалентная ситуация в двухпоточной программе, когда только один из потоков пытается получить блокировку (т. е. вызвать метод lock).

Если оба потока вызывают метод lock, мы получаемповедение, которое вы наблюдали, когда в конце возникает тупик:

1. Первый поток вызывает lock и устанавливает victim в 0 и начинает цикл
2. Второй поток вызывает lock и устанавливает victim в 1 и начинает цикл
3. Первый поток видит, что victim теперь равен 1, и входит в критическую секцию
4. Если первый поток никогда не вызывает lock метод снова, второй поток будет застревать в цикле навсегда, ожидая, пока victim станет 1

Таким образом, (в некотором смысле) последний вызов не завершится, если оба потока вызовутlock метод мюНесколько раз каждый.