4 // Fraunhofer Institute for Open Communication Systems (FOKUS)
5 // Competence Center NETwork research (NET), St. Augustin, GERMANY
6 // Stefan Bund <g0dil@berlios.de>
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.
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.
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.
24 \brief FIFORunner non-inline non-template implementation */
26 #include "FIFORunner.hh"
27 //#include "FIFORunner.ih"
32 #include "../Utils/Exception.hh"
34 //#include "FIFORunner.mpp"
36 ///////////////////////////////cc.p////////////////////////////////////////
38 prefix_ senf::scheduler::FIFORunner::FIFORunner()
39 : tasks_ (), next_ (tasks_.end()), watchdogMs_ (1000), watchdogCount_(0), hangCount_ (0)
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()");
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()");
58 sigaddset(&mask, SIGURG);
59 if (sigprocmask(SIG_UNBLOCK, &mask, 0) < 0)
60 SENF_THROW_SYSTEM_EXCEPTION("sigprocmask()");
63 prefix_ senf::scheduler::FIFORunner::~FIFORunner()
65 timer_delete(watchdogId_);
66 signal(SIGURG, SIG_DFL);
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().
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).
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
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.
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.
91 prefix_ void senf::scheduler::FIFORunner::dequeue(TaskInfo * task)
93 TaskList::iterator i (TaskList::current(*task));
101 : public senf::scheduler::FIFORunner::TaskInfo
107 prefix_ void senf::scheduler::FIFORunner::run()
109 // This algorithm is carefully adjusted to make it work even when arbitrary tasks are removed
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
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.
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_);
132 task.runnable = false;
133 runningName_ = task.name;
135 runningBacktrace_ = task.backtrace;
137 TaskList::iterator i (next_);
139 tasks_.splice(tasks_.end(), tasks_, i);
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()");
154 next_ = tasks_.end();
157 prefix_ void senf::scheduler::FIFORunner::watchdog(int, siginfo_t * si, void *)
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());
168 write(1, "Task was initialized at\n", 24);
169 write(1, runner.runningBacktrace_.c_str(), runner.runningBacktrace_.size());
176 ///////////////////////////////cc.e////////////////////////////////////////
178 //#include "FIFORunner.mpp"
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"