Ada Reference ManualLegal Information
Contents   Index   References   Search   Previous   Next 

D.2.6 Earliest Deadline First Dispatching

1/2
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.
2/3
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.
Paragraphs 3 through 6 were moved to Annex J, “Obsolescent Features”. 

Static Semantics

7/2
The policy_identifier EDF_Across_Priorities is a task dispatching policy.
8/2
The following language-defined library package exists: 
9/2
with Ada.Real_Time;
with Ada.Task_Identification;
package Ada.Dispatching.EDF is
  subtype Deadline is Ada.Real_Time.Time;
  Default_Deadline : constant Deadline :=
              Ada.Real_Time.Time_Last;
  procedure Set_Deadline (D : in Deadline;
              T : in Ada.Task_Identification.Task_Id :=
              Ada.Task_Identification.Current_Task);
  procedure Delay_Until_And_Set_Deadline (
              Delay_Until_Time : in Ada.Real_Time.Time;
              Deadline_Offset : in Ada.Real_Time.Time_Span);
  function Get_Deadline (T : Ada.Task_Identification.Task_Id :=
              Ada.Task_Identification.Current_Task) return Deadline;
end Ada.Dispatching.EDF;
9.1/3
 For a task type (including the anonymous type of a single_task_declaration) or subprogram, the following language-defined representation aspect may be specified:
9.2/3
 Relative_Deadline

The aspect Relative_Deadline is an expression, which shall be of type Real_Time.Time_Span.

Legality Rules

9.3/3
 The Relative_Deadline aspect shall not be specified on a task interface type. 

Post-Compilation Rules

10/2
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.
11/2
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.

Dynamic Semantics

12/3
The Relative_Deadline aspect has no effect if it is specified for a subprogram other than the main subprogram.
13/3
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 (if any).
14/2
The procedure Set_Deadline changes the absolute deadline of the task to D. The function Get_Deadline returns the absolute deadline of the task.
15/2
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.
16/2
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.
17/2
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 deadline.
18/2
A task dispatching point occurs for the currently running task T to which policy EDF_Across_Priorities applies:
19/2
when a change to the deadline of T occurs;
20/2
there is a task on the ready queue for the active priority of T with a deadline earlier than the deadline of T; or
21/2
there is a nonempty ready queue for that processor with a higher priority than the active priority of the running task.
22/2
In these cases, the currently running task is said to be preempted and is returned to the ready queue for its active priority.
23/2
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:
24/2
the lowest priority in the range specified as EDF_Across_Priorities that includes the base priority of T;
25/2
the priorities, if any, currently inherited by T;
26/3
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 P
27/2
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.
28/2
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.
29/2
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

30/2
If EDF_Across_Priorities is specified for priority range Low..High, 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+1.

Erroneous Execution

31/2
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

32/2
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.
NOTES
33/3
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 range, A..C.
34/2
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.

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