Annotated Ada Reference ManualLegal Information
Contents   Index   References   Search   Previous   Next 

D.2.6 Earliest Deadline First Dispatching

1/2
{AI95-00357-01} 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/2
{AI95-00357-01} This clause defines a package for representing the deadline of a task and a dispatching policy that defines Earliest Deadline First (EDF) dispatching. A pragma is defined to assign an initial deadline to a task.
2.a/2
Discussion: This pragma is the only way of assigning an initial deadline to a task so that its activation can be controlled by EDF scheduling. This is similar to the way pragma Priority is used to give an initial priority to a task. 

Language Design Principles

2.b/2
{AI95-00357-01} To predict the behavior of a multi-tasking program it is necessary to control access to the processor which is preemptive, and shared objects which are usually non-preemptive and embodied in protected objects. Two common dispatching policies for the processor are fixed priority and EDF. The most effective control over shared objects is via preemption levels. With a pure priority scheme a single notion of priority is used for processor dispatching and preemption levels. With EDF and similar schemes priority is used for preemption levels (only), with another measure used for dispatching. T.P. Baker showed (Real-Time Systems, March 1991, vol. 3, num. 1, Stack-Based Scheduling of Realtime Processes) that for EDF a newly released task should only preempt the currently running task if it has an earlier deadline and a higher preemption level than any currently “locked” protected object. The rules of this clause implement this scheme including the case where the newly released task should execute before some existing tasks but not preempt the currently executing task. 

Syntax

3/2
{AI95-00357-01} The form of a pragma Relative_Deadline is as follows: 
4/2
  pragma Relative_Deadline (relative_deadline_expression);

Name Resolution Rules

5/2
{AI95-00357-01} The expected type for relative_deadline_expression is Real_Time.Time_Span.

Legality Rules

6/2
{AI95-00357-01} A Relative_Deadline pragma is allowed only immediately within a task_definition or the declarative_part of a subprogram_body. At most one such pragma shall appear within a given construct.

Static Semantics

7/2
{AI95-00357-01} The policy_identifier EDF_Across_Priorities is a task dispatching policy.
8/2
{AI95-00357-01} 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;

Post-Compilation Rules

10/2
{AI95-00357-01} 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
{AI95-00357-01} 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.
11.a/2
Reason: Unlike the other language-defined dispatching policies, the semantic description of EDF_Across_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

12/2
{AI95-00357-01} A Relative_Deadline pragma has no effect if it occurs in the declarative_part of the subprogram_body of a subprogram other than the main subprogram.
13/2
{AI95-00357-01} The initial absolute deadline of a task containing pragma Relative_Deadline is the value of Real_Time.Clock + relative_deadline_expression, where the call of Real_Time.Clock is made between task creation and the start of its activation. If there is no Relative_Deadline pragma 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.]
13.a/2
Proof: The environment task is a normal task by 10.2, so of course this rule applies to it. 
14/2
{AI95-00357-01} 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
{AI95-00357-01} 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
{AI95-00357-01} 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
{AI95-00357-01} 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
{AI95-00357-01} 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 non-empty 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
{AI95-00357-01} 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/2
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. 
26.a/2
Ramification: The active priority of T might be lower than its base priority. 
27/2
{AI95-00357-01} 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.
27.a/2
Discussion: These rules ensure that a task executing in a protected object is preempted only by a task with a shorter deadline and a higher base priority. This matches the traditional preemption level description without the need to define a new kind of protected object locking. 
28/2
{AI95-00357-01} 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
{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.

Bounded (Run-Time) Errors

30/2
{AI95-00357-01} {bounded error (cause) [partial]} 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
{AI95-00357-01} {erroneous execution (cause) [partial]} 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
{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. 
32.a.1/2
Documentation Requirement: Any conditions that cause the completion of the setting of the deadline of a task to be delayed for a multiprocessor.
NOTES
33/2
18  {AI95-00357-01} 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  {AI95-00357-01} 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.
34.a/2
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

34.b/2
{AI95-00357-01} {extensions to Ada 95} Policy EDF_Across_Priorities and package Dispatching.EDF are new. 

Contents   Index   References   Search   Previous   Next 
Ada-Europe Sponsored by Ada-Europe