ring
更新于 2022-01-06
简介
dpdk内部实现的无锁队列
详见官网
技术要点
- CAS指令
- 索引范围0--2^n-1 无符号类型
组成
生产者/消费者头尾指针指向存在Ring里的数据
模式
| 简称 | 英文名 | ||
|---|---|---|---|
| SP/SC | Single-producer/consumer | 单线程出入队 | 32bit CAS |
| MP/MC | Multi-producer/consumer | 多线程出入队 | 32bit CAS |
| MP/MC_RTC | MP/MC with Relaxed Tail Sync | 位置(32bit)+引用(32bit) CAS | |
| MP/MC_HTC | MP/MC with Head/Tail Sync | 32bit CAS |
单生产者入队
生产者头指针(prod_head)和生产者尾指针(prod_tail)会被修改
开始前,ring->prod_head和ring->prod_tail指向相同的位置
入队第一步
将ring->prod_head和ring->cons_tail赋值给临时变量
临时指针prod_next指向存完数据(存一个或若干个数据)后的位置
如果没有足够的空间,则直接返回错误. 
入队第二步
将prod_next赋值给ring->prod_head
将存储对象加入到队列中 
入队第三步
数据入队完后,
将ring->prod_head赋值给ring->prod_tail
入队完成 
单消费者出队
只有消费者头指针(cons_head和消费者尾指针(cons_tail)会被修改
开始前,cons_head和cons_tail指向同样的位置.
第一步
将ring->cons_head和ring->prod_tail赋值给局部变量
临时指针cons_next指向读完数据(一个或若干个)后的位置
如果没有足够的数据,则直接放回失败 
第二步
将cons_next赋值给ring->cons_head
将数据拷贝到用户指针指向的地方 
第三步
数据拷贝完后,
将ring->cons_head赋值给ring->cons_tail
出队完成 
多生产者入队
两个生产者并发入队时,
只有生产者头尾指针(prod_head/cons_tail)会被修改
开始前,ring->prod_head和ring->cons_tail指向相同的位置
入队第一步
两个生产者分别将ring->prod_head和ring->cons_tail赋值给临时变量
临时指针prod_next指向存完数据(一个或若干个)后的位置
如果没有足够的空间,则直接返回错误. 
入队第二步
两个生产者分别通过Compare And Swap(CAS)指令将prod_next赋值给ring->prod_head,详细步骤如下:
- 如果
ring->prod_head和局部变量prod_head不同,则CAS操作失败;重复入队第一步操作*如果成功,局部变量prod_next赋值给ring->prod_head. 如下图所示:核一操作成功,核二操作失败
入队第三步
核二继续入队,并成功
核一插入数据obj4,核二插入数据obj5
入队第四步
两个核都尝试比较ring->prod_tail和局部变量prod_head,去更新ring->prod_tail
核一成功,核二失败
入队第五步
核二更新ring->prod_tail