CSE Roadmap

Core tier · about 4 hours · 7 parts

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.