FOR FREE MATERIALS
Question from Binary Semaphore
Consider two concurrent processes 'P' & 'Q' execute their respective codes
Process P Process Q
While (1)While (1)
{W:{Y:
Print ‘0’; Print '1';
Print '0';Print '1';
X:Z:
}}
What should be the binary semaphore option on w, x, y, z, and what should be the initial values of binary semaphore variables 'S' and 'T' to get O/P as 0011001100...
(a) P(S) at w, V(S) at x, P(T) at y, V(T) at Z, S, and T initially 1.
(b) P(S) at w, V(T) at x, P(T) at y, V(S) at Z, initially S = 1 and T = 0.
(c) P(S) at w, V(T) at x, P(T) at y, V(S) at Z, S, and T initially 1.
(d) P(S) at w, V(S) at x, P(T) at y, V(T) at Z, S = 1 and T = 0.
Answer:
P means down(wait) operations and V means up(signal)operations. And we know down and up operation is an atomic operation. For details see Up and Down Operation.
Option a: Initially S = 1, T = 1
Process P While (1) { W: P(S) Print '0' ; Print '0'; X: V(S) }
Process Q While (1) { Y: P(T) Print '1' ; Print '1'; Z: V(T) } | # Here Initially S = 1, T = 1. So, any process P, Q runs first, either P runs first or Q runs first. So, the output may be started from 11…
So, there is no guarantee that every time it leads to 0011 0011 0011......... .
So option a is not correct. |
Option b: Initially S = 1, T = 0
Process P While (1) { W: P(S) Print '0' ; Print '0'; X: V(T) } Process Q While (1) { Y: P(T) Print '1' ; Print '1'; Z: V(S) }
| # Here S = 1, T = 0. So, process P runs first, Q will not be allowed first because initially T = 0. So, process P runs first and print 00, up(T), now T = 1, then process Q runs and print 11 and up(S). Output right now 0011. Now S = 1, again process P get a chance to enter into the critical section. Print 00. Output right now 001100. So, In this way, every time process P runs first then Q. And the output will be.. 001100110011…..
Option b is correct. |
Let check the rest of the options.
Option c: Initially S = 1, T = 1
Process P While (1) { W: P(S) Print '0' ; Print '0'; X: V(T) } Process Q While (1) { Y: P(T) Print '1' ; Print '1'; Z: V(S) }
| # Here S = 1, T = 1, So, any process P or Q can start first. If process Q starts first then output starts with 11.
So, every time 0011 0011 ....... output is not possible.
Option c is incorrect. |
Option d: Initially S = 1, T = 0
Process P While (1) { W: P(S) Print '0' ; Print '0'; X: V(S) } Process Q While (1) { Y: P(T) Print '1' ; Print '1'; Z: V(T) }
| # here S = 1, T = 0 So, as per the code always process gets a chance to execute but process Q will never execute because never up(T) at process p.
So, the output will be 00 00 00 00…
Option d is incorrect. |
Gate 2013: Question from Binary Semaphore
We have three processes x, y, z, and four mutexes a, b, c, d. Which sequence of processes not incur with deadlock means deadlock-free.
a) X : P(a) P(b) P(c) b) X : P(b) P(a) P(c)
Y : P(b) P(c) P(d) Y : P(b) P(c) P(d)
Z : P(c) P(d) P(a) Z : P(a) P(c) P(d)
c) X : P(b) P(a) P(c) d) X : P(a) P(b) P(c)
Y : P(c) P(b) P(d) Y : P(c) P(b) P(d)
Z : P(a) P(c) P(d) Z : P(c) P(d) P(a)
Answer:
P means Down or Wait operation of binary semaphore.
P or Down operation cannot execute by two processes together for a single semaphore variable. If one process already runs a P or Down operation, then for the next process P or Down operation will be blocked for the same semaphore variable.
Let’s examine
Option a: X: P(a) preempted | Y : P(b) preempted | Z : P(c) preempted
X: P(b) | Y : P(c) | Z : P(d) P(a)
Blocked Blocked Blocked
Option a not correct. Because three processes are blocked i.e. deadlock occurs.
Option b: X: P(b) preempted | Y : P(b) | Z : P(a) preempted
Blocked
X: P(a) | Y : P(b) | Z : P(c) P(d) finished
Blocked Blocked
Process Z is finished means mutex a, c, d is free so, we can solve X and Y easily.
In between three processes if one of the processes is finished then it never leads to a deadlock.
Option b correct.
Still, we check options c and d to clarify the process.
Option c:
X : P(b) preempted | Y : P(c) preempted | Z : P(a) preempted
X : P(a) | Y : P(b) | Z : P(a)
Blocked Blocked Blocked
Option c not correct because it has a circle and deadlock occur
Option d:
X : P(a) preempted | Y : P(c) preempted | Z : P(c)
Blocked
X : P(b) preempted | Y : P(b) | Z : P(c)
Blocked Blocked
X : P(c) | Y : P(b) | Z : P(c)
Blocked Blocked Blocked
Option d not correct because it has a deadlock situation.
So, Option b is the correct answer.
