Chapter 08 · Reps

Concurrency, Threads, and Midterm Review — Reps

← Back to Chapter 8

Chapter 8 — Reps

Conditioning, not grading. Concurrency drills and midterm consolidation this week, all in Python.

Ground rules:

  1. Type every line yourself. No copy-paste — not even from this chapter’s code/ folder. The point is the muscle, and the muscle is in the typing.
  2. Run everything. Concurrency bugs do not show up by reading. Run each rep, watch the output, and run the threaded ones several times — a race shows itself in the variation between runs.
  3. AI stays OFF. Phase 1, and the last week of it. The midterm has no AI; your practice has none either. You cannot direct an agent to choose threads-or-processes well if you have never paid the price of choosing wrong yourself.
  4. Measure, don’t assume. Where a rep involves speed, put a time.perf_counter() clock on it and report the actual number. A claim about cost you didn’t measure is a guess wearing a lab coat.

Toolchain setup (real Python 3.10+, a real editor, git) is in Appendix A. Everything here runs with a bare python3 file.py.

Reps 1–3: Races and Locks

Rep 1 — Reproduce the Race, Then Kill It

Write a program with a module-level counter = 0 and a worker() that loops 100,000 times doing counter += 1. Start eight threads running worker, join them all, and print counter. The expected total is 800,000.

Run it five times. If your counter comes out correct every time, your machine’s interpreter isn’t switching threads aggressively enough to expose the race on this simple statement — add import sys; sys.setswitchinterval(1e-6) at the top and split the increment into three explicit lines (c = counter; c = c + 1; counter = c) to widen the race window. Re-run. Now watch updates vanish.

Then add a threading.Lock() and wrap the increment in with lock:. Re-run five times. Confirm the total is exactly 800,000 every time.

Write one sentence: why did the unsafe version lose updates? (Answer in terms of read-modify-write not being atomic.)

Rep 2 — Smallest Critical Section

Take your locked program from Rep 1. Now make each worker do a little independent busywork before the increment — local = sum(range(50)) — work that touches no shared state.

Write it two ways and time both with time.perf_counter():

  • Coarse: the entire loop body (busywork + increment) inside with lock:.
  • Fine: the busywork outside the lock, only the counter += 1 inside.

Report both times. The fine version should be faster, because the coarse version forces threads to run single-file through work that didn’t need protecting. Write one sentence on what you learned about the cost of holding a lock too long.

Rep 3 — Define Deadlock

No code for this one — a written rep. In your own words (three to five sentences):

  1. What is a deadlock?
  2. Give the classic two-lock scenario that produces one.
  3. State the standard prevention rule.

Then answer: in a producer/consumer pipeline built on queue.Queue, why do you not have to worry about deadlock between your own locks? (Hint: how many locks did you write?)

Reps 4–5: The GIL

Rep 4 — I/O-Bound vs CPU-Bound, Timed

Write two task functions:

def io_task():
    time.sleep(0.25)

def cpu_task():
    total = 0
    for i in range(5_000_000):
        total += i * i

For each task, run it 4 times serially and time it, then run 4 copies in 4 threads and time it. Print a small table:

            serial    threads   speedup
io_task     ?.???s    ?.???s    ?.??x
cpu_task    ?.???s    ?.???s    ?.??x

You should see a large speedup (near 4x) for io_task and roughly no speedup for cpu_task. Write two sentences explaining the difference using the word “GIL” and the phrase “released during I/O.”

Rep 5 — Processes Fix CPU-Bound

Take cpu_task from Rep 4. Run 4 copies three ways and time each: (a) serial, (b) 4 threads, (c) 4 processes via multiprocessing.Pool. Print the three times and the speedup of each versus serial.

Confirm: threads give ~1x (no help), processes give a real speedup (but not a clean 4x — note the gap). Write one sentence explaining why processes help where threads don’t, and one sentence explaining why the process speedup falls short of a perfect 4x (hint: process creation and the cost of shipping data across the boundary).

Don’t forget the if __name__ == "__main__": guard, or your program will spawn processes recursively.

Reps 6–8: Producer/Consumer with a Queue

Rep 6 — A Correct Pipeline

