# 同步，第 8 部分：環形緩沖區示例 > 原文：<https://github.com/angrave/SystemProgramming/wiki/Synchronization%2C-Part-8%3A-Ring-Buffer-Example> ## 什么是環形緩沖區？ 環形緩沖區是一種簡單的，通常是固定大小的存儲機制，其中連續內存被視為圓形，兩個索引計數器跟蹤隊列的當前開始和結束。由于數組索引不是循環的，因此當移過數組末尾時，索引計數器必須回繞到零。當數據被添加（入隊）到隊列的前面或從隊列的尾部移除（出隊）時，緩沖區中的當前項形成一條似乎環繞軌道的列車一個簡單的（單線程）實現如下所示。注意 enqueue 和 dequeue 不會防止下溢或溢出 - 當隊列已滿時可以添加項目，并且當隊列為空時可以刪除項目。例如，如果我們將 20 個整數（1,2,3 ...）添加到隊列中并且沒有使任何項目出列，則值`17,18,19,20`將覆蓋`1,2,3,4`。我們現在不會解決這個問題，相反，當我們創建多線程版本時，我們將確保在環形緩沖區滿或空時分別阻塞入隊和出隊線程。 ```c void *buffer[16]; int in = 0, out = 0; void enqueue(void *value) { /* Add one item to the front of the queue*/ buffer[in] = value; in++; /* Advance the index for next time */ if (in == 16) in = 0; /* Wrap around! */ } void *dequeue() { /* Remove one item to the end of the queue.*/ void *result = buffer[out]; out++; if (out == 16) out = 0; return result; } ``` ## 實現環形緩沖區有什么問題？ 以下面的緊湊形式編寫入隊或出隊方法非常誘人（N 是緩沖區的容量，例如 16）： ```c void enqueue(void *value) b[ (in++) % N ] = value; } ``` 這種方法似乎有效（通過簡單的測試等），但包含一個微妙的 bug。有足夠的入隊操作（超過 20 億），`in`的 int 值將溢出并變為負值！模數（或“余數”）運算符`%`保留符號。因此，您最終可能會寫入`b[-14]`！ 緊湊的形式是正確的使用位屏蔽，只要 N 是 2 ^ x（16,32,64，...） ```c b[ (in++) & (N-1) ] = value; ``` 此緩沖區尚未阻止緩沖區下溢或溢出。為此，我們將轉向我們的多線程嘗試，它將阻塞線程，直到有空間或至少有一個項目要刪除。 ## 檢查多線程實現的正確性（示例 1） 以下代碼是不正確的實現。會發生什么？ `enqueue`和/或`dequeue`會阻塞嗎？相互排斥是否滿足？緩沖區可以下溢嗎？緩沖區可以溢出嗎？為清楚起見，`pthread_mutex`縮短為`p_m`，我們假設 sem_wait 不能被中斷。 ```c #define N 16 void *b[N] int in = 0, out = 0 p_m_t lock sem_t s1,s2 void init() { p_m_init(&lock, NULL) sem_init(&s1, 0, 16) sem_init(&s2, 0, 0) } enqueue(void *value) { p_m_lock(&lock) // Hint: Wait while zero. Decrement and return sem_wait( &s1 ) b[ (in++) & (N-1) ] = value // Hint: Increment. Will wake up a waiting thread sem_post(&s1) p_m_unlock(&lock) } void *dequeue(){ p_m_lock(&lock) sem_wait(&s2) void *result = b[(out++) & (N-1) ] sem_post(&s2) p_m_unlock(&lock) return result } ``` ## 分析 在閱讀之前，看看你能找到多少錯誤。然后確定如果線程調用 enqueue 和 dequeue 方法會發生什么。 * enqueue 方法在同一個信號量（s1）上等待和發布，類似于 equeue 和（s2），即我們遞減值然后立即遞增值，所以在函數結束時信號量值不變！ * s1 的初始值為 16，因此信號量永遠不會減少到零 - 如果環形緩沖區已滿，則 enqueue 不會阻塞 - 因此溢出是可能的。 * s2 的初始值為零，因此對 dequeue 的調用將始終阻塞并且永不返回！ * 需要交換互斥鎖和 sem_wait 的順序（但是這個例子很破壞，這個 bug 沒有效果！）##檢查多線程實現的正確性（例 1） The following code is an incorrect implementation. What will happen? Will `enqueue` and/or `dequeue` block? Is mutual exclusion satisfied? Can the buffer underflow? Can the buffer overflow? For clarity `pthread_mutex` is shortened to `p_m` and we assume sem_wait cannot be interrupted. ```c void *b[16] int in = 0, out = 0 p_m_t lock sem_t s1, s2 void init() { sem_init(&s1,0,16) sem_init(&s2,0,0) } enqueue(void *value){ sem_wait(&s2) p_m_lock(&lock) b[ (in++) & (N-1) ] = value p_m_unlock(&lock) sem_post(&s1) } void *dequeue(){ sem_wait(&s1) p_m_lock(&lock) void *result = b[(out++) & 15] p_m_unlock(&lock) sem_post(&s2) return result; } ``` ### 分析 * s2 的初始值為 0.因此，即使緩沖區為空，enqueue 也會在第一次調用 sem_wait 時阻塞！ * s1 的初始值為 16.因此即使緩沖區為空，dequeue 也不會在第一次調用 sem_wait 時阻塞 - oops 下溢！ dequeue 方法將返回無效數據。 * 該代碼不滿足互斥;兩個線程可以同時修改`in`或`out`！該代碼似乎使用互斥鎖。不幸的是鎖從未用`pthread_mutex_init()`或`PTHREAD_MUTEX_INITIALIZER`初始化 - 所以鎖可能不起作用（`pthread_mutex_lock`可能什么都不做） ## 正確實現環形緩沖區 偽代碼（`pthread_mutex`縮短為`p_m`等）如下所示。 由于互斥鎖存儲在全局（靜態）內存中，因此可以使用`PTHREAD_MUTEX_INITIALIZER`進行初始化。如果我們為堆上的互斥鎖分配了空間，那么我們就會使用`pthread_mutex_init(ptr, NULL)` ```c #include <pthread.h> #include <semaphore.h> // N must be 2^i #define N (16) void *b[N] int in = 0, out = 0 p_m_t lock = PTHREAD_MUTEX_INITIALIZER sem_t countsem, spacesem void init() { sem_init(&countsem, 0, 0) sem_init(&spacesem, 0, 16) } ``` 入隊方法如下所示。注意： * 鎖定僅在關鍵部分（訪問數據結構）期間保持。 * 由于 POSIX 信號，完整的實現需要防止`sem_wait`的早期返回。 ```c enqueue(void *value){ // wait if there is no space left: sem_wait( &spacesem ) p_m_lock(&lock) b[ (in++) & (N-1) ] = value p_m_unlock(&lock) // increment the count of the number of items sem_post(&countsem) } ``` `dequeue`實現如下所示。請注意同步調用`enqueue`的對稱性。在這兩種情況下，如果空格計數或項目數為零，則函數首先等待。 ```c void *dequeue(){ // Wait if there are no items in the buffer sem_wait(&countsem) p_m_lock(&lock) void *result = b[(out++) & (N-1)] p_m_unlock(&lock) // Increment the count of the number of spaces sem_post(&spacesem) return result } ``` ## 值得深思 * 如果交換`pthread_mutex_unlock`和`sem_post`調用的順序會發生什么？ * 如果交換`sem_wait`和`pthread_mutex_lock`調用的順序會發生什么？