CSE Roadmap

Core tier · about 5 hours · 8 parts

Part 8 of 8 · 3 min read

Exercises

Easy

Easy 1: Match the rule (20 minutes)

Match each rule with the condition it removes: (a) spool the output, (b) take all locks at once, (c) release on failure and retry, (d) take locks in numeric order.

Done when: four correct pairs, each with one reason.

Hint

Spooling is about who uses the device.

Easy 2: Fix the order (20 minutes)

A thread locks X then Y, and another locks Y then X. Give X rank 1 and Y rank 2 and rewrite the second thread so that it follows the rule.

Done when: the second thread takes X and then Y.

Hint

The order of unlocking does not matter for deadlocks, only the order of locking.

Easy 3: Spot the cost (20 minutes)

Give one cost for each of the four methods in section 1.

Done when: four sentences, one per method.

Hint

Think of idle resources, extra waiting, wasted attempts, and extra rules.

Medium

Medium 1: Make it safe by ordering (45 minutes)

Write the 4-account transfer program with random pairs and 4 threads, using lock ordering. Run it for 3 s and print the total.

Done when: no stuck run in 5 tries, and a total of 4,000.

Hint

Use lo and hi as in section 5, and skip the case a == b.

Medium 2: Try-lock with back-off (45 minutes)

Write the trylock version with a random pause of 1 to 10 microseconds. Count the failed second locks.

Done when: a working run with a count of retries, and a total of 4,000.

Hint

rand_r with a per-thread seed avoids a shared lock in the random generator.

Medium 3: One big lock (30 minutes)

Write the one-lock version and measure transfers per second with 2 and 4 threads, three runs each.

Done when: a table with six numbers and the range for each thread count.

Hint

Stop the threads with a flag and join them before you read the counters.

Hard

Hard 1: Compare the three (60 minutes)

Put the three programs behind one flag and run each with 2 and 4 threads, three runs of 2 s. Report transfers per second and say which was fastest on your machine.

Done when: a table of 18 runs summarised in six cells, and a sentence that says what you cannot conclude from it.

Hint

Use the same random seeds so the three programs do the same work.

Hard 2: Add the rank checker (60 minutes)

Wrap each account's lock in the RLock structure with rank equal to its account number. Run the correct program, then change one code path to lock in the wrong order, and show the abort message.

Done when: a correct run, and an abort with the account numbers in the message.

Hint

The top variable must be saved and restored in runlock, as in section 6.

Hard 3: Order by address (90 minutes)

Replace the account numbers by a rule based on the address of the lock ((uintptr_t)&acc->m). Handle a == b. Test with 2,000,000 random transfers.

Done when: a run with no stuck lock and a correct total, plus a note on why the address order works as well as the number order.

Hint

Compare pointers cast to uintptr_t, not with < on pointers of different objects.