D.2.6 Earliest Deadline First Dispatching
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.
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.
EDF_Across_Priorities is a task dispatching policy.
The following language-defined
library package exists:
Default_Deadline : constant
Set_Deadline (D : in
T : in
Delay_Until_Time : in
Deadline_Offset : in
Get_Deadline (T : Ada.Task_Identification.Task_Id :=
For a task type (including
the anonymous type of a single_task_declaration
or subprogram, the following language-defined representation aspect may
The aspect Relative_Deadline is an expression
which shall be of type Real_Time.Time_Span.
The Relative_Deadline aspect shall not be specified
on a task interface type.
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.
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.
The Relative_Deadline aspect has no effect if it
is specified for a subprogram other than the main subprogram.
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
The procedure Set_Deadline changes the absolute
deadline of the task to D. The function Get_Deadline returns the absolute
deadline of the task.
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.
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.
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
A task dispatching
point occurs for the currently running task T to which policy
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;
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.
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
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
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.
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.
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
If EDF_Across_Priorities is
specified for priority range Low
, 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
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.
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.
18 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
19 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.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe