Chapter 11: Lock Implementation and Dynamic Memory

Vol 3: Computer Core Expedition · Chapter 11

---

Metadata Card

Attribute	Value
Keywords	Spinlock, Futex, malloc, free, Memory Allocator

---

Your Progress

"Behind every mutex_lock() and every malloc() lies a complex dance between CPU instructions, kernel intervention, and memory management."

---

Encounter 1: Spinlock

void spinlock_lock(volatile int *lock) {
    while (__sync_lock_test_and_set(lock, 1)) {
        // spin (busy-wait)
    }
}

void spinlock_unlock(volatile int *lock) {
    __sync_lock_release(lock);
}

Good for: Short critical sections, no contention. Bad for: Long wait times (wastes CPU cycles).

Encounter 2: Futex (Fast Userspace Mutex)

A hybrid: spin in userspace first, then fall back to kernel sleeping.

Encounter 3: malloc and free

• malloc(N): Finds a free block ≥ N bytes, returns pointer
• free(p): Returns the block to the free list

Internal structures:

• Free list: Linked list of free memory blocks
• Buddy system: Split/merge power-of-2 blocks
• Slab allocator: Object caching for kernel

---

Verification Checklist

• [ ] Can explain how spinlocks work and when to use them
• [ ] Can describe the basic operation of malloc/free
• [ ] Can explain why futex is more efficient than pure spinlock

---

→ Next Stop Preview

Chapter 12: Deadlock