Part 7 of 7 · 2 min read
Exercises
Easy
Easy 1: Trace the loss (20 minutes)
Redo the interleaving table with thread B starting 2 steps after thread A, so that B loads after A has stored. What is the final counter value?
Done when: you show 2, and explain that no update is lost in that order.
Hint
The loss needs both threads to load before either stores.
Easy 2: Safe or not (20 minutes)
For strtok, strtok_r, rand, localtime_r and printf, say whether each is thread-safe on Linux, using the manual pages.
Done when: a table, with printf marked safe because it locks its stream inside.
Hint
man strtok has an ATTRIBUTES section.
Easy 3: Private or shared (20 minutes)
For a local variable, a global, a __thread variable and a malloc block whose address is passed to all threads, say whether it needs a lock.
Done when: no, yes, no, yes.
Hint
A lock is needed when two threads can touch the data and one writes.
Medium
Medium 1: Reproduce the race (30 minutes)
Run the unlocked counter program ten times. Record the ten results, their smallest and their largest values.
Done when: ten different numbers all below 2,000,000.
Hint
Compile without optimisation, -O0.
Medium 2: Lock it (30 minutes)
Add the mutex. Run ten times and confirm every result is 2,000,000. Time both programs with time.
Done when: ten correct results and two timings with the ratio.
Hint
The locked version is slower because the threads wait for each other.
Medium 3: Fix localtime (30 minutes)
Change the localtime test to localtime_r with a buffer per thread. Run it 2,000 rounds and check that no message appears.
Done when: zero buffer changed lines.
Hint
struct tm buf; localtime_r(&t, &buf);.
Hard
Hard 1: Per-thread counters (60 minutes)
Fix the counter without a lock: each thread counts in its own local variable and returns it, and the main thread adds the two results. Time it against the mutex version.
Done when: the answer is 2,000,000 and the time is close to the original unlocked version.
Hint
A local long per thread, returned through pthread_exit or a result struct.
Hard 2: Count lost updates (60 minutes)
Run the racy program with 1, 2, 4 and 8 threads (1,000,000 increments each). Tabulate the fraction of increments lost for each.
Done when: a table with 0 per cent for one thread and a rising loss with more threads, plus one sentence explaining why.
Hint
Loss = 1 − result / (threads × N).
Hard 3: A thread-safe random generator (60 minutes)
Write a function that returns random numbers using a __thread state, so that threads need no lock. Start four threads that each print five numbers from a different seed and show the sequences differ.
Done when: four sequences, repeatable if the seeds are the same, and no use of rand.
Hint
Keep one static __thread unsigned state and update it with a simple formula such as a linear congruential generator.