Writing an OS Kernel from Scratch | Synchronization Primitives — spinlock and semaphore, How the OS Coordinates Concurrent Access
Two processes write data to the same file simultaneously — process A writes the first 100 bytes, process B writes the next 100 bytes. If no coordination is done, what happens?
Process A just read the “current write position” but hasn’t written yet, and process B also reads the same position — both processes think they should write there. The result is interleaved data and file corruption. This is a Race Condition — when concurrently accessing shared resources, the uncertainty of execution order leads to incorrect results.
Synchronization Primitives are used to solve this problem: make concurrent access serial and ordered. Today, let’s understand how spinlock and semaphore are implemented.
1. Race Condition: The Essence of the Problem
Race Condition Example:
Process A and process B share variable `counter = 0`, both want to execute counter++
Correct execution order (A and B each execute once):
counter = 0
A: read counter → 0
A: counter++ → 1
A: write counter → 1
B: read counter → 1
B: counter++ → 2
B: write counter → 2
Final counter = 2 ✓
But if execution order is interleaved:
A: read counter → 0
B: read counter → 0 ← B reads before A writes
A: counter++ → 1
A: write counter → 1
B: counter++ → 1 ← B added based on old value 0
B: write counter → 1
Final counter = 1 ✗ ← Wrong! Both processes incremented once, but result is only 1Where's the problem? read-modify-write is not atomic. To solve this, we must ensure only one process can execute this code at a time — this is Mutual Exclusion.
2. spinlock: Busy-Waiting Mutex
spinlock is the simplest mutual exclusion primitive — if the lock is held, the CPU spins (while loop) until it acquires the lock.
spinlock principle:
struct spinlock {
int locked; // 0=unlocked, 1=locked
}
void lock(struct spinlock *lock) {
// If the lock is held, spin and wait
while (atomic_test_and_set(&lock->locked, 1) == 1) {
// Empty loop, constantly checking if the lock is released
// CPU cannot do anything else during this time (busy wait)
}
// Got it! locked = 1, exit loop
}
void unlock(struct spinlock *lock) {
// Release the lock
atomic_clear(&lock->locked, 0);
}2.1 atomic_test_and_set: Hardware-Guaranteed Atomicity
Why can’t a simple while (x == 1) check guarantee atomicity? Because another CPU could interrupt between the check and the set.
atomic_test_and_set is a CPU instruction-level atomic operation:
# x86 lock instruction prefix (makes the next instruction atomic)
lock xchg %eax, (lock_addr) # Atomic exchange, returns old value
# In C corresponds to:
bool test_and_set(int *ptr) {
bool old = *ptr;
*ptr = 1;
return old;
}The lock prefix makes the CPU lock the bus (or use cache coherency mechanism) when executing xchg, ensuring this operation cannot be interrupted by another CPU — that’s where atomicity comes from.
2.2 The Problem with spinlock: Cache Line Thrashing on Multi-Core
spinlock performance issue on multi-core CPUs:
CPU0 and CPU1 share the same cache line for the lock variable:
CPU0: while(atomic_xchg(&lock, 1) == 1) // tries to acquire lock
|--- wait ---|
|--- wait ---|
|--- wait ---|
MESI protocol: lock variable bounces between CPU0's and CPU1's caches
CPU1: atomic_xchg(&lock, 0) // releases lock
→ lock line becomes Modified
→ CPU0's copy is Invalidated
→ CPU0: cache miss → re-read from memory
→ CPU0 finally gets the lock
But:
- If the critical section is very short, this thrashing is acceptable
- If there are many CPUs, the lock variable bouncing becomes severe2.3 When to Use spinlock
Recommended scenarios for spinlock:
✓ Critical section is very short (just a few instructions)
✓ No blocking operations (cannot sleep!)
✓ Interrupt handler / bottom half context
✓ Multi-core synchronization
Not suitable for spinlock:
✗ Long critical section → wasteful CPU spinning
✗ Operations that may sleep → will sleep with the lock held → deadlock
✗ Single-core preemptible kernel → use preempt_disable instead3. Semaphore: Sleepable Lock
Unlike spinlock’s busy waiting, a semaphore puts the process to sleep when it cannot acquire the lock, freeing the CPU for other tasks.
Semaphore principle:
struct semaphore {
int count; // Available resources count
wait_queue_t wait; // Wait queue (sleeping processes)
}
void down(struct semaphore *sem) {
// Acquire: decrement count, if negative → sleep
atomic_dec(&sem->count);
if (sem->count < 0) {
// Put current process to sleep (add to wait queue)
// Scheduler picks another process to run
sleep_on(&sem->wait);
}
}
void up(struct semaphore *sem) {
// Release: increment count, if negative → wake up one sleeper
atomic_inc(&sem->count);
if (sem->count <= 0) {
// Wake up a process waiting on this semaphore
wake_up(&sem->wait);
}
}3.1 Binary Semaphore vs Counting Semaphore
Semaphore Type:
Binary semaphore (count = 1):
count = 1: lock is free
count = 0: lock is held
count = -1: one process waiting
→ Essentially equivalent to a mutex
Counting semaphore (count = N, N > 1):
count = N: N resources available
count = 0: all resources used
count = -k: k processes waiting
→ Used to manage multiple identical resources (e.g., 5 available database connections)3.2 Mutex vs Binary Semaphore
Differences:
Mutex Binary Semaphore
Owner tracking Yes (who locked No
who unlocks)
Reentrancy Reentrant mutex Typically not
supported
Priority Priority No
inheritance inheritance
Sleep behavior Userspace Can be used in kernel
futex-based interrupt context
lightweight
In Linux: mutex is preferred for most cases; semaphore is mainly used in kernel4. Spinlock vs Semaphore Comparison
Comparison Table:
Property Spinlock Semaphore
Waiting method Busy wait (spins) Sleep (context switch)
CPU usage 100% (wastes) 0% (sleeping)
Critical Very short Long
section
Can sleep No Can be held during sleep
Interrupt Can be used Cannot be used (may sleep)
handler
Multi-core Fits perfectly Fits, but higher overhead
Kernel cost Low (no scheduling) High (scheduling needed)
Implementation atomic_test_and_set Wait queue + schedule()5. Advanced: Lock-Free Data Structures
In some demanding scenarios, locks themselves become performance bottlenecks. Lock-free data structures use atomic operations and memory barriers to achieve concurrency.
Simple Lock-Free Stack:
struct node {
int value;
node *next;
};
node *top = NULL;
void push(int value) {
node *n = new node(value);
do {
n->next = top; // Step 1: set next to current top
} while (!CAS(&top, n->next, n)); // Step 2: atomically update top
}
// CAS = Compare-And-Swap
// If top == n->next, set top = n, return true
// If top != n->next (another thread modified top), retryABA problem hazard: the pointer “looks the same” but points to a different object. Hardware solutions include LL/SC or tagged pointers.
6. Summary
- Race conditions arise from non-atomic read-modify-write operations
- spinlock = busy waiting for locks, suitable for very short critical sections
- Semaphore/Mutex = sleep-based waiting, suitable for long critical sections
- Atomic operations rely on hardware instructions (lock prefix, CAS)
- Lock-free data structures use atomic operations directly but must handle the ABA problem
- Choose wisely: spinlock for short paths, semaphore for long paths
Next up: Memory management — how does the kernel allocate and manage physical memory?
Comments