As studied in the previous post Peterson’s Solution worked only if there were two process. A generalized solution to critical section problem is provided by Semaphores for process synchronization.
What is Semaphore?
Semaphore S is an integer variable which apart from initialization is accessed only through two standard atomic operations: wait() and signal().
Wait() was originally termed as P (proberen : to test)
Signal() was originally termed as V (verhogen: to increment)
The operations wait() and signal() are atomic which means that if a process P is executing either wait() or signal() then no other process can preempt P until it finishes wait()/signal().
Definition of wait()
Definition of signal()
wait(S)
{
while S <= 0 ; //no-operation
S--;
}
signal(S)
{
S++;
}
Working of wait()
The initial value of the Semaphore variable is ‘1’. 1 means that the resource is free and the process can enter the critical section. If the value of S is ‘0’ this means that some other process is in its critical section and thus, the current process should wait.
wait() is called before the critical section. When a process calls wait(), it checks the value of S. If the value is less than or equal to ‘0’, then the process performs no operations. Hence, the process gets stuck in the while loop and is not able to come out of the wait() function. So, it is not able to enter critical section. But if the value of S is ‘1’, then it comes out of the while loop, decrements the value of S to 0 and enters the critical section.
Working of signal()
Once the process has finished the critical section part, it calls signal(). Within the signal() function, the process increments the value of S. Finally, giving a signal to a waiting process to enter in its critical section.
Implementation of Semaphore
do {
wait(mutex);
//critical section
signal(mutex);
//remainder section
}while(TRUE);
Usage of Semaphore
Semaphore are of two types: binary and counting. In Binary semaphore, the value of S can be 0 or 1 only. An alternate name for Binary semaphores is mutex locks because they provide mutual exclusion.
Binary Semaphore is used when there is only one instance of a resource. Hence the semaphore can have two value: 1 for free and 0 for busy.
Counting Semaphore is used when there are multiple instances of the same resource. For example, there are 5 Printers. This means there are 5 instances of the resource Printer. Now 5 process can simultaneously print. So, the initial value of the semaphore variable should be 5 i.e., equal to the number of instances available.
Problem with using Semaphores for Process Synchronization
Busy waiting – suppose that a process P1 is in its critical section and another process P2 also wants to do so. So, P2 calls wait(). But, it gets stuck in the “while” loop. Now, P2 will do nothing except for checking the condition again and again. This means it will only waste the CPU cycles and perform no useful task. So, it kept the CPU busy while it was waiting for P1 to come of the critical section. Busy waiting wastes CPU cycles that some other process might be able to use productively. Such semaphores are also referred to as Spinlocks.
Solution of busy waiting – Modify the definition of wait() and signal() functions as shown below:
wait(semaphore *S) {
S->value--;
}
if (S->value < 0) { } add this process to S->list;
block();
signal(semaphore *S) {
S->value++;
if (S->value <= 0) { remove a process P from S->list;
wakeup(P);
}
}
To understand these new definitions and how they avoid busy waiting visit the link:
https://apps.uttyler.edu/Rainwater/COSC3355/Animations/semaphore.htm
The concept is explained with the help of animation.
Note: It would require you to enable Adobe Flash Player
PPT on Semaphores for Process Synchronization
Video on Semaphores for Process Synchronization
Previous Next Critical Section Problem Hardware Based Solutions