Scheduler/FIFORunner.cc

   1 // $Id$
   2 //
   3 // Copyright (C) 2008
   4 // Fraunhofer Institute for Open Communication Systems (FOKUS)
   5 // Competence Center NETwork research (NET), St. Augustin, GERMANY
   6 //     Stefan Bund <g0dil@berlios.de>
   7 //
   8 // This program is free software; you can redistribute it and/or modify
   9 // it under the terms of the GNU General Public License as published by
  10 // the Free Software Foundation; either version 2 of the License, or
  11 // (at your option) any later version.
  12 //
  13 // This program is distributed in the hope that it will be useful,
  14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 // GNU General Public License for more details.
  17 //
  18 // You should have received a copy of the GNU General Public License
  19 // along with this program; if not, write to the
  20 // Free Software Foundation, Inc.,
  21 // 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  22
  23 /** \file
  24     \brief FIFORunner non-inline non-template implementation */
  25
  26 #include "FIFORunner.hh"
  27 //#include "FIFORunner.ih"
  28
  29 // Custom includes
  30 #include <signal.h>
  31 #include <time.h>
  32 #include <boost/lambda/lambda.hpp>
  33 #include "../Utils/Exception.hh"
  34 #include "../Utils/senfassert.hh"
  35 #include "../Utils/ScopeExit.hh"
  36
  37 //#include "FIFORunner.mpp"
  38 #define prefix_
  39 ///////////////////////////////cc.p////////////////////////////////////////
  40
  41 prefix_ senf::scheduler::detail::FIFORunner::FIFORunner()
  42     : tasks_ (), next_ (tasks_.end()), watchdogRunning_ (false), watchdogMs_ (1000),
  43       watchdogCount_(0), hangCount_ (0)
  44 {
  45     struct sigevent ev;
  46     ::memset(&ev, 0, sizeof(ev));
  47     ev.sigev_notify = SIGEV_SIGNAL;
  48     ev.sigev_signo = SIGURG;
  49     ev.sigev_value.sival_ptr = this;
  50     if (timer_create(CLOCK_MONOTONIC, &ev, &watchdogId_) < 0)
  51         SENF_THROW_SYSTEM_EXCEPTION("timer_create()");
  52
  53     struct sigaction sa;
  54     ::memset(&sa, 0, sizeof(sa));
  55     sa.sa_sigaction = &watchdog;
  56     sa.sa_flags = SA_SIGINFO;
  57     if (sigaction(SIGURG, &sa, 0) < 0)
  58         SENF_THROW_SYSTEM_EXCEPTION("sigaction()");
  59
  60     sigset_t mask;
  61     sigemptyset(&mask);
  62     sigaddset(&mask, SIGURG);
  63     if (sigprocmask(SIG_UNBLOCK, &mask, 0) < 0)
  64         SENF_THROW_SYSTEM_EXCEPTION("sigprocmask()");
  65
  66     tasks_.push_back(highPriorityEnd_);
  67     tasks_.push_back(normalPriorityEnd_);
  68 }
  69
  70 prefix_ senf::scheduler::detail::FIFORunner::~FIFORunner()
  71 {
  72     timer_delete(watchdogId_);
  73     signal(SIGURG, SIG_DFL);
  74 }
  75
  76 prefix_ void senf::scheduler::detail::FIFORunner::startWatchdog()
  77 {
  78     struct itimerspec timer;
  79     ::memset(&timer, 0, sizeof(timer));
  80
  81     timer.it_interval.tv_sec = watchdogMs_ / 1000;
  82     timer.it_interval.tv_nsec = (watchdogMs_ % 1000) * 1000000ul;
  83     timer.it_value.tv_sec = timer.it_interval.tv_sec;
  84     timer.it_value.tv_nsec = timer.it_interval.tv_nsec;
  85
  86     if (timer_settime(watchdogId_, 0, &timer, 0) < 0)
  87         SENF_THROW_SYSTEM_EXCEPTION("timer_settime()");
  88
  89     watchdogRunning_ = true;
  90 }
  91
  92 prefix_ void senf::scheduler::detail::FIFORunner::stopWatchdog()
  93 {
  94     struct itimerspec timer;
  95     ::memset(&timer, 0, sizeof(timer));
  96
  97     if (timer_settime(watchdogId_, 0, &timer, 0) < 0)
  98         SENF_THROW_SYSTEM_EXCEPTION("timer_settime()");
  99
 100     watchdogRunning_ = false;
 101 }
 102
 103 // At the moment, the FIFORunner is not very efficient with many non-runnable tasks since the
 104 // complete list of tasks is traversed on each run().
 105 //
 106 // To optimize this, we woould need a way to find the relative ordering of two tasks in O(1) (at the
 107 // moment, this is an O(N) operation by traversing the list).
 108 //
 109 // One idea is, to give each task an 'order' value. Whenever a task is added at the end, it's order
 110 // value is set to the order value of the last task + 1. Whenever the order value such added exceeds
 111 // some threshold (e.g. 2^31 -1 or some such), the task list is traversed from beginning to end to
 112 // assign new consecutive order values. This O(N) operation is so seldom, that it is amortized over
 113 // a very long time.
 114 //
 115 // With this value at hand, we can do several optimizations: One idea would be the following: The
 116 // runnable set always has two types of tasks: There are tasks, which are heavily active and are
 117 // signaled constantly and other tasks which lie dormant most of the time. Those dormant tasks will
 118 // end up at the beginning of the task queue.
 119 //
 120 // With the above defined 'ordering' field available, we can manage an iterator pointing to the
 121 // first and the last runnable task. This will often help a lot since the group of runnable tasks
 122 // will mostly be localized to the end of the queue. only occasionally one of the dormant tasks will
 123 // be runnable. This additional traversal time will be amortized over a larger time.
 124
 125 prefix_ void senf::scheduler::detail::FIFORunner::dequeue(TaskInfo * task)
 126 {
 127     TaskList::iterator i (TaskList::current(*task));
 128     if (next_ == i)
 129         ++next_;
 130     tasks_.erase(i);
 131 }
 132
 133 prefix_ void senf::scheduler::detail::FIFORunner::run()
 134 {
 135     TaskList::iterator f (tasks_.begin());
 136     TaskList::iterator l (TaskList::current(highPriorityEnd_));
 137     run(f, l);
 138
 139     f = l; ++f;
 140     l = TaskList::current(normalPriorityEnd_);
 141     run(f, l);
 142
 143     f = l; ++f;
 144     l = tasks_.end();
 145     run(f, l);
 146 }
 147
 148 prefix_ void senf::scheduler::detail::FIFORunner::run(TaskList::iterator f, TaskList::iterator l)
 149 {
 150     if (f == l)
 151         // We'll have problems inserting NullTask between f and l below, so just explicitly bail out
 152         return;
 153
 154     // This algorithm is carefully adjusted to make it work even when arbitrary tasks are removed
 155     // from the queue
 156     // - Before we begin, we add a NullTask to the queue. The only purpose of this node is, to mark
 157     //   the current end of the queue. The iterator to this node becomes the end iterator of the
 158     //   range to process
 159     // - We update the TaskInfo and move it to the next queue Element before calling the callback so
 160     //   we don't access the TaskInfo if it is removed while the callback is running
 161     // - We keep the next to-be-processed node in a class variable which is checked and updated
 162     //   whenever a node is removed.
 163
 164     NullTask null;
 165     tasks_.insert(l, null);
 166     TaskList::iterator end (TaskList::current(null));
 167     next_ = f;
 168
 169     using namespace boost::lambda;
 170     ScopeExit atExit ((
 171                           var(watchdogCount_) = 0,
 172                           var(next_) = l
 173                           ));
 174
 175     while (next_ != end) {
 176         TaskInfo & task (*next_);
 177         if (task.runnable_) {
 178             task.runnable_ = false;
 179             runningName_ = task.name();
 180 #       ifdef SENF_DEBUG
 181             runningBacktrace_ = task.backtrace_;
 182 #       endif
 183             TaskList::iterator i (next_);
 184             ++ next_;
 185             tasks_.splice(l, tasks_, i);
 186             watchdogCount_ = 1;
 187             task.run();
 188         }
 189         else
 190             ++ next_;
 191     }
 192 }
 193
 194 prefix_ senf::scheduler::detail::FIFORunner::TaskList::iterator
 195 senf::scheduler::detail::FIFORunner::priorityEnd(TaskInfo::Priority p)
 196 {
 197     switch (p) {
 198     case senf::scheduler::detail::FIFORunner::TaskInfo::PRIORITY_LOW :
 199         return tasks_.end();
 200     case senf::scheduler::detail::FIFORunner::TaskInfo::PRIORITY_NORMAL :
 201         return TaskList::current(normalPriorityEnd_);
 202     case senf::scheduler::detail::FIFORunner::TaskInfo::PRIORITY_HIGH :
 203         return TaskList::current(highPriorityEnd_);
 204     }
 205     return tasks_.begin();
 206 }
 207
 208 prefix_ void senf::scheduler::detail::FIFORunner::watchdog(int, siginfo_t * si, void *)
 209 {
 210     FIFORunner & runner (*static_cast<FIFORunner *>(si->si_value.sival_ptr));
 211     if (runner.watchdogCount_ > 0) {
 212         ++ runner.watchdogCount_;
 213         if (runner.watchdogCount_ > 2) {
 214             ++ runner.hangCount_;
 215             write(1, "\n\n*** Scheduler task hanging: ", 30);
 216             write(1, runner.runningName_.c_str(), runner.runningName_.size());
 217             write(1, "\n", 1);
 218 #ifdef SENF_DEBUG
 219             write(1, "Task was initialized at\n", 24);
 220             write(1, runner.runningBacktrace_.c_str(), runner.runningBacktrace_.size());
 221 #endif
 222             write(1, "\n", 1);
 223         }
 224     }
 225 }
 226
 227 ///////////////////////////////cc.e////////////////////////////////////////
 228 #undef prefix_
 229 //#include "FIFORunner.mpp"
 230
 231 \f
 232 // Local Variables:
 233 // mode: c++
 234 // fill-column: 100
 235 // comment-column: 40
 236 // c-file-style: "senf"
 237 // indent-tabs-mode: nil
 238 // ispell-local-dictionary: "american"
 239 // compile-command: "scons -u test"
 240 // End: