Hardware Reference
In-Depth Information
1, assumed that the consumer was sleeping (which it was not yet), and
sent a wakeup signal that was lost because the consumer was still awake. This dif-
ficulty is known as a race condition , because the method's success depends on
who wins the race to test in and out after out is incremented.
The problem of race conditions is well known. In fact it is so serious that sev-
eral years after Java was introduced, Sun changed the Thread class and deprecated
the suspend and resume calls because they led to race conditions so often. The
solution offered was a language-based solution, but since we are studying operat-
ing systems here, we will discuss a different solution, one supported by many oper-
ating systems, including UNIX and Windows 7.
in
=
out
+
6.4.3 Process Synchronization Using Semaphores
The race condition can be solved in at least two ways. One solution consists of
equipping each process with a ''wakeup waiting bit.'' Whenever a wakeup is sent
to a process that is still running, its wakeup waiting bit is set. Whenever the proc-
ess goes to sleep when the wakeup waiting bit is set, it is immediately restarted and
the wakeup waiting bit is cleared. The wakeup waiting bit stores the superfluous
wakeup signal for future use.
Although this method solves the race condition when there are only two proc-
esses, it fails in the general case of n communicating processes because as many as
n
1 wakeups may have to be saved. Of course, each process could be equipped
with n
1 wakeup waiting bits to allow it to count to n
1 in the unary system,
but this solution is rather clumsy.
Dijkstra (1968b) proposed a more general solution to the problem of synchro-
nizing parallel processes. Somewhere in the memory are some nonnegative integer
variables called semaphores . Two system calls that operate on semaphores, up
and down , are provided by the operating system. Up adds 1 to a semaphore and
down subtracts 1 from a semaphore.
If a down operation is performed on a semaphore that is currently greater than
0, the semaphore is decremented by 1 and the process doing the down continues.
If, however, the semaphore is 0, the down cannot complete; the process doing the
down is put to sleep and remains asleep until the other process performs an up on
that semaphore. Usually sleeping processes are strung together in a queue to keep
track of them.
The up instruction checks to see if the semaphore is 0. If it is and the other
process is sleeping on it, the semaphore is increased by 1. The sleeping process
can then complete the down operation that suspended it, resetting the semaphore to
0 and allowing both processes to continue. An up instruction on a nonzero sema-
phore simply increases it by 1. In essence, a semaphore provides a counter to store
wakeups for future use, so that they will not be lost. An essential property of sem-
aphore instructions is that once a process has initiated an instruction on a sema-
phore, no other process may access the semaphore until the first one has either
 
 
Search WWH ::




Custom Search