!standard D.02.05 (00) 04-11-11 AI95-00355/07 !standard D.02.01 (01) !standard D.02.02 (00) !standard D.02.02 (01) !standard D.04 (07) !class amendment 03-09-27 !status Amendment 200Y 04-09-27 !status WG9 approved 04-11-18 !status ARG Approved 9-0-0 04-09-17 !status work item 03-09-27 !status received 03-09-27 !priority Medium !difficulty Medium !subject Priority Specific Dispatching including Round Robin !summary A means of specifying priority specific dispatching is provided so that FIFO is not the only 'within_priorities' scheme supported. A Round_Robin_Within_Priorities dispatching policy is defined. !problem Although Ada defines a number of mechanisms for specifying task dispatching 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 (e.g. 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 (e.g. 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. This is a need that is increasingly identified in OS provisions and application surveys. !proposal Section D.2 (Priority Scheduling) currently (as modified by AI-321) has 4 subsections: D.2.1 The Dispatching Model D.2.2 Pragma Task_Dispatching_Policy D.2.3 Preemptive Dispatching D.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 D.2.2 and D.2.3, and adding a new D.2.5 (it assumes EDF is also to be supported, in D.2.6). In addition a new package is added to D.2.1 for parameters of dispatching policies. !wording Add before Dynamic Semantics in D.2.1 (as updated by AI-321). Static Semantics The following language-defined library package exists: package Ada.Dispatching is pragma Pure(Dispatching); Dispatching_Policy_Error : exception; 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 individual dispatching policies. Syntax 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 used in a pragma Task_Dispatching_Policy shall be the name of a task dispatching policy. The policy_identifier used in a pragma Priority_Specific_Dispatching shall be the name of a task dispatching policy. Both first_priority_expression and last_priority_expression shall be static expressions in the range of System.Any_Priority; the value of last_priority_expression shall be greater than or equal to that of first_priority_expression. Static Semantics Pragma Task_Dispatching_Policy specifies the task dispatching policy. Pragma Priority_Specific_Dispatching specifies the task dispatching policy for the specified range of priorities. 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. 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 that partition. 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 applies to 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 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. An implementation need not support pragma Priority_Specific_Dispatching if it is infeasible to support it in the target environment. Add to D.2.3 The Standard Task Dispatching Policy Static Semantics The policy_identifier FIFO_Within_Priorities is a task dispatching policy. Add to D.2.4 Non-Preemptive Dispatching - Legality Rules (see AI-298): Non_Preemptive_FIFO_Within_Priorities shall not be specified as the policy_identifier of pragma Priority_Specific_Dispatching (see D.2.2). Add a new section: D.2.5 Round Robin Dispatching This clause defines the task dispatching policy Round_Robin_Within_Priorities and the package Round_Robin. Static Semantics The policy_identifier Round_Robin_Within_Priorities is a task dispatching policy. The following language-defined library package exists: with System; with Ada.Real_Time; package Ada.Dispatching.Round_Robin is Default_Quantum : constant Ada.Real_Time.Time_Span := ; procedure Set_Quantum(Pri : in System.Priority; Quantum : in Ada.Real_Time.Time_Span); procedure Set_Quantum(Low,High : in System.Priority; Quantum : in 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; When task dispatching policy Round_Robin_Within_Priorities is the single policy in effect for a partition, each task with priority in the range of System.Interrupt_Priority is dispatched according to policy FIFO_Within_Priorities. Dynamic Semantics The procedures Set_Quantum set the required Quantum value for a single level Pri or a range of levels Low .. High. 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 Set_Quantum raises exception Ada.Dispatching.Dispatching_Policy_Error if a predefined policy other than Round_Robin_Within_Priorities applies to the specified priority. For Round_Robin_Within_Priorities, the dispatching rules for FIFO_Within_Priorities apply with the following additional rules: o When a task is added or moved to the tail of the ready queue for its base priority, it has an execution time budget 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 While a task is executing, its budget is decreased by the amount of execution time it uses. The accuracy of this accounting is the same as that for execution time clocks (see D.14). o A task that has its base priority set to a Round Robin priority is moved to the tail of the ready queue for its new priority level. AARM Note: It will be given a budget as described in the first bullet. 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. This is a task dispatching point. AARM Note: It will be given a budget as described in the first bullet. Documentation Requirements An implementation shall document the quantum values supported. An implementation shall document the accuracy with which it detects the exhaustion of the budget of a task. Notes Due to implementation constraints, the quantum value returned by Actual_Quantum might not be identical to the value set by Set_Quantum. However, if no value is set by Set_Quantum, then the value returned by Actual_Quantum will be identical to that of Default_Quantum. A task that executes continuously with an inherited priority will not be subject to round robin dispatching. In D.4(7), change "appears in" to "applies to". !example 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); !discussion 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 behavior 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 minimized. 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 given at the 2003 Ada-Europe Conference. It is not repeated here for space reasons. The paper is: A. Burns, M. Gonzalez Harbour, A. J. Welling (2003), "A Round Robin Scheduling Policy for Ada" in Reliable Software Technologies Ada-Europe 2003, LNCS 2655, Springer-Verlag. 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. This wording also fixes a wording glitch; pragmas Task_Dispatching_Policy and Queuing_Policy are configuration pragmas, and thus never appear inside of units; but the last sentence of D.2.2(6) and and D.4(7) implies that they do. The Corrigendum fixed this for D.3(6), but not the other two cases. !corrigendum D.2.1(01) @dinsa The task dispatching model specifies preemptive scheduling, based on conceptual priority-ordered ready queues. @dinss @i<@s8> The following language-defined library package exists: @xcode<@b Ada.Dispatching @b @b Pure(Dispatching); Dispatching_Policy_Error : @b; @b Ada.Dispatching;> Dispatching serves as the parent of other language-defined library units concerned with dispatching. !corrigendum D.02.02(00) @drepl The Standard Task Dispatching Policy @dby Pragmas Task_Dispatching_Policy and Priority_Specific_Dispatching !corrigendum D.02.02(01) @dinsb @i<@s8> The form of a @fa Task_Dispatching_Policy is as follows: @dinst 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 individual dispatching policies. !corrigendum D.2.2(02) @dinsa @fa<@b Task_Dispatching_Policy (@iidentifier);> @dinss The form of a @fa Priority_Specific_Dispatching is as follows: @fa<@b Priority_Specific_Dispatching (@iidentifier, @iexpression, @iexpression);> @i<@s8> The expected type for @i@fa and @i@fa is Integer. !corrigendum D.2.2(03) @drepl The @i_@fa shall either be FIFO_Within_Priorities or an implementation-defined @fa. @dby The @i_@fa used in a @fa Task_Dispatching_Policy shall be the name of a task dispatching policy. The @i_@fa policy_identifier used in a @fa Priority_Specific_Dispatching shall be the name of a task dispatching policy. Both @i@fa and @i@fa shall be static expressions in the range of System.Any_Priority; the value pf @i@fa shall be greater than or equal to @i@fa. @i<@s8> @fa Task_Dispatching_Policy specifies the task dispatching policy. @fa Priority_Specific_Dispatching specifies the task dispatching policy for the specified range of priorities. 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. !corrigendum D.2.2(04) @drepl A Task_Dispatching_Policy pragma is a configuration pragma. @dby 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 that partition. !corrigendum D.2.2(06) @drepl A @i 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, and whether a task is inserted at the head or the tail of the queue for its active priority. The task dispatching policy is specified by a Task_Dispatching_Policy configuration pragma. If no such pragma appears in any of the program units comprising a partition, the task dispatching policy for that partition is unspecified. @dby A @i 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 @fa applies to 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 may move from one dispatching policy to another. It is immediately dispatched according to the new policy. !corrigendum D.2.2(17) @drepl Implementations are allowed to define other task dispatching policies, but need not support more than one such policy per partition. @dby Implementations are allowed to define other task dispatching policies, but need not support more than one task dispatching policy per partition. An implementation need not support @fa Priority_Specific_Dispatching if it is infeasible to support it in the target environment. !corrigendum D.2.3(01) !comment This is a fake to trigger conflict processing. The real change is !comment in conflict text. @dinsc @i<@s8> The @i@fa FIFO_Within_Priorities is a task dispatching policy. !corrigendum D.2.4(01) !comment This is a fake to trigger conflict processing. The real change is !comment in conflict text. @dinsc Non_Preemptive_FIFO_Within_Priorities shall not be specified as the @i@fa of pragma Priority_Specific_Dispatching (see D.2.2). !corrigendum D.2.5(1) @dinsc This clause defines the task dispatching policy Round_Robin_Within_Priorities and the package Round_Robin. @i<@s8> The @i_@fa Round_Robin_Within_Priorities is a task dispatching policy. The following language-defined library package exists: @xcode<@b System; @b Ada.Real_Time; @b Ada.Dispatching.Round_Robin @b Default_Quantum : @b Ada.Real_Time.Time_Span := @ft<@i>; @b Set_Quantum (Pri : @b System.Priority; Quantum : @b Ada.Real_Time.Time_Span); @b Set_Quantum (Low, High : @b System.Priority; Quantum : @b Ada.Real_Time.Time_Span); @b Actual_Quantum (Pri : System.Priority) @b Ada.Real_Time.Time_Span; @b Is_Round_Robin (Pri : System.Priority) @b Boolean; @b Ada.Dispatching.Round_Robin;> When task dispatching policy Round_Robin_Within_Priorities is the single policy in effect for a partition, each task with priority in the range of System.Interrupt_Priority is dispatched according to policy FIFO_Within_Priorities. @i<@s8> The procedures Set_Quantum set the required Quantum value for a single level Pri or a range of levels Low .. High. 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 Set_Quantum raises exception Ada.Dispatching.Dispatching_Policy_Error if a predefined policy other than Round_Robin_Within_Priorities applies to the specified priority. For Round_Robin_Within_Priorities, the dispatching rules for FIFO_Within_Priorities apply with the following additional rules: @xbullet @xbullet @xbullet @xbullet @xbullet @i<@s8> An implementation shall document the quantum values supported. An implementation shall document the accuracy with which it detects the exhaustion of the budget of a task. @xindent<@s9> @xindent<@s9<18 A task that executes continuously with an inherited priority will not be subject to round robin dispatching.>> !corrigendum D.4(7) @drepl Two queuing policies, FIFO_Queuing and Priority_Queuing, are language defined. If no Queuing_Policy pragma appears in any of the program units comprising the partition, the queuing policy for that partition is FIFO_Queuing. The rules for this policy are specified in 9.5.3 and 9.7.1. @dby Two queuing policies, FIFO_Queuing and Priority_Queuing, are language defined. If no Queuing_Policy pragma applies to any of the program units comprising the partition, the queuing policy for that partition is FIFO_Queuing. The rules for this policy are specified in 9.5.3 and 9.7.1. !ACATS test Tests should be created to check on the implementation of this feature. !appendix 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 task dispatching policy; 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? PS 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. **************************************************************** From: Randy Brukardt Sent: Friday, September 24, 2004 7:28 PM AI-355 says: When task dispatching policy Round_Robin_Within_Priorities is the single policy in effect for a partition, each task with priority in the range of System.Interrupt_Priority are dispatched according to policy FIFO_Within_Priorities. Later, it says: A call of Actual_Quantum or Set_Quantum with a priority that is not covered by policy Round_Robin_Within_Priorities raises exception Ada.Dispatching.Dispatching_Policy_Error. What does "covered by policy" mean? In particular, if pragma Task_Dispatching_Policy (Round_Robin_within_Priorities); applies to a partition, what does Set_Quantum (System.Interrupt_Priority'Last, 0.01); do? Since the priority passed is dispatching according to FIFO_Within_Priority, perhaps Dispatching_Policy_Error is raised. Or maybe since the entire partition is a round-robin one, the call is allowed and the quantum as no effect. What's the intent? At the very least, we should have an AARM ramification note to explain this. **************************************************************** From: Tucker Taft Sent: Friday, September 24, 2004 8:59 PM > What does "covered by policy" mean? In particular, if > pragma Task_Dispatching_Policy (Round_Robin_within_Priorities); > applies to a partition, what does > Set_Quantum (System.Interrupt_Priority'Last, 0.01); > do? It seems clear this should raise an exception, since FIFO_Within_Priorities applies to this priority. So we should define "covered by policy" carefully to make sure this is true, or use a different term (e.g., "A call of Actual_Quantum or Set_Quantum raises exception Ada.Dispatching.Dispatching_Policy_Error if policy Round_Robin_Within_Priorities does not apply to the specified priority."). **************************************************************** From: Alan Burns Sent: Sunday, September 26, 2004 4:22 AM I fully agree with Tuck, exception should be raised ed and the wording proposed above is clear (and better!) **************************************************************** From: Robert I. Eachus Sent: Sunday, September 26, 2004 1:20 PM I like the new wording but... It seems to me that if we are too specific here it can hurt. An implementation should be able to provide "Sort_of_Round_Robin_within_Priorities." However the rule as stated means that this dispatching policy has to use different operations to set the quantum. Saying: "A call of Actual_Quantum or Set_Quantum raises exception Ada.Dispatching.Dispatching_Policy_Error if a predefined policy other than Round_Robin_Within_Priorities applies to the specified priority," is at least as clear for the predefined policies, and I don't think we should be stating what happens with implementation defined policies. **************************************************************** From: Robert A. Duff Sent: Sunday, September 26, 2004 6:01 PM I agree that imp-def policies should not be restricted in any way. ****************************************************************