Deadlock
Deadlock and Coffman's four conditions, the allocation graph, prevention through a lock order, avoidance through the banker's algorithm, and how it differs from starvation and livelock.
- 26 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- Scenarios
- Understand
A few cards from the deck
Deadlock: what is it?
Show the answer
A situation where each thread in a group waits for a resource held by another in the group: none can move on.
With blocking locks, the threads are asleep, not busy: the processor is idle and the program is frozen with no error message.
Which interleaving of these two threads leads to deadlock?
```c
/* T1 */ /* T2 */
lock(&a); lock(&b);
lock(&b); lock(&a);
... ...
unlock(&b); unlock(&a);
unlock(&a); unlock(&b);`- T1 takes a, T2 takes b, then each wants the other lock
- T1 runs everything up to its two unlocks, then T2 runs everything
- T2 runs everything up to its two unlocks, then T1 runs everything
- T1 takes a then b, and T2 waits for b while T1 works
Show the answer
T1 takes a, T2 takes b, then each wants the other lock
In the other three cases, one thread finishes or clears the way for the other. Deadlock requires each to hold a lock at the moment it asks for the other: that is circular wait.
Coffman's four conditions, all necessary for a deadlock: …, …, … and ….
Show the answer
Coffman's four conditions, all necessary for a deadlock: mutual exclusion, hold and wait, no preemption and circular wait.
Making just one of them impossible is enough to prevent any deadlock: that is the principle of prevention.
Resource-allocation graph: what is it?
Show the answer
A graph whose vertices are the threads and the resources, with one edge for each resource held and one for each pending request.
A cycle on single-instance resources means deadlock; with several instances, a cycle is necessary but not sufficient.
A two-thread program is frozen.
topshows 0% CPU, andgdbshows both threads insidepthread_mutex_lock. What is it?- A deadlock: each thread waits for the other's mutex
- A livelock: both threads keep restarting in an endless loop
- Starvation: one thread is always overtaken by the other at every turn
- Busy waiting: each thread keeps testing the other's mutex in a loop
Show the answer
A deadlock: each thread waits for the other's mutex
CPU at 0% and threads asleep in lock: they are waiting, not running. A livelock or busy waiting would push the CPU up, and starvation would let the other thread move on.