Ada Reference Manual (Ada 2022)

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 can affect how resources are allocated to the task.

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.

Paragraphs 3 through 6 were moved to Annex J, “Obsolescent Features”.

Static Semantics

The policy_identifier EDF_Within_Priorities is a task dispatching policy.

The following language-defined library package exists:

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;

For a subprogram, a task type (including the anonymous type of a single_task_declaration), or a protected type (including the anonymous type of a single_protected_declaration), 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.

The form of pragma Generate_Deadlines is as follows:

pragma Generate_Deadlines;

The Generate_Deadlines pragma is a configuration pragma.

Legality Rules

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

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.

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.

Dynamic Semantics

The Relative_Deadline aspect has no effect if it is specified for a subprogram other than the main subprogram.

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.

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).

The effect of specifying a Relative_Deadline aspect for a protected type or single_protected_declaration is discussed in D.3.

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.

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.

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).

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.

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.

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.

A task dispatching point occurs for the currently running task T to which policy EDF_Within_Priorities applies:

when a change to the base (absolute) deadline of T occurs;

This paragraph was deleted.

there is a nonempty ready queue for that processor with a higher priority than the active priority of the running task;

there is a ready task with the same priority as T but with an earlier absolute deadline.

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.

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.

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.

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.

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

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

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.

NOTE 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.

This paragraph was deleted.