Skip to main content

D.2 Priority Scheduling

danger

This Reference Manual output has not been verified, and may contain omissions or errors. Report any problems on the tracking issue

1/3

[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​

1.a/3
note
This introduction is simplified in order to reflect the rearrangement and expansion of this subclause.

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/2

The following language-defined library package exists:

1.2/5
package Ada.Dispatching 
  with  Preelaborate, Nonblocking, Global => in out synchronized is 
1.3/5
procedure Yield
   with Nonblocking => False;
1.4/3
Dispatching_Policy_Error : exception;
end Ada.Dispatching;
1.5/2

Dispatching serves as the parent of other language-defined library units concerned with task dispatching.

1.6/5

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):

1.7/5

Yield
The type of aspect Yield is Boolean.
1.a/5
note
Aspect Description for Yield: Ensures that a callable entity includes a task dispatching point.
1.8/5
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/5

If the Yield aspect is specified for a dispatching subprogram that inherits the aspect, the specified value shall be confirming.

1.11/5

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.

1.b/5
reason
The second sentence here is an assume-the-worst rule. The only Nonblocking attributes that are nonstatic are those that depend, directly or indirectly, on the nonblocking aspect of a generic formal parameter. We have to assume these might in fact have the value True if given an appropriate actual entity.
1.12/5

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/2

A 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.

3

It is implementation defined whether, on a multiprocessor, a task that is waiting for access to a protected object keeps its processor busy.

3.a
implementation defined
Whether, on a multiprocessor, a task that is waiting for access to a protected object keeps its processor busy.
4/5

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.

4.a
ramification
On multiprocessor systems, more than one task can be chosen, at the same time, for execution on more than one processor, as explained below.
5/2

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.

5.a
discussion
The core language defines a ready task as one that is not blocked. Here we refine this definition and talk about ready queues.
6/2

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.

6.a
discussion
There is always at least one task to run, if we count the idle task.
7/5

A call of Yield and a delay_statement are task dispatching points for all language-defined policies .

7.a/2
note
This paragraph was deleted.
8/5

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.

8.a/2
note
This paragraph was deleted.

Implementation Permissions​

9/2

An 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.

9.a/2
implementation defined
The effect of implementation-defined execution resources on task dispatching.
10

An implementation may place implementation-defined restrictions on tasks whose active priority is in the Interrupt_Priority range.

10.a/3
ramification
For example, on some operating systems, it might be necessary to disallow them altogether. This permission applies to tasks whose priority is set to interrupt level for any reason: via an aspect, via a call to Dynamic_Priorities.Set_Priority, or via priority inheritance.
10.1/5

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.

10.b/5
reason
This permission is intended to allow the implementation of Ada tasks in terms of target system threads, which may have additional conditions that cause task dispatching. For instance, for Linux threads, page faults are task dispatching points.
10.c/5
discussion
The Non_Preemptive_FIFO_Within_Priorities task dispatching policy (see D.2.4) does not allow additional task dispatching points.
11/3
note
NOTE 1 Clause 9 specifies under which circumstances a task becomes ready. The ready state is affected by the rules for task activation and termination, delay statements, and entry calls. When a task is not ready, it is said to be blocked.
12/5
note
NOTE 2 An example of a possible implementation-defined execution resource is a page of physical memory, which must be loaded with a particular page of virtual memory before a task can continue execution.
13
note
NOTE 3 The ready queues are purely conceptual; there is no requirement that such lists physically exist in an implementation.
14
note
NOTE 4 While a task is running, it is not on any ready queue. Any time the task that is running on a processor is added to a ready queue, a new running task is selected for that processor.
15
note
NOTE 5 In a multiprocessor system, a task can be on the ready queues of more than one processor. At the extreme, if several processors share the same set of ready tasks, the contents of their ready queues is identical, and so they can be viewed as sharing one ready queue, and can be implemented that way. [Thus, the dispatching model covers multiprocessors where dispatching is implemented using a single ready queue, as well as those with separate dispatching domains.]
16
note
NOTE 6 The priority of a task is determined by rules specified in this subclause, and under D.1, “Task Priorities”, D.3, “Priority Ceiling Locking”, and D.5, “Dynamic Priorities”.
17/2
note
NOTE 7 The setting of a task's base priority as a result of a call to Set_Priority does not always take effect immediately when Set_Priority is called. The effect of setting the task's base priority is deferred while the affected task performs a protected action.

