Cam's Cyberspace

Recent Notes

Circular Queue

6 min read

Overview

A circular queue (ring buffer) is a bounded FIFO implemented on a fixed-size array where the head and tail indices advance modulo the capacity. This yields O(1) enqueue and dequeue with predictable memory usage and steady cache locality—ideal for embedded systems, device drivers, real-time pipelines, and producer–consumer handoffs.

Unlike dynamically growing queues, a circular queue never reallocates; instead, it enforces a policy when full: reject, block, or overwrite the oldest element. Correctness hinges on unambiguous full/empty detection, careful boundary handling, and, in concurrent settings, memory ordering and single-producer/single-consumer discipline.

Structure Definition

  • Storage: array Q[0..N-1].
  • Indices: integers head, tail in [0, N-1].
  • Empty vs full: common patterns
    • Reserved slot (capacity N-1):
      • empty ↔ head == tail
      • full ↔ (tail + 1) % N == head
      • Simple logic; loses one slot of capacity.
    • Counted (capacity N): track size and treat head == tail as both empty and full distinguished by size. Slightly more bookkeeping.

Notation: Arrays are 0-indexed; wrap with x = (x + 1) % N.

Core Operations

Below uses the reserved-slot design (capacity N-1) because it simplifies full/empty detection and avoids ambiguous head == tail.

Enqueue (No-Overwrite)

function ENQ(Q, head, tail, x):  // returns (ok, head, tail)
    next_tail = (tail + 1) % N
    if next_tail == head:
        return (false, head, tail)     // full
    Q[tail] = x
    tail = next_tail
    return (true, head, tail)

Dequeue

function DEQ(Q, head, tail):  // returns (ok, value, head, tail)
    if head == tail:
        return (false, ⊥, head, tail)  // empty
    x = Q[head]
    head = (head + 1) % N
    return (true, x, head, tail)

Enqueue (Overwrite-Oldest Policy)

When full, drop the oldest element by advancing head.

function ENQ_OVERWRITE(Q, head, tail, x):  // returns (overwrote, head, tail)
    next_tail = (tail + 1) % N
    overwrote = (next_tail == head)
    if overwrote:
        head = (head + 1) % N            // lose oldest
    Q[tail] = x
    tail = next_tail
    return (overwrote, head, tail)

Peek / Front

function PEEK(Q, head, tail):  // returns (ok, value)
    if head == tail:
        return (false, ⊥)
    return (true, Q[head])

Size (Reserved-Slot)

function SIZE(head, tail):
    if tail >= head:
        return tail - head
    else:
        return N - (head - tail)

Tip

Maintain reserved-slot for simpler invariants in latency-sensitive paths. Use counted capacity only when the extra slot is essential and the additional logic is acceptable.

Example (Stepwise)

Let N = 8, initial head = 0, tail = 0 (empty). Enqueue A, B, C, D, E, F, G:

  1. ENQ A: Q[0]=A, tail=1

  2. ENQ B: Q[1]=B, tail=2

  3. …

  4. ENQ G: Q[6]=G, tail=7

Now size is 7; since reserved-slot design holds, full occurs when (tail+1)%8 == head i.e., 7+1 ≡ 0 == head—true—so the next ENQ without overwrite fails.

  • DEQ twice → remove A at 0 (head=1), B at 1 (head=2).

  • ENQ H and I → write at 7 (tail=0 wrap) then at 0 (tail=1), maintaining FIFO order with wrap-around.

For overwrite mode, if full before ENQ X, advancing head first discards the oldest and admits X with fixed latency.

Complexity and Performance

OperationTimeSpaceNotes
EnqueueO(1)O(N)Wrap with modulo; may reject or overwrite when full
DequeueO(1)O(N)Returns oldest
PeekO(1)O(N)No mutation
Size (calc)O(1)O(1)Formula above; or maintain a counter
Memory—O(N)Fixed, cache-friendly array

  • Predictable latency: constant-time pointer arithmetic only; excellent for real-time/embedded.

  • Locality: contiguous storage improves cache hit rate over linked queues.

