DPDK无锁环形缓冲区

环形缓冲区支持队列管理。rte_ring并不是具有无限大小的链表，它具有如下属性：

• 先进先出（FIFO）
• 最大大小固定，指针存储在表中
• 无锁实现
• 多消费者或单消费者出队操作
• 多生产者或单生产者入队操作
• 批量出队 - 如果成功，将指定数量的元素出队，否则什么也不做
• 批量入队 - 如果成功，将指定数量的元素入队，否则什么也不做
• 突发出队 - 如果指定的数目出队失败，则将最大可用数目对象出队
• 突发入队 - 如果指定的数目入队失败，则将最大可入队数目对象入队

相比于链表，这个数据结构的优点如下：

• 更快；只需要一个sizeof(void *)的Compare-And-Swap指令，而不是多个双重比较和交换指令
• 与完全无锁队列像是
• 适应批量入队/出队操作。因为指针是存储在表中的，适应多个对象的出队将不会产生于链表队列中一样多的cache miss。此外，批量出队成本并不比单个对象出队高。

缺点：

• 大小固定
• 大量ring相比于链表，消耗更多的内存，空ring至少包含n个指针。

数据结构中存储的生产者和消费者头部和尾部指针显示了一个简化版本的ring。

两个生产者同时向ring中添加对象的情况，初始状态是将prod_head 和 prod_tail 指向相同的位置：

第一步：

在生产者的两个core上， ring->prod_head 及 ring->cons_tail 都被复制到局部变量。局部变量prod_next指向下一个元素，或者在批量入队的情况下指向下几个元素。

如果ring中没有足够的空间用于入队(通过检查cons_tail)，将返回错误。

第二步：

第二步是修改ring结构中 ring->prod_head ，来指向prod_next相同的位置。此操作使用比较和交换(CAS)指令，该指令以原子操作的方式执行以下操作：

• 如果ring->prod_head 与本地变量prod_head不同，则CAS操作失败，代码将在第一步重新启动。
• 否则，ring->prod_head设置为本地变量prod_next，CAS操作成功并继续下一步处理。

在图中，core1执行成功，core2重新启动。

第三步：

第四步：

每个core现在都想更新 ring->prod_tail。只有ring->prod_tail等于prod_head本地变量，core才能更新它。当前只有core 1满足，操作在core 1上完成。

最后一步：

一旦ring->prod_tail被core 1更新完，core 2也满足条件，允许更新。Core 2上也完成了操作。