PROCESSES AND THREADS
A enters critical region
A leaves critical region
B attempts to
Mutual exclusion using critical regions.
2.3.3 Mutual Exclusion with Busy Waiting
In this section we will examine various proposals for achieving mutual exclu-
sion, so that while one process is busy updating shared memory in its critical re-
gion, no other process will enter
critical region and cause trouble.
On a single-processor system, the simplest solution is to have each process dis-
able all interrupts just after entering its critical region and re-enable them just be-
fore leaving it. With interrupts disabled, no clock interrupts can occur.
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.
Thus, once a process has disabled interrupts, it can examine and update the shared
memory without fear that any other process will intervene.
This approach is generally unattractive because it is unwise to give user proc-
esses the power to turn off interrupts. What if one of them did it, and never turned
them on again? That could be the end of the system. Furthermore, if the system is
a multiprocessor (with two or more CPUs) disabling interrupts affects only the
CPU that executed the
instruction. The other ones will continue running
and can access the shared memory.
On the other hand, it is frequently convenient for the kernel itself to disable in-
terrupts for a few instructions while it is updating variables or especially lists.
an interrupt occurrs while the list of ready processes, for example, is in an incon-
sistent state, race conditions could occur. The conclusion is: disabling interrupts is
often a useful technique within the operating system itself but is not appropriate 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 many machines, and eight, 16, or 32 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. Conse-
quently, more sophisticated schemes are needed.
As a second attempt, let us look for a software solution. Consider having a sin-
gle, shared (lock) variable, initially 0.
When a process wants to enter its critical re-
gion, 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.
Thus, a 0 means that no process is in its critical region, and a 1 means that some
process is in its critical region.
Unfortunately, this idea contains exactly the same fatal flaw that we saw in the
spooler directory. Suppose that one process reads the lock and sees that it is 0.
fore 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 proc-
esses 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 finished its second check.
A third approach to the mutual exclusion problem is shown in Fig. 2-23. This
program fragment, like nearly all the others in this book, is written in C.
chosen here because real operating systems are virtually always written in C (or
occasionally C++), but hardly ever in languages like Java, Python, or Haskell. C is
powerful, efficient, and predictable, characteristics critical for writing operating
systems. Java, for example, 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 col-
lection in C.
A quantitative comparison of C, C++, Java, and four other languages
is given by Prechelt (2000).
In Fig. 2-23, the integer variable
, initially 0, keeps track of whose turn it is
to enter the critical region and examine or update the shared memory. Initially,
process 0 inspects
, finds it to be 0, and enters its critical region. Process 1 also