关键字： 双向循环链表 + 生产/消费 + 多线程 + 锁

留痕之雁

{:3_193:} 有技术的地方就有牛老师

JohnBull 发表于 2010-03-29 16:53
无锁是不大可能的，但可以看上去无锁。
利用socket把一个链表做成一个服务器线程，接受-响应操作请求。这样 ...

shanehan

明显应该用环形队列嘛，数据结构应该就是一个固定长度的数组，但环形队列是有最大长度的。
或者是一个环形队列外加一个链表，需要生产者负责把链表中的数据带到环形队列中，可以做到无锁并且boundless。

shanehan

huangyacong 发表于 2012-05-31 09:41
’只有一个生产者、一个消费者来操作链表，不需要加锁‘
搞了那么久程序，从来没见过这钟实现，目前这种实 ...

这个真不是口号，生产环境很多在用的。

huangyacong

回复 23# shanehan
问题是，使用了锁了吗？多线程下，锁太难去掉的。或者在这种情况下，使用了原子锁。就是那个给一个整形数加锁的函数，具体忘记那个函数了


   

shanehan

回复 24# huangyacong


这帖子不就是讨论 一个生产者一个消费者，一对一的情况吗？一对一可以不用锁

huangyacong

回复 25# shanehan
对，一个生产者，一个消费者，不使用链表，使用定长数组。不加锁？


   

huangyacong

回复 25# shanehan
不加锁，如何保证那个True变量正确定。


   

shanehan

huangyacong 发表于 2012-05-31 18:22
回复 25# shanehan
对，一个生产者，一个消费者，不使用链表，使用定长数组。不加锁？

你google或百度下“环形队列 无锁”，很多的，只不过搜索出来的可能并没有做成缓冲区形式的，虽然是一个长数组，可能每个元素是结构（一个长度，一个指针）或者是C++对象，所以叫队列，如果要做成缓冲区形式的，就是麻烦一些，需要自己处理环形缓冲区的边界问题。

huangyacong

回复 28# shanehan
其实那些我看过了，都是理论，实现的，能用的代码没有找到。
有个问题，对于这种一个生产者和一个消费者来说，共同访问一个内存，那么应该需要访问一个变量T，看看这个变量的值再做修改。
问题是，你改，我读，不能保证原子执行，那么可能读到脏的数据。那么这种无锁结果如何实现的了呢？或者说即使实现了，那么也是有条件的。

shanehan

huangyacong 发表于 2012-05-31 18:37
回复 28# shanehan
其实那些我看过了，都是理论，实现的，能用的代码没有找到。
有个问题，对于这种一个 ...

其实也就是两个变量的问题嘛，一个read_index，一个write_index。
先要保证read_index一直是在追write_index的条件下（也就是read_index一定不能超过write_index），然后
1. 只要保证读取操作结束的最后一步是改变read_index的值，那么写入方在使用read_index时就不会出现问题。
2. 反过来也一样，只要保证写入操作结束的最后一步去改变write_index的值，读取方使用write_index时就没有问题。

一个写变量，一个读变量，只有写生效的时候，读才是最新值，不然永远是上一次的值。