Semaphore in OS-

Before you go through this article, make sure that you have gone through the previous article on Semaphores in OS.

We have discussed-

• A semaphore is a simple integer variable used to provide synchronization among the processes.
• There are mainly two types of semaphores-

In this article, we will discuss practice problems based on Binary Semaphores.

PRACTICE PROBLEMS BASED ON BINARY SEMAPHORES IN OS-

Problem-01:

Each process P_i, i = 1, 2, …, 9 is coded as follows-

repeat
   P(mutex)
   { Critical Section }
   V(mutex)
forever

The code for P₁₀ is identical except that it uses V(mutex) in place of P(mutex). What is the largest number of processes that can be inside the critical section at any moment?

1. 1
2. 2
3. 3
4. None of these

Solution-

Code for Processes P₁, P₂, … , P₉

repeat
   P(mutex)
   { Critical Section }
   V(mutex)
forever

Code for Process P₁₀

repeat
   V(mutex)
   { Critical Section }
   V(mutex)
forever

Consider mutex is initialized with 1.

Then-

• All the 10 processes may be present inside the critical section at the same time.
• If there would have been more number of processes, then they could also be present inside the critical section at the same time.

The explanation is as follows-

Explanation-

Scene-01:

• Initially, process P₁ arrives.
• It performs the wait operation on mutex and sets its value to 0.
• It then enters the critical section.

Scene-02:

• Consider the processes P₂, P₃, … , P₉ arrives when process P₁ is executing the critical section.
• All the other processes get blocked and are put to sleep in the waiting list.

Scene-03:

• Process P₁₀ arrives.
• It performs the signal operation on mutex.
• It selects one process from the waiting list say process P₂ and wakes it up.
• Process P₂ can now enter the critical section (P₁ is already present).
• Now, process P₁₀ enters the critical section (P₁ and P₂ are already present).
• After executing critical section, during exit, it again performs the signal operation on mutex.
• It selects one process from the waiting list say process P₃ and wakes it up.
• Process P₃ can now enter the critical section (P₁ and P₂ are already present).
• Process P₁₀ may keep on executing repeatedly.
• It wakes up 2 processes each time during its course of execution.
• In this manner, all the processes blocked in the waiting list may get entry inside the critical section.

Thus, Option (D) is correct.

Problem-02:

Let m[0]…m[4] be mutexes (binary semaphores) and P[0]…P[4] be processes. Suppose each process P[i] executes the following:

wait(m[i]);

wait(m[(i+1) mod 4]);

………….

release(m[i]);

release(m[(i+1) mod 4]);

This could cause-

1. Thrashing
2. Deadlock
3. Starvation but not deadlock
4. None of the above

Solution-

Given processes have to execute the wait operations as-

• Process P₀ : wait(m[0]); wait(m[1]);
• Process P₁ : wait(m[1]); wait(m[2]);
• Process P₂ : wait(m[2]); wait(m[3]);
• Process P₃ : wait(m[3]); wait(m[0]);
• Process P₄ : wait(m[4]); wait(m[1]);

Now,

• A deadlock may be caused when different processes execute the wait operations on mutexes.
• The occurrence of following scenes will give birth to a deadlock.

Scene-01:

• Process P₀ arrives.
• It executes wait(m[0]) and gets preempted.

Scene-02:

• Process P₁ gets scheduled.
• It executes wait(m[1]) and gets preempted.

Scene-03:

• Process P₂ gets scheduled.
• It executes wait(m[2]) and gets preempted.

Scene-04:

• Process P₃ gets scheduled.
• It executes wait(m[3]) and gets preempted.

Scene-05:

• Process P₄ gets scheduled.
• It executes wait(m[4]) and gets preempted.

Now,

• The system is in a deadlock state since no process can proceed its execution.
• Thus, Option (B) is correct.

Problem-03:

In the above question, which of the following pairs of processes may be present inside the critical section at the same time?

1. (P₀, P₂)
2. (P₁, P₃)
3. (P₂, P₄)
4. (P₃, P₄)
5. All of these

Solution-