Build a producer/consumer pipeline with queue.Queue:

  • 2 producer threads, each putting 1,000 integers on the queue (2,000 items total).
  • 3 consumer threads, each pulling items and counting how many it processed.
  • A poison pill (None) per consumer to shut them down cleanly.

Track total items consumed in a shared counter guarded by its own lock (the consumers race on that counter otherwise — a race inside your race fix). At the end, assert the total consumed equals 2,000 and assert the queue is empty. The assertion is the rep: it is the “exactly once” correctness proof the midterm grades.

Rep 7 — Break It on Purpose

Take your Rep 6 pipeline and remove the lock around the consumed-counter increment. Run it ten times. Does the assertion ever fail? (It may take several runs, and adding sys.setswitchinterval(1e-6) will make it fail reliably.)

This is the most important rep of the week: you wired up a thread-safe queue and still introduced a race — in your own bookkeeping. The queue guarantees safe hand-off of items; it does not guarantee safe updates to a counter you keep on the side. Restore the lock. Confirm green. Write one sentence: where, exactly, was the race?

Rep 8 — Forget the Poison Pill

Take your correct Rep 6 pipeline. Comment out the loop that puts the poison pills. Run it. The program will hang — the consumers are blocked forever on queue.get() of an empty queue, and main is blocked forever on join. Kill it with Ctrl-C.

Restore the poison pills. Run again; confirm it exits cleanly. Write one sentence on why a blocking get() plus a missing sentinel equals a hang.

Reps 9–10: Midterm Consolidation

Rep 9 — Pick the Tool

For each workload below, write down (a) threads, processes, or event loop, and (b) one sentence of justification. No code — this is the architect’s reflex, drilled.

  1. Download 200 web pages and save them to disk.
  2. Multiply two large matrices, pure Python.
  3. A chat server handling 5,000 mostly-idle simultaneous connections.
  4. Resize 1,000 images (CPU-heavy per image).
  5. Poll 50 sensors that each take ~100 ms to respond.
  6. A single-threaded program that needs to stay responsive to the user while loading a big file.

Then check yourself against the right-tool table in §8.7.

Rep 10 — The Cost Table, From Memory

Close the textbook. On a blank page, reproduce as much of the §8.8 cost table as you can: for each of array (static + dynamic), singly/doubly linked list, stack, queue, deque, hash table, BST, and graph (list + matrix) — write its search cost, its insert cost, and the one workload it is for.

Then open §8.8 and grade yourself. Circle every cell you missed. Those cells are your last day of study. Do this rep again on Day 6 and the morning of the exam; the gaps should shrink each time.

Rep 11 — Hash Table vs BST, Out Loud

A written rep, to drill the single most-tested judgment of Phase 1. Answer in full sentences:

  1. Both a hash table and a balanced BST give you fast lookup. Name three things the BST can do that the hash table cannot.
  2. Name the one thing the hash table does better, and its cost (Big-O) for that operation, average and worst case.
  3. You are choosing the index type for a database column you will query with WHERE created_at BETWEEN x AND y. Which structure, and why? (This is a real Phase 2 decision in disguise.)

Done? One Last Thing.

The midterm dress rehearsal. Set a 60-minute timer. Close this file, close code/, close everything but a blank editor and (if you must) the printed textbook.

From scratch, build a producer/consumer pipeline:

  • 2+ producers putting work items on a queue.Queue.
  • 2+ consumers pulling and “processing” them (a time.sleep(0.001) is fine as the work).
  • Clean shutdown via poison pills.
  • A correctness proof: track items consumed under a lock and assert at the end that every item produced was consumed exactly once and the queue is empty.

If you can do this cold, in under an hour, with the assertion passing on every run — you are ready for the Normal tier of the midterm. If you finish early, add the Medium tier: time an I/O-bound vs a CPU-bound version of the consumer’s work and confirm threads help one and not the other.

Then, and only then, open code/producer_consumer.py and compare. Notice where your structure differs. That comparison is worth more than the build.

Up next: Project 8 — Project 8: Concurrent Data Pipeline, the midterm. Sixty minutes, closed AI, closed internet, open textbook. Then, after the exam, Chapter 9 begins Phase 2.