Concurrency Programming (4): How Mutexes Are Implemented — From Runtime to CPU

Table of Contents

• 0. What Does This Article Answer Next?
• 1. How Does HotSpot Implement synchronized?
  • 1.1 Layers
  • 1.2 End-to-End Implementation Path for synchronized
  • 1.3 Guarantees at the Runtime / Language Implementation Layer
    • 1.3.1 Atomicity
    • 1.3.2 Visibility and Ordering
  • 1.4 Guarantees at the Hardware Layer
• 2. How Is sync.Mutex Implemented in Go?
  • 2.1 Layers
  • 2.2 End-to-End Implementation Path for sync.Mutex
  • 2.3 Guarantees at the Runtime / Language Implementation Layer
    • 2.3.1 Atomicity
    • 2.3.2 Visibility and Ordering
  • 2.4 Guarantees at the Hardware Layer
• 3. How Does CPython Implement threading.Lock?
  • 3.1 Layers
  • 3.2 End-to-End Implementation Path for threading.Lock
  • 3.3 Guarantees at the Runtime / Language Implementation Layer
    • 3.3.1 Atomicity
    • 3.3.2 Visibility and Ordering
  • 3.4 Guarantees at the Hardware Layer
• 4. The Common Pattern Across the Three Implementations
  • 4.1 Who Gets In? — Atomically Updating Lock State
  • 4.2 What Happens If You Don’t Get the Lock? — Spin / Park / Wakeup
  • 4.3 After Acquiring the Lock, Why Are the Previous Holder’s Writes Visible?
• 5. Next: Atomic

---

0. What Does This Article Answer Next?

The previous article used language-memory-model rules to explain how a mutex provides Atomicity, Visibility, and Ordering.

This article goes one layer deeper and follows how Java, Go, and CPython turn those guarantees into concrete behavior across the Runtime, OS Thread, and CPU layers.

---

1. How Does HotSpot Implement synchronized?

1.1 Layers

First, establish the implementation stack for Java:

Java Source Code
Example: synchronized
Role: mark a synchronized region
        │
        ▼
JVM Bytecode
Example: monitorenter / monitorexit (synchronized blocks)
Role: encode Monitor entry / exit
        │
        ▼
JVM Implementation (HotSpot)
Example: Synchronization Runtime
Role: implement the Monitor semantics defined by the JVM
        │
        ▼
OS Thread / Thread Parking
Example: Platform Thread / ParkEvent
Role: carry Park / Wakeup when contention persists
        │
        ▼
x86-64 Hardware
Example: Atomic Instruction / Cache Coherence / Fence
Role: provide the hardware foundation for Atomicity, Visibility, and Ordering

1.2 End-to-End Implementation Path for synchronized

The sequence diagram above shows only the main cross-layer path. Here, OS Thread represents the path that actually blocks a platform thread. Current HotSpot can first try to unmount a virtual thread, so not every contended synchronized operation blocks an OS thread.

The contention path inside the Runtime can be expanded further:

1.3 Guarantees at the Runtime / Language Implementation Layer

1.3.1 Atomicity

Atomicity corresponds to the two atomic lock-acquisition attempts in the flowchart above:

Fast Path: CAS markWord lock bits [Acquire]
Inflated Monitor: CAS _owner [Acquire]

Both update lock state atomically. When multiple threads contend for the lock, only one can acquire it and enter the critical section.

1.3.2 Visibility and Ordering

Visibility and Ordering correspond to the lock boundaries in the flowchart:

Acquire lock: CAS ... [Acquire]
Release lock: release lock state [Release]

Together, Release and Acquire connect the two critical sections, ensuring that writes from the previous lock holder are observed by the next holder in the required order.

1.4 Guarantees at the Hardware Layer

At the hardware layer, these guarantees are realized through CPU Cache Coherence and memory-ordering constraints.

For Java, this corresponds to the hardware model introduced in the first article:

Atomicity
  → Atomic Instruction
  → HotSpot / x86-64: LOCK CMPXCHG

Visibility
  → Cache Coherence
  → Typical x86-64 CPUs: MESI-family (e.g. MESIF / MOESI)

Ordering
  → Fence
  → HotSpot / x86-64: LOCK ADDL $0, 0(%rsp)

