D.2.6 Earliest Deadline First Dispatching
{
AI95-00357-01}
{
AI12-0439-1}
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 can affect
how resources are allocated to the task.
{
AI95-00357-01}
{
AI05-0229-1}
{
AI05-0299-1}
{
AI12-0230-1}
[This subclause presents Dispatching.EDF, a package for representing
the deadline of a task and a dispatching policy that defines Earliest
Deadline First (EDF) dispatching. The Relative_Deadline aspect is provided
to assign an initial deadline to a task. A configuration pragma Generate_Deadlines
is provided to specify that a task's deadline is recomputed whenever
it is made ready.]
Language Design Principles
Static Semantics
{
AI95-00357-01}
The following language-defined library package exists:
{
AI12-0230-1}
{
AI12-0241-1}
{
AI12-0302-1}
with Ada.Real_Time;
with Ada.Task_Identification;
package Ada.Dispatching.EDF
with Nonblocking, Global =>
in out synchronized is
subtype Deadline
is Ada.Real_Time.Time;
subtype Relative_Deadline
is Ada.Real_Time.Time_Span;
Default_Deadline :
constant Deadline :=
Ada.Real_Time.Time_Last;
Default_Relative_Deadline :
constant Relative_Deadline :=
Ada.Real_Time.Time_Span_Last;
procedure Set_Deadline
(D :
in Deadline;
T :
in Ada.Task_Identification.Task_Id :=
Ada.Task_Identification.Current_Task);
function Get_Deadline
(T : Ada.Task_Identification.Task_Id :=
Ada.Task_Identification.Current_Task)
return Deadline;
procedure Set_Relative_Deadline
(D :
in Relative_Deadline;
T :
in Ada.Task_Identification.Task_Id :=
Ada.Task_Identification.Current_Task);
function Get_Relative_Deadline
(T : Ada.Task_Identification.Task_Id :=
Ada.Task_Identification.Current_Task)
return Relative_Deadline;
procedure Delay_Until_And_Set_Deadline
(Delay_Until_Time :
in Ada.Real_Time.Time;
Deadline_Offset :
in Ada.Real_Time.Time_Span)
with Nonblocking => False;
function Get_Last_Release_Time
(T : Ada.Task_Identification.Task_Id :=
Ada.Task_Identification.Current_Task)
return Ada.Real_Time.Time;
end Ada.Dispatching.EDF;
Relative_Deadline
The aspect Relative_Deadline is an
expression,
which shall be of type Real_Time.Time_Span.
Aspect Description for Relative_Deadline:
Task or protected type parameter used in Earliest Deadline First
Dispatching.
pragma Generate_Deadlines;
Legality Rules
{
AI05-0229-1}
{
AI12-0230-1}
The Relative_Deadline aspect shall not be specified on a task or protected
interface type. If the Relative_Deadline aspect is specified for a subprogram,
the
aspect_definition
shall be a static expression.
{
AI22-0121-1}
An internal call shall not occur within the expression
of a Relative_Deadline aspect of a protected type.Reason: Such a
call cannot be meaningful, since it would be evaluated during the creation
of the object (before it is elaborated).
Post-Compilation Rules
{
AI95-00357-01}
{
AI12-0230-1}
If the EDF_Within_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}
{
AI12-0230-1}
If the EDF_Within_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_Within_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.
{
AI12-0230-1}
If pragma Generate_Deadlines is in effect, the deadline of a task is
recomputed each time it becomes ready. The new deadline is the value
of Real_Time.Clock at the time the task is added to a ready queue plus
the value returned by Get_Relative_Deadline.
{
AI95-00357-01}
{
AI05-0229-1}
{
AI12-0230-1}
{
AI12-0128-1}
The initial absolute deadline for a task with a specified Relative_Deadline
is the result of adding the
results of evaluating
both a call to value returned by a call
of Real_Time.Clock
and to
the value of the
expression
specified as the Relative_Deadline aspect, where
both
evaluations (and the addition) are performed this
entire computation, including the call of Real_Time.Clock, is performed
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 (Ada.Real_Time.Time_Last).
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}
{
AI12-0230-1}
A task has both an
active
and a
base
absolute deadline. These are the same except when the task is inheriting
a relative deadline during activation or a rendezvous (see below) or
within a protected action (see
D.3). The procedure
Set_Deadline changes the (base) absolute deadline of the task to D. The
function Get_Deadline returns the (base) absolute deadline of the task.
{
AI12-0230-1}
The procedure Set_Relative_Deadline changes the relative deadline of
the task to D. The function Get_Relative_Deadline returns the relative
deadline of the task.
{
AI12-0230-1}
The function Get_Last_Release_Time returns the time, as provided by Real_Time.Clock,
when the task was last made ready (that is, was added to a ready queue).
{
AI95-00357-01}
{
AI12-0230-1}
The procedure Delay_Until_And_Set_Deadline delays the calling task until
time Delay_Until_Time. When the task becomes ready again it will have
deadline
Delay_Until_Time + Deadline_Offset.
{
AI95-00357-01}
{
AI12-0230-1}
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 onto the ready queue determined by
the rules defined below.
{
AI95-00357-01}
{
AI12-0230-1}
When EDF_Within_Priorities is specified for a priority, the ready queue
for that priority is ordered by deadline. The task at the head of a queue
is the one with the earliest deadline.
{
AI95-00357-01}
{
AI12-0230-1}
A task dispatching point occurs for the currently running task
T
to which policy EDF_Within_Priorities applies:
{
AI12-0230-1}
when a change to the base (absolute) deadline of
T occurs;
{
AI12-0230-1}
there is a nonempty ready queue for that processor with a higher priority
than the active priority of the running task;
{
AI12-0230-1}
there is a ready task with the same priority as
T but with an
earlier absolute deadline.
{
AI12-0230-1}
In these cases, the currently running task is said to be preempted and
is returned to the ready queue for its active priority, at a position
determined by its active (absolute) deadline.
Paragraphs 23 through
27 were deleted.
{
AI95-00357-01}
{
AI12-0230-1}
When the setting of the base priority of a ready task takes effect and
the new priority is specified as EDF_Within_Priorities, the task is added
to the ready queue, at a position determined by its active deadline.
{
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.
To be honest: {
AI22-0058-2}
One has to check whether T is Null_Task_Id before
checking whether T is terminated; this wording treats these are disjoint
conditions.
{
AI12-0230-1}
If two tasks with priority designated as EDF_Within_Priorities rendezvous
then the deadline for the execution of the accept statement is the earlier
of the deadlines of the two tasks.
{
AI12-0230-1}
During activation, a task being activated inherits the deadline that
its activator (see
9.2) had at the time the
activation was initiated.
Paragraph 30 was
deleted.
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.
NOTE {
AI95-00357-01}
{
AI05-0264-1}
{
AI12-0230-1}
If two distinct priorities are specified to have policy EDF_Within_Priorities,
then tasks from the higher priority always run before tasks of the lower
priority, regardless of deadlines.
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.
Incompatibilities With Ada 2012
{
AI12-0005-1}
{
AI12-0230-1}
The policy EDF_Across_Priorities was replaced by
EDF_Within_Priorities. A program using EDF_Across_Priorities could fail
to compile. However, we are not aware of any implementations of EDF_Across_Priorities,
so it seems unlikely that any such programs exist outside of books and
papers.
Wording Changes from Ada 2022
{
AI22-0121-1}
Corrigendum: Made internal calls illegal
in the expression
of the Relative_Deadline aspect. Such a call would be nonsense since
it would be made before the associated object is elaborated. This is
technically incompatible, but since it would only be changing a raise
of Program_Error into illegal code, it cannot occur in useful programs.{
AI22-0128-1}
Corrigendum: Clarified when the expression
of the Relative_Deadline aspect is evaluated. This was a wording problem
for which the intent seems obvious, so it would be surprising if this
change had any effect on an implementation nor any program.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
