八裂问、并發(fā)隊列之LinkedBlockingDeque源碼解析

為什么先介紹LinkedBlockingDeque雙向同步隊列呢，主要是它比較簡單卑惜，對于后面的隊列的理解是一個好的鋪墊

結構

  • Node<E> first 頭節(jié)點
  • Node<E> last 尾節(jié)點
  • int count 節(jié)點數量
  • int capacity 容量
  • ReentrantLock lock = new ReentrantLock(); 鎖
  • Condition notEmpty = lock.newCondition(); 非空條件變量
  • Condition notFull = lock.newCondition(); 未滿條件變量

由上可以看出瘾带，LinkedBlockingDeque有一個獨占鎖鼠哥，且包括它的兩個條件變量，其實這就是一個生產者-消費者模型看政。
再來看其內部Node類

static final class Node<E> {
    E item;
    Node<E> prev;
    Node<E> next;
    Node(E x) {
        item = x;
    }
}

由上可以看出與ConcurrentLinkedQueue不同朴恳，其內部是一個雙端隊列。
到此我們值了解這么多允蚣，重要的操作原理我們往下看源碼

重要方法

因為是隊列于颖，離不開offer、poll嚷兔、peek這幾個重要方法森渐，不過由于LinkedBlockingDeque是一個雙向隊列所以還有對應相反的方法。

入隊操作

入隊方法有如下：

```
public boolean add(E e) {
    addLast(e);
    return true;
}
public void addFirst(E e) {
    if (!offerFirst(e))
        throw new IllegalStateException("Deque full");
}
public void addLast(E e) {
    if (!offerLast(e))
        throw new IllegalStateException("Deque full");
}
public boolean offer(E e) {
    return offerLast(e);
}
public boolean offerFirst(E e) {
    if (e == null) throw new NullPointerException();
    Node<E> node = new Node<E>(e);
    final ReentrantLock lock = this.lock;
    lock.lock();       // 加鎖
    try {
        return linkFirst(node);  // 直接返回linkFirst
    } finally {
        lock.unlock();
    }
}
public boolean offerLast(E e) {
    if (e == null) throw new NullPointerException();
    Node<E> node = new Node<E>(e);
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        return linkLast(node);
    } finally {
        lock.unlock();
    }
}
public void put(E e) throws InterruptedException {
    putLast(e);
}
public void putFirst(E e) throws InterruptedException {
    if (e == null) throw new NullPointerException();
    Node<E> node = new Node<E>(e);
    final ReentrantLock lock = this.lock;
    lock.lock();        // 加鎖
    try {
        while (!linkFirst(node))    // 如果失敗冒晰，則調用notFull.await,也就是同衣，等待未滿條件
            notFull.await();
    } finally {
        lock.unlock();
    }
}
public void putLast(E e) throws InterruptedException {
    if (e == null) throw new NullPointerException();
    Node<E> node = new Node<E>(e);
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        while (!linkLast(node))
            notFull.await();
    } finally {
        lock.unlock();
    }
}
```

從代碼中我們可以看到，一共有三類：add壶运、offer乳怎、put，然后分別有對應last和first的方法。只有三點不同：

  1. put中加個while循環(huán)蚪缀，如果失敗，則進行等待恕出，只有l(wèi)ink成功的條件才往下執(zhí)行询枚，而offer直接返回link的結果
  2. 它們的返回參數不一樣，offer的是boolean浙巫，而put則是void
  3. add函數在失敗后會拋"Deque full"的異常
    于是我們知道金蜀，offer不保證成功，put保證一定能插入元素且是阻塞的方法的畴。
    接著我們繼續(xù)看他們的核心函數link：
private boolean linkFirst(Node<E> node) {
    // assert lock.isHeldByCurrentThread();
    if (count >= capacity)
        return false;       // 數量達到限制渊抄，則返回false
    Node<E> f = first;      // 頭節(jié)點
    node.next = f;          // 當前節(jié)點放到頭節(jié)點，成為新的頭節(jié)點
    first = node;
    if (last == null)
        last = node;        // 如果沒有尾節(jié)點丧裁，則也置為尾節(jié)點
    else
        f.prev = node;
    ++count;
    notEmpty.signal();      // 喚醒出隊操作护桦，代表現在隊列不是空
    return true;
}

上面的函數比較簡單，就做了兩件事：

  1. 重置頭結點
  2. 喚醒出隊線程煎娇，因為是一個入隊操作二庵，那么至少隊列的數量有一個，也就是不可能為空了缓呛，表示現在可以出隊了催享。

linkLast也是一樣，其實由于前面已經加鎖了哟绊，不會產生并發(fā)因妙，所以邏輯非常簡單，就是雙向隊列的入隊操作票髓。

出隊操作

與入隊對應攀涵，出隊操作也有三種，remove炬称、poll汁果、take。玲躯。
看一下三者的區(qū)別：

public E remove() {
        return removeFirst();
    }
public E removeLast() {
    E x = pollLast();       // 其實就是調用的poll
    if (x == null) throw new NoSuchElementException(); 只不過為空的時候會拋錯
    return x;
}
public E pollLast() {
    final ReentrantLock lock = this.lock;
    lock.lock();        // 采用獨占鎖進行同步
    try {
        return unlinkLast();
    } finally {
        lock.unlock();
    }
}
public E takeLast() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        E x;
        while ( (x = unlinkLast()) == null)
            notEmpty.await();
        return x;
    } finally {
        lock.unlock();
    }
}