• All the given pair of processes in options execute wait operation on different mutexes.
• Hence, they can get entry inside the critical section at the same time.
• Thus, Option (E) is correct.

NOTE-

• Mutual exclusion is violated here.
• Maximum number of processes that may be present inside the critical section at the same time = 2.

Problem-04:

The following program consists of 3 concurrent processes and 3 binary semaphores. The semaphores are initialized as S0 = 1, S1 = 0 and S2 = 0.

How many times will process P0 print ‘0’?

1. At least twice
2. Exactly twice
3. Exactly thrice
4. Exactly once

Solution-

Maximum Number Of Times Process P0 Can Print ‘0’-

The occurrence of following scenes will cause process P0 to print ‘0’ three times-

Scene-01:

• Process P0 arrives.
• It executes wait operation on semaphore S0 successfully. Now, S0 = 0.
• It then prints ‘0’. (1^st time)
• It executes signal operation on semaphore S1. Now, S1 = 1.
• It executes signal operation on semaphore S2. Now, S2 = 1.
• While loop causes process P0 to execute again.
• It executes wait operation on semaphore S0 unsuccessfully and gets blocked.

Scene-02:

• Process P1 gets scheduled.
• It executes wait operation on semaphore S1 successfully. Now, S1 = 0.
• It executes signal operation on semaphore S0 which wakes up the process P0.
• The execution of process P1 is completed.

Scene-03:

• Process P0 gets scheduled again.
• It prints ‘0’. (2^nd time)
• It executes signal operation on semaphore S1. Now, S1 = 1.
• It executes signal operation on semaphore S2. Now, S2 = 1.
• While loop causes process P0 to execute again.
• It executes wait operation on semaphore S0 unsuccessfully and gets blocked.

Scene-04:

• Process P2 gets scheduled.
• It executes wait operation on semaphore S2 successfully. Now, S2 = 0.
• It executes signal operation on semaphore S0 which wakes up the process P0.
• The execution of process P2 is completed.

Scene-05:

• Process P0 gets scheduled again.
• It prints ‘0’. (3^rd time)
• It executes signal operation on semaphore S1. Now, S1 = 1.
• It executes signal operation on semaphore S2. Now, S2 = 1.
• While loop causes process P0 to execute again.
• It executes wait operation on semaphore S0 unsuccessfully and gets blocked.

Now,

• The execution of processes P1 and P2 is already completed.
• There is no other process in the system which can perform signal operation on semaphore S0.
• Thus, process P0 can not execute any more.

Thus, maximum number of times process P0 can print ‘0’ = 3 times.

Minimum Number Of Times Process P0 Can Print ‘0’-

The occurrence of following scenes will cause process P0 to print ‘0’ two times-

Scene-01:

• Process P0 arrives.
• It executes wait operation on semaphore S0 successfully. Now, S0 = 0.
• It then prints ‘0’. (1^st time)
• It executes signal operation on semaphore S1. Now, S1 = 1.
• It executes signal operation on semaphore S2. Now, S2 = 1.
• Now, process P0 gets preempted.

Scene-02:

• Process P1 gets scheduled.
• It executes wait operation on semaphore S1 successfully. Now, S1 = 0.
• It executes signal operation on semaphore S0. Now, S0 = 1.
• The execution of process P1 is completed.

Scene-03:

• Process P2 gets scheduled.
• It executes wait operation on semaphore S2 successfully. Now, S2 = 0.
• It executes signal operation on semaphore S0. Now, S0 = 1.
• The execution of process P2 is completed.

Scene-04:

• Process P0 gets scheduled again.
• While loop causes process P0 to execute again.
• It executes wait operation on semaphore S0 successfully.
• It prints ‘0’. (2^nd time)
• It executes signal operation on semaphore S1. Now, S1 = 1.
• It executes signal operation on semaphore S2. Now, S2 = 1.
• While loop causes process P0 to execute again.
• It executes wait operation on semaphore S0 unsuccessfully and gets blocked.

Now,

