CVS difference for ais/ai-00321.txt

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

--- ais/ai-00321.txt	2003/01/24 04:14:27	1.2
+++ ais/ai-00321.txt	2003/02/01 04:40:34	1.3
@@ -1,4 +1,4 @@
-!standard D.02.01 (04)                                 03-01-07  AI95-00321/01
+!standard D.02.01 (04)                                 03-01-24  AI95-00321/02
 !standard D.02.01 (06)
 !standard D.02.01 (08)
 !standard D.02.02 (03)
@@ -13,62 +13,74 @@
 
 !summary
 
-New wording is proposed for paragraphs within D.2.1 and D.2.2 to remove a
-problem and to enable further dispatching policies to be added to Annex D.
+New wording is proposed for paragraphs within D.2.1 and D.2.2 to clarify the
+intended effect of dispatching points, and to allow more freedom to dispatching
+policies.
 
 !problem
 
 As it is currently worded the general model for dispatching (as defined in
-D.2.1) does not define the required behaviour.  Specifically the current
-running task is not considered as a candidate for the next running task as it
-is not on a ready queue.  Rewording of D.2.1 (6) is necessary. In addition,
-some of the specific rules necessary for defining the FIFO_Within_Priority
-policy in D.2.2 are, unnecessarily, given in Section D.2.1 where only the
-general dispatching policy should be defined.  This makes it difficult to
-specify other policies within the annex (for example, non-preemptive
-dispatching).
+D.2.1) does not permit a truly nonpreemptive dispatching policy. There are a
+number of required dispatching points that amount to preemption points, i.e.,
+points that do not logically correspond to a decision by the running task to
+give up the processor.
+
+During the discussion of this issue, it also appeared that the wording of D.2.1
+does not make it clear enough that whenever a running task reaches a
+dispatching point it is conceptually added to one or more of the conceptual
+dispatching queues, and so is always eligible for consideration to continue
+execution.
 
 !proposal
 
-Some wording changes are proposed for the annex.  Those deal with the problems
+Some wording changes are proposed for the annex.  Those deal with the problem
 defined above. Wording changes are also proposed to facilitate the definition
 of other dispatching policies in the Annex.
 
 !wording
 
-Remove 'the completion of an accept_statement (see 9.5.2),' from D.2.1(4).
+Replace the third and fourth sentences of D.2.1(4) by the following:
 
-Replace D.2.1(6) last sentence with:
-If the current running task has a priority greater or equal to the task at the
-head of the highest priority non-empty ready queue it continues to be the
-running task; otherwise the task at the head of the highest priority non-empty
-ready queue is selected, this task is then removed from all ready queues to
-which it belongs.
+  A task reaches a dispatching point whenever it becomes
+  blocked, and when the task terminates.
 
 Replace D.2.1(8) with:
-A task reaches a task dispatching point whenever the task dispatching policy
-requires a running task to go back to a ready queue.
 
+  Whenever a task reaches a task dispatching point
+  it goes back to a (possibly more than one) ready queue.
+
+Change the title of D.2.2 to "Task Dispatching Policies".
+
+
 Replace D.2.2(3) with:
-The policy-identifier shall be FIFO_Within_Priority, an alternative policy from
-D.14 or an implementation-defined identifier.
+
+  The policy-identifier shall be FIFO_Within_Priority, an alternative policy
+  from D.14 or an implementation-defined identifier.
 
 Replace D.2.2 (7):
-When FIFO_Within_Priorities is in effect, modifications to the ready queues
-occur only as follows.
+
+  When FIFO_Within_Priorities is in effect, modifications to the ready queues
+  occur only as follows:
 
 Add after D.2.2(13):
-A new running task is selected whenever there is a non-empty ready queue with a
-higher priority than the priority of the running task.  This is also a task
-dispatching point for this policy.
 
+  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.
+
 !discussion
 
