2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_SYNC_MONITOR_H
32 #define CDSLIB_SYNC_MONITOR_H
34 #include <cds/details/defs.h>
36 namespace cds { namespace sync {
38 @page cds_sync_monitor Synchronization monitor
39 A <a href="http://en.wikipedia.org/wiki/Monitor_%28synchronization%29">monitor</a> is synchronization construct
40 that allows threads to have both mutual exclusion and the ability to wait (block) for a certain condition to become true.
41 Some blocking data structure algoritms like the trees require per-node locking.
42 For huge trees containing millions of nodes it can be very inefficient to inject
43 the lock object into each node. Moreover, some operating systems may not support
44 the millions of system objects like mutexes per user process.
45 The monitor strategy is intended to solve that problem.
46 When the node should be locked, the monitor is called to allocate appropriate
47 lock object for the node if needed, and to lock the node.
48 The monitor strategy can significantly reduce the number of system objects
49 required for data structure.
53 \p libcds contains several monitor implementations:
54 - \p sync::injecting_monitor injects the lock object into each node.
55 That mock monitor is designed for user-space locking primitive like
56 \ref sync::spin_lock "spin-lock".
57 - \p sync::pool_monitor is the monitor that allocates a lock object
58 for a node from the pool when needed. When the node is unlocked
59 the lock assigned to it is given back to the pool if no thread
60 references to that node.
64 If you use a container from \p libcds that requires a monitor, you should just
65 specify required monitor type in container's traits. Usually, the monitor
66 is specified by \p traits::sync_monitor typedef, or by \p cds::opt::sync_monitor
67 option for container's \p make_traits metafunction.
69 If you're developing a new container algorithm, you should know internal monitor
74 // Monitor's injection into the Node class
75 template <typename Node>
76 struct node_injection: public Node
78 // Monitor data to inject into container's node
82 template <typename Node>
83 void lock( Node& node );
85 template <typename Node>
86 void unlock( Node& node );
87 // Scoped lock applyes RAII to Monitor
88 template <typename Node>
89 using scoped_lock = monitor_scoped_lock< pool_monitor, Node >;
92 Monitor's data must be inject into container's node as \p m_SyncMonitorInjection data member:
94 template <typename SyncMonitor>
98 typename SyncMonitor::node_injection m_SyncMonitorInjection;
101 The monitor must be a member of your container:
103 template <typename GC, typename T, typename Traits>
106 typedef typename Traits::sync_monitor sync_monitor;
107 typedef my_node<sync_monitor> node_type;
108 sync_monitor m_Monitor;
113 /// Monitor scoped lock (RAII)
116 - \p Monitor - monitor type
117 - \p Node - node type
119 template <typename Monitor, typename Node>
120 struct monitor_scoped_lock
123 typedef Monitor monitor_type; ///< Monitor type
124 typedef Node node_type; ///< Node type
127 monitor_type& m_Monitor; ///< Monitor
128 node_type const& m_Node; ///< Our locked node
131 /// Makes exclusive access to the node \p p by \p monitor
132 monitor_scoped_lock( monitor_type& monitor, node_type const& p )
133 : m_Monitor( monitor )
139 ~monitor_scoped_lock()
141 m_Monitor.unlock( m_Node );
144 }} // namespace cds::sync
145 #endif // #ifndef CDSLIB_SYNC_MONITOR_H