为什么基于锁的程序不能组成正确的线程安全片段？

Question

蒂姆·哈里斯说：

\n\n

https://en.wikipedia.org/wiki/Software_transactional_memory#Composable_operations

\n\n

\n

也许最基本的反对意见是基于锁的程序无法组合：正确的片段在组合时可能会失败。例如，考虑具有线程安全插入和删除操作的哈希表。现在假设我们要从表t1中删除一项A，并将其插入到表t2中；但中间状态（其中两个表都不包含该项）对于其他线程一定不可见。除非哈希表的实现者预见到这种需求，否则根本没有办法满足此要求。[...] 简而言之，单独正确的操作（插入、删除）不能组合成更大的正确操作。\xe2\x80\x94Tim Harris 等人，\n“可组合内存事务”，第 2 节：背景，第 2 页[6]

\n

\n\n

这是什么意思？

\n\n

如果我有 2 个哈希映射std::unordered_map和 2 个互斥体std::mutex（每个哈希映射一个），那么我可以简单地锁定它们： http: //ideone.com/6RSNyN

\n\n

#include <iostream>\n#include <string>\n#include <mutex>\n#include <thread>\n#include <chrono>\n#include <unordered_map>\n\nstd::unordered_map<std::string, std::string> map1 ( {{"apple","red"},{"lemon","yellow"}} );\nstd::mutex mtx1;\n\nstd::unordered_map<std::string, std::string> map2 ( {{"orange","orange"},{"strawberry","red"}} );\nstd::mutex mtx2;\n\nvoid func() {\n    std::lock_guard<std::mutex> lock1(mtx1);\n    std::lock_guard<std::mutex> lock2(mtx2);\n\n    std::cout << "map1: ";\n    for (auto& x: map1) std::cout << " " << x.first << " => " << x.second << ", ";\n    std::cout << std::endl << "map2: ";\n    for (auto& x: map2) std::cout << " " << x.first << " => " << x.second << ", ";\n    std::cout << std::endl << std::endl;\n\n    auto it1 = map1.find("apple");\n    if(it1 != map1.end()) {\n        auto val = *it1;\n        map1.erase(it1);\n        std::this_thread::sleep_for(std::chrono::duration<double, std::milli>(1000));\n        map2[val.first] = val.second;\n    }\n}\n\nint main ()\n{\n    std::thread t1(func);\n    std::this_thread::sleep_for(std::chrono::duration<double, std::milli>(500));\n    std::thread t2(func);\n    t1.join();\n    t2.join();\n\n    return 0;\n}\n

\n\n

如果我想实现自己的线程安全哈希图，my_unordered_map那么我将实现这样的事情：

\n\n

template<typename key, template val>\nclass my_unordered_map {\n    std::recursive_mutex mtx_ptr;\n    void lock() { mtx_ptr->lock(); }\n    void unlock() { mtx_ptr->unlock(); }\n    template<typename mutex_type> friend class std::lock_guard;\npublic:\n // .. all required public methods which lock recursive mutex before do anything\n    void insert(key k, val v) { std::lock_guard<std::recursive_mutex> lock(mtx); /* do insert ... */ }\n    // ...\n};\n

\n\n

并将这样使用它：

\n\n

my_unordered_map<std::string, std::string> map1 ( {{"apple","red"},{"lemon","yellow"}} );\n\nmy_unordered_map<std::string, std::string> map2 ( {{"orange","orange"},{"strawberry","red"}} );\n\nvoid func() {\n    std::lock_guard<my_unordered_map> lock1(map1);\n    std::lock_guard<my_unordered_map> lock2(map2);\n\n    // work with map1 and map2\n    // recursive_mutex allow multiple locks in: lock1(map1) and map1->at(key)\n}\n

\n\n

类似地，我获得了map1和map2的线程安全代码和完全顺序一致性。

\n\n

但这样说是针对哪些情况呢？

\n\n

\n

也许最基本的反对意见是基于锁的程序无法组合：正确的片段在组合时可能会失败。

\n

\n

Answer 1

你的程序本身就很好。

另一个程序，对于另一个线程中的不同任务，可能会使用类似的东西

void func_other() {
    std::lock_guard<my_unordered_map> lock2(map2);
    std::lock_guard<my_unordered_map> lock1(map1);

    // work with map1 and map2
}

再说一次，这本身就很好。

但是，如果我们同时运行这两个程序，则可能会出现死锁。线程 1 锁定映射 1，线程 2 锁定映射 2，现在两个线程中的下一个锁定将永远等待。

因此我们不能天真地编写这两个程序。

使用 STM 代替锁总是允许这种组合（以一定的性能代价）。