1 /******************************************************************************* 2 * tlx/thread_barrier_spin.hpp 3 * 4 * Part of tlx - http://panthema.net/tlx 5 * 6 * Copyright (C) 2015-2019 Timo Bingmann <tb@panthema.net> 7 * 8 * All rights reserved. Published under the Boost Software License, Version 1.0 9 ******************************************************************************/ 10 11 #ifndef TLX_THREAD_BARRIER_SPIN_HEADER 12 #define TLX_THREAD_BARRIER_SPIN_HEADER 13 14 #include <tlx/meta/no_operation.hpp> 15 16 #include <atomic> 17 #include <thread> 18 19 namespace tlx { 20 21 /*! 22 * Implements a thread barrier using atomics and a spin lock that can be used to 23 * synchronize threads. 24 * 25 * This ThreadBarrier implementation was a lot faster in tests than 26 * ThreadBarrierMutex, but ThreadSanitizer shows data races (probably due to the 27 * generation counter). 28 */ 29 class ThreadBarrierSpin 30 { 31 public: 32 /*! 33 * Creates a new barrier that waits for n threads. 34 */ ThreadBarrierSpin(size_t thread_count)35 explicit ThreadBarrierSpin(size_t thread_count) 36 : thread_count_(thread_count - 1) { } 37 38 /*! 39 * Waits for n threads to arrive. When they have arrive, execute lambda on 40 * the one thread, which arrived last. After lambda, step the generation 41 * counter. 42 * 43 * This method blocks and returns as soon as n threads are waiting inside 44 * the method. 45 */ 46 template <typename Lambda = NoOperation<void> > wait(Lambda lambda=Lambda ())47 void wait(Lambda lambda = Lambda()) { 48 // get synchronization generation step counter. 49 size_t this_step = step_.load(std::memory_order_acquire); 50 51 if (waiting_.fetch_add(1, std::memory_order_acq_rel) == thread_count_) { 52 // we are the last thread to wait() -> reset and increment step. 53 waiting_.store(0, std::memory_order_release); 54 // step other generation counters. 55 lambda(); 56 // the following statement releases all threads from busy waiting. 57 step_.fetch_add(1, std::memory_order_acq_rel); 58 } 59 else { 60 // spin lock awaiting the last thread to increment the step counter. 61 while (step_.load(std::memory_order_acquire) == this_step) { 62 // busy spinning loop 63 } 64 } 65 } 66 67 /*! 68 * Waits for n threads to arrive, yield thread while spinning. When they 69 * have arrive, execute lambda on the one thread, which arrived last. After 70 * lambda, step the generation counter. 71 * 72 * This method blocks and returns as soon as n threads are waiting inside 73 * the method. 74 */ 75 template <typename Lambda = NoOperation<void> > wait_yield(Lambda lambda=Lambda ())76 void wait_yield(Lambda lambda = Lambda()) { 77 // get synchronization generation step counter. 78 size_t this_step = step_.load(std::memory_order_acquire); 79 80 if (waiting_.fetch_add(1, std::memory_order_acq_rel) == thread_count_) { 81 // we are the last thread to wait() -> reset and increment step. 82 waiting_.store(0, std::memory_order_release); 83 // step other generation counters. 84 lambda(); 85 // the following statement releases all threads from busy waiting. 86 step_.fetch_add(1, std::memory_order_acq_rel); 87 } 88 else { 89 // spin lock awaiting the last thread to increment the step counter. 90 while (step_.load(std::memory_order_acquire) == this_step) { 91 std::this_thread::yield(); 92 } 93 } 94 } 95 96 //! Return generation step counter step() const97 size_t step() const { 98 return step_.load(std::memory_order_acquire); 99 } 100 101 protected: 102 //! number of threads, minus one due to comparison needed in loop 103 const size_t thread_count_; 104 105 //! number of threads in spin lock 106 std::atomic<size_t> waiting_ { 0 }; 107 108 //! barrier synchronization generation 109 std::atomic<size_t> step_ { 0 }; 110 }; 111 112 } // namespace tlx 113 114 #endif // !TLX_THREAD_BARRIER_SPIN_HEADER 115 116 /******************************************************************************/ 117