可以看出据德，與入隊幾乎一樣，兩點不同：

  1. take中加個while循環(huán)跷车，如果失敗棘利，則進行等待，只有unlink成功的條件才往下執(zhí)行朽缴，而poll直接返回unlink的結果
  2. remove函數在失敗后會拋錯NoSuchElementException的異常

其核心函數還是unlink ：

private E unlinkLast() {
    // assert lock.isHeldByCurrentThread();
    Node<E> l = last;
    if (l == null)
        return null;
    Node<E> p = l.prev;
    E item = l.item;  // 保存值用來返回
    l.item = null;    
    l.prev = l; // 指向自己延后釋放
    last = p;      // 重新指定隊尾
    if (p == null)
        first = null;  // 如果隊列為空就沒必要再指定下一個節(jié)點了
    else
        p.next = null;
    --count;
    notFull.signal();  // 至少有一個空余善玫，喚醒某個入隊線程，使其加入同步隊列
    return item;
}

上面的函數比較簡單密强，就做了兩件事：

  1. 釋放尾節(jié)點茅郎、并充值last節(jié)點
  2. 喚醒入隊線程蜗元，因為是一個出隊操作，那么至少隊列的數量減一系冗，表示現在可以入隊了奕扣。

獲取元素

該操作與出列非常相似，只是沒有移除的步驟掌敬，獲取操作有兩種：get惯豆、和peek

public E getFirst() {
    E x = peekFirst();
    if (x == null) throw new NoSuchElementException();
    return x;
}
public E peekFirst() {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        return (first == null) ? null : first.item;
    } finally {
        lock.unlock();
    }
}

可以看出唯一的區(qū)別就是為空時拋不拋異常。

最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末奔害，一起剝皮案震驚了整個濱河市楷兽，隨后出現的幾起案子，更是在濱河造成了極大的恐慌华临，老刑警劉巖芯杀，帶你破解...
    沈念sama閱讀 217,509評論 6贊 504
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現場離奇詭異银舱，居然都是意外死亡瘪匿，警方通過查閱死者的電腦和手機，發(fā)現死者居然都...
    沈念sama閱讀 92,806評論 3贊 394
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門寻馏，熙熙樓的掌柜王于貴愁眉苦臉地迎上來棋弥，“玉大人，你說我怎么就攤上這事诚欠⊥缛荆” “怎么了一铅？”我有些...
    開封第一講書人閱讀 163,875評論 0贊 354
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵智蝠，是天一觀的道長。 經常有香客問我烛亦，道長左腔，這世上最難降的妖魔是什么唧垦？ 我笑而不...
    開封第一講書人閱讀 58,441評論 1贊 293
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任，我火速辦了婚禮液样，結果婚禮上振亮，老公的妹妹穿的比我還像新娘。我一直安慰自己鞭莽，他們只是感情好坊秸，可當我...
    茶點故事閱讀 67,488評論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布。 她就那樣靜靜地躺著澎怒，像睡著了一般褒搔。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上，一...
    開封第一講書人閱讀 51,365評論 1贊 302
  • 城市分裂傳說
    那天星瘾，我揣著相機與錄音走孽，去河邊找鬼。 笑死琳状，一個胖子當著我的面吹牛融求，可吹牛的內容都是我干的。 我是一名探鬼主播算撮，決...
    沈念sama閱讀 40,190評論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼县昂！你這毒婦竟也來了肮柜？” 一聲冷哼從身側響起，我...
    開封第一講書人閱讀 39,062評論 0贊 276
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤倒彰，失蹤者是張志新（化名）和其女友劉穎审洞，沒想到半個月后，有當地人在樹林里發(fā)現了一具尸體待讳，經...
    沈念sama閱讀 45,500評論 1贊 314
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡芒澜，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 37,706評論 3贊 335
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時候發(fā)現自己被綠了创淡。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片痴晦。...
    茶點故事閱讀 39,834評論 1贊 347
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖琳彩，靈堂內的尸體忽然破棺而出誊酌，到底是詐尸還是另有隱情，我是刑警寧澤露乏，帶...
    沈念sama閱讀 35,559評論 5贊 345
  • ?日本核電站爆炸內幕
    正文 年R本政府宣布碧浊，位于F島的核電站，受9級特大地震影響瘟仿，放射性物質發(fā)生泄漏箱锐。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點故事閱讀 41,167評論 3贊 328
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一劳较、第九天 我趴在偏房一處隱蔽的房頂上張望驹止。 院中可真熱鬧，春花似錦兴想、人聲如沸幢哨。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,779評論 0贊 22
  • 一樁弒父案嫂便，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽捞镰。三九已至，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間岸售，已是汗流浹背践樱。 一陣腳步聲響...
    開封第一講書人閱讀 32,912評論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來泰國打工， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留凸丸，地道東北人拷邢。 一個月前我還...
    沈念sama閱讀 47,958評論 2贊 370
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長得像屎慢，于是被迫代替她去往敵國和親瞭稼。 傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當晚...
    茶點故事閱讀 44,779評論 2贊 354