Operating System

Answer: (iii) Deadlock avoidance

Banker's algorithm (avoidance) dynamically checks safe state before allocating. Prevention prohibits one of four necessary conditions, Detection+Recovery allows deadlock then resolves, Ignoring (ostrich) does nothing.

Answer: (iv) none of these

Deadlock with single resource: a cycle + hold-and-wait can occur with ≥2 processes, but single instance per type needs cycle. With single resource instance total, deadlock impossible if max need is properly handled via ordering—question phrasing expects "none of these" as single resource deadlock requires circular wait which needs at least two processes holding different instances; trick question often marks none.

Answer: (iii) Deadlock avoidance

Avoidance (Banker's) requires knowledge of future maximum needs to compute safe state. Prevention needs only structural guarantees, Detection works after the fact.

Answer: (iv) All of the above

Coffman conditions for deadlock: Mutual exclusion, Hold-and-wait, No preemption, Circular wait. All four must hold simultaneously.

Answer: (i) Banker's algorithm

Banker's (Dijkstra) is avoidance — checks safe state before grant. Round-robin is CPU scheduling, Elevator is SCAN disk scheduling.

Answer: (ii) 5

Formula for deadlock-free guarantee with single instance type needing up to k=2 per process: n*(k-1)+1 ≤ total => n*1+1 ≤6 => n≤5. So max 5 processes; 6th would allow deadlock if each holds 1 and waits for 1. (Some texts give 4 with stricter Max-need=2 → worst-case hold 1, need 1 extra, need n+1 ≤6 → n=5 same). Detailed: if each needs 2, safe sequence needs at least 1 process to complete to release.

Justification: Cycle in RAG implies deadlock only with single instance per resource type. With multiple instances, a cycle may not imply deadlock because another instance may satisfy request and break cycle. Example: 2 instances of R1, P1 holds R1, P2 holds R1, each requests other — cycle exists but resources can be allocated to break it. Deadlock requires cycle + each resource in cycle has only one instance (or unsatisfiable request). Hence cycle is necessary but not sufficient for multiple instances.

Resource allocation X,Y,Z (5 each) alloc vs request

Total allocated: X=5(1+2+2),Y=4(2+0+2),Z=3(1+1+1) → Available =5-allocated = X0,Y1,Z2 initially? Actually given no available row, compute: assume total 5 each → Avail = Total - sumAlloc = X0,Y1,Z2. Need calc Need=Request.
Check P1 Need 0,1,2 ≤ Avail 0,1,2 → P1 can finish first, release 2,0,1 → Avail 2,1,3. Then P0 Need 1,0,3 ≤ Avail 2,1,3 → P0 finishes last? Let's simulate order P1→P0→P2 gives finish first P1, last P0/P2 depending. Detailed safe sequence P1,P2,P0 => first P1, last P0.

Banker's Safe State Check (5 processes A-D)

Available 1,5,2,0. Need = Max-Alloc.
P0 Need 0,0,0,0 → can run, completes, releases 0,0,1,2 → Avail 1,5,3,2.
P3 Need 0,0,2,0 ≤ Avail → run → Avail 1,11,6,4.
P1 Need 0,7,5,0 ≤ Avail → run → Avail 2,11,6,4.
P2 Need 1,0,0,2 ≤ Avail → run → Avail 3,14,11,8.
P4 Need 0,6,4,2 ≤ Avail → finishes.
Safe sequence P0→P3→P1→P2→P4 exists, so system is safe.

Deadlock Avoidance Principle

Requires safe state check before grant. Resource allocation graph with cycle but no deadlock: use multiple instances. Example: 2 instances of R1, P1 holds R1, P2 holds R1, P1 requests R2, P2 requests R2 held elsewhere — cycle exists but extra instance breaks deadlock. Draw RAG with cycle and extra resource free.

Same as Q113 — Banker's safe sequence P0→P3→P1→P2→P4, system is safe. Need = Max-Alloc, check Available 1,5,2,0. P0 need 0 passes, then P3 etc. Detailed as previous.

Necessary Conditions (Coffman)

1 Mutual Exclusion 2 Hold-and-Wait 3 No Preemption 4 Circular Wait

Handling

• Prevention (break one condition)
• Avoidance (Banker's, safe state)
• Detection & Recovery (wait-for graph, kill/preempt)
• Ignorance (ostrich, used by Unix/Windows)

Deadlock Prevention per Condition

1. Mutual Exclusion: make resource shareable (read-only, spooling)
2. Hold-and-Wait: require process to request all resources at once, or release held before new request
3. No Preemption: allow OS to preempt resources
4. Circular Wait: impose total ordering of resource types, request in order

Banker's Request P1 (1,0,2) with Available 3,3,2

Check Need P1 = Max-Alloc = 1,2,2. Request 1,0,2 ≤ Need (1,2,2) and ≤ Available (3,3,2) → pretend allocate: Avail becomes 2,3,0, Alloc P1 becomes 3,0,2.
Check safe: Need remaining: P0 7,4,3, P1 0,2,0, P2 6,0,0, P3 0,1,1, P4 4,3,1. No safe sequence because Avail 2,3,0 insufficient for any Need → request cannot be granted, would lead to unsafe state, P1 must wait.

Deadlock Definition & Conditions

Deadlock = set of processes blocked each waiting for resource held by another, circular wait.
Four Coffman conditions: Mutual Exclusion, Hold-and-Wait, No Preemption, Circular Wait.
Max n for 6 units, need 3 per process: For deadlock-free, n*(need-1)+1 ≤6 → n*2+1≤6 → n≤2 (integer). So n=2 deadlock-free, n=3 may deadlock. Some texts give n=2.

Deadlock Recovery

• Process termination: abort all deadlocked or one by one (victim selection by priority/cost), rollback.
• Resource preemption: preempt resources, roll back process to safe state, starvation avoidance. Requires selecting victim, rollback, starvation prevention.

Banker's Algorithm

Safe-state avoidance algorithm. Data: Available, Max, Allocation, Need=Max-Alloc. Safety check finds safe sequence where each Need ≤ Available + releases. Request grant checks Request≤Need and Request≤Available then simulates safety. Ensures deadlock avoidance.