并发集合8-LinkedBlockingDeque源码分析
2017-06-23 本文已影响0人
zhanglbjames
前言
LinkedBlockingDeque是基于双向链表的双端有界阻塞队列，使用非公平ReentrantLock实现线程安全，默认和最大长度都为Integer.MAX_VALUE；不允许null元素添加；实现骨架和ConcurrentLinkedDeque一样，只是对并发控制的细节不同（volatile+循环CAS），双端队列可以用来实现 "窃取算法" ,两头都可以操作队列，相对于单端队列可以减少一半的竞争。
定义
实现了BlockingDeque接口
重要字段
双向链表节点
first和last节点在初始化时同时为null。
first和last节点状态相对于ConcurrentLinkedDeque的比较简单，因为此first和last节点都为普通变量，并不会因为频繁的读写（相对于volatile变量）造成性能瓶颈。
count：元素数量计数
capacity：队列最大容量
一个ReentrantLock锁，两个Condition。
构造器
无参构造器，默认容量Integer.MAX_VALUE
指定大于0的容量
集合构造器，默认容量Integer.MAX_VALUE，加锁，保证普通变量刷新到主内存中，保证其线程可见性。
offerFirst方法（不响应中断）
offerLast方法（不响应中断）
putFirst方法（响应中断）
如果已经满了，则等待直到队列不满
putLast（响应中断）
offerFirst （响应中断超时）
offerLast（响应中断超时）
pollFirst（不响应中断）
pollLast（不响应中断）
remove方法
两个方法分别遍历队列头尾遍历数组，时间复杂度为O(n)
contains方法
两个方法分别遍历队列头尾遍历数组，时间复杂度为O(n)
size方法
时间复杂度为O(1)
iterator迭代器
迭代器都是弱一致性的，在操作队列元素时需要加锁，但是在迭代操作之间，队列有可能被其他线程修改，当hasNext返回true，但是下一次next和remove方法元素已经被删除了，此时将抛出NoSuchElementException异常。
方法列表
总结
LinkedBlockingDeque性能基本和LinkedBlockingQueue一致，只是双端队列和单端队列的区别，一把锁和两把锁的区别。
