CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 3 of 7 · 2 min read

Sleeping

In plain words: A customer who finds the shop busy can stand at the counter and stare, or take a ticket and sit down. The one who sits down costs nothing until called. The analogy stops in one place: the shop needs a clerk to call people, and the sleeping thread needs the unlocking thread to wake it.

A lock is contended when a thread tries to take it while another thread holds it. A mutex handles contention by putting the waiting thread to sleep. The kernel removes it from the processor and places it in a waiting state (Level 1, page 2). The unlocking thread asks the kernel to wake it. While it sleeps, the waiter uses no processor time, and the processor can run other threads, perhaps the holder.

A test compares the two. Thread H takes a lock and holds it for 300 ms (it sleeps inside). Thread W tries to lock 20 ms later, and its own CPU time is measured:

mutex   : the waiting thread used 0 ms of CPU while waiting about 280 ms
spinlock: the waiting thread used 261 ms of CPU while waiting about 280 ms

The spinning waiter used nearly all of the 280 ms in processor time, and the sleeping waiter used none. On a machine with fewer processors than threads, the spinner would also take processor time away from the holder, making the wait longer. This is why page 2 recommended spinlocks only for very short critical sections.

Sleeping has a cost too. Putting a thread to sleep and waking it involves system calls and a context switch, together a few microseconds (Level 1, page 5). If the lock is held for less time than this, spinning would have been cheaper. A good mutex implementation spins briefly first and sleeps only if the lock stays held. The glibc mutex has an adaptive variant for this.

Lock contention

Lock contention is the situation in which a thread tries to acquire a lock that another thread currently holds, so that it must wait; a lock with frequent contention is a bottleneck.

Example: four threads that all lock one mutex a million times each cause contention on most acquisitions, and the program is limited by how fast the lock is passed around.

Check yourself: 1. How much CPU did the sleeping waiter use in the test? 2. Why is the sleeping lock slower than a spinlock for a very short wait? 3. What does a contended lock mean?