Chuan-kai Lin's report
Last updated at 12:35 pm UTC on 17 January 2006
Report on Smalltalk Implementation of Monitors
Chuan-kai Lin
December 1, 2003
ABSTRACT
One of the advantages of the Smalltalk programming language is that its
runtime environment has built-in support for concurrency, thus
facilitating the development of programs that have multiple threads of
control. Unfortunately the synchronization construct provided by
Smalltalk – semaphores – is rather primitive, therefore extreme care
must be exercised to prevent deadlocks and race conditions in concurrent
programs. We present Smalltalk implementations of monitors, which are
high-level synchronization constructs that support reentrant critical
regions and conditional variables, and demonstrate how they could be
used to coordinate processes that interact through accessing shared
variables.
1. Introduction
The availability of multiple threads of control, provided either through
multiprocessing or multiprogramming, is now considered an indispensable
part of any modern computing environment. Structuring programs into
multiple processes eliminates the need to explicitly multiplex multiple
tasks into a single sequence (a labor intensive and error-prone job),
but instead requires that access to shared variables by the processes
must be regulated to prevent race conditions. Operating systems and
runtime environments usually provide semaphores to user programs, which
are conceptual locks that can be acquired by no more than a certain
number of processes at the same time. Mutual exclusion can be
guaranteed by requiring processes to acquire the lock before entering
the critical region.
Even though semaphores alone are adequate for implementing most kinds of
synchronization schemes, synchronizing access among processes using
semaphores turns out to be a highly nontrivial task, even for common
scenarios such as producer-consumer processes. The problem is that
anything but the most trivial cases require the use of more than one
semaphores that need to be acquired or released according to the state
of shared resources, so it is easy to run into deadlocks or race
conditions, unless the order of shared resource access, condition
testing, and the signaling and waiting of semaphores is determined with
extreme care.
Obviously this is not an ideal situation. The solution to this problem
is to use high-level constructs such as monitors, as we have implemented
for the Smalltalk language.
2. Monitors
Monitor[2] is a high-level synchronization construct that contains a set
of procedures and variables. The idea behind monitors is that all
access to in-monitor shared variables must be performed by invoking the
procedures defined in the monitor, so that accidental violation of
program invariance and synchronization properties can be avoided.
Mutual exclusion is guaranteed by allowing only one process in the
monitor at any time; a process will block when it tries to enter a
monitor with another process already in the monitor.
In addition, a monitor offers condition variables, which can be used by
an in-monitor process to block itself (wait on a condition variable)
when it cannot make any further progress. A process waiting on a
condition variables is no longer considered in the monitor for mutual
exclusion purposes, and can be waked up when another process signals the
condition variable. Signals do not accumulate when there are no
processes waiting on the condition variable; otherwise each signal wakes
up one process.
There are, however, variations on what should happen when a process
signals a condition variable that at least one process is waiting on:
Hoare Semantics[3]: C.A.R. Hoare proposed that the running process
should be immediately suspended when it signals a condition variable,
so that the previously blocked process can resume execution.
Mesa Semantics[4]: for monitors in Mesa and Modula-3, a signal does
not wake up a blocked process, but simply detaches it from the
condition variables and inserts it into the monitor entry queue, and
the running process that triggers the signal continues running.
Obviously whatever condition that holds when the condition variable is
signaled may not necessarily hold when the blocked process is resumed,
so the condition needed to ensure progress must be double-checked
after waking up.
Hansen Semantics[1]: here a process is required to exit (not suspend
in) the monitor immediately after triggering a signal, and the
previously blocked process is then resumed.
We have implemented monitors with Hoare semantics and Mesa semantics,
which are reported in the next section.
3. Implementation
The function of synchronization constructs usually requires access to
low level hardware or scheduling mechanisms, which is one of the reasons
why they are mostly implemented at the system level. Nonetheless, since
Smalltalk already provides semaphores for process synchronization, we
can build monitors on top of semaphores instead of reinventing the
wheel. The designs of the synchronizing mechanisms for Hoare and Mesa
semantics are described in the subsections.
As stated in Section 2, a monitor construct should provide encapsulation
of its variables, so that they can only be accessed through the
procedure interface. In addition, it should also enforce the rule that
only one process can be inside a monitor (however that is defined) at a
time. Unfortunately it turns out neither of them can be achieved when
monitors are implemented in libraries instead of as Smalltalk language
constructs, so we had to settle for presenting an interface that
encourages programmers to obey these rules.
The monitors are implemented as classes that should be instantiated by
programs that need synchronization:
monitor := Monitor new.
Executing code inside the monitor is done through packing the code
inside a block and sending the block with the critical: message,
monitor critical: [x := x+1].
There are no mechanisms for restricting access to variables by placing
them inside the monitor; the programmers must exercise self discipline.
Condition variables are implemented in separate classes, however you
should not instantiate these classes directly. Instead you should
send a newCondition: message to the monitor, along with a block (which
should evaluate to a boolean value) to specify the condition associated
with the variable:
positive := monitor newCondition: [counter > 0].
The monitor will verify that the block evaluates to false when the
running process tries to wait on the signal, and that the block
evaluates to true when the running process signals the condition
variable. The case where the condition does not evaluate to the
expected value is considered an error in an attempt to help programmers
catch bugs at the earliest opportunity.
To wait on a condition variable, send the wait message of the condition
variable associated with the monitor; to signal a condition variable,
send the signal message:
positive wait.
positive signal.
Both operations check that the process is currently in the monitor, and
trigger an error if the check fails.
3.1 Hoare Semantics
Our implementation of Hoare monitors uses two semaphores, mutex and
urgent, for the monitor itself, and one addition semaphore for each
condition variable. The mutex semaphore acts as a queue for processes
waiting to enter the monitor, and the urgent semaphore serves as a queue
for processes suspended as a consequence of signaling a condition
variable. Processes waiting on the mutex semaphore is only selected for
monitor entry when there are no processes waiting on the urgent
semaphore. The semaphores for condition variables simply act as queues
for processes waiting on that condition variable. This is the canonical
way of implementing monitors with semaphores[3].
3.2 Mesa Semantics
Compared with Hoare monitors, Mesa monitors offer weaker guarantees, but
they are also reputed to be easier to implement. The statement is
certainly true when the synchronization construct is integrated into the
process scheduler of the system: when a condition variable is signaled,
just move one blocked process from the associated queue into the monitor
entry queue, and there is no need to wake that process up at this point.
The key to this simple implementation is the direct access to scheduler
data structures.
Since here we must settle for using semaphores for synchronization, and
there is no portable way of moving processes between semaphores without
waking them up, the simplest implementation of Mesa monitors turns out
to be first implement a Hoare monitor, remove the code that blocks the
process signaling a condition variable, and then make each blocked
process wait on the mutex semaphore when it is awakened. This reduces
the number of semaphores in the implementation by one, but does not
otherwise make the overall structure that much simpler.
Of course, we can make use of the fact that Mesa monitors do no offer
the same degree of guarantee as Hoare monitors and further simplify the
design of our implementation. For example, if we lift the restriction
that signals should not accumulate on condition variables, a few more
lines of code can be removed from the implementation. This would not
break any program that uses Mesa monitors, but will probably make the
programs run slower due to unnecessary suspends and wakeups.
4. Example
Here is a small example that demonstrates how producer-consumer
processes can be implemented with Hoare monitors.
initialize
monitor := Monitor new.
notFull := monitor newCondition: [counter 10].
notEmpty := monitor newCondition: [counter > 0].
counter := 0
producer
monitor critical:
[counter = 10 ifTrue: [notFull wait].
counter := counter+1.
notEmpty signal]
consumer
monitor critical:
[counter = 0 ifTrue: [notEmpty wait].
counter := counter-1.
notFull signal]
5. Future Work
Currently the implementations of both kinds of monitors are done in
Smalltalk using semaphores provided by the runtime environment. Since
the issue of synchronization is closely related to the handling of
processes in the system, the next logical step would be investigating
how these constructs can be directly integrated into the scheduler.
Another problem with the current implementations is that they offer
absolutely no encapsulation to the shared variables. Unrestricted
access to these variables can lead to race conditions that are extremely
difficult to track down, therefore the current situation is not really
satisfactory. It is not clear how such encapsulation and protection can
be provided with minimal modification to the existing language.
Finally, we have implemented monitors with two of the well-known
semantics. Some Smalltalk monitor packages, such as the one developed
by Nathanael Schaerli, provide additional facilities such as timeout to
condition variable waits. It remains to be seen which, if any, of these
nonstandard functionalities would be useful to Smalltalk programmers.
6. Conclusion
We have presented Smalltalk implementations of monitors with both Hoare
semantics and Mesa semantics. In a highly concurrent programming
environment like Smalltalk, support for high-level synchronization
constructs is essential for the development of robust programs, and we
believe that the introduction of monitors should be a step in the right
direction. Even though the theoretical background of monitors are
already well understood, how they could integrate into existing
languages like Smalltalk is not all that clear, and further
investigation may provide a more complete answer to that question.
References
[1] Hansen, P.B. Operating System Principles (Prentice-Hall, 1973).
[2] Hansen, P.B. "Monitors and Concurrent Pascal: A Personal History,"
2nd ACM SIGPLAN Conf. on History of Programming Languages (1993):
pp. 1-35.
[3] Hoare, C.A.R. "Monitors: An Operating System Structuring Concept,"
Comm. of the ACM, Vol.17, No.10 (Oct 1974): pp. 549-557.
[4] Lampson B.W. and Redell D.D. "Experience with Processes and Monitors
in Mesa," Comm. of the ACM, Vol.23, No.2 (Feb 1980): pp. 105-117.
