Thread safe container

There is some exemplary class of container in pseudo code:

class Container
{
public:
  Container(){}
  ~Container(){}
  void add(data new)
  {
    // addition of data
  }
  data get(size_t which)
  {
    // returning some data
  }
  void remov开发者_Python百科e(size_t which)
  {
    // delete specified object
  }

private:
  data d;
};

How this container can be made thread safe? I heard about mutexes - where these mutexes should be placed? Should mutex be static for a class or maybe in global scope? What is good library for this task in C++?

First of all mutexes should not be static for a class as long as you going to use more than one instance. There is many cases where you should or shouldn't use use them. So without seeing your code it's hard to say. Just remember, they are used to synchronise access to shared data. So it's wise to place them inside methods that modify or rely on object's state. In your case I would use one mutex to protect whole object and lock all three methods. Like:

class Container
{
public:
  Container(){}
  ~Container(){}
  void add(data new)
  {
    lock_guard<Mutex> lock(mutex);
    // addition of data
  }
  data get(size_t which)
  {
    lock_guard<Mutex> lock(mutex);
    // getting copy of value
    // return that value
  }
  void remove(size_t which)
  {
    lock_guard<Mutex> lock(mutex);
    // delete specified object
  }

private:
  data d;
  Mutex mutex;
};

Intel Thread Building Blocks (TBB) provides a bunch of thread-safe container implementations for C++. It has been open sourced, you can download it from: http://threadingbuildingblocks.org/ver.php?fid=174 .

First: sharing mutable state between threads is hard. You should be using a library that has been audited and debugged.

Now that it is said, there are two different functional issue:

• you want a container to provide safe atomic operations
• you want a container to provide safe multiple operations

The idea of multiple operations is that multiple accesses to the same container must be executed successively, under the control of a single entity. They require the caller to "hold" the mutex for the duration of the transaction so that only it changes the state.

1. Atomic operations

This one appears simple:

• add a mutex to the object
• at the start of each method grab a mutex with a RAII lock

Unfortunately it's also plain wrong.

The issue is re-entrancy. It is likely that some methods will call other methods on the same object. If those once again attempt to grab the mutex, you get a dead lock.

It is possible to use re-entrant mutexes. They are a bit slower, but allow the same thread to lock a given mutex as much as it wants. The number of unlocks should match the number of locks, so once again, RAII.

Another approach is to use dispatching methods:

class C {
public:
  void foo() { Lock lock(_mutex); foo_impl(); }]

private:
  void foo_impl() { /* do something */; foo_impl(); }
};

The public methods are simple forwarders to private work-methods and simply lock. Then one just have to ensure that private methods never take the mutex...

Of course there are risks of accidentally calling a locking method from a work-method, in which case you deadlock. Read on to avoid this ;)

2. Multiple operations

The only way to achieve this is to have the caller hold the mutex.

The general method is simple:

• add a mutex to the container
• provide a handle on this method
• cross your fingers that the caller will never forget to hold the mutex while accessing the class

I personally prefer a much saner approach.

First, I create a "bundle of data", which simply represents the class data (+ a mutex), and then I provide a Proxy, in charge of grabbing the mutex. The data is locked so that the proxy only may access the state.

class ContainerData {
protected:
  friend class ContainerProxy;
  Mutex _mutex;

  void foo();
  void bar();

private:
  // some data
};


class ContainerProxy {
public:
  ContainerProxy(ContainerData& data): _data(data), _lock(data._mutex) {}

  void foo() { data.foo(); }
  void bar() { foo(); data.bar(); }
};

Note that it is perfectly safe for the Proxy to call its own methods. The mutex will be released automatically by the destructor.

The mutex can still be reentrant if multiple Proxies are desired. But really, when multiple proxies are involved, it generally turns into a mess. In debug mode, it's also possible to add a "check" that the mutex is not already held by this thread (and assert if it is).

3. Reminder

Using locks is error-prone. Deadlocks are a common cause of error and occur as soon as you have two mutexes (or one and re-entrancy). When possible, prefer using higher level alternatives.

Add mutex as an instance variable of class. Initialize it in constructor, and lock it at the very begining of every method, including destructor, and unlock at the end of method. Adding global mutex for all instances of class (static member or just in gloabl scope) may be a performance penalty.

The is also a very nice collection of lock-free containers (including maps) by Max Khiszinsky

LibCDS¹ Concurrent Data Structures

Here is the documentation page:

http://libcds.sourceforge.net/doc/index.html

It can be kind of intimidating to get started, because it is fully generic and requires you register a chosen garbage collection strategy and initialize that. Of course, the threading library is configurable and you need to initialize that as well :)

See the following links for some getting started info:

• initialization of CDS and the threading manager
• http://sourceforge.net/projects/libcds/forums/forum/1034512/topic/4600301/
• the unit tests ((cd build && ./build.sh ----debug-test for debug build)

Here is base template for 'main':

#include <cds/threading/model.h>    // threading manager
#include <cds/gc/hzp/hzp.h>         // Hazard Pointer GC

int main()
{
    // Initialize \p CDS library
    cds::Initialize();

    // Initialize Garbage collector(s) that you use 
    cds::gc::hzp::GarbageCollector::Construct();

    // Attach main thread 
    // Note: it is needed if main thread can access to libcds containers
    cds::threading::Manager::attachThread();

    // Do some useful work 
    ...

    // Finish main thread - detaches internal control structures
    cds::threading::Manager::detachThread(); 

    // Terminate GCs 
    cds::gc::hzp::GarbageCollector::Destruct();

    // Terminate \p CDS library
    cds::Terminate();
}

Don't forget to attach any additional threads you are using:

#include <cds/threading/model.h>

int myThreadFunc(void *)
{
   // initialize libcds thread control structures
   cds::threading::Manager::attachThread();

   // Now, you can work with GCs and libcds containers
   ....

  // Finish working thread
  cds::threading::Manager::detachThread(); 
}

¹ (not to be confuse with Google's compact datastructures library)