libs/fiber/examples/work_stealing.cpp

   1
   2 //          Copyright Oliver Kowalke 2015.
   3 // Distributed under the Boost Software License, Version 1.0.
   4 //    (See accompanying file LICENSE_1_0.txt or copy at
   5 //          http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #include <algorithm>
   8 #include <atomic>
   9 #include <chrono>
  10 #include <condition_variable>
  11 #include <cstdio>
  12 #include <deque>
  13 #include <iomanip>
  14 #include <iostream>
  15 #include <mutex>
  16 #include <sstream>
  17 #include <string>
  18 #include <thread>
  19
  20 #include <boost/assert.hpp>
  21
  22 #include <boost/fiber/all.hpp>
  23
  24 #include "barrier.hpp"
  25
  26 static std::atomic< bool > fini{ false };
  27
  28 boost::fibers::future< int > fibonacci( int);
  29
  30 int fibonacci_( int n) {
  31     boost::this_fiber::yield();
  32     if ( 0 == n) {
  33         return 0;
  34     } else if ( 1 == n || 2 == n) {
  35         return 1;
  36     } else {
  37         boost::fibers::future< int > f1 = fibonacci( n - 1);
  38         boost::fibers::future< int > f2 = fibonacci( n - 2);
  39         return f1.get() + f2.get();
  40     }
  41 }
  42
  43 boost::fibers::future< int > fibonacci( int n) {
  44     boost::fibers::packaged_task< int() > pt( std::bind( fibonacci_, n) );
  45     boost::fibers::future< int > f( pt.get_future() );
  46     boost::fibers::fiber( boost::fibers::launch::dispatch, std::move( pt) ).detach();
  47     return f;
  48 }
  49
  50 void thread( unsigned int max_idx, unsigned int idx, barrier * b) {
  51     boost::fibers::use_scheduling_algorithm< boost::fibers::algo::random_chase_lev >( max_idx, idx);
  52     b->wait();
  53     while ( ! fini) {
  54         // To guarantee progress, we must ensure that
  55         // threads that have work to do are not unreasonably delayed by (thief) threads
  56         // which are idle except for task-stealing.
  57         // This call yields the thief ’s processor to another thread, allowing
  58         // descheduled threads to regain a processor and make progress.
  59         std::this_thread::yield();
  60         boost::this_fiber::yield();
  61     }
  62 }
  63
  64 int main() {
  65     unsigned int max_idx = 8;
  66     boost::fibers::use_scheduling_algorithm< boost::fibers::algo::random_chase_lev >( max_idx, max_idx);
  67     std::vector< std::thread > threads;
  68     barrier b( max_idx + 1);
  69     // launch a couple threads to help process them
  70     for ( unsigned int idx = 0; idx < max_idx; ++idx) {
  71         threads.push_back( std::thread( thread, max_idx, idx, & b) );
  72     };
  73     b.wait();
  74     int n = 30;
  75     // main fiber computes fibonacci( n)
  76     // wait on result
  77     int result = fibonacci( n).get();
  78 //    BOOST_ASSERT( 55 == result);
  79     std::ostringstream buffer;
  80     buffer << "fibonacci(" << n << ") = " << result << '\n';
  81     std::cout << buffer.str() << std::flush;
  82     // set termination flag
  83     fini = true;
  84     // wait for threads to terminate
  85     for ( std::thread & t : threads) {
  86         t.join();
  87     }
  88     std::cout << "done." << std::endl;
  89     return EXIT_SUCCESS;
  90 }