Part 3 of 7 · 2 min read
Safe states
Take one resource type with 10 units, and three threads. This is a made-up example to show the idea:
| Thread | Holds | Maximum claim | Still may need |
|---|---|---|---|
| T1 | 3 | 8 | 5 |
| T2 | 2 | 4 | 2 |
| T3 | 2 | 7 | 5 |
The free units are 10 − (3 + 2 + 2) = 3. Is there an order in which every thread can get its full claim and finish?
T2still needs 2, and 3 are free. Grant them.T2finishes and returns its 4 units. Free units: 3 − 2 + 4 = 5.T1needs 5, and 5 are free. Grant them.T1finishes and returns 8 units. Free: 8.T3needs 5, and 8 are free. Grant them.T3finishes. Free: 10.
In plain words: The order T2, T1, T3 works. Such an order is a safe sequence, and a state that has one is a safe state. A state with no safe sequence is unsafe.
An unsafe state is not yet a deadlock. It means only that if every thread now asked for its full claim, the system could end in a deadlock. Threads may not ask for the full claim, or may finish earlier. So "unsafe" is a warning, not a verdict, and a system that stays in safe states can never deadlock.
Now see what happens with requests, starting from the safe state above:
| Request | Free after grant | Can a thread finish? | Decision |
|---|---|---|---|
| T1 asks 1 | 2 | T2 needs 2: yes, then T1, then T3 |
Safe, grant |
| T2 asks 2 | 1 | T2 needs 0: yes, then T1, then T3 |
Safe, grant |
| T1 asks 2 | 1 | T1 needs 3, T2 needs 2, T3 needs 5: none |
Unsafe, refuse |
| T3 asks 2 | 1 | T1 needs 5, T2 needs 2, T3 needs 3: none |
Unsafe, refuse |
Each refused request would leave 1 free unit, and nobody could finish with it. The refusal is a safety margin: the thread waits, and the other threads keep running until one finishes and returns units.
Safe state
A safe state is a state of the system in which there is some order of the threads, called a safe sequence, such that each thread can get all it may still need from the free resources plus those returned by the threads before it in the order.
Example: with 3 free units, the order T2, T1, T3 is a safe sequence for the table above.
Common mistake
An unsafe state is not a deadlocked state. It is a state from which the system can no longer promise that all threads will finish. Refusing a request in an unsafe state is cautious, and sometimes the refusal was not needed.
Check yourself: 1. In the table, why is "T2 asks 2" safe but "T1 asks 2" unsafe? 2. What is a safe sequence? 3. Does an unsafe state always end in deadlock?