  Most programming languages use monitors with explicit signals for
synchronization in shared-memory programs. Requiring program- mers to signal
threads explicitly results in many concurrency bugs due to missed
notifications, or notifications on wrong condition variables. In this paper, we
describe an implementation of an au- tomatic signaling monitor in Java called
AutoSynch that eliminates such concurrency bugs by removing the burden of
signaling from the programmer. We show that the belief that automatic signaling
monitors are prohibitively expensive is wrong. For most problems, programs
based on AutoSynch are almost as fast as those based on explicit signaling. For
some, AutoSynch is even faster than explicit signaling because it never uses
signalAll, whereas the programmers end up using signalAll with the explicit
signal mechanism. AutoSynch achieves efficiency in synchronization based on
three novel ideas. We introduce an operation called globalization that enables
the predicate evaluation in every thread, thereby reducing context switches
during the execution of the program. Secondly, AutoSynch avoids signalAll by
using a property called relay invari- ance that guarantees that whenever
possible there is always at least one thread whose condition is true which has
been signaled. Finally, AutoSynch uses a technique called predicate tagging to
efficiently determine a thread that should be signaled. To evaluate the effi-
ciency of AutoSynch, we have implemented many different well- known
synchronization problems such as the producers/consumers problem, the
readers/writers problems, and the dining philosophers problem. The results show
that AutoSynch is almost as efficient as the explicit-signal monitor and even
more efficient for some cases.
