Systems Engineering · week 8 · station III

Concurrency

Threads, locks, load-reserved and store-conditional. Interleavings are a state space, and it explodes.

Threads

A thread is a process that shares the address space. Only the stack and the registers are its own.

Fork copies pages. A thread shares them: same page table, code, data and heap, a fresh stack. In selfie a thread is a context whose page table points to the parent's. A difference in how much isolation you keep.

Less isolation, cheaper communication: a global variable is a message. And the timer of week 5, invisible to a process, is now visible: it can fire between any two instructions, and the other thread sees memory as it was at that instant.

        // x = x + 1, as the compiler emits it
        ld   t0,-16(gp)   // read x
        addi t0,t0,1      // ← the timer can fire here
        sd   t0,-16(gp)   // write x
        // two threads, two increments, x goes up by one
      

The state space

Two threads of n instructions have C(2n, n) interleavings. The meaning of the program is the set of all of them.

20interleavings of two 3-instruction threads

≈ 10²⁹of two 50-instruction threads

2³⁵bits of state per thread, before interleaving

The Meaning chapter defined a program's meaning as the state it computes. With threads, the program has one meaning per interleaving, and the scheduler picks which. A program is correct if every interleaving is, and there are more of them than tests. The state-space explosion of the Size chapter, arriving from a new direction.

So concurrency is the second place in this class where testing shows presence and not absence, and where the honest tools are a proof for all interleavings, or a bound. Locks are the way to make most of the interleavings equivalent, so that fewer need to be considered.

Growth · the test, on interleavings

One more instruction per thread. About four times the interleavings.

n	C(2n, n)	× per +1
1	2
2	6	3.0
3	20	3.3
4	70	3.5
5	252	3.6
10	184,756	3.8
50	≈ 10²⁹	≈ 4

Two threads of n instructions each. The test for an exponential: add one to the input and the output multiplies. Here the factor climbs to four, so the count grows like 4ⁿ. A polynomial would answer plus one with a few percent.

Ten times the testing buys about two more instructions of coverage. That is why a race survives years of tests, and why a lock, which removes interleavings instead of visiting them, is the only tool that scales.

Locks

Mutual exclusion: at most one thread in the critical section. Acquiring the lock must itself be atomic.

A lock is a word: 0 free, 1 taken. Acquire: wait until it is 0, then set it to 1. Release: set it to 0. In between, the thread is alone with the shared data, and the interleavings inside the section collapse to one.

But "wait until 0, then set 1" is a load, a branch and a store, and the timer can fire between them: two threads both see 0 and both take the lock. The machine has to offer an instruction that cannot be interleaved.

Blocking

A thread that finds the lock taken can spin, burning its slice, or ask the kernel to block it: the third process state, now entered on a lock. And two threads each holding a lock the other waits for are blocked forever: deadlock, which week 12 places on the axis.

Atomic instructions

lr.d reserves. sc.d succeeds only if nobody wrote in between.

        // x = x + 1, lock-free
        retry:
          lr.d t0,(a0)       // load x, reserve a0
          addi t0,t0,1
          sc.d t1,t0,(a0)    // if reserved: store, t1 = 0
          bne  t1,zero,retry // interfered: retry
      

Load-reserved and store-conditional: the load remembers the address, the store checks that nobody wrote to it since, and fails instead of overwriting. A failed store is information, and the loop uses it.

RISC-U does not have them. Your assignment adds them to the machine, the emulator and the hypervisor: a new line in the instruction table, a new case in mipster's execute.

With these, a lock is four instructions and correct. Without them, no lock is.

Progress

Lock-free is a progress guarantee, not the absence of locks.

Blocking

A thread holding a lock that is preempted, or dies, stops every thread waiting for it. Progress depends on the scheduler being kind.

Lock-free

Some thread always completes in a bounded number of steps of the system. The lr/sc loop: if my store fails, someone else's succeeded. Livelock is possible; deadlock is not.

Wait-free

Every thread completes in a bounded number of its own steps. Stronger, rarer, and the only one that is a bound on a single thread rather than on the system. Bounds again, with different quantifiers.

Progress properties are the concurrency chapter's version of liveness: statements about the future of an execution, hence about all interleavings, hence exactly what testing cannot show.

Assignments

lock and threads.

lock: system calls lock() and unlock() on one global lock in the kernel. Acquire blocks the calling context; release wakes one waiter. The kernel is single-threaded: the door is the atomicity.
threads: pthread_create, pthread_join, pthread_exit: a context that shares the caller's page table and gets its own stack. Join blocks like wait.
Run two threads incrementing one global without a lock and watch the count; then with your lock. Then make the timeout one instruction.
./grader/self.py lock and ./grader/self.py threads.

Next week

Atomic instructions in the machine: lr.d and sc.d in RISC-U, mipster and hypster, and a thread-safe malloc built on them. Keep your threads; they are the test harness.

After this week

Listen, then read.

Listen

Bach · St John Passion — Netherlands Bach Society. The crowd choruses are threads: “Kreuzige!” is a fugue in which every voice enters on the same word at a different moment, and the interleaving is the meaning. A race condition, written out for four parts.

Read

The Art of Multiprocessor Programming — Herlihy and Shavit: the interleavings this class only counted, and every lock-free structure you might want, including the stack of week 10. And, more technical, Wait-Free Synchronization — Herlihy, 1991: the consensus hierarchy, why compare-and-swap and load-reserved can do what test-and-set cannot.

SE 09 · Runtime Systems →