Yuxu Ge
Article · 2025-04-28

Multithreading Locks: Implementation Principles and Engineering Practice

Operating System Primitives vs. Atomic Instructions

The operating system provides a set of primitive operations—semaphores, mutexes, condition variables—implemented within the kernel. These primitives may require threads to transition between user mode and kernel mode to complete synchronization operations. When a thread attempts to acquire a held lock, the operating system suspends it, then resumes it once the lock becomes available. The kernel scheduler thus ensures mutual exclusion while preventing the thread from wasting CPU cycles during the wait.

Atomic instructions are processor-level operations that complete within a single cycle without interruption. Common examples include atomic increment, atomic decrement, and compare-and-swap (CAS). Using these primitives, programmers can implement locks in user mode—for example, spinlocks rely on atomic operations alone.

Unlike OS-primitive-based locks, atomic-based locks do not voluntarily release the CPU. If the lock is held when a thread calls an atomic operation, the thread does not block; instead it retries repeatedly in a loop—this behavior is called busy-waiting. Spinlocks suit scenarios where the critical section is very short, since the waiting thread continuously consumes CPU cycles. For longer critical sections, busy-waiting becomes wasteful.

Performance and Applicable Scenarios

The two approaches differ markedly in performance characteristics.

OS primitives incur overhead from system calls and context switches on every lock operation. Under light contention, this overhead is acceptable; under heavy contention and frequent lock attempts, constant user-kernel mode transitions become a performance bottleneck. OS primitives also prevent needless CPU consumption: when thread A holds a lock, thread B requesting it suspends and consumes no CPU; when A releases, the OS wakes B.

Atomic instruction-based locks operate entirely in user mode, avoiding kernel entry cost and delivering high performance under low contention. However, when many threads contend for the same lock, problems emerge: the lack of blocking means threads spin continuously, consuming CPU. Additionally, frequent atomic operations on a shared variable across multiple cores create cache-coherency overhead—each atomic update requires synchronization across core caches. This can render even fast operations slow. If multiple cores continuously increment and decrement a shared variable atomically, bus contention may cause each operation to take hundreds of nanoseconds or more. Heavy reliance on atomic-based locks thus causes processor resource contention and degrades overall performance.

Use OS primitives when:

These cases favor mutex and semaphore over spinlocks, since blocked threads conserve CPU.

Use atomic operation-based locks when:

Spinlocks avoid mode transitions; on multicore systems with brief contention, a few spin cycles may cost less than thread suspension and resumption. However, if contention intensifies or critical sections lengthen, spinlocks waste CPU—switch to blocking mechanisms.

CPU Cache Coherence and Memory Barriers

Regardless of locking strategy, memory visibility and instruction ordering must be addressed. Modern CPUs perform out-of-order execution and use multilevel caches to accelerate memory access. A write by one thread may not immediately appear to threads on other cores; the processor and compiler may reorder instructions without violating single-threaded semantics. In multithreaded code, these optimizations create hazards: thread A may update a shared variable before releasing a lock, yet thread B acquiring the same lock later reads stale data—either because A's write remains in its own cache or because instruction reordering delayed the write's effect.

Correct multithreaded programs require memory barriers in lock implementations. A memory barrier prevents certain memory operations from reordering and ensures cache data is flushed promptly, making prior memory updates visible to other cores. Most high-level languages embed appropriate barrier semantics in their lock primitives. Java's synchronized blocks establish a "Happens-Before" relationship: changes released by one thread become visible to another that later acquires the same lock. C++'s std::atomic defaults to sequential consistency (memory_order_seq_cst), preventing atomic operation reordering. These mechanisms spare developers from manual barrier insertion. For lower-level implementers using raw atomic instructions, understanding the target architecture's memory model is essential—some weak-model CPUs require explicit mfence or sfence instructions around lock operations. x86, with its strong memory ordering, often needs only the implicit barrier in lock-prefixed instructions like lock cmpxchg.

Lock Optimization Strategies

Several techniques optimize lock performance:

Spin-then-block (adaptive locks): Pure spinlocks waste CPU under heavy contention or long critical sections. Production systems often use adaptive spin: threads spin briefly, then block if the lock remains unavailable. This avoids a context switch when the lock is about to be released, yet prevents CPU waste when release is distant. Linux futex (fast userspace mutex) spins in user mode first, then enters kernel sleep. Java's JVM combines spinning with suspension by default.

Biased locking: Biased locks optimize for the case where one thread repeatedly acquires the same lock. In this mode, after first acquisition the lock is marked as biased toward that thread; subsequent acquisitions by the same thread incur no atomic operations. Contention by another thread revokes the bias and restores normal locking. Benefit: near-zero locking cost under no contention. Cost: some overhead when bias is revoked. Biased locking helps when locks rarely see concurrent access—it hurts when many threads compete. HotSpot JVM uses this as an important optimization (tunable via startup flags).

