Ada Reference Manual (Ada 2022 Draft 34)Legal Information
Contents   Index   References   Search   Previous   Next 

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 :=
  Default_Relative_Deadline : constant Relative_Deadline :=
  procedure Set_Deadline
     (D : in Deadline;
      T : in Ada.Task_Identification.Task_Id :=
  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 :=
  function Get_Relative_Deadline
     (T : Ada.Task_Identification.Task_Id :=
      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 :=
      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:

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.

Contents   Index   References   Search   Previous   Next 
Ada-Europe Ada 2005 and 2012 Editions sponsored in part by Ada-Europe