Version 1.1 of ais/ai-00355.txt
!standard D.03 (00) 03-09-27 AI95-00355/01
!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_Priority 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 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 to have a specific scheme defined (eg FIFO, Round_Robin, EDF, Value_Based,
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.
An extension is proposed for Annex D.
First a new policy-identifier is defined for task dispatching.
When Priority_Specific is used, the dispatching policy is defined on a per
priority level. This is achieved by the use of a new configuration pragma:
pragma Priority_Policy (Policy_Identifier, Priority
The Policy_Identifier shall be FIFO_Within_Priorities, Round_Robin_Within_
Priority or an implementation-defined identifier. For Policy_Identifier
FIFO_Within_Priority there shall be no Policy_Argument_Definition.
For Round_Robin_Within_Priority the Policy_Argument_Definition
shall be a single parameter, Round_Robin_Quantum, this must be a real
literal and represents the size of the required quantum in milliseconds.
For other policy identifiers, the semantics of
the Policy_Argument_Definition are implementation defined.
At all priority levels, the default Priority_Policy is
FIFO_Within_Priorities. The expected type of Priority is an integer
representing a value of System.Priority.
The locking policy associated with the Priority_Specific task
dispatching policy is Ceiling_Locking.
When task dispatching policy is Priority_Specific 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.
The rules for tasks on priority levels with FIFO_Within_Priority are
as defined for that dispatching policy
An implementation will implement round robin dispatching using a
quantum as close as possible to that given in the pragma.
An implementation that supports round robin Scheduling must provide the
following package which is a child of Execution_Time:
package Ada.Real_Time.Execution_Time.Round_Robin_Dispatching is
Default_Quantum : constant Time_Span := implementation-defined;
function Round_Robin(Pri : System.Priority) return Boolean;
(Pri : System.Priority) return Time_Span;
Priority_Error : exception;
The first function returns true if the specified priority level has
be allocated round robin dispatching.
The function Nearest_Supported_Quantum returns the actual quantum used
by the implementation for the priority level given; the exception is
raised if this is not a round robin dispatching priority.
An implmentation must document the range of quantum supported, or the
distinct values supported. Also the maximum priority that can be given to
Use of pragma Priority_Policy implies the following static rules:
If the same priority is given in more than one pragma, the partition is
If the Policy_Identifier is Round_Robin_Within_Priority and the value
of Priority is greater than the implementation can support then the
partition is rejected.
If the Policy_Identifier is Round_Robin_Within_Priority and no quantum is
given the default in Round_Robin_Dispatching applies.
If Task_Dispatching_Policy is not Priority_Specific for the
partition in which a pragma Priority_Policy appears, then the
partition is rejected.
The dynamic semantics for the new dispatching policy are as follows:
The dynamic semantics defined in D.2.2 for FIFO_Within_Priorities apply
to any priority level with Priority_Policy FIFO_Within_Priorities.
For Policy_Identifier Round_Robin_Within_Priority, the same rules
for FIFO_Within_Priority apply with the additional rules:
When a task is added to the tail of the ready queue for a priority level
with Priority_Policy Round_Robin_Within_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 executable again.
When a task is preempted (by a higher priority task), it is added to the
head of the ready queue for its priority level. If this is a round robin
priority level then it retains its remaining budget.
When a task with a base priority at a round robin priority level
is executing, its budget is decreased by the amount of execution time it uses.
The accurancy of this accounting follows the description provided for
execution time clocks.
A task that has its priority changed, via the use of Set_Priority, may
move to, or from, a round robin priority level.
If it is moved to a round robin level then it is placed at the tail of
the ready queue and given a full quantum.
When the implementation detects that a task with a round robin
priority has been executing for a time larger than or equal to its
round robin quantum, the task is said to have exhausted its budget.
When a running task exhausts its budget, it is moved to the tail of
the ready queue for that priority level. The semantics of this
move is equivalent to the task with priority Pri executing Set_Priority(Pri);
see D.5(15). Hence, for example, it will continue to execute within
a protected operation.
pragma Task_Dispatching_Policy (Priority_Specific);
pragma Priority_Policy (Round_Robin_Within_Priority, 10, 50.0);
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 rounf 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 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 behavior 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.
Questions? Ask the ACAA Technical Agent