Part 7 of 7 · 3 min read
Exercises
Easy
Easy 1: Name the condition (20 minutes)
For each case, name which of the four conditions it shows: (a) the printer prints for one job only, and the others wait, (b) a job holds the printer and asks for the scanner, (c) nothing can force a job off the printer, (d) job 1 waits for job 2 and job 2 waits for job 1.
Done when: four correct matches, each with one sentence of reason.
Hint
The condition that needs a cycle is the last one.
Easy 2: Is it a deadlock? (20 minutes)
Decide for each case whether it is a deadlock: (a) a thread waits for a reply from a server that is down, (b) two threads wait for each other's lock, (c) a thread loops forever in while(1);, (d) a thread locks a normal mutex twice.
Done when: four yes or no answers with a one-line reason each; cases (b) and (d) are deadlocks.
Hint
A deadlock needs the waiting threads to depend on each other, not on the outside world.
Easy 3: Count the instances (20 minutes)
A system has 2 printers, 3 tape drives, and 1 mutex called log_lock. List the resource types and the number of instances of each.
Done when: a table with three rows and the correct counts.
Hint
A type with several identical units counts once as a type.
Medium
Medium 1: Reproduce the deadlock (45 minutes)
Write the two-thread program of section 1 with a pause between the locks. Run it, and show the three lines of output. Then remove the pause and run it 100 times in a shell loop with timeout 2.
Done when: the stuck output with the pause, and a count of how many of the 100 runs finished (it may be all of them).
Hint
Use fflush(stdout) before _exit, or the lines may be lost when output goes to a pipe.
Medium 2: Find the owner (45 minutes)
Run your program under gdb, make it stop with abort() after 1 s, and use thread apply all bt and the __data.__owner field to draw the cycle.
Done when: a four-line cycle like the one in section 5, with the thread ids from your own run.
Hint
Compile with -g -O0 so that the lock names are visible.
Medium 3: Self-deadlock (30 minutes)
Write a program that locks a normal mutex twice in one thread, with a timeout. Then use PTHREAD_MUTEX_ERRORCHECK and print the error.
Done when: a hang in the first run, and error 35 with its text in the second.
Hint
pthread_mutexattr_settype sets the type before pthread_mutex_init.
Hard
Hard 1: Three threads, three locks (60 minutes)
Write a program with locks A, B, C and three threads: T1 takes A then B, T2 takes B then C, T3 takes C then A. Add a 0.1 s pause between the two locks. Show the deadlock and draw the cycle.
Done when: a stuck run, and a drawing with three threads and three locks in a ring.
Hint
Each thread needs its own first and second lock; the ring closes with T3 asking for A.
Hard 2: How long does it hide? (60 minutes)
Write the bank program with 4 accounts and 4 threads, with no pause between the locks and a 1 s watchdog on the second lock. Run it 20 times and record the number of transfers before it got stuck.
Done when: a list of 20 numbers with the minimum, the maximum and the median, and a sentence on what this means for testing.
Hint
Count transfers in a per-thread array and sum them when the watchdog fires.
Hard 3: Which condition is missing? (60 minutes)
Change your three-thread program in three different ways, each removing one of the four conditions. For each version, state which condition is removed and show that the program now finishes.
Done when: three finishing programs, each with a one-line note on the condition it removes.
Hint
The easiest changes are a common lock order, a trylock with release, and one big lock.