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

資訊專(zhuān)欄INFORMATION COLUMN

Treiber Stack簡(jiǎn)單分析

junfeng777 / 3061人閱讀

摘要：在添加新項(xiàng)目時(shí)使用堆棧，將堆棧的頂部放在新項(xiàng)目之后。當(dāng)從堆棧中彈出一個(gè)項(xiàng)目時(shí)，在返回項(xiàng)目之前，您必須檢查另一個(gè)線程自操作開(kāi)始以來(lái)沒(méi)有添加其他項(xiàng)目。比較和交換將堆棧的頭部設(shè)置為堆棧中舊的第二個(gè)元素，混合完整的數(shù)據(jù)結(jié)構(gòu)。

Abstract

Treiber Stack Algorithm是一個(gè)可擴(kuò)展的無(wú)鎖棧，利用細(xì)粒度的并發(fā)原語(yǔ)CAS來(lái)實(shí)現(xiàn)的，Treiber Stack在 R. Kent Treiber在1986年的論文Systems Programming: Coping with Parallelism中首次出現(xiàn)。

基本原理

該算法的基本原理是：只有當(dāng)您知道要添加的項(xiàng)目是自開(kāi)始操作以來(lái)唯一添加的項(xiàng)目時(shí)，才會(huì)添加新的項(xiàng)目。 這是通過(guò)使用比較和交換完成的。 在添加新項(xiàng)目時(shí)使用堆棧，將堆棧的頂部放在新項(xiàng)目之后。 然后，將這個(gè)新構(gòu)造的頭元素（舊頭）的第二個(gè)項(xiàng)目與當(dāng)前項(xiàng)目進(jìn)行比較。 如果兩者匹配，那么你可以將舊頭換成新頭，否則就意味著另一個(gè)線程已經(jīng)向堆棧添加了另一個(gè)項(xiàng)目，在這種情況下，你必須再試一次。

當(dāng)從堆棧中彈出一個(gè)項(xiàng)目時(shí)，在返回項(xiàng)目之前，您必須檢查另一個(gè)線程自操作開(kāi)始以來(lái)沒(méi)有添加其他項(xiàng)目。

正確性

在某些語(yǔ)言中，特別是那些沒(méi)有垃圾回收的語(yǔ)言，Treiber棧可能面臨ABA問(wèn)題。當(dāng)一個(gè)進(jìn)程要從堆棧中移除一個(gè)元素時(shí)（就在下面的pop例程比較和設(shè)置之前），另一個(gè)進(jìn)程可以改變堆棧，使得頭部是相同的，但是第二個(gè)元素是不同的。比較和交換將堆棧的頭部設(shè)置為堆棧中舊的第二個(gè)元素，混合完整的數(shù)據(jù)結(jié)構(gòu)。但是，由于Java運(yùn)行時(shí)提供了更強(qiáng)大的保證，所以此頁(yè)面上的Java版本不受此問(wèn)題的影響（新創(chuàng)建的不混淆的對(duì)象引用不可能與任何其他可到達(dá)的對(duì)象引用相同）。

對(duì)諸如ABA之類(lèi)的故障進(jìn)行測(cè)試可能會(huì)非常困難，因?yàn)橛袉?wèn)題的事件序列非常少見(jiàn)。

Java示例

下面是Java中Treiber Stack的實(shí)現(xiàn)，它基于Java Concurrency in Practice提供的

public class ConcurrentStack {
    private AtomicReference> top = new AtomicReference<>();

    public void push(E item) {
        Node newHead = new Node<>(item);
        Node oldHead;
        do {
            oldHead = top.get();
            newHead.next = oldHead;
        } while (!top.compareAndSet(oldHead, newHead));
    }

    public E pop() {
        Node oldHead;
        Node newHead;
        do {
            oldHead = top.get();
            if (oldHead == null)
                return null;
            newHead = oldHead.next;
        } while (!top.compareAndSet(oldHead, newHead));
        return oldHead.item;
    }

    private static class Node {
        public final E item;
        public Node next;
        public Node(E item) {
            this.item = item;
        }
    }
}
流程分析
PUSH操作


根據(jù)上述的描述做圖如上，并分析其工作流程。

首先單鏈表保存了各個(gè)Stack中的各個(gè)元素，成員變量top持有了棧的棧頂元素。

當(dāng)執(zhí)行push操作時(shí)，首先創(chuàng)建一個(gè)新的元素為newHead，并讓該新節(jié)點(diǎn)的next指針指向top節(jié)點(diǎn)（此時(shí)top=oldHead）。

最后通過(guò)CAS替換top=newHead，CAS的交換條件是top=oldHead。

當(dāng)條件滿足后，操作后的狀態(tài)如下：

POP操作


