CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 6 of 7 · 4 min read

Ticket lock

Fairness and the ticket lock

In plain words: A deli counter gives each customer a numbered ticket and displays "now serving". Customers are served in the order of the tickets, so nobody is overtaken. The analogy stops in one place: a customer who has left the shop is skipped at the deli, but a thread whose turn has come cannot be skipped.

The ticket lock repairs the missing bounded waiting. It uses two counters: next (the next ticket to hand out) and serving (the ticket that may enter). A thread takes a ticket with fetch-and-add, and spins until serving equals its ticket. On leaving, it adds one to serving.

static unsigned next_ticket, now_serving;

void ticket_lock(void) {
    unsigned my = __atomic_fetch_add(&next_ticket, 1, __ATOMIC_ACQUIRE);
    while (__atomic_load_n(&now_serving, __ATOMIC_ACQUIRE) != my)
        ;
}
void ticket_unlock(void) { __atomic_fetch_add(&now_serving, 1, __ATOMIC_RELEASE); }

Threads enter in strict order of arrival: bounded waiting is satisfied, and the number of threads that pass a waiting thread is at most the number ahead of it. Older Linux kernels used ticket locks for their spinlocks, and current ones use a queue-based variant of the same idea.

The test shows the weakness. With 2 threads on 2 processors the ticket lock completed in 0.38 s. With 3 or 4 threads on 2 processors, the runs did not finish within 20 seconds, and were stopped. Strict order means that the next lock owner is a specific thread. If that thread is not running (it was descheduled), every other thread waits for it, spinning, until the scheduler runs it again. With a plain spinlock, any running spinner could take the lock, and the lock was not stuck. The lesson: the stricter the order, the worse the effect of a descheduled thread. Fair spinlocks suit cases where threads cannot be preempted. In user space, a sleeping lock is safer (page 3).

Ticket lock

A ticket lock is a spinlock in which each arriving thread takes the next number with an atomic fetch-and-add and enters when the "now serving" counter equals its number, so that threads enter in the order they arrived.

Example: a thread that takes ticket 7 waits until now_serving is 7, and then adds 1 to it on leaving.

Common mistake

Writing a spinlock with an ordinary read and write (while (locked) ; locked = 1;). This is the lock variable of page 1 and loses mutual exclusion. The check and the claim must be one atomic operation.

Interview angle

Answer in your head first, then open it.

What is an atomic operation, and why does locking need one?

An indivisible step in hardware. A lock needs to test and claim in one step.

How does test-and-set build a lock?

Exchange 1 into the lock word. If the old value was 0, the lock is taken.

What is compare-and-swap used for?

To update a value only if it is unchanged, in a retry loop, without a lock.

When is a spinlock the right choice?

Short critical sections, holder cannot be preempted, as in kernels.

What goes wrong with a spinlock on one processor?

The spinner burns its slice while the holder, which is not running, cannot release.

Check yourself: 1. What are the two counters of a ticket lock? 2. Why did the ticket lock fail to finish with 3 threads on 2 processors? 3. Which requirement does the ticket lock add to the plain spinlock?

Words you will meet

Word Meaning
Atomic operation One indivisible step on memory
Fetch-and-add Add to a variable and return the old value
Test-and-set Store a value and return the old one
Compare-and-swap Store a new value only if the old one is as expected
Spinlock A lock that waits by looping
Busy waiting Waiting by testing in a loop
Lock-free Updates by retry, with no thread holding a lock
ABA problem A value changes and changes back, hiding the change
Ticket lock A spinlock that serves threads in order of arrival
Acquire and release Ordering guarantees that keep work inside the lock

Quick notes

  • An atomic operation is an operation on memory that the hardware carries out as one indivisible step, so that no other processor or thread can observe it half finished or change the data in its middle.
  • A spinlock is a lock in which a thread that finds the lock held repeatedly tests it in a tight loop, using processor time, until the lock becomes free, and.
  • Compare-and-swap is an atomic instruction that takes an address, an expected value and a new value, and stores the new value only if the memory still holds the expected value, reporting whether it did.
  • 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.
  • A ticket lock is a spinlock in which each arriving thread takes the next number with an atomic fetch-and-add and enters when the "now serving" counter equals its number, so that threads enter in the order they arrived.