下面引用維基百科排抬，來學(xué)習(xí)環(huán)形緩沖區(qū)。

環(huán)形緩沖器

圓形緩沖區(qū)（circular buffer）授段，也稱作圓形隊(duì)列（circular queue）蹲蒲，循環(huán)緩沖區(qū)（cyclic buffer），環(huán)形緩沖區(qū)（ring buffer）侵贵，是一種用于表示一個固定尺寸届搁、頭尾相連的緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)，適合緩存數(shù)據(jù)流。

用法

圓形緩沖區(qū)的一個有用特性是：當(dāng)一個數(shù)據(jù)元素被用掉后卡睦，其余數(shù)據(jù)元素不需要移動其存儲位置宴胧。相反，一個非圓形緩沖區(qū)（例如一個普通的隊(duì)列）在用掉一個數(shù)據(jù)元素后表锻，其余數(shù)據(jù)元素需要向前搬移恕齐。換句話說，圓形緩沖區(qū)適合實(shí)現(xiàn)先進(jìn)先出緩沖區(qū)瞬逊，而非圓形緩沖區(qū)適合后進(jìn)先出緩沖區(qū)显歧。

圓形緩沖區(qū)適合于事先明確了緩沖區(qū)的最大容量的情形。擴(kuò)展一個圓形緩沖區(qū)的容量确镊，需要搬移其中的數(shù)據(jù)士骤。因此一個緩沖區(qū)如果需要經(jīng)常調(diào)整其容量，用鏈表實(shí)現(xiàn)更為合適蕾域。

寫操作覆蓋圓形緩沖區(qū)中未被處理的數(shù)據(jù)在某些情況下是允許的敦间。特別是在多媒體處理時。例如束铭，音頻的生產(chǎn)者可以覆蓋掉聲卡尚未來得及處理的音頻數(shù)據(jù)廓块。

工作過程

一個圓形緩沖區(qū)最初為空并有預(yù)定的長度。例如契沫，這是一個具有七個元素空間的圓形緩沖區(qū)带猴，其中底部的單線與箭頭表示“頭尾相接”形成一個圓形地址空間：

假定1被寫入緩沖區(qū)中部（對于圓形緩沖區(qū)來說，最初的寫入位置在哪里是無關(guān)緊要的）：

再寫入2個元素懈万，分別是2 & 3 — 被追加在1之后：

如果兩個元素被處理拴清，那么是緩沖區(qū)中最老的兩個元素被移除。在本例中会通，1 & 2被移除口予，緩沖區(qū)中只剩下3:

如果緩沖區(qū)中有7個元素，則是滿的：

如果緩沖區(qū)是滿的涕侈，又要寫入新的數(shù)據(jù)沪停，一種策略是覆蓋掉最老的數(shù)據(jù)。此例中裳涛，2個新數(shù)據(jù)— A & B — 寫入木张，覆蓋了3 & 4:

也可以采取其他策略，禁止覆蓋緩沖區(qū)的數(shù)據(jù)端三，采取返回一個錯誤碼或者拋出異常舷礼。
最終，如果從緩沖區(qū)中移除2個數(shù)據(jù)郊闯，不是3 & 4 而是 5 & 6 妻献。因?yàn)?A & B 已經(jīng)覆蓋了3 & 4：

圓形緩沖區(qū)工作機(jī)制

由于計(jì)算機(jī)內(nèi)存是線性地址空間蛛株，因此圓形緩沖區(qū)需要特別的設(shè)計(jì)才可以從邏輯上實(shí)現(xiàn)。

讀指針與寫指針

一般的育拨，圓形緩沖區(qū)需要4個指針：

• 在內(nèi)存中實(shí)際開始位置谨履；
• 在內(nèi)存中實(shí)際結(jié)束位置，也可以用緩沖區(qū)長度代替至朗；
• 存儲在緩沖區(qū)中的有效數(shù)據(jù)的開始位置（讀指針）屉符；
• 存儲在緩沖區(qū)中的有效數(shù)據(jù)的結(jié)尾位置（寫指針）剧浸。

