Q 3.1 [1992 : 2M] – Deadlock Free Maximum Processes
Complete Question:
A computer system has 6 tape drives, with n processes competing for them. Each process may need 3 tape drives. The maximum value of n for which the system is guaranteed to be deadlock free is
(a) 2
(b) 3
(c) 4
(d) 1
Answer: (a) 2
Solution:
Formula: For deadlock free, Total Resources >= Max Need?
Worst case: Har process ko (need-1) = 2 de do, fir bhi ek extra chahiye sabko pura karne ke liye.
Total = n(k-1) + 1 <= R n(3-1)+1 <= 6 => 2n+1 <=6 => 2n <=5 => n <= 2.5 => max n = 2
Agar n=3 hua to 3*2+1=7 >6 -> deadlock possible hai.
Q 3.2 [1993 : 2M] – Minimum Resources to Avoid Deadlock
Complete Question:
Consider a system having m resources of the same type. These resources are shared by 3 processes A, B and C, which have peak demands of 3, 4 and 6 respectively. For what value of m deadlock will not occur?
(a) 7
(b) 9
(c) 10
(d) 13
Answer: (d) 13 (Minimum guaranteed is 11, so from options 13 is safe)
Solution:
Minimum m for guarantee = Sum(peak_i -1) +1
= (3-1)+(4-1)+(6-1)+1 = 2+3+5+1 = 11
Iska matlab 11 resources honge to kabhi deadlock nahi lagega.
Options me 7,9,10 sab <11 hain, deadlock ho sakta hai. 13 >11 hai, isliye deadlock NOT occur wala answer 13 hoga.
Agar question “minimum m” pucha jaye to answer 11 hota.
1-Line Trick:
Min deadlock-free = Sum(peak-1)+1 = 11. Isse kam par risk, isse zyada par safe.
1-Line Trick:
n*(need-1)+1 <= Total. 2n+1 <=6 => n=2 max.
Q 3.3 [1997 : 2M] – Minimum Units for No Deadlock
Complete Question:
An operating system contains 3 user processes each requiring 2 units of resource R. The minimum number of units of R such that no deadlocks will ever arise is
(a) 3
(b) 5
(c) 4
(d) 6
Answer: (c) 4
Solution:
Same formula: n=3, need=2, R = ?
R >= n(need-1)+1 = 3(1)+1 = 4
3 processes, har ek ko 1 de do, total 3 used, 1 bacha hai. Wo ek jisko bhi milega wo complete ho jayega aur resources release kar dega.
1-Line Trick:
3*1+1 = 4. 4 units par guarantee safe.
Q 3.4 [1998 : 1M] – Tape Drives – 2 Need
Complete Question:
A computer has six tape drives, with n processes competing for them. Each process may need two tape drives. What is the maximum value of n for the system to be deadlock free?
(a) 6
(b) 5
(c) 4
(d) 3
Answer: (b) 5
Solution:
Formula: n(k-1)+1 <= R k=2, R=6 n(1)+1 <=6 => n <=5 Max n=5. Agar 6 processes hue to har ek ko 1-1 mil gaya to sab 1-1 ke liye atke rahenge -> deadlock possible.
1-Line Trick:
n+1 <=6 => n=5 max.
Q 3.5 [GATE] – Valid Deadlock Prevention
Complete Question:
Which of the following is NOT a valid deadlock prevention scheme?
(a) Release all resources before requesting a new resource.
(b) Number the resources uniquely and never request a lower numbered resource than the last one requested.
(c) Never request a resource after releasing any resource.
(d) [Option missing in photo – Usually “Request and all required resources at once”]
Answer: (c) Never request a resource after releasing any resource.
Solution:
Deadlock ke 4 conditions todne se prevention hota hai:
(a) Release all before new -> Hold and Wait ko todta hai -> VALID prevention hai.
(b) Numbering + increasing order -> Circular Wait ko todta hai -> VALID hai.
(c) Never request after release -> Ye prevention nahi hai, isse to Hold & Wait aur badhega, aur resource utilization kharab hoga. Ye valid scheme nahi hai.
Isliye NOT valid = (c).
1-Line Trick:
Prevention = Hold&Wait todo (all at once ya release all) + Circular Wait todo (numbering). “Never request after release” galat hai.
Q 3.6 [2004: 2 Marks] – Deadlock Prevention – Wound-Wait Scheme
Complete Question:
In a certain operating system, deadlock prevention is attempted using the following scheme. Each process is assigned a unique timestamp, and is restarted with the same timestamp if killed. Let Ph be the process holding a resource R, Pr be a process requesting for the same resource R, and T(Ph) and T(Pr) be their timestamps respectively. The decision to wait or preempt one of the processes is based on the following algorithm.
if T(Pr) < T(Ph) then
kill Pr
else
wait
Which one of the following is TRUE?
(a) The scheme is deadlock-free, but not starvation-free
(b) The scheme is not deadlock-free, but starvation-free
(c) The scheme is neither deadlock-free nor starvation-free
(d) The scheme is both deadlock-free and starvation-free
Answer: (a) The scheme is deadlock-free, but not starvation-free
Solution:
Ye Wait-Die Scheme ka variation hai.
Algorithm: If T(Pr) < T(Ph) then kill Pr else wait
Matlab:
- Agar Request karne wala bada hai (timestamp chota hai = Older) -> Usko kill kar do (Die).
- Agar Request karne wala chota hai (timestamp bada = Younger) -> Wait karne do.
- Deadlock-Free Kyu? Kyunki cycle kabhi nahi banega. Hamesha older process ko kill kiya ja raha hai, younger ko wait karaya ja raha hai. Circular wait tut jata hai. Wait karne wala hamesha older ke liye wait karta hai, to resource ka flow ek direction me hai.
- Starvation-Free Kyu Nahi? Kyunki ek hi process baar-baar kill ho sakta hai. T(Pr) < T(Ph) wala process jab bhi resource mangega, kill ho jayega. Same timestamp se restart hoga, phir se kill. Isliye starvation ho sakti hai.
Isliye ye Wound-Wait / Wait-Die family me Deadlock Free to hai, par Starvation Free nahi.
1-Line Trick:
Old ko Kill = Wait-Die = Deadlock Free but Starvation Possible. Trick: Die wale me victim baar-baar marta hai.
Q 3.7 [GATE] – Sufficient Condition for Deadlock Freedom
Complete Question:
Suppose n processes, P1, …, Pn share m identical resource units, which can be reserved and released one at a time. The maximum resource requirement of process Pi is si where si > 0. Which one of the following is a sufficient condition for ensuring that deadlock does not occur?
(a) ∀ i, si < m
(b) ∀ i, si < n
(c) ∑ si < (m + n) (i=1 to n)
(d) ∑ si < (m * n) (i=1 to n)
Answer: (c) ∑(i=1 to n) si < (m + n)
Solution:
Ye Banker’s Safe State ka formula hai.
Sufficient Condition for No Deadlock with identical resources:
Sab processes ko max need si hai. Worst case me har process ko (si – 1) resources de do, fir bhi ek resource bacha ho to koi ek process complete ho jayega, fir uske resources se dusra.
Matlab:
∑(si – 1) < m hona chahiye => ∑ si – n < m => ∑ si < m + n
Isse kam resources bante to kam se kam ek process ko uski poori need mil jayegi, vo finish hoga aur deadlock nahi lagega.
Option (a) si < m galat hai, kyunki sabka sum m se zyada ho sakta hai aur deadlock lag sakta hai.
Option (c) hi sufficient hai.
1-Line Trick:
Deadlock kabhi nahi lagega agar: Sum(si) < m + n. Yaad rakho: Sabko 1 kam de do, fir bhi 1 bacha ho to Safe hai.
Q 3.8 [2006 : 2M] – Producer Consumer Deadlock with Semaphores
Complete Question:
The semaphore E corresponds to the number of elements in the buffer and is initialized to 0.
F corresponds to number of free slots and initialized to N.
S is the mutex semaphore initialized to 1.
Producer Process | Consumer Process
Produce an item; | Wait (E);
Wait (F); | Wait (S);
Wait (S); | Remove an item from the buffer;
Append the item to the buffer; | Signal (S);
Signal (S); | Signal (F);
Signal (E); | Consume the item;
Which of the following interchange operations may result in a deadlock?
I. Interchanging Wait (F) and Wait (S) in the Producer process.
II. Interchanging Signal (S) and Signal (F) in the Consumer process.
(a) I only
(b) II only
(c) Neither I nor II
(d) Both I and II
Answer: (a) I only
Solution:
Case I – Producer me Wait(F) aur Wait(S) interchange:
Producer: Wait(S); Wait(F);
Agar Buffer Full hai (F=0, E=N). Producer mutex S le lega aur F=0 par block ho jayega. Consumer ko S chahiye item nikalne ke liye, par S Producer ke paas hai. Circular Wait -> DEADLOCK pakka lagega.
Case II – Consumer me Signal(S) aur Signal(F) interchange:
Consumer: Signal(F); Signal(S);
Signal ka order change karne se deadlock nahi lagta, sirf performance ka farak padta hai. Mutex S ko baad me chhodne se sirf thoda delay hoga, deadlock nahi.
Isliye sirf I deadlock dega.
1-Line Trick:
Producer me Mutex pehle liya aur Full par atka = Deadlock. Signal ka order interchange karne se kabhi deadlock nahi lagta.
Q 3.9 [2006 : 2M] – Snapshot – Deadlock Necessary Condition
Complete Question:
Consider the following snapshot of a system running n processes. Process i is holding xi instances of a resource R, for 1 ≤ i ≤ n. Currently all instances of R are occupied. Further, for all i, process i has placed a request for an additional yi instances while holding the xi instances it already has. There are exactly two processes p and q such that yp = yq = 0. Which one of the following can serve as a necessary condition to guarantee that the system is not approaching a deadlock?
(a) min(xp, xq) < max k≠p,q yk (b) xp + xq ≥ max k≠p,q yk (c) min(xp, xq) < 1 (d) min(xp, xq) > 1
Answer: (b) xp + xq ≥ max k≠p,q yk
Solution:
yp=yq=0 matlab p aur q ko aur resource nahi chahiye, ye dono finish ho sakte hain aur apne xp, xq resources release kar denge.
System deadlock me nahi jayega agar p aur q ke release karne ke baad kam se kam ek aur process apni need puri kar sake.
Total free after p,q finish = xp + xq
Kisi bhi other process k ki need = yk
To agla process tabhi chalega jab: xp + xq >= uski need yk
To agla process tabhi chalega jab: xp + xq >= uski need yk
Worst case ke liye sabse badi need wala bhi chal jana chahiye, isliye condition hai:
xp + xq >= max yk (where k ≠ p,q)
Agar ye condition fail hogi to koi bhi teesra process start nahi hoga, system deadlock ki taraf jayega.
1-Line Trick:
Jo 2 processes free hain unka sum, baaki me se sabse zyada maangne wale ki demand se bada hona chahiye. xp+xq >= max yk = Safe.
Q 3.10 [2007 : 2 Marks] – Banker’s Algorithm – Who Can Complete?
Complete Question:
A single processor system has three resource types X, Y, Z, which are shared by three processes. There are 5 units of each resource type. Consider the following scenario, where the column alloc denotes the number of units of each resource type allocated to each process, and the column request denotes the number of units of each resource type requested by a process in order to complete execution.
alloc request
X Y Z X Y Z
P0 1 2 1 1 0 3
P1 2 0 1 0 1 2
P2 2 2 1 1 2 0Which of the following is TRUE?
(a) P0
(b) P1
(c) P2
(d) None of the above, since the system is in a deadlock
Answer: (b) P1 can complete first – Safe sequence is P1 -> P0 -> P2. (Your book me (c) P2 tick hai, but calculation se P1 aata hai)
Solution:
Total = [5,5,5]
Sum Alloc = X:1+2+2=5, Y:2+0+2=4, Z:1+1+1=3
Available = Total – Alloc = [0,1,2]
Check Request <= Available: P0: [1,0,3] <= [0,1,2]? X 1>0 => NO
P1: [0,1,2] <= [0,1,2]? YES => P1 can complete.
P2: [1,2,0] <= [0,1,2]? X 1>0, Y 2>1 => NO
So first P1 will complete.
After P1 completes: Available = [0,1,2] + [2,0,1] = [2,1,3]
Now P0: [1,0,3] <= [2,1,3] YES
After P0 completes: Available = [2,1,3] + [1,2,1] = [3,3,4]
Now P2: [1,2,0] <= [3,3,4] YES
Full Safe Sequence = P1, P0, P2. System is NOT in deadlock.
1-Line Trick:
Available = Total – Sum Alloc. Jiska Request <= Available ho, usko chalao. Yaha sirf P1 ka request Available me fit hota hai.
Q 3.11 [2008 : 2 Marks] – Producer Consumer with S and Q Semaphore
Complete Question:
The following is a code with two threads, producer and consumer, that can run in parallel. Further, S and Q are binary semaphores equipped with the standard P and V operations.
semaphore S = 1, Q = 0;
integer x;
producer: consumer:
while (true) do While (true) do
P(S); P(Q);
x = produce(); consume (x);
V(Q); V(S);
done done
Which of the following is TRUE about the program above?
(a) The process can deadlock
(b) One of the threads can starve
(c) Some of the items produced by the producer may be lost
(d) Values generated and stored in ‘x’ by the producer will always be consumed before the producer can generate a new value
Answer: (d) Values generated and stored in ‘x’ by the producer will always be consumed before the producer can generate a new value
Solution:
S=1 (mutex for x), Q=0 (items count).
Flow:
Producer P(S) karke x produce karega, V(Q) karega.
Consumer P(Q) par block rahega jab tak Producer item na banaye. Jaise hi Q=1 hoga, Consumer x consume karega aur V(S) karke Producer ko next produce karne dega.
Ye 1-size ka synchronous buffer hai.
- Deadlock? Nahi. Producer aur Consumer ek-dusre ko signal de rahe hain. Circular wait nahi hai.
- Starvation? Nahi, dono alternate chalenge.
- Item Lost? Nahi, kyunki Producer S par block rahega jab tak Consumer S release na kare. Overwrite nahi hoga.
Isliye (d) sahi hai – Har produced value consume hogi before next produce.
1-Line Trick:
S=1, Q=0 = 1 Buffer Sync. Producer -> Consumer -> Producer… No deadlock, No loss, Every item consumed.
Q 3.12 [2008 : 2 Marks] – Policy: Release All Before New Request
Complete Question:
An operating system implements a policy that requires a process to release all resources before making a request for another resource. Select the TRUE statement from the following:
(a) Both starvation and deadlock can occur
(b) Starvation can occur but deadlock cannot occur
(c) Starvation cannot occur but deadlock can occur
(d) Neither starvation nor deadlock can occur
Answer: (b) Starvation can occur but deadlock cannot occur
Solution:
Policy: “Sab resources chhodo, tabhi naya mango”
- Deadlock? Hold and Wait condition tut gayi. Process ek resource pakad ke dusre ka wait nahi kar sakta, kyunki usko pehle wala chhodna padega. 4 conditions me se ek tuti to deadlock impossible. So Deadlock Cannot Occur.
- Starvation? Ho sakti hai. Ek process baar-baar sab resources release karke fir se request karega, par dusre processes ke wajah se usko kabhi saare resources ek saath na mile. Wo wait karta rahega – Starvation.
Isliye Starvation YES, Deadlock NO.
1-Line Trick:
Release All Before Request = Hold & Wait Todo = Deadlock Free, But Starvation Possible.