Lock & Wait Synchronization in C++

• Download source files - 11.55 Kb
• Download demo project - 10.14 Kb

Introduction

The Boost.Thread library provides portable wrappers under system threading primitives to create a concurrent environment and to apply synchronization on it. It is fully enough to have Boost.Thread library facilities to create full-fledged multithreaded programs with using of the lock & wait based synchronization there. But Boost.Thread library is just a first layer under system threading routines. Interface of the Boost.Thread is identical from functional point of view to the interface of the system threading interfaces such as PTHREAD or Win32 Threads. That means that Boost.Thread allows non-safe operations such as non-synchronized concurrent access to resources, and forces library users to make routine and dangerous work which can be fully done by using the C++ language.

The Lwsync library (lock & wait synchronization) provides implementation for two patterns that can be used instead of raw system synchronization facilities, to allow a user to create lock & wait synchronization on a concurrent environment. Those patterns on one hand can be mapped on any synchronization facility (by default, they are mapped on the Boost.Thread, and so that they can be used anywhere the Boost library is available); on the other hand, they fully rely on the C++ language. So that one can use the Lwsync library as one more layer between any system synchronization facility and end the concurrent code to make the lock & wait synchronization more easy and safe.

The Critical Resource pattern allows one to create a resource object, and guarantee that all accesses to it will be synchronized. All synchronization will be automatically done before and after such an access. The Monitor pattern is a kind of a Critical Resource one, but it not only synchronizes all accesses to a resource object but also allows threads to wait until resource objects become in some defined state. In most cases, it is fully enough to have those two patterns to make the lock & wait based synchronization.

Note that the Lwsync library allows one only to synchronize threads but not to start them, control thread attributes etc. The Boost.Thread library may be used instead.

Lwsync Library

Critical Resource Pattern

Critical Resource is a template that receives resource type in its parameter and allows to access resource objects only when all synchronization is done. Critical Resource provides to the user a kind of smart pointers that are called accessors, which calls all the synchronization in its constructor and destructor, so that the user can access resource objects via accessors only when all the synchronization is done. A single way to access resource object is to use accessor. Critical Resource works well with both automatic and temporary accessors objects. So resource access can be synchronized both by scope of code and by an expression. In case if the critical resource is used with system synchronization facilities that allow recursive acquiring (like boost::recursive_mutex, which is used by default), resource accessors can even be escalated from within a scope of routine where it was created. That means that accessors can be returned from function by value and caller can continue working with accessed object without loosing access over it.

Also, the user is able to use critical resources to synchronize an existing object if it is not synchronized yet by using reference specialization of critical resource templates.

Example 1:

typedef lwsync::critical_resource<int> int_resource_t;
int_resource_t int_res(10);

// thread 1:
// Use temporary accessor object to access int resource.
*int_res.access() = 20;

// thread 2:
{
   // Use automatic accessor object to const access int resource.
   int_resource_t::const_accessor int_res_access = int_res.const_access();
   if ( *int_res_access == 20)
      std::cout << "Thread 1 has already changed int_res value.";
   else
      std::cout << "Thread 1 doesn't change int_res value yet.";
}

Example 2:

lwsync::critical_resource<std::ostream&> sync_cout(std::cout);

// thread N:

// It is thread-safe to use many operators << in one expression to 
// out some data, because critical resource can use temporary objects
// to synchronize an expression.
*sync_cout.access() << "Hello" << " from" << " thread " << N;

Example 3:

typedef lwsync::critical_resource<std::vector<int> > sync_vector_t;
sync_vector_t vec;

// some thread:
{
   // Critical resource can be naturally used with STL containers.
   sync_vector_t::const_accessor vec_access = vec.const_access();
   for(std::vector<int>::const_iterator where = vec_access->begin();
         where != vec_access->end();
         ++where
        )
   std::cout << *where << std::endl;
}

sync_vector_t::accessor some_vector_action()
{
   sync_vector_t::accessor vec_access = vec.access();
   vec_access->puch_back(10);
   return vec_access;
   // Access is escalated from within a some_vector_action() scope
   // So that one can make some other action with vector before it becomes
   // unlocked.
}

{
   sync_vector_t::accessor vec_access = some_vector_action()
   vec_access->puch_back(20);
   // Elements 10 and 20 will be placed in vector sequentially.
   // Any other action with vector cannot be processed between those two
   // push_back's.
}

Note that there exists an ability to use dynamic accessor objects (with using of operator new) or class data-members to manually control access time for some resource. But in most cases, it is not a good idea to store accessors, because during all accessors' lifetime resource remains blocked and there is no other ability to unblock it, except to destroy the accessor object.

It is possible to access more than one critical resource in one expression or scope, but in most cases, it is probably dead-lock unsafe to do that. copy() method can be used in expressions instead to get a copy of the resource and block only one resource in one moment of time.

Example 4:

typedef lwsync::critical_resource<int> int_resource_t;
int_resource_t one_number(10);
int_resource_t other_number(20);

// thread 1:
// this operation is dead lock unsafe because more that one 
// resource will be blocked in a one moment of time.
int result = *one_number.access() + *other_number.access()

// thread 2:
// It can be dead-locked with thread 1 because
// sequence of resources blocking is different
int result = *other_number.access() + *one_number.access()

// thread 3:
// This is dead-lock safe because only one resource
// will be blocked in a one moment of time.
int result = other_number.copy() + one_number.access()

In the example above thread 3 can't lead to deadlock when it is used with thread 1 or thread 2. But in this case there will be no guarantee that one_number and other_number together had result sum at one defined moment of a time. Value of the one_number may be changed after a copy of the other_number is already obtained.

