[Chapter Nineteen][Previous]
[Next] [Art of
Assembly][Randall Hyde]
Art of Assembly: Chapter Nineteen
- 19.5.2 - Semaphores
19.5.2 Semaphores
A semaphore is an object with two basic methods: wait and signal (or
release). To use a semaphore, you create a semaphore variable (an instance)
for a particular critical region or other resource you want to protect.
When a process wants to use a given resource, it waits on the semaphore.
If no other process is currently using the resource, then the wait call
sets the semaphore to in-use and immediately returns to the process. At
that time, the process has exclusive access to the resource. If some other
process is already using the resource (e.g., is in the critical region),
then the semaphore blocks the current process by moving it off the run queue
and onto the semaphore queue. When the process that currently holds the
resource releases it, the release operation removes the first waiting process
from the semaphore queue and places it back in the run queue. At the next
available time slice, that new process returns from its wait call and can
enter its critical region.
Semaphores solve the two important problems with the busy-waiting loop described
in the previous section. First, when a process waits and the semaphore blocks
the process, that process is no longer on the run queue, so it consumes
no more CPU time until the point that a release operation places it back
onto the run queue. So unlike busy-waiting, the semaphore mechanism does
not waste (as much) CPU time on processes that are waiting for some resource.
Semaphores can also solve the starvation problem. The wait operation, when
blocking a process, can place it at the end of a FIFO semaphore queue. The
release operation can fetch a new process from the front of the FIFO queue
to place back on to the run queue. This policy ensures that each process
entering the semaphore queue gets equal priority access to the resource.
Implementing semaphores is an easy task. A semaphore generally consists
of an integer variable and a queue. The system initializes the integer variable
with the number of processes than may share the resource at one time (this
value is usually one for critical regions and other resources requiring
exclusive access). The wait operation decrements this variable. If the result
is greater than or equal to zero, the wait function simply returns to the
caller; if the result is less than zero, the wait function saves the machine
state, moves the process' pcb from the run queue to the semaphore's
queue, and then switches the CPU to a different process (i.e., a yield
call).
The release function is almost the converse. It increments the integer value.
If the result is not one, the release function moves a pcb
from the front of the semaphore queue to the run queue. If the integer value
becomes one, there are no more processes on the semaphore queue, so the
release function simply returns to the caller. Note that the release function
does not activate the process it removes from the semaphore process queue.
It simply places that process in the run queue. Control always returns to
the process that made the release call (unless, of course, a timer interrupt
occurs while executing the release function).
Of course, any time you manipulate the system's run queue you are in a critical
region. Therefore, we seem to have a minor problem here - the whole purpose
of a semaphore is to protect a critical region, yet the semaphore itself
has a critical region we need to protect. This seems to involve circular
reasoning. However, this problem is easily solved. Remember, the main reasons
we do not turn off interrupts to protect a critical region is because that
critical region may take a long time to execute or it may call other routines
that turn the interrupts back on. The critical section in a semaphore is
very short and does not call any other routines. Therefore, briefly turning
off the interrupts while in the semaphore's critical region is perfectly
reasonable.
If you are not allowed to turn off interrupts, you can always use a test
and set instruction in a loop to protect a critical region. Although this
introduces a busy-waiting loop, it turns out that you will never wait more
than two time slices before exiting the busy-waiting loop, so you do not
waste much CPU time waiting to enter the semaphore's critical region.
Although semaphores solve the two major problems with the busy waiting loop,
it is very easy to get into trouble when using semaphores. For example,
if a process waits on a semaphore and the semaphore grants exclusive access
to the associate resource, then that process never releases the semaphore,
any processes waiting on that semaphore will be suspended indefinitely.
Likewise, any process that waits on the same semaphore twice without a release
in-between will suspend itself, and any other processes that wait on that
semaphore, indefinitely. Any process that does not release a resource it
no longer needs violates the concept of a semaphore and is a logic error
in the program. There are also some problems that may develop if a process
waits on multiple semaphores before releasing any. We will return to that
problem in the section on deadlocks (see "Deadlock"
on page 1146).
Although we could write our own semaphore package (and there is good reason
to), the Standard Library process package provides its own wait and release
calls along with a definition for a semaphore variable. The next section
describes those calls.
- 19.5.2 - Semaphores
Art of Assembly: Chapter Nineteen - 29 SEP 1996
[Chapter Nineteen][Previous]
[Next] [Art of
Assembly][Randall Hyde]