13.3 Semaphores 587positions and the number of filled positions in the buffer (to prevent buffer
underflow and overflow). The counter component of a semaphore can be used
for this purpose. One semaphore variable—for example, emptyspots—can
use its counter to maintain the number of empty locations in a shared buf-
fer used by producers and consumers, and another—say, fullspots—can
use its counter to maintain the number of filled locations in the buffer. The
queues of these semaphores can store the descriptors of tasks that have been
forced to wait for access to the buffer. The queue of emptyspots can store
producer tasks that are waiting for available positions in the buffer; the queue
of fullspots can store consumer tasks waiting for values to be placed in
the buffer.
Our example buffer is designed as an abstract data type in which all data
enters the buffer through the subprogram DEPOSIT, and all data leaves the
buffer through the subprogram FETCH. The DEPOSIT subprogram needs only
to check with the emptyspots semaphore to see whether there are any empty
positions. If there is at least one, it can proceed with the DEPOSIT, which must
have the side effect of decrementing the counter of emptyspots. If the buffer
is full, the caller to DEPOSIT must be made to wait in the emptyspots queue
for an empty spot to become available. When the DEPOSIT is complete, the
DEPOSIT subprogram increments the counter of the fullspots semaphore
to indicate that there is one more filled location in the buffer.
The FETCH subprogram has the opposite sequence of DEPOSIT. It checks
the fullspots semaphore to see whether the buffer contains at least one
item. If it does, an item is removed and the emptyspots semaphore has its
counter incremented by 1. If the buffer is empty, the calling task is put in the
fullspots queue to wait until an item appears. When FETCH is finished, it
must increment the counter of emptyspots.
The operations on semaphore types often are not direct—they are done
through wait and release subprograms. Therefore, the DEPOSIT opera-
tion just described is actually accomplished in part by calls to wait and
release. Note that wait and release must be able to access the task-ready
queue.
The wait semaphore subprogram is used to test the counter of a given
semaphore variable. If the value is greater than zero, the caller can carry out
its operation. In this case, the counter value of the semaphore variable is dec-
remented to indicate that there is now one fewer of whatever it counts. If the
value of the counter is zero, the caller must be placed on the waiting queue
of the semaphore variable, and the processor must be given to some other
ready task.
The release semaphore subprogram is used by a task to allow some other
task to have one of whatever the counter of the specified semaphore variable
counts. If the queue of the specified semaphore variable is empty, which means
no task is waiting, release increments its counter (to indicate there is one
more of whatever is being controlled that is now available). If one or more
tasks are waiting, release moves one of them from the semaphore queue to
the ready queue.