Synchronization 2: Semaphores, Lock Implementation, Atomic Instructions

Source: UC Berkeley CS162, Fall 2020/2021 - Prof. John Kubiatowicz, Lecture 7

CS162 Lecture 7 - Synchronization 2: Semaphores, Lock Implementation, Atomic Instructions

The last lecture ended with the idea of a lock - acquire before a critical section, release after - but a lock hanging in space is not an implementation. This lecture makes it concrete. It first introduces the semaphore, the more powerful primitive that solves the producer-consumer problem cleanly, then spends its second half answering the question that was left open: how do you actually build acquire and release? The answer walks up from raw loads and stores, through disabling interrupts, and points at the hardware atomic instructions that come next.

Finishing the picture: entering the kernel on the x86

Before the new material, one detail from the context switch. On the x86 (the processor Pintos runs on), the hardware does part of the user-to-kernel transition for you. The machine keeps a task state segment (TSS) - most operating systems, Pintos and Linux included, keep exactly one - and its important field is the privilege-level-0 stack pointer. When a system call or interrupt takes you from user (level 3) to kernel (level 0), the processor automatically switches to that kernel stack and pushes the old CS:EIP (program counter) and SS:ESP (user stack pointer) onto it. The kernel entry code then saves the remaining user registers itself before it starts clobbering them.

A trap saves the user's CS:EIP and SS:ESP onto the kernel stack (hardware) and the rest of the registers below them (software). For a plain syscall the page-table base register (PTBR) is unchanged; a full thread switch swaps the PTBR and returns via iret into a different process.

If the trap is only a system call or an interrupt that does not change process, the page-table base register (PTBR) stays put and iret returns to the same user code. If instead the scheduler decides to switch threads, it swaps the PTBR for the new process's address space, restores that thread's saved registers, and iret lands in a completely different process. The two cases share the same entry and exit machinery.

⚠

A timer interrupt never interrupts a timer interrupt

As soon as an interrupt is taken, the controller disables interrupts, and the kernel keeps the timer disabled until it is safe again - so you never get a recursive timer interrupt corrupting the saved registers. A higher-priority interrupt may still be allowed through, but not the timer. And disabling an interrupt does not lose it: a pending interrupt is merely deferred until you re-enable, then it fires. You cannot "miss" the timer by having interrupts off.

The producer-consumer (bounded buffer) problem

Now the hardest problem of the class. A bounded buffer is a finite queue shared between multiple producers, which put items in, and multiple consumers, which take them out. Think of a Coke machine: the delivery driver (producer) loads bottles into a fixed number of slots, and students (consumers) pull them out. Producers and consumers arrive at any time, fully asynchronously - we do not want them running in lock step.

Many producers, many consumers, one finite buffer. Pipes in a shell (cat | grep | wc), web-server request queues and routers are all bounded buffers.

Two different things must be coordinated, and they are not the same kind of constraint:

• Mutual exclusion on the buffer itself, so concurrent enqueues and dequeues do not corrupt the queue. This is the lock-style constraint from Lecture 1.
• Blocking when the buffer is in the wrong state: a producer that arrives at a full machine must be put to sleep until a slot frees, and a consumer that arrives at an empty machine must sleep until a bottle appears.

Shaking the machine until the driver shows up - spinning while you wait - is the bad-programming-style version. We want to actually sleep.

The circular buffer underneath

The queue itself is an ordinary circular buffer: a fixed array plus a read index and a write index that wrap around.

A ring buffer with a write pointer and a read pointer. The real questions are: how do you tell full from empty, what do you do when it is, and which parts of insert/remove must be atomic?

typedef struct buf {

int write_index;

int read_index;

<type> *entries[BUFSIZE];

} buf_t;

Insert bumps the write pointer (enqueue); remove bumps the read pointer (dequeue). If two threads bump the same pointer at once, or a reader overtakes a writer, the queue is corrupted - so the pointer updates are exactly what needs to be atomic.

Why a lock alone is not enough

The obvious first attempt wraps the whole thing in one lock and spins while the buffer is in the wrong state. It deadlocks:

Producer(item) {

acquire(&buf_lock);

while (buffer full) { /* spin */ } // holds the lock while spinning!

enqueue(item);

release(&buf_lock);

}

