Information Technology Reference
In-Depth Information
Hansen v. Hoare semantics
In modern condition variables,
signal()
or
broadcast()
calls take waiting threads
from a condition variable's
waitingqueue
and put them on the scheduler's ready list.
Later, when these threads are scheduled, they may block for some time while they try
to reacquire the lock. Thus, modern condition variables implement what are sometimes
called Hansen semantics (for Brinch Hansen, who first defined such condition variables)
or Mesa Semantics (for Mesa, an early programming language at Xerox PARC that
implemented these semantics.)
C.A.R. “Tony” Hoare proposed a different definition for condition variables. Under
Hoare semantics, when a thread calls
signal()
, execution of the signaling thread is
suspended, the ownership of the lock is immediately transferred to one of the waiting
threads, and execution of that thread is immediately resumed. Later, when that resumed
thread releases the lock, ownership of the lock reverts to the signaling thread, whose
execution continues.
Thus, under Hoare semantics, signaling is atomic with the resumption of a waiting
thread, and a signaled thread may assume that the state has not changed since the
signal that woke it up was issued. So, where under Hansen semantics, waiting is always
done in a loop (e.g.,
while(predicate())
if
cv.wait();
g), under Hoarse semantics,
waiting can be done with a simple conditional (e.g.,
if(predicate())
if
cv.wait();
g)
There are debates about which semantics are better. Some argue that the atomicity
of signaling and resuming a waiting process makes it easier to prove liveness properties
of programs under Hoare semantics. For example, if I know that one thread is waiting on
a condition, and I do a signal, I know that waiting thread will resume and make progress
(and not some other late-arriving thread.)
For what it is worth, the authors of this topic come down strongly on the side of
Hansen supporters. The modularity advantages of Hansen semantics greatly simplify
reasoning about an object's core safety properties. For the properties we care most
about (i.e., the safety properties that the threads only proceed when they are supposed
to) and for large programs where modularity matters, Hansen semantics seem vastly
preferable to us Furthermore, in cases where liveness is a concern, you can implement
explicit queuing to manage the order that waiting threads access an object (we leave
this as an exercise for the reader.)
Regardless of which semantics are better, as a practical matter the debate has been
settled: essentially all systems use Hansen semantics, and we know of no widely-used
system that implements Hoare semantics. This resolution of the debate may be due as
much to a desire for simpler implementations than to a universal consensus regarding
the “right” semantics. Furthermore, programmers that program assuming the weaker
Hansen semantics (e.g., always writing
while(predicate())cv.wait(&lock);
) will
write programs that will work under either definition. (And note that the overhead from
the “extra” check of the predicate upon return from
wait()
in a
while
loop rather than
an
if
conditional is unlikely to be significant compared to the signaling and scheduling
overheads being paid in any event.) In any event, as a programmer, you won't go wrong
if you write your code assuming Hansen semantics.
