Почему алгоритм ReentrantLock из книги не работает?

Question

Сегодня я прочитал Нир Шавит, Морис Херлихи, Искусство многопроцессорного программирования и натолкнулся на одну очень непонятную ( лично для меня ) вещь.

Итак, я нашел реализацию ReentrantLock в java (для меня это страница 188, глава 8 ):

class SimpleReentrantLock implements Lock {

    Lock lock;
    Condition condition;
    long owner, holdCount;

    SimpleReentrantLock() {
        lock = new SimpleLock();
        condition = lock.newCondition();
        owner = 0;
        holdCount = 0;
    }

    @Override
    public void lock() {
        long me = Thread.currentThread().getId();
        lock.lock();
        if (owner == me) {
            holdCount++;
            return;
        }

        while (holdCount != 0) {
            try {
                condition.await();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        owner = me;
        holdCount = 1L;
    }

    @Override
    public void unlock() {
        lock.lock();
        try {
            if (holdCount == 0 || owner != Thread.currentThread().getId()) {
                throw new IllegalMonitorStateException();
            }

            holdCount--;
            if (holdCount == 0) {
                condition.signal();
            }
        } finally {
            lock.unlock();
        }
    }
    // Other methods for Lock interface...
}

Я проанализировал это код и до сих пор не до конца его понять.

Итак, я могу использовать ReentrantLock из java.util.concurrent.locks таким образом:

lock.lock();
lock.lock();
// Some code here...
lock.unlock();
lock.unlock();

И все будет в порядке, потому что это ReentrantLock, я может получить критический раздел несколько раз.

Например, вы можете найти реализацию спин-блокировки из этой книги:

class TASLock implements Lock {
    private AtomicBoolean state = new AtomicBoolean(false);

    @Override
    public void lock() {
        while(state.getAndSet(true));
    }

    @Override
    public void unlock() {
        state.set(false);
    }

    // Other Lock methods...
}

Эта реализация работает, как и ожидалось.

Итак SimpleReentrantLock вы можете заметить следующее:

 lock = new SimpleLock();

Как говорит нам автор:

мы инициализируем поле внутренней блокировки для объекта (фиктивного) класса SimpleLock который, вероятно, не реентерабельный

Но на самом деле, у меня есть реализация не -входящий замок (TASLock), поэтому я сделаю следующее встраивание:

lock = new TTASLock();

И, наконец, когда я попытаюсь выполнить следующий код, я получу тупик:

new Thread(() -> {
            lock.lock();
            lock.lock();
            System.out.println("No deadlock found.");
            lock.unlock();
            lock.unlock();
}).start();

И это выглядит довольно ясно, потому что в методе lock у нас есть такой код:

 lock.lock();

Мы фактически пытаемся получить критическую секцию дважды для одного и того же объекта блокировки без каких-либо предварительных условий.

В книге указан неправильный алгоритм? Или я чего-то не понял?

Answer 1

В методе lock () отсутствует lock.unlock (). Алгоритм правильный, это простой упущение.
Как указано в книге:

Поскольку этими двумя полями манипулируют атомарно, нам нужна внутренняя краткосрочная блокировка.

Чтобы ответить на вопрос в комментарии, вот исправленная версия lock ():

    public void lock() {
    long me = Thread.currentThread().getId();
    lock.lock();
    try{
    if (owner == me) {
        holdCount++;
        return;
    }

    while (holdCount != 0) {
        try {
            condition.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    owner = me;
    holdCount = 1L;
    } finally {        
        lock.unlock();  // this call is missing
    }
}