Wording Changes from Ada 95​

17.a/3
note
This description is simplified to describe only the parts of the dispatching model common to all policies. In particular, rules about preemption are moved elsewhere. This makes it easier to add other policies (which might not involve preemption).

Incompatibilities With Ada 2005​

17.b/3
note
Procedure Yield is added to Dispatching. If Dispatching is referenced in a 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.
17.c/4
note
Package Dispatching was a Pure package, but now is Preelaborated with the addition of Yield. This is incompatible as Dispatching can no longer be depended upon from a Pure package. This should happen rarely in practice as the only contents was the exception Dispatching_Policy_Error and none of the child packages that could raise that exception are pure.

Inconsistencies With Ada 2012​

17.d/5
correction
Substantially reduced the Implementation Permission that used to allow “altering” task dispatching points to only allow adding task dispatching points. If an implementation was using this permission to remove task dispatching points, and a program depended on that behavior to work, it could fail when used with Ada 2022. We are not aware of any such implementations, and such behavior was never portable to other implementations, so we do not expect this to matter in practice.

Extensions to Ada 2012​

17.e/5
note
Aspect Yield is new.

Wording Changes from Ada 2012​

17.f/5
note
Redid the description of task dispatching to include the separate threads of control that can be started by a parallel construct.

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​

1

The form of a pragma Task_Dispatching_Policy is as follows:

2

pragma Task_Dispatching_Policy(policy_identifier);

2.1/2

The form of a pragma Priority_Specific_Dispatching is as follows:

2.2/2

pragma Priority_Specific_Dispatching (
policy_identifier, first_priority_expression, last_priority_expression);

Name Resolution Rules​

2.3/2

The expected type for first_priority_expression and last_priority_expression is Integer.

Legality Rules​

3/2

The policy_identifier used in a pragma Task_Dispatching_Policy shall be the name of a task dispatching policy.

3.a/2
note
This paragraph was deleted.
3.1/2

The policy_identifier used in a pragma Priority_Specific_Dispatching shall be the name of a task dispatching policy.

3.2/2

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/2

Pragma Task_Dispatching_Policy specifies the single task dispatching policy.

3.4/2

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.

3.b/2
reason
Each ready queue is managed by exactly one policy. Anything else would be chaos. The ready queue is determined by the active priority. However, how the active priority is calculated is determined by the policy; in order to break out of this circle, we have to say that the active priority is calculated by the method determined by the policy of the base priority.
3.5/3

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/2

A Task_Dispatching_Policy pragma is a configuration pragma. A Priority_Specific_Dispatching pragma is a configuration pragma.

4.1/2

The priority ranges specified in more than one Priority_Specific_Dispatching pragma within the same partition shall not be overlapping.

4.2/2

If a partition contains one or more Priority_Specific_Dispatching pragmas it shall not contain a Task_Dispatching_Policy pragma.

5/2

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.

6.1/2

If neither pragma applies to any of the program units comprising a partition, the task dispatching policy for that partition is unspecified.

6.2/3

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.

6.a/3
discussion
If we have priority specific dispatching then we want preemption across the entire range of priorities. That prevents higher priority tasks from being blocked by lower priority tasks that have a different policy. On the other hand, if we have a single policy for the entire partition, we want the characteristics of that policy to apply for preemption; specifically, we might not require any preemption. Note that policy Non_Preemptive_FIFO_Within_Priorities is not allowed in a priority specific dispatching pragma.
6.3/2

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.

6.b/2
ramification
Once subject to the new dispatching policy, it may be immediately preempted or dispatched, according the rules of the new policy.

