GATE Overflow Test Series | Operating Systems | Test 1 | Question: 22

Question

Consider the following process synchronization program involving $N$ processes.

semaphore S = 21;
Process 1
S.signal();
while (1) {
  // do something
  S.wait();
  //critical section
  S.signal(); 
  // do something
}
Process 2..N
while (1) {
  // do something
  S.wait();
  //critical section
  S.signal(); 
  // do something
}

The maximum number of processes that can be in the critical section at any moment of time is _______

• A. $21$
• B. $22$
• C. $23$
• D. More than $23$

Comments

When I took the exam, I missed seeing s.signal() in process1. It was a silly mistake that anyone could make.

so, after this, anyone will be able to solve this question and get 22 right answers.

Answer 1

Here, process $1$ is doing an extra signal at first making the semaphore value $22.$ In the while loop all the processes are doing a wait and signal alternatively. So, at maximum, $22$ processes can do a wait and enter the critical section.

Comments

I think the answer is option D. Suppose the process 1 is executed for the first k>0 times, then the semaphore S have the value 21 + K.  Since K can be any positive value, the semaphore S could take any value greater than equal to 21. Hence maximum number of processes in critical section could be any value greater than 21. Please feel free to correct me.

---

@pradeep_reddy let's analyze what u said,i run process P1,it's having 1 signal statement outside while loop so will make S=22,now i went inside ,wait will happen which will reduce S to 21 and now 1 process is in Critical section ,now other processes from 2 to 22 can also go inside  making S=0,and suppose if I came out of P1,it will increment S to 1, but at that time no. of processes that are in CS are 21 so 1 process can enter ,and next time if p1 again went ,it won't run initial signal statement as that is out of while loop,so 22 processes can be at max.

---

@Aayush_00, think of it like this.

1. Initially S=21.
2. Run process P1 completely. When P1 comes out of critical section, S will be 22.
3. Run P1 again completely. Now, S will be 23.
4. You can repeat step 3 many times. Every time you run P1, S will be incremented by 1 as the code for P1 has one extra signal statement. 
5. Lets say P1 is run for K times. Now the value of S will be 21+K. Since the value of counting semaphore indicates the maximum number of process that can be present in critical section at any point of time, the answer will be >21.

---

@pradeep_reddy when u will execute P1 again ,it will start after signal statement means that single statement won't be executed,it will start in while loop only