The producer grabs the lock, finds the buffer full, and spins waiting for a slot to open - but the only thread that can open a slot is a consumer, and the consumer can never get the lock the producer is holding. Unresolvable.

The second attempt fixes the deadlock by releasing and re-acquiring the lock each time around the loop:

The second cut releases and re-acquires the lock each spin, so it no longer deadlocks - but a producer facing a full buffer with no consumers just loops unlock/lock/unlock/lock forever, burning cycles. This is busy waiting.

Producer(item) {

acquire(&buf_lock);

while (buffer full) { release(&buf_lock); acquire(&buf_lock); }

enqueue(item);

release(&buf_lock);

}

⚠

Busy waiting is a way to lose points

The second cut works, but a producer at a full machine with no consumers around spins unlock/lock/unlock/lock forever, wasting the processor doing nothing. Polling does not help either: the producer has nothing else to do but produce. Every synchronization problem is solved by waiting; the whole skill is to wait without stealing cycles - to sleep and let another thread run. A lock is not a rich enough abstraction to express "wait until there is space", so we need a better primitive.

Semaphores

Semaphores were defined by Dijkstra in the late 1960s and were the main synchronization primitive in the original Unix. A semaphore is a non-negative integer with exactly two atomic operations:

P(sem): wait until sem > 0, then decrement sem // "down", "wait"

V(sem): increment sem, waking one waiter if any // "up", "signal"

P and V come from Dijkstra's Dutch: P from proberen (to test), V from verhogen (to increment). The names down/up and wait/signal are the same operations. The behavior is defined entirely by two guarantees:

• The value can never go below zero. If a thread runs P on a zero semaphore, it waits - and crucially this is a good wait, the sleep-and-yield kind, not a spin.
• A V that takes the value from 0 to 1 while someone is blocked on P will wake exactly one waiter (waking all of them is fine too, since only one can win the decrement back to zero).

≡

The semaphore contract

• Whole numbers only - a semaphore is like an integer except it can never be negative.
• Only P and V - those are the only operations. You set the initial value, but after that you cannot read or write the value directly. (POSIX exposes a read, but it is not really part of the interface - do not depend on it.)
• Atomic - both operations happen indivisibly.
• Non-deterministic wake - when several threads wait on a P, which one a V wakes is unspecified. Never assume FIFO or any particular order unless the spec promises it.
• Synchronization is a contract. If you initialize a mutex to 1 but then bump it higher, it stops behaving like a mutex - you have violated your own spec and broken your own code. The guarantees only hold if you honor them.

A railway analogy captures the counting behavior: set a semaphore to 2 and let each train run P before entering the shared section. The first two trains pass (the value drops 2 to 1 to 0); a third train runs P on zero and waits. When a train leaves and runs V, the value ticks up and the waiting train is released.

Semaphores come in two flavors depending on the initial value:

Kind	Initial value	Behavior	Use
Binary semaphore (mutex)	1	At most one thread past P at a time; V releases it.	Mutual exclusion - identical to a lock.
Counting semaphore	N (any non-negative)	Up to N threads past P at once; tracks a count of available units.	Resource counting and scheduling constraints.

Two uses of a semaphore

The mutual-exclusion use is a binary semaphore initialized to 1: P to enter the critical section, V to leave, exactly like a lock.

The scheduling-constraint use initializes to 0 so the very first P blocks. The classic example is thread join, where a parent waits for a child:

Semaphore done = 0;

 

ThreadJoin() { P(&done); } // parent blocks: P on 0 sleeps

ThreadFinish() { V(&done); } // child signals: V wakes the parent

Bounded buffer, solved

The producer-consumer problem needs three constraints, so the rule of thumb is one semaphore per constraint: how many full slots there are, how many empty slots there are, and a mutex for the queue.

Three semaphores, three jobs: the mutex (red) protects the queue, V(fullSlots) wakes a waiting consumer, V(emptySlots) wakes a waiting producer. The producer and consumer are mirror images of each other.

Semaphore fullSlots = 0; // initially, no coke

Semaphore emptySlots = bufSize; // initially, all slots empty

