Semaphores

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.