根據(jù)上述的描述做圖如上，并分析其工作流程。

當(dāng)執(zhí)行pop操作時(shí)，創(chuàng)建一個(gè)新的指針，該指針指向top的next元素。

然后通過(guò)CAS替換top=newHead，CAS的交換條件是top=oldHead。

3.當(dāng)條件滿足后，操作后的狀態(tài)如下：

參考：https://en.wikipedia.org/wiki...

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/70832.html

相關(guān)文章

  • FutureTask源碼解析(2)——深入理解FutureTask

    摘要：本文的源碼基于。人如其名，包含了和兩部分。而將一個(gè)任務(wù)的狀態(tài)設(shè)置成終止態(tài)只有三種方法我們將在下文的源碼解析中分析這三個(gè)方法。將棧中所有掛起的線程都喚醒后，下面就是執(zhí)行方法這個(gè)方法是一個(gè)空方 前言 系列文章目錄 有了上一篇對(duì)預(yù)備知識(shí)的了解之后，分析源碼就容易多了，本篇我們就直接來(lái)看看FutureTask的源碼。 本文的源碼基于JDK1.8。 Future和Task 在深入分析源碼之前，我...

    Harpsichord1207 評(píng)論0 收藏0

  • Java多線程進(jìn)階（二二）—— J.U.C之synchronizer框架：Phaser

    摘要：分層支持分層一種樹(shù)形結(jié)構(gòu)，通過(guò)構(gòu)造函數(shù)可以指定當(dāng)前待構(gòu)造的對(duì)象的父結(jié)點(diǎn)。當(dāng)一個(gè)的參與者數(shù)量變成時(shí)，如果有該有父結(jié)點(diǎn)，就會(huì)將它從父結(jié)點(diǎn)中溢移除。當(dāng)首次將某個(gè)結(jié)點(diǎn)鏈接到樹(shù)中時(shí)，會(huì)同時(shí)向該結(jié)點(diǎn)的父結(jié)點(diǎn)注冊(cè)一個(gè)參與者。 showImg(https://segmentfault.com/img/remote/1460000016010947); 本文首發(fā)于一世流云專(zhuān)欄：https://segme...

    Mr_zhang 評(píng)論0 收藏0

  • Java多線程奇幻之旅——CAS算法實(shí)現(xiàn)線程安全

    摘要：大多數(shù)保證線程安全的方法是添加各種類(lèi)型鎖，使用各種同步機(jī)制，用限制對(duì)共享的可變的類(lèi)變量并發(fā)訪問(wèn)的方式來(lái)保證線程安全。只有保證這兩條語(yǔ)句及中間語(yǔ)句以原子方式執(zhí)行，才能避免多線程覆蓋問(wèn)題。 前言 對(duì)于線程安全，我們有說(shuō)不盡的話題。大多數(shù)保證線程安全的方法是添加各種類(lèi)型鎖，使用各種同步機(jī)制，用限制對(duì)共享的、可變的類(lèi)變量并發(fā)訪問(wèn)的方式來(lái)保證線程安全。文本從另一個(gè)角度，使用比較交換算法（Comp...

    jasperyang 評(píng)論0 收藏0

  • FutureTask源碼分析

    摘要：從而可以啟動(dòng)和取消異步計(jì)算任務(wù)查詢(xún)異步計(jì)算任務(wù)是否完成和獲取異步計(jì)算任務(wù)的返回結(jié)果。原理分析在分析中我們沒(méi)有看它的父類(lèi)，其中有一個(gè)方法，返回一個(gè)，說(shuō)明該方法可以獲取異步任務(wù)的返回結(jié)果。 FutureTask介紹 FutureTask是一種可取消的異步計(jì)算任務(wù)。它實(shí)現(xiàn)了Future接口，代表了異步任務(wù)的返回結(jié)果。從而FutureTask可以啟動(dòng)和取消異步計(jì)算任務(wù)、查詢(xún)異步計(jì)算任務(wù)是否完成...

    luqiuwen 評(píng)論0 收藏0

  • Java多線程進(jìn)階（四二）—— J.U.C之executors框架：Future模式

    摘要：本文首發(fā)于一世流云的專(zhuān)欄一模式簡(jiǎn)介模式是多線程設(shè)計(jì)模式中的一種常見(jiàn)模式，它的主要作用就是異步地執(zhí)行任務(wù)，并在需要的時(shí)候獲取結(jié)果。二中的模式在多線程基礎(chǔ)之模式中，我們?cè)?jīng)給出過(guò)模式的通用類(lèi)關(guān)系圖。 showImg(https://segmentfault.com/img/bVbiwcx?w=1000&h=667); 本文首發(fā)于一世流云的專(zhuān)欄：https://segmentfault.co...

    marek 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<