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/2
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.
Syntax
3/2
The form of
a
pragma Relative_Deadline
is as follows:
4/2
pragma Relative_Deadline
(
relative_deadline_expression);
Name Resolution Rules
5/2
The expected type for
relative_deadline_expression
is Real_Time.Time_Span.
Legality Rules
6/2
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;
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/2
13/2
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.
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 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
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.
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.
33/2
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.