Semaphore | Binary Semaphore | Practice Problems

Operating System
Spread the love

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 Pi, i = 1, 2, …, 9 is coded as follows-

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

 

The code for P10 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 P1, P2, … , P9

 

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

 

Code for Process P10

 

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 P1 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 P2, P3, … , P9 arrives when process P1 is executing the critical section.
  • All the other processes get blocked and are put to sleep in the waiting list.

 

Scene-03:

 

  • Process P10 arrives.
  • It performs the signal operation on mutex.
  • It selects one process from the waiting list say process P2 and wakes it up.
  • Process P2 can now enter the critical section (P1 is already present).
  • Now, process P10 enters the critical section (P1 and P2 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 P3 and wakes it up.
  • Process P3 can now enter the critical section (P1 and P2 are already present).
  • Process P10 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 P0 : wait(m[0]); wait(m[1]);
  • Process P1 : wait(m[1]); wait(m[2]);
  • Process P2 : wait(m[2]); wait(m[3]);
  • Process P3 : wait(m[3]); wait(m[0]);
  • Process P4 : 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 P0 arrives.
  • It executes wait(m[0]) and gets preempted.

 

Scene-02:

 

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

 

Scene-03:

 

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

 

Scene-04:

 

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

 

Scene-05:

 

  • Process P4 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. (P0, P2)
  2. (P1, P3)
  3. (P2, P4)
  4. (P3, P4)
  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.

 

Process P0 Process P1 Process P2
while (true)

{

wait (S0);

print ‘0’

release (S1);

release (S2);

}

 wait (S1);

release (S0);

 

 

 

 

 

 wait (S2);

release (S0);

 

 

 

 

 

 

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’-

 

Maximum number of times process P0 can print ‘0’ = 3

 

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’. (1st 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’. (2nd 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’. (3rd 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’-

 

Minimum number of times process P0 can print ‘0’ = 2

 

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’. (1st 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’. (2nd 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 01n0 or 10n1 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 S1 to S9.

 

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 S1 to S6 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.

Summary
Semaphore | Binary Semaphore | Practice Problems
Article Name
Semaphore | Binary Semaphore | Practice Problems
Description
Practice Problems based on Binary Semaphore in OS. In operating system, semaphore is a simple integer variable. There are two types of semaphores- Counting Semaphore and Binary Semaphore also called as mutex.
Author
Publisher Name
Gate Vidyalay
Publisher Logo

Spread the love