///////////////////////////////////////////////////////////////////////////// // // Bossa, a framework for scheduler programming // Copyright (C) 2005 Ecole des Mines de Nantes and // Department of Computer Science, University of Copenhagen // // This file is part of Bossa. // // Bossa is free software; you can redistribute it and/or modify // it under the terms of the GNU Lesser General Public License as published by // the Free Software Foundation; either version 2.1 of the License, or // any later version. // // Bossa is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU Lesser General Public License for more details. // // You should have received a copy of the GNU Lesser General Public License // along with Bossa; if not, write to the Free Software // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA // // Please send remarks, questions and bug reports to bossa@emn.fr // or to: // // Gilles Muller // Ecole des Mines de Nantes, // La Chantrerie - 4, rue Alfred Kastler. B.P. 20722 // 44307 NANTES Cedex 3, FRANCE // /////////////////////////////////////////////////////////////////////////////// /* Scott A. Banachowski and Scott A. Brandt. The BEST Scheduler for Integrated Processing of Best-Effort and Soft Real-Time Processes. Multimedia Computing and Networking (MMCN) 2002. Proceedings of the SPIE Vol 4673, 2002. http://www.soe.ucsc.edu/~sbanacho/ */ scheduler Best = { const int maximum_period = 512; const int CPU_bound_offset = 522; /* 512 + 10 */ const int weight_divisor = 3; /* the paper says "a generous threshold that allows any confidence level to pass" */ const int confidence_threshold = 1; const int initial_quantum = 10; process = { int previous_unblock_time; int period; int deadline; int deadline_timer; int quantum; } states = { RUNNING running : process; READY ready : select queue; READY yield : process; BLOCKED blocked : queue; TERMINATED terminated; } ordering_criteria = { lowest deadline } handler (event e) { On process.end { e.target => terminated; } On block.* { if (e.target in running && running.deadline_timer <= 0) { running.deadline = time_to_ticks(now()) + CPU_bound_offset; } e.target => blocked; } On unblock.preemptive { if (e.target in blocked) { int unblock_time = time_to_ticks(now()); int estimated_period = unblock_time - e.target.previous_unblock_time; e.target.period = ((estimated_period + (e.target.period / weight_divisor)) * weight_divisor) / (weight_divisor + 1); if (e.target.period > maximum_period) { e.target.period = maximum_period; } e.target.deadline = unblock_time + e.target.period; e.target.previous_unblock_time = unblock_time; { int confidence = (estimated_period % e.target.period) - (e.target.period / 2); if (confidence < 0) { confidence = -1 * confidence; } if (confidence < confidence_threshold) { e.target.deadline_timer = 0; } else { e.target.deadline_timer = e.target.period; } } if (!empty(running) && e.target > running) { if (running.deadline_timer <= 0) { running.deadline = time_to_ticks(now()) + CPU_bound_offset; } running => ready; } e.target => ready; } } On unblock.nonpreemptive { if (e.target in blocked) { int unblock_time = time_to_ticks(now()); int estimated_period = unblock_time - e.target.previous_unblock_time; e.target.period = ((estimated_period + (e.target.period / weight_divisor)) * weight_divisor) / (weight_divisor + 1); if (e.target.period > maximum_period) { e.target.period = maximum_period; } e.target.deadline = unblock_time + e.target.period; e.target.previous_unblock_time = unblock_time; { int confidence = (estimated_period % e.target.period) - (e.target.period / 2); if (confidence < 0) { confidence = -1 * confidence; } if (confidence < confidence_threshold) { e.target.deadline_timer = 0; } else { e.target.deadline_timer = e.target.period; } } e.target => ready; } } On system.clocktick { running.deadline_timer--; running.quantum--; if (running.quantum == 0) { running.quantum = initial_quantum; if (running.deadline_timer <= 0) { running.deadline = time_to_ticks(now()) + CPU_bound_offset; } running => ready; } } On yield.system.pause.*, yield.user.* { if (e.target in running && running.deadline_timer <= 0) { running.deadline = time_to_ticks(now()) + CPU_bound_offset; } e.target => yield; } On yield.system.immediate.* { if (e.target in running) { if (running.deadline_timer <= 0) { running.deadline = time_to_ticks(now()) + CPU_bound_offset; } e.target => ready; } } On preempt { if (running.deadline_timer <= 0) { running.deadline = time_to_ticks(now()) + CPU_bound_offset; } running => ready; } On bossa.schedule { if (empty(ready)) { yield => ready; } select() => running; if (!empty(yield)) { yield => ready; } } } interface = { void attach (process p) { p.previous_unblock_time = time_to_ticks(now()); p.period = 0; p.deadline = time_to_ticks(now()); p.deadline_timer = 0; p.quantum = 10; p => ready; } void detach (process p) { } } }