boost threads mutex array

Question

My problem is, I have block matrix updated by multiple threads. Multiple threads may be updating disjoint block at a time but in general there may be race conditions. right now matrix is locked using single lock.

The question is, is it possible (and if it is, how?) to implement an efficient array of locks, so that only portions of matrix maybe locked at a time.

The matrix in question can get rather large, on order of 50^2 blocks. my initial guess is to use dynamically allocate vector/map of mutexes.

Is it good approach? Is it better to use multiple condition variables instead? Is there a better approach?

Answer 1

Use a single lock. But instead of using it to protect the entire matrix use it to guard a std::set (or a boost::unordered_set) which says which blocks are "locked".

Something like this.

class Block;

class Lock_block
{
public:
   Lock_block( Block& block ) : m_block(&block)
   {
      boost::unique_lock<boost::mutex> lock(s_mutex);
      while( s_locked.find(m_block) != s_locked.end() )
      {
         s_cond.wait(lock);
      }
      bool success = s_locked.insert(m_block).second;
      assert(success);
   }

   ~Lock_block()
   {
      boost::lock_guard<boost::mutex> lock(s_mutex);
      std::size_t removed = s_locked.erase(m_block);
      assert(removed == 1);
      s_cond.notify_all();
   }
private:
   Block* m_block;

   static boost::mutex s_mutex;
   static boost::condition s_cond;
   static std::set<Block*> s_locked;
};

Answer 2

It might be a several approaches you can use:

1. Pre-allocate array if CriticalSection/Mutexes (2500 is not so many), and use block index as a lock index to gather block access; before updating blocks lock all of them which you want to change; do update; unlock;

2. If computation time is significantly longer then Lock/Unlock, then copy content of the block in thread context and keep block unlocked during that time; before updating block lock it again and make sure that it was not updated by another thread (if it's relevant for this); if it was updated by another thread, then repeat operation;

3. If the size of the block content is small, use atomic data exchange to update block content, no locks required; just not sure if you use data from one blocks to calculate data for another, in that case locking across all updated blocks required;

4. Is there reading operation on the matrix? If yes use Read/Write locks to improve performance.