Fine-grained locking and lock striping: Architectural decisions also reduce contention. If a coarse lock (protecting many unrelated resources) becomes a bottleneck, split it into multiple finer locks, allowing different threads to lock different resources and reducing conflicts. Similarly, reader-writer locks let multiple threads read concurrently while excluding during writes—effective for read-heavy workloads. These design-level choices fall outside single-lock implementation but significantly improve application concurrency.

Lock-free alternatives: Some scenarios avoid traditional locks altogether using atomic variables or lock-free data structures. This eliminates lock overhead and improves concurrency. However, lock-free algorithms are typically complex and error-prone, requiring careful design and verification. A practical middle ground uses language or library-provided concurrent containers and atomic classes—Java's AtomicInteger, C++'s std::atomic—which leverage underlying atomic operations for thread safety without explicit locking or the cognitive burden of lock-free design.

Engineering Practice Examples

The following code samples in different languages illustrate lock implementations and their behavior.

Example 1: POSIX Mutex (C)

POSIX Threads (Pthreads) is C's standard multithreading library, providing mutexes, condition variables, and other OS primitives. This code shows how to protect a critical section:

#include <pthread.h>
#include <stdio.h>

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
int counter = 0;

void *increment(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&lock);
        counter++;
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

int main() {
    pthread_t t1, t2;

    pthread_create(&t1, NULL, increment, NULL);
    pthread_create(&t2, NULL, increment, NULL);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    printf("Counter: %d\n", counter);

    return 0;
}

Two threads each increment a global counter one million times. We wrap counter++ with pthread_mutex_lock() and pthread_mutex_unlock() to ensure only one thread modifies counter at a time. If one thread holds the lock, the other blocks when calling pthread_mutex_lock, then resumes once the lock is released. This mutual exclusion prevents race conditions and yields a correct final count.

Example 2: C++11 Atomic Spinlock

C++11's header provides atomic instruction interfaces. Using these, we can implement spinlocks:

#include <atomic>
#include <iostream>
#include <thread>

std::atomic_flag lock = ATOMIC_FLAG_INIT;
int counter = 0;

void increment() {
    for (int i = 0; i < 1000000; i++) {
        while (lock.test_and_set(std::memory_order_acquire)) {
            // 自旋等待锁释放
        }
        counter++;
        lock.clear(std::memory_order_release);
    }
}

int main() {
    std::thread t1(increment);
    std::thread t2(increment);

    t1.join();
    t2.join();

    std::cout << "Counter: " << counter << std::endl;
    return 0;
}

Two threads each increment a global counter one million times using an atomic spinlock. Each iteration, a thread calls lock.test_and_set(std::memory_order_acquire) to attempt acquisition. If the lock is held, test_and_set returns true and the while loop spins; once it returns false (successful acquisition), the thread exits the loop, executes counter++, then calls lock.clear(std::memory_order_release) to release. Only one thread executes counter++ at a time. While the lock is held by another thread, the current thread spins in the while loop—avoiding context-switch overhead but wasting CPU if release is distant.

Example 3: Java synchronized Keyword

Java's built-in synchronized keyword protects methods or code blocks, ensuring at most one thread executes the protected code at a time:

public class Counter {
    private int count = 0;

    public synchronized void increment() {
        count++;
    }

    public static void main(String[] args) throws InterruptedException {
        Counter counter = new Counter();
        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 1000000; i++) {
                counter.increment();
            }
        });
        Thread t2 = new Thread(() -> {
            for (int i = 0; i < 1000000; i++) {
                counter.increment();
            }
        });

        t1.start();
        t2.start();
        t1.join();
        t2.join();

        System.out.println("Counter: " + counter.count);
    }
}

The increment() method is declared synchronized, so only one thread can enter at a time; others block at entry. All operations on counter.count are serialized, ensuring correctness.

When a thread enters increment(), the JVM acquires the internal lock associated with the Counter instance (the this object). The implementation combines OS primitives with atomic operations. In HotSpot JVM, locks progress through states: first attempting lightweight locking via CAS, then upgrading to heavyweight locking with kernel blocking if contention is detected. This HotSpot source fragment shows the strategy:

void ObjectSynchronizer::enter(Handle obj, BasicLock* lock, TRAPS) {
    if (UseBiasedLocking) {
        BiasedLocking::revoke_and_rebias(obj, false, THREAD);
        assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now");
    }
    slow_enter(obj, lock, THREAD);
}

void ObjectSynchronizer::slow_enter(Handle obj, BasicLock* lock, TRAPS) {
    // ... 省略其他代码

    if (mark->is_neutral()) {
        // 尝试使用轻量级锁
    } else if (mark->has_locker()) {
        // ... 省略其他代码
    } else {
        // 如果轻量级锁失败，则转为使用重量级锁（基于操作系统原语实现）
        ObjectSynchronizer::inflate(THREAD, obj())->enter(THREAD);
    }
}