讀指針锹引、寫指針可以用整型值來表示。
下例為一個未滿的緩沖區(qū)的讀寫指針：

下例為一個滿的緩沖區(qū)的讀寫指針：

區(qū)分緩沖區(qū)滿或者空

緩沖區(qū)是滿唆香、或是空嫌变，都有可能出現(xiàn)讀指針與寫指針指向同一位置：

有多種策略用于檢測緩沖區(qū)是滿、或是空.

總是保持一個存儲單元為空

緩沖區(qū)中總是有一個存儲單元保持未使用狀態(tài)躬它。緩沖區(qū)最多存入（size - 1） 個數(shù)據(jù)腾啥。如果讀寫指針指向同一位置，則緩沖區(qū)為空冯吓。如果寫指針位于讀指針的相鄰后一個位置倘待，則緩沖區(qū)為滿。這種策略的優(yōu)點(diǎn)是簡單组贺、魯棒凸舵；缺點(diǎn)是語義上實(shí)際可存數(shù)據(jù)量與緩沖區(qū)容量不一致，測試緩沖區(qū)是否滿需要做取余數(shù)計(jì)算失尖。

使用數(shù)據(jù)計(jì)數(shù)

這種策略不使用顯式的寫指針啊奄，而是保持著緩沖區(qū)內(nèi)存儲的數(shù)據(jù)的計(jì)數(shù)。因此測試緩沖區(qū)是空是滿非常簡單掀潮；對性能影響可以忽略菇夸。缺點(diǎn)是讀寫操作都需要修改這個存儲數(shù)據(jù)計(jì)數(shù)，對于多線程訪問緩沖區(qū)需要并發(fā)控制仪吧。

鏡像指示位

緩沖區(qū)的長度如果是n庄新，邏輯地址空間則為0至n-1；那么薯鼠，規(guī)定n至2n-1為鏡像邏輯地址空間摄咆。本策略規(guī)定讀寫指針的地址空間為0至2n-1，其中低半部分對應(yīng)于常規(guī)的邏輯地址空間人断，高半部分對應(yīng)于鏡像邏輯地址空間吭从。當(dāng)指針值大于等于2n時，使其折返（wrapped）到ptr-2n恶迈。使用一位表示寫指針或讀指針是否進(jìn)入了虛擬的鏡像存儲區(qū)：置位表示進(jìn)入涩金，不置位表示沒進(jìn)入還在基本存儲區(qū)谱醇。

在讀寫指針的值相同情況下，如果二者的指示位相同步做，說明緩沖區(qū)為空副渴；如果二者的指示位不同，說明緩沖區(qū)為滿全度。這種方法優(yōu)點(diǎn)是測試緩沖區(qū)滿/空很簡單煮剧；不需要做取余數(shù)操作；讀寫線程可以分別設(shè)計(jì)專用算法策略将鸵，能實(shí)現(xiàn)精致的并發(fā)控制勉盅。 缺點(diǎn)是讀寫指針各需要額外的一位作為指示位。

如果緩沖區(qū)長度是2的冪顶掉，則本方法可以省略鏡像指示位草娜。如果讀寫指針的值相等，則緩沖區(qū)為空痒筒；如果讀寫指針相差n宰闰，則緩沖區(qū)為滿，這可以用條件表達(dá)式（寫指針 == (讀指針 異或 緩沖區(qū)長度)）來判斷簿透。

#include <stdio.h>

// This approach adds one bit to end and start pointers
// Circular buffer object
typedef struct {
    int size; // maximum number of elements
    int start; // index of oldest element
    int end; // index at which to write new element
    ElemType *elems; // vector of elements
} CircularBuffer;

void cbInit(CircularBuffer *cb, int size) {
    cb->size = size;
    cb->start = 0;
    cb->end = 0;
    cb->elems = (ElemType *)calloc(cb->size, sizeof(ElemType));
}

