八、并发队列之LinkedBlockingDeque源码解析

为什么先介绍LinkedBlockingDeque双向同步队列呢，主要是它比较简单，对于后面的队列的理解是一个好的铺垫

结构

  • Node<E> first 头节点
  • Node<E> last 尾节点
  • int count 节点数量
  • 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循环，如果失败，则进行等待，只有link成功的条件才往下执行，而offer直接返回link的结果
  2. 它们的返回参数不一样，offer的是boolean，而put则是void
  3. add函数在失败后会抛"Deque full"的异常
    于是我们知道，offer不保证成功，put保证一定能插入元素且是阻塞的方法。
    接着我们继续看他们的核心函数link：
private boolean linkFirst(Node<E> node) {
    // assert lock.isHeldByCurrentThread();
    if (count >= capacity)
        return false;       // 数量达到限制，则返回false
    Node<E> f = first;      // 头节点
    node.next = f;          // 当前节点放到头节点，成为新的头节点
    first = node;
    if (last == null)
        last = node;        // 如果没有尾节点，则也置为尾节点
    else
        f.prev = node;
    ++count;
    notEmpty.signal();      // 唤醒出队操作，代表现在队列不是空
    return true;
}

上面的函数比较简单，就做了两件事：

  1. 重置头结点
  2. 唤醒出队线程，因为是一个入队操作，那么至少队列的数量有一个，也就是不可能为空了，表示现在可以出队了。

linkLast也是一样，其实由于前面已经加锁了，不会产生并发，所以逻辑非常简单，就是双向队列的入队操作。

出队操作

与入队对应，出队操作也有三种，remove、poll、take。。
看一下三者的区别：

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循环，如果失败，则进行等待，只有unlink成功的条件才往下执行，而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;  // 如果队列为空就没必要再指定下一个节点了
    else
        p.next = null;
    --count;
    notFull.signal();  // 至少有一个空余，唤醒某个入队线程，使其加入同步队列
    return item;
}

上面的函数比较简单，就做了两件事：

  1. 释放尾节点、并充值last节点
  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();
    }
}

可以看出唯一的区别就是为空时抛不抛异常。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,718评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,683评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 158,207评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,755评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,862评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,050评论 1赞 291
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,136评论 3赞 410
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,882评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,330评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,651评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,789评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,477评论 4赞 333
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,135评论 3赞 317
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,864评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,099评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,598评论 2赞 362
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,697评论 2赞 351