一个无锁编程的问题

[alexapollo]

在写程序的时候，见到一个蛮巧妙的思路（一写者，多读者）：
维持两块内存，A1、A2，代表同一个对象
假如一开始读A1，那么就写A2，写完以后置一个标志位，让读写者倒换，也即之后的读者就读A2了，而写者写A1。

有人见过类似的思路吗？它是否有一个名字？
我想了很久，只觉得它很类似read-copy-update，但RCU在用户态用起来好像有点麻烦。不知道有没有更方便的实现？

[isayme]

还在 读A1的时候 进行 读写者倒换 怎么办?
这种情况, 还是老老实实加个读写锁吧.

[yuelang85]

这种思路很多人都做过。你这个还欠一个 二者数据同步机制。

我也不知叫啥，求答案。

哦，对了，mysql有一种常见做法，叫“读写分离”，跟你的有些出入，他是不互换角色，而是只从”从库“读取，只写入到”主库“，从库定期从主库同步数据。

[yuelang85]

@isayme 下一个请求才切换。

[shoumu]

A1和A2的数据同步还是涉及到同步问题了啊？

[zhangdawei]

linux中，内核里面有个“读写自旋锁”，
http://os.chinaunix.net/a2006/0909/1003/000001003383.shtml
可以参考下，linux内核里面考虑读写、异步、死锁、原子操作这些功能想了很多招。

[Mutoo]

这个叫 double-buffer 吧

http://gameprogrammingpatterns.com/double-buffer.html
参见最后 see also 上面的例子

[alexapollo]

@yuelang85
@shoumu
恩，这块是定期刷配置用的，无状态，所以还比较简单，不用考虑数据同步
@zhangdawei
就是觉得rwlock性能稍微差一些（在我这场景里），所以想换个lock-free的方法

[nelson]

弄个二值变量就可以了吧。。
变量=A，reader读A；writer要写的话写B，写完将变量置为B；变量=B反之。
就是有可能reader会读到上次的数据，但可以保证不会读到脏数据

[ETiV]

OpenGL 里叫双 buffer

当前显示的显存区域就是LZ说的读
另外后台渲染的显存区域就是用来写的了

然后等待屏幕垂直刷新更新完成后（垂直同步），交换两个buffer的指针……

[semicircle21]

这个思路有限制, 可能是你描述的不完整, 我觉得不是完全无锁的, 就是写线程换 A/B 的时机, 需要和读操作同步. 假设1读 1写:
1) 读线程 读到标志A1
2) 写线程 切换到标志 A1
3) 写线程 写入到 A1 区域
4) 读线程 从 A1 读入脏数据
对 A/B 这个标志位的访问还是需要用锁控制的.

[SoloCompany]

copy-on-write-modification
和你说的类似，只不过 CPW 是即抛型

但你确定，如果不用拷贝，你的双缓存状态怎么保持一致？

附 wiki 参考 http://en.wikipedia.org/wiki/Copy-on-write

[alexapollo]

@nelson 二值变量？没有搜到相关的资料，有没有相关阅读？思路就是这个。
@ETiV 恩，你说的这个就是标准RCU了。但看起来更像是1读1写的场景，会简化一些。
@semicircle21
1) 读线程 读到标志A1
2) 写线程 写A2
3) 写线程 写完后切换读标志为A2
4) 读线程 第二次读，从A2开始读取
5) 写线程 第二次写，从A1开始写

[alexapollo]

@semicircle21 仔细想了一下，是有道理的，这个模型可能存在隐患。
1) 读线程读A1过程中，被调度给写线程
2) 写线程串行无打断写了一次A2，切换标志，下次写A1读A2
3) 写线程写A1开始，被调度走
3) 读线程还在读A1，调度回来了，此时A1是脏数据

[pright]

@alexapollo 变量只允许读线程切换，就没这个问题。不过这种方案只适合单读单写，不然还得加锁。这个其实就是简化的ring buffer。

[alexapollo]

@pright 理解你的想法，多读者时，可能存在部分读者读A1，部分读A2的场景，这个场景无法写入

那么用ring的角度来看，还是有可行方法的（近似），假设一个数组 A[N]，0是初始cursor，有个bitmap表示数组哪些项被读者占用了，每次写的时候，尝试寻找未被占用的A[i]，如果找到了，那么就update，并且令cursor=i，这样在N足够大时，风险是比较小的，注意这里要保持服务有损，也即如果所有A[i]都被读者占用时，返回错误

[alexapollo]

@SoloCompany 之前研究过一段COW，但不是很理解。它讲的是程序需要修改某个变量时，就自己复制一份，然后改掉自己用。这个过程可以保护其他线程不受影响，但我需要的是修改这个变量，全局的，最后必须要所有线程都感知到它的修改。

[pright]

@alexapollo 倒是不存在读者读不同区域的问题，因为标志为A1，肯定大家都是读A1，主要问题是无法断定什么时候该切换标志为A2了，除非读者个数是确定的。

ring buffer的一般实践是用读写指针的，保证写指针不越过读指针，在单读单写情况下可以无锁。

[SoloCompany]

@改完之后当然需要回写，当然回写的时候野生需要锁得，只是锁的粒度就小多了，另外你的语言支持 violate 关键字之类的语义的话（如java），是可以无锁的，如果对状态一致性有要求，可以增加修改计数器来判断是否有并发写入，在发现有并发写的时候重新执行cow过程

[alexapollo]

@pright 我们的思路不同。我的思路是，在写者写完之后置换标志，此时如果置读标志为A1，那么之后都会读A1，但可能有部分读者还在读A2，没有完成操作。
我不是很理解你的思路，能不能详细讲讲？

[alexapollo]

@SoloCompany 使用C++。C里有violate关键字，但我没有用过。似乎它很少被使用。
是的，我明白你的意思，可以用rwlock配合来一个很短时间的锁：一个赋值过程的锁。

有道理。之前我也有类似的思路，你这么一说就理顺了，多谢啦~