LOCK ADDL $0, 0(%rsp) is a concrete path HotSpot uses to implement a full fence on Linux/x86. This does not mean every synchronized operation executes an extra instance of that instruction: x86 memory-ordering rules and LOCKed RMW operations also contribute to the required ordering guarantees.

For implementation details, see OpenJDK’s markWord.hpp, objectMonitor.cpp, objectMonitor.inline.hpp, graphKit.cpp, and orderAccess_linux_x86.hpp.

---

2. How Is sync.Mutex Implemented in Go?

2.1 Layers

Go Source Code
Example: sync.Mutex / Lock() / Unlock()
Role: define a mutual-exclusion boundary
        │
        ▼
Go Implementation
Example: sync / internal/sync
Role: implement the Mutex state machine and fast / slow paths
        │
        ▼
Go Runtime / Scheduler
Example: runtime_SemacquireMutex / gopark / goready
Role: park / wake goroutines
        │
        ▼
OS Thread (M)
Example: M in the G-M-P model
Role: execute goroutines; gopark does not block M
        │
        ▼
x86-64 Hardware
Example: Atomic Instruction / Cache Coherence / Fence
Role: provide the hardware foundation for Atomicity, Visibility, and Ordering

2.2 End-to-End Implementation Path for sync.Mutex

The sequence diagram above shows only the main cross-layer path. The key difference from Java and CPython is that sync.Mutex waits through gopark: it parks the goroutine (G), not the OS thread (M), so that M can continue running another runnable goroutine.

The contention path inside sync.Mutex can be expanded further:

2.3 Guarantees at the Runtime / Language Implementation Layer

2.3.1 Atomicity

Atomicity corresponds to the atomic lock-state modifications in the flow above:

Acquire lock: CompareAndSwapInt32(&state, 0, mutexLocked)
Release lock: AddInt32(&state, -mutexLocked)

When multiple goroutines contend for the mutex, only one can atomically change state from unlocked to locked and enter the critical section.

On amd64, these atomic operations are implemented with LOCK CMPXCHGL and LOCK XADDL.

2.3.2 Visibility and Ordering

Visibility and Ordering come from the synchronization boundary formed by Lock / Unlock. Once one holder calls Unlock, a goroutine that subsequently acquires the mutex with Lock observes writes from the previous critical section in the required order.

2.4 Guarantees at the Hardware Layer

At the hardware layer, these guarantees are realized through CPU Cache Coherence, x86 memory ordering, and the ordering constraints of the atomic instructions themselves.

For Go, this corresponds to the hardware model introduced in the first article:

Atomicity
  → Atomic Instruction
  → Go / x86-64: LOCK CMPXCHGL / LOCK XADDL

Visibility
  → Cache Coherence
  → Typical x86-64 CPUs: MESI-family (e.g. MESIF / MOESI)

Ordering
  → Fence / equivalent ordering constraint
  → Go / x86-64: LOCK CMPXCHGL / LOCK XADDL

This amd64 Mutex path does not need an additional MFENCE; the LOCKed RMW operations already provide both the atomic state update and the ordering constraints required here.

For implementation details, see internal/sync/mutex.go, runtime/sema.go, runtime/HACKING.md, and internal/runtime/atomic/atomic_amd64.s.

---

3. How Does CPython Implement threading.Lock?

This section focuses on the current CPython implementation.

3.1 Layers

Python Source Code
Example: threading.Lock / acquire() / release()
Role: declare a mutual-exclusion boundary
        │
        ▼
CPython Binding
Example: _thread.lock
Role: map the Python Lock API to CPython's lock implementation
        │
        ▼
CPython Implementation
Example: PyMutex / Parking Lot
Role: implement lock state and waiter queues
        │
        ▼
OS Thread / OS Wait Primitive
Example: WaitForMultipleObjects / sem_wait / pthread_cond_wait
Role: block / wake the thread when the Parking Lot waits
        │
        ▼
x86-64 Hardware
Example: Atomic Instruction / Cache Coherence / Fence
Role: provide the hardware foundation for Atomicity, Visibility, and Ordering

3.2 End-to-End Implementation Path for threading.Lock

The sequence diagram above shows only the main cross-layer path. CPython’s internal contention path can be expanded further:

3.3 Guarantees at the Runtime / Language Implementation Layer

3.3.1 Atomicity