Semaphore mutex = 1; // no one is using the machine

 

Producer(item) {

P(&emptySlots); // wait until there is space

P(&mutex); // wait until the machine is free

Enqueue(item);

V(&mutex);

V(&fullSlots); // tell consumers there is more coke

}

 

Consumer() {

P(&fullSlots); // wait until there is a coke

P(&mutex); // wait until the machine is free

item = Dequeue();

V(&mutex);

V(&emptySlots); // tell producers there is more room

return item;

}

The middle P(&mutex) ... V(&mutex) is pure mutual exclusion keeping the queue consistent - you could protect a red-black tree there instead of a ring buffer and nothing else would change. The outer emptySlots/fullSlots pair is the blocking constraint: a producer that finds emptySlots at zero sleeps inside P(&emptySlots), and a consumer's later V(&emptySlots) wakes it.

⚠

The order of the P operations matters - the V operations do not

Take the semaphores in the wrong order - grab the mutex before checking emptySlots - and you deadlock: the producer holds the mutex and then sleeps on emptySlots, so no consumer can ever take the mutex to make room. Always acquire the resource-count semaphore first, then the mutex. The order of the two V operations at the end, by contrast, is harmless - it only nudges scheduling.

Building synchronization from the hardware up

So far acquire/release and P/V have floated in space. The rest of the lecture builds them for real, and the plan is a layered stack: user programs sit on a higher-level API (locks, semaphores, monitors, send/receive), which is in turn built on hardware primitives.

The implementation stack. Everything above is built from the hardware primitives below. Building it all out of only atomic load/store is painful (as the milk problem shows), so real hardware provides more.

The starting question is: what can the hardware do to help? Begin with the weakest possible tool - atomic loads and stores - and see how far it gets us.

Too Much Milk: what "atomic" really buys you

The motivating example: you share a fridge with roommates and you must never end up with too much milk. Someone comes home, sees no milk, and goes to buy some.

The failure: A leaves for the store at 3:05, B checks the empty fridge at 3:10 while A is still out, and both buy milk. The shared 'is there milk?' state was read and acted on without coordination.

The correctness properties, written down before coding (think first, code later):

1. Never more than one person buys milk.
2. Someone buys milk if it is needed.

The rules of the game: only atomic loads and stores are available. A load returns all the bits at once and a store writes all the bits at once - nothing stronger.

Solution 1: leave a note

A note is like a lock: leave it before buying, remove it after, do not buy if a note is present.

The single-note solution. It mostly works - but a thread can be switched out after checking milk and note yet before buying, so both threads pass the checks and both buy. Too much milk, but only occasionally.

if (no milk) {

if (no note) {

leave note;

buy milk;

remove note;

}

}

Thread A can run both if checks, then get switched out by the Murphy's Law scheduler before leaving the note; Thread B then runs the same checks, and both buy. The bug is now intermittent, which is strictly worse than a bug that always fires - a failure that happens once a week, at 3am, is the one you can never find. (Setting the note before checking, "solution 1.5", is no better: now the thread sees its own note and nobody ever buys milk.)

Solution 2: a note each

Give each thread its own note (note A, note B) and check for the other's note before buying. Now the failure flips to the opposite disaster:

Thread A Thread B

leave note A; leave note B;

if (no note B) { if (no note A) {

if (no milk) buy milk; if (no milk) buy milk;

} }

remove note A; remove note B;

If both leave their note just before checking, each sees the other's note, each assumes the other will buy, and nobody buys milk. That is a form of starvation.

Solution 3: asymmetric, and it actually works

Make the two threads' code different. Thread A leaves its note and then spins while B's note is present; Thread B leaves its note and buys only if A's note is absent.

Solution 3 works. At X (no note B) it is safe for A to buy; otherwise A waits. At Y (no note A) it is safe for B to buy; otherwise A is either buying or spinning. It even generalizes to N threads via Lamport's Bakery Algorithm.

Thread A Thread B

leave note A; leave note B;

while (note B) { // X if (no note A) { // Y

do nothing; if (no milk) {

} buy milk;

if (no milk) { }

buy milk; }

} remove note B;

remove note A;

