D.2 Priority Scheduling
This Reference Manual output has not been verified, and may contain omissions or errors. Report any problems on the tracking issue
[This subclause describes the rules that determine which task is selected for execution when more than one task is ready (see 9).]
Wording Changes from Ada 95
D.2.1 The Task Dispatching Model
1/2[The task dispatching model specifies task scheduling, based on conceptual priority-ordered ready queues.]
Static Semantics
1.1/2The following language-defined library package exists:
package Ada.Dispatching
with Preelaborate, Nonblocking, Global => in out synchronized is
1.3/5procedure Yield
with Nonblocking => False;
1.4/3Dispatching_Policy_Error : exception;
end Ada.Dispatching;
1.5/2Dispatching serves as the parent of other language-defined library units concerned with task dispatching.
For a noninstance subprogram (including a generic formal subprogram), a generic subprogram, or an entry, the following language-defined aspect may be specified with an aspect_specification
(see 13.1.1):
Yield
- The type of aspect Yield is Boolean.
- If directly specified, the
aspect_definition
shall be a static expression. If not specified (including by inheritance), the aspect is False. 1.9/5 - If a Yield aspect is specified True for a primitive subprogram S of a type T, then the aspect is inherited by the corresponding primitive subprogram of each descendant of T.
Legality Rules
1.10/5If the Yield aspect is specified for a dispatching subprogram that inherits the aspect, the specified value shall be confirming.
If the Nonblocking aspect (see 9.5) of the associated callable entity is statically True, the Yield aspect shall not be specified as True. For a callable entity that is declared within a generic body, this rule is checked assuming that any nonstatic Nonblocking attributes in the expression of the Nonblocking aspect of the entity are statically True.
In addition to the places where Legality Rules normally apply (see 12.3), these rules also apply in the private part of an instance of a generic unit.
Dynamic Semantics
2/2A task can become a running task only if it is ready (see 9) and the execution resources required by that task are available. Processors are allocated to tasks based on each task's active priority.
It is implementation defined whether, on a multiprocessor, a task that is waiting for access to a protected object keeps its processor busy.
Task dispatching is the process by which a logical thread of control associated with a ready task is selected for execution on a processor. This selection is done during the execution of such a logical thread of control, at certain points called task dispatching points. Such a logical thread of control reaches a task dispatching point whenever it becomes blocked, and when its associated task terminates. [Other task dispatching points are defined throughout this Annex for specific policies.] Below we talk in terms of tasks, but in the context of a parallel construct, a single task can be represented by multiple logical threads of control, each of which can appear separately on a ready queue.
Task dispatching policies are specified in terms of conceptual ready queues and task states. A ready queue is an ordered list of ready tasks. The first position in a queue is called the head of the queue, and the last position is called the tail of the queue. A task is ready if it is in a ready queue, or if it is running. Each processor has one ready queue for each priority value. At any instant, each ready queue of a processor contains exactly the set of tasks of that priority that are ready for execution on that processor, but are not running on any processor; that is, those tasks that are ready, are not running on any processor, and can be executed using that processor and other available resources. A task can be on the ready queues of more than one processor.
Each processor also has one running task, which is the task currently being executed by that processor. Whenever a task running on a processor reaches a task dispatching point it goes back to one or more ready queues; a task (possibly the same task) is then selected to run on that processor. The task selected is the one at the head of the highest priority nonempty ready queue; this task is then removed from all ready queues to which it belongs.
A call of Yield and a delay_statement
are task dispatching points for all language-defined policies .
If the Yield aspect has the value True, then a call to procedure Yield is included within the body of the associated callable entity, and invoked immediately prior to returning from the body if and only if no other task dispatching points were encountered during the execution of the body.
Implementation Permissions
9/2An implementation is allowed to define additional resources as execution resources, and to define the corresponding allocation policies for them. Such resources may have an implementation-defined effect on task dispatching.
An implementation may place implementation-defined restrictions on tasks whose active priority is in the Interrupt_Priority range.
Unless otherwise specified for a task dispatching policy, an implementation may add additional points at which task dispatching may occur , in an implementation-defined manner.
Wording Changes from Ada 95
Incompatibilities With Ada 2005
use_clause
, and an entity E with a defining_identifier
of Yield is defined in a package that is also referenced in a use_clause
, the entity E may no longer be use-visible, resulting in errors. This should be rare and is easily fixed if it does occur.Inconsistencies With Ada 2012
Extensions to Ada 2012
Wording Changes from Ada 2012
D.2.2 Task Dispatching Pragmas
0.1/3[This subclause allows a single task dispatching policy to be defined for all priorities, or the range of priorities to be split into subranges that are assigned individual dispatching policies.]
Syntax
1The form of a pragma
Task_Dispatching_Policy is as follows:
pragma Task_Dispatching_Policy(policy_identifier
);
The form of a pragma
Priority_Specific_Dispatching is as follows:
pragma Priority_Specific_Dispatching (
policy_identifier
, first_priority_expression
, last_priority_expression
);
Name Resolution Rules
2.3/2The expected type for first_priority_expression
and last_priority_expression
is Integer.
Legality Rules
3/2The policy_identifier
used in a pragma
Task_Dispatching_Policy shall be the name of a task dispatching policy.
The policy_identifier
used in a pragma
Priority_Specific_Dispatching shall be the name of a task dispatching policy.
Both first_priority_expression
and last_priority_expression
shall be static expressions in the range of System.Any_Priority; last_priority_expression
shall have a value greater than or equal to first_priority_expression
.
Static Semantics
3.3/2Pragma
Task_Dispatching_Policy specifies the single task dispatching policy.
Pragma
Priority_Specific_Dispatching specifies the task dispatching policy for the specified range of priorities. Tasks with base priorities within the range of priorities specified in a Priority_Specific_Dispatching pragma have their active priorities determined according to the specified dispatching policy. Tasks with active priorities within the range of priorities specified in a Priority_Specific_Dispatching pragma are dispatched according to the specified dispatching policy.
If a partition contains one or more Priority_Specific_Dispatching pragmas, the dispatching policy for priorities not covered by any Priority_Specific_Dispatching pragmas is FIFO_Within_Priorities.
Post-Compilation Rules
4/2A Task_Dispatching_Policy pragma is a configuration pragma. A Priority_Specific_Dispatching pragma is a configuration pragma.
The priority ranges specified in more than one Priority_Specific_Dispatching pragma within the same partition shall not be overlapping.
If a partition contains one or more Priority_Specific_Dispatching pragmas it shall not contain a Task_Dispatching_Policy pragma.
This paragraph was deleted.
Dynamic Semantics
6/2[A task dispatching policy specifies the details of task dispatching that are not covered by the basic task dispatching model. These rules govern when tasks are inserted into and deleted from the ready queues.] A single task dispatching policy is specified by a Task_Dispatching_Policy pragma. Pragma Priority_Specific_Dispatching assigns distinct dispatching policies to subranges of System.Any_Priority.
If neither pragma
applies to any of the program units comprising a partition, the task dispatching policy for that partition is unspecified.
If a partition contains one or more Priority_Specific_Dispatching pragmas, a task dispatching point occurs for the currently running task of a processor whenever there is a nonempty ready queue for that processor with a higher priority than the priority of the running task.
A task that has its base priority changed may move from one dispatching policy to another. It is immediately subject to the new dispatching policy.
Paragraphs 7 through 13 were moved to D.2.3.
Implementation Requirements
13.1/2An implementation shall allow, for a single partition, both the locking policy (see D.3) to be specified as Ceiling_Locking and also one or more Priority_Specific_Dispatching pragmas to be given.
Documentation Requirements
Paragraphs 14 through 16 were moved to D.2.3.
Implementation Permissions
17/5Implementations are allowed to define other task dispatching policies, but are not required to support specifying more than one task dispatching policy per partition.
An implementation is not required to support pragma
Priority_Specific_Dispatching if it is infeasible to support it in the target environment.
Extensions to Ada 95
Wording Changes from Ada 95
D.2.3 Preemptive Dispatching
1/3[This subclause defines a preemptive task dispatching policy.]
Static Semantics
2/2The policy_identifier
FIFO_Within_Priorities is a task dispatching policy.
Dynamic Semantics
3/2When FIFO_Within_Priorities is in effect, modifications to the ready queues occur only as follows:
- When a blocked task becomes ready, it is added at the tail of the ready queue for its active priority.
- When the active priority of a ready task that is not running changes, or the setting of its base priority takes effect, the task is removed from the ready queue for its old active priority and is added at the tail of the ready queue for its new active priority, except in the case where the active priority is lowered due to the loss of inherited priority, in which case the task is added at the head of the ready queue for its new active priority.
- When the setting of the base priority of a running task takes effect, the task is added to the tail of the ready queue for its active priority.
- When a task executes a
delay_statement
that does not result in blocking, it is added to the tail of the ready queue for its active priority.
Each of the events specified above is a task dispatching point (see D.2.1).
A task dispatching point occurs for the currently running task of a processor whenever there is a nonempty ready queue for that processor with a higher priority than the priority of the running task. The currently running task is said to be preempted and it is added at the head of the ready queue for its active priority.
Implementation Requirements
10/2An implementation shall allow, for a single partition, both the task dispatching policy to be specified as FIFO_Within_Priorities and also the locking policy (see D.3) to be specified as Ceiling_Locking.
Documentation Requirements
11/2Priority inversion is the duration for which a task remains at the head of the highest priority nonempty ready queue while the processor executes a lower priority task. The implementation shall document:
- The maximum priority inversion a user task can experience due to activity of the implementation (on behalf of lower priority tasks), and
- whether execution of a task can be preempted by the implementation processing of delay expirations for lower priority tasks, and if so, for how long.
Wording Changes from Ada 95
D.2.4 Non-Preemptive Dispatching
1/3[This subclause defines a non-preemptive task dispatching policy.]
Static Semantics
2/2The policy_identifier
Non_Preemptive_FIFO_Within_Priorities is a task dispatching policy.
The following language-defined library package exists:
package Ada.Dispatching.Non_Preemptive
with Preelaborate, Nonblocking, Global => in out synchronized is
procedure Yield_To_Higher;
procedure Yield_To_Same_Or_Higher renames Yield;
end Ada.Dispatching.Non_Preemptive;
A call of Yield_To_Higher is a task dispatching point for this policy. If the task at the head of the highest priority ready queue has a higher active priority than the calling task, then the calling task is preempted.
Legality Rules
3/2Non_Preemptive_FIFO_Within_Priorities shall not be specified as the policy_identifier
of pragma
Priority_Specific_Dispatching (see D.2.2).
Dynamic Semantics
4/2When Non_Preemptive_FIFO_Within_Priorities is in effect, modifications to the ready queues occur only as follows:
- When a blocked task becomes ready, it is added at the tail of the ready queue for its active priority.
- When the active priority of a ready task that is not running changes, or the setting of its base priority takes effect, the task is removed from the ready queue for its old active priority and is added at the tail of the ready queue for its new active priority.
- When the setting of the base priority of a running task takes effect, the task is added to the tail of the ready queue for its active priority.
- When a task executes a
delay_statement
that does not result in blocking, it is added to the tail of the ready queue for its active priority.
For this policy, blocking or termination of a task, a delay_statement
, a call to Yield_To_Higher, and a call to Yield_To_Same_Or_Higher or Yield are the only task dispatching points (see D.2.1).
delay_statement
is always a task dispatching point even if it is not blocking. Similarly, a call to Yield_To_Higher is never blocking, but it is a task dispatching point In each of these cases, they can cause the current task to stop running (it is still ready). Otherwise, the running task continues to run until it is blocked.Implementation Requirements
10/2An implementation shall allow, for a single partition, both the task dispatching policy to be specified as Non_Preemptive_FIFO_Within_Priorities and also the locking policy (see D.3) to be specified as Ceiling_Locking.
Implementation Permissions
11/3Since implementations are allowed to round all ceiling priorities in subrange System.Priority to System.Priority'Last (see D.3), an implementation may allow a task of a partition using the Non_Premptive_FIFO_Within_Priorities policy to execute within a protected object without raising its active priority provided the associated protected unit does not contain any subprograms with aspects Interrupt_Handler or Attach_Handler specified, nor does the unit have aspect Interrupt_Priority specified. When the locking policy (see D.3) is Ceiling_Locking, an implementation taking advantage of this permission shall ensure that a call to Yield_to_Higher that occurs within a protected action uses the ceiling priority of the protected object (rather than the active priority of the task) when determining whether to preempt the task.
Extensions to Ada 95
Extensions to Ada 2005
D.2.5 Round Robin Dispatching
1/3[This subclause defines the task dispatching policy Round_Robin_Within_Priorities and the package Round_Robin.]
Static Semantics
2/2The policy_identifier
Round_Robin_Within_Priorities is a task dispatching policy.
The following language-defined library package exists:
with System;
with Ada.Real_Time;
package Ada.Dispatching.Round_Robin
with Nonblocking, Global => in out synchronized is
Default_Quantum : constant Ada.Real_Time.Time_Span :=
implementation-defined;
procedure Set_Quantum (Pri : in System.Priority;
Quantum : in Ada.Real_Time.Time_Span);
procedure Set_Quantum (Low, High : in System.Priority;
Quantum : in Ada.Real_Time.Time_Span);
function Actual_Quantum (Pri : System.Priority)
return Ada.Real_Time.Time_Span;
function Is_Round_Robin (Pri : System.Priority) return Boolean;
end Ada.Dispatching.Round_Robin;
When task dispatching policy Round_Robin_Within_Priorities is the single policy in effect for a partition, each task with priority in the range of System.Interrupt_Priority is dispatched according to policy FIFO_Within_Priorities.
Dynamic Semantics
6/2The procedures Set_Quantum set the required Quantum value for a single priority level Pri or a range of priority levels Low .. High. If no quantum is set for a Round Robin priority level, Default_Quantum is used.
The function Actual_Quantum returns the actual quantum used by the implementation for the priority level Pri.
The function Is_Round_Robin returns True if priority Pri is covered by task dispatching policy Round_Robin_Within_Priorities; otherwise, it returns False.
A call of Actual_Quantum or Set_Quantum raises exception Dispatching.Dispatching_Policy_Error if a predefined policy other than Round_Robin_Within_Priorities applies to the specified priority or any of the priorities in the specified range.
For Round_Robin_Within_Priorities, the dispatching rules for FIFO_Within_Priorities apply with the following additional rules:
- When a task is added or moved to the tail of the ready queue for its base priority, it has an execution time budget equal to the quantum for that priority level. This will also occur when a blocked task becomes executable again.
- When a task is preempted (by a higher priority task) and is added to the head of the ready queue for its priority level, it retains its remaining budget.
- While a task is executing, its budget is decreased by the amount of execution time it uses. The accuracy of this accounting is the same as that for execution time clocks (see D.14).
- When a task has exhausted its budget and is without an inherited priority (and is not executing within a protected operation), it is moved to the tail of the ready queue for its priority level. This is a task dispatching point.
Implementation Requirements
15/2An implementation shall allow, for a single partition, both the task dispatching policy to be specified as Round_Robin_Within_Priorities and also the locking policy (see D.3) to be specified as Ceiling_Locking.
Documentation Requirements
16/2An implementation shall document the quantum values supported.
An implementation shall document the accuracy with which it detects the exhaustion of the budget of a task.
Extensions to Ada 95
D.2.6 Earliest Deadline First Dispatching
1/5The 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 affect how resources are allocated to the task.
[This subclause presents Dispatching.EDF, 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 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.]
Language Design Principles
Paragraphs 3 through 6 were moved to Annex J, “Obsolescent Features”.
Static Semantics
7/5The policy_identifier
EDF_Within_Priorities is a task dispatching policy.
The following language-defined library package exists:
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;
end Ada.Dispatching.EDF;
For a subprogram, a task type (including the anonymous type of a single_task_declaration
), or a protected type (including the anonymous type of a single_protected_declaration
) , the following language-defined representation aspect may be specified:
Relative_Deadline
- The aspect Relative_Deadline is an
expression
, which shall be of type Real_Time.Time_Span.
The form of pragma
Generate_Deadlines is as follows:
pragma Generate_Deadlines;
The Generate_Deadlines pragma
is a configuration pragma.
Legality Rules
9.6/5The 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
10/5If the EDF_Within_Priorities policy is specified for a partition, then the Ceiling_Locking policy (see D.3) shall also be specified for the partition.
If the EDF_Within_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/3The Relative_Deadline aspect has no effect if it is specified for a subprogram other than the main subprogram.
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.
The initial absolute deadline for a task with a specified Relative_Deadline 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 aspect, where this entire computation , including the call of Real_Time.Clock, is performed 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).
The effect of specifying a Relative_Deadline aspect for a protected type or single_protected_declaration
is discussed in D.3.
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.
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.
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).
The procedure Delay_Until_And_Set_Deadline delays the calling task until time Delay_Until_Time. When the task becomes ready again it will have deadline Delay_Until_Time + Deadline_Offset.
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 the ready queue determined by the rules defined below.
When EDF_Within_Priorities is specified for a priority, the ready queue for that priority is ordered by deadline. The task at the head of a queue is the one with the earliest deadline.
A task dispatching point occurs for the currently running task T to which policy EDF_Within_Priorities applies:
- when a change to the base (absolute) deadline of T occurs;
- This paragraph was deleted.
- there is a nonempty ready queue for that processor with a higher priority than the active priority of the running task;
- there is a ready task with the same priority as T but with an earlier absolute deadline.
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.
When the setting of the base priority of a ready task takes effect and the new priority is specified as EDF_Within_Priorities , the task is added to the ready queue, at a position determined by its active deadline .
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.
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.
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
30/5
Paragraph 30 was deleted.
Erroneous Execution
31/2If 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/2On 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.