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 "../Utils/Exception.hh"
  33
  34 //#include "FIFORunner.mpp"
  35 #define prefix_
  36 ///////////////////////////////cc.p////////////////////////////////////////
  37
  38 prefix_ senf::scheduler::FIFORunner::FIFORunner()
  39     : tasks_ (), next_ (tasks_.end()), watchdogMs_ (1000), watchdogCount_(0), hangCount_ (0)
  40 {
  41     struct sigevent ev;
  42     ::memset(&ev, 0, sizeof(ev));
  43     ev.sigev_notify = SIGEV_SIGNAL;
  44     ev.sigev_signo = SIGURG;
  45     ev.sigev_value.sival_ptr = this;
  46     if (timer_create(CLOCK_MONOTONIC, &ev, &watchdogId_) < 0)
  47         SENF_THROW_SYSTEM_EXCEPTION("timer_create()");
  48
  49     struct sigaction sa;
  50     ::memset(&sa, 0, sizeof(sa));
  51     sa.sa_sigaction = &watchdog;
  52     sa.sa_flags = SA_SIGINFO;
  53     if (sigaction(SIGURG, &sa, 0) < 0)
  54         SENF_THROW_SYSTEM_EXCEPTION("sigaction()");
  55
  56     sigset_t mask;
  57     sigemptyset(&mask);
  58     sigaddset(&mask, SIGURG);
  59     if (sigprocmask(SIG_UNBLOCK, &mask, 0) < 0)
  60         SENF_THROW_SYSTEM_EXCEPTION("sigprocmask()");
  61 }
  62
  63 prefix_ senf::scheduler::FIFORunner::~FIFORunner()
  64 {
  65     timer_delete(watchdogId_);
  66     signal(SIGURG, SIG_DFL);
  67 }
  68
  69 // At the moment, the FIFORunner is not very efficient with many non-runnable tasks since the
  70 // complete list of tasks is traversed on each run().
  71 //
  72 // To optimize this, we woould need a way to find the relative ordering of two tasks in O(1) (at the
  73 // moment, this is an O(N) operation by traversing the list).
  74 //
  75 // One idea is, to give each task an 'order' value. Whenever a task is added at the end, it's order
  76 // value is set to the order value of the last task + 1. Whenever the order value such added exceeds
  77 // some threshold (e.g. 2^31 -1 or some such), the task list is traversed from beginning to end to
  78 // assign new consecutive order values. This O(N) operation is so seldom, that it is amortized over
  79 // a very long time.
  80 //
  81 // With this value at hand, we can do several optimizations: One idea would be the following: The
  82 // runnable set always has two types of tasks: There are tasks, which are heavily active and are
  83 // signaled constantly and other tasks which lie dormant most of the time. Those dormant tasks will
  84 // end up at the beginning of the task queue.
  85 //
  86 // With the above defined 'ordering' field available, we can manage an iterator pointing to the
  87 // first and the last runnable task. This will often help a lot since the group of runnable tasks
  88 // will mostly be localized to the end of the queue. only occasionally one of the dormant tasks will
  89 // be runnable. This additional traversal time will be amortized over a larger time.
  90
  91 prefix_ void senf::scheduler::FIFORunner::dequeue(TaskInfo * task)
  92 {
  93     TaskList::iterator i (TaskList::current(*task));
  94     if (next_ == i)
  95         ++next_;
  96     tasks_.erase(i);
  97 }
  98
  99 namespace {
 100     struct NullTask
 101         : public senf::scheduler::FIFORunner::TaskInfo
 102     {
 103         void run() {};
 104     };
 105 }
 106
 107 prefix_ void senf::scheduler::FIFORunner::run()
 108 {
 109     // This algorithm is carefully adjusted to make it work even when arbitrary tasks are removed
 110     // from the queue
 111     // - Before we begin, we add a NullTask to the queue. The only purpose of this node is, to mark
 112     //   the current end of the queue. The iterator to this node becomes the end iterator of the
 113     //   range to process
 114     // - We update the TaskInfo and move it to the end of the queue before calling the callback so
 115     //   we don't access the TaskInfo if it is removed while the callback is running
 116     // - We keep the next to-be-processed node in a class variable which is checked and updated
 117     //   whenever a node is removed.
 118     NullTask null;
 119     tasks_.push_back(null);
 120     TaskList::iterator end (TaskList::current(null));
 121     next_ = tasks_.begin();
 122     struct itimerspec timer;
 123     timer.it_interval.tv_sec = watchdogMs_ / 1000;
 124     timer.it_interval.tv_nsec = (watchdogMs_ % 1000) * 1000000ul;
 125     timer.it_value.tv_sec = timer.it_interval.tv_sec;
 126     timer.it_value.tv_nsec = timer.it_interval.tv_nsec;
 127     if (timer_settime(watchdogId_, 0, &timer, 0) < 0)
 128         SENF_THROW_SYSTEM_EXCEPTION("timer_settime()");
 129     while (next_ != end) {
 130         TaskInfo & task (*next_);
 131         if (task.runnable) {
 132             task.runnable = false;
 133             runningName_ = task.name;
 134 #       ifdef SENF_DEBUG
 135             runningBacktrace_ = task.backtrace;
 136 #       endif
 137             TaskList::iterator i (next_);
 138             ++ next_;
 139             tasks_.splice(tasks_.end(), tasks_, i);
 140             watchdogCount_ = 1;
 141             task.run();
 142         }
 143         else
 144             ++ next_;
 145     }
 146     watchdogCount_ = 0;
 147     timer.it_interval.tv_sec = 0;
 148     timer.it_interval.tv_nsec = 0;
 149     timer.it_value.tv_sec = 0;
 150     timer.it_value.tv_nsec = 0;
 151     if (timer_settime(watchdogId_, 0, &timer, 0) < 0)
 152         SENF_THROW_SYSTEM_EXCEPTION("timer_settime()");
 153     tasks_.erase(end);
 154     next_ = tasks_.end();
 155 }
 156
 157 prefix_ void senf::scheduler::FIFORunner::watchdog(int, siginfo_t * si, void *)
 158 {
 159     FIFORunner & runner (*static_cast<FIFORunner *>(si->si_value.sival_ptr));
 160     if (runner.watchdogCount_ > 0) {
 161         ++ runner.watchdogCount_;
 162         if (runner.watchdogCount_ > 2) {
 163             ++ runner.hangCount_;
 164             write(1, "\n\n*** Scheduler task hanging: ", 30);
 165             write(1, runner.runningName_.c_str(), runner.runningName_.size());
 166             write(1, "\n", 1);
 167 #ifdef SENF_DEBUG
 168             write(1, "Task was initialized at\n", 24);
 169             write(1, runner.runningBacktrace_.c_str(), runner.runningBacktrace_.size());
 170 #endif
 171             write(1, "\n", 1);
 172         }
 173     }
 174 }
 175
 176 ///////////////////////////////cc.e////////////////////////////////////////
 177 #undef prefix_
 178 //#include "FIFORunner.mpp"
 179
 180 \f
 181 // Local Variables:
 182 // mode: c++
 183 // fill-column: 100
 184 // comment-column: 40
 185 // c-file-style: "senf"
 186 // indent-tabs-mode: nil
 187 // ispell-local-dictionary: "american"
 188 // compile-command: "scons -u test"
 189 // End: