Skip to main content

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

Lock-based Concurrent Data Structures

Locks make a structure thread-safe. How you place them decides correctness and scalability.

Crux: where to put locks so the structure is correct and many threads can proceed concurrently when it matters?

Concurrent counters​

Simple pattern: one mutex around every method (monitor-style [BH73]). Correct — and often enough.

Problem: a hot shared counter does not scale. Four threads each doing 1M increments can be orders of magnitude slower than one thread (Fig 29.3). Ideal is perfect scaling: more CPUs finish more work in about the same wall time.

Approximate (sloppy) counters​

One logical counter ≈ many local counters (per CPU) + one global:

  1. Increment under the local lock (no cross-CPU contention).
  2. When local ≥ threshold S, add local into global under glock, reset local.
  3. get() returns global — approximate (lag ≤ #CPUs × S unless you lock everything).

Small S → accurate, slow. Large S → scalable, looser. Fig 29.4/29.6 show the trade-off. Linux has cared about this for real multicore scaling [B+10][C06].

Quiz

Rank the sequence

1 / 1

Order the steps of a sloppy (approximate) counter increment that triggers a transfer to the global counter.

OrderDrag the handle to rearrange — top should be first.

  1. 1Acquire the local (per-CPU) lock and increment the local counter
  2. 2Acquire glock, add local into the global counter, and reset local to 0
  3. 3Release the local lock
  4. 4Check whether local has reached the threshold S

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

Concurrent linked lists​

Start with one list lock for insert/lookup/delete.

Control-flow tip: don’t lock, then malloc fail, then unlock on every exit path — error-prone (~40% of some kernel bugs sit on rare paths [L+13]). Better:

  • Allocate outside the lock (if malloc is thread-safe).
  • Hold the lock only to splice.
  • Lookup: single unlock on a common return path (Fig 29.8).

Hand-over-hand (lock coupling)​

Lock per node; grab next, release current while walking. Sounds concurrent; in practice lock traffic often beats a single big lock. Measure before adopting.

More concurrency ≠ faster

Extra lock acquire/release can dominate. Build simple first; compare.

Concurrent queues​

Michael & Scott [MS98]: headLock + tailLock + a dummy node so enqueue (tail) and dequeue (head) rarely contend. Common multi-threaded building block; waiting when empty/full needs condition variables (next chapter).

Concurrent hash tables​

Non-resizing table: BUCKETS concurrent lists → lock per bucket. Operations on different buckets run in parallel. Fig 29.11: hash scales; single-lock list does not.

Avoid premature optimization (Knuth)

Start with one big lock. Refine only when measurement says you must. Linux’s BKL, then many locks; Solaris designed concurrency in from the start.

Interactive​

Try: precise vs approximate counters · list lock tips · MS queue · per-bucket hash.

Check your understanding​

Quiz

Lock-based concurrent structures

1 / 6

A single mutex around every counter method is…

Pick an answer to see if you are right.

Coding challenges​

Homework lab: measure concurrent structures​

OSTEP’s Ch. 29 homework is code + timing on a real machine (gettimeofday / rdtsc), not the x86.py simulator.

Lab

Homework: concurrent counters and lists

0/5 started

Loading lab…

Summary​

StructureSimple approachScaling idea
CounterOne mutexApproximate / sloppy locals + S
ListOne mutexCareful CS; HOH rarely faster
QueueOne mutexMS: head/tail locks + dummy
HashOne mutexLock per bucket (lists)

Previous: Locks

Next: Condition Variables — waiting, Mesa semantics, producer/consumer.

Further Reading​