摘要：在本例中，講述的無鎖來自于并發包我們將這個無鎖的稱為。在這里，我們使用二維數組來表示的內部存儲，如下變量存放所有的內部元素。為什么使用二維數組去實現一個一維的呢這是為了將來進行動態擴展時可以更加方便。
我們已經比較完整得介紹了有關無鎖的概念和使用方法。相對于有鎖的方法，使用無鎖的方式編程更加考驗一個程序員的耐心和智力。但是，無鎖帶來的好處也是顯而易見的，第一，在高并發的情況下，它比有鎖的程序擁有更好的性能；第二，它天生就是死鎖免疫的。就憑借這2個優勢，就值得我們冒險嘗試使用無鎖的并發。
這里，我想向大家介紹一種使用無鎖方式實現的Vector。通過這個案例，我們可以更加深刻地認識無鎖的算法，同時也可以學習一下有關Vector實現的細節和算法技巧。（在本例中，講述的無鎖Vector來自于amino并發包）
我們將這個無鎖的Vector稱為LockFreeVector。它的特點是可以根據需求動態擴展其內部空間。在這里，我們使用二維數組來表示LockFreeVector的內部存儲，如下：
private final AtomicReferenceArray> buckets;
變量buckets存放所有的內部元素。從定義上看，它是一個保存著數組的數組，也就是通常的二維數組。特別之處在于這些數組都是使用CAS的原子數組。為什么使用二維數組去實現一個一維的Vector呢？這是為了將來Vector進行動態擴展時可以更加方便。我們知道，AtomicReferenceArray內部使用Object[]來進行實際數據的存儲，這使得動態空間增加特別的麻煩，因此使用二維數組的好處就是為將來增加新的元素。
此外，為了更有序的讀寫數組，定義一個稱為Descriptor的元素。它的作用是使用CAS操作寫入新數據。
static class Descriptor {
public int size;
volatile WriteDescriptor writeop;
public Descriptor(int size, WriteDescriptor writeop) {
this.size = size;
this.writeop = writeop;
}
public void completeWrite() {
WriteDescriptor tmpOp = writeop;
if (tmpOp != null) {
tmpOp.doIt();
writeop = null; // this is safe since all write to writeop use
// null as r_value.
}
}
}
static class WriteDescriptor {
public E oldV;
public E newV;
public AtomicReferenceArray addr;
public int addr_ind;
public WriteDescriptor(AtomicReferenceArray addr, int addr_ind,
E oldV, E newV) {
this.addr = addr;
this.addr_ind = addr_ind;
this.oldV = oldV;
this.newV = newV;
}
public void doIt() {
addr.compareAndSet(addr_ind, oldV, newV);
}
}
上述代碼第4行定義的Descriptor構造函數接收2個參數，第一個為整個Vector的長度，第2個為一個writer。最終，寫入數據是通過writer進行的（通過completeWrite()方法）。第24行，WriteDescriptor的構造函數接收4個參數。第一個參數addr表示要修改的原子數組，第二個參數為要寫入的數組索引位置，第三個oldV為期望值，第4個newV為需要寫入的值。
在構造LockFreeVector時，顯然需要將buckets和descriptor進行初始化。
public LockFreeVector() {
buckets = new AtomicReferenceArray>(N_BUCKET);
buckets.set(0, new AtomicReferenceArray(FIRST_BUCKET_SIZE));
descriptor = new AtomicReference>(new Descriptor(0,
null));
}
在這里N_BUCKET為30,也就是說這個buckets里面可以存放一共30個數組（由于數組無法動態增長，因此數組總數也就不能超過30個）。并且將第一個數組的大小為FIRST_BUCKET_SIZE為8。到這里，大家可能會有一個疑問，如果每個數組8個元素，一共30個數組，那豈不是一共只能存放240個元素嗎？
如果大家了解JDK內的Vector實現，應該知道，Vector在進行空間增長時，默認情況下，每次都會將總容量翻倍。因此，這里也借鑒類似的思想，每次空間擴張，新的數組的大小為原來的2倍（即每次空間擴展都啟用一個新的數組），因此，第一個數組為8，第2個就是16，第3個就是32。以此類推，因此30個數組可以支持的總元素達到。
這數值已經超過了2^33，即在80億以上。因此，可以滿足一般的應用。
當有元素需要加入LockFreeVector時，使用一個名為push_back()的方法，將元素壓入Vector最后一個位置。這個操作顯然就是LockFreeVector的最為核心的方法，也是最能體現CAS使用特點的方法，它的實現如下：
public void push_back(E e) {
Descriptor desc;
Descriptor newd;
do {
desc = descriptor.get();
desc.completeWrite();
int pos = desc.size + FIRST_BUCKET_SIZE;
int zeroNumPos = Integer.numberOfLeadingZeros(pos);
int bucketInd = zeroNumFirst - zeroNumPos;
if (buckets.get(bucketInd) == null) {
int newLen = 2 * buckets.get(bucketInd - 1).length();
if (debug)
System.out.println("New Length is:" + newLen);
buckets.compareAndSet(bucketInd, null,
new AtomicReferenceArray(newLen));
}
int idx = (0x80000000>>>zeroNumPos) ^ pos;
newd = new Descriptor(desc.size + 1, new WriteDescriptor(
buckets.get(bucketInd), idx, null, e));
} while (!descriptor.compareAndSet(desc, newd));
descriptor.get().completeWrite();
}
可以看到，這個方法主體部分是一個do-while循環，用來不斷嘗試對descriptor的設置。也就是通過CAS保證了descriptor的一致性和安全性。在第23行，使用descriptor將數據真正地寫入數組中。這個descriptor寫入的數據由20~21行構造的WriteDescriptor決定。
摘自：實戰Java高并發程序設計
【實戰Java高并發程序設計1】Java中的指針：Unsafe類
【實戰Java高并發程序設計2】無鎖的對象引用：AtomicReference
【實戰Java高并發程序設計 3】帶有時間戳的對象引用：AtomicStampedReference
【實戰Java高并發程序設計 4】數組也能無鎖AtomicIntegerArray
【實戰Java高并發程序設計5】讓普通變量也享受原子操作
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65760.html
