cds/sync/monitor.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_SYNC_MONITOR_H
   4 #define CDSLIB_SYNC_MONITOR_H
   5
   6 #include <cds/details/defs.h>
   7
   8 namespace cds { namespace sync {
   9
  10     /**
  11         @page cds_sync_monitor Synchronization monitor
  12
  13         A <a href="http://en.wikipedia.org/wiki/Monitor_%28synchronization%29">monitor</a> is synchronization construct
  14         that allows threads to have both mutual exclusion and the ability to wait (block) for a certain condition to become true.
  15
  16         Some blocking data structure algoritms like the trees require per-node locking.
  17         For huge trees containing millions of nodes it can be very inefficient to inject
  18         the lock object into each node. Moreover, some operating systems may not support
  19         the millions of system objects like mutexes per user process.
  20         The monitor strategy is intended to solve that problem.
  21         When the node should be locked, the monitor is called to allocate appropriate
  22         lock object for the node if needed, and to lock the node.
  23         The monitor strategy can significantly reduce the number of system objects
  24         required for data structure.
  25
  26         <b>Implemetations</b>
  27
  28         \p libcds contains several monitor implementations:
  29         - \p sync::injecting_monitor injects the lock object into each node.
  30             That mock monitor is designed for user-space locking primitive like
  31             \ref sync::spin_lock "spin-lock".
  32         - \p sync::pool_monitor is the monitor that allocates a lock object
  33             for a node from the pool when needed. When the node is unlocked
  34             the lock assigned to it is given back to the pool if no thread
  35             references to that node.
  36
  37         <b>How to use</b>
  38
  39         If you use a container from \p libcds that requires a monitor, you should just
  40         specify required monitor type in container's traits. Usually, the monitor
  41         is specified by \p traits::sync_monitor typedef, or by \p cds::opt::sync_monitor
  42         option for container's \p make_traits metafunction.
  43
  44         If you're developing a new container algorithm, you should know internal monitor
  45         interface:
  46         \code
  47         class Monitor {
  48         public:
  49             // Monitor's injection into the Node class
  50             template <typename Node>
  51             struct node_injection: public Node
  52             {
  53                 // Monitor data to inject into container's node
  54                 // ...
  55             };
  56
  57             // Locks the node
  58             template <typename Node>
  59             void lock( Node& node );
  60
  61             // Unlocks the node
  62             template <typename Node>
  63             void unlock( Node& node );
  64
  65             // Scoped lock applyes RAII to Monitor
  66             template <typename Node>
  67             using scoped_lock = monitor_scoped_lock< pool_monitor, Node >;
  68         };
  69         \endcode
  70
  71         Monitor's data must be inject into container's node as \p m_SyncMonitorInjection data member:
  72         \code
  73         template <typename SyncMonitor>
  74         struct my_node
  75         {
  76             // ...
  77             typename SyncMonitor::node_injection m_SyncMonitorInjection;
  78         };
  79         \endcode
  80
  81         The monitor must be a member of your container:
  82         \code
  83         template <typename GC, typename T, typename Traits>
  84         class my_container {
  85             // ...
  86             typedef typename Traits::sync_monitor   sync_monitor;
  87             typedef my_node<sync_monitor> node_type;
  88             sync_monitor m_Monitor;
  89             //...
  90         };
  91         \endcode
  92     */
  93
  94     /// Monitor scoped lock (RAII)
  95     /**
  96         Template arguments:
  97         - \p Monitor - monitor type
  98         - \p Node - node type
  99     */
 100     template <typename Monitor, typename Node>
 101     struct monitor_scoped_lock
 102     {
 103     public:
 104         typedef Monitor monitor_type;   ///< Monitor type
 105         typedef Node    node_type;      ///< Node type
 106
 107     private:
 108         //@cond
 109         monitor_type&    m_Monitor; ///< Monitor
 110         node_type const& m_Node;    ///< Our locked node
 111         //@endcond
 112
 113     public:
 114         /// Makes exclusive access to the node \p p by \p monitor
 115         monitor_scoped_lock( monitor_type& monitor, node_type const& p )
 116             : m_Monitor( monitor )
 117             , m_Node( p )
 118         {
 119             monitor.lock( p );
 120         }
 121
 122         /// Unlocks the node
 123         ~monitor_scoped_lock()
 124         {
 125             m_Monitor.unlock( m_Node );
 126         }
 127     };
 128
 129 }} // namespace cds::sync
 130
 131 #endif // #ifndef CDSLIB_SYNC_MONITOR_H
 132