• The execution of processes P1 and P2 is already completed.
• There is no other process in the system which can perform signal operation on semaphore S0.
• Thus, process P0 can not execute any more.

Thus, minimum number of times process P0 can print ‘0’ = 2 times.

Thus, Option (A) is correct.

Problem-05:

Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the processes P and Q is shown below-

Process P:

while(1)
{
   W:
   print '0';
   print '0';
   X:
}

Process Q:

while(1)
{
   Y:
   print '1';
   print '1';
   Z:
}

Synchronization statements can be inserted only at points W, X, Y and Z. Which of the following will always lead to an output string with ‘001100110011’?

1. P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1
2. P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially 1 and T initially 0
3. P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1
4. P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S initially 1 and T initially 0

Solution-

The correct option is (B).

The explanation is as follows-

Explanation-

For better understanding, let us write-

• P(S) = wait(S) and P(T) = wait(T)
• V(S) = signal(S) and V(T) = signal(T)

Process P:

while(1)
{
   wait(S)
   print '0';
   print '0';
   signal(T)
}

Process Q:

while(1)
{
   wait(T)
   print '1';
   print '1';
   signal(S)
}

• S is initialized with value 1.
• T is initialized with value 0.

Scene-01:

• Semaphore T is initialized with value 0.
• So, process Q can not execute first and if it tries to execute first, it will be blocked.
• Semaphore S is initialized with value 1.
• So, process P can execute.

Scene-02:

• Process P begins its execution.
• It executes wait(S) operation successfully and sets the value of semaphore S to 0.
• It prints ‘0’ two times.
• It executes signal(T) operation successfully and sets the value of semaphore T to 1.
• Now, process P can not execute again since S = 0 and if it tries, it will be blocked.
• Since value of semaphore T is now 1, so process Q can now execute.

Output string till now = 00

Scene-03:

• Process Q begins its execution.
• It executes wait(T) operation successfully and sets the value of semaphore S to 0.
• It prints ‘1’ two times.
• It executes signal(S) operation successfully and sets the value of semaphore S to 1.
• Now, process Q can not execute again since T = 0 and if it tries, it will be blocked.
• Since value of semaphore S is now 1, so process P can now execute.

Output string till now = 0011

In this way,

• The procedure goes on and both the processes keep executing alternately following strict alternation approach and prints 00 and 11 alternately.
• Thus, Correct Option is (B).

Problem-06:

In problem-05, which of the following will ensure that the output string never contains a sub string of the form 01ⁿ0 or 10ⁿ1 where n is odd?

1. P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1
2. P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1
3. P(S) at W, V(S) at X, P(S) at Y, V(S) at Z, S initially 1
4. V(S) at W, V(T) at X, P(S) at Y, V(T) at Z, S and T initially 1

Solution-

The correct option is (C).

The explanation is as follows-

Explanation-

• To obtain the strings of desired form, we must ensure that the other process is able to execute only after the first process has executed completely.
• Only option (C) ensures that the other process is not able to execute if the executing process gets preempted in the middle.
• In all other options, the other process is able to execute if the executing process gets preempted in the middle.
• In option (C), the process will have to compulsorily complete its execution to give chance to the other process to execute or to repeat itself.
• Thus, Option (C) is correct.

Problem-07:

Three concurrent processes X, Y and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e. wait) on semaphores a, b and c; process Y executes the P operation on semaphores b, c and d; process Z executes the P operation on semaphores c, d and a before entering the respective code segments. After completing the execution of its code segment, each process invokes the V operation (i.e. signal) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the P operations by the processes?

1. X:P(a)P(b)P(c) , Y: P(b)P(c)P(d) , Z: P(c)P(d)P(a)
2. X:P(b)P(a)P(c) , Y: P(b)P(c)P(d) , Z: P(a)P(c)P(d)
3. X:P(b)P(a)P(c) , Y: P(c)P(b)P(d) , Z: P(a)P(c)P(d)
4. X:P(a)P(b)P(c) , Y: P(b)P(c)P(d) , Z: P(c)P(d)P(a)

Solution-

The correct option is (B).

The explanation is as follows-

