edited by
1,112 views
10 votes
10 votes

Suppose that an operating system provides two functions, $block()$ which puts the calling process on the blocked queue, and $wakeup(P)$ which moves process $P$ to the runnable queue if it is currently on the blocked queue (otherwise, its behaviour is unpredictable). Consider two processes $A$ and $B$ running the code given below. The intended behaviour of the code is to have $A$ and $B$ run forever, alternately printing their names on the screen.

$$\begin{array}{l|l}  \text{void A()}  &  \text{void B()}  \\  \text{\{} & \text\{{} \\ 
\quad\text{while(1) \{} & \quad \text{while(1) \{} \\ 
\quad\quad\text{block();} &\quad\quad \text{printf(“B");} \\
\quad\quad\text{printf(“A");} & \quad\quad\text{wakeup(A);} \\
\quad\quad\text{wakeup(B);} & \quad\quad\text{block();}\\
\quad \text{ \}}& \quad \text{ \}}  \\
\text{\}}&  \text{\}}  \end{array}$$

  1. Construct a scenario in which the intended behaviour would not be observed.
  2. Redesign the code using semaphore(s) so that it works correctly. You should show the initialisation of the semaphore(s), and the calls to $wait()$ and $signal()$ made by $A$ and $B$.
edited by

3 Answers

Best answer
9 votes
9 votes

Consider a scenario

Process $B$ arrives..and it executes...till the step wakeup$(A)$ & after this step..process $B$ Preempts..now process $A$ arrives..it get blocked as it executes block() call..now after that process $B$ ..returns and it also executes block$()$ call...so it is also..blocked..now process $A$ is waiting for process $B$ to wakeup & process $B$ is waiting for process $A$ to wakeup. Hence, deadlock. 

Correct code

Binary semaphore $X = 1 , Y=0$

void A()
{ 
    while(1) {
        P(X)
        printf("A");
        V(Y)
    }
}
void B()
{
    while(1) {
        P(Y)
        printf("B");
        V(X)
    }
}

 

The above code prints $ABAB\ldots$ but not $BABA\ldots.$ Since the question asks for $A$ and $B$ alternating we can assume $“A"$ has to be printed first.

edited by
2 votes
2 votes

 

Process A Process B
1. block();  
  1. print "B"
  2. wakeup(A);
2. print "A"   
3. wakeup(B);  
  3. block(); (end of process B)
1. block(); (process A is executed again)  

In this scenario, process $B$ is blocked and is waiting for process $A$ to wakeup (as wakeup(B) is performed only by process $A$)  and process $A$ is blocked and is waiting for process $B$ to wakeup- Deadlock (none of the process proceeds). 

Correction in the code as per intended behaviour( alternately printing names) two binary semaphores say $X, Y$ can be used, with initial values:

$X=1, Y=1 $

void A()
{ 
    while(1) {
        wait(X);
        printf("A");
        signal(Y);
    }
}

 

void B()
{ 
    while(1) {
        wait(Y);
        printf("B");
        signal(X);
    }
}

 

Either the process $A$ can start first in which the printed sequence will be $ABABA....$or process $B$ can start first in which the printed sequence will be $BABAB....$

This is wrong as there can be sequences ABB or BAA( not intended behaviour)

Process A Process B
wait(X);  
print "A"  
  wait(Y);
  print "B"
signal(Y);  
  wait(Y); (process B executes again)
  print "B" (sequence printed is $ABB$)

So, semaphore initialization should be either $X=0, Y=1 $ or $ X=1, Y=0$

0 votes
0 votes
for part (i) its already explaned and for part (ii) i am having different solution:

Initially Binary Semaphore:  X=1; and Y=1;

void A() {

while(1) {

P(X);

Printf("A");

V(Y);

}

}

 

Void B() {

While(1) {

P(Y);

Printf("B");

V(X);

}

}

Related questions

16 votes
16 votes
1 answer
1
go_editor asked Jun 1, 2016
1,667 views
A system has $4$ processes $A$, $B$, $C$, $D$ and $5$ allocatable resources $R_1, \: R_2,\: R_3, \: R_4,\: R_5$. The maximum resource requirement for each process and its...
1 votes
1 votes
0 answers
2
go_editor asked Jun 1, 2016
513 views
A connected, simple, undirected planar graph $G(V, E)$ is given where $V$ denotes the set of vertices and E denotes the set of edges. In $V$, there is a designated source...
2 votes
2 votes
2 answers
4
go_editor asked Jun 1, 2016
1,050 views
A block of bits with $n$ rows and $m$ columns uses horizontal and vertical parity bits for error detection. If exactly 4 bits are in error during transmission, derive an ...