medfall

A super great game engine
Log | Files | Refs

full_search_scheduler.hpp (12777B)


      1 /*  Relacy Race Detector
      2  *  Copyright (c) 2008-2013, Dmitry S. Vyukov
      3  *  All rights reserved.
      4  *  This software is provided AS-IS with no warranty, either express or implied.
      5  *  This software is distributed under a license and may not be copied,
      6  *  modified or distributed except as expressly authorized under the
      7  *  terms of the license contained in the file LICENSE in this distribution.
      8  */
      9 
     10 #ifndef RL_FULL_SEARCH_SCHEDULER_HPP
     11 #define RL_FULL_SEARCH_SCHEDULER_HPP
     12 #ifdef _MSC_VER
     13 #   pragma once
     14 #endif
     15 
     16 #include "base.hpp"
     17 #include "scheduler.hpp"
     18 #include "foreach.hpp"
     19 
     20 
     21 namespace rl
     22 {
     23 
     24 
     25 template<thread_id_t thread_count>
     26 struct tree_search_scheduler_thread_info : scheduler_thread_info
     27 {
     28     unsigned                    yield_sched_count_ [thread_count];
     29     unsigned                    yield_priority_ [thread_count];
     30     unsigned                    total_yield_priority_;
     31     //unsigned                    subsequent_timed_waits_;
     32 
     33     void reset(test_params& params)
     34     {
     35         scheduler_thread_info::reset(params);
     36         foreach<thread_count>(yield_sched_count_, &assign_zero_u);
     37         foreach<thread_count>(yield_priority_, &assign_zero_u);
     38         total_yield_priority_ = 0;
     39         //subsequent_timed_waits_ = 0;
     40     }
     41 };
     42 
     43 
     44 
     45 
     46 template<typename derived_t, typename thread_info_type, thread_id_t thread_count>
     47 class tree_search_scheduler
     48     : public scheduler<derived_t, thread_info_type, thread_count>
     49 {
     50 public:
     51     typedef scheduler<derived_t, thread_info_type, thread_count> base_t;
     52     typedef typename base_t::thread_info_t thread_info_t;
     53     typedef typename base_t::shared_context_t shared_context_t;
     54 
     55     struct task_t
     56     {
     57     };
     58 
     59     tree_search_scheduler(test_params& params, shared_context_t& ctx, thread_id_t dynamic_thread_count)
     60         : base_t(params, ctx, dynamic_thread_count)
     61         , stree_depth_()
     62         , iteration_count_mean_()
     63         , iteration_count_probe_count_()
     64     {
     65         stree_.reserve(128);
     66     }
     67 
     68     thread_id_t iteration_begin_impl()
     69     {
     70         stree_depth_ = 0;
     71 
     72         unsigned const index = rand_impl(this->running_threads_count, sched_type_sched);
     73         thread_id_t const th = this->running_threads[index];
     74         return th;
     75     }
     76 
     77     bool iteration_end_impl()
     78     {
     79         RL_VERIFY(stree_depth_ == stree_.size());
     80 
     81         for (size_t i = stree_.size(); i != 0; --i)
     82         {
     83             stree_node& n = stree_[i - 1];
     84             if (n.index_ != n.count_ - 1)
     85             {
     86                 stree_.resize(i);
     87                 n.index_ += 1;
     88                 RL_VERIFY(n.index_ < n.count_);
     89                 return false;
     90             }
     91         }
     92         return true;
     93     }
     94 
     95     void yield_priority(unsigned yield)
     96     {
     97         RL_VERIFY(yield);
     98 
     99         thread_info_t& t = *this->thread_;
    100         thread_id_t const& running_thread_count = this->running_threads_count;
    101 
    102         for (thread_id_t i = 0; i != thread_count; ++i)
    103         {
    104             thread_info_t& y = this->threads_[i];
    105             RL_VERIFY(0 == y.yield_priority_[t.index_]);
    106 
    107             if (t.index_ != i
    108                 && y.yield_sched_count_[t.index_] < yield
    109                 && y.state_ != thread_state_finished)
    110             {
    111                 y.yield_priority_[t.index_] = yield;
    112                 y.total_yield_priority_ += yield;
    113                 this->block_thread(t.index_, false);
    114             }
    115             y.yield_sched_count_[t.index_] = 0;
    116         }
    117 
    118         if (0 == running_thread_count)
    119             purge_blocked_threads();
    120     }
    121 
    122     thread_id_t schedule_impl(unpark_reason& reason, unsigned yield)
    123     {
    124         thread_info_t& t = *this->thread_;
    125         thread_id_t const& running_thread_count = this->running_threads_count;
    126 
    127 #ifdef _DEBUG
    128         {
    129             unsigned tmp = 0;
    130             for (thread_id_t i = 0; i != thread_count; ++i)
    131                 tmp += t.yield_priority_[i];
    132             RL_VERIFY(t.total_yield_priority_ == tmp);
    133         }
    134 #endif
    135 
    136         if (t.total_yield_priority_)
    137         {
    138             for (thread_id_t i = 0; i != thread_count; ++i)
    139             {
    140                 unsigned& prio = t.yield_priority_[i];
    141                 if (prio)
    142                 {
    143                     prio -= 1;
    144                     t.total_yield_priority_ -= 1;
    145                     if (0 == prio)
    146                     {
    147                         this->unblock_thread(i);
    148                     }
    149                 }
    150                 t.yield_sched_count_[i] += 1;
    151             }
    152         }
    153 
    154         if (yield)
    155             yield_priority(yield);
    156 
    157         reason = unpark_reason_normal;
    158         thread_id_t thread_index = 0;
    159 
    160         if (self().can_switch(t)
    161             || t.state_ != thread_state_running)
    162         {
    163             thread_id_t timed_thread_count = this->timed_thread_count_;
    164             if (timed_thread_count)
    165             {
    166                 thread_id_t cnt;
    167                 if (running_thread_count)
    168                     cnt = timed_thread_count + 1;
    169                 else
    170                     //!!! spurious thread will be never unblocked in such case - bad
    171                     cnt = timed_thread_count;
    172                 thread_id_t idx = this->rand(cnt, sched_type_user);
    173                 if (idx < timed_thread_count)
    174                 {
    175                     thread_info_t* thr = this->timed_threads_[idx];
    176                     thread_index = thr->index_;
    177                     //??? suboptimal state space exploration
    178                     // if (1 != thr->block_count_) then we are making
    179                     // superfluous rand()
    180                     if (1 == thr->block_count_)
    181                     {
    182                         this->unpark_thread(thread_index);
    183                         RL_VERIFY(thr->state_ == thread_state_running);
    184                         reason = unpark_reason_timeout;
    185                     }
    186                 }
    187             }
    188 
    189             RL_VERIFY(running_thread_count);
    190 
    191             if (unpark_reason_normal == reason)
    192             {
    193                 thread_id_t spurious_thread_count = this->spurious_thread_count_;
    194                 if (spurious_thread_count)
    195                 {
    196                     thread_id_t cnt = spurious_thread_count + 1;
    197                     thread_id_t idx = this->rand(cnt, sched_type_user);
    198                     if (idx < spurious_thread_count)
    199                     {
    200                         thread_info_t* thr = this->spurious_threads_[idx];
    201                         thread_index = thr->index_;
    202                         //??? suboptimal state space exploration
    203                         // if (1 != thr->block_count_) then we are making
    204                         // superfluous rand()
    205                         if (1 == thr->block_count_)
    206                         {
    207                             this->unpark_thread(thread_index);
    208                             RL_VERIFY(thr->state_ == thread_state_running);
    209                             reason = unpark_reason_spurious;
    210                         }
    211                     }
    212                 }
    213             }
    214 
    215             if (unpark_reason_normal == reason)
    216             {
    217                 if (1 != running_thread_count)
    218                 {
    219                     unsigned const index = this->rand(running_thread_count, sched_type_sched);
    220                     thread_index = this->running_threads[index];
    221                 }
    222                 else
    223                 {
    224                     thread_index = this->running_threads[0];
    225                 }
    226             }
    227         }
    228         else
    229         {
    230             RL_VERIFY(t.state_ == thread_state_running);
    231             thread_index = t.index_;
    232         }
    233 
    234         if (t.index_ == thread_index)
    235             return thread_index;
    236 
    237         //t.subsequent_timed_waits_ = 0;
    238         self().on_switch(t);
    239 
    240         return thread_index;
    241     }
    242 
    243     void thread_finished_impl()
    244     {
    245     }
    246 
    247     void purge_blocked_threads()
    248     {
    249         for (thread_id_t i = 0; i != thread_count; ++i)
    250         {
    251             on_thread_block(i, false);
    252         }
    253     }
    254 
    255     unsigned rand_impl(unsigned limit, sched_type t)
    256     {
    257         unsigned result = 0;
    258         size_t const size = stree_.size();
    259         if (stree_depth_ == size)
    260         {
    261             stree_node n = {limit, 0, t};
    262             stree_.push_back(n);
    263         }
    264         else
    265         {
    266             RL_VERIFY(size);
    267             stree_node& n = stree_[stree_depth_];
    268 
    269             // If you hit assert here, then probably your test is non-deterministic
    270             // Check whether you are using functions like ::rand()
    271             // or static variables or values of object addresses (for hashing) in your test
    272             // Replace ::rand() with rl::rand(), eliminate static variables in the test
    273             RL_VERIFY(n.type_ == t);
    274 
    275             RL_VERIFY(n.count_ == limit);
    276             RL_VERIFY(n.index_ < n.count_);
    277             result = n.index_;
    278         }
    279         stree_depth_ += 1;
    280         return result;
    281     }
    282 
    283     iteration_t iteration_count_impl()
    284     {
    285         double current = self().iteration_count_approx();
    286         if (current <= this->iter_)
    287             current = this->iter_ + 1.0;
    288 
    289         iteration_count_mean_ *= iteration_count_probe_count_;
    290         iteration_count_probe_count_ += 1;
    291         iteration_count_mean_ /= iteration_count_probe_count_;
    292         iteration_count_mean_ += current / iteration_count_probe_count_;
    293 
    294         iteration_t result = (iteration_t)(iteration_count_mean_ + 0.5);
    295         if (result <= this->iter_)
    296             result = this->iter_ + 1;
    297         return result;
    298     }
    299 
    300     void get_state_impl(std::ostream& ss)
    301     {
    302         ss << (unsigned)stree_.size() << " ";
    303         for (size_t i = 0; i != stree_.size(); ++i)
    304         {
    305             stree_node& n = stree_[i];
    306             ss << n.count_ << " ";
    307             ss << n.index_ << " ";
    308             ss << static_cast<unsigned>(n.type_) << " ";
    309         }
    310     }
    311 
    312     void set_state_impl(std::istream& ss)
    313     {
    314         size_t size = 0;
    315         ss >> size;
    316         for (size_t i = 0; i != size; ++i)
    317         {
    318             stree_node n = {};
    319             ss >> n.count_;
    320             ss >> n.index_;
    321             unsigned type = 0;
    322             ss >> type;
    323             n.type_ = static_cast<sched_type>(type);
    324             stree_.push_back(n);
    325         }
    326     }
    327 
    328     void on_thread_block(thread_id_t th, bool yield)
    329     {
    330         //!!! doubled in schedule_impl()
    331         thread_info_t& t = this->threads_[th];
    332         if (t.total_yield_priority_)
    333         {
    334             for (thread_id_t i = 0; i != thread_count; ++i)
    335             {
    336                 if (t.yield_priority_[i])
    337                 {
    338                     t.total_yield_priority_ -= t.yield_priority_[i];
    339                     t.yield_priority_[i] = 0;
    340                     this->unblock_thread(i);
    341                 }
    342             }
    343         }
    344 
    345         (void)yield;
    346         //if (yield)
    347         //    yield_priority(1);
    348     }
    349 
    350 protected:
    351     struct stree_node
    352     {
    353         unsigned    count_;
    354         unsigned    index_;
    355         sched_type  type_;
    356         unsigned    pad_;
    357     };
    358 
    359     typedef typename vector<stree_node>::type stree_t;
    360     stree_t         stree_;
    361     size_t          stree_depth_;
    362 
    363 private:
    364     double          iteration_count_mean_;
    365     unsigned        iteration_count_probe_count_;
    366 
    367     derived_t& self()
    368     {
    369         return *static_cast<derived_t*>(this);
    370     }
    371 
    372     RL_NOCOPY(tree_search_scheduler);
    373 };
    374 
    375 
    376 
    377 
    378 template<thread_id_t thread_count>
    379 class full_search_scheduler
    380     : public tree_search_scheduler<full_search_scheduler<thread_count>
    381         , tree_search_scheduler_thread_info<thread_count>, thread_count>
    382 {
    383 public:
    384     typedef tree_search_scheduler<full_search_scheduler<thread_count>
    385         , tree_search_scheduler_thread_info<thread_count>, thread_count> base_t;
    386     typedef typename base_t::thread_info_t thread_info_t;
    387     typedef typename base_t::shared_context_t shared_context_t;
    388 
    389     full_search_scheduler(test_params& params, shared_context_t& ctx, thread_id_t dynamic_thread_count)
    390         : base_t(params, ctx, dynamic_thread_count)
    391     {
    392     }
    393 
    394     bool can_switch(thread_info_t& /*t*/)
    395     {
    396         return true;
    397     }
    398 
    399     void on_switch(thread_info_t& /*t*/)
    400     {
    401     }
    402 
    403     double iteration_count_approx()
    404     {
    405         double total = 1;
    406         size_t const size = this->stree_.size();
    407         for (size_t i = 0; i != size; ++i)
    408         {
    409             total *= this->stree_[i].count_;
    410         }
    411         return total;
    412     }
    413 
    414     RL_NOCOPY(full_search_scheduler);
    415 };
    416 
    417 
    418 }
    419 
    420 #endif
    421