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

@Yash Chhapariya not need any link 

---

Thanks

---

thanks

 

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

@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.

---

Beautiful and the best explanation!!!

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.

 

Option B saying two processes in code section Q at any time. As signal(b) in the if condition executes when count=n, then one more signal(b) executed by processes. Due to this we can have more than 2 processes also in the code section Q. Hence option B is false.

 

Remaing options are talking about code section P. Where there is no information provided about that. Hence, you can't comment on that.

Comments

@Shaik Masthan Sir,can you explain option C?

---

@Sunnychxfyhc,

As I mentioned, we don't have any information regarding code section of P.

Hence, we can't say whether it is true or false.

---

Ok sir

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

why there cant be multithreading?

---

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

---

in option d atmost n process is bcz in ques  have already mentioned that code section p is non critical section part so there must not be any restriction that is how many process can be there .

Answer 4

Simpler explanation ...

Answer 5

b is initialized to 0.

Code section Q can only be accessed when count becomes n otherwise any process which executes if condition will be blocked because of 0 as initial value of b.

To go into that condition the count has to be n.
and
count only increases after execution of code section P.

So until and unless every process executes P, the count will not be same as n.

When every process executes code section P, the condition becomes true and b becomes 1.

So one process at a time will enter CS and will execute code section Q.

Answer is A.