void cbPrint(CircularBuffer *cb) {
    printf("size = 0x%x, start = %d, end = %d\n", cb->size, cb->start, cb->end);
}

int cbIsFull(CircularBuffer *cb) {
    return cb->end == (cb->start ^ cb->size); // This inverts the most significant bit of 
                                               //start before comparison
}

int cbIsEmpty(CircularBuffer *cb) {
    return cb->end == cb->start;
}

int cbIncr(CircularBuffer *cb, int p) {
    return (p + 1) & (2 * cb->size - 1); // start and end pointers incrementation is done 
                                                        //modulo 2*size
}

void cbWrite(CircularBuffer *cb, ElemType *elem) {
    cb->elems[cb->end & (cb->size - 1)] = *elem;
    if (cbIsFull(cb)) // full, overwrite moves start pointer
        cb->start = cbIncr(cb, cb->start);
    cb->end = cbIncr(cb, cb->end);
}

void cbRead(CircularBuffer *cb, ElemType *elem) {
    *elem = cb->elems[cb->start & (cb->size - 1)];
    cb->start = cbIncr(cb, cb->start);
}

讀/寫 計(jì)數(shù)

用兩個有符號整型變量分別保存寫入移袍、讀出緩沖區(qū)的數(shù)據(jù)數(shù)量。其差值就是緩沖區(qū)中尚未被處理的有效數(shù)據(jù)的數(shù)量老充。這種方法的優(yōu)點(diǎn)是讀線程葡盗、寫線程互不干擾；缺點(diǎn)是需要額外兩個變量蚂维。

記錄最后的操作

使用一位記錄最后一次操作是讀還是寫戳粒。讀寫指針值相等情況下，如果最后一次操作為寫入虫啥，那么緩沖區(qū)是滿的蔚约；如果最后一次操作為讀出，那么緩沖區(qū)是空涂籽。 這種策略的缺點(diǎn)是讀寫操作共享一個標(biāo)志位苹祟，多線程時需要并發(fā)控制。

POSIX優(yōu)化實(shí)現(xiàn)

#include <sys/mman.h>
#include <stdlib.h>
#include <unistd.h>

#define report_exceptional_condition() abort ()

struct ring_buffer {
    void *address;
    unsigned long count_bytes;
    unsigned long write_offset_bytes;
    unsigned long read_offset_bytes;
};

