这里的队列并不是指Node结构的队列,而是使用数组的形式模拟的环型队列结构。
无锁高并发框架disruptor使用到了RingBuffer
为什么要采用数组
因为数组具有缓存优化的特性。缓存优化:CPU有L1、L2、L3缓存,CPU获取数据的顺序 寄存器 -> L1缓存 -> L2缓存 -> L3缓存 -> 主存,当运行程序的时候CPU会把当前变量邻近的变量一块放入缓存中,当读取数组的某个值时,数组后面的元数也会被读入缓存中。
cursor的计算
RingBuffer是定长的数组,当数组存满后再次插入就得从头开始,那么存入环型队列的第n个元素它的索引如何计算?
cursor = sequence % length
比如RingBuffer的length = 8, 则第9个元数存放的位置cursor = 9 % 8 = 1
如果规定length的长度为2的冥次方,则索引可使用更高效的位运算:
cursor = sequence & (length - 1)
这个位运算是怎么来的:
首先 length - 1:
21 的二进制 10 21 - 1 的二进制 1
22 的二进制 100 22 - 1 的二进制 11
23 的二进制 1000 23 - 1 的二进制 111
如果RingBuffer的长度为23=8,计算第9个元数的cursor:
9 & ( 8 - 1)
把9转换成二进制:1001, 1001 & 111 = 1