環形緩衝區

圆形缓冲区（circular buffer），也称作圆形队列（circular queue），循环缓冲区（cyclic buffer），环形缓冲区（ring buffer），是一种用于表示一个固定尺寸、头尾相连的缓冲区的数据结构，适合缓存数据流。

用法

圆形缓冲区的一个有用特性是：当一个数据元素被用掉后，其余数据元素不需要移动其存储位置。相反，一个非圆形缓冲区（例如一个普通的队列）在用掉一个数据元素后，其余数据元素需要向前搬移。换句话说，圆形缓冲区适合实现先进先出缓冲区，而非圆形缓冲区适合后进先出缓冲区。  

圆形缓冲区适合于事先明确了缓冲区的最大容量的情形。扩展一个圆形缓冲区的容量，需要搬移其中的数据。因此一个缓冲区如果需要经常调整其容量，用链表实现更为合适。 
写操作覆盖圆形缓冲区中未被处理的数据在某些情况下是允许的。特别是在多媒体处理时。例如，音频的生产者可以覆盖掉声卡尚未来得及处理的音频数据。

圆形缓冲区工作机制

由于计算机内存是线性地址空间，因此圆形缓冲区需要特别的设计才可以从逻辑上实现。

总是保持一个存储单元为空

缓冲区中总是有一个存储单元保持未使用状态。缓冲区最多存入个数据。如果读写指针指向同一位置，则缓冲区为空。如果写指针位于读指针的相邻后一个位置，则缓冲区为满。这种策略的优点是简单、粗暴；缺点是语义上实际可存数据量与缓冲区容量不一致，测试缓冲区是否满需要做取余数计算。

使用数据计数

这种策略不使用显式的写指针，而是保持着缓冲区内存储的数据的计数。因此测试缓冲区是空是满非常简单；对性能影响可以忽略。缺点是读写操作都需要修改这个存储数据计数，对于多线程访问缓冲区需要并发控制。

镜像指示位

缓冲区的长度如果是n，逻辑地址空间则为0至n-1；那么，规定n至2n-1为镜像逻辑地址空间。本策略规定读写指针的地址空间为0至2n-1，其中低半部分对应于常规的逻辑地址空间，高半部分对应于镜像逻辑地址空间。当指针值大于等于2n时，使其折返（wrapped）到ptr-2n。使用一位表示写指针或读指针是否进入了虚拟的镜像存储区：置位表示进入，不置位表示没进入还在基本存储区。
在读写指针的值相同情况下，如果二者的指示位相同，说明缓冲区为空；如果二者的指示位不同，说明缓冲区为满。这种方法优点是测试缓冲区满/空很简单；不需要做取余数操作；读写线程可以分别设计专用算法策略，能实现精致的并发控制。 缺点是读写指针各需要额外的一位作为指示位。  
如果缓冲区长度是2的幂，则本方法可以省略镜像指示位。如果读写指针的值相等，则缓冲区为空；如果读写指针相差n，则缓冲区为满，这可以用条件表达式（写指针== (读指针异或 缓冲区长度)）来判断。
 1 // This approach adds one bit to end and start pointers 2 // Circular buffer object 3 typedef struct { 4     int size; // maximum number of elements 5     int start; // index of oldest element 6     int end; // index at which to write new element 7     ElemType *elems; // vector of elements 8 } CircularBuffer; 9 10 void cbInit(CircularBuffer *cb, int size) {11     cb->size = size;12     cb->start = 0;13     cb->end = 0;14     cb->elems = (ElemType *)calloc(cb->size, sizeof(ElemType));15 }16 17 void cbPrint(CircularBuffer *cb) {18     printf("size = 0x%x, start = %d, end = %d\n", cb->size, cb->start, cb->end);19 }20 21 int cbIsFull(CircularBuffer *cb) {22     return cb->end == (cb->start ^ cb->size); // This inverts the most significant bit of start before comparison23 }24 25 int cbIsEmpty(CircularBuffer *cb) {26     return cb->end == cb->start;27 }28 29 int cbIncr(CircularBuffer *cb, int p) {30     return (p + 1) & (2 * cb->size - 1); // start and end pointers incrementation is done modulo 2*size31 }32 33 void cbWrite(CircularBuffer *cb, ElemType *elem) {34     cb->elems[cb->end & (cb->size - 1)] = *elem;35     if (cbIsFull(cb)) // full, overwrite moves start pointer36         cb->start = cbIncr(cb, cb->start);37     cb->end = cbIncr(cb, cb->end);38 }39 40 void cbRead(CircularBuffer *cb, ElemType *elem) {41     *elem = cb->elems[cb->start & (cb->size - 1)];42     cb->start = cbIncr(cb, cb->start);43 }

读/写 计数

用两个有符号整型变量分别保存写入、读出缓冲区的数据数量。其差值就是缓冲区中尚未被处理的有效数据的数量。这种方法的优点是读线程、写线程互不干扰；缺点是需要额外两个变量。