Paragraphs 7 through 13 were moved to D.2.3.

Implementation Requirements​

13.1/2

An 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.

16.a/2
note
This paragraph was deleted.

Implementation Permissions​

17/5

Implementations are allowed to define other task dispatching policies, but are not required to support specifying more than one task dispatching policy per partition.

18/5

An implementation is not required to support pragma Priority_Specific_Dispatching if it is infeasible to support it in the target environment.

18.a/2
implementation defined
Implementation defined task dispatching policies.
note
Paragraphs 19 through 21 were deleted.

Extensions to Ada 95​

21.a/2
correction
Amendment It is no longer required to specify Ceiling_Locking with the language-defined task dispatching policies; we only require that implementations allow them to be used together.
21.b/3
note
Pragma Priority_Specific_Dispatching is new; it allows the specification of different policies for different priorities.

Wording Changes from Ada 95​

21.c/2
note
Clarified that an implementation need support only one task dispatching policy (of any kind, language-defined or otherwise) per partition.
21.d/3
note
This description is simplified to describe only the rules for the Task_Dispatching_Policy pragma that are common to all policies. In particular, rules about preemption are moved elsewhere. This makes it easier to add other policies (which might not involve preemption).

D.2.3 Preemptive Dispatching​

1/3

[This subclause defines a preemptive task dispatching policy.]

Static Semantics​

2/2

The policy_identifier FIFO_Within_Priorities is a task dispatching policy.

Dynamic Semantics​

3/2

When FIFO_Within_Priorities is in effect, modifications to the ready queues occur only as follows:

4/2
  • When a blocked task becomes ready, it is added at the tail of the ready queue for its active priority.
    • 5/2
  • 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.
    • 6/2
  • 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.
    • 7/2
  • 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.
7.a/2
ramification
If the delay does result in blocking, the task moves to the “delay queue”, not to the ready queue.
8/2

Each of the events specified above is a task dispatching point (see D.2.1).

9/2

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/2

An 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.

10.a/2
reason
This is the preferred combination of the FIFO_Within_Priorities policy with a locking policy, and we want that combination to be portable.

Documentation Requirements​

11/2

Priority 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:

12/2
  • The maximum priority inversion a user task can experience due to activity of the implementation (on behalf of lower priority tasks), and
12.a/2
note
Documentation Requirement: The maximum priority inversion a user task can experience from the implementation.
13/2
  • 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.
13.a/2
note
Documentation Requirement: The amount of time that a task can be preempted for processing on behalf of lower-priority tasks.
14/2
note
NOTE 1 If the active priority of a running task is lowered due to loss of inherited priority (as it is on completion of a protected operation) and there is a ready task of the same active priority that is not running, the running task continues to run (provided that there is no higher priority task).
15/2
note
NOTE 2 Setting the base priority of a ready task causes the task to move to the tail of the queue for its active priority, regardless of whether the active priority of the task actually changes.

Wording Changes from Ada 95​

15.a/2
note
This subclause is new; it mainly consists of text that was found in D.2.1 and D.2.2 in Ada 95. This was separated out so the definition of additional policies was easier.
15.b/2
note
We require that implementations allow this policy and Ceiling_Locking together.
15.c/2
note
We explicitly defined FIFO_Within_Priorities to be a task dispatching policy.

D.2.4 Non-Preemptive Dispatching​

1/3

[This subclause defines a non-preemptive task dispatching policy.]

Static Semantics​

2/2

The policy_identifier Non_Preemptive_FIFO_Within_Priorities is a task dispatching policy.

2.1/3

The following language-defined library package exists:

2.2/5
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;
2.3/3

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.

2.a/3
ramification
For language-defined policies other than Non_Preemptive_FIFO_Within_Priorities, a higher priority task should never be on a ready queue while a lower priority task is executed. Thus, for such policies, Yield_To_Higher does nothing.
2.b/3
note
Yield_To_Higher is not a potentially blocking operation; it can be used during a protected operation. That is allowed, as under the predefined Ceiling_Locking policy any task with a higher priority than the protected operation cannot call the operation (that would violate the locking policy). An implementation-defined locking policy may need to define the semantics of Yield_To_Higher differently.

