Synchronization monitor

A monitor is synchronization construction that allows threads to have both mutual exclusion and the ability to wait (block) for a certain condition to become true. Some blocking data structure algoritms like the trees require per-node locking. For huge trees containing millions of nodes it can be very inefficient to inject the lock object into each node. Moreover, some operating systems may not support the millions of system objects like mutexes per user process. The monitor strategy is intended to solve that problem. When the node should be locked, the monitor is called to allocate appropriate lock object for the node if needed, and to lock the node. The monitor strategy can significantly reduce the number of system objects required for data structure.

Implemetations

libcds contains several monitor implementations:

• sync::injecting_monitor injects the lock object into each node. That mock monitor is designed for user-space locking primitive like spin-lock.
• sync::pool_monitor is the monitor that allocates a lock object for a node from the pool when needed. When the node is unlocked the lock assigned to it is given back to the pool if no thread references to that node.

How to use

If you use a container from libcds that requires a monitor, you should just specify required monitor type in container's traits. Usually, the monitor is specified by traits::sync_monitor typedef, or by cds::opt::sync_monitor option for container's make_traits metafunction.

If you're developing a new container algorithm, you should know internal monitor interface:

class Monitor {
public:
    // Monitor's injection into the Node class
    template <typename Node>
    struct node_injection: public Node
    {
        // Monitor data injecting into container's node
        // ...
    };
    // Locks the node
    template <typename Node>
    void lock( Node& node );
    // Unlocks the node
    template <typename Node>
    void unlock( Node& node );
    // Scoped lock applyes RAII to Monitor
    template <typename Node>
    using scoped_lock = monitor_scoped_lock< pool_monitor, Node >;
};

Monitor's data must be injected into container's node as m_SyncMonitorInjection data member:

template <typename SyncMonitor>
struct my_node
{
    // ...
    typename SyncMonitor::node_injection m_SyncMonitorInjection;
};

The monitor must be a member of your container:

template <typename GC, typename T, typename Traits>
class my_container {
    // ...
    typedef typename Traits::sync_monitor   sync_monitor;
    typedef my_node<sync_monitor> node_type;
    sync_monitor m_Monitor;
    //...
};