多线程无锁队列实现思路

本文是基于单生产者单消费者线程的实现。

struct {

char buf[65536];

unsigned short writer_index;

unsigned short reader_index;

}

reader_index只由读线程改变,writer_index只由写线程改变。

读线程读取reader_index到writer_index之间的数据,读取完毕向前移动reader_index。发现writer_index小于reader_index,读线程读取数据直到队列结尾,并将reader_index移到队列开头,继续读取。

写线程计算检查可用写空间,将数据写入,并移动writer_index。当写到队列结尾,将writer_index移动到队列开头,再从头开始写。

读线程看到的writer_index不一定是最新的,但不会导致读取错误数据,只是会比应该读取的少读一些。

写线程看到的reader_index不一定是最新的,但不会导致写入错误,只是会比应该写入的少写一些。

需要注意的是cpu对指令的乱序执行以及cpu间cache同步乱序问题。

1.cpu完全可以先将写指针移动,然后再写入数据,这样的执行顺序对于单线程没有任何影响。对于我们现在这种模型,读线程就有机率读取到错误的数据。同样读线程先执行读指针移动,后读取数据,会有机率导致还没有读出的数据被写线程写入覆盖。

2.cpu间数据同步数据可能乱序。比如cpu1修改了a和b,同步给cpu2,a和b到达cpu2的顺序不确定。如果读线程写线程分处于两个不同cpu执行,有机率出现1问题中同样的错误,即读线程先看到了写指针的改变,并读取了还没有被写入的脏数据。

解决方法就是给cpu使绊,使用memory barrier(内存屏障)让cpu必须顺序执行指令,并保证同步顺序。关于memory barrier的用法可以自行google,也可以关注我的下一篇关于内存屏障的使用介绍。

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容