Legality Rules​

3/2

Non_Preemptive_FIFO_Within_Priorities shall not be specified as the policy_identifier of pragma Priority_Specific_Dispatching (see D.2.2).

3.a/2
reason
The non-preemptive nature of this policy could cause the policies of higher priority tasks to malfunction, missing deadlines and having unlimited priority inversion. That would render the use of such policies impotent and misleading. As such, this policy only makes sense for a complete system.

Dynamic Semantics​

4/2

When Non_Preemptive_FIFO_Within_Priorities is in effect, modifications to the ready queues occur only as follows:

5/2
  • When a blocked task becomes ready, it is added at the tail of the ready queue for its active priority.
    • 6/2
  • 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.
    • 7/2
  • 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.
    • 8/2
  • 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.
8.a/2
ramification
If the delay does result in blocking, the task moves to the “delay queue”, not to the ready queue.
9/3

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).

9.a/3
ramification
A 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.
9.b/5
note
This rule supersedes the Implementation Permission of D.2.1; an implementation that adds additional task dispatching points to this policy is incorrect.

Implementation Requirements​

10/2

An 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.

10.a/2
reason
This is the preferred combination of the Non_Preemptive_FIFO_Within_Priorities policy with a locking policy, and we want that combination to be portable.

Implementation Permissions​

11/3

Since 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.

11.a.1/3
reason
We explicitly require that the ceiling priority be used in calls to Yield_to_Higher in order to prevent a risk of priority inversion and consequent loss of mutual exclusion when Yield_to_Higher is used in a protected object. This requirement might lessen the value of the permission (as the current Ceiling_Priority will have to be maintained in the TCB), but loss of mutual exclusion cannot be tolerated. The primary benefit of the permission (eliminating the need for preemption at the end of a protected action) is still available. As noted above, an implementation-defined locking policy will need to specify the semantics of Yield_to_Higher, including this case.

Extensions to Ada 95​

11.a/2
note
Policy Non_Preemptive_FIFO_Within_Priorities is new.

Extensions to Ada 2005​

11.b/3
note
Package Dispatching.Non_Preemptive is new.

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/2

The policy_identifier Round_Robin_Within_Priorities is a task dispatching policy.

3/2

The following language-defined library package exists:

4/5
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;
4.a.1/2
implementation defined
The value of Default_Quantum in Dispatching.Round_Robin.
5/2

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/2

The 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.

7/2

The function Actual_Quantum returns the actual quantum used by the implementation for the priority level Pri.

8/3

The function Is_Round_Robin returns True if priority Pri is covered by task dispatching policy Round_Robin_Within_Priorities; otherwise, it returns False.

9/2

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.

10/2

For Round_Robin_Within_Priorities, the dispatching rules for FIFO_Within_Priorities apply with the following additional rules:

11/2
  • 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.
    • 12/2
  • 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.
    • 13/2
  • 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).
13.a/2
ramification
Note that this happens even when the task is executing at a higher, inherited priority, and even if that higher priority is dispatched by a different policy than round robin.
14/2
  • 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.
14.a/2
ramification
In this case, it will be given a budget as described in the first bullet.
14.b/2
note
The rules for FIFO_Within_Priority (to which these bullets are added) say that a task that has its base priority set to a Round Robin priority is moved to the tail of the ready queue for its new priority level, and then will be given a budget as described in the first bullet. That happens whether or not the task's original base priority was a Round Robin priority.

Implementation Requirements​

15/2

An 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.

15.a/2
reason
This is the preferred combination of the Round_Robin_Within_Priorities policy with a locking policy, and we want that combination to be portable.

Documentation Requirements​

16/2

An implementation shall document the quantum values supported.

16.a.1/2
note
Documentation Requirement: The quantum values supported for round robin dispatching.
17/2

