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.
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}
The initial absolute deadline for a task with a specified Relative_Deadline
is the result of adding the value returned by a call of Real_Time.Clock
to the value of the
expression
specified as the Relative_Deadline aspect, where 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.
{
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.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
