edited by
3,546 views
27 votes
27 votes

Consider the blocked-set semaphore where the signaling process awakens any one of the suspended process; i.e.,

Wait (S): If $S>0$ then $S\leftarrow S - 1$, else suspend the execution of this process.

Signal (S): If there are processes that have been suspended on semaphore $S$, then wake any one of them, else $S\leftarrow S + 1$

Consider the following solution of mutual exclusion problem using blocked-set semaphores.

s := 1;
cobegin 
P(1)   ||    P(2)     ||    .....   ||     P(N) 
coend

Where the task body P(i) is

begin 
while true do 
begin 
 < non critical section >  
 Wait (S) 
<critical section>  
 Signal (S) 
end  
end

Here $N$ is the number of concurrent processors. Which of the following is true?

  1. The program fails to achieve mutual exclusion of critical regions.
  2. The program achieves mutual exclusion, but starvation freedom is ensured only for $N\leq 2$
  3. The program does not ensure mutual exclusion if $N\geq 3$
  4. The program achieves mutual exclusion, but allows starvation for any $N\geq 2$
  5. The program achieves mutual exclusion and starvation freedom for any $N\geq 1$
edited by

3 Answers

Best answer
23 votes
23 votes

(B) is correct option!

$\textbf{Wait (S)}: \text{If } S > 0 \text{ then } S \leftarrow S-1, \text{else suspend the execution of this process.}$

$\textbf{Signal (S)}: \text{If there are processes that have been suspended on semaphore} \:S,$ $\text{ then wake any one of them, else } S \leftarrow S+1$

Suppose there are only $2$ processes in the system i.e., $N=2.$

s :=1
cobegin
    P(1) | P(2);
coend;

There are two concurrent processes lets say P1 and P2, which are trying to to access critical section, by executing $P(1)$ and $P(2)$ respectively.

Suppose $P(1)$ gets executed first, and it makes $s=0$. when $P(2)$ executes $Wait(S)$ then P2 will be blocked when $P1$ executes $Signal(S)$, there is one suspended process, hence $P2$ will be waken up and be placed into ready queue, now it can execute its critical section. The value of S is still 0, hence ME is satisfied


There is only 1 process in the suspended state, hence there is no chance that it will starve because as soon as the other process performs signal operation this process will be waken up.

If $N > 2,$ then there is a chance that multiple processes are blocked, and a random process will be unblocked when a process perform $signal(S)$ operation, there is a chance that one blocked process is not getting its chance hence it might starve. So, (E) is not correct option.

PS: A blocked queue semaphore awakens processes in the order they are suspended- hence no starvation even for $N > 2$ if used in this question.

edited by
7 votes
7 votes

I think answer would be option D
since at one time only one process can enter the critical section.

 If P1 keep on entering the critical section P2 never get the chance to enter the critical section so starvation can occur for any n>2

0 votes
0 votes
Why not A?

If Wait and Signal are not atomic mutual exclusion will never occur.. rt? It is not given in the question that wait and signal are atomic. Does "blocked-set semaphore" means atomic?

Lets have following scenario:

Let S=1. P1 and P2 both can enter Wait(). Now P1 checks if (S>0) and gets preempted. P2 also checks if(S>0). Both are true. P1 resumes sets S to 0 and P2 then resumes and sets S to -1.

Both can enter the CS now.

So mutual exclusion itself is not possible here I guess.

Correct me if I am wrong.
Answer: