Documentation contradictions about ReentrantReadWriteLock. Does eventually write lock has priority over read lock or not in fair mode?

Question

From ReentrantLock javadoc:

Fair mode
When constructed as fair, threads contend for entry using an approximately arrival-order policy. When the currently held lock is released either the longest-waiting single writer thread will be assigned the write lock, or if there is a group of reader threads waiting longer than all waiting writer threads, that group will be assigned the read lock.

A thread that tries to acquire a fair read lock (non-reentrantly) will block if either the write lock is held, or there is a waiting writer thread. The thread will not acquire the read lock until after the oldest currently waiting writer thread has acquired and released the write lock. Of course, if a waiting writer abandons its wait, leaving one or more reader threads as the longest waiters in the queue with the write lock free, then those readers will be assigned the read lock.

A thread that tries to acquire a fair write lock (non-reentrantly) will block unless both the read lock and write lock are free (which implies there are no waiting threads). (Note that the non-blocking ReentrantReadWriteLock.ReadLock.tryLock() and ReentrantReadWriteLock.WriteLock.tryLock() methods do not honor this fair setting and will acquire the lock if it is possible, regardless of waiting threads.)

Maybe it is problem with my English but I see contradictions at this decription:
From first paragrapgh I don't understand meaning of approximately arrival-order policy

1. from first paragraph I understand that lock acquire the oldest waiting thread. If oldest thread - read thread then it will be group of read threads which wait longer than the longest waiting write thread.
2. From second paragraph I understand that read lock will not acquire if write lock exists in wait-set.

Please clarify this contradiction.

Answer 1

Here, quoting from your quote:

or if there is a group of reader threads

In other words: a writer wins over a single reader; but when a group of readers wants the lock, those get the lock.

Regarding the question: "and what does group actually mean" ... that would be an implementation detail, only available by looking into the source code.

Answer 2

I don't see any contradictions in the description you quoted and I think you understand #1 correctly but #2 wrongly.

And by the way I think GhostCat description is wrong. There is nothing that sums up waiting time of different threads and compares them. The logic is actually much simpler.

My answer tends to be long but hopefully explanatory.

Nonfair mode

Let's start with "nonfair" mode lock first. "Nonfair" here means that

A nonfair lock that is continuously contended may indefinitely postpone one or more reader or writer threads

So "fairness" here means that no thread could wait forever. "Nonfairness" means that if there is a constant flow of threads to acquire the read lock, and we have some thread (W1) that is waiting for the write lock, when new thread for read lock (Rn) comes it might get lock before the W1 thread and so might in unlucky circumstances happen indefinitely. Note that even in "nonfair" mode ReentrantReadWriteLock tries to be reasonably fair it just doesn't guaranties fairness because, as the doc says, "fairness" is not free and the cost is lower throughput.

Nonfair mode example

So how real unfair behavior might happen. Assume there is a W0 thread holding write lock and queue as of now is R0 and R1 waiting for the read lock, then W1 waiting for the write lock, and also in the future there will be a huge stream of new thread coming for the read lock Ri. Also assume that thread R1 thread has the lowest priority in the system and the OS never bumps up priority of threads even if they haven't worked for a very long time.

1. Write lock is held by W0, waiting queue is [R0, R1, W1]
2. W0 releases the write lock, R0 is woken up and acquires the read lock, now R1 has low priority and is not woken up so can't acquire the read lock right now. Waiting queue is now [R1, W1]
3. W1 is woken up but can't acquire the lock because of R0
4. Now while R0 still holds the read lock, new reader thread R2 arrives. As read lock is already acquired and the first thread in the waiting queue is a reader R1, R2 acquires the read-lock immediately. The read lock is held by [R0, R2]. Waiting queue is still [R1, W1].
5. Now R0 releases the lock but W1 still can't acquire the write lock as it is held now by R2. Waiting queue is still [R1, W1].
6. Now while R2 still holds the read lock, new reader thread R3 arrives, acquires the read lock and the same story goes on and on.

What is important here is that:

