Embedded Concurrency Primitives

In this lesson, you will learn how to implement lock-free queues to facilitate safe, low-latency data transfer between tasks of different priority levels in real-time embedded systems.

The Challenge of Priority Inversion

In embedded systems, tasks often operate at different hardware-defined priorities. If a high-priority task needs data from a low-priority task, using a traditional Mutex can lead to priority inversion, where the high-priority task is blocked waiting for a lock held by a low-priority task that has been preempted.

To solve this, we use Single-Producer Single-Consumer (SPSC) lock-free queues. These structures rely on atomic operations to ensure that data can be pushed and popped without ever needing to "sleep" or lock a resource.

Implementing a Lock-Free Circular Buffer

A typical SPSC queue uses a ring buffer with two atomic indices: head (where the producer writes) and tail (where the consumer reads). Because there is only one writer and one reader, we do not need complex compare-and-swap (CAS) loops. We only need memory ordering guarantees (like Acquire and Release) to ensure visibility across CPU cores or privilege levels.

use core::sync::atomic::{AtomicUsize, Ordering};
use core::cell::UnsafeCell;

pub struct SpscQueue<T, const N: usize> {
    buffer: [UnsafeCell<Option<T>>; N],
    head: AtomicUsize,
    tail: AtomicUsize,
}

impl<T, const N: usize> SpscQueue<T, N> {
    pub fn enqueue(&self, item: T) -> Result<(), T> {
        let head = self.head.load(Ordering::Relaxed);
        let next_head = (head + 1) % N;
        
        if next_head == self.tail.load(Ordering::Acquire) {
            return Err(item); // Queue full
        }
        
        unsafe { *self.buffer[head].get() = Some(item); }
        self.head.store(next_head, Ordering::Release);
        Ok(())
    }
}

Why This Works

The Release store on the head index ensures that the data written into the buffer is visible to any task that performs an Acquire load on the head. By using Ordering::Release and Ordering::Acquire, we create a "happens-before" relationship. The high-priority consumer thread can check the head pointer; if it has moved, it knows data is available without ever having to engage the kernel's scheduler or wait for a mutex. This ensures your real-time response times remain deterministic and jitter-free.

Key Takeaway: By using atomic indices with Acquire/Release memory ordering, SPSC queues eliminate locking overhead and priority inversion in high-performance embedded systems.