2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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_ALGO_FLAT_COMBINING_WAIT_STRATEGY_H
32 #define CDSLIB_ALGO_FLAT_COMBINING_WAIT_STRATEGY_H
34 #include <cds/algo/flat_combining/defs.h>
35 #include <cds/algo/backoff_strategy.h>
37 #include <condition_variable>
38 #include <boost/thread/tss.hpp> // thread_specific_ptr
41 namespace cds { namespace opt {
43 /// Wait strategy option for \p flat_combining::kernel
44 template <typename Strategy>
45 struct wait_strategy {
47 template <typename Base> struct pack: public Base
49 typedef Strategy wait_strategy;
54 }} // namespace cds::opt
56 namespace cds { namespace algo { namespace flat_combining {
58 /// Wait strategies for \p flat_combining technique
60 Wait strategy specifies how a thread waits until its request is performed by the combiner.
61 See \p wait_strategy::empty wait strategy to explain the interface.
63 namespace wait_strategy {
65 /// Empty wait strategy
67 Empty wait strategy is just spinning on request field.
68 All functions are empty.
72 /// Metafunction for defining a publication record for flat combining technique
74 Any wait strategy may expand the publication record for storing
76 \p PublicationRecord is the type specified by \p flat_combining::kernel.
77 - If the strategy has no thread-private data, it should typedef \p PublicationRecord
78 as a return \p type of metafunction.
79 - Otherwise, if the strategy wants to store anything in thread-local data,
80 it should expand \p PublicationRecord, for example:
82 template <typename PublicationRecord>
83 struct make_publication_record {
84 struct type: public PublicationRecord
91 template <typename PublicationRecord>
92 struct make_publication_record {
93 typedef PublicationRecord type; ///< Metafunction result
96 /// Prepares the strategy
98 This function is called before enter to waiting cycle.
99 Some strategies need to prepare its thread-local data in \p rec.
101 \p PublicationRecord is thread's publication record of type \p make_publication_record::type
103 template <typename PublicationRecord>
104 void prepare( PublicationRecord& rec )
109 /// Waits for the combiner
111 The thread calls this function to wait for the combiner process
113 The function returns \p true if the thread was waked up by the combiner,
114 otherwise it should return \p false.
116 \p FCKernel is a \p flat_combining::kernel object,
117 \p PublicationRecord is thread's publication record of type \p make_publication_record::type
119 template <typename FCKernel, typename PublicationRecord>
120 bool wait( FCKernel& fc, PublicationRecord& rec )
127 /// Wakes up the thread
129 The combiner calls \p %notify() when it has been processed the request.
131 \p FCKernel is a \p flat_combining::kernel object,
132 \p PublicationRecord is thread's publication record of type \p make_publication_record::type
134 template <typename FCKernel, typename PublicationRecord>
135 void notify( FCKernel& fc, PublicationRecord& rec )
141 /// Moves control to other thread
143 This function is called when the thread becomes the combiner
144 but the request of the thread is already processed.
145 The strategy may call \p fc.wakeup_any() instructs the kernel
146 to wake up any pending thread.
148 \p FCKernel is a \p flat_combining::kernel object,
150 template <typename FCKernel>
151 void wakeup( FCKernel& fc )
157 /// Back-off wait strategy
159 Template argument \p Backoff specifies back-off strategy, default is cds::backoff::delay_of<2>
161 template <typename BackOff = cds::backoff::delay_of<2>>
164 typedef BackOff back_off; ///< Back-off strategy
166 /// Incorporates back-off strategy into publication record
167 template <typename PublicationRecord>
168 struct make_publication_record
171 struct type: public PublicationRecord
178 /// Resets back-off strategy in \p rec
179 template <typename PublicationRecord>
180 void prepare( PublicationRecord& rec )
185 /// Calls back-off strategy
186 template <typename FCKernel, typename PublicationRecord>
187 bool wait( FCKernel& /*fc*/, PublicationRecord& rec )
194 template <typename FCKernel, typename PublicationRecord>
195 void notify( FCKernel& /*fc*/, PublicationRecord& /*rec*/ )
199 template <typename FCKernel>
200 void wakeup( FCKernel& )
204 /// Wait strategy based on the single mutex and the condition variable
206 The strategy shares the mutex and conditional variable for all thread.
208 Template parameter \p Milliseconds specifies waiting duration;
209 the minimal value is 1.
211 template <int Milliseconds = 2>
212 class single_mutex_single_condvar
216 std::condition_variable m_condvar;
219 typedef std::unique_lock< std::mutex > unique_lock;
224 c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds ///< Waiting duration
227 /// Empty metafunction
228 template <typename PublicationRecord>
229 struct make_publication_record {
230 typedef PublicationRecord type; ///< publication record type
234 single_mutex_single_condvar()
239 template <typename PublicationRecord>
240 void prepare( PublicationRecord& /*rec*/ )
243 /// Sleeps on condition variable waiting for notification from combiner
244 template <typename FCKernel, typename PublicationRecord>
245 bool wait( FCKernel& fc, PublicationRecord& rec )
247 if ( fc.get_operation( rec ) >= req_Operation ) {
248 unique_lock lock( m_mutex );
249 if ( fc.get_operation( rec ) >= req_Operation ) {
255 bool ret = m_condvar.wait_for( lock, std::chrono::milliseconds( c_nWaitMilliseconds ) ) == std::cv_status::no_timeout;
263 /// Calls condition variable function \p notify_all()
264 template <typename FCKernel, typename PublicationRecord>
265 void notify( FCKernel& fc, PublicationRecord& /*rec*/ )
270 /// Calls condition variable function \p notify_all()
271 template <typename FCKernel>
272 void wakeup( FCKernel& /*fc*/ )
274 unique_lock lock( m_mutex );
276 m_condvar.notify_all();
280 /// Wait strategy based on the single mutex and thread-local condition variables
282 The strategy shares the mutex, but each thread has its own conditional variable
284 Template parameter \p Milliseconds specifies waiting duration;
285 the minimal value is 1.
287 template <int Milliseconds = 2>
288 class single_mutex_multi_condvar
294 typedef std::unique_lock< std::mutex > unique_lock;
299 c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds ///< Waiting duration
302 /// Incorporates a condition variable into \p PublicationRecord
303 template <typename PublicationRecord>
304 struct make_publication_record {
305 /// Metafunction result
306 struct type: public PublicationRecord
309 std::condition_variable m_condvar;
315 single_mutex_multi_condvar()
320 template <typename PublicationRecord>
321 void prepare( PublicationRecord& /*rec*/ )
324 /// Sleeps on condition variable waiting for notification from combiner
325 template <typename FCKernel, typename PublicationRecord>
326 bool wait( FCKernel& fc, PublicationRecord& rec )
328 if ( fc.get_operation( rec ) >= req_Operation ) {
329 unique_lock lock( m_mutex );
331 if ( fc.get_operation( rec ) >= req_Operation ) {
337 bool ret = rec.m_condvar.wait_for( lock, std::chrono::milliseconds( c_nWaitMilliseconds ) ) == std::cv_status::no_timeout;
345 /// Calls condition variable function \p notify_one()
346 template <typename FCKernel, typename PublicationRecord>
347 void notify( FCKernel& /*fc*/, PublicationRecord& rec )
349 unique_lock lock( m_mutex );
351 rec.m_condvar.notify_one();
354 /// Calls \p fc.wakeup_any() to wake up any pending thread
355 template <typename FCKernel>
356 void wakeup( FCKernel& fc )
362 /// Wait strategy where each thread has a mutex and a condition variable
364 Template parameter \p Milliseconds specifies waiting duration;
365 the minimal value is 1.
367 template <int Milliseconds = 2>
368 class multi_mutex_multi_condvar
371 typedef std::unique_lock< std::mutex > unique_lock;
375 c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds ///< Waiting duration
378 /// Incorporates a condition variable and a mutex into \p PublicationRecord
379 template <typename PublicationRecord>
380 struct make_publication_record {
381 /// Metafunction result
382 struct type: public PublicationRecord
386 std::condition_variable m_condvar;
397 template <typename PublicationRecord>
398 void prepare( PublicationRecord& /*rec*/ )
401 /// Sleeps on condition variable waiting for notification from combiner
402 template <typename FCKernel, typename PublicationRecord>
403 bool wait( FCKernel& fc, PublicationRecord& rec )
405 if ( fc.get_operation( rec ) >= req_Operation ) {
406 unique_lock lock( rec.m_mutex );
408 if ( fc.get_operation( rec ) >= req_Operation ) {
409 if ( rec.m_wakeup ) {
410 rec.m_wakeup = false;
414 bool ret = rec.m_condvar.wait_for( lock, std::chrono::milliseconds( c_nWaitMilliseconds ) ) == std::cv_status::no_timeout;
415 rec.m_wakeup = false;
422 /// Calls condition variable function \p notify_one()
423 template <typename FCKernel, typename PublicationRecord>
424 void notify( FCKernel& /*fc*/, PublicationRecord& rec )
426 unique_lock lock( rec.m_mutex );
428 rec.m_condvar.notify_one();
431 /// Calls \p fc.wakeup_any() to wake up any pending thread
432 template <typename FCKernel>
433 void wakeup( FCKernel& fc )
439 } // namespace wait_strategy
440 }}} // namespace cds::algo::flat_combining
442 #endif //CDSLIB_ALGO_FLAT_COMBINING_WAIT_STRATEGY_H