無 鎖 算法 詳 解
無 鎖 的Vector 實現(xiàn)：
參照著JDK中的 Vector 源碼
1、Vector中的 add 方法的實現(xiàn)，它是一個同步方法，所以保證了每一次只能又一個值對數(shù)組 elementData 進(jìn)行操作。
protected Object[] elementData; 通過數(shù)據(jù)來實現(xiàn)存儲
protected int elementCount; 記錄對這個Vector的操作數(shù)

十余年的福貢網(wǎng)站建設(shè)經(jīng)驗，針對設(shè)計、前端、開發(fā)、售后、文案、推廣等六對一服務(wù)，響應(yīng)快，48小時及時工作處理。營銷型網(wǎng)站的優(yōu)勢是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動調(diào)整福貢建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計，從而大程度地提升瀏覽體驗。成都創(chuàng)新互聯(lián)公司從事“福貢網(wǎng)站設(shè)計”,“福貢網(wǎng)站推廣”以來，每個客戶項目都認(rèn)真落實執(zhí)行。

public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);//這邊是做越界判斷
elementData[elementCount++] = e;
return true;
}

private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);//如果沒有越界
}

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
//如果初始化的時候不指定增量capacityIncrement，那么就是將oldCapacity+oldCapacity賦值給新的長度，如果指定增量那么就是oldCapacity+capacityIncrement
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
//最后將老的元素和新的一起加入到Vector中
}
public static T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
值得注意的一點就是如果指定增量，那么可以減少空間的浪費。

JDK閱讀只是為未無鎖的Vector做鋪墊

無鎖的Vector的實現(xiàn)

