Hardware Reference
In-Depth Information
completed its instruction or been suspended trying to perform a
down
on a 0. Fig-
ure 6-28 summarizes the essential properties of the
up
and
down
system calls.
Instruction
Semaphore = 0
Semaphore > 0
Up
Semaphore = semaphore + 1;
if the other process was halted at-
tempting to complete a
down
instruction
on this semaphore, it may now com-
plete the
down
and continue running
Semaphore = semaphore + 1
Down
Process halts until the other process
up
s this semaphore
Semaphore = semaphore
−
1
Figure 6-28.
The effect of a semaphore operation.
As mentioned above, Java has a language-based solution for dealing with race
conditions, and we are discussing operating systems now. Thus we need a way to
express semaphore usage in Java, even though it is not in the language or the stan-
dard classes. We will do this by assuming that two native methods have been writ-
ten,
up
and
down
, which make the
up
and
down
system calls, respectively. By cal-
ling these with ordinary integers as parameters, we have a way to express the use
of semaphores in Java programs.
Figure 6-29 shows how the race condition can be eliminated through the use of
semaphores. Two semaphores are added to the
m
class,
available
, which is ini-
tially 100 (the buffer size), and
filled
, which is initially 0. The producer starts ex-
ecuting at P1 in Fig. 6-29 and the consumer starts executing at C1 as before. The
down
call on
filled
halts the consumer processor immediately. When the producer
has found the first prime, it calls
down
with
available
as parameter, setting
avail-
able
to 99. At P5 it calls
up
with
filled
as parameter, making
filled
1. This action
releases the consumer, which is now able to complete its suspended
down
call. At
this point,
filled
is 0 and both processes are running.
Let us now reexamine the race condition. At a certain point in time,
in
= 22,
out
= 21, the producer is at P1, and the consumer is at C5. The consumer finishes
what it was doing and gets to C1 where it calls
down
on
filled
, which had the value
1 before the call and 0 after it. The consumer then takes the last number out of the
buffer and ups
available
, making it 100. The consumer prints the number and goes
to C1. Just before the consumer can call
down
, the producer finds the next prime
and in quick succession executes statements P2, P3, and P4.
At this point,
filled
is 0. The producer is about to
up
it and the consumer is
about to call
down
. If the consumer executes its instruction first, it will be sus-
pended until the producer releases it (by calling
up
). On the other hand, if the pro-
ducer goes first, the semaphore will be set to 1 and the consumer will not be sus-
pended at all. In both cases, no wakeup is lost. This, of course, was our goal in
introducing semaphores in the first place.
The essential property of the semaphore operations is that they are indivisible.
Once a semaphore operation has been initiated, no other running process can use