CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 7 of 7 · 2 min read

Exercises

Easy

Easy 1: Who can enter? (20 minutes)

A read-write lock is held in read mode by two threads. Say which of a new reader and a new writer can enter at once.

Done when: the reader can (with reader preference), and the writer must wait.

Hint

Readers share, a writer needs everyone out.

Easy 2: Spot the cycle (20 minutes)

Five philosophers each hold the left fork and wait for the right. Write the wait-for chain.

Done when: P0 waits for P1 waits for P2 waits for P3 waits for P4 waits for P0.

Hint

Each waits for the next philosopher's fork.

Easy 3: Pick the lock (20 minutes)

Choose mutex or read-write lock for: a counter incremented by every thread, and a settings table read by every request and changed once a day.

Done when: mutex for the counter and read-write lock for the table.

Hint

A counter has no read-only phase.

Medium

Medium 1: Measure readers (45 minutes)

Write the mutex and read-write lock test with 1, 2 and 4 reader threads. Report the times.

Done when: a table in which the read-write lock stays flat up to your processor count while the mutex grows.

Hint

Keep the work under the lock the same in both runs.

Medium 2: Starve the writer (45 minutes)

Write the test with three overlapping readers and a writer using pthread_rwlock_timedwrlock. Run it with both preference settings.

Done when: a timeout under reader preference and a short wait under writer preference.

Hint

PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP is the writer setting.

Medium 3: Deadlock the philosophers (30 minutes)

Write the naive philosophers with a 1 ms pause between the two locks. Run it with a timeout and show that nobody eats.

Done when: 0 meals and a stuck report.

Hint

End the program with _exit after a timer, since it cannot join.

Hard

Hard 1: Both fixes (60 minutes)

Add the ordering fix and the seat-limit fix. Run 2 seconds each and report meals per philosopher.

Done when: a table like section 4, and a sentence on fairness.

Hint

Use the same pauses in both fixes.

Hard 2: Back off and retry (60 minutes)

Replace the second lock by trylock: if it fails, put the first fork down, wait a random 1 to 3 ms and retry. Count the meals and the retries.

Done when: a working run with some retries, and a note on the risk of livelock.

Hint

Release the first fork before the pause.

Hard 3: A fair read-write lock (90 minutes)

Build a read-write lock from a mutex and condition variables that serves waiting threads in order of arrival, and test that neither a writer nor a reader starves in the overlapping-readers test.

Done when: the writer gets the lock in under 100 ms and no reader waits more than 1 s.

Hint

Use a ticket number for each arriving thread.