-The inclusion of 'completion of an accept_statement (see 9.5.2),' in
-D.2.1(4) does not seem to be justified. It is not the only case in which
-a task changes priority and/or unblocks another task. It has not been
-moved to D.2.2 as the overriding rule of higher priority task always
-preempting covers this and all similar cases.
+The inclusion of 'completion of an accept_statement (see 9.5.2),' in D.2.1(4)
+was redundant for preemptive policies, and ruled out nonpreemptive policies. It
+is not the only case in which a task changes priority and/or unblocks another
+task. It has not been moved to D.2.2 as the overriding rule of higher priority
+task always preempting covers this and all similar cases.
+
+Likewise, the inclusion of whenever a task 'becomes ready' was redundant.
+Dispatching points are defined only for running tasks. Becoming ready requires
+insertion into one or more ready queues, which invokes the preemption rule
+D.2.2(13) if the policy is preemptive and the newly ready task has higher
+priority than a running task for a processor to which the queue belongs.
 
 !example
 
@@ -76,6 +88,9 @@
 
 !ACATS test
 
+Since this AI is rearranging the text of the standard, but not (intentionally)
+changing the semantics, no test is needed.
+
 !appendix
 
 From: Randy Brukardt
@@ -372,6 +387,211 @@
 intended, and a compiler that felt bound by this wording error would
 be just as incorrect as an original Ada 83 compiler that thought that
 all subtypes were non-static due to a wording error).