Explanation-

• Except option (B), all other options can give birth to a deadlock.
• Among processes X and Y, the process which arrives first executes the wait operation on semaphore ‘b’.
• The later process when tries to execute the wait operation on semaphore ‘b’ gets blocked.
• Therefore, it won’t be able to execute until the former process completes execution.
• Now, it is possible that the former process may get preempted in the middle after executing the wait operation on one or more variables and process Z gets scheduled.
• Consider the former process gets preempted just after executing the wait operation on semaphore ‘b’.
• Now, process Z arrives and executes the wait operation on one or more variables.
• Consider process Z executes the wait operation on semaphore ‘a’ or on semaphores ‘a’ and ‘c’.
• In both these cases, the former process will not be able to continue its execution.
• But it won’t give birth to a deadlock.
• In that case, process Z will complete its execution first and then former process will complete its execution and then later process will complete its execution.
• To sum up, no matter in which order the processes get execute and where they get preempt, no deadlock will occur.

Example Where Option-(A) Gives Birth To Deadlock-

• X: P(a) executes and preempts.
• Y: P(b) executes and preempts.
• Z: P(c)P(d) executes.
• Now, no process can execute and system is in a deadlock state.

Example Where Option-(C) Gives Birth To Deadlock-

• X: P(b) executes and preempts.
• Y: P(c) executes and preempts.
• Z: P(a) executes.
• Now, no process can execute and system is in a deadlock state.

Example Where Option-(D) Gives Birth To Deadlock-

• X: P(a) executes and preempts.
• Y: P(b) executes and preempts.
• Z: P(c)P(d) executes.
• Now, no process can execute and system is in a deadlock state.

NOTE-

In  general,

• To decrease the chances of deadlock, it is recommended to execute the wait operation on all the similar semaphores for all processes in the same order.
• As a short trick, you may first compare the execution order of the semaphore variables of all the processes.
• The option where most of the processes execute the wait operation on similar semaphores in the same order is likely to be deadlock-free.
• This can also be observed in the above question.

Problem-08:

Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S1 and S2. The code for the processes P and Q is shown below-

Process P:

while(1)
{
   P(S1);
   P(S2);
   Critical Section
   V(S1);
   V(S2);
}

Process Q:

while(1)
{
   P(S1);
   P(S2);
   Critical Section
   V(S1);
   V(S2);
}

This ensures-

1. Mutual Exclusion
2. Deadlock
3. Starvation but not deadlock
4. None of these

Solution-

• The process which so ever arrives first performs the wait operation on the semaphores.
• If the other process arrives in the middle, it will get blocked and put to sleep in the waiting list.
• When the former process performs the signal operation on semaphores, it wakes up the latter process.
• This ensures mutual exclusion.
• There is no possibility of deadlock or starvation.

Thus, Option (A) is correct.

NOTE-

• In the code of above processes, there is no need of using two semaphores.
• Mutual exclusion could be achieved by using only one semaphore too.

Problem-09:

Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S1 and S2. The code for the processes P and Q is shown below-

Process P:

while(1)
{
   P(S1);
   P(S2);
   Critical Section
   V(S1);
   V(S2);
}

Process Q:

while(1)
{
   P(S2);
   P(S1);
   Critical Section
   V(S1);
   V(S2);
}

This ensures-

1. Mutual Exclusion
2. Deadlock
3. Both (A) and (B)
4. None of these

Solution-

The occurrence of following scenes may cause deadlock-

Scene-01:

• Process P arrives.
• It executes wait operation on semaphore S1 successfully.
• Process P gets preempted.

Scene-02:

• Process Q gets scheduled.
• It executes wait operation on semaphore S2 successfully.
• Process Q gets preempted.

Scene-03:

• Process P gets scheduled again.
• It executes wait operation on semaphore S2 unsuccessfully and gets blocked.
• Process P gets preempted.

Scene-04:

• Process Q gets scheduled again.
• It executes wait operation on semaphore S1 unsuccessfully and gets blocked.

Now,

