More on Conditional Critical Regions

region x when B do S;

using semaphores?

Would this one do?

	while not B do ;
	wait(mutex);
	S;
	signal(mutex);

How about this one?

	wait(mutex);
	while not B do
	begin
		signal(mutex);
		wait(mutex);
	end;
	S;
	signal(mutex);

But the busy loop is just too tight, wasting a lot of CPU cycles. This one is more like it:

	wait(mutex);
	while not B do
	begin
		signal(mutex);
		delay;
		wait(mutex);
	end;
	S;
	signal(mutex);

Three-Semaphore Solution

The following is a graphical representation of that implementation.

Note that B could be different for different processes, as is the case of the bounded buffer problem:

	producer: ... region buffer when count < n ...
	consumer: ... region buffer when count > 0 ...

There are three queues, guarded by three different binary semaphores:

• The mutex queue (Q0) is for entry.
• The first-delay queue (Q1) is for those processes whose B has just been tested to be false. Their B cannot become true unless some process has successfully executed S at a later time.
• The second-delay queue (Q2) is for processes coming from Q1 whose B might have become true as a result of an execution of S by some process. These processes then take turns to reevaluate their B.

The entry gate is open if and only if

• no process is executing S; and
• no process is in the second-delay queue (Q2).

When some process is executing S, all other activities inside the region come to a standstill, and no processes are allowed to enter the region through the entry gate.

When the process finishes executing S, it initiates a transfer of all processes in Q1 to Q2. This transfer happens in a cascading fashion: the first process in Q1 is awaken, which awakens the next, and so on until all processes in Q1 have been awakened and transferred to Q2. Then one process in Q2 is allowed to reevaluate its B. If this process' B is true, it proceeds to execute S; otherwise, it rejoins Q1 and lets the second process in Q2 to reevaluate its B, and so on.

Only when Q2 becomes empty (and no process is executing S) would the entry gate be reopened, letting in new processes.

The three semaphores, mutex, first-delay, second-delay, are called split binary semaphores as they satisfy the following invariant property.

0 <= mutex + first-delay + second-delay <= 1

In other words, at most one of the three black dots in the picture above would turn "green" (=1) at any one time.

Can we use just one queue instead of two inside the region? The answer seems to be no, because if a process in Q2 immediately rejoins Q2 after reevaluating its B to be false, then we will be stuck in an infinite cycle of reevaluation by processes in Q2.

Two-Semaphore Solution Revisited

	// entry:
        wait(mutex);
        delayCnt++;
        while (not B) {
                signal(mutex);
                wait(delay);
                wait(mutex);
        }
        delayCnt--;

        S;

        // exit:
        for (i = 1; i <= delayCnt; i++)
                signal(delay);
        signal(mutex);

The delay queue here is equivalent to Q1 in the previous solution: it holds processes waiting for their B to be changed (possibly) by some process executing S. Once the latter happens and completes, these processes (all of them) are transferred to the mutex queue so that they can reevaluate their B.

The above code has a little bug: the for line should read as follows since all the processes in the delay queue would be transferred.

	for ( ; delayCnt > 0; delayCnt--)
		signal(delay);

(This morning in class I spotted another bug: processes waking up from the delay will join the mutex queue, but they are not counted with delayCnt in the solution as shown above. These are big authors in the field, but see how careless they had been. The corrected code follows.)

	// entry:
        wait(mutex);
        while (not B) {
		delayCnt++;
                signal(mutex);
                wait(delay);
                wait(mutex);
        }

        S;

        // exit:
	for ( ; delayCnt > 0; delayCnt--)
		signal(delay);
        signal(mutex);

Here is the situation of this simpler solution:

One obvious difference between this solution and the previous one is that in the current solution, those transferred processes do not get to evaluate their B right away; they have to rejoin the mutex queue at the entry and wait for their turn to evaluate B again; whereas in the previous solution, processes transferred to Q2 immediately get to reevaluate their B albeit one after another.

• L. Bic and A.C. Shaw, The Logical Design of Operating Systems, 2nd edition, Prentice-Hall, 1988.

A Bit of History

• E.W. Dijkstra, "On two beautiful solutions designed by Martin Rem", in Selected Writings on Computing: A Personal Perspective, Springer-Verlag, 1982.
• C.A.R. Hoare, "Towards a theory of parallel programming", in Operating Systems Techniques, Academic Press, 1972.
• J.L.W. Kessels and A.J. Martin, "Two implementations of the conditional critical region using a split binary semaphore", Information Processing Letters, Vol. 8, No. 2, 1979.
• H.A. Schmid, "On the efficient implementation of conditional critical regions and the construction of monitors", Acta Informatica, Vol. 6, 1976.