这是一个创建于 3707 天前的主题，其中的信息可能已经有所发展或是发生改变。
在写程序的时候，见到一个蛮巧妙的思路（一写者，多读者）：
维持两块内存，A1、A2，代表同一个对象
假如一开始读A1，那么就写A2，写完以后置一个标志位，让读写者倒换，也即之后的读者就读A2了，而写者写A1。
有人见过类似的思路吗？它是否有一个名字？
我想了很久，只觉得它很类似read-copy-update，但RCU在用户态用起来好像有点麻烦。不知道有没有更方便的实现？
维持两块内存，A1、A2，代表同一个对象
假如一开始读A1，那么就写A2，写完以后置一个标志位，让读写者倒换，也即之后的读者就读A2了，而写者写A1。
有人见过类似的思路吗？它是否有一个名字？
我想了很久，只觉得它很类似read-copy-update，但RCU在用户态用起来好像有点麻烦。不知道有没有更方便的实现？
 |
1
isayme 2014-09-15 15:57:14 +08:00
还在 读A1的时候 进行 读写者倒换 怎么办?
这种情况, 还是老老实实加个读写锁吧. |
 |
2
yuelang85 2014-09-15 15:59:03 +08:00
这种思路很多人都做过。你这个还欠一个 二者数据同步机制。
我也不知叫啥，求答案。 哦，对了，mysql有一种常见做法，叫“读写分离”，跟你的有些出入，他是不互换角色，而是只从”从库“读取，只写入到”主库“，从库定期从主库同步数据。 |
 |
4
shoumu 2014-09-15 16:21:15 +08:00
A1和A2的数据同步还是涉及到同步问题了啊？
|
 |
5
zhangdawei 2014-09-15 16:28:23 +08:00
linux中，内核里面有个“读写自旋锁”，
http://os.chinaunix.net/a2006/0909/1003/000001003383.shtml 可以参考下，linux内核里面考虑读写、异步、死锁、原子操作这些功能想了很多招。 |
 |
6
Mutoo 2014-09-15 16:47:04 +08:00
|
 |
7
alexapollo OP @yuelang85
@shoumu 恩，这块是定期刷配置用的，无状态，所以还比较简单，不用考虑数据同步 @zhangdawei 就是觉得rwlock性能稍微差一些（在我这场景里），所以想换个lock-free的方法 |
 |
8
nelson 2014-09-15 20:32:00 +08:00
弄个二值变量就可以了吧。。
变量=A，reader读A；writer要写的话写B，写完将变量置为B；变量=B反之。 就是有可能reader会读到上次的数据，但可以保证不会读到脏数据 |
 |
9
ETiV 2014-09-15 20:39:24 +08:00 via iPhone
OpenGL 里叫双 buffer
当前显示的显存区域就是LZ说的读 另外后台渲染的显存区域就是用来写的了 然后等待屏幕垂直刷新更新完成后（垂直同步），交换两个buffer的指针…… |
 |
10
semicircle21 2014-09-15 21:51:53 +08:00
这个思路有限制, 可能是你描述的不完整, 我觉得不是完全无锁的, 就是写线程换 A/B 的时机, 需要和读操作同步. 假设1读 1写:
1) 读线程 读到标志A1 2) 写线程 切换到标志 A1 3) 写线程 写入到 A1 区域 4) 读线程 从 A1 读入脏数据 对 A/B 这个标志位的访问还是需要用锁控制的. |
 |
11
SoloCompany 2014-09-15 22:02:43 +08:00
copy-on-write-modification
和你说的类似，只不过 CPW 是即抛型 但你确定，如果不用拷贝，你的双缓存状态怎么保持一致？ 附 wiki 参考 http://en.wikipedia.org/wiki/Copy-on-write |
|
12
alexapollo OP  1
@nelson 二值变量？没有搜到相关的资料，有没有相关阅读？思路就是这个。
@ETiV 恩，你说的这个就是标准RCU了。但看起来更像是1读1写的场景，会简化一些。 @semicircle21 1) 读线程 读到标志A1 2) 写线程 写A2 3) 写线程 写完后切换读标志为A2 4) 读线程 第二次读，从A2开始读取 5) 写线程 第二次写，从A1开始写 |
|
13
alexapollo OP @semicircle21 仔细想了一下，是有道理的，这个模型可能存在隐患。
1) 读线程读A1过程中，被调度给写线程 2) 写线程串行无打断写了一次A2，切换标志，下次写A1读A2 3) 写线程写A1开始，被调度走 3) 读线程还在读A1，调度回来了，此时A1是脏数据 |
 |
