/* 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/ */ module Best(RUNNING process running) { 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 initial_quantum; } ordering_criteria = { lowest deadline } handler (event e) { On unblock.preemptive, unblock.nonpreemptive { if (e.target in READY) { } 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; } } } next(); } On system.clocktick { running.deadline_timer--; next(); } } interface = { void attach (requires process p) { p.previous_unblock_time = time_to_ticks(now()); p.period = 0; p.deadline = time_to_ticks(now()); p.deadline_timer = 0; p.initial_quantum = initial_quantum; next(); } } transition (process p) = { On RUNNING => READY, BLOCKED { if (p.deadline_timer <= 0) { p.deadline = time_to_ticks(now()) + CPU_bound_offset; } } } }