Version 1.1 of ais/ai-00355.txt

Unformatted version of ais/ai-00355.txt version 1.1
Other versions for file 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
!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_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 user-definable quantum.
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.
pragma Task_Dispatching_Policy(Priority_Specific);
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; function Nearest_Supported_Quantum (Pri : System.Priority) return Time_Span; Priority_Error : exception; end Ada.Real_Time.Execution_Time.Round_Robin_Dispatching;
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 Round_Robin_Within_Priority.
Use of pragma Priority_Policy implies the following static rules:
If the same priority is given in more than one pragma, the partition is rejected.
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