schedule_rbed.c File Reference

Kernel scheduling policy: Rate-Based Earliest Deadline (RBED) More...

Macros
#define	SPECTRUM   1000000
#define	BETA   (SPECTRUM / 10)

Functions
struct dcb *	schedule (void)
	Scheduler policy. More...
void	scheduler_remove (struct dcb *dcb)
	Remove 'dcb' from scheduler ring. More...
void	scheduler_yield (struct dcb *dcb)
	Yield 'dcb' for the rest of the current timeslice. More...

Detailed Description

Kernel scheduling policy: Rate-Based Earliest Deadline (RBED)

The algorithm is described in the paper "Dynamic Integrated Scheduling of Hard Real-Time, Soft Real-Time and Non-Real-Time Processes" by Scott A. Brandt of UC Santa Cruz.

Note that while in the paper real number arithmetic is used on some variables, we employ fixed-point integer arithmetic within SPECTRUM in these cases.

Macro Definition Documentation

#define BETA   (SPECTRUM / 10)

Minimum resource rate reserved for best-effort processes, in SPECTRUM. We set this to 10%.

#define SPECTRUM   1000000

Implementation Notes

real-time tasks: the behaviour of real-time tasks is characterized by four parameters: wcet (worst case execution time), period, (relative) deadline, and release_time. Besides release_time, the values of these parameters are not changed by the scheduler. RT tasks are considered to be periodic. Note that the interpretation of the parameters is a little different than the original RBED paper.

->release_time is the time that the task is ready to be scheduled. RT tasks with ->release_time in the future are not effectively considered to be on the runqueue and are ignored by the scheduler. In order to meet its deadline the task needs to be scheduled no later than ->release_time + deadline - wcet. EDF guarantees this property, as long as the utilization rate is <= 1.

The execution of an rt task for a particular period ends either when: (a) the task runs outs of budget (->etime >= ->wcet), or (b) the task yields using scheduler_yield(). When this happens the task's ->etime is reset to 0, while ->release_time is increased by ->period. Note that scheduler_remove() does not finalize the current period of the task. Also, note that depending on ->period, there might be a case that an rt task is not executed, even if the CPU is idle.

best-effort tasks: for best-effort tasks the scheduler is responsible to assigns proper values the RT parameters. Also, To prioritize between BE tasks, the scheduler uses ->weight.

Function Documentation

struct dcb* schedule

(

void

)

Scheduler policy.

Returns

Next DCB to schedule or NULL if wait for interrupts.

void scheduler_remove

(

struct dcb *

dcb

)

Remove 'dcb' from scheduler ring.

Removes dispatcher 'dcb' from the scheduler ring. If it was not in the ring, this function is a no-op. The postcondition for this function is that dcb is not in the ring.

Parameters

dcb	Pointer to DCB to remove.

void scheduler_yield

(

struct dcb *

dcb

)

Yield 'dcb' for the rest of the current timeslice.

Re-sorts 'dcb' into the scheduler queue with its release time increased by the timeslice period. It is an error to yield a dispatcher not in the scheduler queue.

Parameters

dcb	Pointer to DCB to remove.