Deadlock Detection and Recovery

Detection and Recovery

Unlike prevention, detection does not require restricting requests in advance to break a necessary condition. The OS can run detection periodically. Waiting cycles suffice for single-instance resources; multiple-instance resources also require checking requests and available quantities.

When deadlock is found, common recovery methods include:

1. Abort: terminate some or all deadlocked processes and reclaim their resources, considering process priority and termination cost.
2. Rollback: restore one or more processes to a state that avoids deadlock and releases resources. This requires stored history and restoration points.

Dining Philosophers

Taking the left chopstick before the right can deadlock. To let all philosophers eat, the algorithm must prevent deadlock and starvation. Allowing at most four philosophers into the dining room prevents a five-way waiting ring, letting at least one obtain two chopsticks and release them after eating. This is prevention; avoiding starvation additionally requires fair admission and resource allocation.

Semaphore capacity = 4;

Process philosopher(index) {
	do {
		wait(capacity);
		wait(chopstick[index]);
		wait(chopstick[(index + 1) % 5]);
		eat;
		signal(chopstick[(index + 1) % 5]);
		signal(chopstick[index]);
		signal(capacity);
	} while (true);
}