/////////////////////////////////////////////////////////////////////////////
//
// 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) { }
  }
}