Version 1.3 of ais/ai-00355.txt

Unformatted version of ais/ai-00355.txt version 1.3
Other versions for file ais/ai-00355.txt

!standard D.03 (00)          03-11-24 AI95-00355/02
!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.
(See wording.)
Add two new sections:
D.2.5 The Priority Specific Dispatching Policy
A priority specific dispatching policy is defined via policy_identifier Priority_Specific. When Priority_Specific dispatching is in effect, tasks within the range of priorities specified are dispatched according to a single dispatching policy.
The form of a pragma Priority_Policy is as follows:
pragma Priority_Policy (priority_policy_identifier,
first_priority, last_priority {,policy_parameter});
Name Resolution Rules
The expected type for first_priority and last_priority is integer. The expected type for any policy_parameter is either integer or universal real.
Legality Rules
Priority_Specific can be specified as the policy_identifier of pragma Task_Dispatching_Policy (see D.2.2).
The priority_policy_identifier shall be FIFO_Within_Priorities, Round_Robin_Within_Priorities, EDF_Within_Priorities or an implementation-defined identifier.
Both first_priority and last_priority are static expressions; last_priority has a value greater or equal to first_priority. Any policy_parameter is a static expression.
For priority_policy_identifier FIFO_Within_Priorities there shall be no policy_parameter, and first_priority must equal last_priority.
For priority_policy_identifier Round_Robin_Within_Priorities there shall be at most one single policy_parameter, and first_priority must equal last_priority.
For priority_policy_identifier EDF_Within_Priorities there shall be no policy_parameter.
Post-Compilation Rules
A Priority_Policy pragma is a configuration pragma.
If the Priority_Specific policy is specified for a partition, then the Ceiling_Locking policy (see D.3) shall also be specified for the partition.
Static Semantics
If the same priority is specified in more than one Priority_Policy pragma, the partition is rejected.
If Task_Dispatching_Policy is not Priority_Specific for the partition in which a pragma Priority_Policy appears, then the partition is rejected.
If the values of first_priority and last_priority are not in the range of System.Any_Priority the partition is rejected.
At all priority levels, the default Priority_Policy is FIFO_Within_Priorities.
Dynamic Semantics
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_Priorities are as defined for that dispatching policy (D.2.3).
D.2.6 The Round Robin Dispatching Policy
This clause defines the priority_policy_identifier, Round_Robin_Within_Priorities, and package Round_Robin_Dispatching.
Static Semantics
The following language-defined library package exist:
with System; package Ada.Real_Time.Round_Robin_Dispatching is Default_Quantum : constant Time_Span := <implementation-defined>; function Round_Robin(Pri : System.Priority) return Boolean; function Actual_Quantum (Pri : System.Priority) return Time_Span; Priority_Error : exception; end Ada.Real_Time.Round_Robin_Dispatching;
For priority_policy_identifier Round_Robin_Within_Priorities the single policy_parameter (if present) gives the size of the required quantum in milliseconds. If no parameter is given, Default_Quantum is used.
Dynamic Semantics
The Round_Robin function returns True if the specified priority level has been allocated Round_Robin_Within_Priorities; otherwise it returns False.
The function Actual_Quantum returns the actual quantum used by the implementation for the priority level given; the exception Priority_Error is raised if this is not a round robin dispatching priority.
For Round_Robin_Within_Priorities, the same dispatching rules for FIFO_Within_Priorities apply with the following additional rules. A task is referred to as a RR task if its base priority is one designated as Round_Robin_Within_Priorities.
When a RR 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.
When a RR task is preempted (by a higher priority task), it is added to the head of the ready queue for its priority level. It retains its remaining budget.
When a RR task is executing, its budget is decreased by the amount of execution time it uses. The accuracy of this accounting follows the that for execution time clocks (D.14).
A task that has its base 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 RR task 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 the task is next 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 full quantum.
A non RR task executing with active priority at a level designated as round robin follows the rules for FIFO_Within_Priorities: if blocked it goes to the back of the associated ready queue; if preempted it goes to the front of the ready queue. It is not subject to the rules concerning the exhaustion of budget of RR tasks.
Documentation Requirement
An implementation shall document the range of quantum supported, or the distinct values supported. Also the maximum priority that can be given to Round_Robin_Within_Priorities.
An implementation shall document the accuracy with which it detects the exhaustion of a task's budget.
Imlementation Permissions
The implementation is allowed to reject a partition if it cannot support Round Robin dispatching for the priority requested.
Implementation Advice
An implementation will implement round robin dispatching using a quantum as close as possible to that given in the Priority_Policy pragma.
pragma Task_Dispatching_Policy (Priority_Specific); pragma Priority_Policy (Round_Robin_Within_Priorities, 10, 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 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 fifth 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 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