fiber/detail/spinlock_ttas.hpp

0001
0002 //          Copyright Oliver Kowalke 2016.
0003 // Distributed under the Boost Software License, Version 1.0.
0004 //    (See accompanying file LICENSE_1_0.txt or copy at
0005 //          http://www.boost.org/LICENSE_1_0.txt)
0006
0007 #ifndef BOOST_FIBERS_SPINLOCK_TTAS_H
0008 #define BOOST_FIBERS_SPINLOCK_TTAS_H
0009
0010 #include <algorithm>
0011 #include <atomic>
0012 #include <chrono>
0013 #include <cmath>
0014 #include <random>
0015 #include <thread>
0016
0017 #include <boost/fiber/detail/config.hpp>
0018 #include <boost/fiber/detail/cpu_relax.hpp>
0019 #include <boost/fiber/detail/spinlock_status.hpp>
0020
0021 // based on informations from:
0022 // https://software.intel.com/en-us/articles/benefitting-power-and-performance-sleep-loops
0023 // https://software.intel.com/en-us/articles/long-duration-spin-wait-loops-on-hyper-threading-technology-enabled-intel-processors
0024
0025 namespace boost {
0026 namespace fibers {
0027 namespace detail {
0028
0029 class spinlock_ttas {
0030 private:
0031     template< typename FBSplk >
0032     friend class spinlock_rtm;
0033
0034     std::atomic< spinlock_status >              state_{ spinlock_status::unlocked };
0035
0036 public:
0037     spinlock_ttas() = default;
0038
0039     spinlock_ttas( spinlock_ttas const&) = delete;
0040     spinlock_ttas & operator=( spinlock_ttas const&) = delete;
0041
0042     void lock() noexcept {
0043         static thread_local std::minstd_rand generator{ std::random_device{}() };
0044         std::size_t collisions = 0 ;
0045         for (;;) {
0046             // avoid using multiple pause instructions for a delay of a specific cycle count
0047             // the delay of cpu_relax() (pause on Intel) depends on the processor family
0048             // the cycle count can not guaranteed from one system to the next
0049             // -> check the shared variable 'state_' in between each cpu_relax() to prevent
0050             //    unnecessarily long delays on some systems
0051             std::size_t retries = 0;
0052             // test shared variable 'status_'
0053             // first access to 'state_' -> chache miss
0054             // sucessive acccess to 'state_' -> cache hit
0055             // if 'state_' was released by other fiber
0056             // cached 'state_' is invalidated -> cache miss
0057             while ( spinlock_status::locked == state_.load( std::memory_order_relaxed) ) {
0058 #if !defined(BOOST_FIBERS_SPIN_SINGLE_CORE)
0059                 if ( BOOST_FIBERS_SPIN_BEFORE_SLEEP0 > retries) {
0060                     ++retries;
0061                     // give CPU a hint that this thread is in a "spin-wait" loop
0062                     // delays the next instruction's execution for a finite period of time (depends on processor family)
0063                     // the CPU is not under demand, parts of the pipeline are no longer being used
0064                     // -> reduces the power consumed by the CPU
0065                     // -> prevent pipeline stalls
0066                     cpu_relax();
0067                 } else if ( BOOST_FIBERS_SPIN_BEFORE_YIELD > retries) {
0068                     ++retries;
0069                     // std::this_thread::sleep_for( 0us) has a fairly long instruction path length,
0070                     // combined with an expensive ring3 to ring 0 transition costing about 1000 cycles
0071                     // std::this_thread::sleep_for( 0us) lets give up this_thread the remaining part of its time slice
0072                     // if and only if a thread of equal or greater priority is ready to run
0073                     static constexpr std::chrono::microseconds us0{ 0 };
0074                     std::this_thread::sleep_for( us0);
0075                 } else {
0076                     // std::this_thread::yield() allows this_thread to give up the remaining part of its time slice,
0077                     // but only to another thread on the same processor
0078                     // instead of constant checking, a thread only checks if no other useful work is pending
0079                     std::this_thread::yield();
0080                 }
0081 #else
0082                 std::this_thread::yield();
0083 #endif
0084             }
0085             // test-and-set shared variable 'status_'
0086             // everytime 'status_' is signaled over the bus, even if the test failes
0087             if ( spinlock_status::locked == state_.exchange( spinlock_status::locked, std::memory_order_acquire) ) {
0088                 // spinlock now contended
0089                 // utilize 'Binary Exponential Backoff' algorithm
0090                 // linear_congruential_engine is a random number engine based on Linear congruential generator (LCG)
0091                 std::uniform_int_distribution< std::size_t > distribution{
0092                     0, static_cast< std::size_t >( 1) << (std::min)(collisions, static_cast< std::size_t >( BOOST_FIBERS_CONTENTION_WINDOW_THRESHOLD)) };
0093                 const std::size_t z = distribution( generator);
0094                 ++collisions;
0095                 for ( std::size_t i = 0; i < z; ++i) {
0096                     // -> reduces the power consumed by the CPU
0097                     // -> prevent pipeline stalls
0098                     cpu_relax();
0099                 }
0100             } else {
0101                 // success, thread has acquired the lock
0102                 break;
0103             }
0104         }
0105     }
0106
0107     bool try_lock() noexcept {
0108         return spinlock_status::unlocked == state_.exchange( spinlock_status::locked, std::memory_order_acquire);
0109     }
0110
0111     void unlock() noexcept {
0112         state_.store( spinlock_status::unlocked, std::memory_order_release);
0113     }
0114 };
0115
0116 }}}
0117
0118 #endif // BOOST_FIBERS_SPINLOCK_TTAS_H