Skip to main content

Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 28, Arpaci-Dusseau & Arpaci-Dusseau

Locks

Concurrency needs atomic critical sections, but interrupts and multiprocessors break naive sequences. A lock (mutex) lets programmers wrap a CS so it executes as if it were one atomic instruction.

lock_t mutex;
lock(&mutex);
balance = balance + 1;   // critical section
unlock(&mutex);

The lock variable is free or held (exactly one owner). lock() acquires or waits; unlock() frees (or wakes a waiter). Locks give programmers a slice of scheduling control: at most one thread in that CS.

pthread mutex​

POSIX: pthread_mutex_lock / unlock. Different locks for different data → fine-grained concurrency vs one coarse global lock.

Evaluating locks​

AxisQuestion
CorrectnessMutual exclusion?
FairnessCan a waiter starve?
PerformanceCost with no contention; with contention on 1 CPU; on many CPUs

Crux: build an efficient lock — what hardware? what OS?

Controlling interrupts​

Early uniprocessor trick: disable interrupts in the CS. Simple, but:

  • Trusts user code with a privileged op (greedy / infinite loop = hang)
  • Fails on multiprocessors
  • Long mask → lost interrupts
  • Slow on modern CPUs

Still used inside the OS for short kernel critical sections.

Failed attempt: plain flag​

Spin while flag==1, then flag=1. Broken: test and set are not atomic — both threads can pass the test (Fig 28.2). Also spin-waiting wastes CPU (especially on one core while the holder is descheduled).

Malicious scheduler

Assume interrupts at the worst moment. If a bad schedule is possible, the design is wrong.

Dekker / Peterson show locks with only loads/stores (theory interest); modern relaxed memory makes them impractical vs hardware atomics.

Test-and-set spin locks​

Atomic TestAndSet(ptr, new): return old value, store new, indivisibly.

while (TestAndSet(&lock->flag, 1) == 1)
    ; // spin
// unlock: flag = 0

Correct ME. Not fair (possible starvation). Spin cost: painful if holder preempted on 1 CPU; OK on multi-CPU if CS is short. Needs preemption on a uniprocessor or the spinner never yields.

Compare-and-swap​

CompareAndSwap(ptr, expected, new): if *ptr==expected, store new; return actual. Spin lock: wait until CAS from 0→1 succeeds. More powerful than TAS (later: lock-free structures).

Load-linked / store-conditional​

LL loads; SC stores only if no intervening write to that address. Lock: spin until LL sees 0, then SC(1); retry on SC fail. Only one of two racing SC succeeds.

Fetch-and-add: ticket lock​

Atomic FetchAndAdd returns old and increments. Ticket lock [MS91]: myturn = FetchAndAdd(&ticket); spin until turn == myturn; unlock does turn++. Fair progress once you hold a ticket — unlike plain TAS.

Quiz

Rank the sequence

1 / 1

Order the steps a thread performs to acquire and release a ticket lock.

OrderDrag the handle to rearrange — top should be first.

  1. 1Enter the critical section
  2. 2Call FetchAndAdd on ticket to get myturn
  3. 3Increment turn (unlock)
  4. 4Spin while turn != myturn

Drag items into the correct order (or use ↑↓), then check.

Too much spinning → yield, then sleep​

On one CPU, spinning for a preempted holder wastes whole timeslices.

  1. Yield while lock held — better than pure spin, still thrashing with many waiters; starvation remains.
  2. Queue + park/unpark (Solaris-style, Fig 28.9): short guard spin-lock around flag/queue; failed acquire → enqueue, release guard, park. Unlock unparks next (often pass the lock without clearing flag). Use setpark() to avoid the wakeup/waiting race.
  3. Linux futex: wait/wake on an address; fast path when uncontended; waiter count packed with lock bit.
  4. Two-phase locks: spin briefly, then sleep (hybrid).
Quiz

Rank the sequence

1 / 1

Order a thread's steps when it fails to acquire a queue + park/unpark lock (Fig 28.9).

OrderDrag the handle to rearrange — top should be first.

  1. 1Park (go to sleep)
  2. 2Release the guard spin-lock
  3. 3Acquire the guard spin-lock and find the flag held
  4. 4Add itself to the waiting queue

Drag items into the correct order (or use ↑↓), then check.

Priority inversion

High-priority spinner blocked on low-priority holder → hang (Pathfinder). Mitigations: avoid long spins, priority inheritance, or equal priorities.

Interactive​

Try: lock API · broken flag · TAS · ticket · park/queue.

Check your understanding​

Quiz

Locks

1 / 6

A mutex’s main job is to…

Pick an answer to see if you are right.

Coding challenges​

Homework lab: x86.py locks​

Use the OSTEP locks homework (flag.s, test-and-set.s, peterson.s, ticket.s, yield.s, …).

Lab

Homework: x86.py locks

0/5 started

Loading lab…

Summary​

ApproachME?Fair?Notes
Interrupt disableUni yes—Not for apps / MP
Plain flagNo—Race on test/set
TAS / CAS spinYesPoorOK if CS short + multi-CPU
Ticket (FAA)YesBetterOrdered tickets
Yield while heldYesPoorLess spin, still waste
Queue + park/futexYesControllableReal libraries; two-phase hybrid

Previous: Concurrency — An Introduction

Next: Lock-based Concurrent Data Structures — counters, lists, queues, hash tables.

Further Reading​