[ENH] Monitor for higher-level process synchronization

Stephane Ducasse ducasse at iam.unibe.ch
Sun Jul 6 14:53:28 UTC 2003


Hi

I resend this now that we have a better harvesting process.

Stef

Begin forwarded message:

> From: Nathanael Schärli <n.schaerli at gmx.net>
> Date: Mon Jul 1, 2002  11:17:44 PM Europe/Zurich
> To: squeak-dev at lists.squeakfoundation.org
> Subject: [ENH] Monitor for higher-level process synchronization
> Reply-To: squeak-dev at lists.squeakfoundation.org
>
> Hey,
>
> I haven been programming some multi-threaded applications in Squeak, 
> and
> once more I got reminded that it is really hard and cumbersome to write
> safe and understandable code by just using semaphores as the only means
> of synchronization.
>
> Having a look at the class SharedQueue is a good example: At a first
> glance, it seems to be doing what it is supposed to, but when you look
> at it more closely, you'll notice that there are about 5 or more
> synchronization bugs in it.
>
> I believe that it is possible to avoid most of these problems by using 
> a
> higher-level synchronization mechanism, and therefore I implemented a
> variant of the well-known Monitor data-structure in Squeak. (In fact, I
> ported an implementation I did in VW about 2 years ago).
> This monior has the following properties:
>
> 1) At any time, only one process can be executing code inside a critcal
> section of a monitor.
> 2) A monitor is reentrant, which means that the active process in a
> monitor does never get blocked when it enters a (nested) critical
> section of the same monitor.
> 3) Inside a critcal section, a process can wait for an event that may 
> be
> coupled to a certain condition. If the condition is not fulfilled, the
> process leaves the monitor temporarily (in order to let other processes
> enter) and waits until another process signals the event. Then, the
> original process checks the condition again (this often necessary
> because the state of the monitor could have changed in the meantime) 
> and
> continues if it is fulfilled.
> 4) The monitor is fair, which means that the process that is waiting on
> a signaled condition the longest gets activated first.
> 5) The monitor allows to define timeouts after which a process gets
> activated automatically.
>
> There are several important advantages of such a Monitor over a
> Semaphore:
> 1) A process autimatically leaves the monitor when a condition is not
> fulfilled.
> 2) When a blocked process is woken up, the condition is always
> rechecked.
> 3) Point 1) and 2) together guarantee that the code following the
> condition is only executed if the condition holds. In addition, busy
> waits will never occur.
> 4) The monitor is reentrant
>
>
> In order to illustrate how a Monitor can drastically simplify process
> synchronization, let's assume that we would like to implement a
> thread-safe BoundedCounter with the following properties:
> - The counter provides methods #inc and #dec, which increment and
> decrement the counter.
> - If the value of the counter is equal to a certain #lowerBound (e.g.
> 0), every process invoking #dec gets blocked until the decrementation
> can be performed without getting a value less than #lowerBound.
> - Similarly, inc blocks processes in order to avoid values bigger than
> #upperBound (e.g. 10)
>
> Without a monitor, we typically use 3 semaphores (mutex, incPossible,
> decPossible) to safely implement this behavior. And as you can see, the
> whole synchronization is rather complex because the the usage of the
> semaphores have to be nested in order to avoid unsafe situations or
> deadlocks:
>
> BoundedCounter>>dec
> 	| done |
> 	done _ false.
> 	[done] whileFalse: [
> 		mutex critical: [
> 			value > self lowerBound ifTrue: [
> 				value _ value - 1.
> 				done _ true.
> 				incPossible signal]].
> 		done ifFalse: [decPossible wait]].
>
> BoundedCounter>>inc
> 	| done |
> 	done _ false.
> 	[done] whileFalse: [
> 		mutex critical: [
> 			value < self upperBound ifTrue: [
> 				value _ value + 1.
> 				done _ true.
> 				decPossible signal]].
> 		done ifFalse: [incPossible wait]].
>
>
> Instead of using 3 Semaphores, we can use just one Monitor (monitor).
> Like that, the code would look as follows:
>
> BoundedCounter>>dec
> 	monitor critical: [
> 		monitor waitUntil: [value > self lowerBound].
> 		value = self upperBound ifTrue: [monitor signalAll].
> 		value _ value - 1].
>
> BoundedCounter>>inc
> 	monitor critical: [
> 		monitor waitUntil: [value < self upperBound].
> 		value = self lowerBound ifTrue: [monitor signalAll].
> 		value _ value + 1].
>
> Let's have a closer look at what happens:
> - Invocation of #critical: ensures that only one process can be
> modifying the counter at a time.
> - Invocation of #waitUntil: guarantees that the argument condition 
> holds
> when the following code is executed. As long as this condition does not
> hold, the process gets blocked and leaves the critical section so that
> another process can enter.
> - Invocation of #signalAll wakes up all the processes that have been
> blocked because there waiting condition was not fulfilled. As explained
> above, the conditio gets rechecked before the following code is
> executed.
>
>
> As you can see, this code is already a lot nicer than the original one.
> However, using more advanced features of the monitor can make it even
> nicer:
>
> BoundedCounter>>dec
> 	monitor critical: [
> 		monitor waitUntil: [value > self lowerBound] for:
> #decPossible.
> 		monitor signal: #incPossible.
> 		value _ value - 1].
>
> BoundedCounter>>inc
> 	monitor critical: [
> 		monitor waitUntil: [value < self upperBound] for:
> #incPossible.
> 		monitor signal: #decPossible.
> 		value _ value + 1].
>
> The difference to the implementation above are as follows:
> - The method #waitUntil:for: is very similar to the #waitUntil:. The
> only difference is the fact that a blocked process only gets woken up 
> if
> the event provided as the second argument is signaled.
> - The method #signal: is very similar to #signalAll. The difference to
> #signalAll is that
> #signal: only wakes up *one* process that is waiting for the event
> specified as the argument.
>
>
> Well, you can find a complete documentation of the Monitor in the
> changeset "Monitor.1.cs" that is attached to this email (read the class
> comment). In addition, there is a changeset "MonitorTest.1.cs" that
> contains some SUnit tests, and a file BoundedCounter.1.cs that contains
> this example.
>
> Please let me know if you find bugs or have suggestions for changes...
>
>
> Cheers,
> Nathanael
>
> BTW: One remark for the ones that already know the Java synchronization
> mechanism: This Monitor implementation can be considered as a more
> powerful version of the Java synchronization mechanism. Just replace:
>
> #critical: ...  ->  synchronized() { ... }
> #wait  ->  wait()
> #signal  ->  notify()
> #signalAll  ->  notifyAll()
-------------- next part --------------
A non-text attachment was scrubbed...
Name: BoundedCounter.1.cs
Type: application/octet-stream
Size: 3014 bytes
Desc: not available
Url : http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20030706/55bad4fb/BoundedCounter.1.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Monitor.1.cs
Type: application/octet-stream
Size: 18244 bytes
Desc: not available
Url : http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20030706/55bad4fb/Monitor.1.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: MonitorTest.1.cs
Type: application/octet-stream
Size: 4931 bytes
Desc: not available
Url : http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20030706/55bad4fb/MonitorTest.1.obj


More information about the Squeak-dev mailing list