CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 5 of 7 · 2 min read

Cost

In plain words: A spinning thread burns processor time without doing useful work. Whether that matters depends on how long the wait lasts and on whether the lock holder is running.

Timings of one million lock-protected increments per thread (median of five runs, in seconds, on a machine with 2 processors):

Method 2 threads 4 threads 8 threads
Atomic add (no lock) 0.027 0.060 0.143
Spinlock (test-and-set) 0.042 0.382 1.364
Spinlock, test-and-test-and-set 0.076 0.399 1.52
Spinlock with sched_yield 0.020 0.043 0.082
Mutex (pthread_mutex_t, page 3) 0.109 0.209 0.478
Ticket lock (section 5) 0.38 not finished in 20 s not tested

Notes on the table:

  • With 2 threads on 2 processors, the spinlock is faster than the mutex: the holder is running on the other processor and releases the lock quickly, so the wait is short.
  • With 4 and 8 threads on 2 processors, the plain spinlock gets much slower (1.364 s for 8 threads), and the mutex wins (0.478 s). The reason: a thread that holds the lock can be taken off its processor by the scheduler, in the middle of the critical section. All the spinners then burn their whole time slices (a few milliseconds each, page 3 of Level 3) waiting for a thread that is not running.
  • Test-and-test-and-set reads the lock word with ordinary reads until it looks free, and only then tries the exchange. This keeps the cache line shared among the spinners, so it should reduce traffic between processors. On this small machine it gave no gain.
  • A spinlock that calls sched_yield after a failed try gives its processor away, so the holder can run. It was the fastest lock here. The critical section is tiny, so the effect is large. In general, yielding has its own unpredictable costs.
  • Run-to-run spread was large: the same test varied by a factor of two (for instance, the 2-thread mutex ran from 0.069 to 0.157 s). A single timing proves little.

Spinning is a good choice only when waits are shorter than a context switch (about a microsecond, Level 1) and the holder cannot be preempted. Inside the kernel, spinlocks are used with interrupts disabled, so the holder is not interrupted. In ordinary programs, a lock that puts a waiting thread to sleep is better (page 3).

Busy waiting

Busy waiting is waiting for a condition by repeatedly testing it in a loop, so that the waiting thread keeps using a processor instead of giving it up.

Example: a spinlock waiter that loops on the exchange while the holder is descheduled burns whole time slices without progress.

Check yourself: 1. Why is the spinlock faster than the mutex on 2 threads but slower on 8? 2. What does test-and-test-and-set change? 3. In what place are spinlocks the right tool?