Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

CAS queue protocol: link, help, and reclaim safely

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A linked multiple-producer, multiple-consumer queue can use a dummy head, a tail pointer, and compare-and-swap operations to coordinate insertion and removal. Enqueue first links a new node after the observed tail, then tries to advance tail. Another participant may help advance a lagging tail. Dequeue reads the successor of the dummy head, helps tail if needed, and advances head to claim the next item. This Python program is a sequential schedule model: its comparison methods are ordinary Python checks and assignments, not atomic instructions. It demonstrates state transitions and a stale-link failure; it cannot be called a concurrent lock-free queue.

Operational case

One simulated participant remembers the initial tail. A completed offer links J-47, changing that tail node's successor. The remembered attempt to link a different node with the old expected successor returns false. J-61 follows, and two takes return J-47 then J-61 before empty returns None. A real implementation must make every shared-pointer comparison atomic, define memory ordering, and prevent a removed node from being freed or reused while another participant still holds its address. An address reused too early can make a stale comparison appear valid again; tagging or managed reclamation addresses that separate boundary.

Working Python program

python
"""Sequential CAS schedule model, not a concurrent lock-free implementation."""

from dataclasses import dataclass


@dataclass
class QueueNode:
    job_id: str | None
    next_id: int | None = None


class QueueSchedule:
    def __init__(self):
        self.nodes = {0: QueueNode(None)}
        self.head_id = 0
        self.tail_id = 0
        self.next_node_id = 1

    def cas_link(self, node_id, expected_next, replacement):
        if self.nodes[node_id].next_id != expected_next:
            return False
        self.nodes[node_id].next_id = replacement
        return True

    def cas_tail(self, expected_tail, replacement):
        if self.tail_id != expected_tail:
            return False
        self.tail_id = replacement
        return True

    def cas_head(self, expected_head, replacement):
        if self.head_id != expected_head:
            return False
        self.head_id = replacement
        return True

    def offer(self, job_id):
        node_id = self.next_node_id
        self.next_node_id += 1
        self.nodes[node_id] = QueueNode(job_id)
        while True:
            tail = self.tail_id
            successor = self.nodes[tail].next_id
            if successor is not None:
                self.cas_tail(tail, successor)
            elif self.cas_link(tail, None, node_id):
                self.cas_tail(tail, node_id)
                return

    def take(self):
        while True:
            head = self.head_id
            tail = self.tail_id
            successor = self.nodes[head].next_id
            if successor is None:
                return None
            if head == tail:
                self.cas_tail(tail, successor)
                continue
            job_id = self.nodes[successor].job_id
            if self.cas_head(head, successor):
                return job_id


schedule = QueueSchedule()
stale_tail = schedule.tail_id
schedule.offer("J-47")
print(schedule.cas_link(stale_tail, None, 99))
schedule.offer("J-61")
print(schedule.take(), schedule.take(), schedule.take())

Output

Output
False
J-47 J-61 None

Time, space, and tradeoff

The model's successful link and head moves each take O(1) local operations, but loops may retry and there is no bound on one participant's completion time. A proven lock-free implementation argues system-wide progress under its atomic and reclamation assumptions; this sequential Python model proves no such property. Space is O(Q + R) for Q queued nodes and R nodes retained after removal in this model, because it never reclaims nodes. Actual memory reclamation, ABA protection, close semantics, and platform-specific atomic support can dominate an implementation review. Use the condition-protected queue when a working in-process Python buffer is the requirement.

Common Mistakes

  • Do not call a sequence of Python equality checks and assignments atomic CAS.
  • Do not free or recycle a removed node while another participant may still read it.
  • Do not assume moving tail is the insertion linearization point; linking the node makes it reachable.
  • Do not equate lock-free system progress with wait-free completion for each caller.

Connected lessons

Test this contract in the live depot audit project, then check the operations quiz.

data structures
range-query-structures
Storage details