Signalling threads in a lock's condition

Question

I have taken the following points from this API and I would like to know the difference between the 2 following points:

1. Waiting threads are signalled in FIFO order.

2. The ordering of lock reacquisition for threads returning from waiting methods is the same as for threads initially acquiring the lock, which is in the default case not specified, but for fair locks favors those threads that have been waiting the longest.

It is related to Condition class which is usually returned by the ReentrantLock method .newCondition(), and the bit I quoted it's explaining the difference between the methods of Condition and the regular monitor methods of the Object class.

"Waiting threads are signalled in FIFO order". I think that as long as a lock is created either fair or not, the fact that the waiting threads are signalled in a FIFO order is totally irrelevant isn'it? because anyhow it's whether they have been constructed, fair or not, which decides how they are queued.

Just asking for a confirmation.

Thanks in advance.

Answer 1

Please see below answers to your questions:

1.Waiting threads are signalled in FIFO order.

When we invoke await() method of Condition, thread goes into waiting state, the above statement refers to how these threads in waiting state are signalled. So if threads T1 went to waiting state before T2, T1 will be signalled before T2.

2.The ordering of lock reacquisition for threads returning from waiting methods is the same as for threads initially acquiring the lock, which is in the default case not specified, but for fair locks favors those threads that have been waiting the longest.

In continuation to above statement, when waiting thread is signalled, it tend to reaquire lock. Though above statement says T1 will be signalled before T2, but when it comes to reaquiring lock, the order of reacquisition uses concepts defined by Lock. So, it depends on how Lock object was created. While creating Lock you might have specified a fairness parameter:

ReentrantLock(boolean fair)

If yes then that parameter is used, if not then default behaviour of locks happens, you can read more on ReentrantLock Locks at this link

There could be more explanations to these statements, just tried to best detail my understanding here. Hoping was able to clarify.

Cheers !!

Answer 2

As long as a lock is created either fair or not, the fact that the waiting threads are signaled in a FIFO order is totally irrelevant, isn't it? Because anyhow it's whether they have been constructed, fair or not, which decides how they are queued.

I think it is relevant.

Consider a scenario where T1 and T2 are waiting on a condition C (with T1 waiting longer than T2), T3 is running inside the monitor and T4 is waiting for its initial lock acquisition. T3 signals C and leaves the monitor releasing the lock. Let's suppose no spurious wakeup occur.

If the lock is fair, T4 will definitely acquire the lock before T1, but the fact that waiting threads are signaled in FIFO order will guarantee you that T1 will acquire the lock before T2.

Also, if the lock is not fair, we can't say which thread will acquire the lock first between T1 and T4, but again the fact that waiting threads are signaled in FIFO order guarantees that T1 will acquire the lock before T2, provided no other signals occur until T1 acquires the lock (for example in case T1 is responsible for the next signaling).

Answer 3

I think the source code can give us more clues about how it works.ReentrantLock.newCondition() return a ConditionObject in AbstractQueuedSynchronizer.Here is the source code link AQS source code.

1.Waiting threads are signalled in FIFO order.

There are two queues in AbstractQueuedSynchronizer.

One is for waiting for the lock(just call it lock waiting queue),you will see two volatile variable head and tail in AbstractQueuedSynchronizer's class definition,and the fairness parameter will affect this queue's behavior.When you new a fair ReentrantLock and call acquire,AQS will call FairSync's tryAcquire to check if current thread is the first thread waiting in the lock waiting queue,see hasQueuedPredecessors.

Another queue is the signal queue in the definition of ConditionObject,you will see two variable firstWaiter and lastWaiter.When await is called,a node will add to the tail of the queue and When signal is called,a node from the head will be dequeued and add to the lock waiting queue to reacquire the lock.Add to the lock waiting queue didn't mean it will be woke up,but a Lock.unlock() will be called after signal,which will wake up the waiters,see unparkSuccessor.

2.The ordering of lock reacquisition for threads returning from waiting methods is the same as for threads initially acquiring the lock, which is in the default case not specified, but for fair locks favors those threads that have been waiting the longest.

wake up from the await method didn't mean to hold the lock,it will call acquireQueued to reacquire the lock and could be parked again. In my understanding,the order of initially acquiring the lock is the same as the order of calling await,so the same as the order of calling acquireQueued,What confused me was but for fair locks favors those threads that have been waiting the longest.,When wake up from the await,in my opinion,it will be the first thread in the lock waiting queue,When call acquireQueued and check p == head && tryAcquire(arg),lock fair or not has no effect.

Hope this helps and let me if I am wrong.