Java高并發(fā)四：無(wú)鎖的實(shí)際應(yīng)用-創(chuàng)新互聯(lián)

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

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

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
//如果初始化的時(shí)候不指定增量capacityIncrement，那么就是將oldCapacity+oldCapacity賦值給新的長(zhǎng)度，如果指定增量那么就是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> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
值得注意的一點(diǎn)就是如果指定增量，那么可以減少空間的浪費(fèi)。

JDK閱讀只是為未無(wú)鎖的Vector做鋪墊

無(wú)鎖的Vector的實(shí)現(xiàn)

/**

@author Allen李
@date
/
public class LockFreeVector<E> extends AbstractList<E>{
private static final boolean debug = false;
private static final int FIRST_BUCKET_SIZE = 8;
//雖然這邊籃子的個(gè)數(shù)是固定的，但是絕對(duì)是夠用的因?yàn)榭偣驳幕@子數(shù)就是82^30-1
private static final int N_BUCKET = 30;
private final AtomicReferenceArray<AtomicReferenceArray<E>> buckets;
//利用二維數(shù)組來(lái)嵌套是為了使一維的AtomicReferenceArray盡量避免修改，在一維數(shù)組填充滿了時(shí)是不會(huì)去擴(kuò)充的，
// 而是往二維數(shù)組里面填充，這樣就避免了修改一維數(shù)組，而且高并發(fā)就是避免不必要的寫(xiě)來(lái)影響性能
public LockFreeVector(AtomicReferenceArray<AtomicReferenceArray<E>> buckets) {
this.buckets = buckets;
}
static class WriteDescriptor<E>{
public E oldV;
public E newV;
public AtomicReferenceArray<E> addr;
public int addr_ind;
```
public WriteDescriptor( AtomicReferenceArray<E> 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<E>{
public int size;
volatile WriteDescriptor<E> writeOp;
```
public Descriptor(int size, WriteDescriptor<E> writeOp) {
    this.size = size;
    this.writeOp = writeOp;
}

public void completeWrite(){
   writeDescriptor<E> tmpOp = writeOp;
    if(tmpOp != null){
        tmpOp.doInt();
       writeOp=null;
    }
}
```
}
private AtomicReference<Descriptor<E>> descriptor;
private static final int zeroNumFirst = Integer.numberOfLeadingZeros(FIRST_BUCKET_SIZE);
public LockFreeVector(){
buckets = new AtomicReferenceArray<AtomicReferenceArray<E>>(N_BUCKET);
buckets.set(0,new AtomicReferenceArray<E>(FIRST_BUCKET_SIZE));
descriptor = new AtomicReference<Descriptor<E>>(new Descriptor<E>(0,null));
}
public void push_back(E e){
Descriptor<E> desc;
Descriptor<E> 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<E>(newLen));
    }
    //0x80000000就是1000000...  總共32位
    int idx = (0x80000000>>>zeroNumPos) ^ pos;
    newD = new Descriptor<>(desc.size + 1,new WriteDescriptor<E>(buckets.get(bucketInd),idx,null, e));
}while (!descriptor.compareAndSet(desc,newD));
descriptor.get().completeWrite();
```
}
public E pop_back(){
Descriptor<E> desc;
Descriptor<E> 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<E>(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<E> 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<E>(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<AtomicReferenceArray<E>> buckets;
從這里我們可以看到，它的內(nèi)部是采用的是無(wú)鎖的引用數(shù)組，數(shù)組嵌套數(shù)組
變量buckets存放所有的內(nèi)部元素。從定義上看，它是一個(gè)保存著數(shù)組的數(shù)組，也就是通常的二維數(shù)組。特別之處在于這些數(shù)組都是使用CAS的原子數(shù)組。為什么使用二維數(shù)組去實(shí)現(xiàn)一個(gè)一維的Vector呢？這是為了將來(lái)Vector進(jìn)行動(dòng)態(tài)擴(kuò)展時(shí)可以更加方便。我們知道，AtomicReferenceArray內(nèi)部使用Object[]來(lái)進(jìn)行實(shí)際數(shù)據(jù)的存儲(chǔ)，這使得動(dòng)態(tài)空間增加特別的麻煩，因此使用二維數(shù)組的好處就是為將來(lái)增加新的元素。

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

為了更有序的讀寫(xiě)數(shù)組，定義了一個(gè)Descriptor的靜態(tài)內(nèi)部類。它的作用是使用CAS操作寫(xiě)入新數(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：為第一個(gè)數(shù)組的長(zhǎng)度

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

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

3. push_back
Java 高并發(fā)四：無(wú)鎖的實(shí)際應(yīng)用

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

在循環(huán)最開(kāi)始（第5行），使用descriptor先將數(shù)據(jù)寫(xiě)入數(shù)組，是為了防止上一個(gè)線程設(shè)置完descriptor后（22行），還沒(méi)來(lái)得及執(zhí)行第23行的寫(xiě)入，因此，做一次預(yù)防性的操作。
Java 高并發(fā)四：無(wú)鎖的實(shí)際應(yīng)用

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

LockFreeVector每次都會(huì)擴(kuò)容。它的第一個(gè)數(shù)組長(zhǎng)度為8，第2個(gè)就是16，第3個(gè)就是32，依次類推。它們的二進(jìn)制表示如下：
Java 高并發(fā)四：無(wú)鎖的實(shí)際應(yīng)用

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

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

它可以使得數(shù)組大小發(fā)生一次二進(jìn)制進(jìn)位（如果不進(jìn)位說(shuō)明還在第一個(gè)數(shù)組中），進(jìn)位后前導(dǎo)零的數(shù)量就會(huì)發(fā)生變化。而元素所在的數(shù)組，和pos（第8行定義的比變量）的前導(dǎo)零直接相關(guān)。每進(jìn)行一次數(shù)組擴(kuò)容，它的前導(dǎo)零就會(huì)減1。如果從來(lái)沒(méi)有擴(kuò)容過(guò)，它的前導(dǎo)零就是28個(gè)。以后，逐級(jí)減1。這就是第9行獲得pos前導(dǎo)零的原因。第10行，通過(guò)pos的前導(dǎo)零可以立即定位使用哪個(gè)數(shù)組（也就是得到了bucketInd的值）。
Java 高并發(fā)四：無(wú)鎖的實(shí)際應(yīng)用
第11行，判斷這個(gè)數(shù)組是否存在。如果不存在，則創(chuàng)建這個(gè)數(shù)組，大小為前一個(gè)數(shù)組的兩倍，并把它設(shè)置到buckets中。

Java 高并發(fā)四：無(wú)鎖的實(shí)際應(yīng)用

接著再看一下元素沒(méi)有恰好填滿的情況：
Java 高并發(fā)四：無(wú)鎖的實(shí)際應(yīng)用

那么總大小如下：
Java 高并發(fā)四：無(wú)鎖的實(shí)際應(yīng)用

總個(gè)數(shù)加上二進(jìn)制1000后，得到：
Java 高并發(fā)四：無(wú)鎖的實(shí)際應(yīng)用

顯然，通過(guò)前導(dǎo)零可以定位到第4個(gè)數(shù)組。而剩余位，顯然就表示元素在當(dāng)前數(shù)組內(nèi)偏移量（也就是數(shù)組下標(biāo)）。根據(jù)這個(gè)理論，就可以通過(guò)pos計(jì)算這個(gè)元素應(yīng)該放在給定數(shù)組的哪個(gè)位置。通過(guò)第19行代碼，獲得pos的除了第一位數(shù)字1以外的其他位的數(shù)值。因此，pos的前導(dǎo)零可以表示元素所在的數(shù)組，而pos的后面幾位，則表示元素所在這個(gè)數(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元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

網(wǎng)站名稱：Java高并發(fā)四：無(wú)鎖的實(shí)際應(yīng)用-創(chuàng)新互聯(lián)
文章分享：http://muchs.cn/article34/dsgdse.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動(dòng)網(wǎng)站建設(shè)、虛擬主機(jī)、企業(yè)網(wǎng)站制作、Google、小程序開(kāi)發(fā)、定制網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容