Version 1.5 of ais/ai-00355.txt

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

!standard D.03 (00)          04-08-12 AI95-00355/04
!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_priorities' 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 (as modified by AI-321) 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 are proposed (Round Robin in this AI and EDF in AI-357). In addition a means of specifying mixed scheduling is proposed in this AI.
This AI deals with modifying 2.2 and 2.3, and adding a new 2.5 (it assumes EDF is also to be supported, in 2.6).
In addition a new package is added to D.2.1 for parameters to dispatching policies.
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(Dispatching); exception Dispatching_Policy_Error; end Ada.Dispatching;
Dispatching serves as the parent of other language-defined library units concerned with dispatching.
Modify D.2.2 to the following:
D.2.2 Pragmas Task_Dispatching_Policy and Priority_Specific_Dispatching
This clause allows a single task dispatching policy to be defined for all priorities, or the range of priorities to be split into subranges that are assigned distinct dispatching policies.
The form of a pragma Task_Dispatching_Policy is as follows:
pragma Task_Dispatching_Policy(policy_identifier);
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 for use with pragma Task_Dispatching_Policy shall either be one defined in this Annex or an implementation-defined identifier.
The policy_identifier for use with pragma Priority_Specific_Dispatching 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 than or equal to first_priority_expression.
Post-Compilation Rules
A Task_Dispatching_Policy pragma is a configuration pragma. A Priority_Specific_Dispatching pragma is a configuration pragma.
The priority ranges specified in more than one Priority_Specific_Dispatching pragma within the same partition shall not be overlapping.
If a partition contains one or more Priority_Specific_Dispatching pragmas it shall not contain a Task_Dispatching_Policy pragma.
If a partition contains one or more Priority_Specific_Dispatching pragmas then the Ceiling_Locking policy (see D.3) shall also be specified for the partition.
Static Semantics
Tasks within the range of priorities specified in a Priority_Specific_Dispatching pragma are dispatched according to the specified dispatching policy.
If a partition contains one or more Priority_Specific_Dispatching pragmas the dispatching policy for priorities not covered by any Priority_Specific_Dispatching pragmas is FIFO_Within_Priorities.
Dynamic Semantics
A task dispatching policy specifies the details of task dispatching that are not covered by the basic task dispatching model. These rules govern when tasks are inserted into and deleted from the ready queues. A single task dispatching policy is specified by a Task_Dispatching_Policy pragma. Pragma Priority_Specific_Dispatching assigns distinct dispatching policies to ranges of System.Any_Priority.
If neither pragma appears in any of the program units comprising a partition, the task dispatching policy for that partition is unspecified.
If a partition contains one or more Priority_Specific_Dispatching pragmas 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 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.
Implementation Permissions
Implementations are allowed to define other task dispatching policies, but need not support more than one task dispatching policy per partition.
Add to D.2.3 The Standard Task Dispatching Policy
Static Semantics
The following language-defined policy_identifier exists: FIFO_Within_Priorities.
Add a new section:
D.2.5 Round Robin Dispatching
This clause defines the task dispatching policy Round_Robin_Within_Priorities and package Round_Robin_Dispatching.
Static Semantics
The following language-defined policy_identifier exists: Round_Robin_Within_Priorities.
The following language-defined library package exists:
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; function Is_Round_Robin (Pri : System.Priority) return Boolean; end Ada.Dispatching.Round_Robin_Dispatching;
When task dispatching policy Round_Robin_Within_Priorities is the single policy in effect for a partition, 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 priorities in the range Low..High in the second procedure. If no quantum is set for a Round Robin priority level, Default_Quantum is used.
The function Actual_Quantum returns the actual quantum used by the implementation for the priority level Pri.
The function Is_Round_Robin returns True if priority Pri is covered by task dispatching policy Round_Robin_Within_Priorities; otherwise it returns False.
A call of Actual_Quantum or either Set_Quantum with a priority that is not covered by policy Round_Robin_Within_Priorities raises exception Ada.Dispatching.Dispatching_Policy_Error.
For Round_Robin_Within_Priorities, the dispatching rules for FIFO_Within_Priorities apply with the following additional rules.
o When a 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 (see D.14).
o A task that has its base priority set, via the use of Set_Priority, to
a Round Robin 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 active 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.
To specify round robin dispatching for the lowest priority in a 32 priority system:
pragma Priority_Specific_Dispatching (FIFO_Within_Priorities, 2, 32); pragma Priority_Specific_Dispatching (Round_Robin_Within_Priorities, 1, 1);
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.

From: Alan Burns
Sent: Sunday, August 29, 2004  5:54 AM

As time is running out I would appreciate review of this AI
before the next meeting. I've made the changes requested by the
meeting and minutes, but there are still style issues I may
not have got right. D2.2 now defines two pragmas, and there is
some repetition in the wording - also it is not clear to
me exactly how to say X is a valid policy_identifier for
Task_Dispatching_Policy and/or Priority_Specific_Dispatching.

comments please


From: Robert Dewar
Sent: Sunday, August 29, 2004  12:49 PM

Just a general comment. I am a bit concerned by the phenomenon of
rushing new features into the next version of the language without
adequate review, prototyping experience etc.


From: Randy Brukardt
Sent: Monday, August 30, 2004  9:18 PM

For the record, in this particular case, it's mostly about finding the best
organization of the wording; the semantics haven't changed much in the last
couple of iterations.

But I certainly agree we have to beware of rushing stuff in. The good news
is that there aren't many work items that haven't stabilized, so we at least
can concentrate on those and either figure them out or drop them completely.


From: Randy Brukardt
Sent: Monday, August 30, 2004  9:28 PM

> also it is not clear to
> me exactly how to say X is a valid policy_identifier for
> Task_Dispatching_Policy and/or Priority_Specific_Dispatching.

I've had the same problem trying to word things. I don't think the standard has
properly handled this issue, and I think we ought to fix it so that it does.
That is, we should explicitly define that in D.2.2:

"pragma Task_Dispatching_Policy specifies the <i>task dispatching policy</i>;
the policy_identifier shall designate a task dispatching policy."

Similar wording is needed for Priority_Specific_Dispatching.

Then we can say something like

"The policy_identifier X designates a task dispatching policy."

(It would be nice if the locking policy was defined and specified the same way
- but we don't have the same need to do surgery on that section.)


From: Alan Burns
Sent: Thursday, September 2, 2004  5:16 AM

Should I revise the AI to follow the above?

There was some comments about this AI been rushed through and untried.
This comes from IRTAW meetings (more than one). There has been a paper
on this at Ada Europe and Michael H has an implementation of the round robin
feature on his MARTE Ada system. Much discussion by a wide group.


From: Randy Brukardt
Sent: Thursday, September 2, 2004  1:43 PM

I think so. No one else seems to have a strong enough opinion to write, so
I'd suggest going ahead.


Questions? Ask the ACAA Technical Agent