在编写并发程序的时候，经常要面对共享数据结构的保护问题。 虽然 C++ 提供的 RAII 实现的各种 guard lock 模式，早就让“忘记解锁” 导致的死锁成为历史。但是，锁带来的性能损耗依然是我们不得不面对的问题。
为了避免锁带来的开销，使用“无锁” 的数据结构似乎是个好主意。 然而事情的发展总是出乎所有人的意料。现代的多核CPU随着核数的越来越高，核与核之间的通信开销也变得越来越大。于是，所谓的“无锁” 容器，因为内部大量的“原子操作”变得越来越不适应于当前的时代。
不使用原子操作，又想大并发，又想安全，唯一能想到的，就只有“不修改” 了。 只读的数据，永远不需要锁的保护。这也是为何当下的程序员越来越青睐函数式编程。
然而，只有 const 没有 variable 的程序是根本不可能的。程序要运行，就得有变化。有变化，就不能使用只读的数据结构，不能只读，还是少不了要上锁。一锁，就离高性能大并发越来越远了。
有没有既可以修改，又可以无锁，还不需要使用原子操作的办法呢？
当然有啊，就是 RCU。但是 RCU 的局限性非常大，具体的来说就是，因为其赖以实现的原理导致了 RCU 只能是 list 容器。不能实现为更高效的 vector 和 hashmap 容器。
RCU 先修改 关联节点的 next/prev 指针，使得 后续的读者，会跳过当前要操作的节点，然后等待一段时间后， 释放节点。这样，读可以全速并发进行。无需任何锁的介入。而只有 list 容器，才能在不使用原子操作和锁的情况下，安全的 Detach 掉一个节点。map 容器，因为要对 tree 重新排序，无法实现成 RCU 操作。
即使 RCU 的读取速度再怎么好， list 就决定了，它在大元素量下注定的低性能。因此 rcu 即使在内核里，使用的也非常有限。只用在为数不多的 “读远大于写，而且容器元素不多” 的地方。
这个虽然不是 RCU 的问题，而是 list 的问题，但是 RCU 注定只能使用 list。
有没有办法让我最喜欢的 map/set/multiset/multimap/boost.multiindex 都能并发化呢？
一个数据结构，没有办法在修改的时候不上锁，主要原因就是他有“危险的中间态”。锁就是用来阻止其他线程访问危险的中间态的。
但是其实，不用锁也是有办法隔离掉危险的中间态的，就是 “Transaction”
如果对数据结构的多个修改，只有最终 commit 的时候， 才生效（其他线程才看的到），就不需要锁了。
使用 事务内存 就可以达成大并发，无锁，而且还不需要使用原子操作。
然而，如果没有事务内存又如何呢？其实，事务内存也是可以模拟的！今天要介绍的主角，就是在普通内存的机器上，为容器开启事务功能，达到使用事务内存一样的功效。
做法也很简单。就是使用2个容器 :smile:
假设要将一个 map 事务化， 设置一个当前指针 map* cur = new map; 然后，所有的读取操作，都在 *cur 上进行。
凡是要对 容器 做修改的时候， 先 map * alt = new map(*cur); 复制一份。 然后 alt 上进行修改。 改完了， cur = alt 赋值。搞定。
接着是对老容器的回收，这种情况下， 不能立即回收，因为可能还有其他线程在访问这个老容器。怎么办呢？ 就是 setTimeout(1000, delete oldmap);
总不会这么长时间了， 还有线程在访问吧 :wink:
Comments