// Warning order should be at least 12 for Linux
void ring_buffer_create (struct ring_buffer *buffer, unsigned long order) {
    char path[] = "/dev/shm/ring-buffer-XXXXXX";
    int file_descriptor;
    void *address;
    int status;
    file_descriptor = mkstemp(path);
    if (file_descriptor < 0)
        report_exceptional_condition();
    status = unlink(path);
    if (status)
        report_exceptional_condition();
    buffer->count_bytes = 1UL << order;
    buffer->write_offset_bytes = 0;
    buffer->read_offset_bytes = 0;
    status = ftruncate(file_descriptor, buffer->count_bytes);
    if (status)
        report_exceptional_condition();
    buffer->address = mmap (NULL, buffer->count_bytes << 1, PROT_NONE,
                            MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
    if (buffer->address == MAP_FAILED)
        report_exceptional_condition();
    address =
        mmap(buffer->address, buffer->count_bytes, PROT_READ | PROT_WRITE,
             MAP_FIXED | MAP_SHARED, file_descriptor, 0);
    if (address != buffer->address)
        report_exceptional_condition();
    address = mmap(buffer->address + buffer->count_bytes,
                   buffer->count_bytes, PROT_READ | PROT_WRITE,
                   MAP_FIXED | MAP_SHARED, file_descriptor, 0);
    if (address != buffer->address + buffer->count_bytes)
        report_exceptional_condition();
    status = close(file_descriptor);
    if (status)
        report_exceptional_condition();
}

void ring_buffer_free(struct ring_buffer *buffer) {
    int status;
    status = munmap(buffer->address, buffer->count_bytes << 1);
    if (status)
        report_exceptional_condition ();
}

void *ring_buffer_write_address(struct ring_buffer *buffer) {
    // void pointer arithmetic is a constraint violation.
    return buffer->address + buffer->write_offset_bytes;
}

void ring_buffer_write_advance(struct ring_buffer *buffer, unsigned long count_bytes) {
    buffer->write_offset_bytes += count_bytes;
}

void *ring_buffer_read_address(struct ring_buffer *buffer) {
    return buffer->address + buffer->read_offset_bytes;
}

void ring_buffer_read_advance(struct ring_buffer *buffer, unsigned long count_bytes) {
    buffer->read_offset_bytes += count_bytes;
    if (buffer->read_offset_bytes >= buffer->count_bytes) {
        // 如果讀指針大于等于緩沖區(qū)長度评雌，那些讀寫指針同時折返回[0, buffer_size]范圍內(nèi)
        buffer->read_offset_bytes -= buffer->count_bytes;
        buffer->write_offset_bytes -= buffer->count_bytes;
    }
}

unsigned long ring_buffer_count_bytes(struct ring_buffer *buffer) {
    return buffer->write_offset_bytes - buffer->read_offset_bytes;
}

unsigned long ring_buffer_count_free_bytes(struct ring_buffer *buffer) {
    return buffer->count_bytes - ring_buffer_count_bytes (buffer);
}

void ring_buffer_clear(struct ring_buffer *buffer) {
    buffer->write_offset_bytes = 0;
    buffer->read_offset_bytes = 0;
}

/*  Note, that initial anonymous mmap() can be avoided - after initial mmap() for descriptor fd,
    you can try mmap() with hinted address as (buffer->address + buffer->count_bytes) and if it fails -
    another one with hinted address as (buffer->address - buffer->count_bytes).
    Make sure MAP_FIXED is not used in such case, as under certain situations it could end with segfault.
    The advantage of such approach is, that it avoids requirement to map twice the amount you need initially
    (especially useful e.g. if you want to use hugetlbfs and the allowed amount is limited)
    and in context of gcc/glibc - you can avoid certain feature macros
    (MAP_ANONYMOUS usually requires one of: _BSD_SOURCE, _SVID_SOURCE or _GNU_SOURCE). */

Linux內(nèi)核的kfifo

在Linux內(nèi)核文件kfifo.h和kfifo.c中树枫，定義了一個先進(jìn)先出圓形緩沖區(qū)實(shí)現(xiàn)。如果只有一個讀線程景东、一個寫線程砂轻，二者沒有共享的被修改的控制變量，那么可以證明這種情況下不需要并發(fā)控制斤吐。kfifo就滿足上述條件搔涝。kfifo要求緩沖區(qū)長度必須為2的冪厨喂。讀庄呈、寫指針分別是無符號整型變量蜕煌。把讀寫指針變換為緩沖區(qū)內(nèi)的索引值，僅需要“按位與”操作：（指針值 按位與 （緩沖區(qū)長度-1））诬留。這避免了計(jì)算代價高昂的“求余”操作斜纪。且下述關(guān)系總是成立：

讀指針 + 緩沖區(qū)存儲的數(shù)據(jù)長度 == 寫指針

即使在寫指針達(dá)到了無符號整型的上界，上溢出后寫指針的值小于讀指針的值文兑，上述關(guān)系仍然保持成立（這是因?yàn)闊o符號整型加法的性質(zhì)）盒刚。 kfifo的寫操作，首先計(jì)算緩沖區(qū)中當(dāng)前可寫入存儲空間的數(shù)據(jù)長度：

len = min{待寫入數(shù)據(jù)長度, 緩沖區(qū)長度 - （寫指針 - 讀指針）}

然后彩届，分兩段寫入數(shù)據(jù)伪冰。第一段是從寫指針開始向緩沖區(qū)末尾方向誓酒；第二段是從緩沖區(qū)起始處寫入余下的可寫入數(shù)據(jù)樟蠕，這部分可能數(shù)據(jù)長度為0即并無實(shí)際數(shù)據(jù)寫入。