- Semaphore was proposed by Dijkstra in 1965 which is a very significant technique to manage concurrent processes by using a simple integer value, which is known as a semaphore. Semaphore is simply a variable which is non-negative and shared between threads. This variable is used to solve the critical section problem and to achieve process synchronization in the multiprocessing environment. Semaphores are of two types:
- Binary Semaphore – This is also known as mutex lock. It can have only two values – 0 and 1. Its value is initialized to 1. It is used to implement the solution of critical section problem with multiple processes.
- Counting Semaphore – Its value can range over an unrestricted domain. It is used to control access to a resource that has multiple instances.
Problem in this implementation of semaphore Whenever any process waits then it continuously checks for semaphore value (look at this line while (s==0); in P operation) and waste CPU cycle. To avoid this another implementation is provided below.
Implementation of counting semaphore
struct Semaphore {
int value;
Queue<process> q;
} P(Semaphore s)
{
s.value = s.value - 1;
if (s.value < 0) {
q.push(p);
block();
}
else
return;
}
V(Semaphore s)
{
s.value = s.value + 1;
if (s.value <= 0) {
q.pop();
wakeup(p);
}
else
return;
}
|
In this implementation whenever process waits it is added to a waiting queue of processes associated with that semaphore. This is done through system call block() on that process. When a process is completed it calls signal function and one process in the queue is resumed. It uses wakeup() system call.
Problem
The enter_CS( ) and leave_CS( ) functions to implement critical section of a process are realized using test and set instruction as follows-
In the above solution, X is a memory location associated with the CS and is initialized to 0.
> Computer and Education