From 72e49c055c4ea5fbe36727a9682561fac0fa7620 Mon Sep 17 00:00:00 2001 From: khizmax Date: Sun, 26 Jun 2016 09:27:43 +0300 Subject: [PATCH] Added description of wait strategies for flat combining --- cds/algo/flat_combining/kernel.h | 12 +- cds/algo/flat_combining/wait_strategy.h | 140 ++++++++++++++++++++---- change.log | 2 + thanks | 2 + 4 files changed, 128 insertions(+), 28 deletions(-) diff --git a/cds/algo/flat_combining/kernel.h b/cds/algo/flat_combining/kernel.h index f9843759..1f24cc21 100644 --- a/cds/algo/flat_combining/kernel.h +++ b/cds/algo/flat_combining/kernel.h @@ -25,7 +25,7 @@ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_ALGO_FLAT_COMBINING_KERNEL_H @@ -55,10 +55,10 @@ namespace cds { namespace algo { of a publication list. The publication list is a list of thread-local records of a size proportional to the number of threads that are concurrently accessing the shared object. - Each thread \p t accessing the structure to perform an invocation of some method \p m + Each thread \p t accessing the structure to perform an invocation of some method \p f() on the shared object executes the following sequence of steps:
    -
  1. Write the invocation opcode and parameters (if any) of the method \p m to be applied +
  2. Write the invocation opcode and parameters (if any) of the method \p f() to be applied sequentially to the shared object in the request field of your thread local publication record (there is no need to use a load-store memory barrier). The request field will later be used to receive the response. If your thread local publication record is marked as active @@ -66,15 +66,15 @@ namespace cds { namespace algo {
  3. Check if the global lock is taken. If so (another thread is an active combiner), spin on the request field waiting for a response to the invocation (one can add a yield at this point to allow other threads on the same core to run). Once in a while while spinning check if the lock is still taken and that your - record is active. If your record is inactive proceed to step 5. Once the response is available, - reset the request field to null and return the response.
    4. + record is active (you may use any of \p wait_strategy instead of spinning). If your record is inactive proceed to step 5. + Once the response is available, reset the request field to null and return the response.
  4. If the lock is not taken, attempt to acquire it and become a combiner. If you fail, return to spinning in step 2.
  5. Otherwise, you hold the lock and are a combiner.
    • Increment the combining pass count by one.
    • Execute a \p fc_apply() by traversing the publication list from the head, - combining all nonnull method call invocations, setting the age of each of these records + combining all non-null method call invocations, setting the age of each of these records to the current count, applying the combined method calls to the structure D, and returning responses to all the invocations. This traversal is guaranteed to be wait-free.
    • If the count is such that a cleanup needs to be performed, traverse the publication diff --git a/cds/algo/flat_combining/wait_strategy.h b/cds/algo/flat_combining/wait_strategy.h index c8ec6f83..f16c6d7f 100644 --- a/cds/algo/flat_combining/wait_strategy.h +++ b/cds/algo/flat_combining/wait_strategy.h @@ -56,58 +56,133 @@ namespace cds { namespace opt { namespace cds { namespace algo { namespace flat_combining { /// Wait strategies for \p flat_combining technique + /** + Wait strategy specifies how a thread waits until its request is performed by the combiner. + See \p wait_strategy::empty wait strategy to explain the interface. + */ namespace wait_strategy { /// Empty wait strategy + /** + Empty wait strategy is just spinning on request field. + All functions are empty. + */ struct empty { - //@cond + /// Metafunction for defining a publication record for flat combining technique + /** + Any wait strategy may expand the publication record for storing + its own private data. + \p PublicationRecord is the type specified by \p flat_combining::kernel. + - If the strategy has no thread-private data, it should typedef \p PublicationRecord + as a return \p type of metafunction. + - Otherwise, if the strategy wants to store anything in thread-local data, + it should expand \p PublicationRecord, for example: + \code + template + struct make_publication_record { + struct type: public PublicationRecord + { + int strategy_data; + }; + }; + \endcode + */ template struct make_publication_record { - typedef PublicationRecord type; + typedef PublicationRecord type; ///< Metafunction result }; + /// Prepares the strategy + /** + This function is called before enter to waiting cycle. + Some strategies need to prepare its thread-local data in \p rec. + + \p PublicationRecord is thread's publication record of type \p make_publication_record::type + */ template - void prepare( PublicationRecord& /*rec*/ ) - {} + void prepare( PublicationRecord& rec ) + { + CDS_UNUSED( rec ); + } + + /// Waits for the combiner + /** + The thread calls this function to wait for the combiner process + the request. + The function returns \p true if the thread was waked up by the combiner, + otherwise it should return \p false. + \p FCKernel is a \p flat_combining::kernel object, + \p PublicationRecord is thread's publication record of type \p make_publication_record::type + */ template - bool wait( FCKernel& /*fc*/, PublicationRecord& /*rec*/ ) + bool wait( FCKernel& fc, PublicationRecord& rec ) { + CDS_UNUSED( fc ); + CDS_UNUSED( rec ); return false; } + /// Wakes up the thread + /** + The combiner calls \p %notify() when it has been processed the request. + + \p FCKernel is a \p flat_combining::kernel object, + \p PublicationRecord is thread's publication record of type \p make_publication_record::type + */ template - void notify( FCKernel& /*fc*/, PublicationRecord& /*rec*/ ) - {} + void notify( FCKernel& fc, PublicationRecord& rec ) + { + CDS_UNUSED( fc ); + CDS_UNUSED( rec ); + } + /// Moves control to other thread + /** + This function is called when the thread becomes the combiner + but the request of the thread is already processed. + The strategy may call \p fc.wakeup_any() instructs the kernel + to wake up any pending thread. + + \p FCKernel is a \p flat_combining::kernel object, + */ template - void wakeup( FCKernel& /*fc*/ ) - {} - //@endcond + void wakeup( FCKernel& fc ) + { + CDS_UNUSED( fc ); + } }; /// Back-off wait strategy + /** + Template argument \p Backoff specifies back-off strategy, default is cds::backoff::delay_of<2> + */ template > struct backoff { - //@cond - typedef BackOff back_off; + typedef BackOff back_off; ///< Back-off strategy + /// Incorporates back-off strategy into publication record template - struct make_publication_record { + struct make_publication_record + { + //@cond struct type: public PublicationRecord { back_off bkoff; }; + //@endcond }; + /// Resets back-off strategy in \p rec template void prepare( PublicationRecord& rec ) { rec.bkoff.reset(); } + /// Calls back-off strategy template bool wait( FCKernel& /*fc*/, PublicationRecord& rec ) { @@ -115,14 +190,15 @@ namespace cds { namespace algo { namespace flat_combining { return false; } + /// Does nothing template void notify( FCKernel& /*fc*/, PublicationRecord& /*rec*/ ) {} + /// Does nothing template void wakeup( FCKernel& ) {} - //@endcond }; /// Wait strategy based on the single mutex and the condition variable @@ -140,21 +216,25 @@ namespace cds { namespace algo { namespace flat_combining { std::condition_variable m_condvar; typedef std::unique_lock< std::mutex > unique_lock; + //@endcond public: enum { - c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds + c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds ///< Waiting duration }; + /// Empty metafunction template struct make_publication_record { - typedef PublicationRecord type; + typedef PublicationRecord type; ///< publication record type }; + /// Does nothing template void prepare( PublicationRecord& /*rec*/ ) {} + /// Sleeps on condition variable waiting for notification from combiner template bool wait( FCKernel& fc, PublicationRecord& rec ) { @@ -166,18 +246,19 @@ namespace cds { namespace algo { namespace flat_combining { return false; } + /// Calls condition variable function \p notify_all() template void notify( FCKernel& fc, PublicationRecord& rec ) { m_condvar.notify_all(); } + /// Calls condition variable function \p notify_all() template void wakeup( FCKernel& /*fc*/ ) { m_condvar.notify_all(); } - //@endcond }; /// Wait strategy based on the single mutex and thread-local condition variables @@ -194,24 +275,31 @@ namespace cds { namespace algo { namespace flat_combining { std::mutex m_mutex; typedef std::unique_lock< std::mutex > unique_lock; + //@endcond public: enum { - c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds + c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds ///< Waiting duration }; + /// Incorporates a condition variable into \p PublicationRecord template struct make_publication_record { + /// Metafunction result struct type: public PublicationRecord { + //@cond std::condition_variable m_condvar; + //@endcond }; }; + /// Does nothing template void prepare( PublicationRecord& /*rec*/ ) {} + /// Sleeps on condition variable waiting for notification from combiner template bool wait( FCKernel& fc, PublicationRecord& rec ) { @@ -223,18 +311,19 @@ namespace cds { namespace algo { namespace flat_combining { return false; } + /// Calls condition variable function \p notify_one() template void notify( FCKernel& fc, PublicationRecord& rec ) { rec.m_condvar.notify_one(); } + /// Calls \p fc.wakeup_any() to wake up any pending thread template void wakeup( FCKernel& fc ) { fc.wakeup_any(); } - //@endcond }; /// Wait strategy where each thread has a mutex and a condition variable @@ -247,25 +336,31 @@ namespace cds { namespace algo { namespace flat_combining { { //@cond typedef std::unique_lock< std::mutex > unique_lock; - + //@endcond public: enum { - c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds + c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds ///< Waiting duration }; + /// Incorporates a condition variable and a mutex into \p PublicationRecord template struct make_publication_record { + /// Metafunction result struct type: public PublicationRecord { + //@cond std::mutex m_mutex; std::condition_variable m_condvar; + //@endcond }; }; + /// Does nothing template void prepare( PublicationRecord& /*rec*/ ) {} + /// Sleeps on condition variable waiting for notification from combiner template bool wait( FCKernel& fc, PublicationRecord& rec ) { @@ -277,18 +372,19 @@ namespace cds { namespace algo { namespace flat_combining { return false; } + /// Calls condition variable function \p notify_one() template void notify( FCKernel& /*fc*/, PublicationRecord& rec ) { rec.m_condvar.notify_one(); } + /// Calls \p fc.wakeup_any() to wake up any pending thread template void wakeup( FCKernel& fc ) { fc.wakeup_any(); } - //@endcond }; } // namespace wait_strategy diff --git a/change.log b/change.log index fcf866eb..fbfb9922 100644 --- a/change.log +++ b/change.log @@ -2,6 +2,8 @@ General release - Changed: CMake is used for build libcds. Ancient build.sh is removed - Changed: unit and stress tests are migrated to googletest framework + - Added: wait strategies for flat combining technique. Based on + research of Marsel Galimullin and Nikolai Rapotkin. - Fixed: serious bug in MichaelSet::emplace() function New node was created twice from the arguments by move semantics. However, move semantics may change internal state of the argument diff --git a/thanks b/thanks index 97471040..6e0d6cd5 100644 --- a/thanks +++ b/thanks @@ -9,7 +9,9 @@ Kyle Hegeman (https://github.com/khegeman) Lily Tsai (https://github.com/tslilyai) Lucas Larsch Markus Elfring +Marsel Galimullin Mykola Dimura Mike Krinkin (https://github.com/krinkinmu) +Nikolai Rapotkin rwf (https://github.com/rfw) Tamas Lengyel -- 2.34.1