国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

世界上最簡單的無等待算法(getAndIncrement)

everfly / 1972人閱讀

摘要:本文基于指令完成一個無等待并發算法。并且導致它失敗的那一方必定取得了進展。通過將包裹的,從更新為來更新狀態的同時傳遞對應線程通過判定操作已完成。,代表這個已經被對應的線程預定了,剩余線程達成共識。

本文基于compareandswap指令完成一個無等待并發算法。
根據維基百科,它的定義如下:

An algorithm is wait-free if every operation has a bound on the number of steps the algorithm will take before the operation completes.

本文的方法參考了Wait-free queues with multiple enqueuers and dequeuers,A methodology for creating fast wait-free data structures,A practical wait-free simulation for lock-free data structures。
它的目標非常簡單,就是把一個值通過原子指令CMPXCHG加N,然后返回原來的值。
lock-free版本如下:

    public final int getAndIncrement(int add) {
        for (;;) {
            int current = get();
            int next = current + add;
            if (compareAndSet(current, next))
                return current;
        }
    }

那么,這里的方式是,compareAndSet失敗了重試。并且導致它失敗的那一方必定取得了進展。
這里的問題在于,究竟需要重試多少次compareAndSet才能成功呢?
假如一直處于競爭環境下,這個重試次數是沒有上限的。這里也就是饑餓的問題。
有沒有辦法給出一個上限,哪怕這個上限比較大
這種并發的性質被稱為wait-freedom。
先給出一個我實現好了的代碼,之后再來講思路:

    public static int getAndIncrement(int index, int add) {
        //fast-path, 最多MAX次。
        int count = MAX;
        for(;;) {
            ValueObj valueObj_ = valueObj;
            if(valueObj_.threadObj == null) {
                ValueObj valueObjNext = new ValueObj(valueObj_.value + add, null);
                if(casValueObj(valueObj_, valueObjNext)) {
                    StateObj myState = states[index];
                    //前進一步,每assistStep,嘗試一個幫助。
                    if(((++myState.steps) & myState.assistStep) == 0){
                        long helpThread = myState.index;
                        help(helpThread);
                        //下一個協助的對象。
                        ++myState.index;
                    }
                    return valueObj_.value;
                }
                Thread.yield();Thread.yield();Thread.yield();Thread.yield();
            } else {
                helpTransfer(valueObj_);
            }
            
            if(--count == 0)
                break;
        }
//        System.out.println("here " + inter.incrementAndGet());
        for(int j = 0; j < bigYields; ++j)
            Thread.yield();
        
        //slow-path,將自己列為被幫助對象。
        ThreadObj myselfObj = new ThreadObj(new ThreadObj.WrapperObj(null, false), add);
        setThreadObj(index, myselfObj);
        //開始幫助自己
        ValueObj result = help(index);
        setThreadObj(index, null);
        return result.value;
    }
    
    // valueObj->threadObj->wrapperObj->valueObj。
    // step 1-3,每一個步驟都不會阻塞其他步驟。
    // 嚴格遵守以下順序: 
    // step 1: 通過將ValueObj指向ThreadObj:
    //         atomic: (value, null)->(value, ThreadObj)來錨定該值                      //確定該value歸ThreadObj對應線程所有。
    // step 2: 通過將ThreadObj包裹的WrapperObj,
    //         atomic: 從(null, false)更新為(valueObj, true)來更新狀態的同時傳遞value    //對應線程通過isFinish判定操作已完成。
    // step 3: 更新ValueObj,提升value,同時設置ThreadObj為null:
    //         atomic: (value, ThreadObj)->(value+1, null)完成收尾動作                 //此時value值回到了沒有被線程錨定的狀態,也可以看做step1之前的狀態。
    private static ValueObj help(long helpIndex) {
        helpIndex = helpIndex % N;
        ThreadObj helpObj = getThreadObj(helpIndex);
        ThreadObj.WrapperObj wrapperObj;
        if(helpObj == null || helpObj.wrapperObj == null)
            return null;
        //判定句,是否該線程對應的操作未完成,(先取valueObj,再取isFinish,這很重要)。
        ValueObj valueObj_ = valueObj;
        while(!(wrapperObj = helpObj.wrapperObj).isFinish) {
            /*ValueObj valueObj_ = valueObj;*/
            if(valueObj_.threadObj == null) {
                ValueObj intermediateObj = new ValueObj(valueObj_.value, helpObj);
                //step1
                if(!casValueObj(valueObj_, intermediateObj)) {
                    valueObj_ = valueObj;
                    continue;
                }
                //step1: 錨定該ValueObj,接下來所有看到該valueObj的線程,都會一致地完成一系列操作.
                valueObj_ = intermediateObj;
            }
            //完成ValueObj、ThreadObj中的WrapperObj的狀態遷移。
            helpTransfer(valueObj_);
            valueObj_ = valueObj;
        }
        valueObj_ = wrapperObj.value;
        helpValueTransfer(valueObj_);
        //返回錨定的valueObj。
        return valueObj_;
    }
    
    private static void helpTransfer(ValueObj valueObj_) {
        ThreadObj.WrapperObj wrapperObj = valueObj_.threadObj.wrapperObj;
        //step2: 先完成ThreadObj的狀態遷移,WrapperObj(valueObj,true)分別表示(值,完成),原子地將這兩個值喂給threadObj。
        if(!wrapperObj.isFinish) {
            ThreadObj.WrapperObj wrapValueFiniash = new ThreadObj.WrapperObj(valueObj_, true);
            valueObj_.threadObj.casWrapValue(wrapperObj, wrapValueFiniash);
        }
        //step3: 最后完成ValueObj上的狀態遷移
        helpValueTransfer(valueObj_);
    }
    
    private static ValueObj helpValueTransfer(ValueObj valueObj_) {
        if(valueObj_ == valueObj) {
            ValueObj valueObjNext = new ValueObj(valueObj_.value + valueObj_.threadObj.add, null);
            casValueObj(valueObj_, valueObjNext);
        }
        return valueObj_;
    }

