Deadlock Analysis

01 Lab overview

This lab contributes to U7.1 through U7.5, and to course learning outcomes CLO3 and CLO8.

02 Learning objectives

03 Background

3.1 The four necessary conditions

Deadlock can occur if and only if all four of the following conditions hold simultaneously:

• Mutual exclusion. At least one resource is non-shareable — only one process may hold it at a time.
• Hold and wait. A process holding at least one resource is waiting to acquire additional resources held by other processes.
• No preemption. A resource can be released only voluntarily by the process holding it.
• Circular wait. There is a closed chain of processes, each waiting for a resource held by the next.

The four conditions are independently necessary: if any one is removed, deadlock becomes impossible. This is why every prevention technique targets exactly one of them.

3.2 Resource allocation graphs

A resource allocation graph has two node sets (processes P and resources R) and two edge sets: a request edge from a process to a resource, and an assignment edge from a resource to a process. If every resource has a single instance, a cycle in the graph is a necessary and sufficient condition for deadlock. If resources have multiple instances, a cycle is necessary but not sufficient — the deadlock depends on which instance a process is waiting for.

3.3 Banker's algorithm

The Banker's algorithm is a deadlock avoidance technique. It maintains the matrices Allocation, Max, and the vector Available, and grants a request only if the resulting state is safe. A state is safe if there exists at least one sequence in which every process can finish using the currently available resources plus those held by processes that have already finished. If no such sequence exists, the request is denied (the requesting process is blocked and retries later).

# Safe-state test (n processes, m resource types)
Work = Available; Finish[i] = false for all i
while there is an i with Finish[i]==false and Need[i] <= Work:
    Work += Allocation[i]
    Finish[i] = true
return true if Finish[i] == true for all i

3.4 Detection and recovery

Detection runs a cycle-detection algorithm (for single-instance resources) or the Banker's-style reduction (for multiple instances) periodically or when the system suspects deadlock. Recovery may involve process termination (kill all deadlocked processes, or kill them one at a time until the cycle is broken) or resource preemption (take a resource from one holder and give it to a waiter, rolling the holder back to a safe point if the system supports checkpoints).

04 Guided activities

Activity 4.1 — Constructing a deadlock deliberately

1. Create the lab directory and the file deadlock_basic.c:

   mkdir -p ~/comp3150/lab6 && cd ~/comp3150/lab6

2. Write a program with two mutexes A and B and two threads. Thread 1 locks A, sleeps briefly, then locks B. Thread 2 locks B, sleeps briefly, then locks A. The sleep ensures the interleaving that produces deadlock.
3. Run the program. Confirm that it hangs. Attach gdb to the running process (gdb -p <pid>), and use info threads and thread apply all bt to show that each thread is blocked on a pthread_mutex_lock call for the mutex held by the other.
4. Take a screenshot or save the backtrace output as deadlock_basic.txt.
5. Verify with valgrind --tool=helgrind that the tool reports a lock-order inversion. What does the report say, and how does it identify the two locks and the two threads?

Activity 4.2 — Breaking the circular wait

1. Modify the program to impose a global lock ordering: both threads must acquire A before B. The deadlock disappears.
2. Now modify the program to release the first lock before acquiring the second (breaks hold-and-wait). The deadlock also disappears, but the program's semantics change — the operation is no longer atomic across the two locks.
3. Use pthread_mutex_trylock to implement the "no preemption" break: if the second lock cannot be acquired, release the first and retry. Add randomised back-off and verify the program terminates.
4. For each of the three fixes, write two sentences stating which of the four necessary conditions it removes.

Activity 4.3 — Resource allocation graph

1. For the program in Activity 4.1, draw the resource allocation graph. Each thread is a process node; each mutex is a resource node with one instance.
2. Render the graph with Graphviz (dot -Tpdf) and include it in your report.
3. Extend the program to a third thread and a third mutex in a configuration that produces a longer cycle. Draw the new graph and confirm that the cycle is a single closed chain.
4. Construct a program with no deadlock but a cycle in the graph. This is impossible for single-instance resources; explain why, and then construct the analogous case for multiple-instance resources: two processes each waiting for an instance of a resource, but the resource has two instances and the other process holds the one that satisfies its request.

Activity 4.4 — Banker's algorithm

1. Implement the Banker's algorithm in banker.c:
   • The program reads an Allocation matrix, a Max matrix, and an Available vector from standard input (or a file).
   • It implements safe_state() that returns the safe sequence if one exists, or reports that the state is unsafe.
   • It implements request(pid, request_vector) that checks the request against Need, the request against Available, and then tests the resulting state for safety before granting the request.
