|
|
Optimize with a SATA RAID Storage Solution
Range of capacities as low as $1250 per TB. Ideal if you currently rely on servers/disks/JBODs
Page 4 of 4
As an interesting example of using Hoare-style monitors, let's look at how a number of threads can synchronize and exchange
information. The specific problem is that a number of threads must vote on a boolean result. I've used a simple majority,
with ties going to false. Listing 5 shows the monitor.
importmonitor.* ; public class VoteMonitor extends AbstractMonitor { private final int N ; private volatile int votesFor = 0, votesAgainst = 0 ; private Condition electionDone = makeCondition( new Assertion() { public boolean isTrue() { return votesFor+votesAgainst == N ; } } ) ; public VoteMonitor(int N) { assert N>0 ; this.N = N ; } @Override protected boolean invariant() { return 0 <= votesFor && 0 <= votesAgainst && votesFor+votesAgainst < N ; } public boolean castVoteAndWaitForResult(boolean vote) { enter() ; if( vote ) votesFor++ ; else votesAgainst++ ; electionDone.conditionalAwait() ; // votesFor + votesAgainst == N boolean result = votesFor > votesAgainst ; if( ! electionDone.isEmpty() ) { electionDone.signalAndLeave() ; } else { // The last one woken up is the first one out and cleans up. votesFor = votesAgainst = 0 ; leave() ; } return result ; } }
The constructor takes the number of threads involved in the elections. After construction each thread casts its vote and receives
the majority using the castVoteAndWaitForResult method.
The election is over when votesFor+votesAgainst==N and so this assertion is PelectionDone. Interestingly, this assertion contradicts the invariant. After casting its vote, a thread waits for the election to be over
by conditionally waiting on electionDone. On returning from electionDone.conditionalAwait(), the thread can be sure that PelectionDone is true. Thus it could leave the monitor and return with the result at that time.
This would cause two problems, however: First, only the last thread to vote would get the result; all others would wait forever.
Second, there would be no way to reuse the monitor object for a second election. To solve these two problems I divided the
work: Each thread awakens one waiting thread until no threads are waiting on electionDone -- I call this technique "daisy chaining." The last thread on the chain finds there are no more threads to awaken; it resets
the state of the monitor to the original state; having done that, it has reestablished the monitor invariant and may leave
the monitor unoccupied.
Note that the invariant is not true when signalAndLeave is called. Despite the fact that the invariant has not been reestablished, it is acceptable for the signaling threads to
leave the monitor, because they are not leaving it empty. As discussed in the next section, this approach would not be possible
using Java's standard methods.
It wouldn't be right to present my Java-based monitor package without comparing it with Java's "native" monitors, which are built using the synchronized keyword and the wait() and notify() methods from the Object class.
In Java, every object is associated with two queues: an entry queue and a wait queue. When a thread calls a method marked
as synchronized, the thread will wait on the entry queue until no other thread occupies the object. On returning from a synchronized method the thread relinquishes occupancy. Threads unconditionally wait on the wait queue by calling the wait() method of the synchronizing object. A call to notify() does not relinquish exclusive access; rather it simply moves some waiting thread, if there is one, from the object's wait
queue to the object's entry queue. There also is a notifyAll() method that moves all threads from the wait queue to the entry queue.
Java's native monitors are similar to those found in Mesa and are sometimes said to use the "signal and continue" (SC) signaling discipline. By contrast, my monitor package gives you a choice of "signal and wait" (SW) or "signal and leave" (SL).
The following list summarizes the main differences between my monitor package and Java's wait() and notify() approach:
monitor package provides support for defensive programming through the invariant() method and the assertion objects associated with each condition object. Java's notify() and wait() provide no assertion checking.
monitor package provides condition objects, each providing its own wait queue. Threads waiting for different assertions to become
true wait on different queues. Using wait(), there is only one wait queue per object. Threads waiting for different assertions to become true must all wait on the same
queue; thus a notify() call could awaken a thread that is waiting for the "wrong" assertion. The usual solution is to replace calls to notify() with calls to notifyAll() and to always put calls to wait() in a loop, so:
while( ! Pc ) { wait(); }
wait(), it does so from the entry queue and so the invariant must be true.
monitor package, following Hoare's suggestion, control is passed seamlessly from the signaling thread to an awaiting thread. You
can be sure that, after returning from an await(), the assertion the thread has waited for is true. In contrast, the notify() and notifyAll() methods simply move a waiting thread back to the entry queue for the monitor. By the time the waiting thread actually becomes
the occupant, the assertion for which it was waiting may no longer be true. This is a second reason for putting wait() calls in a loop. But such loops have a problem: an invocation of notify() that awakens a thread that then re-waits is effectively lost. As notify() calls can be lost, it can be difficult to ensure "sufficient signaling" -- the property that any waiting thread is eventually
awakened. With the monitor package, ensuring sufficient signaling requires only ensuring that each await() be matched by some signal() on the same condition object in the future.
Hoare-style monitors provide a sound programming method for coordinating the interactions of multiple threads. In the limited space of this article, I could only illustrate this point with very simple examples. As the complexity of the interactions increase, the benefit of using Hoare-style monitors increases.
In Hoare's original concept, a monitor's invariant and the assertions associated with condition variables were purely tools
of design and documentation: the truth of the assertions can be proved and there is no need to check them at runtime. In practice
though, even careful designers make mistakes and, as software evolves, errors can creep in. Thus it is pragmatic to check
assertions at runtime. The monitor package in this article automatically checks assertions and invariants, letting you move the assertions out of the comments
and into the code.
See the Resources section for the source code for the monitor package.
Thanks to Alain O'Dea for suggesting an improvement to the monitor package, to Michael Bruce-Lockhart and Dennis Peters for suggesting improvements to this article, and to Ric Holt for introducing
me to Hoare-style monitors many years ago.
Archived Discussions (Read only)