+
+****************************************************************
+
+From: Ted Baker
+Sent: Friday, January 24, 2003  7:35 AM
+
+
+Alan has been so good as to provide me with a copy of his proposed
+AI-321.  While I appreciate and endorse the idea of adding new
+dispatching policies to the standard, including nonpreemptive
+ones, I am not happy with this proposal.
+
+| As it is currently worded the general model for dispatching (as
+| defined in D.2.1) does not define the required behaviour.
+| Specifically the current running task is not considered as a
+| candidate for the next running task as it is not on a ready queue.
+
+The above certainly was not the intent when we wrote that section
+of the RM.  Looking now at the words, I think I see why you are
+having problems with them.  It comes from the effect of multiple
+authors and incremental changes, specifically the addition of
+task dispatching points without the corresponding specification
+of where the running task gets inserted into the ready queue at
+the dispatching point.
+
+The core model was derived from the POSIX real-time scheduling
+model, and intended to allow an implementation of that model to
+also comply with the Ada standard.  Therefore, in resolving the
+problem it may help to look at the POSIX standard The June 2001
+draft of the POSIX/ISO/Open Group ("Austin Group") combined
+standard (sorry, I don't have the final document on line) says:
+
+| "A conforming implementation shall select the thread that is
+| defined as being at the head of the highest priority non-empty
+| thread list to become a running process, regardless of its
+| associated policy.  This thread is then removed from its thread
+| list."
+
+Compare the Ada 94 RM words:
+
+| "Whenever a task running on a processor reaches a task
+| dispatching point, one task is selected to run on that
+| processor. The task selected is the one at the head of the
+| highest priority nonempty ready queue; this task is then removed
+| from all ready queues to which it belongs."
+
+The intent in both cases was that whenever a scheduling decision
+is made (a dispatching point), the currently executing thread
+(task) is first returned to one of the conceptual thread (task)
+lists (queues).  The scheduling (dispatching) policies determine
+when scheduling decisions are made, and the positions where
+threads (tasks) are inserted into the lists (queues).
+
+If you look at D.2.2 you will see that for each of the dispatching
+points there is a specification of where the running task is inserted
+into a dispatching queue.
+
+The right solution is to clarify the model, i.e., that every time
+the running task reaches a dispatching point, it is inserted into
+one (or more) ready queues before the dispatching decision is made.
+
+Beside the above issue, Alan's proposal wants to move some of the
+requirements for dispatching points, including the end of an
+accept statement, from the general requirements to specific
+policies.  Since we only have one named policy at this point,
+this should have no impact on existing practice.
+
+Therefore, I propose the following revision of the AI.  I have
+left in the movement of dispatching point specifications, since I
+see no immediate reason to object to them.  However, I hope we all
+think hard about whether these changes make sense from the point
+of view of a real-time application.
+
+--Ted Baker
+
+! summary
+
+New wording is proposed for paragraphs within D.2.1 and D.2.2 to
+clarify the intended effect of dispatching points, and to allow
+more freedom to dispatching policies.
+
+! problem
+
+As it is currently worded the general model for dispatching (as
+defined in D.2.1) does not permit a truly nonpreemptive dispatching
+policy.  There are a number of required dispatching points that
+amount to preemption points, i.e., points that do not logically
+correspond to a decision by the running task to give up the
+processor.
+
+During the discussion of this issue, it also appeared that the
+wording of D.2.1 does not make it clear enough that whenever a
+running task reaches a dispatching point it is conceptually added
+to one or more of the conceptual dispatching queues, and so is
+always eligible for consideration to continue execution.
+
+! proposal
+
+Some wording changes are proposed for the annex.  Those deal with
+the problem defined above. Wording changes are also proposed to
+facilitate the definition of other dispatching policies in the
+Annex.
+
+! wording
+
+Collapse the third and fourth sentences of D.2.1(4) by the
+following:
+
+  A task reaches a dispatching point whenever it becomes
+  blocked, and when the task terminates.
+
+Change the title of D.2.2 to "Task Dispatching Policies".
+
+Replace D.2.1(8) with:
+
+  Whenever a task reaches a task dispatching point
+  it goes back to a (possibly more than one) ready queue.
+
+Replace D.2.2(3) with:
+
+  The policy-identifier shall be
+  FIFO_Within_Priority, an alternative policy from D.14 or an
+  implementation-defined identifier.
+
+Replace D.2.2 (7):
+
+  When FIFO_Within_Priorities is in effect,
+  modifications to the ready queues occur only as follows:
+
+Add after D.2.2(13):
+
+  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.
+
+! discussion
+
+The inclusion of 'completion of an accept_statement (see 9.5.2),'
+in D.2.1(4) was redundant for preemptive policies, and ruled out
+nonpreemptive policies.  It is not the only case in which a task
+changes priority and/or unblocks another task. It has not been
+moved to D.2.2 as the overriding rule of higher priority task
+always preempting covers this and all similar cases.
+
+Likewise, the inclusion of whenever a task 'becomes ready'
+was redundant.  Dispatching points are defined only for
+running tasks.  Becoming ready requires insertion into one or more
+ready queues, which invokes the preemption rule D.2.2(13) if the
+policy is preemptive and the newly ready task has higher priority
+than a running task for a processor to which the queue belongs.
+
+| Ted,
+
+| I was about to email you to make ask you to make time
+| to look at this. Some background. During discussion at ARG
+| on dispatching policies, in particular, a new non-preemptive
+| one (but also others) it became clear (to ARG) that it was
+| not straightforward as some rules in D.2.1 (the general model)
+| were too specific and should really be in D.2.2 (the particular
+| dispatching policy). One example was requiring an immediate
+| switch to high pri process when it is released. I was charged
+| be ARG to do some moving between D.2.1 and D.2.2 to fix this.
+
+| But when doing so I notice, and others agreed, that D.2.1 does
+| not actually say what we all assumed it did. At a task dispatching
+| point the highest priority task on a ready queue is chosen to
+| run next, but the wording is clear that the current running task
+| is not on a ready queue (it had previously been removed, when it
+| is made runnable, and is only put back when another task is chosen
+| to execute). Hence logically current task must give up processor
+| even if it is the highest pri.
+
+| So AI-321 aims to fit both of the above problems, without breaking
+| the rest of the standard (I hope). Your observations would be
+| useful. Note IRTAW is talking about a few new dispatching policies,
+| including non-preemptive, round robin, EDF and combinations of
+| these - so some wording changes are just to allow more than one
+| policy to be defined in the standard.
+
+| cheers - here is the AI, the changes are really quite small
+
+[Editor's note: This was version /01 of the AI, not repeated here.]
+
+****************************************************************
+
+From: Alan Burns
+Sent: Tuesday, January 28, 2003  3:55 AM
+
+I am happy with Ted's alternative method of putting
+D.2.1 right.
+
+A couple of minor points
+
+1. The last sentence in D.2.1(7) is not quite
+accurate as it talks about a single ready queue.
+With Ted's words for D.2.1(8) which correctly
+notes that the task may go back to more than one
+queue, it may be best to delete this last sentence
+of D.2.1(7) as a definition of preemption is not
+really needed.
+
+2. I would not change the title of D.2.2,
+FIFO_Within_Priority will still be THE standard
+policy, others will be in a new D.14.
 
 ****************************************************************
 

Questions? Ask the ACAA Technical Agent