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/3
{
AI95-00357-01}
{
AI05-0229-1}
This clause defines a package for representing
the deadline of a task and a dispatching policy that defines Earliest
Deadline First (EDF) dispatching. An aspect A
pragma is defined to assign an initial
deadline to a task.2.a/3
Discussion: {
AI05-0229-1}
This aspect 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 aspect 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/3
4/3
pragma
Relative_Deadline (relative_deadline_expression);
Name Resolution Rules
5/3
Legality Rules
6/3
Static Semantics
7/2
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;
9.1/3
{
AI05-0229-1}
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.
9.a/3
Aspect Description
for Relative_Deadline: Task
parameter used in Earliest Deadline First Dispatching.
Legality Rules
9.3/3
{
AI05-0229-1}
The Relative_Deadline aspect shall not be specified
on a task interface type. 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/3
13/3
{
AI95-00357-01}
{
AI05-0229-1}
The initial absolute deadline of a task for
which aspect containing
pragma Relative_Deadline is specified is the value of Real_Time.Clock
+ the expression
that is the value of the aspect relative_deadline_expression,
where this entire expression, including
the call of Real_Time.Clock,
is evaluated is made between task creation and
the start of its activation. If the aspect there
is no Relative_Deadline is
not specified, 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,
using the value of the Relative_Deadline aspect of the main subprogram.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/3
{
AI05-0055-1}
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.
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}
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}
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.
33/3
21 {
AI95-00357-01}
{
AI05-0264-1}
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
22 {
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}
Policy EDF_Across_Priorities
and package Dispatching.EDF are new. Extensions to Ada 2005
34.c/3
{
AI05-0229-1}
Aspect Relative_Deadline is
new; pragma
Relative_Deadline is now obsolescent. Wording Changes from Ada 2005
34.d/3
{
AI05-0055-1}
Correction: Corrected definition of active
priority to avoid deadline inversion in an unusual case.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
