Prep: Spinlocks and Semaphores — 37k · 38k¶

Session: Thu Oct 29, 1h45 · Exercises: 37k_spinlocks, 38k_semaphores · Prep time: ~30 min · Lecture: Week 10 · Locks, Semaphores, and Turning the MMU On

What you will build¶

Two layers of synchronization, bottom up. First a spinlock: an AtomicBool beside an UnsafeCell<T>, claimed by compare-and-exchange, whose only path to the data is a guard that unlocks itself in Drop. Second, a counting semaphore built on that lock, non-blocking since nobody can be woken yet, and with it the kernel's first heap: a page-per-allocation #[global_allocator] that makes Box, Vec, and Arc usable, so two owners can share one semaphore.

Concepts you need¶

A race lives in the interleaving; more code cannot close the window — Week 10 · A race, built by hand · Key Concepts: race condition
Compare-and-exchange vs. test-and-set; Acquire on take, Release on release — Week 10 · One indivisible step, Test-and-set versus CAS · Key Concepts: atomicity
UnsafeCell, interior mutability, and the RAII guard — Week 10 · Shared, yet mutable: UnsafeCell, Send and Sync, The guard unlocks for you · Rust for Systems: The guard pattern
Send, Sync, and what unsafe impl Sync promises — Week 10 · Shared, yet mutable: UnsafeCell, Send and Sync · Unsafe guide: Send and Sync
Counting semaphores: permits, P and V, the lost wakeup — Week 10 · Permits: P and V, The lost wakeup · Key Concepts: semaphore
The heap arrives: GlobalAlloc, one page per allocation, Arc — Week 10 · The heap arrives, Arc: one value, many owners · Key Concepts: heap

Read before class¶

What	Time
Week 10 · This week, then Thursday · `37k` Spinlocks through One indivisible step	4 min
Week 10 · Shared, yet mutable: `UnsafeCell`, `Send` and `Sync`, The guard unlocks for you and Interrupts off while you hold it	4 min
Week 10 · Thursday · `38k` Semaphores and the heap, all three sections	4 min
Week 10 · For the exam: Test-and-set versus CAS, Deadlock, The lost wakeup and Bounded buffers. Not needed today; on Midterm 2	2 min
Unsafe guide: `UnsafeCell` and `Send` and `Sync`	3 min
Key Concepts guide: Concurrency, then heap	4 min

Mental model¶

Two harts decrement a ticket count under one spinlock:

 time  hart A                                hart B                            locked  tickets
   1   CAS false->true  -> Ok                .                                 true    3
   2   ld 3; addi -1; sd 2                   CAS false->true  -> Err(true)     true    2
   3   guard dropped: fence rw,w; sb false   pause; CAS false->true -> Ok      true    2
   4   .                                     ld 2; addi -1; sd 1               true    1
   5   .                                     guard dropped                     false   1

Only one CAS can win the false → true transition, so B's read-modify-write cannot slide between A's load and store. A's Release at drop and B's Acquire on its winning CAS are why B loads 2, not a stale 3: the pair protects the data, not merely the flag. A counting semaphore is this picture plus one rule: the count never goes below zero, and a caller who finds zero is refused, not put to sleep, since on one hart nobody else would run to return the permit.

Check yourself¶

if !busy { busy = true; } guards a critical section on rv6's single hart, interrupts enabled. Why can it still fail?
Answer
It is a load, a branch, and a store; an interrupt between load and store runs a handler that also reads false and enters. Only an operation with no interior, one amoor.w.aq, closes the window.
A struct holds an UnsafeCell<T>. Why does the compiler reject static X: ThatStruct, and what does unsafe impl<T: Send> Sync for ThatStruct claim?
Answer
A static must be Sync; UnsafeCell is deliberately !Sync, so the struct is too. The unsafe impl is the author's promise that the lock serializes every access.
After let b = Arc::clone(&a);, how many copies of the value exist, and how can either mutate it?
Answer
One. Arc::clone copies a pointer and atomically bumps the strong count. Arc<T> yields only &T, so mutation needs interior mutability inside T: a lock.

What "done" looks like¶

oslings run is green, then oslings submit before you leave. Not green? Submit anyway — the tests that pass earn their share — then finish it at a make-up session (office hours, on the class network) for three quarters, or anywhere else for half, and submit again.

If you finish early¶

Work Week 10 · Problem 2: When does the guard drop? and Problem 3: A bounded buffer of two on paper and read Week 10 · Deadlock on single-hart deadlock (Midterm 2 material), then chapter 6, "Locking," of the xv6 book, or start Friday's Prep: Virtual Memory.