3

问题

  • 我有一个目录D，我想将(K, V)它们放入
  • void save(K, V)K将包含内容的文件名保存V到目录D
    • 具有“即发即弃”的语义 - 函数可能在将文件实际保存到磁盘之前返回
  • 目录是定义函数D的类的字段Csave
  • 调用void save(K, V)应该同时运行
    • tbb::task用于并发
    • 同一密钥的两个文件写入不能同时运行
    • 也就是说，如果两个线程同时调用save(K, V1)，save(K, V2)结果应该是Dnamed中的文件，其K内容等于or（但未损坏） V1 V2

计划的方法

  • H选择一个映射K到一个哈希函数std::size_t
  • 选择一个整数N > 1
  • 给类C一个互斥体数组tbb::mutex mutex_map[N]
  • void save(K, V)等待获取锁mutex_map[H(K) % N]以执行其文件写入

问题

  • 这是一个明智的做法吗？
  • 你能想出一个可能比这更有优势的替代方案吗？
  • 是否有一些tbb数据结构已经封装了互斥映射的这个概念？
    • 想想类似的东西，std::map<TKey, tbb::mutex>但是界面给出了每个可能的键同时具有关联互斥锁的外观。
4

2 回答 2

2

是的，这是一个非常明智的做法。我想不出替代方案（除了使用std::mutex代替的琐碎替代方案tbb:mutex。）

N与您认为将同时锁定的互斥锁数量相比，您应该选择大的。生日悖论说，如果您希望有k个线程同时尝试锁定，那么在您得到N > o(k 2 )之前，发生至少一个虚假哈希冲突的概率大于 50% 。

我不知道类似于互斥体映射的 tbb 数据结构。但是在内部，我相信 tbb::malloc 使用了您建议的技巧（线程被随机分配给独立的 malloc 数据结构），并且 tbb::concurrent_hash_map 的实现使得每个哈希桶都有一个互斥锁。

于 2013-05-11T16:07:02.927 回答
0

我的后代实现

#include <vector>
#include <functional>
#include <tbb/mutex.h> //could of course use std::mutex instead, if available

template <typename Key, typename Hash = std::hash<Key>>
class mutex_map
{
public:
    typedef Key key_type;
    typedef tbb::mutex value_type;
    static const std::size_t default_bucket_count = 16;

private:
    std::vector<value_type> mutexes;
    Hash hash;

public:
    mutex_map(
        std::size_t bucket_count = default_bucket_count,
        const Hash& hash = Hash())
        : hash(hash)
    {
        mutexes.resize(bucket_count);
    }

    std::size_t size() const
    {
        return mutexes.size();
    }

    value_type& get(const Key& key)
    {
        auto n = hash(key) % size();
        n += (n < 0) * size();
        return mutexes[n];
    }
};
于 2013-05-13T21:25:31.740 回答