介面設計 fs_loop_queue.h
#ifndef FS_LOOP_QUEUE_H
#define FS_LOOP_QUEUE_H
#include "fs_define.h"
struct fs_loop_queue;
struct fs_loop_queue* fs_create_loop_queue(size_t len);
bool fs_loop_queue_push(struct fs_loop_queue*, void* item);
void* fs_loop_queue_pop(struct fs_loop_queue*);
bool fs_loop_queue_full(struct fs_loop_queue*);
bool fs_loop_queue_empty(struct fs_loop_queue*);
void fs_loop_queue_free(struct fs_loop_queue*);
#endif
實現 fs_loop_queue.c
#include <stdio.h>
#include "fs_loop_queue.h"
#include "fs_malloc.h"
struct fs_loop_queue {
void **que; // 元素指標陣列
size_t head; // 寫入位置
size_t tail; // 讀取位置
size_t max_len; // 容量
unsigned long script_id; // 業務標識
};
#define _pos_add(x, n, max) x = (x + n) % max
struct fs_loop_queue* fs_create_loop_queue(size_t len) {
struct fs_loop_queue *q = fs_malloc(sizeof(*q));
fs_zero(q, sizeof(*q));
q->max_len = len;
q->que = fs_malloc(sizeof(void*) * len);
fs_zero(q->que, sizeof(void*) * len);
return q;
}
bool fs_loop_queue_push(struct fs_loop_queue *q, void *item) {
if (fs_loop_queue_full(q)) return false;
q->que[q->head] = item;
_pos_add(q->head, 1, q->max_len);
return true;
}
void* fs_loop_queue_pop(struct fs_loop_queue *q) {
if (fs_loop_queue_empty(q)) return NULL;
void *item = q->que[q->tail];
q->que[q->tail] = NULL;
_pos_add(q->tail, 1, q->max_len);
return item;
}
bool fs_loop_queue_full(struct fs_loop_queue *q) {
return ((q->head + 1) % q->max_len) == q->tail;
}
bool fs_loop_queue_empty(struct fs_loop_queue *q) {
return q->head == q->tail;
}
void fs_loop_queue_free(struct fs_loop_queue *q) {
fs_free(q->que);
fs_free(q);
}
設計亮點與無鎖特性
- 單生產單消費無鎖：
head 僅生產者寫、tail 僅消費者寫，head==tail 判空、(head+1)%cap==tail 判滿，無競態條件（需記憶體屏障/volatile 保證可見性）。
- 浪費一格區分滿空： 犧牲 1 個槽位，避免額外計數器與原子操作。
- 元素型別泛化：
void** 陣列存指標，支援任意型別載荷。
- 自定義記憶體管理：
fs_malloc/fs_free/fs_zero 適配專案記憶體池。
使用範例
struct fs_loop_queue *q = fs_create_loop_queue(1024);
// 生產者執行緒
while (running) {
Task *t = create_task();
while (!fs_loop_queue_push(q, t)) sched_yield(); // 滿則讓權
}
// 消費者執行緒
while (running) {
Task *t = fs_loop_queue_pop(q);
if (t) { process(t); destroy_task(t); }
else sched_yield();
}
擴展方向
- 多生產/多消費：需原子操作
__sync_bool_compare_and_swap 或 mutex 保護 head/tail。
- 批次操作：
push_batch/pop_batch 減少函式呼叫開銷。
- 阻塞版本：結合條件變數/信號量實現
blocking_push/pop。
- 無鎖 MPMC：參考 LCRQ、Boost lockfree queue 等進階演算法。
