shared_ptr的线程安全性
近期在网上冲浪时看到一篇boost的文章，里面聊到了shared_ptr的线程安全性
据原文所说，shared_ptr的线程安全性与c++中的容器是一致的。比如说std::map，你可以多线程访问，但是多个线程不能同时析构它，不能同时修改它。同样，shared_ptr可以多线程读，但是不能多线程析构，不能够多线程修改。这里说的shared_ptr是shared_ptr这个class本身的线程安全性与c++的其他容器是一致的，而不是shared_ptr所指向的对象。
一个shared_ptr至少包含了这几个成员：weak_count, ref_count, object_ptr。两个count都是原子类型的，所以对他们递增或递减是不存在多线程问题的。
更准确的说，一个shared_ptr的成员大概是这样的：
template <typename T> class shared_ptr { T *object_ptr; struct Count { atomic_int weak_count, ref_count; }; Count *counts; }; 但是！众所周知，多线程线程安全性是不可组合的，所以这里两个原子操作，一旦混合起来就无法确保线程安全性。以前文链接中的example6为例子：
// 注意，这里p3是一个全局变量，所以可以被两个线程访问。 // thread A p = p3; // reads p3, writes p // thread B p3.reset(); // writes p3; undefined, simultaneous read/write 这里p3.reset包含2个操作，两个都不是原子的，即object_ptr = nullptr, counts = nullptr。这里假定p3的ref_count是1，weak_count=0，那么如果说example6的执行顺序是这样的：
- thread A检查了counts->ref_count，发现不是0
- thread B调用reset，发现ref_count==1，所以析构了object_ptr，并设置其为nullptr
- thread A设置了counts = p3.counts
- thread B由于ref_count1, weak_count0, 释放了counts
- thread A尝试递增counts，完蛋了
有一个推荐的做法，即：
void ThreadFunc(shared_ptr p) { shared_ptr local_copy; { lock_guard guard{mutex}; local_copy = p; } // 继续操作local_copy ...... } 这样做就符合了shared_ptr的线程安全性了。
cmu15445 Copy On Write的线程安全字典树(trie)
到这里忽然想到了之前做cmu15445的project0的时候也有不少用上shared_ptr的地方，所以想着回顾一下代码，看看有没有什么地方我忽略了线程安全性问题。
首先先介绍一下这个字典树的实现吧。
首先，它使用shared_ptr实现一个线程不安全的trie。假定一开始的trie是这样的：
然后我给插入了一个"ad"，那么它会连着root一起复制一遍shared_ptr，原来的trie如虚线所示，新的trie则是蓝色部分：
可以看出，trie是从根开始，一路复制shared_ptr到需要修改的地方的。至于删除则类似。
那么这个trie的线程安全性如何？
看起来都是对原来的trie的读取，包括对shared_ptr的读取操作和每个节点的map<char,shared_ptr>的读取，所有的修改都只是在复制之后的副本上进行修改的。这样一来，只要保证初始被多个线程共享的root这个shared_ptr不会析构即可，这里可以用上前面推荐的操作：
struct Guard { shared_ptr<TrieNode> guard; // 为了减少代码，这里用void *这种形式来表现一个值 void *value; } shared_ptr<TrieNode> root; // 这个Get操作有点MVCC的味道，都是读取的时候不会锁住所有写入操作的，都是可以访问历史版本的。 Guard Get(string_view sv) { shared_ptr local_copy; { lock_guard lock{mutex}; local_copy = root; } return Guard{local_copy, local_copy->Get(string_view key)}; } shared_ptr<TrieNode> Put(string_view key, void *value) { shared_ptr local_copy; { lock_guard lock{mutex}; local_copy = root; } // 这里的put就是前面说的从根开始进行了复制，直到被修改的地方的操作。 return local_copy->Put(key, value); } 这样一来线程安全就已经做到了，所有写入都可以做到写时复制。但是奇怪的是为什么project0要求我用一个写锁？
后面看了当时写的代码才想起来，原来project0要求实现的是对前面的线程安全版本的封装，即：
class TrieStore { ...... shared_ptr<TrieNode> Put(string_view key, void *value) { lock_guard lock{write_lock}; shared_ptr local_copy; { lock_guard lock{mutex}; local_copy = root; } root = local_copy->Put(key, value); } Guard Get(string_view sv) { shared_ptr local_copy; { lock_guard lock{mutex}; local_copy = root; } return Guard{local_copy, local_copy->Get(string_view key)}; } } trie_store; void ThreadFunc() { // 给trie_store放入1到65536的key，value都是old+key的形式，比如说1的value是old1,54321的是old54321 // 给trie_store移除1到65536 // 给trie_store放入1到65536，value都是new+key的形式 } void Test() { // 起n个线程，每个线程都执行ThreadFunc // 检查是否有1到65535，每个键是否都是new+key的形式 } 要确保每一个修改都最终可以通过trie_store这个对象确认到，但是所有读取操作都不能被阻塞，所以里面的Put操作需要上一个写锁。
