Semaphores

Question 1
Consider the following pseudocode, where S is a semaphore initialized to 5 in line#2 and counter is a shared variable initialized to 0 in line#1. Assume that the increment operation in line#7 is not atomic.
  1. int counter = 0
  2. Semaphore S = init(5);
  3. void parop(void)
  4. {
  5.       wait(S);
  6.       wait(S);
  7.       counter++;
  8.       signal(S);
  9.       signal(S);
  10. }  
If five threads execute the function parop concurrently, which of the following program behaviour(s) is/are possible?
A
The value of counter is 1 after all the threads successfully complete the execution of parop.
B
The value of counter is 5 after all the threads successfully complete the execution of parop.
C
The value of counter is 0 after all the threads successfully complete the execution of parop.
D
There is a deadlock involving all the threads.
Operating-SystemsSemaphoresGATE 2021 CS-Set-1Video-Explanation
Question 1 Explanation: 

count =0

S=5

func()

{

    wait();

    wait();

       count++;

       signal();

       signal();

}

Answer:

(1) Deadlock is possible.

For a deadlock free operation

No. of resources >= No. of process (Req-1) + 1

Here, no. of resources = 5 (semaphore value)

Each thread requires = 2 resources (wait call)

No. of threads = 5

      5 ≥ 5* (2-1)+1

         ≱ 6. So deadlock is possible.

This occurs when all 5 threads get blocked on first wait().

(2) count =5 is possible

When all threads enter CS and execute count++ sequentially.

(3) Count=1 is possible.

Assembly level:

     read R0, count

     inc R0, 1

     write count, R0

Thread - 1 reads Count=0 in R0, preempted



Thread-2 reads count=0, is r1, completes, count=1

Thread-3, 4 & 5 completes.

Thread-1 is given CPU

MC R0, 1, so R0=1

Write R0 to count.

So, Count=1. 

Question 2

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(c) 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(j); P(k); S9 end;
 coend
 end;
A
Theory Explanation.
Operating-SystemsSemaphoresGATE 1995
Question 3

Write a concurrent program using parbegin-parend and semaphores to represent the precedence constraints of the statements S1 to S6, as shown in figure below.

A
Theory Explanation.
Operating-SystemsSemaphoresGATE 1993
Question 4

At a particular time of computation the value of a counting semaphore is 7. Then 20 P operations and 15 V operations were completed on this semaphore. The resulting value of the semaphore is:

A
42
B
2
C
7
D
12
Operating-SystemsSemaphoresGATE 1992Video-Explanation
Question 4 Explanation: 
Let the semaphore be S.
Initial value of S is 7.
So after 20P operations and 15V operations the value of semaphore S will be,
S = 7 - 20 + 15 = 2
There are 4 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access