/**

• @author Allen李

• @date
  /
  public class LockFreeVector extends AbstractList{
  private static final boolean debug = false;
  private static final int FIRST_BUCKET_SIZE = 8;
  //雖然這邊籃子的個數(shù)是固定的，但是絕對是夠用的因為總共的籃子數(shù)就是82^30-1
  private static final int N_BUCKET = 30;
  private final AtomicReferenceArray> buckets;
  //利用二維數(shù)組來嵌套是為了使一維的AtomicReferenceArray盡量避免修改，在一維數(shù)組填充滿了時是不會去擴(kuò)充的，
  // 而是往二維數(shù)組里面填充，這樣就避免了修改一維數(shù)組，而且高并發(fā)就是避免不必要的寫來影響性能
  public LockFreeVector(AtomicReferenceArray> buckets) {
  this.buckets = buckets;
  }
  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.oldV = oldV;
      this.newV = newV;
      this.addr = addr;
      this.addr_ind = addr_ind;
  }
  
  public void doInt(){
      addr.compareAndSet(addr_ind,oldV,newV);
  }

  }
  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.doInt();
         writeOp=null;
      }
  }

  }

  private AtomicReference> descriptor;
  private static final int zeroNumFirst = Integer.numberOfLeadingZeros(FIRST_BUCKET_SIZE);

  public LockFreeVector(){
  buckets = new AtomicReferenceArray>(N_BUCKET);
  buckets.set(0,new AtomicReferenceArray(FIRST_BUCKET_SIZE));
  descriptor = new AtomicReference>(new Descriptor(0,null));
  }

  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));
      }
      //0x80000000就是1000000...  總共32位
      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();

  }

  public E pop_back(){
  Descriptor desc;
  Descriptor newD;
  E elem;
  do {
  desc = descriptor.get();
  desc.completeWrite();
  int pos = desc.size + FIRST_BUCKET_SIZE - 1;
  int bucketInd = Integer.numberOfLeadingZeros(FIRST_BUCKET_SIZE) - Integer.numberOfLeadingZeros(pos);
  int idx = Integer.highestOneBit(pos) ^ pos;
  elem = buckets.get(bucketInd).get(idx);
  newD = new Descriptor(desc.size - 1,null);
  }while (!descriptor.compareAndSet(desc,newD));

  return elem;

  }

  @Override
  public E get(int index){
  int pos = index + FIRST_BUCKET_SIZE;
  int zeroNumPos = Integer.numberOfLeadingZeros(pos);
  int bucketInd = zeroNumFirst - zeroNumPos;
  int idx = (0x80000000>>>zeroNumPos) ^ pos;
  return buckets.get(bucketInd).get(idx);
  }

  @Override
  public E set(int index,E e){
  int pos = index + FIRST_BUCKET_SIZE;
  int bucketInd = Integer.numberOfLeadingZeros(FIRST_BUCKET_SIZE) - Integer.numberOfLeadingZeros(pos);
  int idx = Integer.highestOneBit(pos) ^ pos;
  AtomicReferenceArray bucket = buckets.get(bucketInd);
  while (true){
  E oldV = bucket.get(idx);
  if (bucket.compareAndSet(idx,oldV,e))
  return oldV;
  }
  }

  public void reserve(int newSize){
  int size = descriptor.get().size;
  int pos = size + FIRST_BUCKET_SIZE - 1;
  int i = Integer.numberOfLeadingZeros(FIRST_BUCKET_SIZE) - Integer.numberOfLeadingZeros(pos);

  if (i<1)
      i = 1;
  
  int initialSize = buckets.get(i - 1).length();
  while (i < Integer.numberOfLeadingZeros(FIRST_BUCKET_SIZE) - Integer.numberOfLeadingZeros(newSize + FIRST_BUCKET_SIZE - 1)){
      i++;
      initialSize *= FIRST_BUCKET_SIZE;
      buckets.compareAndSet(i, null , new AtomicReferenceArray(initialSize));
  }

  }

  public int size(){
  return descriptor.get().size;
  }

  @Override
  public boolean add(E obj){
  push_back(obj);
  return true;
  }
  }
  它的結(jié)構(gòu)是：private final AtomicReferenceArray> buckets;
  從這里我們可以看到，它的內(nèi)部是采用的是 無鎖的引用數(shù)組， 數(shù)組嵌套數(shù)組
  變量buckets存放所有的內(nèi)部元素。從定義上看，它是一個保存著數(shù)組的數(shù)組，也就是通常的二維數(shù)組。特別之處在于這些數(shù)組都是使用CAS的原子數(shù)組。為什么使用二維數(shù)組去實現(xiàn)一個一維的Vector呢？這是為了將來Vector進(jìn)行動態(tài)擴(kuò)展時可以更加方便。我們知道，AtomicReferenceArray內(nèi)部使用Object[]來進(jìn)行實際數(shù)據(jù)的存儲，這使得動態(tài)空間增加特別的麻煩，因此使用二維數(shù)組的好處就是為將來增加新的元素。

相當(dāng)于一個二維數(shù)組，它的大小可以動態(tài)的進(jìn)行擴(kuò)展，

為了更有序的讀寫數(shù)組，定義了一個Descriptor的靜態(tài)內(nèi)部類。它的作用是使用CAS操作寫入新數(shù)據(jù)。

它定義了

private static final int FIRST_BUCKET_SIZE = 8;

/**

• number of buckets. 30 will allow 8(2^30-1) elements
  /
  private static final int N_BUCKET = 30;

FIRST_BUCKET_SIZE：為第一個數(shù)組的長度

N_BUCKET 整個二維數(shù)組大可擴(kuò)轉(zhuǎn)至30

每次的擴(kuò)展是成倍的增加，即：第一個數(shù)組長度為8，第二個為8<<1，第三個為8<<2 ......第30個為 8<<29

3. push_back

在第23行，使用descriptor將數(shù)據(jù)真正地寫入數(shù)組中。這個descriptor寫入的數(shù)據(jù)由20~21行構(gòu)造的WriteDescriptor決定。

在循環(huán)最開始（第5行），使用descriptor先將數(shù)據(jù)寫入數(shù)組，是為了防止上一個線程設(shè)置完descriptor后（22行），還沒來得及執(zhí)行第23行的寫入，因此，做一次預(yù)防性的操作。

第8~10行通過當(dāng)前Vector的大?。╠esc.size），計算新的元素應(yīng)該落入哪個數(shù)組。這里使用了位運算進(jìn)行計算。

LockFreeVector每次都會擴(kuò)容。它的第一個數(shù)組長度為8，第2個就是16，第3個就是32，依次類推。它們的二進(jìn)制表示如下：

它們之和就是整個LockFreeVector的總大小，因此，如果每一個數(shù)組都恰好填滿，那么總大小應(yīng)該類似如下的值（以4個數(shù)組為例）00000000 00000000 00000000 01111000：4個數(shù)組都恰好填滿時的大小。

導(dǎo)致這個數(shù)字進(jìn)位的最小條件，就是加上二進(jìn)制的1000。而這個數(shù)字整好是8（FIRST_BUCKET_SIZE就是8）這就是第8行代碼的意義。

它可以使得數(shù)組大小發(fā)生一次二進(jìn)制進(jìn)位（如果不進(jìn)位說明還在第一個數(shù)組中），進(jìn)位后前導(dǎo)零的數(shù)量就會發(fā)生變化。而元素所在的數(shù)組，和pos（第8行定義的比變量）的前導(dǎo)零直接相關(guān)。每進(jìn)行一次數(shù)組擴(kuò)容，它的前導(dǎo)零就會減1。如果從來沒有擴(kuò)容過，它的前導(dǎo)零就是28個。以后，逐級減1。這就是第9行獲得pos前導(dǎo)零的原因。第10行，通過pos的前導(dǎo)零可以立即定位使用哪個數(shù)組（也就是得到了bucketInd的值）。

第11行，判斷這個數(shù)組是否存在。如果不存在，則創(chuàng)建這個數(shù)組，大小為前一個數(shù)組的兩倍，并把它設(shè)置到buckets中。

接著再看一下元素沒有恰好填滿的情況：

那么總大小如下：

總個數(shù)加上二進(jìn)制1000后，得到：

顯然，通過前導(dǎo)零可以定位到第4個數(shù)組。而剩余位，顯然就表示元素在當(dāng)前數(shù)組內(nèi)偏移量（也就是數(shù)組下標(biāo)）。根據(jù)這個理論，就可以通過pos計算這個元素應(yīng)該放在給定數(shù)組的哪個位置。通過第19行代碼，獲得pos的除了第一位數(shù)字1以外的其他位的數(shù)值。因此，pos的前導(dǎo)零可以表示元素所在的數(shù)組，而pos的后面幾位，則表示元素所在這個數(shù)組中的位置。由此，第19行代碼就取得了元素所在位置idx。

代碼理解可以參考：
https://blog.csdn.net/netcobol/article/details/79785651
和
http://www.shaoqun.com/a/197387.html

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

文章題目：Java高并發(fā)四：無鎖的實際應(yīng)用-創(chuàng)新互聯(lián)
文章出自：http://weahome.cn/article/dsgdse.html