[转载] 环形缓冲区（Circular Buffer）

2026-07-14

原文出处： https://en.wikipedia.org/wiki/Circular_buffer
许可协议： 原文基于 Creative Commons Attribution-ShareAlike 4.0 License 发布。本文为其中文翻译，所有权利归原文作者及 Wikimedia 基金会所有。

环形缓冲区的概念示意图——一个环形结构 — 环形示意图，从概念上展示环形缓冲区。此图直观地表明缓冲区没有真正的终点，可以绕环循环。但由于内存物理上永远不会被创建为环形，通常使用线性表示，如下文所示。

环形缓冲区（英文 circular buffer，也称为 circular queue、cyclic buffer 或 ring buffer）是计算机科学中的一种数据结构，使用单个固定大小的缓冲区，并将其视为首尾相连。这种结构天然适合于缓冲数据流。早期的硬件实现已经存在。

概述

24字节键盘环形缓冲区的动画演示 — 一个 24 字节的键盘环形缓冲区。当写指针即将追上读指针时——因为微处理器未响应——缓冲区停止记录按键。在某些计算机上，此时会发出蜂鸣声。

环形缓冲区从空状态开始，具有固定的长度。以下示例使用一个 7 元素缓冲区，分步演示其运作过程：

缓冲区状态	操作说明
	初始状态：缓冲区为空，尚未存入任何元素
	写入元素 1：将第一个元素存入缓冲区（起始位置任意）
	添加 2 和 3：在 1 之后继续写入两个新元素
	移除两个元素：最先进入的 1 和 2 被移除，缓冲区中只剩 3
	缓冲区填满：继续写入直至 7 个槽位全部占满
	覆盖旧数据：缓冲区已满后继续写入 A 和 B，覆盖最旧的 3 和 4
	再次移除：移除两个元素时，被移除的是当前最旧的 5 和 6（而非 A 和 B）

环形缓冲区使用 FIFO（先进先出） 逻辑——先进入的元素先被移除。
移除操作仅将读指针向前移动，被移除的元素仍留在内存中，直到后续写入将其覆盖。
当缓冲区已满且有新数据写入时，默认行为是覆盖最旧的数据；但程序也可以选择阻止覆盖，返回错误或抛出异常。具体采用哪种方式取决于缓冲区实现的语义或应用需求。

用途

环形缓冲区的一个关键优势是：当元素被消费时，不需要移动其他元素。非环形缓冲区则需要将所有元素移位。环形缓冲区非常适合用作 FIFO 缓冲区，而标准线性缓冲区则适用于 LIFO（后进先出）使用场景。

环形缓冲区为具有固定最大长度的队列提供了出色的实现策略。如果采用了最大长度限制，环形缓冲区是理想选择——所有队列操作都在常数时间内完成。然而，扩展环形缓冲区需要内存搬移，代价相对较高。对于需要任意增长的队列，链表可能更合适。

带覆盖机制的环形缓冲区在多媒体中有其用途。在生产者-消费者问题中，如果消费者（例如声卡）暂时落后，可能希望生产者（例如音频生成器）覆盖旧数据。LZ77 系列无损压缩算法假设最近出现过的字符串更有可能再次出现；其实现将最近的数据存储在环形缓冲区中。

环形缓冲区机制

环形缓冲区的硬件实现专利示意图 — 环形缓冲区的硬件实现，美国专利 3979733 图 4

环形缓冲区可以用一个指针和四个整数实现：

缓冲区在内存中的起始地址
缓冲区容量（长度）
“写入到"缓冲区索引（尾端）
“从"缓冲区读取索引（首端）

部分填充的缓冲区（长度 = 7）：

满缓冲区，四个元素已被覆盖（1 至 4）：

初始时，尾端和首端索引都为 0。写操作将元素放入尾端索引处，然后将尾端索引加一。读操作从首端索引处取出元素，然后将首端索引加一。

仅靠首端和尾端索引无法在使用全部缓冲区槽位时区分满状态和空状态，但如果将最大在用大小限制为"长度 − 1”，则可以区分。在这种方法中，当首端和尾端索引相等时缓冲区为空，当在用大小达到"长度 − 1"时缓冲区为满。另一种解决方案是使用一个单独的计数整数，写时递增，读时递减；计数为 0 表示空，计数等于长度表示满。

以下是环形缓冲区的多语言实现：

C C++ Python Rust

#include <stdio.h>

enum { N = 10 };  // 环形缓冲区的大小

int buffer[N]; // 注意：任意时刻最多只能存储 (N - 1) 个元素
int writeIndx = 0;
int readIndx  = 0;

int put (int item)
{
  if ((writeIndx + 1) % N == readIndx)
  {
     // 缓冲区已满，避免溢出
     return 0;
  }
  buffer[writeIndx] = item;
  writeIndx = (writeIndx + 1) % N;
  return 1;
}

int get (int * value)
{
  if (readIndx == writeIndx)
  {
     // 缓冲区为空
     return 0;
  }

  *value = buffer[readIndx];
  readIndx = (readIndx + 1) % N;
  return 1;
}

int main ()
{
  // 测试环形缓冲区
  int value = 1001;
  while (put (value ++));
  while (get (& value))
     printf ("read %d\n", value);
  return 0;
}

#include <iostream>
#include <array>

template <typename T, size_t N>
class CircularBuffer {
private:
    std::array<T, N> buffer{};
    size_t writeIndx = 0;
    size_t readIndx  = 0;

public:
    bool put(const T& item) {
        if ((writeIndx + 1) % N == readIndx)
            return false; // buffer full
        buffer[writeIndx] = item;
        writeIndx = (writeIndx + 1) % N;
        return true;
    }

