无锁队列

去年在做一个项目时,遇到一个问题:需要处理一些数据,其输入速度是一定的,但输入的数据中只有一部分是实际需要处理,具体比例不一定,但希望能够保证实际处理数据的速度是一定的。所以,在这里用到了队列。首先对数据进行预处理,判断是否需要进行实际处理,如果需要则放入队列。同时还以一定的速率从队列取数据进行处理。这些操作都是在一个进程中,所以用 C 写了一个很简单的队列实现:基于共享内存,保证进程重启队列数据不会丢失;支持当队列满时自动 dump 到文件,使用文件作为存储。

最近又有一个这样的需求:一个进程产生数据放入队列,另一个进程判断队列长度,如果大于某一个值则进行处理,典型的“生产者 – 消费者”模型。这里就要求队列支持多进程,直接把之前写的队列拿来用会有问题,因为读和写队列可能同时进行,当两个进程同时修改某一个计数器时就可能会导致数据不一致。这里简单对队列进行加锁,即读和写是互斥的,就很容易的解决了这个问题。但在高并发时,读写互斥会带来性能上降低。之前公司内部看到有人分享过无锁队列的实现,研究了一下代码发现这个实现并不是真正的无锁队列,读写仍然是互斥的。

在参考了酷壳的文章:无锁队列的实现 之后,根据文章提供的思路,实现了一个无锁队列,它的要求是:

1、支持多进程(线程)同时对队列进行读写。

2、使用共享内存作为存储。

3、能够获取到当前队列的长度。

4 、兼容32位和64位系统

另外前题是:数据单元长度是固定的。

代码在此:https://github.com/haipome/lock_free_queue

大致的思路是:

在初始化时获取一大块内存自己分配,永不释放。将内存划分为控制区和数据区,数据区分成平均的数据块,每个数据块又有一个数据块头。通过数据块头,将队列中的数据组织成为链表。控制区里有两个“指针”分别指向链表的头和尾,这里并不能使用真正的指针,而是数据块的编号,使用 -1 标识链表的结束,为了解决队列在最开始时的初始化问题,所以这里多使用了一个编号为 -1 的数据块。另外,为了解决头尾指针指向同一数据块的问题,当 pop 时,读取的是头指针指向的数据块的下一个数据块,所以这里又多使用了一个数据块。

后记:多进程到处是坑,花了将近两天时间来 DEBUG

参考:

Legacy __sync Built-in Functions for Atomic Memory Access

发表评论

电子邮件地址不会被公开。 必填项已用*标注