Semaphores are integer variables
that are used to solve the critical section problem by using two atomic
operations, wait and signal that are used for process synchronization.
The definitions of wait and
signal are as follows:
1.
Wait
The wait operation decrements the
value of its argument S, if it is positive. If S is negative or zero, then no
operation is performed.
wait(S)
{
while (S<=0);
S--;
}
2.
Signal
The signal operation increments
the value of its argument S.
signal(S)
{
S++;
}
All modifications to the integer
value of the semaphore in the wait() and signal() operations must be executed
indivisibly. That is, when one process modifies the semaphore value, no other
process can simultaneously modify that same semaphore value. In addition, in wait(S),
the testing of the integer value of S (S ≤ 0), as well as its possible
modification (S--), must be executed without interruption.
1. Semaphore
Usage
Semaphores can take on one of two
forms:
- Binary semaphores can
take on one of two values, 0 or 1. They can be used to solve the critical
section problem and can be used as mutexes on systems that do not provide
a separate mutex mechanism.
- Counting semaphores can
take on any integer value, which is equal to available resources. The
counter is initialized to the number of such resources available in the
system, and whenever the counting semaphore is greater than zero, and then
a process can enter a critical section and use one of the resources. When
the counter gets to zero ( or negative in some implementations ), then the
process blocks until another process frees up a resource and increments
the counting semaphore with a signal call.
Semaphores can also be used to
synchronize certain operations between processes.
For example, suppose it is
important that process P1 execute statement S1 before process P2 executes
statement S2.
- First
create a semaphore named sync that is shared by the two processes, and
initialize it to zero.
- Then
in process P1 we insert the code:
S1;
signal( sync);
- and
in process P2 we insert the code:
wait(
sync );
S2;
- Because
sync was initialized to 0, process P2 will block on the wait until after
P1 executes the call to signal.
2. Semaphore
Implementation
The big problem with semaphores
is the busy loop in the wait call, which consumes CPU cycles without doing any
useful work. This type of lock is known as a spinlock, because the
lock just sits there and spins while it waits. While this is generally a bad
thing, it does have the advantage of not invoking context switches, and so it
is sometimes used in multi-processing systems when the wait time is expected to
be short - One thread spins on one processor while another completes their
critical section on another processor.
An alternative approach is to
block a process when it is forced to wait for an available semaphore, and swap
it out of the CPU. In this implementation each semaphore needs to maintain a
list of processes that are blocked waiting for it, so that one of the processes
can be woken up and swapped back in when the semaphore becomes available. The
new definition of a semaphore and the corresponding wait and signal operations
are follows:
Each semaphore has an integer value
and a list of processes list. When a process must wait on a semaphore, it is
added to the list of processes. A signal() operation removes one process from
the list of waiting processes and awakens that process.
The wait() and signal() semaphore
operation can be defined as:
In this implementation the value
of the semaphore can actually become negative, in which case its magnitude is
the number of processes waiting for that semaphore. This is a result of
decrementing the counter before checking its value.
Key to the success of semaphores
is that the wait and signal operations be atomic, that is no other process can
execute a wait or signal on the same semaphore at the same time. ( Other
processes could be allowed to do other things, including working with other
semaphores, they just can't have access to this semaphore. )
On single processors this can be
implemented by disabling interrupts during the execution of wait and signal;
Multiprocessor systems have to use more complex methods, including the use of
spinlocking.
3. Deadlocks and
Starvation
One important problem that can
arise when using semaphores to block processes waiting for a limited resource
is the problem of deadlocks, which occur when multiple processes
are blocked, each waiting for a resource that can only be freed by one of the
other ( blocked ) processes.
Suppose that P0 executes wait(S)
and then P1 executes wait(Q).When P0 executes wait(Q), it must
wait until P1 executes signal(Q). Similarly, when P1 executes wait(S),
it must wait until P0 executes signal(S). Since these signal() operations
cannot be executed, P0 and P1 are deadlocked.
Another problem to consider is
that of starvation, in which one or more processes gets
blocked forever, and never get a chance to take their turn in the critical
section. Indefinite blocking may occur if processes are removed from the list
associated with a semaphore in LIFO (last-in, first-out) order.
4. Priority
Inversion
A scheduling challenge arises
when a high-priority process gets blocked waiting for a resource that is
currently held by a low-priority process.
If the low-priority process gets
pre-empted by one or more medium-priority processes, then the high-priority
process is essentially made to wait for the medium priority processes to finish
before the low-priority process can release the needed resource, causing
a priority inversion. If there are enough
medium-priority processes, then the high-priority process may be forced to wait
for a very long time.
One solution is a priority-inheritance
protocol, in which a low-priority process holding a resource for
which a high-priority process is waiting will temporarily inherit the high
priority from the waiting process. This prevents the medium-priority processes
from preempting the low-priority process until it releases the resource,
blocking the priority inversion problem.
