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

Bash
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 1

Where'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.

Bash
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:

Asm
# 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

Bash
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 severe

2.3 When to Use spinlock

Bash
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 instead

3. 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.

Bash
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

Bash
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

Bash
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 kernel

4. Spinlock vs Semaphore Comparison

Bash
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.

Bash
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), retry

ABA problem hazard: the pointer “looks the same” but points to a different object. Hardware solutions include LL/SC or tagged pointers.

6. Summary

  1. Race conditions arise from non-atomic read-modify-write operations
  2. spinlock = busy waiting for locks, suitable for very short critical sections
  3. Semaphore/Mutex = sleep-based waiting, suitable for long critical sections
  4. Atomic operations rely on hardware instructions (lock prefix, CAS)
  5. Lock-free data structures use atomic operations directly but must handle the ABA problem
  6. Choose wisely: spinlock for short paths, semaphore for long paths

Next up: Memory management — how does the kernel allocate and manage physical memory?

OS #KernelDevelopment #Synchronization #Spinlock #Semaphore #Mutex #LockFree #WritingFromScratch

Last modified: 2024年2月4日

Author

Comments

Write a Reply or Comment

Your email address will not be published.