It is possible to construct an accessor object without explicit calling of the access (or const_access) method. This ability can be used as a syntax sugar.

Example 5:

typedef lwsync::critical_resource<int> int_resource_t;
int_resource_t critical_number;

{
   // Method critical_number.access() is invoked implicitly.
   int_resource_t::accessor number_access = critical_number;
}

{
   // Method critical_number.const_access() is invoked implicitly.
   int_resource_t::const_accessor number_access = critical_number;
}

Monitor Pattern

Monitor is a kind of Critical Resource, and one can access resource object by the same way as for Critical Resourced. But monitor not only provides synchronization of resources, but also allow waiting until the resource becomes in some defined state. The state of the resource is defined with predicates, so one can use STL predicates as well to monitor some resource.

After the monitor becomes in a defined state, the user will get an accessor to the resource, and it is important that the predicate is called within the same lock that this accessor handles. So the monitor pattern guarantees that the user gets access to a resource within the same lock where the predicate was called.

Example 6:

typedef lwsync::monitor<std::vector<int> > sync_vector_t;
bool is_not_empty(const std::vector<int>& vec)
{
   return !vec.empty();
}

{
   sync_vector_t::accessor vec_access = vec.wait_for(is_not_empty);
   // Do something with vector. One can guarantee that 
   // this vector is not empty.
}

{  // Output vectors content when it becomes not empty.
   sync_vector_t::const_accessor vec_access =
      vec.const_wait_for(is_not_empty);
   for(std::vector<int>::const_iterator where = vec_access->begin();
         where != vec_access->end();
         ++where
        )
   std::cout << *where << std::endl;
}

Also, the monitor is able to wait for a resource if this resource is a bool or can be converted to a bool without predicates. For example, one can wait for a moment when the pointer will not be null.

Example 7:

typedef lwsync::monitor<my_data_t*> my_data_monitor_t;
my_data_monitor_t my_data_instance(0);

// thread 1:
{
   // Waiting for monitor without any predicate.
   my_data_monitor_t::accessor data = my_data_instance.wait();
   data->invoke_something();
}

// thread 2:
*my_data_instance.access() = new my_data_t();
// Thread 1 can start working at this moment.

Example 8:

typedef lwsync::monitor<bool> notifyer_t;
notifyer_t notify_object;

// thread 1:

for(;;)
{
   notify_object::accessor notify_access = notify_object.wait();
   // Perform some action here
   *notify_access = false; // Work have done.
}

// thread 2:
// Request thread 1 to perform some action:
*notify_object.access() = true;

Waiting predicate has access resource by value or const reference and cannot change even in case of waiting for no-const access for a resource. Predicates which use the non-const reference are prohibited to avoid live-locks when two threads are waiting for some monitor and the entire time they are trying to re-evaluate the state of the resource after each other to detect possible changes.

Monitor Waiting Cancellation

All threads which are waiting for some monitor can be cancelled with the cancel() method. In this case, the thread will receive the monitor::waiting_canceled exception instead of an accessor object. Monitor in this case enters a cancelled state as well. If some thread will try to wait for the canceled monitor, the thread will receive the monitor::waiting_canceled exception also. The monitor can be returned to the normal state with the renew() method and all the threads will be able to wait for it again.

In some cases, it is a necessity to force the monitor to reevaluate all predicates. It can be necessary if some predicate is a complex and change its state without changing the state of the monitor. The method touch() will force all threads to reevaluate its predicates.

Synchronization Policies

In most cases when Boost.Thread is available one can use Lwsync without using of synchronization policies. But they are still necessary for some special cases. For example if it is necessary to log out all accesses for some critical resource.

Critical resource and monitor patterns use synchronization policies as a template parameter, so that it can be mapped to any synchronization facility. By default, both synchronization policies use the boost::recursive_mutex and boost::condition portable synchronization facilities. Note that the synchronization policies for the critical resource and the monitor are different. The critical resource synchronization policy is based only on the locking facility but the monitor one has to have not only the locking but also waiting facility. One can use the monitor synchronization policy to synchronize critical resources (like monitor does, as a fact) but not vice versa.

Critical resource synchronization policy has to provide a locker_type, which can be used as a data-member of the critical resource to associate resource objects with a guard. Also, it has to provide four methods to perform synchronization:

template<typename Resource>

static void const_lock(locker_type*, const Resource*);

template<typename Resource>
static void lock(locker_type*, Resource*);

template<typename Resource>
static void const_unlock(locker_type*, const Resource*);

template<typename Resource>
static void unlock(locker_type*, Resource*);

All those methods will be invoked by resource accessors. The synchronization policy has the const_lock and const_unlock methods to naturally work with the rwlock synchronization pattern. The monitor synchronization policy has everything from the critical resource one, but also it has to have two waiting methods:

template<typename Resource, typename Predicate>

static void wait(locker_type*, const Resource&, Predicate);

template<typename Resource, typename Predicate>
static void const_wait(locker_type*, const Resource&, Predicate);

It makes it possible to implement waiting for a resource, and acquire a locking guard for reading when the resource becomes a defined state in case the Rwlock pattern is available and the waiting facility doesn't require mutual execution. It is safe to throw an exception from the waiting facility or the waiting predicate. In this case, the user will receive an exception instead of an access to the resource. One can implement the waiting facility as a cancellation point, and throw an exception from the wait() method if the thread is canceled. Or the predicate can throw an exception if it decides that the object becomes in a broken state. The Monitor pattern will correctly handle all those situations.

History

• 7 August 2006 - Initial revision.
• 22 October 2006 - Monitor Waiting Cancellation was added.
• 28 July 2008 - Lwsync is compatible now with boost 1.35.0.