Atomicity comes from the atomic state changes that PyMutex performs on _bits:

Acquire lock: _Py_atomic_compare_exchange_uint8(..., _Py_LOCKED)
Release lock (no waiter): _Py_atomic_compare_exchange_uint8(..., _Py_UNLOCKED)

When waiters exist, the release path enters _PyParkingLot_Unpark(), whose callback atomically updates _bits.

When multiple threads contend for the lock, only one can successfully set _Py_LOCKED and enter the critical section.

3.3.2 Visibility and Ordering

Visibility and Ordering come from the synchronization boundary formed by acquire() / release(). In current CPython, the default atomic compare-exchange and store operations use __ATOMIC_SEQ_CST in the GCC / Clang implementation.

3.4 Guarantees at the Hardware Layer

At the hardware layer, these guarantees are realized through CPU Cache Coherence, x86 memory ordering, and those sequentially consistent atomic operations.

For current CPython, this corresponds to the hardware model introduced in the first article:

Atomicity
  → Atomic Instruction
  → CPython / x86-64: LOCK CMPXCHGB

Visibility
  → Cache Coherence
  → Typical x86-64 CPUs: MESI-family (e.g. MESIF / MOESI)

Ordering
  → Fence / equivalent ordering constraint
  → CPython / x86-64: SEQ_CST atomic
    (typically LOCK CMPXCHGB / memory XCHGB)

This likewise does not require every Lock operation to execute an additional MFENCE: on x86-64, LOCKed RMW operations and sequentially consistent atomics already provide the required ordering constraints.

For implementation details, see Modules/_threadmodule.c, Python/lock.c, Python/parking_lot.c, and Include/cpython/pyatomic_gcc.h.

---

4. The Common Pattern Across the Three Implementations

With Java, Go, and CPython in view, we can strip away the implementation-specific details and focus on the three problems every mutex implementation must solve.

4.1 Who Gets In? — Atomically Updating Lock State

Suppose a lock is represented by a single state variable:

0 = unlocked
1 = locked

A and B must not both read 0 and then both write 1; otherwise, each would believe it had acquired the lock.

Therefore, checking the lock state and changing it to locked must be one atomic operation, such as Compare-And-Swap:

Compare-And-Swap(lock_state, 0, 1)

When two execution units compete:

CPU A                         CPU B

CAS 0 -> 1                   CAS 0 -> 1
    │                             │
    ▼                             ▼
  success                       failed

Only one contender can successfully modify the lock state. A mutex builds on this small hardware atomic primitive to protect an arbitrary critical section such as counter++.

4.2 What Happens If You Don’t Get the Lock? — Spin / Park / Wakeup

After CAS fails, an execution unit should not spin on the lock state forever.

A common path is:

try atomic lock acquisition
        │
        ├── success ──> enter critical section
        │
        └── failure
              │
              ├── Spin briefly
              │      │
              │      └── retry
              │
              └── Park / wait
                         │
                         └── wake after lock release

Spinning works well when the expected wait is very short because it avoids immediately entering a blocking path. If contention persists, parking prevents the waiter from continuously consuming CPU time.

4.3 After Acquiring the Lock, Why Are the Previous Holder’s Writes Visible?

The first two questions answer who gets the lock and what happens when acquisition fails. The third is about memory visibility: why are writes from the previous holder’s critical section visible to the next holder?

Across all three implementations, the common mechanism is a Release / Acquire synchronization boundary between lock release and the next lock acquisition:

previous lock holder
critical-section writes
    │
    ▼
unlock [Release]
    │
    ▼
lock [Acquire]
    │
    ▼
next lock holder
critical-section reads

Release constrains memory operations before the unlock, while Acquire constrains memory operations after the subsequent lock.

Therefore, when the next execution unit acquires the same lock, writes from the earlier critical section are ordered before reads in the later one. This is the memory-ordering guarantee that every mutex implementation must establish.

The first three sections showed how each Runtime and CPU pair realizes this Release / Acquire boundary.

---

5. Next: Atomic

A mutex only needs a small amount of atomic state to enforce mutual exclusion over a critical section of arbitrary size.

Atomic narrows the scope further: instead of protecting an entire critical section, it makes a single read, write, or update of shared state indivisible.

The next article follows how this smaller synchronization unit is implemented.