    bool get(T& value) {
        if (readIndx == writeIndx)
            return false; // buffer empty
        value = buffer[readIndx];
        readIndx = (readIndx + 1) % N;
        return true;
    }
};

int main() {
    CircularBuffer<int, 10> cb;
    int value = 1001;
    while (cb.put(value++));
    while (cb.get(value))
        std::cout << "read " << value << '\n';
    return 0;
}

class CircularBuffer:
    def __init__(self, size: int = 10):
        self.buffer = [None] * size
        self.size = size
        self.write_idx = 0
        self.read_idx = 0

    def put(self, item) -> bool:
        if (self.write_idx + 1) % self.size == self.read_idx:
            return False  # buffer full
        self.buffer[self.write_idx] = item
        self.write_idx = (self.write_idx + 1) % self.size
        return True

    def get(self):
        if self.read_idx == self.write_idx:
            return None  # buffer empty
        value = self.buffer[self.read_idx]
        self.read_idx = (self.read_idx + 1) % self.size
        return value


if __name__ == '__main__':
    cb = CircularBuffer()
    value = 1001
    while cb.put(value):
        value += 1
    while (v := cb.get()) is not None:
        print(f"read {v}")

const N: usize = 10; // 环形缓冲区的大小

struct CircularBuffer {
    // 注意：任意时刻最多只能存储 (N - 1) 个元素
    buffer: [Option<i32>; N],
    write_idx: usize,
    read_idx: usize,
}

impl CircularBuffer {
    fn new() -> Self {
        CircularBuffer {
            buffer: [const { None }; N],
            write_idx: 0,
            read_idx: 0,
        }
    }

    fn put(&mut self, item: i32) -> bool {
        if (self.write_idx + 1) % N == self.read_idx {
            return false; // 缓冲区已满，避免溢出
        }
        self.buffer[self.write_idx] = Some(item);
        self.write_idx = (self.write_idx + 1) % N;
        true
    }

    fn get(&mut self) -> Option<i32> {
        if self.read_idx == self.write_idx {
            return None; // 缓冲区为空
        }
        let value = self.buffer[self.read_idx].take();
        self.read_idx = (self.read_idx + 1) % N;
        value
    }
}

fn main() {
    let mut cb = CircularBuffer::new();
    let mut value = 1001;
    while cb.put(value) {
        value += 1;
    }
    while let Some(v) = cb.get() {
        println!("read {}", v);
    }
}

put() 函数存储一个元素，成功返回 true，缓冲区满则返回 false（C 中为 1/0）。get() 函数取出一个元素，成功返回 true，缓冲区空则返回 false（C 中通过指针参数传出值，Python 和 Rust 中返回 None/Option::None）。

优化

一种优化实现是将底层缓冲区映射到两个连续的虚拟内存区域。当然，缓冲区的长度必须是系统页面大小的整数倍。这样，读写操作可以更高效地使用直接内存访问（DMA）；当访问超出第一个虚拟内存区域时，会自动回绕到缓冲区的起始位置。当读取偏移量进入第二个区域时，读取和写入偏移量都减去底层缓冲区的长度。

固定长度元素与连续块环形缓冲区

最常见的版本使用 8 位字节作为元素。

一些实现使用更大的固定长度元素——16 位整数用于音频缓冲区，53 字节 ATM 信元用于电信缓冲区，等等。每个元素是连续的且具有适当的数据对齐，与非连续、非对齐的值相比，可以实现更快的软件访问。

乒乓缓冲（Ping-pong buffering）可以看作是一种高度特化的环形缓冲区，它恰好包含两个大的固定长度元素。

bip buffer（bipartite buffer，二分缓冲区）类似于环形缓冲区，但始终返回可变长度的连续内存块。它几乎具有环形缓冲区的所有效率优势，同时支持需要连续内存块的 API。

固定大小的压缩环形缓冲区使用基于初等数论的索引策略，来维护整个数据序列的固定大小压缩表示。

参考文献

本文引用了 10 份来源：

Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), Operating Systems: Three Easy Pieces (PDF)
Hartl, Johann (2011). Impulse repeater telephone exchange video on YouTube
Fraser, Alexander Gibson. US patent 3979733 “Digital data communications system packet switch”
Liu, Z.; Wu, F.; Das, S.K. (2021). Wireless Algorithms, Systems, and Applications (Springer)
Chandrasekaran, Siddharth (2014). “Implementing Circular/Ring Buffer in Embedded C” (EmbedJournal)
Circular buffers documentation (kernel.org)
Morin, Pat. “ArrayQueue: An Array-Based Queue” (Open Data Structures)
Mike Ash (2012). “Friday Q&A: Ring Buffers and Mirrored Memory” (mikeash.com)
Simon Cooke (2003). “The Bip Buffer - The Circular Buffer with a Twist” (CodeProject)
Gunther, John C. (2014). “Algorithm 938: Compressing circular buffers” (ACM Transactions on Mathematical Software)

外部链接

CircularBuffer at the Portland Pattern Repository (wiki.c2.com)
Boost: Templated Circular Buffer Container and Synchronized Bounded Queue
Circular buffers in the Linux kernel (kernel.org)
Circular buffers in DSP (dspguide.com)
Circular queue in C (martinbroadhurst.com, archived)

原文分类：Computer memory, Arrays
原文最后编辑于 2026 年 6 月 29 日。原文基于 Creative Commons Attribution-ShareAlike 4.0 License 发布。