C語言無鎖環形隊列實現：單生產者單消費者模型

編輯：關於C語言

設計背景

環形隊列是高併發場景下常用的無鎖數據結構。本實現採用「單生產者單消費者」（SPSC）模型，利用記憶體屏障與原子操作特性，在單核或特定架構下實現無鎖入隊出隊。

核心數據結構

struct fs_loop_queue {
    void **que;           // 指標陣列，存儲 void* 元素
    size_t head;          // 寫入位置（生產者索引）
    size_t tail;          // 讀取位置（消費者索引）
    size_t max_len;       // 隊列容量（必須是 2 的冪次以優化取模）
    unsigned long script_id; // 擴展標識
};

關鍵算法：索引環繞

使用宏 _pos_add(x, n, max) 實現環繞：

#define _pos_add(x, n, max) x = (x + n) % max

若 max_len 為 2 的冪次，可優化為位運算 x = (x + n) & (max - 1)，效率更高。

入隊操作

fs_bool fs_loop_queue_push(struct fs_loop_queue* que, void* item) {
    if (fs_loop_queue_full(que)) return fs_false; // 滿則失敗
    que->que[que->head] = item;
    _pos_add(que->head, 1, que->max_len);
    return fs_true;
}

出隊操作

void* fs_loop_queue_pop(struct fs_loop_queue* que) {
    if (fs_loop_queue_empty(que)) return NULL; // 空則返回 NULL
    void* item = que->que[que->tail];
    que->que[que->tail] = NULL; // 清空引用，助GC/檢測洩漏
    _pos_add(que->tail, 1, que->max_len);
    return item;
}

滿/空判斷條件

空：head == tail
滿：(head + 1) % max_len == tail

犧牲一個槽位區分滿/空，簡化邏輯。實際可用容量為 max_len - 1。

無鎖條件分析

作者註釋：「這種循環隊列，在 A push B pop 是無鎖的。」成立條件：

單生產者單消費者：只有線程 A 調用 push，線程 B 調用 pop，無多生產者/消費者競爭。
內存可見性：需配合 volatile 或原子操作（C11 atomic），確保編譯器不優化掉對 head/tail 的訪問，CPU 緩存一致性協議（MESI）保證跨核可見。
指針大小原子性：void* 讀寫在目標架構上必須是原子的（現代 32/64 位 CPU 滿足）。

若違反上述條件（如多生產者），需引入鎖或 CAS 原子操作。

記憶體管理

隊列僅管理 void* 指標，不負責元素內存生命週期。
fs_create_loop_queue 分配指標陣列與結構體，fs_loop_queue_free 釋放兩者。
使用自定義 fs_malloc/fs_free 便於內存池整合。

適用場景與局限

優點	局限
極低延遲，無鎖開銷	僅支援 SPSC 模型
記憶體佔用固定，無動態分配抖動	容量固定，無法動態擴容
實現簡潔，易於驗證正確性	元素類型擦除為 void*，類型安全靠自律