环形缓冲区Ring buffer

在固定容量存储上循环推进读写位置。

读序为 A、B、C、D：索引从 5 回到 0。head 指向下一次读取位置，tail 指向下一次写入位置；此例用一个空槽区分满与空。

常见操作#

C 为固定容量；n 为当前元素数；b 为一次批量复制的元素数。

操作	时间复杂度	条件与说明
入队 / 出队一个元素	$O(1)$	推进读写位置并回绕；满时拒绝、覆盖或等待由调用方约定。
查看空闲量 / 已用量	$O(1)$	维护读写位置，并明确空满判定；并发读到的量可能只是边界估计。
批量读写	$O(b)$	回绕时至多拆成两段；不包含等待数据的时间。
遍历现存数据	$O(n)$	从读位置访问到写位置；并发修改时需额外协议。

固定容量不自动扩容。单生产者单消费者仍需正确的发布顺序与内存屏障。

1 个案例 · 附源码

Linux Kernel·IIO 软件采样缓冲 / kfifov6.12

Linux IIO 的 kfifo 缓冲在采样进入内核与用户态读取之间暂存数据，按先进先出顺序交付采样记录。

附源码片段 · 内存管理

基础原理参考资料

Linux 6.12 · Circular Buffers环形下标、可用空间计算与单生产者单消费者的内存屏障。