细粒度锁定

Question

假设我们有一个很大的数组，并且有许多线程在该数组中的具体索引上操作。两个线程不能同时对一个索引进行操作，其中一个线程应该等待另一个线程完成。还有一个糟糕的问题:如何在Linux/C/C++中对数组的每个索引实现test-and-set锁？

Answer 1

对于细粒度锁定，请使用读/写锁的数组(正如Carey Hickling建议的那样)。散列索引值并通过位掩码(或使用模数)对其进行过滤，以选择要使用的锁。

这有效地将索引拆分成N个存储桶，其中N是您创建的锁的数量。为便于位屏蔽的锁数选择2的幂(掩码=N- 1)。这个场景中唯一的缺点是，您不仅锁定了一个特定的索引，而且还锁定了每个索引，这些索引在散列后会对齐到相同的锁指针。

也就是说，您创建的锁越多，锁的粒度就越细(16可能是一个很好的起点)。读锁也与rw_locks共享，因此您只需担心在写入期间等待锁。

Answer 2

你要么需要一个简单的互斥锁，然后做：

    mutex.lock();
    //access array using index
    mutex.unlock();

或者POSIX提供读写锁。因此，您可以这样做：

    pthread_rwlock_rdlock(rw_lock_ptr);
    // read the array
    pthread_rwlock_unlock(rw_lock_ptr);

和：

    pthread_rwlock_wrlock(rw_lock_ptr);
    // update the array
    pthread_rwlock_unlock(rw_lock_ptr);

这允许用于读操作的共享锁和用于写操作的排它锁。

我建议您为数组的每个元素创建一个类或一对，并实现上述其中之一。如果在类的读取/更新函数中隐藏互斥锁，则可以更容易地限制互斥锁的范围并轻松避免死锁。

Answer 3

将数组元素类型设置为同步类型。如果你想互斥你的数据，你可以有一个std::pair<T, std::mutex>；如果你可以在每次访问时都使用自旋锁，你可以有一个std::pair<T, std::atomic<bool>>。然后，让每个数组访问通过同步数据获得对元素的独占访问。