首先全局作用域有個值ValueObj,一種自然的想法是ValueObj應該值包含一個int值value,圖[1]:

如圖所示,無鎖并發的版本無非就是從一個值原子地變化為另一個+1的值。
但是我們要的是wait-free,勢必涉及到線程之間的互助。如何在線程之間傳遞信息從而實現協助呢?
我們給ValueObj增加一個字段threadObj,那么上圖的版本現在可以視為,圖[2]:

那么現在增加了一個數據ThreadObj(后面會解釋如何使用),ValueObj會有兩種狀態:

(Value, null)

(Value, threadObj)

那么好,現在是兩種情況:

(value, null),代表這個value我可以去競爭。

(value, threadObj),代表這個value已經被threadObj對應的線程預定了,剩余線程達成共識。

所以情況2我們能做什么呢?
這里就涉及到無等待算法的核心技術,help,通俗地說,就是多個線程間的相互協助。
我們會先將value,原子地喂給threadObj,再將(value, threadObj)原子地遷移到(value+1, null)。
這里的順序很重要,因為假如線程A先遷移了(value, threadObj)->(value+1, nulll),那么剩下的其他所有線程都無法再看到threadObj,也就是說盡管value已經增加了,但是threadObj對應線程被鎖住了。只能等待線程A將value喂給threadObj。
ThreadObj中包裹著WrapperObj,WrapperObj中初始化為(null, false),將會原子地轉變為(ValueObj, ture),從而ThreadObj拿到了ValueObj。
所以這里一共是三個steps:
step 1: (value, null) atomic-> (value, threadObj)
step 2: threadObj.WrapperObj(null, false) atomic-> WrapperObj(valueObj, true)
stpe 3: (value, trheadObj) atomic-> (value + 1, null)
如圖所示[3]:

其中灰框黑字標識了關鍵的3個step.
圖[3]所示是一種通用的無等待構造技術。
對于其中的ThreadObj以及每個線程協助其他線程的策略states,可以通過數組來構造,具體可在代碼里看到。
最后我們的程序結構,如圖[4]:

最后給出完整的可執行代碼 WaitFreeGetAndIncrement:

https://github.com/Pslydhh/Ps...

or WaitFreeAtomic:

https://github.com/Pslydhh/Wa...

,每個loop,100個線程每個操作100000次。
https://github.com/Pslydhh/Ps...
參考文獻:
0:Wait-free synchronization
1:Wait-free queues with multiple enqueuers and dequeuers
2:A methodology for creating fast wait-free data structures
3:A practical wait-free simulation for lock-free data structures

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/70627.html

相關文章

  • ICML 2015壓軸討論總結:6大神暢談深度學習的未來

    摘要:年的深度學習研討會,壓軸大戲是關于深度學習未來的討論。他認為,有潛力成為深度學習的下一個重點。認為這樣的人工智能恐懼和奇點的討論是一個巨大的牽引。 2015年ICML的深度學習研討會,壓軸大戲是關于深度學習未來的討論?;谄胶饪紤],組織方分別邀請了來自工業界和學術界的六位專家開展這次圓桌討論。組織者之一Kyunghyun Cho(Bengio的博士后)在飛機上憑記憶寫下本文總結了討論的內容,...

    netScorpion 評論0 收藏0
  • 為什么我需要深度學習?

    摘要:為什么我又要重新開始寫機器學習相關的文章了最主要的原因是現在的機器學習和五年前十年前區別很大。深度學習帶來了什么深度學習最重要的東西就是自帶了特征學習,有時候也被翻譯為表征學習,簡單來說就是,不需要進行特別的特征抽取。 1.為什么我開始寫這個系列博客說五年前我還在某A云公司的時候,身在一個機器學習算法組,對機器學習懷有濃厚的興趣?;撕枚嗟臅r間來試圖搞清楚各種流行的機器學習算法,經常周末也跟...

    lordharrd 評論0 收藏0
  • 線程安全

    摘要:不可變在中,不可變的對象一定是線程安全的。在里標注自己是線程安全的類,大多都不是絕對線程安全,比如某些情況下類在調用端也需要額外的同步措施。無同步方案要保證線程安全,不一定就得需要數據的同步,兩者沒有因果關系。 在之前學習編程的時候,有一個概念根深蒂固,即程序=算法+數據結構。數據代表問題空間中的客體,代碼就用來處理這些數據,這種思維是站在計算機的角度去抽象問題和解決問題,稱之為面向過...

    fuyi501 評論0 收藏0
  • Google GAN之父 ICCV2017演講:解讀生成對抗網絡的原理與應用

    摘要:但年在機器學習的較高級大會上,蘋果團隊的負責人宣布,公司已經允許自己的研發人員對外公布論文成果。蘋果第一篇論文一經投放,便在年月日,斬獲較佳論文。這項技術由的和開發,使用了生成對抗網絡的機器學習方法。 GANs「對抗生成網絡之父」Ian Goodfellow 在 ICCV 2017 上的 tutorial 演講是聊他的代表作生成對抗網絡(GAN/Generative Adversarial ...

    plokmju88 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<