• The first write thread W1 is blocked from reading by a reading thread R1 which is not woken up to acquire the lock because of low priority and/or pure bad luck.
• for newly arrived Ri thread to find out if there is any writing thread in the whole queue takes some time and effort and thus a simpler heuristic is applied (step #4): whether the very first waiting thread is write or read thread and the R1 is reading one allowing fast acquisition. Note also that this logic at step #4 with checking the first thread in the queue is the attempt to be fair that I mentioned earlier and this is better than just naive implementation that has no such check.

Fair mode

So now back to fairness. As you might find at the sources of FairSync inner class (I stripped minor details) :

class FairSync extends Sync {
     final boolean writerShouldBlock() {
         return hasQueuedPredecessors();
     }
     final boolean readerShouldBlock() {
         return hasQueuedPredecessors();
     }
}

So literally yes, the difference between "fair" and "non-fair" is that in "fair" mode reader thread before acquiring the read-lock that it otherwise could acquire without breaking the ReadWriteLock contract additionally checks if there is any other thread in the queue before it. In this way W1 thread from the previous example could not wait forever as R2 and next thread would not acquire the read lock before it.

Fair mode example

Another attempt on the same example in fair mode:

1. Write lock is held by W0, waiting queue is [R0, R1, W1]
2. W0 releases the write lock, R0 acquires the read lock queue is [R1, W1]
3. W1 is woken up but can't acquire the lock because of R0
4. R2 arrives to the queue. Although the read lock is held by R0 and R2 seem to be able to acquire it as well, it doesn't do it because it sees W1 ahead of itself. The read lock is held by R0 and the queue is [R1, W1, R2]
5. Now both W1 and R2 can't acquire lock until R1 is removed from the queue. Because of this finally R1 is woken up gets the lock does the processing and releases the lock.
6. Finally W1 acquires the write lock and R2, R3 and others are still in the queue waiting.

In terms of this example R0 and R1 form a "group" but R2 doesn't belong to that "group" because it is after W1 in the queue.

Summary

So first paragraph describes is what happens when a lock is released and the strategy is simple: the first waiting thread acquires the lock. If the first waiting thread happens to be read-thread, then all other read threads in the queue before the first writing thread acquire the read lock. All such read threads are called "group". Note that this doesn't mean all read threads waiting for the lock!

Second paragraph describes what happens when a new read-thread arrives and tries to acquire lock and behavior here is actually consistent with first paragraph: if there is a waiting write-thread in the queue before the current thread, it will not acquire the lock the same way it would not acquire the lock if it was added to the queue before lock was released and rules from paragraph #1 would apply. Hope this helps.

Answer 3

The fair mode policy is only "approximately arrival-order" because threads waiting to acquire a read-lock are batched, and a thread that arrived later to acquire a read lock might get the lock earlier than another thread from the same batch trying to acquire a read lock, due to OS scheduling.

A "group of reader threads" can be just one thread.

There is no contradiction in the spec, but it might not be as clear as it could be.

Suppose thread A holds a write lock on the mutex.

Thread B arrives and tries to get a write lock. Then thread C arrives and tries to get a read lock. Then thread D arrives and tries to get a read lock. Then thread E arrives and tries to get a write lock. Then thread F arrives and tries to get a read lock.

Now thread A unlocks the mutex. The fair mode policy implies that thread B will get the lock: it has been waiting longest.

When thread B releases the lock, threads C and D will get the read lock, but not thread F. C and D are a "group of reader threads waiting longer than all waiting writer threads". Thread F is still blocked, because it has been waiting less long than thread E, which is a writer thread.

If thread E then abandons the wait (e.g. it times out), then thread F is now the oldest waiting thread, and the current lock is a read lock, so thread F can acquire the lock before threads C and D release theirs.

If thread G now tries to acquire the write lock, it will block until all of threads C, D and F have released their read locks.

If thread H now tries to acquire a read lock, it will block: there is a waiting writer thread.

If thread I now tries to acquire a writer lock, it will block: there is a queue of waiting threads.

Now, C, D and F release their locks, so thread G (the longest waiting thread) acquires the writer lock.

Thread G releases the lock, and thread H acquires the lock: it is a group of one reader thread, that has been waiting longer than any waiting writer.

Finally, when thread H releases the lock, thread I can acquire it.