Version 1.4 of ais/ai-00355.txt

Unformatted version of ais/ai-00355.txt version 1.4
Other versions for file 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
!priority Medium
!difficulty Medium
!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 user-definable quantum.
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 be supported).
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).
Static Semantics
The following language-defined library package exists:
package Ada.Dispatching is pragma Pure(Ada); end Ada.Dispatching;
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.
Post-Compilation Rules
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 partition.
Static Semantics
The following language-defined library package exist:
with System; with Ada.Real_Time; package Ada.Dispatching.Round_Robin_Dispatching is Default_Quantum : constant Ada.Real_Time.Time_Span := <implementation-defined>; 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); function Actual_Quantum (Pri : System.Priority) return Ada.Real_Time.Time_Span; end Ada.Dispatching.Round_Robin_Dispatching;
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.
Dynamic Semantics
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 executable again.
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 budget.
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.
Documentation Requirement
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 Priority_Specific_Dispatching.
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
The expected type for first_priority_expression and last_priority_expression is integer.
Legality Rules
The policy_identifier shall be FIFO_Within_Priorities, Round_Robin_Within_Priorities, EDF_Across_Priorities or an implementation-defined identifier.
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 first_priority_expression.
Post-Compilation Rules
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.
Static Semantics
The following language-defined library package exist:
with System; package Ada.Dispatching.Priority_Specific_Dispatching is type Dispatching_Policy is (FIFO_Within_Priorities, Round_Robin_Within_Priorities, EDF_Across_Priorities, Other); function Policy(Pri : System.Any_Priority) return Dispatching_Policy; end Ada.Dispatching.Priority_Specific_Dispatching;
At all priority levels, the default Priority_Policy is FIFO_Within_Priorities.
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.
Dynamic Semantics
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 return Ada.Real_Time.Time_Span_Last.
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.
Notes 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 are equivalent.
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 locking?]
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.
!ACATS test
Tests should be created to check on the implementation of this feature.


Questions? Ask the ACAA Technical Agent