The JVM first attempts biased locking (if enabled), then lightweight locking (for neutral mark words). If another thread holds the lock, it calls inflate() to promote to heavyweight and blocks the thread. This layered approach lets Java use fast atomic operations under no contention and kernel scheduling under contention, balancing performance and functionality.

Example 4: Java AtomicInteger

Java's java.util.concurrent.atomic package provides atomic classes like AtomicInteger and AtomicLong, offering lock-free thread safety via underlying atomic instructions:

import java.util.concurrent.atomic.AtomicInteger;

public class Counter {
    private AtomicInteger count = new AtomicInteger(0);

    public void increment() {
        count.incrementAndGet();
    }

    public static void main(String[] args) throws InterruptedException {
        Counter counter = new Counter();
        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 1000000; i++) {
                counter.increment();
            }
        });
        Thread t2 = new Thread(() -> {
            for (int i = 0; i < 1000000; i++) {
                counter.increment();
            }
        });

        t1.start();
        t2.start();
        t1.join();
        t2.join();

        System.out.println("Counter: " + counter.count);
    }
}

Two threads each increment an AtomicInteger counter one million times. The incrementAndGet() method ensures the increment is atomic (thread-safe). Unlike traditional locks, atomic classes operate entirely in user mode with no thread switching or context overhead—ideal for simple counting.

Internally, AtomicInteger relies on CAS and other atomic instructions. Here's a simplified incrementAndGet():

public final int incrementAndGet() {
    for (;;) {
        int current = get();
        int next = current + 1;
        if (compareAndSet(current, next))
            return next;
    }
}

The method spins in a loop, repeatedly trying until CAS successfully updates the count. Each iteration reads the current value, computes the new value, then calls compareAndSet(current, next) to atomically update. If compareAndSet returns false (another thread modified the value), the loop retries. compareAndSet invokes a processor atomic instruction—lock cmpxchg on x86—ensuring compare-and-swap atomicity.

Common Issues and Precautions

Concurrent programming with locks introduces several pitfalls:

Deadlock: Mutual waiting among threads causes deadlock. For instance, thread A holds L1 and waits for L2; thread B holds L2 and waits for L1. Both threads suspend forever. Prevention techniques include minimizing nested locks, establishing a fixed lock acquisition order across all threads, and using timeout-based tryLock() to detect potential deadlock.

Priority inversion: A real-time systems hazard. A high-priority thread waiting for a lock held by a low-priority thread may be starved if a medium-priority thread consumes CPU. The system's execution order inverts relative to thread priorities. The famous Mars Pathfinder bug exemplified this: a low-priority task held a lock, a high-priority task waited for it, and a medium-priority task ran continuously, starving the high-priority task. One mitigation is priority inheritance: temporarily raise the priority of the lock holder when a high-priority thread blocks, allowing the lock holder to run and release the lock quickly.

Spinlock hazards: Spinlocks depend on environment and critical section duration. On single-core processors, spinlocks perform poorly—if the lock holder is suspended by the scheduler, other threads spin uselessly while the holder cannot run, potentially starving the system. Even on multicore systems, long critical sections make busy-waiting wasteful. Spinlocks suit short critical sections and multicore systems; single-core systems and long-held locks favor blocking mechanisms.

Lock release guarantees: Every lock acquisition path must have a corresponding release. If an exception or early return occurs in the critical section, the lock must still be released. Java requires release in a finally block; C++ uses RAII (Resource Acquisition Is Initialization) to manage lock lifetimes. An unreleased lock causes other threads to wait forever, degrading system stability.

Lock granularity and performance: Choosing appropriate granularity is crucial. Coarse-grained locks (one global lock for many unrelated resources) reduce concurrency and serialize work that could run in parallel. Fine-grained locks (each small object separately locked) increase complexity and deadlock risk. Balance data consistency against concurrent performance—avoid both excessive contention and fragmentation.

Conclusion

Multithreading locks use two primary approaches—OS primitives and atomic instructions—with distinct trade-offs. OS primitives support complex synchronization (blocking waits, signaling) reliably but incur kernel overhead that may limit performance under high contention. Atomic-based locks minimize overhead and leverage hardware potential under no contention but offer limited synchronization support and risk CPU waste if misused (missing barriers, wrong scenario).

There is no one-size-fits-all solution. Evaluate the specific case: simple counters often benefit from atomic variables, avoiding traditional lock overhead; complex mutual exclusion and synchronization demand OS-level tools like mutex or semaphore. Most modern languages and frameworks already combine multiple strategies (spin-then-block, biased locking) into production-ready locks, and their defaults usually suffice.

Understanding lock internals helps write more efficient, robust concurrent code. More important still: follow sound concurrent practices—minimize lock usage, avoid holding locks long, prevent deadlock and starvation.

References

© 2026 Yuxu Ge ·