Fine Lock

Question

Let's say we have a large array and many threads working with specific indices in this array. Two threads cannot work with one index at the same time, you need to wait until the other ends. And the lame question: how to implement a test-and-set lock for each array index in Linux / C / C ++?

Answer 1

For a fine-grained commit, use an array of read / write locks (as suggested by Carey Hickling). Hash the index value and filter it through a bitmask (or use a module) to choose which lock to use.

This effectively splits the indices into N buckets, where N is the number of locks you create. Select the number of two locks to quickly block the bits (mask = N - 1). The only drawback of this scenario is that you are not just blocking a specific index, you are blocking every index that, when hashed, aligns with the same lock pointer.

Thus, the more locks you create, the larger the granular lock (16 is probably a good starting point). Reading locks is also used with rw_locks, so you only need to worry about waiting for a lock while writing.

Answer 2

You either need a simple mutex, or do:

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

Or POSIX provides read read locks. Therefore, you can:

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

and

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

This allows you to use shared locks for read operations and exclusive locks for write operations.

I would suggest that you have a class or pair for each element of the array and implement one of the above. If you hide the mutex lock in the read / update functions of the class, then you can more easily limit the volume of mutex locks and easily avoid deadlocks.

Answer 3

Make the element type of the array into something synchronized. If you want to use the mutex for your data, you can have std::pair<T, std::mutex> ; if you can get away with a spinlock every time you access, you can have std::pair<T, std::atomic<bool>> . Then, simply allow each access to the array to gain exclusive access to the element using synchronization data.