一个无锁编程的问题

[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配合来一个很短时间的锁：一个赋值过程的锁。

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

[xylophone21]

可以看一下Linux内核里的ringbuf

http://www.cs.fsu.edu/~baker/devices/lxr/http/source/linux/kernel/kfifo.c

[WKPlus]

见过很多这类应用，双buffer切换呀，应用场景是这样的：
1.多线程服务端程序，使用本地文件作为词表，有一个线程专门来检查文件是否更新，检测到更新之后，需要把新文件load到内存中的
2.每次前端有请求过来的时候，使用内存中的词表做查询，对内存中的词表只要求完整性（即不能使用更新了一半的词表），但是及时性要求不是那么高

所以做法就如题主所说，开了两个buffer，在读buffer 0的时候就写buffer 1，写完之后更新读buffer的标识（原子操作）即可。

这里其实有一个race condition：
如果有线程在读buffer 0，然后buffer 1写完成了，标识读buffer为1，又检测到更新开始写buffer 0，如果原来读buffer 0的线程还没有结束，就可能出现数据不完整的情况。

但在实际上，是不会发生的，因为每次更新完文件之后，至少要等待5min才会去检测文件是否更新，而我们服务最长的请求处理时间不会有5min这么长，所以上面的race condition就不会发生，因此也就可以无锁了。

[semicircle21]

@alexapollo 是的, 应用这个思路要有一些前提的, 我又想了一下, 对标志位加锁也不能保证不读到脏数据. 关键是改标志位的时候, 要有前提条件或机制保证此时没有正在读的线程.
我感觉, 一般无锁/同步问题都是具体问题具体分析的, 有一些常用的 Pattern, 但能直接用上的很少. 因为涉及到的细节很多, 比如时间短的操作, 在kernel 里可以关中断自旋锁来保证同步, 但在多处理器场景又不行了, 然后还要保证访问的内存是已经在 cache 里的, 否则怎么也不会是"时间短的"...
所以, 针对一般情况, 如果仅仅是追求数据吞吐量, Share information by queue, 比 memory 靠谱多了.

[glogo]

那标志位的读写不需要同步吗

[nelson]

@alexapollo 其实就是i = (i + 1) % 2
不过这种方法确实会像LSSS+说的，读A的过程中连续写了两次数据（B、A），会导致读到脏数据

[pslydhh]

用户态 RCU 哪里有资料介绍吗