Hardware Reference
In-Depth Information
the semaphore until the first process has either completed the operation or been
suspended trying. Furthermore, with semaphores, no wakeups are lost. In con-
trast, the
if
statements of Figure 6-26 are not indivisible. Between the evaluation of
the condition and the execution of the selected statement, another process can send
a wakeup signal.
In effect the problem of process synchronization has been eliminated by
declaring the
up
and
down
system calls made by
up
and
down
to be indivisible. In
order for these operations to be indivisible, the operating system must prohibit two
or more processes from using the same semaphore at the same time. At the very
least, once an
up
or
down
system call has been made, no other user code will be
run until the call has been completed. On single-processor systems, semaphores
are sometimes implemented by disabling interrupts during semaphore operations.
On multiple-processor systems, this trick does not work.
Synchronization using semaphores is a technique that works for arbitrarily
many processes. Several processes may be sleeping, attempting to complete a
down
system call on the same semaphore. When some other process finally per-
forms an
up
on that semaphore, one of the waiting processes is allowed to com-
plete its
down
and continue running. The semaphore value remains 0 and the other
processes continue waiting.
An analogy may make the nature of semaphores clearer. Imagine a picnic with
20 volleyball teams divided into 10 games (processes), each playing on its own
court, and a large basket (the semaphore) for the volleyballs. Unfortunately, only
seven volleyballs are available. At any instant, there are between zero and seven
volleyballs in the basket (the semaphore has a value between 0 and 7). Putting a
ball in the basket is an
up
because it increases the value of the semaphore; taking a
ball out of the basket is a
down
because it decreases the value.
At the start of the picnic, each court sends a player to the basket to get a vol-
leyball. Seven of them successfully manage to get a volleyball (complete the
down
); three are forced to wait for a volleyball (i.e., fail to complete the
down
).
Their games are suspended temporarily. Eventually, one of the other games fin-
ishes and puts a ball into the basket (executes an
up
). This operation allows one of
the three players waiting around the basket to get a ball (complete an unfinished
down
), allowing one game to continue. The other two games remain suspended
until two more balls are put into the basket. When two more balls come back (two
more
up
s are executed), the last two games can proceed.
In this section we will continue discussing our example systems, the Core i7
and the OMAP4430 ARM CPU. For each one we will look at an operating system
used on that processor. For the Core i7 we will use Windows; for the OMAP4430
ARM CPU we will use
UNIX
. Since
UNIX
is simpler and in many ways more