2. Test the implementation with the following state and verify that a safe sequence exists:

           Allocation   Max       Available
   P0      0 1 0        7 5 3     3 3 2
   P1      2 0 0        3 2 2
   P2      3 0 2        9 0 2
   P3      2 1 1        2 2 2
   P4      0 0 2        4 3 3

   One valid safe sequence is ⟨P1, P3, P4, P0, P2⟩. Write the state transitions step by step.
3. Now issue the request P1: (1, 0, 2). The request exceeds the need for resource type 1; the algorithm must deny it. Then issue P4: (3, 3, 0) — this request cannot be granted because it exceeds Available. Finally issue P0: (0, 2, 0) and show that granting it leads to an unsafe state.
4. Discuss the practical limitations of Banker's algorithm: the need to know Max in advance, the cost of the safety check on every request, and the fact that the algorithm cannot handle dynamic process arrival or resources that appear and disappear.

Activity 4.5 — Deadlock detection

1. Write detect.c that implements the detection algorithm for multiple-instance resources:

   Work = Available
   Finish[i] = (Allocation[i] == 0) for all i
   while exists i with Finish[i] == false and Request[i] <= Work:
       Work += Allocation[i]
       Finish[i] = true
   Deadlocked = {i : Finish[i] == false}

2. Feed the algorithm the states from Activity 4.4 and verify the expected results: after the initial state, no deadlock; after the erroneous grant of P0: (0, 2, 0) forced through, the deadlock set should be non-empty.
3. Add periodic detection to a running program: spawn four threads that acquire and release mutexes, and a fifth thread that every second runs the detector on a shared snapshot of the lock state. Log every detection event.
4. Simulate recovery by killing one of the detected deadlocked threads with pthread_cancel and verifying that the other threads proceed. Discuss why killing the wrong thread may leave shared data inconsistent, and how a real system decides which thread to victimise.

05 Exercises

06 Deliverables

Submit a single archive named lab6-<lastname>-<studentnumber>.tar.gz containing:

• deadlock_basic.c — Activity 4.1.
• deadlock_fixed.c — Activity 4.2 with three prevention strategies selectable by a command-line flag.
• banker.c — Activity 4.4.
• detect.c — Activity 4.5.
• philosophers.c — Exercise 1 (four prevention strategies selectable by a flag).
• waitfor.c — Exercise 4 (wait-for graph with recovery).
• The Makefile with one target per program and a clean target.
• deadlock_basic.txt — the gdb backtrace and Helgrind report from Activity 4.1.
• graphs/ — the Graphviz source and rendered PDFs for Activity 4.3.
• outputs.txt — the output logs of all programs with the commands that produced them.
• report.md (or report.pdf) — the lab report described below.

Lab report

The report should be 4–6 pages (excluding code) and contain:

1. Deadlock characterisation. For each deadlock you produce, identify which of the four necessary conditions hold and, for the fixes, which condition is removed. Use the resource allocation graph to justify each claim.
2. Banker's algorithm. The safe sequence for the test state, with the intermediate Work vectors, and the three denied requests with the reason for each denial.
3. Detection results. The deadlock sets produced by the detector for each test state, and the recovery decisions with their justification.
4. Throughput comparison. The measurements from Exercise 5, with a discussion of the trade-offs between the four strategies.
5. Reflection. A discussion of why Linux, Windows, and most general-purpose operating systems do not implement Banker's algorithm, and what they do instead (lock ordering discipline, timeout and roll-back in databases, and detection with killing in a few kernel subsystems).

07 Grading rubric

Late submission penalty: 10% per day, up to a maximum of three days, after which the lab is accepted only with documented extenuating circumstances.

08 Knowledge check

        Allocation   Max
P0      0 1 0        7 5 3
P1      2 0 0        3 2 2
P2      3 0 2        9 0 2
P3      2 1 1        2 2 2

09 References

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 8.
• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 32.
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 6.
• Coffman, E. G., Elphick, M. J., & Shoshani, A. System Deadlocks. ACM Computing Surveys, 1971.
• Havender, J. W. Avoiding Deadlock in Multitasking Systems. IBM Systems Journal, 1968.
• Dijkstra, E. W. Cooperating Sequential Processes. Academic Press, 1968.
• Linux man-pages: man 3 pthread_mutex_lock, man 3 pthread_mutex_trylock, man 1 valgrind (Helgrind section).