CSE Roadmap

Core tier · about 4 hours · 7 parts

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.