Deadlock
Deadlock¶
Overview¶
Deadlock is a state where two or more processes wait indefinitely for each other to release resources. In this lesson, we'll learn about the four necessary conditions for deadlock, resource allocation graphs, and methods for prevention, avoidance, detection, and recovery.
Table of Contents¶
- What is Deadlock?
- Deadlock Necessary Conditions
- Resource Allocation Graph
- Deadlock Prevention
- Deadlock Avoidance
- Deadlock Detection and Recovery
- Practice Problems
1. What is Deadlock?¶
Definition¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Deadlock β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Deadlock = Circular waiting state β
β = Two or more processes wait indefinitely for β
β each other's resources β
β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β β
β β Process A Process B β β
β β βββββββββ βββββββββ β β
β β β β ββR2 requestβββΆβ β β β
β β β R1 β β R2 β β β
β β β holds β βββR1 requestβββ holds β β β
β β β β β β β β
β β βββββββββ βββββββββ β β
β β β β
β β A waits for R2, B waits for R1 β β
β β β Both wait forever (deadlock) β β
β β β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Real-World Examples¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Real-World Deadlock Examples β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 1. Intersection deadlock: β
β β
β β β β
β β β² β β
β β β β β
β ββββββββΌββββββΌβββββββ β
β βββββ β β
β ββββββββΌββββββΌβββββββ β
β β βββββΆ β
β ββββββββΌββββββΌβββββββ β
β β β β β
β β βΌ β β
β β
β Four cars all waiting for the car in front β
β β
β 2. Bridge deadlock: β
β β
β βββββββββββββββββββββββββββββ β
β β ββββ ββββΆ β β
β β Car A Car B β β
β βββββββββββββββββββββββββββββ β
β Both entered from opposite ends of narrow bridge β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Code Example¶
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock2 = PTHREAD_MUTEX_INITIALIZER;
void* thread_A(void* arg) {
pthread_mutex_lock(&lock1);
printf("Thread A: acquired lock1\n");
sleep(1); // Increase deadlock probability
printf("Thread A: waiting for lock2\n");
pthread_mutex_lock(&lock2); // Deadlock!
printf("Thread A: acquired both\n");
pthread_mutex_unlock(&lock2);
pthread_mutex_unlock(&lock1);
return NULL;
}
void* thread_B(void* arg) {
pthread_mutex_lock(&lock2);
printf("Thread B: acquired lock2\n");
sleep(1); // Increase deadlock probability
printf("Thread B: waiting for lock1\n");
pthread_mutex_lock(&lock1); // Deadlock!
printf("Thread B: acquired both\n");
pthread_mutex_unlock(&lock1);
pthread_mutex_unlock(&lock2);
return NULL;
}
int main() {
pthread_t tA, tB;
pthread_create(&tA, NULL, thread_A, NULL);
pthread_create(&tB, NULL, thread_B, NULL);
pthread_join(tA, NULL);
pthread_join(tB, NULL);
printf("Done\n"); // Never reached if deadlocked
return 0;
}
/*
Output (when deadlocked):
Thread A: acquired lock1
Thread B: acquired lock2
Thread A: waiting for lock2
Thread B: waiting for lock1
... (wait forever)
*/
2. Deadlock Necessary Conditions¶
Four Necessary Conditions¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Four Necessary Conditions for Deadlock β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β All four conditions must hold simultaneously for β
β deadlock to occur (break one β no deadlock) β
β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β 1. Mutual Exclusion β β
β β - Resource can be used by only one process β β
β β at a time β β
β β - Other processes wait until resource is releasedβ β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β 2. Hold and Wait β β
β β - Process holds resources while waiting for β β
β β additional resources β β
β β - Requests more while keeping what it has β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β 3. No Preemption β β
β β - Resources cannot be forcibly taken away β β
β β - Process must voluntarily release them β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β 4. Circular Wait β β
β β - In process set {P0, P1, ..., Pn} β β
β β - Circular chain exists: P0βP1βP2β...βPnβP0 β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Circular Wait Visualization¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Circular Wait Example β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Three processes, three resources: β
β β
β βββββββββ β
β β P0 β β
β βββββ¬ββββ β
β holds: R0 β
β waits: R1 ββββββββββββ β
β β β β
β βΌ βΌ β
β βββββββββ βββββββββ β
β β R1 β β P1 β β
β βββββββββ βββββ¬ββββ β
β holds: R1 β
β waits: R2 ββββββ β
β β β β
β βΌ βΌ β
β ββββββββββββββββββ β
β β R2 ββ P2 β β
β ββββββββββββββ¬ββββ β
β holds: R2 β
β waits: R0 βββββΆ R0 β
β β (P0 holds) β
β ββββββββββββββββββββββ
β ββ
β P0 β R1 β P1 β R2 β P2 β R0 β P0 (circular!) ββ
β ββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
3. Resource Allocation Graph¶
Graph Notation¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Resource Allocation Graph (RAG) β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Nodes: β
β β’ Process: β (circle) β
β β’ Resource type: β‘ (rectangle) β
β - Internal dots (β): number of resource instances β
β β
β Edges: β
β β’ Request edge: Pi β Rj (Pi requests Rj) β
β β’ Assignment edge: Rj β Pi (Rj is assigned to Pi) β
β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Example β β
β β β β
β β β P1 ββββrequestββββΆ β‘ R1 β β
β β β β β β β
β β β β β
β β βΌ assignment β β
β β β P2 β β
β β β β
β β P1 requests R1 β β
β β One instance of R1 is assigned to P2 β β
β β R1 has 2 instances β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Graph with Deadlock¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Resource Allocation Graph with Deadlock β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β βββββββββββββββββββββββββββββββββββββββββββββββ β
β β β β
β β β P1 β β
β β ββ β β
β β requestβ β² assignment β β
β β βΌ β² β β
β β βββββββ β² β β
β β β R1 β β² β β
β β β β β β² β β
β β ββββ¬βββ β² β β
β β β β² β β
β β assignmentβ β² β β
β β βΌ β² β β
β β β P2 βββrequestββββΆ βββββββ β β
β β β β R2 β β β
β β β² assignment β β β β β
β β β² ββββ¬βββ β β
β β β² βassignmentβ β
β β β² βΌ β β
β β β²βββββββββββ P3 β β
β β β β β
β β β request β β
β β βΌ β β
β β βββββββ β β
β β β R3 β βββββββββ β β
β β β β β βassignmentβ β
β β βββββββ β β β
β β β P1 βββββββ β β
β β β β
β βββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Cycle: P1 β R1 β P2 β R3 β P3 β R2 β P1 β
β (or P2 β R3 β P3 β R2 β P2) β
β β
β β Deadlock exists! β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Cycles and Deadlock¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Relationship Between Cycles and Deadlock β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Rules: β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β’ No cycle β No deadlock β β
β β β’ Cycle exists: β β
β β - Single instance per resource β Deadlock β β
β β - Multiple instances per resource β Possible β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Cycle exists but no deadlock case: β
β β
β β P1 βrequestββΆ βββββββ ββrequestβ β P3 β
β β β R1 β β β
β β β ββ β β β
β β ββββ¬βββ β β
β β β β β
β β assign assign βΌ assign β assign β
β β β β β
β βββββββ β P2 β P4 βββββββββββββββ β
β β
β R1 has 2 instances β If P2 & P4 release, P1 & P3 β
β can proceed β Not deadlock β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
4. Deadlock Prevention¶
Breaking One of Four Conditions¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Deadlock Prevention β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 1. Break Mutual Exclusion β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β’ Use sharable resources when possible β β
β β β’ Example: read-only files β β
β β β’ Limitation: inherently exclusive resources β β
β β (printers, mutexes) β generally hard to break β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β 2. Break Hold and Wait β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Method 1: Request all resources at start β β
β β β’ Request all needed resources at once β β
β β β’ Downside: low resource utilization, starvationβ β
β β β β
β β Method 2: Release all before requesting new β β
β β β’ Return held resources before new request β β
β β β’ Downside: difficult to implement β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β 3. Break No Preemption β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β’ Force release of held resources if request failsβ β
β β β’ Or preempt resources from other processes β β
β β β’ Applicable: CPU registers, memory β β
β β β’ Difficult: mutexes, printers β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β 4. Break Circular Wait β
Most practical β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β’ Assign ordering number to resources β β
β β β’ Request resources only in ascending order β β
β β β’ Circular wait structurally impossible β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Circular Wait Prevention Code¶
#include <stdio.h>
#include <pthread.h>
// Assign ordering numbers to resources
// lock1 = resource 1 (order 1)
// lock2 = resource 2 (order 2)
pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock2 = PTHREAD_MUTEX_INITIALIZER;
// Always acquire in ascending order!
void* thread_A(void* arg) {
// Acquire in order: lock1(1) β lock2(2)
pthread_mutex_lock(&lock1); // Order 1
printf("Thread A: acquired lock1\n");
pthread_mutex_lock(&lock2); // Order 2
printf("Thread A: acquired lock2\n");
// Critical section
printf("Thread A: performing work\n");
pthread_mutex_unlock(&lock2);
pthread_mutex_unlock(&lock1);
return NULL;
}
void* thread_B(void* arg) {
// Same order: lock1(1) β lock2(2)
pthread_mutex_lock(&lock1); // Order 1
printf("Thread B: acquired lock1\n");
pthread_mutex_lock(&lock2); // Order 2
printf("Thread B: acquired lock2\n");
// Critical section
printf("Thread B: performing work\n");
pthread_mutex_unlock(&lock2);
pthread_mutex_unlock(&lock1);
return NULL;
}
int main() {
pthread_t tA, tB;
pthread_create(&tA, NULL, thread_A, NULL);
pthread_create(&tB, NULL, thread_B, NULL);
pthread_join(tA, NULL);
pthread_join(tB, NULL);
printf("Done (no deadlock!)\n");
return 0;
}
5. Deadlock Avoidance¶
Safe State vs Unsafe State¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Safe State vs Unsafe State β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Safe State: β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β’ All processes can complete without deadlock β β
β β β’ Safe sequence exists β β
β β β β
β β Safe sequence: <P1, P3, P4, P2, P0> β β
β β = All can complete if allocated in this order β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Unsafe State: β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β’ No safe sequence exists β β
β β β’ Deadlock possible (not necessarily occurring) β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β β
β β βββββββββββββββββββββββββββββββββββββββββββββββ β β
β β β Safe State β β β
β β β (Deadlock impossible) β β β
β β β β β β
β β βββββββββββββββββββββββββββββββββββββββββββββββ β β
β β β β
β β βββββββββββββββββββββββββββββββββββββββββββββββ β β
β β β Unsafe State β β β
β β β βββββββββββββββββββββββββββββββββββββββ β β β
β β β β β β β β
β β β β Deadlock State β β β β
β β β β β β β β
β β β βββββββββββββββββββββββββββββββββββββββ β β β
β β βββββββββββββββββββββββββββββββββββββββββββββββ β β
β β β β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Avoidance strategy: Maintain safe state only β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Banker's Algorithm¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Banker's Algorithm β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Developed by Dijkstra (1965) β
β Similar to how a banker lends to customers β
β β
β Data structures: β
β β’ n = number of processes β
β β’ m = number of resource types β
β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Available[m] β β
β β Number of available instances of each resource β β
β β β β
β β Max[n][m] β β
β β Maximum resources each process can request β β
β β β β
β β Allocation[n][m] β β
β β Resources currently allocated to each process β β
β β β β
β β Need[n][m] = Max[n][m] - Allocation[n][m] β β
β β Additional resources needed by each process β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Banker's Algorithm Example¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Banker's Algorithm Example β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Resource types: A, B, C (total: 10, 5, 7) β
β Processes: P0, P1, P2, P3, P4 β
β β
β Current state: β
β βββββββββββ¬βββββββββββββββββ¬ββββββββββββββ¬ββββββββββββββ
β β Process β Allocation β Max β Need ββ
β β β A B C β A B C β A B C ββ
β βββββββββββΌβββββββββββββββββΌββββββββββββββΌβββββββββββββ€β
β β P0 β 0 1 0 β 7 5 3 β 7 4 3 ββ
β β P1 β 2 0 0 β 3 2 2 β 1 2 2 ββ
β β P2 β 3 0 2 β 9 0 2 β 6 0 0 ββ
β β P3 β 2 1 1 β 2 2 2 β 0 1 1 ββ
β β P4 β 0 0 2 β 4 3 3 β 4 3 1 ββ
β βββββββββββ΄βββββββββββββββββ΄ββββββββββββββ΄ββββββββββββββ
β β
β Available = [3, 3, 2] (A:3, B:3, C:2 available) β
β β
β Safety check: β
β 1. Need[P1] = [1,2,2] β€ Available[3,3,2] β P1 can run β
β After P1: Available = [3,3,2] + [2,0,0] = [5,3,2] β
β β
β 2. Need[P3] = [0,1,1] β€ Available[5,3,2] β P3 can run β
β After P3: Available = [5,3,2] + [2,1,1] = [7,4,3] β
β β
β 3. Need[P4] = [4,3,1] β€ Available[7,4,3] β P4 can run β
β After P4: Available = [7,4,3] + [0,0,2] = [7,4,5] β
β β
β 4. Need[P0] = [7,4,3] β€ Available[7,4,5] β P0 can run β
β After P0: Available = [7,4,5] + [0,1,0] = [7,5,5] β
β β
β 5. Need[P2] = [6,0,0] β€ Available[7,5,5] β P2 can run β
β β
β Safe sequence: <P1, P3, P4, P0, P2> β
β β System is in safe state β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Banker's Algorithm Code¶
#include <stdio.h>
#include <stdbool.h>
#define P 5 // Number of processes
#define R 3 // Number of resource types
int available[R] = {3, 3, 2};
int maximum[P][R] = {
{7, 5, 3},
{3, 2, 2},
{9, 0, 2},
{2, 2, 2},
{4, 3, 3}
};
int allocation[P][R] = {
{0, 1, 0},
{2, 0, 0},
{3, 0, 2},
{2, 1, 1},
{0, 0, 2}
};
// Calculate Need
int need[P][R];
void calculate_need() {
for (int i = 0; i < P; i++)
for (int j = 0; j < R; j++)
need[i][j] = maximum[i][j] - allocation[i][j];
}
bool is_safe() {
int work[R];
bool finish[P] = {false};
int safe_sequence[P];
int count = 0;
// work = copy of available
for (int i = 0; i < R; i++)
work[i] = available[i];
while (count < P) {
bool found = false;
for (int i = 0; i < P; i++) {
if (!finish[i]) {
// Check if need[i] <= work
bool can_allocate = true;
for (int j = 0; j < R; j++) {
if (need[i][j] > work[j]) {
can_allocate = false;
break;
}
}
if (can_allocate) {
// Simulate resource reclamation
for (int j = 0; j < R; j++)
work[j] += allocation[i][j];
finish[i] = true;
safe_sequence[count++] = i;
found = true;
}
}
}
if (!found)
return false; // No safe sequence
}
printf("Safe sequence: ");
for (int i = 0; i < P; i++)
printf("P%d ", safe_sequence[i]);
printf("\n");
return true;
}
int main() {
calculate_need();
if (is_safe())
printf("System is in safe state.\n");
else
printf("System is in unsafe state!\n");
return 0;
}
6. Deadlock Detection and Recovery¶
Detection Algorithm¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Deadlock Detection Algorithm β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Single instance resources: β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Use Wait-for Graph β β
β β β β
β β Remove resource nodes from RAG: β β
β β β β
β β Pi β Rq β Pj transforms toβ Pi β Pj β β
β β (Pi requests Rq, Rq assigned to Pj) β β
β β β β
β β Cycle in wait-for graph β Deadlock β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Multiple instance resources: β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Use similar approach to Banker's algorithm β β
β β Safety check based on current requests β β
β β Identify set of deadlocked processes β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Detection frequency: β
β β’ Every resource request β high overhead β
β β’ Periodically (e.g., every 5 minutes) β
β β’ When CPU utilization drops β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Wait-for Graph Example¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Wait-for Graph Example β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Resource Allocation Graph: Wait-for Graph: β
β β
β βP1 βrequestββΆ β‘R1 βP1 ββββββββββ β
β β β assign β β β
β assignβ βP2 βP2 βββββββββ β
β β β request β β
β β‘R2 ββββββ βP3 βββββββββ β
β β assign β β β
β βP3 βrequestββΆ β‘R3 βassignβ βP4 βP4 ββββββ β
β β
β R1 β P2 β R2 β P3 β R3 β P4 β
β β
β Wait-for Graph: β
β P1 β P2 β P3 β P4 β P3 (cycle!) β
β β
β β Deadlock exists (P3, P4 are deadlocked) β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Deadlock Recovery Methods¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Deadlock Recovery Methods β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 1. Process Termination β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Method 1: Abort all deadlocked processes β β
β β β’ Certain but expensive β β
β β β’ Long-running processes also terminated β β
β β β β
β β Method 2: Abort one at a time β β
β β β’ Recheck for deadlock after each termination β β
β β β’ Selection criteria: priority, run time, resourcesβ β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β 2. Resource Preemption β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β’ Forcibly take resources from processes and β β
β β assign to others β β
β β β β
β β Considerations: β β
β β β’ Victim selection: which process to preempt β β
β β β’ Rollback: restore preempted process to safe stateβ β
β β β’ Starvation prevention: same process not repeatedlyβ β
β β victimized β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β 3. Checkpoint/Recovery β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β’ Periodically save process state (checkpoint) β β
β β β’ Rollback to previous checkpoint when deadlock β β
β β β’ Commonly used in database systems β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Deadlock Handling Method Comparison¶
ββββββββββββββββ¬βββββββββββββββ¬βββββββββββββββ¬ββββββββββββββββ
β Method β Overhead β Resource β Implementationβ
β β β Utilization β Complexity β
ββββββββββββββββΌβββββββββββββββΌβββββββββββββββΌββββββββββββββββ€
β Prevention β High β Low β Low β
β β β β β
ββββββββββββββββΌβββββββββββββββΌβββββββββββββββΌββββββββββββββββ€
β Avoidance β High β Medium β High β
β β β β β
ββββββββββββββββΌβββββββββββββββΌβββββββββββββββΌββββββββββββββββ€
β Detection/ β Medium β High β Medium β
β Recovery β β β β
ββββββββββββββββΌβββββββββββββββΌβββββββββββββββΌββββββββββββββββ€
β Ignore β None β Highest β None β
β (Ostrich) β β β β
ββββββββββββββββ΄βββββββββββββββ΄βββββββββββββββ΄ββββββββββββββββ
Ignore (Ostrich Algorithm):
β’ Assumes deadlock occurs rarely
β’ Manually reboot if it occurs
β’ Adopted by most OSes: Unix, Linux, Windows
β’ Practical approach
7. Practice Problems¶
Problem 1: Deadlock Necessary Conditions¶
Which of the following is NOT one of the four necessary conditions for deadlock?
A. Mutual Exclusion B. Circular Wait C. Priority Inversion D. No Preemption E. Hold and Wait
Show Answer
**Answer: C. Priority Inversion** Four necessary conditions for deadlock: 1. Mutual Exclusion 2. Hold and Wait 3. No Preemption 4. Circular Wait Priority inversion is a different concurrency problem from deadlock.Problem 2: Resource Allocation Graph¶
Determine if the following resource allocation graph represents a deadlock state.
P1 β R1, R1 β P2
P2 β R2, R2 β P3
P3 β R1
Show Answer
**Analysis:** - P1 requests R1 - R1 is assigned to P2 - P2 requests R2 - R2 is assigned to P3 - P3 requests R1 **Wait relationships:** - P1 β P2 (due to R1) - P2 β P3 (due to R2) - P3 β P2 (due to R1, which P2 holds) **Cycle:** P2 β P3 β P2 **Conclusion: Deadlock** (assuming single instance per resource)Problem 3: Banker's Algorithm¶
Determine if the system is in a safe state given:
Available = [1, 1, 2]
| Process | Allocation | Max |
|---|---|---|
| P0 | (0,1,0) | (2,2,2) |
| P1 | (1,0,0) | (1,1,2) |
| P2 | (0,0,1) | (1,2,3) |
Show Answer
**Calculate Need:** - P0: (2,2,2) - (0,1,0) = (2,1,2) - P1: (1,1,2) - (1,0,0) = (0,1,2) - P2: (1,2,3) - (0,0,1) = (1,2,2) **Safety check:** 1. Available = [1,1,2] 2. Need[P1] = [0,1,2] <= [1,1,2]? Yes! - After P1: Available = [1,1,2] + [1,0,0] = [2,1,2] 3. Need[P0] = [2,1,2] <= [2,1,2]? Yes! - After P0: Available = [2,1,2] + [0,1,0] = [2,2,2] 4. Need[P2] = [1,2,2] <= [2,2,2]? Yes! - After P2: Done **Safe sequence:Problem 4: Circular Wait Prevention¶
Explain the method of assigning ordering to resources to prevent circular wait, and prove why this method prevents deadlock.
Show Answer
**Method:** - Assign unique ordering number to all resource types - Processes must request resources only in ascending order **Proof:** For circular wait to occur: P0 β R(i0) β P1 β R(i1) β ... β Pn β R(in) β P0 Each arrow means "holds then requests": - P0 holds R(i0) and P1 waits for R(i0) - P1 holds R(i1) and P2 waits for R(i1) - ... - Pn holds R(in) and P0 waits for R(in) By ascending order rule: - For P0 to request R(in), must have i0 < in - But if circular: in < i0 < i1 < ... < in (contradiction!) Therefore circular wait impossible β deadlock impossibleProblem 5: Deadlock Recovery¶
When using the "abort one process at a time" recovery method after deadlock occurs, explain the criteria for selecting victims.
Show Answer
**Victim selection criteria:** 1. **Process priority** - Terminate lower priority processes first 2. **Execution time** - Terminate processes that ran for shorter time (minimize loss) - Or protect processes near completion 3. **Resource usage** - Terminate processes holding more resources (free more resources) 4. **Resources needed to complete** - Terminate processes needing many more resources 5. **Process type** - Protect interactive processes over batch jobs 6. **Starvation prevention** - Prevent same process from being repeatedly victimized - Count and limit number of terminations **Optimal selection:** Define cost function as weighted sum of above criteria, select minimum cost processNext Steps¶
This completes the process synchronization section. Next learning topic: - 10_Memory_Management_Basics.md - Memory management