Locks and Synchronization

[!NOTE] This module explores the core principles of Locks and Synchronization, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Solving the Race

To fix the race condition, we need to ensure Mutual Exclusion. We need a “lock” that prevents two threads from entering the Critical Section simultaneously.

But how do we implement a lock? If we just use a boolean flag:

while (locked == true); // Wait
locked = true; // Enter
// Critical Section
locked = false; // Exit

This fails! The check while(locked == true) and the set locked = true are distinct operations. Two threads can both see locked == false and enter together.

2. Hardware Primitives: The Secret Sauce

We cannot build a lock using just software (on modern CPUs). We need help from the hardware. The CPU provides Atomic Instructions that perform a Read-Modify-Write in a single, indivisible step.

1. Test-and-Set (TAS)

Atomically writes 1 (true) to a memory location and returns its old value.

boolean TestAndSet(boolean *lock) {
    boolean old = *lock;
    *lock = true;
    return old;
}

2. Compare-and-Swap (CAS)

The basis of all modern synchronization (including Java’s AtomicInteger). Atomically checks if a value matches expected, and if so, updates it to new.

boolean CAS(int *ptr, int expected, int new) {
    if (*ptr == expected) {
        *ptr = new;
        return true;
    }
    return false;
}

---

3. Interactive: CAS Visualizer

Understand the atomic nature of Compare-And-Swap. Try to update the value from 0 to 1. Then try to update it again assuming it’s still 0 (which will fail).

Memory Address 0x1A

Current Value

0

CAS(Expected, New)

→

Ready...

---

4. Spinlocks vs Mutexes

Once we have atomic instructions, we can build locks.

1. The Spinlock (Busy Waiting)

The thread runs a loop checking the lock status repeatedly.

while (CAS(&lock, 0, 1) == false); // Spin

• Pros: Zero latency if the lock is held briefly. No context switch.
• Cons: Wastes CPU cycles (“spinning”).
• Use Case: Kernel interrupt handlers, low-level driver code.

2. The Mutex (Sleeping)

If the lock is busy, the thread Yields the CPU and tells the OS Scheduler to put it in the Waiting Queue.

• Pros: Efficient use of CPU. Other threads can run.
• Cons: High latency. A Context Switch takes ~1-5 microseconds (thousands of CPU cycles).
• Use Case: Application level code (Java synchronized, Go Mutex).

---

5. Code Example: Using Locks

Always use the standard library locks. Do not implement your own spinlock in user-space code.

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class SafeCounter {
    private int count = 0;
    private final Lock lock = new ReentrantLock();

    public void increment() {
        lock.lock(); // Acquire lock
        try {
            count++; // Critical Section
        } finally {
            lock.unlock(); // Always unlock in finally!
        }
    }
}

package main

import (
    "sync"
)

type SafeCounter struct {
    mu    sync.Mutex
    count int
}

func (c *SafeCounter) Increment() {
    c.mu.Lock()   // Acquire lock
    defer c.mu.Unlock() // Ensure unlock happens
    c.count++     // Critical Section
}