shared_ptr的线程安全性与再论cmu15445 project0的COW线程安全字典树 ...

shared_ptr的线程安全性

近期在网上冲浪时看到一篇boost的文章，里面聊到了shared_ptr的线程安全性
https://www.boost.org/doc/libs/1_87_0/libs/smart_ptr/doc/html/smart_ptr.html#shared_ptr_thread_safety
据原文所说，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的成员大概是这样的：

1. template <typename T>
2. class shared_ptr {
3.   T *object_ptr;
4.   struct Count {
5.     atomic_int weak_count, ref_count;
6.   };
7.   Count *counts;
8. };

复制代码

但是！众所周知，多线程线程安全性是不可组合的，以是这里两个原子操作，一旦混合起来就无法确保线程安全性。以前文链接中的example6为例子：

1. // 注意，这里p3是一个全局变量，所以可以被两个线程访问。
2. // thread A
3. p = p3; // reads p3, writes p
5. // thread B
6. 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，完蛋了
  

有一个推荐的做法，即：

1. void ThreadFunc(shared_ptr p) {
2.   shared_ptr local_copy;
3.   {
4.     lock_guard guard{mutex};
5.     local_copy = p;
6.   }
7.   // 继续操作local_copy
8.   ......
9. }

复制代码

这样做就符合了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的读取，所有的修改都只是在复制之后的副本上举行修改的。这样一来，只要保证初始被多个线程共享的root这个shared_ptr不会析构即可，这里可以用上前面推荐的操作：

1. struct Guard {
2.   shared_ptr<TrieNode> guard;
3.   // 为了减少代码，这里用void *这种形式来表现一个值
4.   void *value;
5. }
6. shared_ptr<TrieNode> root;
7. // 这个Get操作有点MVCC的味道，都是读取的时候不会锁住所有写入操作的，都是可以访问历史版本的。
8. Guard Get(string_view sv) {
9.   shared_ptr local_copy;
10.   {
11.     lock_guard lock{mutex};
12.     local_copy = root;
13.   }
14.   return Guard{local_copy, local_copy->Get(string_view key)};
15. }
16. shared_ptr<TrieNode> Put(string_view key, void *value) {
17.   shared_ptr local_copy;
18.   {
19.     lock_guard lock{mutex};
20.     local_copy = root;
21.   }
22.   // 这里的put就是前面说的从根开始进行了复制，直到被修改的地方的操作。
23.   return local_copy->Put(key, value);
24. }

复制代码

这样一来线程安全就已经做到了，所有写入都可以做到写时复制。但是奇怪的是为什么project0要求我用一个写锁？
背面看了当时写的代码才想起来，原来project0要求实现的是对前面的线程安全版本的封装，即：

1. class TrieStore {
2.   ......
3.   shared_ptr<TrieNode> Put(string_view key, void *value) {
4.     lock_guard lock{write_lock};
5.     shared_ptr local_copy;
6.     {
7.       lock_guard lock{mutex};
8.       local_copy = root;
9.     }
10.     root = local_copy->Put(key, value);
11.   }
12.   Guard Get(string_view sv) {
13.     shared_ptr local_copy;
14.     {
15.       lock_guard lock{mutex};
16.       local_copy = root;
17.     }
18.     return Guard{local_copy, local_copy->Get(string_view key)};
19.   }
20. } trie_store;
21. void ThreadFunc() {
22.   // 给trie_store放入1到65536的key，value都是old+key的形式，比如说1的value是old1,54321的是old54321
23.   // 给trie_store移除1到65536
24.   // 给trie_store放入1到65536，value都是new+key的形式
25. }
26. void Test() {
27.   // 起n个线程，每个线程都执行ThreadFunc
28.   // 检查是否有1到65535，每个键是否都是new+key的形式
29. }

复制代码

要确保每一个修改都最终可以通过trie_store这个对象确认到，但是所有读取操作都不能被阻塞，以是里面的Put操作必要上一个写锁。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。