D.2.6 Earliest Deadline First Dispatching
{
AI95-00357-01}
The deadline of a task is an indication of the urgency of the task; it
represents a point on an ideal physical time line. The deadline might
affect how resources are allocated to the task.
{
AI95-00357-01}
{
AI05-0229-1}
{
AI05-0299-1}
This subclause defines a package for representing the deadline of a task
and a dispatching policy that defines Earliest Deadline First (EDF) dispatching.
An aspect is defined to assign an initial deadline to a task.
Discussion: {
AI05-0229-1}
This aspect is the only way of assigning an initial deadline to a task
so that its activation can be controlled by EDF scheduling. This is similar
to the way aspect Priority is used to give an initial priority to a task.
Language Design Principles
{
AI95-00357-01}
{
AI05-0299-1}
To predict the behavior of a multi-tasking program it is necessary to
control access to the processor which is preemptive, and shared objects
which are usually non-preemptive and embodied in protected objects. Two
common dispatching policies for the processor are fixed priority and
EDF. The most effective control over shared objects is via preemption
levels. With a pure priority scheme a single notion of priority is used
for processor dispatching and preemption levels. With EDF and similar
schemes priority is used for preemption levels (only), with another measure
used for dispatching. T.P. Baker showed (
Real-Time Systems, March
1991, vol. 3, num. 1,
Stack-Based Scheduling of Realtime Processes)
that for EDF a newly released task should only preempt the currently
running task if it has an earlier deadline and a higher preemption level
than any currently “locked” protected object. The rules of
this subclause implement this scheme including the case where the newly
released task should execute before some existing tasks but not preempt
the currently executing task.
Static Semantics
{
AI95-00357-01}
The following language-defined library package exists:
with Ada.Real_Time;
with Ada.Task_Identification;
package Ada.Dispatching.EDF
is
subtype Deadline
is Ada.Real_Time.Time;
Default_Deadline :
constant Deadline :=
Ada.Real_Time.Time_Last;
procedure Set_Deadline (D :
in Deadline;
T :
in Ada.Task_Identification.Task_Id :=
Ada.Task_Identification.Current_Task);
procedure Delay_Until_And_Set_Deadline (
Delay_Until_Time :
in Ada.Real_Time.Time;
Deadline_Offset :
in Ada.Real_Time.Time_Span);
function Get_Deadline (T : Ada.Task_Identification.Task_Id :=
Ada.Task_Identification.Current_Task)
return Deadline;
end Ada.Dispatching.EDF;
{
AI05-0229-1}
For a task type (including the anonymous type of a
single_task_declaration)
or subprogram, the following language-defined representation aspect may
be specified:
Relative_Deadline
The aspect Relative_Deadline is an
expression,
which shall be of type Real_Time.Time_Span.
Aspect Description for Relative_Deadline:
Task parameter used in Earliest Deadline First Dispatching.
Legality Rules
{
AI05-0229-1}
The Relative_Deadline aspect shall not be specified on a task interface
type.
Post-Compilation Rules
{
AI95-00357-01}
If the EDF_Across_Priorities policy is specified for a partition, then
the Ceiling_Locking policy (see
D.3) shall
also be specified for the partition.
{
AI95-00357-01}
If the EDF_Across_Priorities policy appears in a Priority_Specific_Dispatching
pragma (see
D.2.2) in a partition, then the
Ceiling_Locking policy (see
D.3) shall also
be specified for the partition.
Reason: Unlike the other language-defined
dispatching policies, the semantic description of EDF_Across_Priorities
assumes Ceiling_Locking (and a ceiling priority) in order to make the
mapping between deadlines and priorities work. Thus, we require both
policies to be specified if EDF is used in the partition.
Dynamic Semantics
{
AI95-00357-01}
{
AI05-0229-1}
The Relative_Deadline aspect has no effect if it is specified for a subprogram
other than the main subprogram.
{
AI95-00357-01}
{
AI05-0229-1}
The initial absolute deadline of a task for which aspect Relative_Deadline
is specified is the value of Real_Time.Clock + the
expression
that is the value of the aspect, where this entire expression, including
the call of Real_Time.Clock, is evaluated between task creation and the
start of its activation. If the aspect Relative_Deadline is not specified,
then the initial absolute deadline of a task is the value of Default_Deadline.
The environment task is also given an initial deadline by this rule,
using the value of the Relative_Deadline aspect of the main subprogram
(if any).
Proof: The environment task is a normal
task by
10.2, so of course this rule applies
to it.
{
AI95-00357-01}
The procedure Set_Deadline changes the absolute deadline of the task
to D. The function Get_Deadline returns the absolute deadline of the
task.
{
AI95-00357-01}
The procedure Delay_Until_And_Set_Deadline delays the calling task until
time Delay_Until_Time. When the task becomes runnable again it will have
deadline Delay_Until_Time + Deadline_Offset.
{
AI95-00357-01}
On a system with a single processor, the setting of the deadline of a
task to the new value occurs immediately at the first point that is outside
the execution of a protected action. If the task is currently on a ready
queue it is removed and re-entered on to the ready queue determined by
the rules defined below.
{
AI95-00357-01}
When EDF_Across_Priorities is specified for priority range
Low..
High
all ready queues in this range are ordered by deadline. The task at the
head of a queue is the one with the earliest deadline.
{
AI95-00357-01}
A task dispatching point occurs for the currently running task
T
to which policy EDF_Across_Priorities applies:
when a change to the deadline of T occurs;
there is a task on the ready queue for the active
priority of T with a deadline earlier than the deadline of T;
or
there is a nonempty ready queue for that processor
with a higher priority than the active priority of the running task.
In these cases, the currently running task is said
to be preempted and is returned to the ready queue for its active priority.
{
AI95-00357-01}
For a task
T to which policy EDF_Across_Priorities applies, the
base priority is not a source of priority inheritance; the active priority
when first activated or while it is blocked is defined as the maximum
of the following:
the lowest priority in the range specified as EDF_Across_Priorities
that includes the base priority of T;
the priorities, if any, currently inherited by
T;
{
AI05-0055-1}
the highest priority
P, if any, less than the base priority of
T such that one or more tasks are executing within a protected
object with ceiling priority
P and task
T has an earlier
deadline than all such tasks; and furthermore
T has an earlier
deadline than all other tasks on ready queues with priorities in the
given EDF_Across_Priorities range that are strictly less than
P.
Ramification: The active priority of
T might be lower than its base priority.
{
AI95-00357-01}
When a task
T is first activated or becomes unblocked, it is added
to the ready queue corresponding to this active priority. Until it becomes
blocked again, the active priority of
T remains no less than this
value; it will exceed this value only while it is inheriting a higher
priority.
Discussion: These rules ensure that a
task executing in a protected object is preempted only by a task with
a shorter deadline and a higher base priority. This matches the traditional
preemption level description without the need to define a new kind of
protected object locking.
{
AI95-00357-01}
When the setting of the base priority of a ready task takes effect and
the new priority is in a range specified as EDF_Across_Priorities, the
task is added to the ready queue corresponding to its new active priority,
as determined above.
{
AI95-00357-01}
For all the operations defined in Dispatching.EDF, Tasking_Error is raised
if the task identified by T has terminated. Program_Error is raised if
the value of T is Null_Task_Id.
Bounded (Run-Time) Errors
{
AI95-00357-01}
If EDF_Across_Priorities is specified for priority
range
Low..
High, it is a bounded error to declare a protected
object with ceiling priority
Low or to assign the value
Low
to attribute 'Priority. In either case either Program_Error is raised
or the ceiling of the protected object is assigned the value
Low+1.
Erroneous Execution
{
AI95-00357-01}
If a value of Task_Id is passed as a parameter to
any of the subprograms of this package and the corresponding task object
no longer exists, the execution of the program is erroneous.
Documentation Requirements
{
AI95-00357-01}
On a multiprocessor, the implementation shall document any conditions
that cause the completion of the setting of the deadline of a task to
be delayed later than what is specified for a single processor.
Documentation Requirement: Any conditions
that cause the completion of the setting of the deadline of a task to
be delayed for a multiprocessor.
18 {
AI95-00357-01}
{
AI05-0264-1}
If two adjacent priority ranges,
A..
B and
B+1..
C
are specified to have policy EDF_Across_Priorities, then this is not
equivalent to this policy being specified for the single range,
A..
C.
19 {
AI95-00357-01}
The above rules implement the preemption-level protocol (also called
Stack Resource Policy protocol) for resource sharing under EDF dispatching.
The preemption-level for a task is denoted by its base priority. The
definition of a ceiling preemption-level for a protected object follows
the existing rules for ceiling locking.
Implementation Note: {
AI95-00357-01}
An implementation may support additional dispatching policies by replacing
absolute deadline with an alternative measure of urgency.
Extensions to Ada 95
{
AI95-00357-01}
Policy EDF_Across_Priorities and package Dispatching.EDF
are new.
Extensions to Ada 2005
{
AI05-0229-1}
Aspect Relative_Deadline is new;
pragma
Relative_Deadline is now obsolescent.
Wording Changes from Ada 2005
{
AI05-0055-1}
Correction: Corrected definition of active priority to avoid deadline
inversion in an unusual case.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
