CVS difference for ais/ai-00355.txt

Differences between 1.2 and version 1.3
Log of other versions for file ais/ai-00355.txt

--- ais/ai-00355.txt	2003/10/29 22:54:14	1.2
+++ ais/ai-00355.txt	2003/11/25 02:23:53	1.3
@@ -1,4 +1,4 @@
-!standard D.03 (00)                                  03-09-27  AI95-00355/01
+!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
@@ -10,19 +10,19 @@
 
 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.
+A Round_Robin_Within_Priorities dispatching policy is defined.
 
 
 !problem
 
 Although Ada defines a number of mechanisms for specifying
-scheduling policies, only one, FIFO_Within_Priorities} is guaranteed
+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
+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.
+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
@@ -30,149 +30,208 @@
 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,
+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.
 
 !proposal
 
-An extension is proposed for Annex D.
+(See wording.)
 
-First a new policy-identifier is defined for task dispatching.
+!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.
+
+Syntax
+
+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.
 
-pragma Task_Dispatching_Policy(Priority_Specific);
+For priority_policy_identifier EDF_Within_Priorities there shall
+be no policy_parameter.
 
-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:
+Post-Compilation Rules
 
-pragma Priority_Policy (Policy_Identifier, Priority
-                        {,Policy_Argument_Definition});
-
-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.
+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. The expected type of Priority is an integer
-representing a value of System.Priority.
+FIFO_Within_Priorities.
 
-The locking policy associated with the Priority_Specific task
-dispatching policy is Ceiling_Locking.
 
+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_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.
+The rules for tasks on priority levels with FIFO_Within_Priorities are
+as defined for that dispatching policy (D.2.3).
 
-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;
+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 Nearest_Supported_Quantum
+  function Actual_Quantum
            (Pri : System.Priority) return Time_Span;
   Priority_Error : exception;
-end Ada.Real_Time.Execution_Time.Round_Robin_Dispatching;
+end Ada.Real_Time.Round_Robin_Dispatching;
 
-The first function returns true if the specified priority level has
-be allocated 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.
 
-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.
+Documentation Requirement
 
-An implmentation must document the range of quantum supported, or the
+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_Priority.
+Round_Robin_Within_Priorities.
 
-Use of pragma Priority_Policy implies the following static rules:
+An implementation shall document the accuracy with which it detects the
+exhaustion of a task's budget.
 
-  If the same priority is given in more than one pragma, the partition is
-  rejected.
+Imlementation Permissions
 
-  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.
+The implementation is allowed to reject a partition if it cannot support
+Round Robin dispatching for the priority requested.
 
-!wording
+Implementation Advice
+
+An implementation will implement round robin dispatching using a
+quantum as close as possible to that given in the Priority_Policy
+pragma.
 
 
 !example
 
 pragma Task_Dispatching_Policy (Priority_Specific);
-pragma Priority_Policy (Round_Robin_Within_Priority, 10, 50.0);
+pragma Priority_Policy (Round_Robin_Within_Priorities, 10, 10, 50.0);
 
 !discussion
 
 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
+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
+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
+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
+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.
+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

Questions? Ask the ACAA Technical Agent