背景
在多線程環境下為了保證線程安全，往往需要加鎖，例如讀寫鎖可以保證讀寫互斥，讀讀不互斥。有沒有一種資料結構能夠實作無鎖的線程安全呢？答案就是使用RingBuffer循環隊列。在Disruptor項目中就運用到了RingBuffer。
RingBuffer基本原理
在RingBuffer中設定了兩個指針，head和tail。head指向下一次讀的位置，tail指向的是下一次寫的位置。RingBuffer可用一個數組進行存儲，數組内元素的記憶體位址是連續的，這是對CPU緩存友好的----也就是說，在硬體級别，數組中的元素是會被預加載的，是以在RingBuffer中，CPU無需時不時去主記憶體加載數組中的下一個元素。通過對head和tail指針的移動，可以實作資料在數組中的環形存取。當head==tail時，說明buffer為空，當head==（tail+1）%bufferSize則說明buffer滿了。
在進行讀操作的時候，我們隻修改head的值，而在寫操作的時候我們隻修改tail的值。在寫操作時，我們在寫入内容到buffer之後才修改tail的值，而在進行讀操作的時候，我們會讀取tail的值并将其指派給copyTail。指派操作是原子操作。是以在讀到copyTail之後，從head到copyTail之間一定是有資料可以讀的，不會出現資料沒有寫入就進行讀操作的情況。同樣的，讀操作完成之後，才會修改head的數值；而在寫操作之前會讀取head的值來判斷是否有空間可以用來寫資料。是以，這時候tail到head-1之間一定是有空間可以寫資料的，而不會出現一個位置的資料還沒有讀出就被寫操作覆寫的情況。這樣就保證了RingBuffer的線程安全性。
import java.util.Arrays;
public class RingBuffer<T> {
private final static int DEFAULT_SIZE = 1024;
private Object[] buffer;
private int head = 0;
private int tail = 0;
private int bufferSize;
public RingBuffer(){
this.bufferSize = DEFAULT_SIZE;
this.buffer = new Object[bufferSize];
}
public RingBuffer(int initSize){
this.bufferSize = initSize;
this.buffer = new Object[bufferSize];
}
private Boolean empty() {
return head == tail;
}
private Boolean full() {
return (tail + 1) % bufferSize == head;
}
public void clear(){
Arrays.fill(buffer,null);
this.head = 0;
this.tail = 0;
}
public Boolean put(String v) {
if (full()) {
return false;
}
buffer[tail] = v;
tail = (tail + 1) % bufferSize;
return true;
}
public Object get() {
if (empty()) {
return null;
}
Object result = buffer[head];
head = (head + 1) % bufferSize;
return result;
}
public Object[] getAll() {
if (empty()) {
return new Object[0];
}
int copyTail = tail;
int cnt = head < copyTail ? copyTail - head : bufferSize - head + copyTail;
Object[] result = new String[cnt];
if (head < copyTail) {
for (int i = head; i < copyTail; i++) {
result[i - head] = buffer[i];
}
} else {
for (int i = head; i < bufferSize; i++) {
result[i - head] = buffer[i];
}
for (int i = 0; i < copyTail; i++) {
result[bufferSize - head + i] = buffer[i];
}
}
head = copyTail;
return result;
}
} 為什麼要有環形緩沖器
當有大量資料的時候，我們不能存儲所有的資料，那麼計算機處理資料的時候，隻能先處理先來的，那麼處理完後呢，就會把資料釋放掉，再處理下一個。那麼，已經處理的資料的記憶體就會被浪費掉。因為後來的資料隻能往後排隊，如果要将剩餘的資料都往前移動一次，那麼效率就會低下了，肯定不現實，是以，環形隊列就出現了。
頻繁的記憶體配置設定不但增加了系統開銷，更使得記憶體碎片不斷增多，非常不利于我們的伺服器長期穩定運作。也許我們可以使用記憶體池，比如SGI STL中附帶的小記憶體配置設定器。但是對于這種按照嚴格的先進先出順序處理的，塊大小并不算小的，而且塊大小也并不統一的記憶體配置設定情況來說，更多使用的是一種叫做環形緩沖區的方案。
區分緩沖區是否為滿的政策
1.總是保持一個存儲單元為空
緩沖區中總是有一個存儲單元保持未使用狀态。緩沖區最多存入（size - 1） 個資料。如果讀寫指針指向同一位置，則緩沖區為空。如果寫指針位于讀指針的相鄰後一個位置，則緩沖區為滿。這種政策的優點是簡單、魯棒；缺點是語義上實際可存資料量與緩沖區容量不一緻，測試緩沖區是否滿需要做取餘數計算。
2.使用資料計數
這種政策不使用顯式的寫指針，而是保持着緩沖區記憶體儲的資料的計數。是以測試緩沖區是空是滿非常簡單；對性能影響可以忽略。缺點是讀寫操作都需要修改這個存儲資料計數，對于多線程通路緩沖區需要并發控制。
3.鏡像訓示位
緩沖區的長度如果是n，邏輯位址空間則為0至n-1；那麼，規定n至2n-1為鏡像邏輯位址空間。本政策規定讀寫指針的位址空間為0至2n-1，其中低半部分對應于正常的邏輯位址空間，高半部分對應于鏡像邏輯位址空間。當指針值大于等于2n時，使其折返（wrapped）到ptr-2n。使用一位表示寫指針或讀指針是否進入了虛拟的鏡像存儲區：置位表示進入，不置位表示沒進入還在基本存儲區。
在讀寫指針的值相同情況下，如果二者的訓示位相同，說明緩沖區為空；如果二者的訓示位不同，說明緩沖區為滿。這種方法優點是測試緩沖區滿/空很簡單；不需要做取餘數操作；讀寫線程可以分别設計專用算法政策，能實作精緻的并發控制。 缺點是讀寫指針各需要額外的一位作為訓示位。