摘要：在本例中，講述的無鎖來自于并發(fā)包我們將這個(gè)無鎖的稱為。在這里，我們使用二維數(shù)組來表示的內(nèi)部存儲(chǔ)，如下變量存放所有的內(nèi)部元素。為什么使用二維數(shù)組去實(shí)現(xiàn)一個(gè)一維的呢這是為了將來進(jìn)行動(dòng)態(tài)擴(kuò)展時(shí)可以更加方便。

我們已經(jīng)比較完整得介紹了有關(guān)無鎖的概念和使用方法。相對(duì)于有鎖的方法，使用無鎖的方式編程更加考驗(yàn)一個(gè)程序員的耐心和智力。但是，無鎖帶來的好處也是顯而易見的，第一，在高并發(fā)的情況下，它比有鎖的程序擁有更好的性能；第二，它天生就是死鎖免疫的。就憑借這2個(gè)優(yōu)勢(shì)，就值得我們冒險(xiǎn)嘗試使用無鎖的并發(fā)。

這里，我想向大家介紹一種使用無鎖方式實(shí)現(xiàn)的Vector。通過這個(gè)案例，我們可以更加深刻地認(rèn)識(shí)無鎖的算法，同時(shí)也可以學(xué)習(xí)一下有關(guān)Vector實(shí)現(xiàn)的細(xì)節(jié)和算法技巧。（在本例中，講述的無鎖Vector來自于amino并發(fā)包）

我們將這個(gè)無鎖的Vector稱為LockFreeVector。它的特點(diǎn)是可以根據(jù)需求動(dòng)態(tài)擴(kuò)展其內(nèi)部空間。在這里，我們使用二維數(shù)組來表示LockFreeVector的內(nèi)部存儲(chǔ)，如下：

private final AtomicReferenceArray> buckets;  

變量buckets存放所有的內(nèi)部元素。從定義上看，它是一個(gè)保存著數(shù)組的數(shù)組，也就是通常的二維數(shù)組。特別之處在于這些數(shù)組都是使用CAS的原子數(shù)組。為什么使用二維數(shù)組去實(shí)現(xiàn)一個(gè)一維的Vector呢？這是為了將來Vector進(jìn)行動(dòng)態(tài)擴(kuò)展時(shí)可以更加方便。我們知道，AtomicReferenceArray內(nèi)部使用Object[]來進(jìn)行實(shí)際數(shù)據(jù)的存儲(chǔ)，這使得動(dòng)態(tài)空間增加特別的麻煩，因此使用二維數(shù)組的好處就是為將來增加新的元素。

此外，為了更有序的讀寫數(shù)組，定義一個(gè)稱為Descriptor的元素。它的作用是使用CAS操作寫入新數(shù)據(jù)。

    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構(gòu)造函數(shù)接收2個(gè)參數(shù)，第一個(gè)為整個(gè)Vector的長度，第2個(gè)為一個(gè)writer。最終，寫入數(shù)據(jù)是通過writer進(jìn)行的（通過completeWrite()方法）。第24行，WriteDescriptor的構(gòu)造函數(shù)接收4個(gè)參數(shù)。第一個(gè)參數(shù)addr表示要修改的原子數(shù)組，第二個(gè)參數(shù)為要寫入的數(shù)組索引位置，第三個(gè)oldV為期望值，第4個(gè)newV為需要寫入的值。

在構(gòu)造LockFreeVector時(shí)，顯然需要將buckets和descriptor進(jìn)行初始化。

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,也就是說這個(gè)buckets里面可以存放一共30個(gè)數(shù)組（由于數(shù)組無法動(dòng)態(tài)增長，因此數(shù)組總數(shù)也就不能超過30個(gè)）。并且將第一個(gè)數(shù)組的大小為FIRST_BUCKET_SIZE為8。到這里，大家可能會(huì)有一個(gè)疑問，如果每個(gè)數(shù)組8個(gè)元素，一共30個(gè)數(shù)組，那豈不是一共只能存放240個(gè)元素嗎？

如果大家了解JDK內(nèi)的Vector實(shí)現(xiàn)，應(yīng)該知道，Vector在進(jìn)行空間增長時(shí)，默認(rèn)情況下，每次都會(huì)將總?cè)萘糠?。因此，這里也借鑒類似的思想，每次空間擴(kuò)張，新的數(shù)組的大小為原來的2倍（即每次空間擴(kuò)展都啟用一個(gè)新的數(shù)組），因此，第一個(gè)數(shù)組為8，第2個(gè)就是16，第3個(gè)就是32。以此類推，因此30個(gè)數(shù)組可以支持的總元素達(dá)到。

這數(shù)值已經(jīng)超過了2^33，即在80億以上。因此，可以滿足一般的應(yīng)用。

當(dāng)有元素需要加入LockFreeVector時(shí)，使用一個(gè)名為push_back()的方法，將元素壓入Vector最后一個(gè)位置。這個(gè)操作顯然就是LockFreeVector的最為核心的方法，也是最能體現(xiàn)CAS使用特點(diǎn)的方法，它的實(shí)現(xiàn)如下：

    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();
}

可以看到，這個(gè)方法主體部分是一個(gè)do-while循環(huán)，用來不斷嘗試對(duì)descriptor的設(shè)置。也就是通過CAS保證了descriptor的一致性和安全性。在第23行，使用descriptor將數(shù)據(jù)真正地寫入數(shù)組中。這個(gè)descriptor寫入的數(shù)據(jù)由20~21行構(gòu)造的WriteDescriptor決定。

摘自：實(shí)戰(zhàn)Java高并發(fā)程序設(shè)計(jì)

【實(shí)戰(zhàn)Java高并發(fā)程序設(shè)計(jì)1】Java中的指針：Unsafe類
【實(shí)戰(zhàn)Java高并發(fā)程序設(shè)計(jì)2】無鎖的對(duì)象引用：AtomicReference
【實(shí)戰(zhàn)Java高并發(fā)程序設(shè)計(jì) 3】帶有時(shí)間戳的對(duì)象引用：AtomicStampedReference
【實(shí)戰(zhàn)Java高并發(fā)程序設(shè)計(jì) 4】數(shù)組也能無鎖AtomicIntegerArray
【實(shí)戰(zhàn)Java高并發(fā)程序設(shè)計(jì)5】讓普通變量也享受原子操作