聊城建设工程质量信息网站,网站推广员能力要求,鞍山58同城招聘网最新招聘,长沙马拉松调整为线上赛一、队列简介
队列是一种特殊的线性表#xff0c;遵循先入先出、后入后出#xff08;FIFO#xff09;的基本原则#xff0c;一般来说#xff0c;它只允许在表的前端进行删除操作#xff0c;而在表的后端进行插入操作#xff0c;但是java的某些队列运行在任何地方插入删…一、队列简介
队列是一种特殊的线性表遵循先入先出、后入后出FIFO的基本原则一般来说它只允许在表的前端进行删除操作而在表的后端进行插入操作但是java的某些队列运行在任何地方插入删除比如我们常用的 LinkedList 集合它实现了Queue 接口因此我们可以理解为 LinkedList 就是一个队列 二、Java队列分类
Java中队列主要分为阻塞和非阻塞有界和无界、单向链表和双向链表之分
2.1、阻塞和非阻塞 阻塞队列 入列(添加元素)时如果元素数量超过队列总数会进行等待阻塞待队列的中的元素出列后元素数量未超过队列总数时就会解除阻塞状态进而可以继续入列 出列(删除元素)时如果队列为空的情况下也会进行等待阻塞待队列有值的时候即会解除阻塞状态进而继续出列 阻塞队列的好处是可以防止队列容器溢出只要满了就会进行阻塞等待也就不存在溢出的情况 只要是阻塞队列都是线程安全的 非阻塞队列 不管出列还是入列都不会进行阻塞 入列时如果元素数量超过队列总数则会抛出异常 出列时如果队列为空则取出空值
一般情况下非阻塞式队列使用的比较少一般都用阻塞式的对象比较多阻塞和非阻塞队列在使用上的最大区别就是阻塞队列提供了以下2个方法 出队阻塞方法 take() 入队阻塞方法 put()
2.2、有界和无界 有界有界限大小长度受限制 无界无限大小其实说是无限大小其实是有界限的只不过超过界限时就会进行扩容就行ArrayList 一样在内部动态扩容
2.3、单向链表和双向链表
单向链表 每个元素中除了元素本身之外还存储一个指针这个指针指向下一个元素 双向链表 除了元素本身之外还有两个指针一个指针指向前一个元素的地址另一个指针指向后一个元素的地址 三、Java内置队列
3.1、Java 队列接口继承图 3.2、常见的Java线程安全的内置队列
队列有界性锁数据结构队列类型ArrayBlockingQueue有界加锁ReentrantLock读写同一把锁arraylist数组阻塞LinkedBlockingQueue可选加锁ReentrantLock读写各自一把锁linkedlist链表阻塞ConcurrentLinkedQueue无界无锁CASlinkedlist链表非阻塞LinkedTransferQueue无界无锁CASlinkedlist链表阻塞PriorityBlockingQueue无界加锁ReentrantLock读写同一把锁heap堆阻塞DelayQueue无界加锁ReentrantLock读写同一把锁heap堆阻塞ArrayBlockingQueue 一个用数组实现的有界阻塞队列初始化时必须指定队列大小。此队列按照先进先出FIFO的原则对元素进行排序。默认情况下采用非公平锁的方式实现可以通过构造器传参控制是采用公平锁还是非公平锁实现 LinkedBlockingQueue 一个由链表结构组成的有界阻塞队列,此队列按照先进先出FIFO的原则对元素进行排序 LinkedTransferQueue 一个由链表结构组成的无界阻塞队列 ConcurrentLinkedQueue 一个通过CAS实现的线程安全的无界非阻塞队列 PriorityBlockingQueue 一个带优先级的无界队列而不是先进先出队列。元素按优先级顺序被移除而且它也是无界的也就是没有容量上限虽然此队列逻辑上是无界的但是由于资源被耗尽所以试图执行添加操作可能会导致 OutOfMemoryError 错误 DelayQueue 一个通过PriorityBlockingQueue实现延迟获取元素的无界队列无界阻塞队列其中添加进该队列的元素必须实现Delayed接口指定延迟时间而且只有在延迟期满后才能从中提取元素。
如果要 实现 一个 线程安全的队列有两种方式一种是使用阻塞算法另一种是使用非阻塞算法。
使用阻塞算法的队列可以用一个 锁 入队和出队用同一把锁ArrayBlockingQueue 或两个锁 入队和出队 用不同的锁 LinkedBlockingQueue等方式来 实现 。 非阻塞的实现 方式则 可以使用循环CAS 的方式来实现ConcurrentLinkedQueue 。
3.3、队列常用方法 add增加一个元索 如果队列已满则抛出一个IIIegaISlabEepeplian异常 remove移除并返回队列头部的元素 如果队列为空则抛出一个NoSuchElementException异常 element返回队列头部的元素 如果队列为空则抛出一个NoSuchElementException异常 offer添加一个元素并返回true 如果队列已满则返回false poll移除并返问队列头部的元素 如果队列为空则返回null peek返回队列头部的元素 如果队列为空则返回null put添加一个元素 如果队列满则阻塞 take移除并返回队列头部的元素 如果队列为空则阻塞 drainTo(list)一次性取出队列所有元素
知识点 remove、element、offer 、poll、peek 其实是属于Queue接口。
四、高性能队列Disruptor
4.1、Disruptor简介
Disruptor是英国外汇交易公司LMAX开发的一个高性能队列研发的初衷是解决内存队列的延迟问题。与Kafka、RabbitMQ用于服务间的消息队列不同disruptor一般用于线程间消息的传递。基于Disruptor开发的系统单线程能支撑每秒600万订单。 disruptor适用于多个线程之间的消息队列作用与ArrayBlockingQueue有相似之处但是disruptor从功能、性能都远好于ArrayBlockingQueue当多个线程之间传递大量数据或对性能要求较高时可以考虑使用disruptor作为ArrayBlockingQueue的替代者。 官方也对disruptor和ArrayBlockingQueue的性能在不同的应用场景下做了对比目测性能只有有5~10倍左右的提升。
目前包括Apache Storm、Camel、Log4j2等等知名的框架都在内部集成了Disruptor用来替代jdk的队列以此来获得高性能。
Disruptor使用观察者模式, 主动将消息发送给消费者, 而不是等消费者从队列中取; 在无锁的情况下, 实现queue(环形, RingBuffer)的并发操作, 性能远高于BlockingQueue。
4.2、高性能原理
Disruptor为什么性能这么好呢主要依赖于以下四个特性
无锁设计CAS
采用CAS无锁方式保证线程的安全性。多线程环境下多个生产者通过do/while循环的条件CAS来判断每次申请的空间是否已经被其他生产者占据。假如已经被占据该函数会返回失败While循环重新执行申请写入空间。如果申请到之后直接在该位置写入或者读取数据。
ArrayBlockingQueue用了重量级lock锁在我们加锁过程中我们会把锁挂起解锁后又会把线程恢复这一过程会有一定的开销并且我们一旦没有获取锁这个线程就只能一直等待这个线程什么事也不能做。
CAS 更多知识见 Java 锁
RingBuffer : 环形数组
引入环形的数组结构这种固定大小的环形队列的另外一个好处就是可以做到完全的内存复用。在系统的运行过程中不会有新的空间需要分配或者老的空间需要回收大大减少系统分配空间及回收空间的额外开销避免频繁的GC同时数组对处理器的缓存机制更加友好。
[图片上传失败...(image-1650c4-1677132259413)] 元素位置的定位 数组长度强制要求一定是 2^n 这样可以通过位运算加快定位的速度。通过sequence (queueSize-1)就能立即定位到实际的元素位置index这比取余%操作快得多hashMap定位也是采用这种方式。 下标采取递增的形式不用担心index溢出的问题index是long类型即使100万QPS的处理速度也需要30万年才能用完。 消除伪共享 : 通过添加额外的无用信息避免伪共享问题 当CPU访问某一个变量时候首先会去看CPU Cache内是否有该变量如果有则直接从中获取否者就去主内存里面获取该变量然后把该变量所在内存区域的一个Cache行大小的内存拷贝到Cachecache行是Cache与主内存进行数据交换的单位。 由于存放到Cache行的的是内存块而不是单个变量所以可能会把多个变量存放到了一个cache行。当多个线程同时修改一个缓存行里面的多个变量时候由于同时只能有一个线程操作缓存行所以相比每个变量放到一个缓存行性能会有所下降这就是伪共享。 总之伪共享的产生是因为多个变量被放入了一个缓存行并且多个线程同时去写入缓存行中不同变量解决伪共享最直接的方法就是填充通过添加额外的无用信息避免伪共享问题。 如上图变量x,y同时被放到了CPU的一级和二级缓存当线程1使用CPU1对变量x进行更新时候首先会修改cpu1的一级缓存变量x所在缓存行这时候缓存一致性协议会导致cpu2中变量x对应的缓存行失效那么线程2写入变量x的时候就只能去二级缓存去查找这就破坏了一级缓存而一级缓存比二级缓存更快。更坏的情况下如果cpu只有一级缓存那么会导致频繁的直接访问主内存。我们的缓存都是以缓存行作为一个单位来处理的所以失效x的缓存的同时也会把y失效反之亦然。
4.3、Disruptor应用场景
参考使用到disruptor的一些框架.
log4j2
Log4j 2相对于Log4j 1最大的优势在于多线程并发场景下性能更优。该特性源自于Log4j 2的异步模式采用了Disruptor来处理。 Jstorm 在流处理中不同线程中数据交换数据计算可能蛮多内存中计算 流计算快进快出disruptor应该不错的选择。 百度uid-generator 部分使用ring buffer和去伪共享等思路缓存已生成的uid也部分参考了disruptor
经过测试Disruptor的速度比LinkedBlockingQueue提高了七倍。所以当你在使用LinkedBlockingQueue出现性能瓶颈的时候你就可以考虑采用Disruptor的代替。