记录最后的操作

使用一位记录最后一次操作是读还是写。读写指针值相等情况下，如果最后一次操作为写入，那么缓冲区是满的；如果最后一次操作为读出，那么缓冲区是空。 这种策略的缺点是读写操作共享一个标志位，多线程时需要并发控制。

POSIX优化实现

1 #include <sys/mman.h>  2 #include <stdlib.h>  3 #include <unistd.h>  4   5 #define report_exceptional_condition() abort ()  6   7 struct ring_buffer {  8     void *address;  9     unsigned long count_bytes; 10     unsigned long write_offset_bytes; 11     unsigned long read_offset_bytes; 12 }; 13  14 // Warning order should be at least 12 for Linux 15 void ring_buffer_create (struct ring_buffer *buffer, unsigned long order) { 16     char path[] = "/dev/shm/ring-buffer-XXXXXX"; 17     int file_descriptor; 18     void *address; 19     int status; 20     file_descriptor = mkstemp(path); 21     if (file_descriptor < 0) 22         report_exceptional_condition(); 23     status = unlink(path); 24     if (status) 25         report_exceptional_condition(); 26     buffer->count_bytes = 1UL << order; 27     buffer->write_offset_bytes = 0; 28     buffer->read_offset_bytes = 0; 29     status = ftruncate(file_descriptor, buffer->count_bytes); 30     if (status) 31         report_exceptional_condition(); 32     buffer->address = mmap (NULL, buffer->count_bytes << 1, PROT_NONE, 33                             MAP_ANONYMOUS | MAP_PRIVATE, -1, 0); 34     if (buffer->address == MAP_FAILED) 35         report_exceptional_condition(); 36     address = 37         mmap(buffer->address, buffer->count_bytes, PROT_READ | PROT_WRITE, 38              MAP_FIXED | MAP_SHARED, file_descriptor, 0); 39     if (address != buffer->address) 40         report_exceptional_condition(); 41     address = mmap(buffer->address + buffer->count_bytes, 42                    buffer->count_bytes, PROT_READ | PROT_WRITE, 43                    MAP_FIXED | MAP_SHARED, file_descriptor, 0); 44     if (address != buffer->address + buffer->count_bytes) 45         report_exceptional_condition(); 46     status = close(file_descriptor); 47     if (status) 48         report_exceptional_condition(); 49 } 50  51 void ring_buffer_free(struct ring_buffer *buffer) { 52     int status; 53     status = munmap(buffer->address, buffer->count_bytes << 1); 54     if (status) 55         report_exceptional_condition (); 56 } 57  58 void *ring_buffer_write_address(struct ring_buffer *buffer) { 59     // void pointer arithmetic is a constraint violation. 60     return buffer->address + buffer->write_offset_bytes; 61 } 62  63 void ring_buffer_write_advance(struct ring_buffer *buffer, unsigned long count_bytes) { 64     buffer->write_offset_bytes += count_bytes; 65 } 66  67 void *ring_buffer_read_address(struct ring_buffer *buffer) { 68     return buffer->address + buffer->read_offset_bytes; 69 } 70  71 void ring_buffer_read_advance(struct ring_buffer *buffer, unsigned long count_bytes) { 72     buffer->read_offset_bytes += count_bytes; 73     if (buffer->read_offset_bytes >= buffer->count_bytes) { 74         // 如果读指针大于等于缓冲区长度，那些读写指针同时折返回[0, buffer_size]范围内 75         buffer->read_offset_bytes -= buffer->count_bytes; 76         buffer->write_offset_bytes -= buffer->count_bytes; 77     } 78 } 79  80 unsigned long ring_buffer_count_bytes(struct ring_buffer *buffer) { 81     return buffer->write_offset_bytes - buffer->read_offset_bytes; 82 } 83  84 unsigned long ring_buffer_count_free_bytes(struct ring_buffer *buffer) { 85     return buffer->count_bytes - ring_buffer_count_bytes (buffer); 86 } 87  88 void ring_buffer_clear(struct ring_buffer *buffer) { 89     buffer->write_offset_bytes = 0; 90     buffer->read_offset_bytes = 0; 91 } 92  93 /*  Note, that initial anonymous mmap() can be avoided - after initial mmap() for descriptor fd, 94     you can try mmap() with hinted address as (buffer->address + buffer->count_bytes) and if it fails - 95     another one with hinted address as (buffer->address - buffer->count_bytes). 96     Make sure MAP_FIXED is not used in such case, as under certain situations it could end with segfault. 97     The advantage of such approach is, that it avoids requirement to map twice the amount you need initially 98     (especially useful e.g. if you want to use hugetlbfs and the allowed amount is limited) 99     and in context of gcc/glibc - you can avoid certain feature macros100     (MAP_ANONYMOUS usually requires one of: _BSD_SOURCE, _SVID_SOURCE or _GNU_SOURCE). */