The case analysis: at X, if there is no note B, then B has not started (or will notice A's note), so A may safely buy. At Y, if there is no note A, then because B has already left its note, A is either not in this code or is caught in its spin loop until B finishes - so B may safely buy. Either way exactly one buys.

⚠

Solution 3 works but you should never ship it

It is correct, and it even generalizes to N threads (Lamport's 1974 "Bakery Algorithm"). But it is a terrible lock: thread A's code is different from thread B's, so it does not look like a symmetric acquire/release at all, and it grows unmanageable past a few threads. Worse, A waits by spinning - the exact busy-waiting we said not to do. Correct is not the same as good. We need to leave loads and stores behind and get a stronger primitive from the hardware.

Implementing locks

We really want a symmetric acquire/release that works for any number of threads, supports many independent locks (a milk lock, an OJ lock, a yogurt lock), and puts waiters to sleep instead of spinning. What hardware support gets us there?

?How should the hardware help us build a lock?

A single hardware lock/unlock instruction→RejectSleeping requires knowing the OS thread layout and wait queues - that does not belong in hardware. Historically tried (Intel iAPX 432) and abandoned as too complex.

Disable and enable interrupts→Use it to build locks, not as the lockFine on a uniprocessor and only for the kernel, but you cannot hand it to users and it does not scale to multiple cores.

Atomic read-modify-write (test-and-set, compare-and-swap)→The real answerReads and writes a memory word atomically, works at user level and on multiprocessors. This is where the next lecture goes.

Pick this when: you are choosing the primitive that acquire and release will be built on

Why not a hardware lock instruction?

A lock/unlock instruction sounds tempting, but the part that does not fit in hardware is putting a thread to sleep: that needs to know the current operating system, how threads are laid out on the stack, and where to park them. Baking one sleep mechanism into the silicon would tie you to one OS. The historical Intel iAPX 432 actually had hardware lock instructions; you find it only in computer museums.

Disabling interrupts: naive, then useful

On a uniprocessor, if you turn off interrupts the timer cannot fire, so no context switch can steal the CPU mid-critical-section. The naive lock is therefore:

Acquire() { disable interrupts; }

Release() { enable interrupts; }

This is a bad idea. You cannot give it to users (a user Acquire() could while (true) with interrupts off and hang the machine), there is only one lock in the whole system, and a long critical section keeps interrupts off long enough to miss something urgent - the nuclear-reactor alarm going unheard.

The fix is to use interrupt disable/enable to implement acquire/release rather than be them. Keep a value in memory as the lock, and disable interrupts only for the few instructions needed to inspect and change it:

The lock is a memory value; interrupts are disabled only long enough to test-and-maybe-set it or to go to sleep. The user's critical section can then run as long as it likes with interrupts on. The open question: when a thread must sleep, where does it re-enable interrupts?

int value = 0; // 0 = FREE, 1 = BUSY

 

Acquire() {

disable interrupts;

if (value == BUSY) {

put thread on wait queue;

Go to sleep(); // <- re-enable interrupts... where?

} else {

value = BUSY;

}

enable interrupts;

}

 

Release() {

disable interrupts;

if (anyone on wait queue) {

take a thread off the wait queue;

place it on the ready queue; // implicitly hands over the lock

} else {

value = FREE;

}

enable interrupts;

}

The critical section with respect to interrupts is now tiny and internal to the lock, so it is safe even in a real-time system: whoever holds the lock runs with interrupts on and can take as long as they want.

The go-to-sleep puzzle

There is a subtlety in Acquire. You cannot go to sleep with interrupts still disabled - that freezes the machine. But you cannot re-enable them before sleeping either: if you re-enable just before putting yourself on the wait queue, the malicious scheduler can run the other thread's Release (which finds nobody waiting yet) and then you go to sleep on a lock that is already free - a missed wakeup, and you hold a lock that is deadlocked. So interrupts must be re-enabled after you are safely asleep, which seems impossible for the sleeping thread to do itself.

The resolution: the scheduler always runs with interrupts disabled (switch must not be interrupted mid-save). Thread A sleeps with interrupts off; the switch hands control to thread B, and it is B, on the way back out to user level, that re-enables interrupts. The next thread to run does the re-enabling.

⚠

Re-enable interrupts after the sleep, via the next thread

The trick: deep in the scheduler, switch already runs with interrupts disabled (an interrupt mid-register-save would corrupt everything). So a thread goes on the wait queue and calls switch with interrupts off; switch returns into a different thread, and that thread, as it works its way back up to user level, is the one that re-enables interrupts. The thread that went to sleep does not re-enable its own interrupts - the next thread to run does it. That is why "re-enable after sleep" is both required and possible.

Watching it run

Simulating two threads sharing this in-kernel lock ties it together:

The simulation tracks value (0 free / 1 busy), the wait queue, and (for our benefit only) an owner. A acquires: interrupts off, value 0 so set value = 1, interrupts on, and it returns from Acquire holding the lock. B later tries Acquire, finds value = 1, goes on the wait queue and sleeps. A's Release finds B waiting and moves it to the ready queue - handing over the lock.

Two details the simulation makes clear:

• A thread only returns from Acquire once it holds the lock. Sleeping waiters are parked inside Acquire; emerging from it means success.
• On Release, when a waiter exists, the value is never reset to 0. Handing the lock straight to the woken thread means it stays busy (value 1) the whole time. The value only drops to FREE when Release finds nobody waiting. And there is one wait queue per lock - 12,000 locks means 12,000 wait queues - so a Release always knows exactly whom to wake.

This is an in-kernel lock: it relies on disabling interrupts, which users are not allowed to do. To offer it to user threads you wrap acquire/release as system calls.

The cost of going into the kernel

Making every lock operation a system call works, but it is slow. A system call costs roughly 25x a plain function call, and if each acquire/release must cross into the kernel, that crossing bounds your throughput no matter how fast everything else is.

If a lock operation costs X to enter and leave the kernel, throughput is capped at 1/X operations per second - regardless of how many cores you have. Even uncontended, unrelated locks pay the kernel-crossing tax.

#

The kernel-crossing tax

• A system call costs about 25x a function call.
• Using Jeff Dean's rule-of-thumb latencies: if crossing into the kernel and back costs X = 1 millisecond, you get only about 1,000 synchronization operations per second.
• With that model the sustained rate is 1/X, independent of the number of cores - so thousands of threads grabbing thousands of unrelated locks all serialize on the crossing.

We would like the common uncontended case - many threads grabbing and releasing locks that have nothing to do with each other - to run at full speed, never entering the kernel at all.

Next: atomic read-modify-write

That means the lock implementation cannot depend on disabling interrupts, for two reasons now: it needs to run at user level, and disabling interrupts does not even work on a multiprocessor (turning interrupts off on one core says nothing about the others, and cross-core disabling is prohibitively expensive).

The way out is a hardware atomic read-modify-write instruction: one instruction that reads a memory location and writes it back atomically, with the hardware guaranteeing nothing sneaks in between. The canonical example is test-and-set: given an address, it reads the current value and stores a 1, atomically. That single operation is enough to build a simple lock - the starting point for the next lecture, along with swap and compare-and-swap.

Recap

• The x86 TSS switches to the kernel stack and pushes the user's CS:EIP and SS:ESP in hardware on every trap; a plain syscall leaves the PTBR alone, while a thread switch swaps it and irets into another process.
• The bounded buffer needs two kinds of coordination - mutual exclusion on the queue, and blocking when it is full or empty. A lock alone gives either deadlock or busy waiting.
• A semaphore is a non-negative integer with atomic P (down/wait) and V (up/signal). Initialized to 1 it is a mutex; initialized to 0 it is a scheduling constraint like thread join. One semaphore per constraint solves the bounded buffer cleanly - and the order of the P operations matters.
• Too Much Milk shows that with only atomic load/store, correctness is possible (solution 3, Lamport's Bakery) but ugly and still busy-waits. Real synchronization needs stronger hardware.
• Locks can be built by disabling interrupts to protect a memory value, with the subtlety that a sleeping thread's interrupts are re-enabled by the next thread to run. But this is kernel-only, does not work on multiprocessors, and pays a heavy kernel-crossing cost.
• The fix, next lecture, is hardware atomic read-modify-write (test-and-set, swap, compare-and-swap) that runs at user level.