Is there a deadlock when acquiring, releasing, and then acquiring multiple permits with semaphores i-CodePudding

The following code snippet is a solution to https://leetcode.com/problems/print-in-order/ which runs printFirst.run(), printSecond.run(), and printThird.run() in order using a single semaphore. Three threads A, B, and C call the functions. Thread A will call first, thread B will call second, and thread C will call third.

I understand why lock.acquire(); followed by lock.release(); is required in third, rather than calling lock.acquire(2); immediately, due to the way Java assigns permits to waiting threads in a queue. Calling lock.acquire(2); creates a deadlock as nothing can ever release enough permits.

That being said, I do not understand how lock.acquire(); followed by lock.release(); before this fixes it.

Would somebody be able to explain to me what happens in the situation where first first calls lock.release() and then third calls lock.acquire(); lock.release(); lock.acquire(2); before second runs? Does this result in a deadlock, in the same way that calling lock.acquire(2); by itself would result in a deadlock? Is this just an unlikely situation which is why this works?

Any help with this would be greatly appreciated, thank you!

class Foo {
    
    private Semaphore lock = new Semaphore(0);

    public void first(Runnable printFirst) throws InterruptedException {
        // printFirst.run() outputs "first". Do not change or remove this line.
        printFirst.run();
        lock.release();
    }

    public void second(Runnable printSecond) throws InterruptedException {
        lock.acquire();
        // printSecond.run() outputs "second". Do not change or remove this line.
        printSecond.run();
        lock.release(2);
    }

    public void third(Runnable printThird) throws InterruptedException {
        lock.acquire();
        lock.release();
        lock.acquire(2);
        // printThird.run() outputs "third". Do not change or remove this line.
        printThird.run();
    }
}

CodePudding user response：

I now understand why this is correct and will not deadlock.

Having the acquire() and release() before acquire(2) in third() means that the number of permits is guaranteed to either be 1 at the time it acquires, meaning that second() can acquire and still progress, OR second() has already called acquire() and there are 0 permits, but this doesn't matter because second() is about to release(2), which will allow third() to continue.

Without acquire() and release() in third(), there is a chance third() will acquire(2) before ANY progress has been made in the other threads (i.e. there are no permits and second() hasn't successfully acquired), meaning that the released permit in first() will go towards third() and second's acquire will never succeed.