GATE CSE 2020 | Question: 34

Question

Each of a set of $n$ processes executes the following code using two semaphores $a$ and $b$ initialized to $1$ and $0$, respectively. Assume that $\text{count}$ is a shared variable initialized to $0$ and not used in CODE SECTION P.

$\begin{array}{|c|} \hline \textbf{CODE SECTION P} \\ \hline \end{array}$

wait(a); count=count+1;
if (count==n) signal (b);
signal (a): wait (b) ; signal (b);

$\begin{array}{|c|} \hline \textbf{CODE SECTION Q} \\ \hline \end{array}$

What does the code achieve?

• A. It ensures that no process executes CODE SECTION Q before every process has finished CODE SECTION P.
• B. It ensures that two processes are in CODE SECTION Q at any time.
• C. It ensures that all processes execute CODE SECTION P mutually exclusively.
• D. It ensures that at most $n-1$ processes are in CODE SECTION P at any time.

Comments

I am confused like which code section to use for P and V. Like https://gateoverflow.in/39576/Gate-cse-2016-set-2-question-49 in this question S can be negative. But here in the current question b is not getting reduced below zero.

This is the code given gfg https://www.geeksforgeeks.org/semaphores-in-process-synchronization/ 

---

why there cant be multithreading?

---

Based on the best answer provided on https://stackoverflow.com/questions/20656295/what-is-general-semaphores-range, the concern of whether to let the semaphore value go below zero or not is an implementation detail. In either case, they behave in the exact same way in which we want a semaphore to behave, i.e., the two implementations are equivalent with respect to their behaviors.

Answer 1

Answer: A. It ensures that no process executes CODE SECTION Q before every process has finished CODE SECTION P.

Explanation
In short, semaphore 'a' controls mutually exclusive execution of statement count+=1 and semaphore 'b' controls entry to CODE SECTION Q when all the process have executed CODE SECTION P. As checked by given condition if(count==n) signal(b); the semaphore 'b' is initialized to 0 and only increments when this condition is TRUE. (Side fact, processes do not enter the CODE SECTION Q in mutual exclusion, the moment all have executed CODE SECTION P, process will enter CODE SECTION Q in any order.)

Detailed explanation:-
Consider this situation as the processes need to execute three stages- Section P, then the given code and finally Section Q.

It is evident that semaphores do not control Section P hence, There is no restriction in execution of P.

Now, we are given 2 semaphores 'a' and 'b' initialized to '1' and '0' respectively.

Take an example of 3 processes (hence n=3, count=0(initially) ) and lets say first of them has finished executing Section P and enters the given code. It does following changes:-
1. will execute wait(a) hence making semaphore a=0
2. increment the count from 0 to 1 (first time)
3. If(count==n) evaluates FALSE and hence signal(b) is not executed. So semaphore b remains 0
4. signal(a) hence making semaphore a=1
5. wait(b) But since semaphore b is already 0, The process will be in blocked/waiting state.
First out of the three processes is unable to enter the CODE SECTION Q !

Now say second process completes CODE SECTION P and starts executing the given code. It can be concluded that it will follow the same sequence (5 steps) as mentioned above and status of variables will be:- count = 2 (still count<n), semaphore a=1, semaphore b=0 (no change)

Finally the last process finishes execution of CODE SECTION P.
It will follow same steps 1 and 2 making semaphore a=0 and count = 3
3. if(count==n) evalueates TRUE! and hence signal(b) is executed marking semaphore b = 1 FOR THE FIRST TIME.
4 and 5 will be executed the same way.

Now the moment this last process signaled b, the previously blocked process will be able to execute wait(b) and the very next moment execute signal(b) to allow other blocked/waiting process to proceed.
This way all the processes enter CODE SECTION Q after executing CODE SECTION P.

Comments

It can be concluded that it will follow the same sequence (5 steps) as mentioned above and status of variables will be:- count = 2 (still count<n), semaphore a=1, semaphore b=0 (no change)

I have a doubt regarding the above part in the answer.

I understood the entire explanation perfectly fine. However, when process 1 and 2 get blocked at wait(b); - wouldn't the value of 'b' go down to -1 and -2 respectively from the initial value of 0? 

I understand that semaphores don't have negative values, but in the implementation of wait() in OS Principles by Galvin, it is possible for semaphores to take negative values.

---

@kumaravel.rajan deriving from the details of semaphores from Galvin (9th Edition), whenever the value of a semaphore reaches zero (or even if you consider zero as valid then if(sem < 0)); the requesting process is either blocked or put in a spinlock. Semaphore value = zero implies the resource is unavailable or all the possible instance are currently exhausted (counting semaphore). This last implication is what generally implied whenever the semaphore's value is zero; or if zero is valid then its transitions to negative (though it should not be).
P.S. Question does not specify the implementation of wait() and signal(), hence a natural implementation must be assumed.

---

Just realized that this is a barrier construct. Barriers don’t allow processes to pass until all processes have completed executing up to that point. They are used for cases where application execution is done in phases and all processes must enter a phase together.

Answer 2

a is initialized to 1 and b is initialized to 0.

when a process tries to perform down on b, it will be block.

 

if you observe the code, when count equals to n, then one process from blocked queue, enter into CODE SECTION Q.

so, for any process, to enter into CODE SECTION Q, count must be equals to n.

When Count equals to n ?

when all processes, completes CODE SECTION P, after that, the subsequent code executed by them, after that, count equals to n.

 

Option A is correct

Comments

@Shaik Masthan Please check this Comment and respective answer!

---

@dhruvhacks

yes you are right

---

what happens if the process is preempted after the signal(a) then any process can into Critical section right??

Answer 3

Answer : A

Option A:  Assume few processes try to enter in Code Q and get blocked since b=0 and we have to do wait(b) ,When count = n, then one process from blocked queue, enter into Code Q.

Option B: no context of atmost 2 present in code. So, false

Option C: No in code P n-number of process can run simultaneously i.e. when signal(a) done more process can enter in Code P while other process preempt before signal(b) i.e. shared variable count shared by many processes at same time.  So, false.

Option D: Code P can have atmost n process at any time. So, false

Comments

@Prashant.NOT GETTING OPTION D

---

why there cant be multithreading?

---

yeah your answer was needed after reading best answer to get satisfied with analysing other options. well explained