防止共享哈希中的数据竞争 table

Question

如果这是重复的，我很抱歉，但尽管我搜索了很多，但我只找到了不适用的解决方案：

所以我有一个散列 table，我希望多个线程同时读取和写入 table。但是在以下情况下如何防止数据竞争：

个线程写入与另一个相同的散列
写入正在读取的哈希的线程

编辑：如果可能的话，因为这个散列需要非常快，因为它被非常频繁地访问，有没有办法锁定两个竞争线程，只有当它们访问散列的相同索引时 table?

Answer 1

所以你需要基本的线程同步还是什么？您必须在读写函数中使用互斥锁、lock_guard 或其他一些线程同步机制。在 cppreference.com 你有标准库的文档。

Answer 2

避免数据竞争的最可靠和适当的方法是使用互斥体序列化对散列的访问 table；即每个线程在对散列table执行任何操作（读取或写入）之前需要获取互斥量，并在完成后释放互斥量。

不过，您可能正在寻找的是实现 无锁散列 table，但确保无锁的正确多线程行为极其困难做对了，如果你的技术水平达到了实现这样的目的，你就不需要在 Whosebug 上询问它了。所以我强烈建议你要么坚持使用序列化访问方法（它适用于 99% 的软件，并且可以在不深入了解 CPU、缓存架构、RAM 的情况下正确实施, OS, scheduler, optimizer, C++ language spec, etc) 或者如果你必须使用无锁数据结构，你可以从 reputable 要使用的源代码，而不是尝试自己编写。事实上，即使你想自己动手，你也应该从查看工作示例的源代码开始，了解他们在做什么以及他们为什么这样做。

Answer 3

我以前回答过这个问题的变体。请阅读我关于此主题的previous answer。

许多人尝试实现线程安全集合 classes（列表、散列 tables、映射、集合、队列等...）但都失败了。或者更糟的是，失败了，不知道，但还是发货了。

构建线程安全散列 table 的一种简单方法是从现有散列 table 实现开始，然后向所有 public 方法添加互斥体。你可以想象一个假设的实现是这样的：

// **THIS IS BAD**

template<typename K, typename V>
class ThreadSafeMap
{
private:
    std::map<K,V> _map;
    std::mutex _mutex;

public:

    void insert(const K& k, const V& v)
    {
        std::lock_guard lck(_mutex);
        _map[k] = v;
    }

    const V& at(const K& key)
    {
        std::lock_guard lck(_mutex);
        return _map.at(k);
    }

    // other methods not shown - but are essentially a repeat of locking a mutex
    // before accessing the underlying data structure

};

在上面的例子中，std::lock_guard在lck变量实例化时锁定互斥量，而lock_guard的析构函数会在lck变量实例化时释放互斥量超出范围

并且在一定程度上，它是线程安全的。但是当你开始以复杂的方式使用上面的数据结构时，它就崩溃了。

散列 table 上的交易通常是多步操作。例如，table 上的整个应用程序事务可能是查找记录并在成功返回记录后，更改记录指向的某些成员。

所以想象一下我们在不同的线程中使用了上面的 class，如下所示：

 ThreadSafeMap g_map<std::string, Item>;

 // thread 1
 Item& item = g_map.at(key);
 item.value++;
 

 // thread 2
 Item& item = g_map.at(key);
 item.value--;

 // thread 3
 g_map.erase(key);
 g_map[key] = newItem;

很容易认为上面的操作是线程安全的，因为散列table本身就是线程安全的。但他们不是。线程 1 和线程 2 都试图访问锁外的同一个项目。线程 3 甚至试图替换可能被其他两个线程引用的记录。这里有很多未定义的行为。

解决办法？坚持使用单线程哈希 table 实现并在 application/transaction 级别使用互斥锁。更好：

 std::unordered_map<std::string, Item> g_map;
 std::mutex g_mutex;

 // thread 1
 {
   std::lock_guard lck(g_mutex);
   Item& item = g_map.at(key);
   item.value++;
 }
 

 // thread 2
 {
   std::lock_guard lck(g_mutex);
   Item& item = g_map.at(key);
   item.value--;
 }

 // thread 3
 {
   std::lock_guard lck(g_mutex);
   g_map.erase(key);
   g_map[key] = newItem;
 }

底线。不要只是在你的低级数据结构上加上互斥锁和锁，然后宣称它是线程安全的。在调用者期望对哈希 table 本身执行其操作集的级别使用互斥锁和锁。

防止共享哈希中的数据竞争 table

preventing data races in shared hash table

c++

multithreading

thread-safety