FIT2100 Chap.8 Semaphores and Deadlock
Semaphores and Deadlock
Semaphores coordinate concurrent work through atomic wait and signal operations. A binary semaphore can enforce one-at-a-time entry, while a counting semaphore represents several available resource instances. Correct use depends on the initial value, placement of operations and a signal on every completion or cleanup path.
Deadlock requires mutual exclusion, hold and wait, no preemption and circular wait.
Prevention removes a condition, avoidance keeps allocation in a safe state, detection searches for an existing deadlock, and recovery changes or terminates affected work. Banker-style safety analysis computes Need and Available and demonstrates a completion sequence rather than guessing from totals.
What this chapter covers
- 01
Semaphore operations
- 02
Binary and counting semaphores
- 03
Mutexes
- 04
Deadlock definition
- 05
Four necessary conditions
- 06
Prevention and avoidance
- 07
Detection and recovery
- 08
Banker safety analysis
Worked example · free
Find a safe resource sequence
- +2Total allocated is 2 + 3 + 1 = 6, so Available = 9 − 6 = 3.
- +2Remaining Need values are P1 = 2, P2 = 2 and P3 = 3 after subtracting Allocation from Max.
- +2P1 can finish with available 3 and releases 2, making 5. P2 can then finish and release 3, making 8.
- +2P3 then finishes. P1, P2, P3 is safe, while other orders may also satisfy every comparison.
Key terms
- Semaphore
- A synchronisation variable manipulated by atomic operations to control access or represent available capacity.
- Binary Semaphore
- A semaphore restricted to two availability states and often used for one-at-a-time access.
- Counting Semaphore
- A semaphore whose count represents multiple interchangeable resource instances.
- Deadlock
- A state in which each process in a set waits for an event that only another member can cause.
- Circular Wait
- A closed chain where each process waits for a resource held by the next process.
- Safe State
- A resource state with at least one order in which all processes can satisfy remaining needs and finish.
Semaphores and Deadlock FAQ
How does a counting semaphore differ from a mutex?
A counting semaphore represents a quantity of available capacity and need not encode ownership. A mutex expresses exclusive ownership more directly and is released by the owner under the intended discipline. The primitive should match the constraint.
Are the deadlock conditions sufficient?
All four conditions are necessary for deadlock to be possible. Under some resource models, finding them indicates risk rather than proving that a particular state is already stuck. A wait graph or safety calculation supplies the state-specific evidence.
How does prevention differ from avoidance?
Prevention imposes rules that eliminate at least one necessary condition, such as a global resource order. Avoidance examines requests against declared maximum demands and grants them only when the resulting state remains safe.
Why can deadlock prevention waste resources?
Conservative rules may require early reservation, forbid useful overlap or delay requests that would have completed without conflict. They buy certainty by restricting the set of allowed allocation patterns.
Assessment move
Write wait and signal around a named resource rule and explain the starting semaphore value. For deadlock, memorise the four conditions through diagnostic questions rather than initials alone. Practise safety matrices with fresh numbers, printing Allocation, Max, Need, Available and every update. Compare prevention, avoidance, detection and recovery on certainty, overhead and utilisation.
During demonstrations, show blocked and released states and explain why a particular operation wakes or cannot wake a waiter. For each semaphore program, write the invariant represented by every counter and justify its initial value from real capacity. In a bounded buffer, keep empty slots, filled slots and mutual exclusion as three separate responsibilities.
Trace one producer and consumer through waits, critical updates and signals, recording which operation can block and which resource is already held. Rearrange a wait deliberately and diagnose the dependency it creates. For deadlock, draw both a hold-and-wait table and a resource-allocation graph.
Test mutual exclusion, hold and wait, no preemption and circular wait with a concrete sentence; do not infer all four from the word “blocked.” State the resource-instance assumption before using a graph cycle as proof. For avoidance practice, generate new Allocation and Max matrices, verify non-negative Need, recompute Available from Total and show each component-wise comparison in a proposed safe sequence.
Try a request that leaves the state unsafe and explain why unsafe is not identical to already deadlocked. Compare a global lock order, acquire-all-at-once policy, Banker-style avoidance and detection with recovery on utilisation and information needs. During a demonstration, expose semaphore values or queue events carefully enough to explain progress without depending on a single scheduler interleaving.
Working through Semaphores and Deadlock in FIT2100? Sia is AskSia’s AI Computer Science tutor — ask any FIT2100 Semaphores and Deadlock question and get a clear, step-by-step explanation grounded in how FIT2100 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
