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
  31 //#include "FIFORunner.mpp"
  32 #define prefix_
  33 ///////////////////////////////cc.p////////////////////////////////////////
  34
  35 // At the moment, the FIFORunner is not very efficient with many non-runnable tasks since the
  36 // complete list of tasks is traversed on each run().
  37 //
  38 // To optimize this, we woould need a way to find the relative ordering of two tasks in O(1) (at the
  39 // moment, this is an O)(N) operation by traversing the list).
  40 //
  41 // One idea is, to give each task an 'order' value. Whenever a task is added at the end, it's order
  42 // value is set to the order value of the last task + 1. Whenever the order value such added exceeds
  43 // some threshold (e.g. 2^31 -1 or some such), the task list is traversed from beginning to end to
  44 // assign new consecutive order values. This O(N) operation is so seldom, that it is amortized over
  45 // a very long time.
  46 //
  47 // With this value at hand, we can do several optimizations: One idea would be the following: The
  48 // runnable set always has two types of tasks: There are tasks, which are heavily active and are
  49 // signaled constantly and other tasks which lie dormant most of the time. Those dormant tasks will
  50 // end up at the beginning of the task queue.
  51 //
  52 // With the above defined 'ordering' field available, we can manage an iterator pointing to the
  53 // first and the last runnable task. This will often help a lot since the group of runnable tasks
  54 // will mostly be localized to the end of the queue. only occasionally one of the dormant tasks will
  55 // be runnable. This additional traversal time will be amortized over a larger time.
  56
  57 prefix_ void senf::scheduler::FIFORunner::dequeue(TaskInfo * task)
  58 {
  59     TaskList::iterator i (TaskList::current(*task));
  60     if (next_ == i)
  61         ++next_;
  62     tasks_.erase(i);
  63 }
  64
  65 namespace {
  66     struct NullTask
  67         : public senf::scheduler::FIFORunner::TaskInfo
  68     {
  69         void run() {};
  70     };
  71 }
  72
  73 prefix_ void senf::scheduler::FIFORunner::run()
  74 {
  75     // This algorithm is carefully adjusted to make it work even when arbitrary tasks are removed
  76     // from the queue
  77     // - Before we begin, we add a NullTask to the queue. The only purpose of this node is, to mark
  78     //   the current end of the queue. The iterator to this node becomes the end iterator of the
  79     //   range to process
  80     // - We update the TaskInfo and move it to the end of the queue before calling the callback so
  81     //   we don't access the TaskInfo if it is removed while the callback is running
  82     // - We keep the next to-be-processed node in a class variable which is checked and updated
  83     //   whenever a node is removed.
  84     NullTask null;
  85     tasks_.push_back(null);
  86     TaskList::iterator end (TaskList::current(null));
  87     next_ = tasks_.begin();
  88     while (next_ != end) {
  89         TaskInfo & task (*next_);
  90         if (task.runnable) {
  91             task.runnable = false;
  92             TaskList::iterator i (next_);
  93             ++ next_;
  94             tasks_.splice(tasks_.end(), tasks_, i);
  95             task.run();
  96         }
  97         else
  98             ++ next_;
  99     }
 100     tasks_.erase(end);
 101     next_ = tasks_.end();
 102 }
 103
 104 ///////////////////////////////cc.e////////////////////////////////////////
 105 #undef prefix_
 106 //#include "FIFORunner.mpp"
 107
 108 \f
 109 // Local Variables:
 110 // mode: c++
 111 // fill-column: 100
 112 // comment-column: 40
 113 // c-file-style: "senf"
 114 // indent-tabs-mode: nil
 115 // ispell-local-dictionary: "american"
 116 // compile-command: "scons -u test"
 117 // End: