D.2.6 Earliest Deadline First Dispatching
{
AI95-00357-01}
{
AI12-0439-1}
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 might
affect how resources are allocated to the task.
{
AI95-00357-01}
{
AI05-0229-1}
{
AI05-0299-1}
{
AI12-0230-1}
[This subclause
presents Dispatching.EDF, defines
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 An
aspect is defined 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. ]
This paragraph
was deleted.Discussion: {
AI05-0229-1}
{
AI12-0230-1}
This aspect 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 Priority is used to give an initial
priority to a task.
Language Design Principles
This paragraph
was deleted.{
AI95-00357-01}
{
AI05-0299-1}
{
AI12-0230-1}
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 subclause implement this scheme including the case where the newly
released task should execute before some existing tasks but not preempt
the currently executing task.
Static Semantics
{
AI95-00357-01}
The following language-defined library package exists:
{
AI12-0230-1}
{
AI12-0241-1}
{
AI12-0302-1}
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 :=
Ada.Real_Time.Time_Last;
Default_Relative_Deadline : constant Relative_Deadline :=
Ada.Real_Time.Time_Span_Last;
procedure Set_Deadline
(D :
in Deadline;
T :
in Ada.Task_Identification.Task_Id :=
Ada.Task_Identification.Current_Task);
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 :=
Ada.Task_Identification.Current_Task);
function Get_Relative_Deadline
(T : Ada.Task_Identification.Task_Id :=
Ada.Task_Identification.Current_Task)
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 :=
Ada.Task_Identification.Current_Task)
return Ada.Real_Time.Time;;
function Get_Deadline (T : Ada.Task_Identification.Task_Id :=
Ada.Task_Identification.Current_Task) return Deadline;
end Ada.Dispatching.EDF;
Relative_Deadline
The aspect Relative_Deadline is an
expression,
which shall be of type Real_Time.Time_Span.
Aspect Description
for Relative_Deadline: Task
or protected type parameter used in Earliest
Deadline First Dispatching.
pragma
Generate_Deadlines;
Legality Rules
{
AI05-0229-1}
{
AI12-0230-1}
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
{
AI95-00357-01}
{
AI12-0230-1}
If the
EDF_Within_Priorities EDF_Across_Priorities
policy is specified for a partition, then the Ceiling_Locking policy
(see
D.3) shall also be specified for the partition.
{
AI95-00357-01}
{
AI12-0230-1}
If the
EDF_Within_Priorities 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.
Reason: Unlike the other language-defined
dispatching policies, the semantic description of EDF_Within_Priorities 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
{
AI95-00357-01}
{
AI05-0229-1}
The Relative_Deadline aspect has no effect if it is specified for a subprogram
other than the main subprogram.
{
AI12-0230-1}
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.{
AI95-00357-01}
{
AI05-0229-1}
{
AI12-0230-1}
The initial absolute deadline
for of
a task
with a specified for
which aspect Relative_Deadline
is specified
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 that
is the value of the aspect, where this entire
computation expression,
including the call of Real_Time.Clock, is
performed 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
(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).
Proof: The environment task is a normal
task by
10.2, so of course this rule applies
to it.
{
AI95-00357-01}
{
AI12-0230-1}
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.
{
AI12-0230-1}
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. {
AI12-0230-1}
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).{
AI95-00357-01}
{
AI12-0230-1}
The procedure Delay_Until_And_Set_Deadline delays the calling task until
time Delay_Until_Time. When the task becomes
ready runnable
again it will have deadline
Delay_Until_Time + Deadline_Offset.
{
AI95-00357-01}
{
AI12-0230-1}
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 on
to the ready queue determined by the rules defined below.
{
AI95-00357-01}
{
AI12-0230-1}
When
EDF_Within_Priorities EDF_Across_Priorities
is specified for
a priority
,
the range Low..High all
ready
queue for that priority is queues
in this range are ordered by deadline. The task at the head of
a queue is the one with the earliest deadline.
{
AI95-00357-01}
{
AI12-0230-1}
A task dispatching point occurs for the currently running task
T
to which policy
EDF_Within_Priorities EDF_Across_Priorities
applies:
{
AI12-0230-1}
when a change to the
base (absolute) deadline
of
T occurs;
This paragraph
was deleted.{
AI12-0230-1}
there is a task on the ready queue for the active
priority of T with a deadline earlier than the deadline of T;
or
{
AI12-0230-1}
there is a nonempty ready queue for that processor with a higher priority
than the active priority of the running task
;.{
AI12-0230-1}
there is a ready task with the same priority as
T but with an earlier absolute deadline.{
AI12-0230-1}
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.
{
AI95-00357-01}
{
AI12-0230-1}
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:the lowest priority in the
range specified as EDF_Across_Priorities that includes the base priority
of T;
the priorities, if any, currently
inherited by T;
{
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. Ramification: The
active priority of T might be lower than its base priority.
{
AI95-00357-01}
{
AI12-0230-1}
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.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.
{
AI95-00357-01}
{
AI12-0230-1}
When the setting of the base priority of a ready task takes effect and
the new priority is
in a range specified
as
EDF_Within_Priorities EDF_Across_Priorities,
the task is added to the ready queue
, at a position
determined by its active deadline corresponding
to its new active priority, as determined above.
{
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.
{
AI12-0230-1}
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. {
AI12-0230-1}
During activation, a task being activated inherits
the deadline that its activator (see 9.2) had
at the time the activation was initiated.Bounded (Run-Time) Errors
{
AI95-00357-01}
{
AI12-0230-1}
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. Paragraph
30 was deleted.
Erroneous Execution
{
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
{
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.
Documentation Requirement: Any conditions
that cause the completion of the setting of the deadline of a task to
be delayed for a multiprocessor.
NOTE {
AI95-00357-01}
{
AI05-0264-1}
{
AI12-0230-1}
If two
distinct priorities adjacent
priority ranges, A..B and B+1..C are
specified to have policy
EDF_Within_Priorities EDF_Across_Priorities,
then
tasks from the higher priority always run
before tasks of the lower priority, regardless of deadlines this
is not equivalent to this policy being specified for the single range,
A..C.
This paragraph was
deleted.NOTE {
AI95-00357-01}
{
AI12-0230-1}
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.
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
{
AI95-00357-01}
Policy EDF_Across_Priorities and package Dispatching.EDF
are new.
Extensions to Ada 2005
{
AI05-0229-1}
Aspect Relative_Deadline is new;
pragma
Relative_Deadline is now obsolescent.
Wording Changes from Ada 2005
{
AI05-0055-1}
Correction: Corrected definition of active priority to avoid deadline
inversion in an unusual case.
Incompatibilities With Ada 2012
{
AI12-0005-1}
{
AI12-0230-1}
The policy EDF_Across_Priorities
was replaced by EDF_Within_Priorities. A program using EDF_Across_Priorities
could fail to compile. However, we are not aware of any implementations
of EDF_Across_Priorities, so it seems unlikely that any such programs
exist outside of books and papers.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
