Mutual Exclusion with Busy Waiting

Mutual Exclusion with Busy Waiting

In this section we will study various proposals for achieving mutual exclusion, so that while one process is busy updating shared memory in its critical region, no other process will go into its critical region and cause trouble.

Disabling Interrupts

On a single-processor system, the simplest solution is to have each process disable all interrupts just after entering its critical region and re-enable them just before leaving it. With interrupts disabled, no clock interrupts can happen. The CPU is only switched from process to process as a result of clock or other interrupts, after all, and with interrupts turned off the CPU will not be switched to another process. In this way, once a process has disabled interrupts, it can inspect and update the shared memory without fear that any other process will interfere.

This approach is usually unattractive because it is unwise to give user processes the power to turn off interrupts. Suppose that one of them did it, and never turned them on again? That could be the end of the system. Moreover, if the system is a multiprocessor (with two or possibly more CPUs) disabling interrupts affects only the CPU that executed the disable instruction. The other ones will continue running and can access the shared memory.

On the other hand, it is often convenient for the kernel itself to disable interrupts for a few instructions while it is updating variables or lists. If an interrupt happened while the list of ready processes, for instance, was in an inconsistent state, race conditions could happen. The conclusion is: disabling interrupts is frequently a useful technique within the operating system itself but is not suitable as a general mutual exclusion mechanism for user processes.

The possibility of achieving mutual exclusion by disabling interrupts-even within the kernel - is becoming less every day due to the increasing number of multicore chips even in low-end PCs. Two cores are already common, four are present in high-end machines, and eight or 16 are not far behind. In a multicore (i.e., multiprocessor system) disabling the interrupts of one CPU does not prevent other CPUs from interfering with operations the first CPU is performing. As a result, more complicated schemes are required.

Lock Variables

As a second attempt, let us look for a software solution. Consider having a single, shared (lock) variable, initially 0. When a process wants to enter its critical region, it first tests the lock. If the lock is 0, the process sets it to 1 and enters the critical region. If the lock is already 1, the process just waits until it becomes 0. In this way a 0 means that no process is in its critical region, and a 1 means that some process is in its critical region.

Unluckily, this idea includes exactly the same fatal flaw that we saw in the spooler directory. Assume that one process reads the lock and sees that it is 0. Before it can set the lock to 1, another process is scheduled, runs, and sets the lock to 1. When the first process runs again, it will also set the lock to 1, and two processes will be in their critical regions at the same time.

Now you might think that we could get around this problem by first reading out the lock value, then checking it again just before storing into it, but that really does not help. The race now occurs if the second process modifies the lock just after the first process has completed its second check.

Strict Alternation

A third approach to the mutual exclusion problem is shown in figure 1. This program fragment, like nearly all the others in this blog, is  written in C. C was chosen here because real operating systems are virtually always written in C (or occasionally C++), but hardly ever in  languages like Java, Modula 3, or Pascal. C is powerful, efficient, and predictable, characteristics critical for writing operating systems. Java, for instance, is not predictable because it might run out of storage at a critical moment and need to invoke the garbage collector to reclaim memory at a most inopportune time. This cannot happen in C because there is no garbage collection in C. A quantitative comparison of C, C++, Java, and four other languages is given in (Prechelt, 2000).

A proposed solution to the critical region problem

In figure 1, the integer variable turn, initially 0, keeps track of whose turn it is to enter the critical region and examine or update the shared memory. At first, process 0 inspects turn, finds it to be 0, and enters its critical region. Process 1 also finds it to be 0 and therefore sits in a tight loop continually testing turn to see when it becomes 1. Continuously testing a variable until some value appears is called busy waiting. It should generally be avoided, since it wastes CPU time. Only when there is a reasonable expectation that the wait will be short is busy waiting used. A lock that uses busy waiting is called a spin lock.

When process 0 leaves the critical region, it sets turn to 1, to allow process 1 to enter its critical region. Assume that process 1 finishes its critical region quickly, so that both processes are in their noncritical regions, with turn set to 0. Now process 0 executes its whole loop quickly, exiting its critical region and setting turn to 1. At this point turn is 1 and both processes are executing in their noncritical regions.

Suddenly, process 0 finishes its noncritical region and goes back to the top of its loop. Unluckily, it is not allowed to enter its critical region now, because turn is 1 and process 1 is busy with its noncritical region. It hangs in its while loop until process 1 sets turn to 0. Put differently, taking turns is not a good idea when one of the processes is much slower than the other.

This situation violates condition 3 set out above: process 0 is being blocked by a process not in its critical region. Going back to the spooler directory discussed above, if we now relate the critical region with reading and writing the spooler directory, process 0 would not be allowed to print another file because process 1 was doing something else.

Actually, this solution requires that the two processes strictly alternate in entering their critical regions, for instance, in spooling files. Neither one would be permitted to spool two in a row. While this algorithm does avoid all races, it is not in fact a serious candidate as a solution because it violates condition 3.


Tags

shared memory, kernel, multicore chips, spin lock