ring¶

更新于 2022-01-06

简介¶

dpdk内部实现的无锁队列
详见官网

技术要点¶

CAS指令
索引范围0--2^n-1 无符号类型

组成¶

ring
生产者/消费者头尾指针指向存在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指向存完数据(存一个或若干个数据)后的位置
如果没有足够的空间,则直接返回错误. ring

入队第二步¶

将prod_next赋值给ring->prod_head
将存储对象加入到队列中 ring

入队第三步¶

数据入队完后,
将ring->prod_head赋值给ring->prod_tail
入队完成 ring

单消费者出队¶

只有消费者头指针(cons_head和消费者尾指针(cons_tail)会被修改
开始前,cons_head和cons_tail指向同样的位置.

第一步¶

将ring->cons_head和ring->prod_tail赋值给局部变量
临时指针cons_next指向读完数据(一个或若干个)后的位置
如果没有足够的数据,则直接放回失败 ring

第二步¶

将cons_next赋值给ring->cons_head
将数据拷贝到用户指针指向的地方 ring

第三步¶

数据拷贝完后,
将ring->cons_head赋值给ring->cons_tail
出队完成 ring

多生产者入队¶

两个生产者并发入队时,
只有生产者头尾指针(prod_head/cons_tail)会被修改
开始前,ring->prod_head和ring->cons_tail指向相同的位置

入队第一步¶

两个生产者分别将ring->prod_head和ring->cons_tail赋值给临时变量
临时指针prod_next指向存完数据(一个或若干个)后的位置
如果没有足够的空间,则直接返回错误. ring

入队第二步¶

两个生产者分别通过Compare And Swap(CAS)指令将prod_next赋值给ring->prod_head,详细步骤如下: * 如果ring->prod_head和局部变量prod_head不同,则CAS操作失败;重复入队第一步操作 *如果成功,局部变量prod_next赋值给ring->prod_head . 如下图所示:核一操作成功,核二操作失败 ring

入队第三步¶

核二继续入队,并成功
核一插入数据obj4,核二插入数据obj5 ring

入队第四步¶

两个核都尝试比较ring->prod_tail和局部变量prod_head,去更新ring->prod_tail
核一成功,核二失败
ring

入队第五步¶

核二更新ring->prod_tail
ring