An implementation shall document the accuracy with which it detects the exhaustion of the budget of a task.

17.a.1/2
note
Documentation Requirement: The accuracy of the detection of the exhaustion of the budget of a task for round robin dispatching.
18/5
note
NOTE 1 Due to implementation constraints, the quantum value returned by Actual_Quantum can differ from that set with Set_Quantum.
19/2
note
NOTE 2 A task that executes continuously with an inherited priority will not be subject to round robin dispatching.

Extensions to Ada 95​

19.a/2
note
Policy Round_Robin_Within_Priorities and package Dispatching.Round_Robin are new.

D.2.6 Earliest Deadline First Dispatching​

1/5

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 affect how resources are allocated to the task.

2/5

[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.]

2.a/5
discussion
This paragraph was deleted.

Language Design Principles​

2.b/5
note
This paragraph was deleted.

Paragraphs 3 through 6 were moved to Annex J, “Obsolescent Features”.

Static Semantics​

7/5

The policy_identifier EDF_Within_Priorities is a task dispatching policy.

8/2

The following language-defined library package exists:

9/5
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;
9.1/5

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:

9.2/3

Relative_Deadline
The aspect Relative_Deadline is an expression, which shall be of type Real_Time.Time_Span.
9.a/5
note
Aspect Description for Relative_Deadline: Task or protected type parameter used in Earliest Deadline First Dispatching.
9.3/5

The form of pragma Generate_Deadlines is as follows:

9.4/5

pragma Generate_Deadlines;

9.5/5

The Generate_Deadlines pragma is a configuration pragma.

Legality Rules​

9.6/5

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​

10/5

If 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.

11/5

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.

11.a/5
reason
Unlike the other language-defined dispatching policies, the semantic description of EDF_Within_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

The Relative_Deadline aspect has no effect if it is specified for a subprogram other than the main subprogram.

12.1/5

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.

13/5

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).

13.a/2
proof
The environment task is a normal task by 10.2, so of course this rule applies to it.
13.1/5

The effect of specifying a Relative_Deadline aspect for a protected type or single_protected_declaration is discussed in D.3.

14/5

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.

14.1/5

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.

14.2/5

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).

15/5

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.

16/5

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.

17/5

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.

18/5

A task dispatching point occurs for the currently running task T to which policy EDF_Within_Priorities applies:

19/5
  • when a change to the base (absolute) deadline of T occurs;
    • 20/5
  • This paragraph was deleted.
    • 21/5
  • there is a nonempty ready queue for that processor with a higher priority than the active priority of the running task;
    • 21.1/5
  • there is a ready task with the same priority as T but with an earlier absolute deadline.
22/5

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.

23/5


24/5
26.a/5
ramification

27/5


27.a/5
discussion

28/5

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 .

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.

29.1/5

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.

29.2/5

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/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.

32.a.1/2
note
Documentation Requirement: Any conditions that cause the completion of the setting of the deadline of a task to be delayed for a multiprocessor.
33/5
note
NOTE If two distinct priorities are specified to have policy EDF_Within_Priorities , then tasks from the higher priority always run before tasks of the lower priority, regardless of deadlines .
34/5
note
This paragraph was deleted.
34.a/2
implementation note
An implementation may support additional dispatching policies by replacing absolute deadline with an alternative measure of urgency.

Extensions to Ada 95​

34.b/2
note
Policy EDF_Across_Priorities and package Dispatching.EDF are new.

Extensions to Ada 2005​

34.c/3
note
Aspect Relative_Deadline is new; pragma Relative_Deadline is now obsolescent.

Wording Changes from Ada 2005​

34.d/3
correction
Corrected definition of active priority to avoid deadline inversion in an unusual case.

Incompatibilities With Ada 2012​

34.e/5
note
The policy EDF_Across_Priorities was replaced by EDF_Within_Priorities. A program using EDF_Across_Priorities could fail to compile. However, we not are aware of any implementations of EDF_Across_Priorities, so it seems unlikely that any such programs exist outside of books and papers.