Threads throw a monkey wrench
into the art of programming!
For instance, since there are many readers inside an advisory lock, and a Java lock only allows one in, the code must work this way: a decision is made while holding the lock as to whether the reader is allowed in or not. If not, the reader waits, using Java's monitor capability. If it can, you exit the critical section and let the reader go on to whatever it has asked to do. (But the reader will re-enter the lock when it is ready to leave the data structure, to notify it is no longer reading.)
Since the writer must know about readers reading, there must be some sort of count, readers_reading, that is manipulated by the reader thread on the way in and on the way out. The data structure invariant reads: the value readers_reading is the number of threads that currently hold an advisory lock.
VERY ROUGH IDEA
reader flow:
[ synchronized:
loop {
(writers_waiting) ?
yes: wait
no: break
}
readers_reading ++
]
... reader can work (not holding lock!) ...
[ synchronized:
readers_reading --
notify_all // unless readers_reading>0 ?
]
writer flow:
[ synchronized:
loop {
(readers_reading>0) ?
yes: writers_waiting set true
wait
// sett flag false here?
// fairness/liveness maybe?
writers_waiting set false
no: break
}
.. writer can work (holds lock!) ...
notify_all // can we use a simple notify?
]
Once you clear the entry criteria, for readers you certainly must exit the synchronization block. The "trace" of its existence is captured in the readers-reading count non-zero. A writer can't proceed until this count goes to zero.
To get safety, all you need is that the writer doesn't not enter if the reader-reading count is non-zero. But this does not capture the special correctness of this sort of synchronization primitive. It also seems the a heightened fairness towards writers is considered as a correctness critieria: to require that a reader does not enter if a writer is waiting.
For this reason, a writer failing to enter the critical section, and going on the wait queue, must leave behind a signal that new readers cannot proceed. Maybe it sets a writer_waiting flag before the wait. This flag has to be renewed in the wakeup loop in case there are multiple writers waiting.
The writer can proceed while holding the lock. Only one writer is allowed in so there maybe there is no point having it release the lock only to have all the threads re-wait on some trace that a writer is in the data structure. While the writer writes no one can proceed so maybe it is best just to have them wait outside the monitor, but notified, until the writer leaves the monitor.
Extra credit: Can you prove your code? What are the proof tools that you have? That is, how will you even approach a proof? Does it help to consider safety, liveness and fairness separately? You have two classes of threads, readers and writers. How does that affect proof statement?
Copyright 2012 burton rosenberg
Last modified: 15 Oct 2012