CSE Roadmap

Common tier · about 5 hours · 7 parts

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?

  • T2 still needs 2, and 3 are free. Grant them. T2 finishes and returns its 4 units. Free units: 3 − 2 + 4 = 5.
  • T1 needs 5, and 5 are free. Grant them. T1 finishes and returns 8 units. Free: 8.
  • T3 needs 5, and 8 are free. Grant them. T3 finishes. 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?