• Both the processes are blocked and keeps waiting for the signal from the each other.
• The system is in a deadlock state.
• Also, mutual exclusion can be guaranteed.
• Thus, Option (C) is correct.

Problem-10:

Consider the following program segment for concurrent processing using semaphore operators P and V for synchronization. Draw the precedence graph for the statements S₁ to S₉.

var
a,b,c,d,e,f,g,h,i,j,k : semaphore;
begin
cobegin
    begin S1; V(a); V(b) end;
    begin P(a); S2; V(c); V(d) end;
    begin P(c); S4; V(e) end;
    begin P(d); S5; V(f) end;
    begin P(e); P(f); S7; V(k) end
    begin P(b); S3; V(g); V(h) end;
    begin P(g); S6; V(i) end;
    begin P(h); P(i); S8; V(j) end;
    begin P(j); P(k); S9 end;
coend
end;

Solution-

Precedence graph will be as shown below-

Problem-11:

Write a concurrent program using parbegin-parend and semaphores to represent the precedence constraints of the statements S₁ to S₆ as shown in given figure-

Solution-

var
a,b,c,d,e,f,g : semaphore;
begin
cobegin
    begin S1; V(a); V(b) end;
    begin P(a); S2; V(c); V(d) end;
    begin P(b); S3; V(e) end;
    begin P(c); P(f); S4 end;
    begin P(d); P(e); P(g); S5 end
    begin S6; V(f); V(g) end;
coend
end;

To watch video solutions and practice other problems,

Watch this Video Lecture

Next Article- Deadlock in OS

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Semaphores in OS-

Before you go through this article, make sure that you have gone through the previous article on Semaphores in OS.

We have discussed-

• A semaphore is a simple integer variable used to provide synchronization among the processes.
• There are mainly two types of semaphores-

In this article, we will discuss about Binary Semaphores.

Binary Semaphores-

A binary semaphore is implemented as-

struct semaphore
{
   enum value (0,1);
   Queue type L;
}

Wait (semaphore s)
{
   if (s.value == 1)
   {
      s.value=0;
   }
   else
   {
      put process (PCB) in s.L;
      sleep();
   }
}

Signal (semaphore s)
{
   if (s.L is empty)
   {
      s.value=1;
   }
   else
   {
       select a process (PCB) from s.L;
       wake up();
   }
}

Explanation-

The above implementation of binary semaphore has been explained in the following points-

Point-01:

A binary semaphore has two components-

• An integer value which can be either 0 or 1
• An associated waiting list (usually a queue)

Point-02:

• The waiting list of binary semaphore contains the processes that got blocked when trying to enter the critical section.
• In waiting list, the blocked processes are put to sleep.
• The waiting list is usually implemented using a queue data structure.
• Using a queue as waiting list ensures bounded waiting.
• This is because the process which arrives first in the waiting queue gets the chance to enter the critical section first.

Point-03:

• The wait operation is executed when a process tries to enter the critical section.
• Then, there are two cases possible-

Case-01: Binary Semaphore Value = 1

If the value of binary semaphore is 1,

• The value of binary semaphore is set to 0.
• The process is allowed to enter the critical section.

Case-02: Binary Semaphore Value = 0

If the value of binary semaphore is 0,

• The process is blocked and not allowed to enter the critical section.
• The process is put to sleep in the waiting list.

Point-04:

• The signal operation is executed when a process takes exit from the critical section.
• Then, there are two cases possible-

Case-01: Waiting List is Empty-

• If the waiting list is empty, the value of binary semaphore is set to 1.

Case-02: Waiting List is Not Empty-

• If the waiting list is not empty, a process is chosen from the waiting list and wake up to execute.

Point-05:

Binary semaphores are mainly used for two purposes-

• To ensure mutual exclusion.
• To implement the order in which the processes must execute.

Example-

In this example-

• Two binary semaphores S1 and S2 both initialized with 0 are used.
• The execution order of the processes is P2 → P1 → P3.

To gain better understanding about Binary Semaphores,

Watch this Video Lecture

Next Article- Practice Problems On Binary Semaphores

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.