Implementation Notes or Trade-offs

Full/Empty Policy

  • No-overwrite: preserves all data; producer must block, drop, or signal backpressure on full.

  • Overwrite-oldest: favors latest data with constant forward progress; common for telemetry streams. Document the policy explicitly.

Reserved Slot vs Counted

  • Reserved slot (capacity N-1): simplest invariants; faster fast path; one slot lost.

  • Counted (size field): true capacity N, but extra reads/writes and more complex concurrency.

Modulo Arithmetic

  • Use tail = tail + 1; if tail == N: tail = 0 to avoid % on hot paths if the compiler/hardware doesn’t optimize %.

  • For power-of-two capacities, x & (N-1) is equivalent to x % N.

Concurrency & ISR-Safe Pattern (SPSC)

  • Single Producer / Single Consumer (SPSC) rings are naturally lock-free:

    • Producer exclusively updates tail and writes Q[tail].

    • Consumer exclusively updates head and reads Q[head].

    • Use the reserved-slot rule for simple full/empty checks.

    • Insert store-release on producer’s tail update and load-acquire on consumer’s tail read (and vice versa for head) to prevent reordering on weakly ordered CPUs.

  • ISR-safe example: Producer runs in an interrupt service routine; consumer in the main loop. Ensure head/tail are volatile (or atomic) and that critical sections are minimal to meet ISR timing.

Multi-Producer / Multi-Consumer

  • SPSC is straightforward. MPSC/MCSP/MPMC require additional synchronization (CAS, tickets, or per-producer slots). Prefer queues designed specifically for MPMC if needed.

Testing & Verification (Boundary Conditions)

  • Empty: head == tail; DEQ returns empty; PEEK returns empty.

  • Full: (tail + 1) % N == head (reserved-slot).

  • Wrap-around: Enqueue to tail == N-1 then ensure tail → 0. Dequeue to head == N-1 then head → 0.

  • Off-by-one: Fill to size = N-1, then verify next ENQ fails (no-overwrite) or overwrites (overwrite mode).

  • Interleaving (SPSC): Alternate ENQ/DEQ near boundaries repeatedly.

  • Overwrite policy: Verify oldest element is discarded and queue remains consistent.

  • Concurrency ordering: Stress on weakly ordered platforms with memory fences enabled.

Tip

For traceability, expose a watermark (max observed size) and dropped/overwritten counters to tune capacity and detect pressure.

Practical Use Cases

  • Embedded drivers and DSP pipelines: Capture ISR-produced samples to a main-loop consumer with bounded latency.

  • Telemetry and logging: Overwrite-oldest rings to prefer the latest observations under bursts.

  • Audio/video buffers: Steady-rate producers/consumers with small jitter tolerance.

  • Networking and IO queues: Bounded staging between DMA/interrupt handlers and application threads.

Limitations / Pitfalls

Warning

Ambiguous full/empty without a policy. If head == tail and you don’t track size or reserve a slot, the state is ambiguous; choose one method and keep it consistent.

Warning

Overwrite surprises. Overwrite-oldest changes semantics: consumers may miss data. Document this behavior, export “overwritten count,” and select per-use-case.

Warning

Blocking producers. In no-overwrite mode, decide whether to block, drop, or signal backpressure; otherwise producers may livelock.

Warning

Concurrency without fences. On weakly ordered CPUs, missing acquire/release barriers can reorder head/tail with data, causing stale or torn reads.

Summary

Circular queues implement a bounded, array-backed FIFO with wrap-around indices for O(1) operations and predictable performance. The key design choices are full/empty policy (no-overwrite vs overwrite-oldest), reserved-slot vs counted capacity, and, in concurrent or ISR contexts, SPSC discipline with proper memory ordering. With careful boundary handling and a clear policy, ring buffers are robust, cache-friendly building blocks for real-time and systems programming.

See also

Graph View

Backlinks