Version 1.4 of ais/ai-00355.txt
!standard D.03 (00) 04-02-19 AI95-00355/03
!class amendment 03-09-27
!status work item 03-09-27
!status received 03-09-27
!subject Priority Specific Dispatching including Round Robin
A means of specifying priority specific dispatching is proposed
so that FIFO is not the only 'within_priority' scheme supported.
A Round_Robin_Within_Priorities dispatching policy is defined.
Although Ada defines a number of mechanisms for specifying
scheduling policies, only one, FIFO_Within_Priorities is guaranteed
to be supported by all implementations of the Real-Time Systems Annex.
Many applications have a mixture of real-time and non
real-time activities. The natural way of scheduling non real-time activities
is by time sharing the processor using Round Robin Scheduling. Currently, the
only way of achieving this is by incorporating yield (eg delay 0.0) operations
in the code. This is ad hoc and intrusive.
This AI proposes a new scheduling policy which allows one or more priority
levels to be identified as round robin priorities. A task whose base priority
is set to one of these levels is scheduled in a round robin manner with a
The method proposed is a general one and will allow any priority
level/band to have a specific scheme defined (eg FIFO, Round_Robin, EDF,
etc). This not only extends the facilities of Ada but also provides
a well defined means of combining different dispatching schemes. A need
that is increasingly identified in OS provisions and application surveys.
Section D.2 (Priority Scheduling) currently has 4 subsections:
2.1 The Dispatching Model
2.2 Pragma Task_Dispatching_Policy
2.3 Preemptive Dispatching
2.4 Non-Preemptive Dispatching
Two new specific policies as proposed (Round Robin in this AI and EDF
in AI 357). In addition a means of specify mixed scheduling is proposed
in this AI. The ARG expressed the wish for the specific policies
to be defined in their own right and then the mixed scheme defined.
Hence the proposed new subsections are;
2.5 Round Robin Dispatching
2.6 Earliest Deadline First Dispatching
2.7 Priority Specific Dispatching
This AI deals with 2.5 and 2.7 (but will assume EDF is also to
In addition a new (empty) package is added to D.2.2 for parameters
to dispatching policies. Child packages are defined in 2.5, 2.6 and 2.7.
Add before Dynamic Semantics to D.2.1 (as updated by AI-321).
The following language-defined library package exists:
package Ada.Dispatching is
Dispatching serves as the parent of other language-defined library
units concerned with dispatching; its declaration is empty (except for
the pragma Pure).
Add a new section:
D.2.5 Round Robin Dispatching
This clause defines the policy_identifier, Round_Robin_Within_Priorities,
and package Round_Robin_Dispatching.
If the Round_Robin_Within_Priorities policy is specified for a partition,
then the Ceiling_Locking policy (see D.3) shall also be specified for the
The following language-defined library package exist:
package Ada.Dispatching.Round_Robin_Dispatching is
Default_Quantum : constant Ada.Real_Time.Time_Span :=
procedure Set_Quantum(Pri : System.Priority;
Quantum : Ada.Real_Time.Time_Span);
procedure Set_Quantum(Low,High : System.Priority;
Quantum : Ada.Real_Time.Time_Span);
(Pri : System.Priority) return Ada.Real_Time.Time_Span;
When task dispatching policy Round_Robin_Within_Priorities is in effect,
tasks with priority in the range of System.Interrupt_Priority are
dispatched according to policy FIFO_Within_Priorities.
A call of either Set_Quantum procedure sets the required quantum value
for the priority level Pri in the first procedure, and the levels in
the range Low..High for the second procedure. If no quantum is set for
a priority level, Default_Quantum is used.
The function Actual_Quantum returns the actual quantum used
by the implementation for the priority level Pri.
For Round_Robin_Within_Priorities, the dispatching rules
for FIFO_Within_Priorities apply with the following additional rules.
o When task is added to the tail of the ready queue for its base
priority, it has an execution time budget set equal to the quantum for
that priority level. This will also occur when a blocked task becomes
o 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
o When a task is executing, its budget is decreased by the amount of
execution time it uses. The accuracy of this accounting follows
that for execution time clocks (D.14).
o A task that has its base priority set, via the use of Set_Priority,
is moved to the tail of the ready queue and given a budget equal to the
quantum for the new priority level.
o When a task has an active priority higher than its base priority it is
given an infinite quantum at its action priority level; its base priority
budget is still decreased when it executes.
o 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 and is given a budget
equal to the quantum for its priority level. This is a task dispatching point.
An implementation shall document the range of quantum supported, or the
distinct values supported.
An implementation shall document the accuracy with which it detects the
exhaustion of a task's budget.
Due to implementation constraints, the quantum value returned by a call of
Actual_Quantum may not be identical to that set by a call of Set_Quantum.
A task that executes continuously with an inherited priority will not
be subject to round robin dispatching.
Add a new section:
D.2.7 Priority Specific Dispatching
This clause defines the policy_identifier, Priority_Specific,
the pragma Priority_Specific_Dispatching and package
The form of a pragma Priority_Specific_Dispatching is as follows:
pragma Priority_Specific_Dispatching (policy_identifier,
Name Resolution Rules
The expected type for first_priority_expression and
last_priority_expression is integer.
The policy_identifier shall be FIFO_Within_Priorities,
Round_Robin_Within_Priorities, EDF_Across_Priorities or an
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 or equal to
A Priority_Specific_Dispatching pragma is a configuration pragma.
If the Priority_Specific task dispatching policy is specified for a
partition, then the Ceiling_Locking policy (see D.3) shall also be
specified for the partition.
The priority ranges specified in more than one Priority_Specific_Dispatching
pragma within the same partition shall not be overlapping.
If pragma Priority_Specific_Dispatching appears in a partition then the
Task_Dispatching_Policy shall be Priority_Specific.
The following language-defined library package exist:
package Ada.Dispatching.Priority_Specific_Dispatching is
type Dispatching_Policy is (FIFO_Within_Priorities,
function Policy(Pri : System.Any_Priority) return Dispatching_Policy;
At all priority levels, the default Priority_Policy is
When Priority_Specific dispatching is in effect, tasks within the
range of priorities specified in a Priority_Specific_Dispatching pragma
are dispatched according to the specified dispatching policy.
When task dispatching policy Priority_Specific is in effect a
task dispatching point occurs for the currently running task of a
processor whenever there is a non-empty ready queue for that processor
with a higher priority than the priority of the running task.
A call of Policy returns the task dispatching policy in effect for
the specified priority, Pri; Other is returned if an implementation
defined policy is in effect.
A task that has its base priority changed, via the use of Set_Priority,
may move from one dispatching policy to another. It is immediately
dispatched according to the new policy.
A call of Ada.Dispatching.Round_Robin_Dispatching.Set_Quantum with a
priority Pri (or priority range Low..High) has no effect on priority
levels that are not covered by policy Round_Robin_Within_Priorities.
A call of Ada.Dispatching.Round_Robin_Dispatching.Actual_Quantum with
a priority Pri not covered by policy Round_Robin_Within_Priorities will
If task dispatching policy EDF_Across_Priorities is in effect for any
range of priorities then all tasks have deadline Default_Deadline (defined
in D.2.6) unless modified by pragma Relative_Deadline or calls of
Set_Deadline or Set_Relative_Deadline (see D.2.6).
If EDF_Across_Priorities is defined for any priority range Low..High then
the properties assigned to priority System.Any_Priority'first in the
definition of dispatching policy EDF_Across_Priorities are assigned to
priority Low for that range of priorities.
If two adjacent priority ranges, A..B and B+1..C are allocated policy
EDF_Across_Priorities then this is not equivalent to a single range, A..C.
For policies FIFO_Within_Priorities and Round_Robin_Within_Priorities they
pragma Task_Dispatching_Policy (Priority_Specific);
pragma Priority_Specific_Dispatching (Round_Robin_Within_Priorities, 10, 10);
[Open Issue: For Round Robin on its own is it necessary to have ceiling
For the Round Robin proposal: the rule concerning budget exhaustion
gives the important details of the proposal.
First it is the base priority of a task that is significant.
If a task's base priority is at a round robin level then it will
consume its budget whenever it is executing even when it has inherited
a higher priority (i.e. its active priority is greater than its base
priority). The final rule also deals with the key question of what happens
if the budget becomes exhausted while executing in a protected object. To
ensure mutual exclusion, without requiring a further lock, it is necessary to
allow the task to keep executing within the PO. It will consume more than its
quantum but the expected behaviour of the system is maintained. The usual
programming discipline of keeping the code within protected objects as short as
possible will ensure that quantum overrun is minimised. Further support for
these semantics comes from observing that execution within a PO is
abort-deferred. Quantum exhaustion is a less severe state than being
aborted; deferred behaviour thus seems appropriate.
The detailed motivation for this proposal is contained in a paper by Burns
et al at the 2003 Ada-Europe Conference. It is not repeated here for space
reasons. The title of the paper is A Round Robin Scheduling Policy for Ada.
The proposal is easily implemented on top of the POSIX provision for
Round Robin scheduling. Indeed it has been implemented in this way by
Michael Gonzalez Harbour. He reports no difficulty with the implementation.
Tests should be created to check on the implementation of this feature.
Questions? Ask the ACAA Technical Agent