Semaphores in Operating System

Semaphores

Semaphore is a synchronization tool denied by Dijkstra in 1965 for managing concurrent process by using the value of simple variable.
Semaphores are the main synchronization primitive used in UNIX.
A Semaphore S is a simple integer variable which can take non-negative values.
Two different operations can be performed on semaphore : wait and signal. Wait operation is also called P and signal operation is called V because in Dijkstra’s original paper the letter P is used for wait and the letter V for signal. These are the initials of the Dutch words for ‘to test’ (proberen) and ‘to increment’ (Verhogen).
Entry to critical region of active processes is controlled by the wait operation and exit from a critical region is signaled by the signal operation.
Wait Operation : It decrements the semaphore value. If the value becomes negative, then the process executing the wait is blocked.
Signal Operation : It increments the semaphore value. If the value is not positive, then process blocked by a wait operation is unblocked.

Essentially, a semaphore, such as S, indicates the availability of some resource ; if it has a non-zero positive value it is available. If it is zero it is unavailable i.e. it is being accessed by another process.
The signal operation signals the fact that some process has released a resource which can now be used by a process waiting for it.
Trying the wait operation may allow a process access to the resource (S > 0) or oy cause a process to be blocked.
The wait and signal are assumed to be atomic ; that is, they cannot be interrupted and each routine can be treated as indivisible step.
It is also important that no two processes should execute wait and signal operations on the same semaphore at the same time. Otherwise this would lead to critical section problem.

There are two variety of semaphore:

Binary Semaphore : When the integer value (S) can have only 0 or 1 value, it is known as binary semaphore.
Counting Semaphore : When the integer value (S) can be any non-negative value, it is known as counting Semaphore. Counting semaphore is also known as general semaphore.

Mutual exclusion is achieved by initializing a semaphore variable (S) to 1.
When S = 1, the first process that executes a wait will be able to immediately enter the critical section and will set S to S-lie. S = 0
Any other process that wants to enter its critical section will find it busy (i.e. S= 0) and will be blocked and will also decrement S i.e. S = S-1 (S =-1)
Any number of processes may attempt entry ; each such unsuccessful attempt results in a further decrement of the value of S.

When the first process exits from its critical region, it will execute signal and will increment the value of S.
In such situation, one of the blocked processes (if any) is removed from the queue blocked processes associated with the semaphore and is put in a ready state.
When it is next scheduled by the operating system, it may enter critical section.

Like hardware instruction, semaphores also suffer from the problem of busy-waiting.
When a process is in its critical section, any other process that tries to enter its critical section must loop continuously in the entry code. This is known as busy waiting.
Such a continuous looping is a problem in a real multiprogramming system, where a single CPU is shared among many processes.
Busy waiting wastes the CPU cycles that some other process might be able to use productively.
This kind of semaphores, that implements busy waiting is known as spin lock as the process spins while waiting for a lock.
Spin locks are useful in multiprocessor system.
The advantage of spin lock is that no context switch is required when a process must wait on a lock, and a context switch may take considerable time. Thus when locks are expected to be held for short times, spinlocks are used.

To implement semaphores without busy waiting, a waiting queue is associated with each semaphore.
Each entry in a waiting queue has two data items : value and a pointer to next record in the list.

For such an implementation, two more operations are defined:

Block : To place the process invoking the operation on the appropriate waiting
Wakeup : To remove one of processes in the waiting queue and place it in ready queue.

The definitions of wait and signal operations are also modified.
In this situation, when a process executes the wait and finds that the semaphore value is not positive, it must wait.
However, rather than busy waiting the process is blocked. The block operation process into waiting queue associated with the semaphore. The state of process is then change to waiting state.
Then, the control is transferred to the CPU scheduler, which selects another process to execute.
A process that is blocked, waiting on a semaphore is restarted when some other process executes a signal operation.

Such a process is restored by a wakeup operation which changes the process from the waiting state to the ready state. The process is then placed in the ready queue.
The block operation suspends the process that invokes it. The wakeup (P) operation resumes the execution of a blocked process P. Both block and wakeup operations are provided by the OS as basic system calls.

Busy-Waiting : Like hardware instructions, semaphores also suffer from the problem of busy waiting.
Processes can be deadlocked : The implementation of semaphore with a waiting queue may result in a situation where two or more processes are waiting indefinitely for an event that can be caused only by one of the waiting processes. Such a situation mar lead to deadlock.
Problem of indefinite blocking or starvation : Indefinite blocking of processes may occur if we add and remove processes from the waiting queue associated with a semaphore in LIFO order.