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

接上篇设计4: 索引管理层 MpmcIndexQueue / CyclicIndexSubscriber存储数据使用的是queue是为了保证数据的读取顺序。MpmcLockFreeQueue为了满足多个进程同时写的情况采用了索引数据分离的方案底层的索引实现为MpmcIndexQueue。虽然已经将索引队列分为m_freeIndices空闲队列和m_usedIndices使用队列但是使用队列仍然需要考虑并发的问题。当进程A和进程B同时往m_usedIndices索引队列中写入index的时候m_usedIndices本身维护 r w指针同时有cells[capacity] 用保存index正常写入(push(index))的步骤为1. 将数据放入队列队列竞争cells[w].compare_exchange(index)2. 更新w指针指针竞争w.compare_cxchange(w1)【这里的w指针需要在数据写入后才能更新不然pop()时会出来脏数据】Iceoryx(冰羚) 使用CyclicIndex管理 r 、w 以及 value (value 为转换成CyclicIndex类型的index) 的原因解决队列竞争的问题。CAS正常情况A、B都想往cells[0]里存放自己手上的indexB成功了A失败A继续尝试往cells[1]写ABA情况A、B都想往cells[0]里存放自己手上的index假设A执行compare_exchange被挂起B先成功了由于B放入的数据与A中进行compare的数据一致结果compare_exchange后A也成功了A覆盖了B的数据具体的例子index2323cells[0]cells[1]cells[2]cells[3]假设 A进程想往cells[0]放入index4此时队列中存放的数据为2cells[0]是可以写入的里面是旧数据假设队列当前r w 为空队列里面的数据都是历史数据没有被清空current_w w.load() 假设w此时为4old_index cells[w] old_index 2)cells[w].compare_exchange(old_index,index1)若未执行这步进程被挂起。假设在A被挂起期间队列被放了数据又被取走了一轮 此时 w 8无cycle的场景 ❌ 写入index进程B想要放入index 2cell[8%4] 2进程B执行成功☑️B的数据刚放入未被消费。当前cells[8%4]中的数据是☑️有效的不该被改动A进程cells[4%4].compare_exchange(old_index,index1)成功cells[4%4] 中的2被覆盖成了4有cycle的场景 ✅ 写入value进程B想要放入index 2cycle w / capacity 8 / 4 2value index cycle * capacity 2 2 * 4 10cell[8%4] 10进程B执行成功☑️B的数据刚放入未被消费。当前cells[8%4]中的数据是☑️有效的不该被改动A进程cells[4%4].compare_exchange(old_index,index1)失败重新获取w继续尝试往cells[w%4]位置写入index 4 (实际写入的是valuevalue index cycle * capacity 4 2 * 4 12value index cycle * capacity所以cells中存放的其实不只是index而是 index cycle * capacity还是上面的例子假设012被其他进程占用未释放只有3一直被使用释放使用释放。假设当前已经是第2轮需要抢占第3个位置则 cells [11 % 4, 11 % 4 , 7 % 4, 7 % 4 ]若2 也参与竞争则是value 10 和 11 同时竞争 cells[2] (value 7)的位置这篇理解还挺难的主要还是要理解cells 竞争的 ABA 问题。