Table of Contents
- 0. What Does This Article Answer Next?
- 1. How Does the JDK Implement ArrayBlockingQueue?
- 2. How Does Go Runtime Implement Channels?
- 3. How Does CPython Implement queue.Queue?
- 4. The Common Pattern Across the Three Implementations
- 5. Next: How the Two Models Relate
0. What Does This Article Answer Next?
The previous article examined the Atomicity, Visibility, and Ordering guarantees of BlockingQueue, channels, and queue.Queue at the language and standard-library level.
This article examines how Java, Go, and CPython implement those guarantees, from the runtime and OS threads down to the CPU.
1. How Does the JDK Implement ArrayBlockingQueue?
1.1 Layers
Java Source Code
Example: BlockingQueue.put() / take()
Role: define message handoff and blocking operations
│
▼
JDK Class Library
Example: ArrayBlockingQueue / ReentrantLock / AQS / ConditionObject
Role: maintain queue state, mutual exclusion, and condition waiters
│
▼
JVM Implementation (HotSpot)
Example: Unsafe.park, HotSpot Parker, Continuations
Role: implement low-level thread parking and virtual-thread execution
│
▼
OS Thread / Thread Parking
Example: Platform Thread / Parker; Virtual Thread / Carrier
Role: suspend and resume the relevant execution unit
│
▼
x86-64 Hardware
Example: Atomic Instruction / Cache Coherence / Memory Ordering
Role: provide the hardware foundations for Atomicity, Visibility, and Ordering
1.2 End-to-End Implementation Path for put / take
Within the JDK, these calls follow the paths below:
1.3 Guarantees at the Runtime / Language Implementation Layer
1.3.1 Atomicity
Here, Atomicity means one enqueue or dequeue updates the queue state without interleaving with another thread's queue operation.
Look at the second diagram in section 1.2, “ArrayBlockingQueue put/take control flow”. Both put and take call lockInterruptibly() before enqueue(e) or dequeue(). The array, indices, and count are updated while holding the lock, so other threads cannot modify the queue midway through.
1.3.2 Visibility and Ordering
Here, Visibility means the consumer can see data the producer wrote before enqueueing the message. Ordering means those writes take effect before the consumer reads them.
Look at the first diagram in section 1.2, “ArrayBlockingQueue across implementation layers”. The producer writes message.delta = 1, calls jobs.put(message), and releases the lock (Release). The consumer then acquires the same lock (Acquire), takes the message, and reads delta == 1. The earlier unlock happens-before the later lock acquisition, making the producer's writes visible to the consumer. notEmpty.signal() notifies the waiting consumer.
1.4 Guarantees at the Hardware Layer
At the hardware level, these guarantees rely on atomic instructions, cache coherence, and memory-ordering constraints:
Atomicity
→ Atomic Instruction
→ lock-state updates: LOCK CMPXCHG and related atomic operations
Visibility
→ Cache Coherence
→ cache-coherence protocols on x86-64 CPUs (e.g., MESIF or MOESI)
Ordering
→ Acquire / Release and required Memory Ordering
→ x86-64 memory ordering, locked RMW, and compiler constraints
Source code: ArrayBlockingQueue.java, AbstractQueuedSynchronizer.java, and ReentrantLock.java.
2. How Does Go Runtime Implement Channels?
2.1 Layers
Go Source Code
Example: jobs <- message / message := <-jobs
Role: define send/receive operations and their synchronization
│
▼
Go Implementation
Example: runtime/chan.go, chansend / chanrecv, hchan, sudog
Role: manage the buffer, waiting goroutines, and sender–receiver pairing
│
▼
Go Runtime / Scheduler (G / M / P)
Example: gopark / goready
Role: park a waiting goroutine and make a notified goroutine runnable
│
▼
OS Thread / Thread Parking
Example: M carrying a G, native waiting under internal lock contention
Role: run goroutines and park or wake OS threads when necessary
│
▼
x86-64 Hardware
Example: Atomic Instruction / Cache Coherence / Memory Ordering
Role: provide the hardware foundations for Atomicity, Visibility, and Ordering
2.2 End-to-End Implementation Path for Channel Communication
First, follow the Go channel communication across implementation layers sequence diagram for an unbuffered channel:
The core send and receive paths are:
2.3 Guarantees at the Runtime / Language Implementation Layer
2.3.1 Atomicity
Here, Atomicity means the channel-state changes and message pairing in one send or receive do not interleave with another goroutine's channel operation.
Look at the second diagram in section 2.2, “Core channel send and receive paths”. The runtime acquires hchan.lock before updating buf, sendx, recvx, and qcount for buffered channels or finding a waiting peer in recvq or sendq for a direct handoff. If communication cannot proceed, gopark suspends the goroutine and releases the lock. Once the other side completes the handoff, goready makes it runnable again.
2.3.2 Visibility and Ordering
Here, Visibility means the consumer can see the producer's writes from before the send after receiving the message. Ordering means those writes take effect before the consumer's reads after the receive.
Look at the first diagram in section 2.2, “Go channel communication across implementation layers”. The producer writes message.delta = 1 and sends the message on an unbuffered channel. sendDirect transfers it to the waiting consumer, which can read delta == 1 after the receive completes. The Go memory model states that a send is synchronized-before the corresponding receive completes. Buffered channels store the message first but follow the same rule.
2.4 Guarantees at the Hardware Layer
At the lowest level, the channel lock relies on atomic instructions and memory-ordering guarantees:
Atomicity
→ Atomic Instruction
→ CAS, exchange, and other atomics used by runtime locks
Visibility
→ Cache Coherence
→ cache-coherence protocols on x86-64 CPUs (e.g., MESIF or MOESI)
Ordering
→ Acquire / Release and required Memory Ordering
→ compiler constraints, x86-64 memory ordering, and locked RMW
Source code: runtime/chan.go, runtime/proc.go, internal/runtime/atomic/atomic_amd64.s.
3. How Does CPython Implement queue.Queue?
3.1 Layers
Python Source Code
Example: queue.Queue.put() / get()
Role: define enqueue, dequeue, and blocking behavior
│
▼
CPython Standard Library
Example: queue.Queue / threading.Condition / collections.deque
Role: maintain queue state, check conditions, and notify waiting threads
│
▼
CPython Implementation
Example: _thread.lock / PyMutex / Parking Lot
Role: manage atomic lock state and thread parking
│
▼
OS Thread / Thread Parking
Example: native threads, semaphores, platform-specific wait primitives
Role: block and wake threads under contention or while waiting for a condition
│
▼
x86-64 Hardware
Example: Atomic Instruction / Cache Coherence / Memory Ordering
Role: provide the hardware foundations for Atomicity, Visibility, and Ordering
3.2 End-to-End Implementation Path for put / get
First, follow the CPython queue.Queue across implementation layers sequence diagram with a consumer waiting on an empty queue:
The second diagram shows CPython Queue put/get control flow:
3.3 Guarantees at the Runtime / Language Implementation Layer
3.3.1 Atomicity
Here, Atomicity means a put or get checks and updates the queue without interleaving with another thread's queue operation.
Look at the second diagram in section 3.2, “CPython Queue put/get control flow”. Both put and get acquire Queue.mutex before checking the queue and calling deque.append(item) or deque.popleft(). If the queue is full or empty, Condition.wait() releases the lock. After notification, the thread reacquires the lock and checks the condition again before proceeding.
3.3.2 Visibility and Ordering
Here, Visibility means the consumer can see the message contents the producer wrote before enqueueing. Ordering means those writes take effect before the consumer reads them.
Look at the first diagram in section 3.2, “CPython queue.Queue across implementation layers”. The producer writes message.delta = 1, enqueues it with put(message), and releases Queue.mutex (Release). The consumer is notified, reacquires the same lock (Acquire), and reads delta == 1 after get() returns. Releasing and acquiring the lock provides the synchronization; not_empty.notify() notifies the waiting thread.
3.4 Guarantees at the Hardware Layer
One level lower, Queue.mutex is implemented using _thread.lock. Its PyMutex uses atomic operations to acquire the lock; if acquisition fails, the Parking Lot and platform-specific waiting mechanisms can suspend the thread:
Atomicity
→ Atomic Instruction
→ CAS and exchange operations on the PyMutex lock state
Visibility
→ Cache Coherence
→ cache-coherence protocols on x86-64 CPUs (e.g., MESIF or MOESI)
Ordering
→ Acquire / Release and required Memory Ordering
→ compiler-enforced atomic ordering and CPU memory-ordering constraints
Source code: Lib/queue.py, Lib/threading.py, Python/lock.c, Python/parking_lot.c.
4. The Common Pattern Across the Three Implementations
Consider a queue with capacity 2, shared by two producers and two consumers. A correct handoff must address three questions:
| Question | What can go wrong? | Mechanism |
|---|---|---|
| How can multiple producers and consumers hand off messages safely? | A message may be overwritten or removed twice | Mutex / Atomicity |
| What should happen when a handoff cannot proceed? | Consumers cannot take from an empty queue, and producers cannot put into a full one; busy-waiting also wastes CPU | Condition / Park / Wakeup |
| How can the consumer see what the producer wrote? | The consumer may receive a message without seeing earlier writes | Release / Acquire, Visibility / Ordering |
4.1 Who Can Enqueue or Dequeue? — Mutex / Atomicity
Initially, both queue slots are empty, and tail = 0 marks the next insertion position. Without synchronization, both producers can read the same index:
Producer A Producer B
Read tail = 0 Read tail = 0
Write buffer[0] = A Write buffer[0] = B
Result: both write slot 0, so one message is overwritten
Between reading the insertion position and updating the queue state, another producer may act on the same stale position.
Protect the queue with a mutex. Suppose Producer A acquires the lock first:
Initial queue: [empty, empty], tail = 0
Producer A Producer B
Lock acquired Try Lock → wait
Read tail = 0
Write slot 0: A
Update tail = 1
Unlock ──────────────────→ Lock acquired
Re-read tail = 1
Write slot 1: B
Update tail = 0
Unlock
Final queue: [A, B]
Producer B waits until A releases the mutex, then reads the updated value, tail = 1. It writes to slot 1 rather than overwriting slot 0. Either producer could acquire the lock first; both messages are still enqueued safely.
The same principle applies to competing consumers: checking the queue, taking a message, and updating queue state must happen within one critical section so two consumers cannot remove the same message. The mutex itself uses atomic operations to decide who acquires the lock, giving queue operations their Atomicity.
4.2 What If the Queue Is Empty or Full? — Condition / Park / Wakeup
Mutual exclusion prevents conflicting updates, but a consumer still cannot take from an empty queue, nor can a producer add to a full one.
Queue empty → Consumer waits on notEmpty
Queue full → Producer waits on notFull
For example, a consumer tries to take from an empty queue:
Consumer Producer
Lock → Queue is empty
Register notEmpty wait
Unlock → Park
Lock → Enqueue
signal(notEmpty)
Unlock
Wakeup → Lock
Recheck Queue state
Take message → Unlock
For a full queue, the roles reverse: the producer waits on notFull until a consumer dequeues a message and signals it.
The waiting thread must release the mutex so the other side can change the queue. On waking, it must acquire the lock and check again: another thread may have changed the queue first. Registering a waiter and releasing the mutex must also be coordinated to avoid lost wakeups.
4.3 After Handoff, Why Is the Message Visible? — Release / Acquire
Mutual exclusion and waiting make the handoff possible. The consumer must also see the data the producer wrote before sending the message.
Producer Consumer
Writes message.delta = 1
↓
Publish [Release] ─── Synchronized handoff ───▶ Receive [Acquire]
↓
Read delta == 1
For a mutex-protected queue, the producer's unlock (Release) happens-before the consumer's subsequent lock (Acquire) on the same mutex. This ensures the consumer can see what the producer wrote before sending the message.
An unbuffered Go channel does not need a message buffer. Instead, it directly pairs the sender and receiver, while ensuring that writes before the send are visible to the receiver.
Together with a message buffer and queue state, these three mechanisms form the core of a bounded blocking queue:
Message buffer + queue state
+
Mutex: protect an indivisible handoff
+
Condition: wait and wake when empty or full
+
Release / Acquire: make messages visible and ordered
↓
Blocking Queue
5. Next: How the Two Models Relate
The next article explores how shared memory and message passing relate and work together in practice. Article 12 will conclude the series by bringing the broader picture of concurrent programming together.
This article was first published on ThinkerQAQ's personal blog and syndicated here by the author. The original article may be revised over time; please refer to the personal blog for the latest version.
Top comments (0)