14
pright 2014-09-16 00:11:36 +08:00
@alexapollo 变量只允许读线程切换，就没这个问题。不过这种方案只适合单读单写，不然还得加锁。这个其实就是简化的ring buffer。
|
|
15
alexapollo OP @pright 理解你的想法，多读者时，可能存在部分读者读A1，部分读A2的场景，这个场景无法写入
那么用ring的角度来看，还是有可行方法的（近似），假设一个数组 A[N]，0是初始cursor，有个bitmap表示数组哪些项被读者占用了，每次写的时候，尝试寻找未被占用的A[i]，如果找到了，那么就update，并且令cursor=i，这样在N足够大时，风险是比较小的，注意这里要保持服务有损，也即如果所有A[i]都被读者占用时，返回错误 |
|
16
alexapollo OP @SoloCompany 之前研究过一段COW，但不是很理解。它讲的是程序需要修改某个变量时，就自己复制一份，然后改掉自己用。这个过程可以保护其他线程不受影响，但我需要的是修改这个变量，全局的，最后必须要所有线程都感知到它的修改。
|
|
17
pright 2014-09-16 00:31:21 +08:00
@alexapollo 倒是不存在读者读不同区域的问题，因为标志为A1，肯定大家都是读A1，主要问题是无法断定什么时候该切换标志为A2了，除非读者个数是确定的。
ring buffer的一般实践是用读写指针的，保证写指针不越过读指针，在单读单写情况下可以无锁。 |
|
18
SoloCompany 2014-09-16 01:15:36 +08:00 via iPad
@改完之后当然需要回写，当然回写的时候野生需要锁得，只是锁的粒度就小多了，另外你的语言支持 violate 关键字之类的语义的话（如java），是可以无锁的，如果对状态一致性有要求，可以增加修改计数器来判断是否有并发写入，在发现有并发写的时候重新执行cow过程
|
|
19
alexapollo OP @pright 我们的思路不同。我的思路是，在写者写完之后置换标志，此时如果置读标志为A1，那么之后都会读A1，但可能有部分读者还在读A2，没有完成操作。
我不是很理解你的思路，能不能详细讲讲？ |
|
20
alexapollo OP @SoloCompany 使用C++。C里有violate关键字，但我没有用过。似乎它很少被使用。
是的，我明白你的意思，可以用rwlock配合来一个很短时间的锁：一个赋值过程的锁。 有道理。之前我也有类似的思路，你这么一说就理顺了，多谢啦~ |
 |
21
xylophone21 2014-09-16 09:26:24 +08:00
|
 |
22
WKPlus 2014-09-16 12:56:08 +08:00
见过很多这类应用，双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就不会发生，因此也就可以无锁了。 |
|
23
semicircle21 2014-09-16 13:43:02 +08:00
@alexapollo 是的, 应用这个思路要有一些前提的, 我又想了一下, 对标志位加锁也不能保证不读到脏数据. 关键是改标志位的时候, 要有前提条件或机制保证此时没有正在读的线程.
我感觉, 一般无锁/同步问题都是具体问题具体分析的, 有一些常用的 Pattern, 但能直接用上的很少. 因为涉及到的细节很多, 比如时间短的操作, 在kernel 里可以关中断自旋锁来保证同步, 但在多处理器场景又不行了, 然后还要保证访问的内存是已经在 cache 里的, 否则怎么也不会是"时间短的"... 所以, 针对一般情况, 如果仅仅是追求数据吞吐量, Share information by queue, 比 memory 靠谱多了. |
 |
24
glogo 2014-09-16 20:43:47 +08:00
那标志位的读写不需要同步吗
|
|
25
nelson 2014-09-17 23:52:30 +08:00
@alexapollo 其实就是i = (i + 1) % 2
不过这种方法确实会像LSSS+说的，读A的过程中连续写了两次数据（B、A），会导致读到脏数据 |
 |
26
pslydhh 2021-01-29 13:02:30 +08:00
用户态 RCU 哪里有资料介绍吗
|
Select Language