Mutex ownership and a bounded work queue

A mutex protects a bounded work queue when it guards the relationship between the queue’s fields. Locking each array access separately can leave the head, tail and count inconsistent. If you are implementing a ring buffer, write the queue invariant before choosing where the lock starts and ends.

Use a capacity-three queue of integer jobs. head identifies the next slot to remove, tail identifies the next slot to fill, and count says how many jobs are present. The model assumes multiple producers and consumers, one shared mutex, and operations that either complete under that mutex or leave the queue unchanged.

The OSTEP locks chapter explains mutual exclusion for such critical sections. Its concurrency-bugs chapter also shows why protecting individual accesses can still miss a larger atomicity requirement.

Follow the ring through a wrap

Start empty with head zero, tail zero and count zero. Enqueue job 10 into slot zero, advance tail to one and increase count to one. Enqueue job 20 into slot one; tail becomes two and count becomes two.

Dequeue returns slot zero’s job 10, advances head to one and decreases count to one. Enqueue job 30 into slot two. Advancing tail modulo three wraps it to zero. Finally enqueue job 40 into slot zero; tail becomes one and count becomes three.

Operation	Head	Tail	Count	Logical queue
Empty	0	0	0	Empty
Enqueue 10, 20	0	2	2	10, 20
Dequeue	1	2	1	20
Enqueue 30	1	0	2	20, 30
Enqueue 40	1	1	3	20, 30, 40

Head and tail are equal when the queue is empty and when it is full. The count resolves that ambiguity in this representation. Another implementation can reserve an unused slot or maintain a separate full flag, but it then needs a different invariant.

View full-size image ↗

The physical array at the end contains 40, 20 and 30. The logical dequeue order is 20, 30 and 40. A debugging print that lists array indices in ascending order can misrepresent the queue unless it begins at head and uses count.

Choose the critical-section boundary

An enqueue must check that count is below capacity, write the new item, advance tail and increase count while holding the same mutex. If it releases the lock after the capacity check, another producer can consume the final free slot before the original producer writes.

Likewise, dequeue checks nonempty state, reads the item, advances head and decreases count under the mutex. Returning a failure for an empty queue is one possible API. Waiting for work is another, but waiting needs a separate coordination mechanism that releases the mutex so a producer can make progress.

The invariant includes 0 <= count <= capacity and valid index ranges. It also includes the ordering relationship between occupied slots and head. A count that stays within range is insufficient if two producers overwrite the same slot or if tail advances before the slot contains a valid item.

A practical review technique is to identify the operation’s linearization point: a moment during its execution at which it can be regarded as taking effect. In this locked design, the protected transition can provide such a point because other queue operations cannot observe its intermediate fields. The exact selected instruction matters less than the proof that callers see a legal sequential order.

Avoid work with an uncontrolled lifetime under the lock

A consumer should usually remove a job while holding the mutex, release the mutex, then execute the job. Running an arbitrary callback inside the critical section holds up every producer and consumer. The callback may also call back into the queue and attempt to acquire the same nonrecursive mutex.

Moving a complex job object can throw in some languages and type designs. The queue must define whether a failed move leaves the item present, removes it, or requires another recovery rule. Integer jobs make the teaching trace simple, but they do not eliminate exception-safety questions in a generic container.

Lock ownership also needs a consistent scope. A guard object or equivalent structured cleanup reduces the risk that an error path returns while still holding the mutex. If the queue stores references to externally owned jobs, document how long those jobs must remain alive after enqueue.

Mutual exclusion is not a fairness promise

A mutex prevents simultaneous protected access. It does not necessarily guarantee FIFO acquisition or a bounded waiting time for every thread. A producer can repeatedly lose the race to acquire the mutex while other threads continue making progress. If the application needs a fairness or deadline contract, evaluate that separately.

A single mutex also serializes queue bookkeeping. That can be acceptable when job execution dominates the cost. Replacing it with a more complicated concurrent queue only helps if the queue is a meaningful bottleneck and the replacement preserves the required semantics, including shutdown and memory reclamation.

Test wraparound, empty and full transitions, alternating enqueue/dequeue and multiple complete wraps. Then add concurrent stress with a way to check each submitted job appears exactly once. Preserve the sequential ring-buffer tests: concurrency does not excuse an incorrect tail update that would already fail with one thread.

Run the queue’s sequential contract first

This Python implementation keeps each check and mutation inside one lock context. It uses ordinary object references as jobs. The example exercises the wrap shown above, rejection of a full enqueue and the difference between an empty result and a real item whose value is None. Run it as a standalone Python script.

from threading import Lock

class Ring:
    def __init__(self, capacity):
        if type(capacity) is not int or capacity <= 0:
            raise ValueError("capacity must be a positive integer")
        self._slots = [None] * capacity
        self._head = self._tail = self._count = 0
        self._lock = Lock()

    def try_put(self, item):
        with self._lock:
            if self._count == len(self._slots):
                return False
            self._slots[self._tail] = item
            self._tail = (self._tail + 1) % len(self._slots)
            self._count += 1
            return True

    def try_get(self):
        with self._lock:
            if self._count == 0:
                return False, None
            item = self._slots[self._head]
            self._slots[self._head] = None
            self._head = (self._head + 1) % len(self._slots)
            self._count -= 1
            return True, item

    def snapshot(self):
        with self._lock:
            size = len(self._slots)
            return [self._slots[(self._head + i) % size]
                    for i in range(self._count)]

queue = Ring(3)
assert queue.try_put(10) and queue.try_put(20)
assert queue.try_get() == (True, 10)
assert queue.try_put(30) and queue.try_put(40)
assert queue.snapshot() == [20, 30, 40]
assert not queue.try_put(50)
assert [queue.try_get() for _ in range(3)] == [
    (True, 20), (True, 30), (True, 40)
]
assert queue.try_get() == (False, None)
assert queue.try_put(None)
assert queue.try_get() == (True, None)

The name try_put means that a full queue returns immediately after acquiring the mutex; it does not promise a nonblocking mutex acquisition. Another thread may still hold the lock. Likewise, try_get returns an explicit success bit so that an empty result is distinguishable from a queued None. The snapshot creates a new outer list while holding the mutex; it does not clone the objects referenced by that list. Callers that mutate a shared job object still need an ownership rule.

View full-size image ↗

The second figure separates two possible API implementations. In the broken version, A checks count two, unlocks, and later acts on that old answer after B raises count to three. In the protected version, whichever producer acquires the lock second observes three and returns false without touching a slot. The operation’s result depends on the state at its protected decision, not on an earlier observation made outside that transition.

For an exercise, compare the ring with a simple reference list over a chosen sequence of put and get commands. Accept a put exactly when the reference length is below capacity; otherwise require false and an unchanged snapshot. On a successful get, require the reference’s first object by identity, not just an equal value. Include capacity one: equal head and tail then occur after every operation, so a design that guesses emptiness from those indices alone fails immediately.

After the sequential contract passes, test several producers with uniquely identified jobs and verify that completed consumption contains every accepted job exactly once. Such a finite run can reveal omissions or duplicates but cannot prove all thread schedules safe. The review argument still depends on the shared mutex discipline, the invariant at each operation boundary and a shutdown protocol that keeps the queue alive until all callers finish.