Iceoryx(冰羚)：无锁队列与并发控制的设计与实现4（源码解析）

接上篇

总结一下1～3篇

设计1: SpscFifo（Single Producer Single Consumer First In Fisrt Out）

设计2: SpscSofi （Single Producer Single Consumer Stack Overflow Fisrt In First Out）

https://blog.csdn.net/hanyuan1993/article/details/159386614

设计3: MpmcLockFreeQueue （Multiple Producer Multiple Consumer）

https://blog.csdn.net/hanyuan1993/article/details/159424230

设计4: 索引管理层（ MpmcIndexQueue / CyclicIndex）

https://blog.csdn.net/hanyuan1993/article/details/159462305?spm=1001.2014.3001.5502

这3篇文章分析的都是Subscriber的Queue的实现，使用场景在这里也再总结一下：

• SpscFifo：单生产者单消费者，满等待
• SpscSofi：单生产者单消费者，满覆盖
• MpmcLockFreeQueue：多生产多消费者，可以满等待也可以满覆盖
• MpmcIndexQueue / CyclicIndex：MpmcLockFreeQueue 的索引层，解决了多生产者情况下的索引竞争问题（ABA）

但是concurrent里面还有一个MpmcLoFFLi实现没有说，这篇会解析完～～

补充 设计5: MpmcLoFFLi

Mempool的内存池管理，也是用索引和数据分离的方案来减少竞争，是维护了一个索引栈。与Subscriber的Queue不同，Subscriber取数据需要保留先进先出的顺序，但是Mempool不需要顺序执行。

数据结构：

Mempool的使用场景是，多进程pop拿到唯一的index，多进程push唯一的index；其实MpmcLockFreeQueue的设计也能满足Mempool的需求。但是Iceoryx(冰羚)的设计精妙的点在于利用了链表的结构。

• 如果使用普通的栈结构，则无法区分栈中存放的数据，栈里面可能是2221222，但索引栈里的数据只能唯一，即使是乱序，也应该只有一份，比如（2360145）。
• 链表很好的利用了数组的下标唯一的特点。链表状态下，push两个不同的index，存放的是数组[index1] 和数组[index2] 不会是同一块内存。（具体看例子理解）

Iceoryx(冰羚)的实践：数组先维护成链表，然后再由head来指向栈顶。

维护的成员变量：
m_head：indexToNextFreeIndex + abacounter

（指向栈顶， abacounter保证 CAS时不会出现 ABA 问题）

m_nextFreeIndex：数组

（从head中的indexToNextFreeIndex开始，将数组形成一张链表）

m_invalidIndex：11

（以下例子的假设数据）

m_size：10

（以下例子的假设数据）

m_head初始化：0 + 0
m_nextFreeIndex 初始化后：

使用了[0], [1], [2], [3] 后:

m_head：indexToNextFreeIndex（4） + abacounter（4）

m_nextFreeIndex 当前状态：

假设先还回来0:

m_head：indexToNextFreeIndex（0） + abacounter（5）

m_nextFreeIndex 当前状态：

假设再还回来2:

m_head：indexToNextFreeIndex（2） + abacounter（6）

m_nextFreeIndex 当前状态：

此时pop，index为2：

m_head：indexToNextFreeIndex（0） + abacounter（7）

m_nextFreeIndex 当前状态：

pop逻辑：

• 移动 head > new_head (CAS + ABA)
• 拿出 head里面的index

current_head = m_head.load() do { new_head = m_nextFreeIndex[current_head.index] new_head.abacounter = current_head.abacounter + 1 } while(m_head.compare_exchange(current_head, new_head)) index = current_head.indexToNextFreeIndex current_head.index = m_invalidIndex

push逻辑：

• 先建立 m_nextFreeIndex 队列中，当前index的值的链接 m_nextFreeIndex[index] = head.indexToNextFreeIndex
• 创建 new_head
• 移动 head > new_head (CAS, ABA)

current_head = m_head.load() do { m_nextFreeIndex[index] = current_head.indexToNextFreeIndex new_head.index = index new_head.abacounter = current_head.abacounter + 1 } while(m_head.compare_exchange(current_head, new_head))

MpmcLoFFLi、MpmcLockFreeQueue 对比：

链表这个设计确实很精妙～学到了～