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

Question

蒂姆哈里斯说：

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

Perhaps the most fundamental objection [...] is that lock-based programs do not compose: correct fragments may fail when combined. For example, consider a hash table with thread-safe insert and delete operations. Now suppose that we want to delete one item A from table t1, and insert it into table t2; but the intermediate state (in which neither table contains the item) must not be visible to other threads. Unless the implementor of the hash table anticipates this need, there is simply no way to satisfy this requirement. [...] In short, operations that are individually correct (insert, delete) cannot be composed into larger correct operations. —Tim Harris et al., "Composable Memory Transactions", Section 2: Background, pg.2[6]

这是什么意思？

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

#include <iostream>
#include <string>
#include <mutex>
#include <thread>
#include <chrono>
#include <unordered_map>

std::unordered_map<std::string, std::string> map1 ( {{"apple","red"},{"lemon","yellow"}} );
std::mutex mtx1;

std::unordered_map<std::string, std::string> map2 ( {{"orange","orange"},{"strawberry","red"}} );
std::mutex mtx2;

void func() {
    std::lock_guard<std::mutex> lock1(mtx1);
    std::lock_guard<std::mutex> lock2(mtx2);

    std::cout << "map1: ";
    for (auto& x: map1) std::cout << " " << x.first << " => " << x.second << ", ";
    std::cout << std::endl << "map2: ";
    for (auto& x: map2) std::cout << " " << x.first << " => " << x.second << ", ";
    std::cout << std::endl << std::endl;

    auto it1 = map1.find("apple");
    if(it1 != map1.end()) {
        auto val = *it1;
        map1.erase(it1);
        std::this_thread::sleep_for(std::chrono::duration<double, std::milli>(1000));
        map2[val.first] = val.second;
    }
}

int main ()
{
    std::thread t1(func);
    std::this_thread::sleep_for(std::chrono::duration<double, std::milli>(500));
    std::thread t2(func);
    t1.join();
    t2.join();

    return 0;
}

如果我想自己实现线程安全的哈希映射 my_unordered_map 那么我会实现这样的东西：

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

并将这样使用它：

my_unordered_map<std::string, std::string> map1 ( {{"apple","red"},{"lemon","yellow"}} );

my_unordered_map<std::string, std::string> map2 ( {{"orange","orange"},{"strawberry","red"}} );

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

    // work with map1 and map2
    // recursive_mutex allow multiple locks in: lock1(map1) and map1->at(key)
}

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

但是关于哪些情况是这样说的呢？

Perhaps the most fundamental objection [...] is that lock-based programs do not compose: correct fragments may fail when combined.

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 而不是锁将始终允许此类组合（以某些性能代价）。

Answer 2

插入和擦除的线程安全原子操作通常将互斥锁隐藏在其中。这可以防止在没有锁定的情况下进行访问。

在您的情况下，您改为公开互斥体。这需要每个用户 正确处理互斥锁，否则它会中断。

通过完全访问互斥锁，您可以排除安全地看到中间状态：您的代码失败，因为它没有使用 std::lock 来保证互斥锁锁定顺序是全局一致的，这可能导致死锁如果其他代码使用不同的锁定顺序。

这种问题——您必须不断地了解您的交易需要哪些互斥锁，以及您持有哪些互斥锁——不会分解成小的、易于确定正确的部分。正确性变得非本地化，然后复杂性爆炸式增长，错误比比皆是。

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

Why lock-based programs do not compose correct thread-safe fragments?

c++

concurrency

multithreading

mutex

c++11