CVS difference for ais/ai-00357.txt

Differences between 1.20 and version 1.21
Log of other versions for file ais/ai-00357.txt

--- ais/ai-00357.txt	2005/12/15 02:44:13	1.20
+++ ais/ai-00357.txt	2005/12/20 02:34:11	1.21
@@ -3131,3 +3131,3178 @@
 
 ****************************************************************
 
+From: Alan Burns
+Sent: Tuesday, May 10, 2005  3:25 AM
+
+>>EPD17: D.2.6 20/2 BIG BUG !?! This model does not work. Consider a
+>>task in a protected operation, having its ceiling as active priority; it
+>>calls a delay (stupid, but not forbidden); when it comes back, it can
+>>end up in the lowest ready queue rather than a ready queue for the
+>>ceiling priority it holds. Is this ok? I doubt it very much; it plays havoc
+>>with the ceiling model.
+>
+>>	NOT A BIG BUG - a task cannot call a delay within a protected op
+>>	ie it is forbidden (for all policies)!
+
+>No it isn't. 9.5.1 (17) It's a bounded error with one of 3 possible outcomes:
+>   - P_E raised
+>   - deadlock
+>   - nested protected action (which I read as "normal semantics")
+>   - (none other)
+>Havoc is not one of them  :-)
+>It would be more robust to specify the semantics that puts the task back on
+>the "right" queue.
+
+My reading of 9.5.1 (17) is that there are 2 possible behaviors
+1)  bounded error is detected and Program_Error is raised
+2) bounded error is not detected and the program continues; in this case a
+number of things may happen including the two noted but also (and more
+importantly and not noted) is that mutual exclusion can be broken. It is not
+defined if the delaying task holds the 'lock' on the PO - indeed it would not
+if the recommend implementation model of the real-time annex is followed (just
+use priority to get mutual exclusion).
+
+With EDF the situation is no different. If the bounded error is not detected
+the task executing the delay within the PO will allow other task in - when it
+next executes it will execute with the ceiling priority of the PO. This follows
+from the use of Ceiling_Locking which requires execution at ceiling level while
+in the PO. Nothing in the definition of EDF undermines this.
+
+So its not havoc (well it is but the same havoc as Ada 95)
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Tuesday, May 10, 2005  5:20 AM
+
+> My reading of 9.5.1 (17) is that there are 2 possible behaviors
+> 1)  bounded error is detected and Program_Error is raised
+> 2) bounded error is not detected and the program continues; in this case
+> a number of things may happen including the two noted but also (and more
+> importantly and not noted) is that mutual exclusion can be broken.
+
+Not so. The point of bounded error is that it is indeed bounded to the
+alternatives specified. So, mutual exclusion must not be broken. (What you
+are describing is erroneousness.) -- Aside: where you are going here, i.e.,
+ceiling locking, you need an enforced Restriction "no voluntary release
+of CPU" to make this a legal implementation.
+
+I haven't checked present semantics, but my presumption is that a delayed
+task, when resumed in Ada95, resumes at its active priority, i.e., is robust
+against the nested case. Why you would want to introduce a less robust model
+for EDF, I do not understand. Implementationwise, one is as easy/hard as the
+other. (Admittedly, wording-wise it is a bit harder - the EDF-tasks need to
+resume at their active preemption level rather than bottom priority --, but
+still doable.)
+
+****************************************************************
+
+From: Alan Burns
+Sent: Tuesday, May 10, 2005  7:37 AM
+
+Sorry, I strongly disagree. Yes the bounded error is bound, either the
+condition is recognized and program_error is raised or it is not recognized.
+End of story. It makes no sense to say condition is not recognized but the
+following actions must be taken - how can they be taken if the condition is not
+recognized!
+
+To require a lock to deliver correct behavior following a bounded error is
+completely against the point of the priority model. This is an issue for Ada
+95, not the new EDF facility. The wording in 9.5.1 (17) clearly does not cover
+all the cases listed in paragraphs above. Deadlock or nesting is only an issue
+if the blocking operation is a call on an entry. For delay statement no
+alternative is given.
+
+Looking at the words of 9.5.1 (17) it is clear that 'deadlock' is not an
+alternative - how can it be? You cannot force a program to deadlock - the
+paragraph is just noting what could happen if the second alternative (no
+action) is taken
+
+****************************************************************
+
+From: Bob Duff
+Sent: Tuesday, May 10, 2005  7:16 AM
+
+> Not so. The point of bounded error is that it is indeed bounded to the
+> alternatives specified.
+
+True.  But the other point is that bounded errors try to avoid causing
+difficulties for efficient implementation.  Is that the case here?
+
+This discussion illustrates one reason why I dislike bounded errors:
+they cause language designers to spend inordinate amounts of time
+worrying about the detailed semantics of wrong programs.  The concept
+"raise an exception" and the opposite concept "erroneous" are both much
+simpler.  Sigh.
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Tuesday, May 10, 2005  8:52 AM
+
+I agree with Alan that if the error is not detected,
+mutual exclusion can be broken, just as is true for
+Ada 95.  That is what we meant in Ada 95 by saying
+that one possible outcome is that a "nested protected
+action" might take place -- i.e. mutual exclusion might
+be broken.
+
+This will probably *not* directly lead to
+erroneous execution due to concurrent access, as described
+in 9.10(11), since we don't have two tasks simultaneously
+manipulating the data inside the protected object;
+one of them is blocked.  Of course it is clearly
+a programming error, but the whole point here is that
+we don't require that this particular error be detected
+by the implementation.
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Tuesday, May 10, 2005  12:43 PM
+
+I didn't/don't like bounded errors either. However, on this specific case,
+which includes the case of nested monitor calls, the language better not go
+for erroneousness or anything seemingly like it. Which is why I intend to
+stick to my guns on this discussion.
+
+Sometimes one does need nested monitor calls. (Not to be able to call
+IO out of protected ops is a bloody nuisance.) Soft real-time guys won't be
+deterred. If anything, this particular bounded error went overboard in my
+opinion.  It should not have been an error at all.
+
+True that hard real-time systems guys hate them and do so for good reason.
+But to make them completely ill-defined for all would be really bad. And is
+EDF only for hard real-time guys?  I sure hope not!
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Tuesday, May 10, 2005  2:44 PM
+
+I don't know what you mean by "stick to your guns" on this one.
+The Ada 95 rules clearly allow the mutual exclusion to be
+broken as one of the outcomes.  That is not erroneous, because
+it doesn't imply that you have concurrent access.  The "nested"
+protected action occurs while the original locker is blocked.
+Obviously not the programmer's intent, but not chaos either.
+If you want this error detected, then that's what Annex H
+provides.  I don't see any value in requiring that EDF detect
+blocking but FIFO_Within_Priorities not detect blocking.
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Wednesday, May 11, 2005  1:21 PM
+
+That't not my issue. Yes, mutual exclusion can be broken in the sense that
+you describe.  And I am not asking for any additional checking or suchlike
+in the EDF rules.
+
+My issue is that a nested protected call that does not access the same
+object or an object locked by some other task should work. Period. I guess
+we all agree that this is so by RM rules. They are not bounded errors.
+
+In my reading of the rules of D.2.6 (20-24), this case is treated
+incorrectly. Upon loss of active priority due to completion of a nested
+protected call, the task can end up on the wrong ready queue; it needs to go
+to the queue of its active priority (still due to the ongoing protected
+call).
+
+
+Moreover, I ask that a blocking call within a protected op (such as an
+entry call) is allowed to work correctly, as it will in many, many cases
+anyway, even though it is called a bounded error.
+
+Specifically I am asking that blocked tasks are resumed at their active
+preemption level aka active priority, not at the EDF base queue priority. My
+rationale is that resumption at the active priority level preserves most of
+the guarantees that ceiling priorities give you, while resumption at the
+base priority "creates havoc" with all the ceiling protocol
+guarantees. (Note that I am asking for the same thing in all cases, i.e.,
+always enqueue in the queue of the active priority.)
+
+Alan's argument is that this case should never arise where the active
+priority is unequal to base priority upon resumption, as all situations
+in which this could be the case, are classified as a bounded error and
+hence it is o.k. to say "base priority".
+
+I am replying that most of these cases of bounded error are perfectly fine,
+practically speaking (assuming a locking implementation), and the rules
+should not be written so that these cases are certain to be damaged. D.2.6
+(24/2) is a punitive rule that intentionally screws up ceiling protocols
+in the presence of nested blocking operations for no good reason.
+
+Conceivably one can argue that, if the implementation choses to not use
+locks (legitimate only on uni-processors) and hence can cause mutual
+exclusion to be truly violated (and not just in the sense of Tuck's
+message), the punitive rule ought to discourage all users from issuing
+nested blocking calls. I don't believe in such sophistry. The implementation
+behaviour would not be sanctioned by 9.5.1 (17) anyway, because it would not
+be a nested protected action on the same object, but rather two completely
+independent protected actions, i.e., a true screw-up.
+
+You want this efficient but risky implementation, you figure out some other
+way, e.g., an implementation permission.
+
+
+I don't think that anybody can argue that queuing into the active priority
+queue rather than the base priority queue can create any kind of
+implementation burden. Note that the active priority re-enqueing must
+be available anyhow upon completion of a nested protected op that is not a
+bounded error, e.g., a nested call on some protected procedure of another
+object.
+
+----
+
+Aside: 9.5.1(17) actually has a bug. It does not allow for "it just works
+normally" semantics as one of the bounded error alternatives (i.e., the case
+where it simply works to call a blocking entry from within a protected
+op). But that interpretation is outlandish, since it would force
+implementations into doing work to screw things up intentionally, so that I
+read the "might" as also including the canonical semantics of the blocking
+operation.
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Wednesday, May 11, 2005  3:58 PM
+
+
+P.S. In order to make discussion/understanding easier, here is a sample
+program to illustrate my point(s) about the EDF scheduling problem:
+
+(imagine the right pragmas inserted to make EDF happen over
+prio range 1..5)
+
+with Ada.Text_IO;
+procedure Edftest is
+
+   task T1 is  pragma Priority(1);   end T1;
+
+   task T2 is  pragma Priority(2);   end T2;
+
+   protected O1 is
+      pragma Priority(4);
+      procedure Change;
+      entry Block;
+   private
+      Proceed: Boolean := True;
+   end O1;
+
+   protected O2 is
+      pragma Priority(3);
+      procedure Driver;
+   end O2;
+
+   protected body O1 is
+    procedure Change is
+    begin
+      Proceed := not Proceed; -- at active priority 4
+    end Change;
+
+    entry Block when Proceed is begin null; end Block;
+   end O1;
+
+   protected body O2 is
+     procedure Driver is
+     begin
+      O1.Change; -- perfectly o.k.
+      -- should run here at (active) priority 3
+      -- per D-11 rule, is in the EDF priority 1 ready queue !
+
+      Ada.Text_Io.Put_Line("1");  -- this better be the very first output
+
+      O1.Block;  -- bounded error since a blocking call
+      -- none of the specified behaviours other than P-E make any sense.
+      -- expect normal operation ... P_E would be o.k, too
+
+      -- should run here at (active) priority 3
+      -- per D-11 rule, is in the EDF priority 1 ready queue !
+
+      Ada.Text_Io.Put_Line("3");  -- must be the 3. output
+     end Driver;
+   end O2;
+
+   task body T1 is
+   begin
+      Ada.Text_Io.Put_Line("2"); -- must be the 2. output
+      O1.Change;
+   end T1;
+
+   task body T2 is
+   begin
+      O2.Driver;
+      Ada.Text_Io.Put_Line("4"); -- must be the last output
+   end;
+
+begin  -- T1 runs until blocked; then T2, which unblocks T1
+null;
+end Edftest;
+
+****************************************************************
+
+From: Alan Burns
+Sent: Thursday, May 12, 2005  5:31 AM
+
+Erhard made a number of points in his email and I want to make
+some general points/replies in a moment - but his example highlights a
+misunderstanding, either the current wording is wrong, or Erhard's
+reading of the words, or both!
+
+I'll edit his example down to the first key bit
+
+>   protected body O2 is
+>     procedure Driver is
+>     begin
+>      O1.Change; -- perfectly o.k.
+>      -- should run here at (active) priority 3
+>      -- per D-11 rule, is in the EDF priority 1 ready queue !
+
+NO.  This task must run at priority 3 (as you require).
+I am using the fact that the task is in a PO and Ceiling_Locking applies
+to give me the rule that any task within a PO runs at ceiling level.
+
+So it sounds like we agree on the required behavior - but must make sure
+the words say that.
+
+>      Ada.Text_Io.Put_Line("1");  -- this better be the very first output
+
+you don't mean this do you?
+this is the second output - the first comes from the task before it
+calls any PO
+
+...
+>   task body T1 is
+>   begin
+>      Ada.Text_Io.Put_Line("2"); -- must be the 2. output
+
+As above - this is first output - its the first thing the program does
+
+...
+
+To return to the general issues 9.5.1(17) (ie not EDF specific).
+
+First the term 'nested protected actions' is a little confusing. 'Nested
+monitor calls' is a well used phrase in concurrency and concernes a task in one
+monitor calling another monitor (should it keep the first lock was the original
+question asked in these situations). But in 9.5.1(17) nesting here means
+concurrent execution within the same PO.
+
+I feel Ada 95 made exactly the right decision(s) for controling access  to POs:
+
+1. It does not require an actual lock, nor preclude one.
+2. It thus allows for an efficient implementation on a single
+processor (using priority itself to give mutual exclusion).
+3. In the non-lock case there is a potential to break mutual excision
+if a task blocks within a PO.
+4. But a programmer can accept this when he/she knows that no actual
+state (within the PO) is compromised (as in Erhard's example).
+5. So 3 cases exist
+    a) no lock, and we want to ensure no blocking, here raising P_E is the
+right thing to do (as required in Ravenscar)
+    b) no lock but allow blocking and its up to programmer to get it right, so
+no exception raised and the program continues its execution
+    c) a lock is used and retained by a blocking task, this reduces concurrency
+but does not undermine correctness, so again allowing the program to continue
+is fine
+
+None of these cases are erroneous (and should not be). Ada 95 allows all three.
+It does this by saying its a bounded error to block but raising P_E or just
+continuing is OK. Whether bounded error should have been used in this
+situation I'm not sure, but it was so I guess we live with it in Ada 2005.5
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Thursday, May 12, 2005  7:07 AM
+
+minor clarification so we are on the same page... I used priority pragma to
+indicate a priority ordering of the tasks that, by EDF, I would need to
+achieve by means of deadlines causing this ordering.
+
+In that case, I believe I can insist on the "1234"-Output on a
+uni-processor. (And I actually ran the program to make sure :-)
+
+****************************************************************
+
+From: Alan Burns
+Sent: Thursday, May 12, 2005  8:01 AM
+
+yes agree - was reading task 1 rather than task 2 calling this object.
+
+Are you agreeing with the substantive points?
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Thursday, May 12, 2005  10:01 AM
+
+This time, give me time to not simply cross-read, but really think about the
+corner cases as well. The quick read said, for the simple cases, that I
+agree; I might not (immediately) agree on the ultimate treatment of the
+nested case.
+
+Meanwhile, since we agree on the example, I need to understand why you
+believe that the EDF paragraphs that I am quoting do not apply or say
+priority 3 -- which I definitely cannot interpret into those paragraphs.
+///let me rephrase to be precise.../// or why a task with active priority 3
+has any business being on the ready queue for priority 1, which is what I
+think the paragraphs are saying.
+
+****************************************************************
+
+From: Alan Burns
+Sent: Thursday, May 12, 2005 11:01 AM
+
+I agree it has no business on ready queue for priority 1.
+
+I am assuming (probably wrongly!) that any task executing in a PO MUST run with
+the ceiling priority (for locking policy C_L). The whole point of the model we
+have is that no change is made to the C_L policy. So in your example, if a task
+delays or blocks within a PO when it next executes it does so with the ceiling
+priority. I do not say anything in the new parapraphs as I am assuming C_L
+covers these details. This may be wrong, in which case words need to be added
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Thursday, May 12, 2005  12:40 PM
+
+> To return to the general issues 9.5.1(17) (ie not EDF specific).
+
+> First the term 'nested protected actions' is a little confusing. 'Nested
+> monitor calls' is a well used phrase in concurrency and concernes a task in
+> one monitor calling another monitor (should it keep the first lock was the
+> original question asked in these situations).
+
+Certainly Agree.
+
+> But in 9.5.1(17) nesting here means concurrent execution within the same
+> PO.
+
+Absolutely, but only within (17). (8-13) take a much more general view on
+what causes a bounded error, i.e., not just nested monitor calls.
+
+For a nested monitor call the bounded error situations would indeed be
+complete, assuming that "it simply works" is also allowed: you block on a
+semaphore or on a lock held by another process (possibly deadlocking), or
+you run into a lock held by the current process, but that one may not lock
+you out; hence atomicity (but not mutual exclusion of processes) gets
+violated. The bounded error situation exists whether or not ceiling
+protocols are implemented with or without actual locking
+mechanisms. Rather, this bounded error reflects the implementation question
+of who or what owns the lock; that question gives rise to the "dont know
+whether deadlock or non-atomic access occurs by a nested monitor call on the
+same object."  Without this question, the bounded error should be:
+  -- works as canonically promised
+  -- deadlocks (under the right circumstances)
+  -- raises P_E
+
+For all the other cases of (8-13), the scenario that causes problems is not
+the nested monitor call. It is the fact that the monitor is logically held
+by the task that is about to be blocked on some condition or
+event. Consequently, a risk of deadlock arises (extremely hard to detect,
+even at runtime) for subsequent monitor calls, hence one of the bounded
+error situations. P_E is ok, if the implementation were to detect the
+deadlock. The big question discussed further below is whether another
+monitor call to the same object by another task/threads is locked out.  If not,
+we loose both atomicity and mutual exclusion for that object. Put
+differently, really bad things can start to happen.
+
+----
+> ....
+Glad to hear that we agree that the "no-problem" cases of potentially
+blocking operations should indeed work :-)
+
+-----
+
+Let me cut to the heart to the matter: Does "general Ada" allow for an
+implementation of ceiling locking on a uni-processor without actual locks,
+i.e., relying entirely on the priority protocol to ensure mutual exclusion ?
+By "general Ada" I mean the canonical semantics in the absence of any
+Profile.
+
+It is reasonably well known that the mutual exclusion guarantee of an
+immediate ceiling protocol without using actual locks holds only if there
+is no possibility that, once a monitor is entered, the running task is
+synchronously blocked.  9.5.1 (8-16) seems to try to enumerate all these
+situations. So, if all these situations were illegal or guaranteed to
+raise exceptions, indeed, Ada would support an implementation of ceiling
+protocols without locks.
+
+In Ada95, they are neither illegal or guaranteed ot raise P_E. They are
+rendered Bounded Error with the really serious problem of loss of mutual
+exclusion among different processes not mentioned as one of the allowed
+outcomes.
+
+Conclusion: No, Ada95 in canonical semantics does not allow for leaving
+out the locks. It's o.k. to do so under Ravenscar, because the raising of
+P_E is mandated!
+
+Question: should Ada05 allow leaving out the locks? (by fixing it to what
+seemed to have been the intent of Ada95 ??)
+
+I have been mulling this over for the last week ever since this came up,
+because the EDF-model seemed to imply this permission.
+
+It's a close call, but I am presently on the side of safety: No, Ada does
+not and should not allow a lock-free implementation of ceiling protocols in
+its canonical semantics (since it has all thse potentially blocking
+operations), but it should allow it under a set of Restrictions that ensure
+that monitor calls cannot be synchronously blocked. Mandating the P_E check
+is one of them (but then the cost of the check is rather close to the cost
+of locking); static restrictions are equally conceivable, although pretty
+draconian.  At any time, non-standard modes can do it anyway in a
+"user-beware" mode. I just do not want to see the language bent (as it
+partially is right now in 9.5.1) towards an efficient but inherently unsafe
+semantics.
+
+Mutual Exclusion among threads should be guaranteed by the language.
+
+So, Alan, in terms of ultimate conclusion, no I guess we do disagree,
+since I read youz msg to say that the canonical semantics should be
+implementable without locks. I do not know how to make that safe.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, May 12, 2005  1:50 PM
+
+...
+> Mutual Exclusion among threads should be guaranteed by the language.
+>
+> So, Alan, in terms of ultimate conclusion, no I guess we do disagree,
+> since I read youz msg to say that the canonical semantics should be
+> implementable without locks. I do not know how to make that safe.
+
+I should keep my nose out of this, but I have to come down on Alan's side.
+
+The bounded error in question (as has been said before) does not allow
+havoc. It only allows deadlock, Program_Error, or working (with possible
+loss of atomicity). Right?
+
+So that is a constraint on the *implementation*, as well as the programmer.
+The implementation has to insure that only results allowed by this bounded
+error occur. Otherwise, the implementation is incorrect.
+
+The implementation can always do that by raising Program_Error (as that is
+one of the allowed options). So I can't imagine why a lock-free
+implementation is a problem.
+
+If you have a lock, you don't need to detect blocking, because one of the
+prescribed conditions will occur. But if you don't have a lock, you will
+have trouble if you don't detect blocking. OK, so the implementation has to
+move the cost somewhere else. Big deal.
+
+Your explanation makes it sound like the implementation may not detect the
+blocking for general Ada (without Ravenscar). That's silly; an
+implementation can always do the work to detect blocking. Indeed, Janus/Ada
+actually detects the blocking *and* uses a lock.
+
+The blocking check is fairly cheap; it isn't impossible like detecting
+deadlock. All that is needed is a bit in the TCB and a test of that bit
+before operations in the list. So avoiding it isn't that big of a deal, and
+if you need it to be correct, you ought to do it.
+
+Based on your description, an implementation that implemented general Ada
+tasking with no lock *and* no blocking check would be an incorrect
+implementation of Ada. I can buy that,  there are a lot of incorrect
+implementations of Ada possible. You can't use them! But it doesn't mean
+that a no-lock implementation is impossible, only that a no-lock
+implementation must detect blocking. (And thus it is already a leg up on
+Ravenscar.) So the implementer is trading off a lock for a (cheap) check.
+That seems like a net win to me, and certainly doesn't mean that no lock is
+impossible or somehow less safe than a locking implementation. (Personally,
+I think that the blocking check is cheap enough that it always should be
+made [why allow deadlock?], but here I am getting out of my area of
+expertise so I'll keep quiet.)
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Thursday, May 12, 2005  4:04 PM
+
+> The bounded error in question (as has been said before) does not allow
+> havoc. It only allows deadlock, Program_Error, or working (with possible
+> loss of atomicity). Right?
+> So that is a constraint on the *implementation*, as well as the programmer.
+> The implementation has to insure that only results allowed by this bounded
+> error occur. Otherwise, the implementation is incorrect.
+
+Exactly my interpretation, too.
+
+> The implementation can always do that by raising Program_Error (as that is
+> one of the allowed options). So I can't imagine why a lock-free
+> implementation is a problem.
+
+I did not mean to exclude this option. You are completely correct in saying
+that.
+
+I am only opposing a model that reads into 9.5.1(17) a permission ("it's an
+error anyway") to not do locking and not do checking either, with the result
+being that mutual exclusion is no longer guaranteed. With a grain of salt, I
+could read this into the last sentence of (17) -- all I have to do is to
+drop the "nested".
+Certainly Alan did when he wrote:
+>    b) no lock but allow blocking and its up to programmer to get it
+>    right, so no exception raised and the program continues its execution
+
+
+----
+as to you statement that the P_E check is easy...that depends: if it is
+merely a check that ensures that no potentially blocking operation gets
+called, yes it is cheap. But that automatically also excludes lots of
+useful programs, i.e., my sample program would raise P_E then, for no
+good reason. (I am tempted to say that this would curtail the language
+capabilities too much, but I don't want to start that argument.)
+
+That's the corner where I will say that 9.5.1 went overboard in
+summarily making any potentially blocking call a bounded error. It needs to
+turn into a bounded error only if a cyclic resource dependency arises at
+run-time. Without the cycle, everything should simply work as advertised.
+
+Notice that the P_E check does NOT protect against all deadlocks, since the
+nested monitor call on another object is not a Bounded Error, and that
+is all it takes to create a deadlocking cyclic dependency in the general case.
+
+In the special case of immediate ceiling protocols, the P_E check protects
+against loss of mutual exclusion, though, for a non-locking implementation
+and it prevents the one situation that can give rise to a deadlock in an
+implementation of the protocol with locks (so it is a deadlock preventer
+under that scheduling regime, but not in general). For that purpose, it
+would suffice if P_E were raised if the blocking does occur, not just
+if the call is potentially blocking (and is as easily realized as
+the check on potentially blocking).
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Thursday, May 12, 2005  4:28 PM
+
+    I interpreted one of your earlier responses to say
+you were *not* worried about the permission in 9.5.1(17).
+Now it appears you are again.  It was perfectly clear
+at the time we wrote 9.5.1(17) that we were allowing
+mutual exclusion to be lost to some other thread if
+the thread holding the lock blocks, and you are using
+priorities rather than locks to provide ceiling "locking."
+Let's not try to rewrite history here.
+
+No matter how much someone may be concerned about this,
+I don't think we should try to change it.  We have
+10 years of use out there with existing RTS', and noone
+has complained (officially) about this rule in the interim, as
+far as I know.  Implementors have presumably settled
+on an appropriate compromise of safety and efficiency,
+and I don't see the need to push them one way or the
+other at this point.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, May 12, 2005  4:49 PM
+
+...
+> I did not mean to exclude this option. You are completely correct
+> in saying that.
+>
+> I am only opposing a model that reads into 9.5.1(17) a permission ("it's an
+> error anyway") to not do locking and not do checking either, with the result
+> being that mutual exclusion is no longer guaranteed. With a grain of salt, I
+> could read this into the last sentence of (17) -- all I have to do is to
+> drop the "nested".
+> Certainly Alan did when he wrote:
+> >    b) no lock but allow blocking and its up to programmer to get it
+> >    right, so no exception raised and the program continues its execution
+
+And that is absolutely correct; such an implementation is just plain wrong.
+Bounded error is not the same as erroneous (which is where the discussion
+started, I think).
+
+...
+> as to you statement that the P_E check is easy...that depends: if it is
+> merely a check that ensures that no potentially blocking operation gets
+> called, yes it is cheap. But that automatically also excludes lots of
+> useful programs, i.e., my sample program would raise P_E then, for no
+> good reason. (I am tempted to say that this would curtail the language
+> capabilities too much, but I don't want to start that argument.)
+
+But you did anyway. :-) :-)
+
+Your sample program raises Program_Error "on line 43" when run under Janus/Ada;
+that's the call "O1.Block". That seems exactly right, given the existing rules.
+
+> That's the corner where I will say that 9.5.1 went overboard in
+> summarily making any potentially blocking call a bounded error. It needs to
+> turn into a bounded error only if a cyclic resource dependency arises at
+> run-time. Without the cycle, everything should simply work as advertised.
+
+That would have been an alternative. But it's too expensive to check. And I
+don't think it would actually work with Janus/Ada runtime of hard locks:
+once a lock is locked, nothing can get it again, including the task that
+locked it. That would probably deadlock in some cases that you would "expect
+to work".
+
+I probably would have said the bounded error happens if the task actually
+blocks (period). And I'd probably require the check to be made at that point
+(it isn't expensive enough to justify avoiding it).
+
+But I can understand the current rule, too. Checking only for actual
+blocking may mean that the error only shows up under weird timing conditions
+(ones that Murphy says will never happen in testing). So now the rocket
+reaches staging and the software raises Program_Error due to a latent
+blocking problem. With the current rules and use of pragma Detect_Blocking,
+that is much less likely to happen: the error will almost certainly appear
+in testing.
+
+> Notice that the P_E check does NOT protect against all deadlocks, since the
+> nested monitor call on another object is not a Bounded Error, and that
+> is all it takes to create a deadlocking cyclic dependency in the
+> general case.
+
+Yes, of course.
+
+> In the special case of immediate ceiling protocols, the P_E check protects
+> against loss of mutual exclusion, though, for a non-locking implementation
+> and it prevents the one situation that can give rise to a deadlock in an
+> implementation of the protocol with locks (so it is a deadlock preventer
+> under that scheduling regime, but not in general). For that purpose, it
+> would suffice if P_E were raised if the blocking does occur, not just
+> if the call is potentially blocking (and is as easily realized as
+> the check on potentially blocking).
+
+Yes, I noted that above. That's probably the rule I would have used. But
+there is at least an argument for the current rule (I made it above), and we
+certainly aren't going to change this for the sake of changing it. (Why make
+work for implementations?)
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, May 12, 2005  5:11 PM
+
+>     I interpreted one of your earlier responses to say
+> you were *not* worried about the permission in 9.5.1(17).
+> Now it appears you are again.  It was perfectly clear
+> at the time we wrote 9.5.1(17) that we were allowing
+> mutual exclusion to be lost to some other thread if
+> the thread holding the lock blocks, and you are using
+> priorities rather than locks to provide ceiling "locking."
+> Let's not try to rewrite history here.
+
+Well, maybe that's clear to you, but I for one can't read that into the rule
+as it exists or anything in the AARM. I can believe that you thought that
+when the rule was crafted, but if so, it has been a well-kept secret.
+
+> No matter how much someone may be concerned about this,
+> I don't think we should try to change it.  We have
+> 10 years of use out there with existing RTS', and noone
+> has complained (officially) about this rule in the interim, as
+> far as I know.  Implementors have presumably settled
+> on an appropriate compromise of safety and efficiency,
+> and I don't see the need to push them one way or the
+> other at this point.
+
+I agree with this, but for the opposite reason: I see nothing in the current
+rules that allow the loss of mutual exclusion. And, practically, I don't
+think that an implementation could pass the ACATS if it allowed such a loss.
+(That's hard to prove, of course, since so much of this depends on timing.
+But I don't think there is any special cases in the ACATS to allow loss of
+mutual exclusion.) So I don't think that there are, in practice, any
+implementations of Ada that allow such a loss.
+
+Now, there are a lot of "almost Ada" things in real implementations (the
+infamous "non-standard mode"), and they can do what they want. But we don't
+care (here) about such things.
+
+A "nested protected action" doesn't imply that the original action is
+somehow null-and-void; it simply allows a task to start a second action on
+an object it already holds. It certainly doesn't imply that anything goes
+for other tasks. If you want some words that mean that, then *you* have to
+try to change the words. Or try to put in an AARM note to that effect (if
+you want to mis-interpret the words, which admittedly are quite vague).
+
+Certainly, if an implementer tried to blame this paragraph for the failure
+of an ACATS test because of loss of mutual exclusion, I would not give them
+much sympathy.
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Thursday, May 12, 2005  5:36 PM
+
+> A "nested protected action" doesn't imply that the original action is
+> somehow null-and-void; it simply allows a task to start a second action on
+> an object it already holds.
+
+But this is all in the context that the task holding the lock
+is *blocked*.
+
+The only possible meaning of nested protected action here
+is that some other task instigates it.  I also know that
+that is what I meant and what was discussed with the
+design and review teams.  We didn't create an AARM note
+here because we didn't sense any confusion on anyone's part.
+Apparently you and Erhard were absent during this discussion!
+I hope at least someone else in the ARG remembers it...
+
+Basically, if you use priorities for locking, then this
+is what you get.  And we knew that.  It sounds like Alan
+understood that as well.
+
+> ... It certainly doesn't imply that anything goes
+> for other tasks. If you want some words that mean that, then *you* have to
+> try to change the words. Or try to put in an AARM note to that effect (if
+> you want to mis-interpret the words, which admittedly are quite vague).
+
+I can provide some AARM wording if others think it necessary.
+But it seems pretty clear to me we must be talking about
+what can happen on behalf of other tasks, not on behalf of the task
+that is blocked.
+
+> Certainly, if an implementer tried to blame this paragraph for the failure
+> of an ACATS test because of loss of mutual exclusion, I would not give them
+> much sympathy.
+
+But you would be wrong in this case, in my view.
+
+In any case, I would be surprised if there were an ACATS test
+that would reveal this.  I am pretty sure we have
+validated with an RTS that uses priorities for locking.
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Thursday, May 12, 2005  5:55 PM
+
+>    I interpreted one of your earlier responses to say
+> you were *not* worried about the permission in 9.5.1(17).
+> Now it appears you are again.
+
+Weeell... truth be told, you did read it right. I wasn't too worried,
+because I was hoping that no implementer would have the irresponsible
+attitude to use the loophole. The more I am thinking about it, the more
+I worry.
+
+But the REAL concern that started all this was that somehow the "no locks
+needed, no blocking calls possible or, if possible, ignorable" model that
+started out with a permission flavor in 9.5.1 had turned into canonical
+semantics in EDF, i.e., the semantics only made sense if the above was
+always true, not just an option. I definitely oppose that route which
+makes a sensible and safe implementation impossible.  Meanwhile, I guess
+Alan and I are coming to a shared understanding of the Annex D semantics,
+so that the REAL concern is lessened.
+
+> It was perfectly clear at the time we wrote 9.5.1(17) that we were allowing
+> mutual exclusion to be lost to some other thread if
+> the thread holding the lock blocks, and you are using
+> priorities rather than locks to provide ceiling "locking."
+> ... Let's not try to rewrite history here.
+
+If you say so. :-)
+Should we then drop the "nested"?
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, May 12, 2005  6:18 PM
+
+...
+> The only possible meaning of nested protected action here
+> is that some other task instigates it.  I also know that
+> that is what I meant and what was discussed with the
+> design and review teams.  We didn't create an AARM note
+> here because we didn't sense any confusion on anyone's part.
+> Apparently you and Erhard were absent during this discussion!
+> I hope at least someone else in the ARG remembers it...
+
+I'm sure that I slept through it. :-)
+
+I didn't understand any of this until I tried to implement it, and that was
+years after the discussions that you are mentioning.
+
+> Basically, if you use priorities for locking, then this
+> is what you get.  And we knew that.  It sounds like Alan
+> understood that as well.
+
+I see no reason for that. The check to maintain exclusion is dirt cheap, and
+there is no reason whatsoever to allow implementations to ignore the most
+fundamental invariant of multitasking just to skip two extra instructions
+before operations that are already relatively rare (in the context of a
+complete program) and quite expensive (blocking).
+
+Certainly an implementation could follow Erhard's model and only raise the
+exception if it actually was going to block. That would make the check even
+cheaper.
+
+In any case, this is the multitasking equivalent of assuming that
+uninitialized objects are in their range. We certainly don't allow
+implementations to do that, even though it has a substantial impact on
+performance. Why in the world would we allow the same thing here, where the
+check is *cheaper* and the damage is as great (and a lot less common, making
+it much harder to track down).
+
+> > ... It certainly doesn't imply that anything goes
+> > for other tasks. If you want some words that mean that, then *you* have to
+> > try to change the words. Or try to put in an AARM note to that effect (if
+> > you want to mis-interpret the words, which admittedly are quite vague).
+>
+> I can provide some AARM wording if others think it necessary.
+> But it seems pretty clear to me we must be talking about
+> what can happen on behalf of other tasks, not on behalf of the task
+> that is blocked.
+
+I have no idea how you could reason in any useful way about a program for a
+runtime that doesn't enforce exclusion. It's very difficult to reason about
+a program that *does* enforce exclusion! So I can't imagine why this is a
+"bounded error", given that the actual effects are nearly unbounded.
+
+> > Certainly, if an implementer tried to blame this paragraph for the failure
+> > of an ACATS test because of loss of mutual exclusion, I would not give them
+> > much sympathy.
+>
+> But you would be wrong in this case, in my view.
+>
+> In any case, I would be surprised if there were an ACATS test
+> that would reveal this.  I am pretty sure we have
+> validated with an RTS that uses priorities for locking.
+
+Priorities for locking is fine, as long as you don't allow blocking in a PO.
+That requires a bit (not a lock), which is no big deal.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, May 12, 2005  6:35 PM
+
+...
+> Weeell... truth be told, you did read it right. I wasn't too worried,
+> because I was hoping that no implementer would have the irresponsible
+> attitude to use the loophole. The more I am thinking about it, the more
+> I worry.
+
+The one thing I have taken away from this exercise is that implementers will
+take any loophole given to them, no matter how irresponsible. That applies
+to me, too. When I'm wearing my implementer hat, I'll try to do whatever it
+takes to make my customers happy. Now, I don't care if implementers have
+a -fast_but_more_dangerous_than_C option switch, but the Standard shouldn't
+be in the business of allowing unnecessary dangerous constructs. (Especially
+when having such a switch is just fine.) That goes here, that goes for
+13.9.1(12), and probably other cases as well.
+
+My strong preference is to eliminate such loopholes; make sure that the
+checks involved have names so that users can suppress them when needed, but
+make the default as safe as it can be without significant distributed
+overhead. That seems to have been ignored at many turns for Ada 9X. How sad.
+After all, all Ada really has going for it are safer semantics than C (the
+syntax being better is hardly an argument that is going to make much
+difference), and abandoning that at the first sign of trouble is awful.
+Especially when so many other cases where it was *not* abandoned mean extra
+overhead for Ada compared to C.
+
+Oh well, better get off the soapbox.
+
+...
+> I definitely oppose that route which
+> makes a sensible and safe implementation impossible.  Meanwhile, I guess
+> Alan and I are coming to a shared understanding of the Annex D semantics,
+> so that the REAL concern is lessened.
+
+Absolutely. As in 13.9.1, I got just enough so that a safe implementation is
+still possible. But whether that can be done in the marketplace is a good
+question...
+
+...
+> If you say so. :-)
+> Should we then drop the "nested"?
+
+Absolutely. There is nothing "nested" about them. It is in parens, however,
+so in theory it doesn't mean anything. I suppose that's Tucker's argument;
+these are just "additional" protected operations, and the use of the word
+"nested" is unfortunate, because only the task in question could make a
+"nested" operation.
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Thursday, May 12, 2005  6:55 PM
+
+
+Alan, to come back to D.2.6 ....
+
+I read history, the AI and everything,  and I am 100% convinced now that
+rule 2 in the AI, resp. D.2.6 (24/2) is plain wrong.
+> If no such ready queue exists the task is added to the ready queue for the
+> lowest priority in the range specified as EDF_Across_Priorities.
+needs to say:
+If no such ready queue exists the task is added to the ready queue for the
+active priority of the task.
+
+<<< this rules works both for blocked tasks becoming ready again as well as
+    for newly created tasks. It is also the rule for any other scheduling
+    policy. Without this, the ceiling protocol can be violated. continue
+    reading, before questioning...>>>>
+--------------
+There is a second problem that creates numerous inconsistencies; it was
+discussed at length in the AI, but was never turned into wording.
+There definitely needs to be a rule saying:
+
+If the base priority of a task is in a priority range specified by the
+pragma EDF_Across_Priorities, the active priority of a task is the maximum
+of any priority it inherits and of the lowest priority in the priority
+range. (The base priority has no direct influence on the active priority for
+EDF dispatching.)
+
+<<<< this rule is consistent with D.1 (15), D.3.(12), D.2.6(26/2), and
+ the above rewrite of D.2.6(24/2) for newly created tasks.
+ Among others, it avoids the present inconsistency that an EDF task can be
+ in a queue with lesser priority than base or active priority. See D.2.1 (5/2)>>>
+
+-----------
+ The paras 20-23 need to be supplemented by the statement that P becomes the
+ active priority of T (or else you break D.2.1 (5/2), since without an
+ explicit statement, the active priority will be different; I can formulate
+ this in terms of inheritance, too, if you like ...).
+
+ There is a bullet 23.1 missing that says:
+    - P is greater than the active priority of T
+ <<< i.e., (20-23) can only increase the priority, not decrease.
+     Again, this is needed so that the ceiling protocol stays intact >>>
+
+----------
+Looks to me as if these changes would do away with the most noticeable
+consistency problems.
+
+----------
+
+On a more academic side: I am completely unconvinced that sensible RTA
+predictions can come from this scheduling model: the semantics in (20-23)
+resp.  rule 2 of the AI of enqueing a readied task T on the highest priority
+queue less than the preemption level of T and currently occupied by at least
+one task creates a significant race condition: arrival of such other task
+just prior or just after task T makes the active priority of T
+non-deterministic within the range Low to T'BasePriority. How RTA prediction
+can survive that is a miracle to me -- don't I get the possibility of
+starvation despite a very near deadline and a very high preemption level? I
+certainly can draw timelines where a task happens to drop into the LOW
+bucket and now needs to wait until all other tasks have completed all
+protected operations, with additionally started protected operations receiving
+preferential treatment even for tasks with remote deadlines.
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Thursday, May 12, 2005  7:59 PM
+
+> If you say so. :-)
+> Should we then drop the "nested"?
+
+I think that could hurt more than help.  It is already parenthesized.
+The point is that there is already a protected action underway,
+and because the task blocks, it allows another task at the same
+or lower priority to proceed, and it might then reenter
+the protected object performing a *nested* protected action
+on the same object.  Once it is done, the blocked task might
+reawaken and regain control, in which case it would return
+from the routine that evilly invoked the blocking construct,
+and then finish the "outer" protected action.
+
+This certainly seems pretty nested, and we make it clear
+we are talking about a protected action on the
+*same* target protected object.  So I really don't
+see where there could be any confusion if you actually
+read all the words in the sentence!
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Thursday, May 12, 2005  8:06 PM
+
+> ...
+> My strong preference is to eliminate such loopholes; make sure that the
+> checks involved have names so that users can suppress them when needed, but
+> make the default as safe as it can be without significant distributed
+> overhead.
+> ...
+
+The history behind protected objects was *all*
+about efficiency.  Being able to have a construct
+that only required raising and lowering the
+priority with no queuing whatsoever on a
+monoprocessor was one of the "raison d'etre" of
+the design.  I will object strongly if we try
+to make the priority-based implementation inappropriate,
+or require additional checks.
+
+>>If you say so. :-)
+>>Should we then drop the "nested"?
+>
+> Absolutely. There is nothing "nested" about them. ...
+
+I explained what this means.  I think you and Erhard
+must have some fundamental different world view, because I
+don't understand your confusion.
+
+Protected actions are not associated with a particular task --
+they are associated with a particular protected object.
+In a single protected action work can be done on behalf
+of many tasks.  Nesting is with respect to the protected
+object.  That is, while one protected action is underway,
+another one starts on the *same* protected object, runs
+to completion, and then at some point the outer one
+continues and completes.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, May 12, 2005  8:20 PM
+
+> This certainly seems pretty nested, and we make it clear
+> we are talking about a protected action on the
+> *same* target protected object.  So I really don't
+> see where there could be any confusion if you actually
+> read all the words in the sentence!
+
+I *did* read all of the words in the sentence! And while I agree with Erhard
+("If you say so."), you've made it clear why *you* think this is what was
+intended. But "nested" is what makes this totally mysterious, because there
+is no nesting here!
+
+Let's look at *all of the words* again:
+
+"If not detected, the bounded error might result in deadlock or a (nested)
+protected action on the same target object."
+
+Without the parenthesized comment: "a protected action on the same object"
+makes no sense, since there already is one by the current task. There would
+have to be more than one to have this mean anything at all. And "nested"
+makes it worse, because it implies that the current task is doing it - an
+operation by some other task could never be "nested" - its a completely
+separate thread of control.
+
+This should be crystal clear that it is destroying the entire tasking model.
+At a very least it should say "...or an additional protected action on the
+same target object.", which is not as open to misinterpretation. And an AARM
+note similar to the one above would be a good idea. And I would also like to
+see a documentation requirement that implementors that take advantage of
+this permission to violate mutual exclusion, so users can avoid them if they
+care.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, May 12, 2005  8:38 PM
+
+...
+> Protected actions are not associated with a particular task --
+> they are associated with a particular protected object.
+> In a single protected action work can be done on behalf
+> of many tasks.  Nesting is with respect to the protected
+> object.  That is, while one protected action is underway,
+> another one starts on the *same* protected object, runs
+> to completion, and then at some point the outer one
+> continues and completes.
+
+Fine, that's what *you* think it means. But this is not a defined term, it
+never appears normatively in the Standard or AARM, and the places where I
+see it used are completely in passing. So you completely leave it open to
+interpretation what the heck a "nested protected action" is. Nesting is
+usually a static concept ("procedure P is nested in procedure S"), so it is
+utterly confusing to use this in a totally dynamic case.
+
+Essentially, this is a case of "knowing" what you mean by something, using
+it in normative wording, and then justifying that everyone should know that
+by explaining that it means precisely what you know it means.
+
+I don't have the slightest problem believing that you think that nesting
+means what you explain above. It could even make sense; but without any such
+indication in the AARM, how in the heck is the reader supposed to know? The
+only way to know what it means is for Tucker to come along and "explain" it.
+I can't imagine that every Ada user has that resource available!
+
+For me a protected object is something that enforces mutual exclusion
+always. It's worthless if it doesn't do that. Clearly, some Ada
+implementations are worthless (in this respect), and that is allowed by the
+Standard. Can't we at least make this clear so that users can judge for
+themselves if this important? By making it a bounded error, and including
+complete havoc as one of the choices, you are neither providing well-defined
+semantics nor any documentation of the fact. I suppose that's why Ravenscar
+felt it necessary to include what is now pragma Detect_Blocking, because
+otherwise the language is unmentionably shoddy in this respect. It would be
+worlds better if we had pragma Suppress(Blocking_Check), for people that
+actually need this ultimate performance. But I suppose it is too late for
+that.
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Thursday, May 12, 2005  9:34 PM
+
+For what it's worth, 9.5.3(22) tries to make it clear
+that protected actions are associated with protected
+objects, not with particular threads of control, and
+so a "(nested) protected action on the same target object"
+was thought to be pretty clear as well.
+
+But I can accept that the term "nested protected action"
+is confusing to current readers of the manual.  When
+we wrote it, I believe it was crystal clear to the
+reviewers what it meant, and perhaps we didn't have the
+foresight to put ourselves in the shoes of someone
+10 years hence who hadn't spent 3 years arguing about
+protected records vs. passive tasks, eggshell models,
+etc., etc.
+
+So by all means, lets make it clear to the group who
+missed out, or have blessedly forgotten, all those
+discussions.  But let's not try to change the semantics.
+They were very carefully designed, and if you want to
+hear all the gory details, we will have to get Ted
+Baker and Offer Pazy on the line...  This was definitely
+not just a case of being sloppy or hang loose or throwing
+caution to the winds.  We very much knew exactly what
+we wanted to accomplish, and we discussed the whole
+area of how to handle (potentially) blocking operations
+for months, if not years.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, May 12, 2005  10:08 PM
+
+> But I can accept that the term "nested protected action"
+> is confusing to current readers of the manual.  When
+> we wrote it, I believe it was crystal clear to the
+> reviewers what it meant, and perhaps we didn't have the
+> foresight to put ourselves in the shoes of someone
+> 10 years hence who hadn't spent 3 years arguing about
+> protected records vs. passive tasks, eggshell models,
+> etc., etc.
+
+I was there, of course, but I slept through most of those discussions. I
+recall thinking that the model was neat, but totally impractical. And I
+still think that...
+
+> So by all means, lets make it clear to the group who
+> missed out, or have blessedly forgotten, all those
+> discussions.  But let's not try to change the semantics.
+> They were very carefully designed, and if you want to
+> hear all the gory details, we will have to get Ted
+> Baker and Offer Pazy on the line...  This was definitely
+> not just a case of being sloppy or hang loose or throwing
+> caution to the winds.  We very much knew exactly what
+> we wanted to accomplish, and we discussed the whole
+> area of how to handle (potentially) blocking operations
+> for months, if not years.
+
+Fair enough. But I continue to think (with the benefit of hindsight, of
+course) that the result was misguided. It smacks very much of premature
+optimization. After all, all we are really discussing is whether the check
+should have been required rather than a bounded error.
+
+It seems to me that either tasking operations are implemented by calling
+some library, or by doing them in-line. (I remember Ted trying to tell me
+that people actually thought they could successfully and profitably do those
+in-line. I still don't believe it, but let's assume they can...) If they are
+implemented in a library, the cost of setting a bit and the cost of testing
+the bit to check is far less than the calling overhead into the library. So
+there is no performance reason there for not making the check.
+
+If the operations are implemented in-line, they are available to the
+compiler for optimization. That means that a pragma Suppress on the check
+would be effective at eliminating (the already tiny) overhead.
+Alternatively, one could have had a pragma like Do_Not_Detect_Blocking to
+eliminate the overhead. Either way, the default should have been safe.
+
+Making the default safe and eliminating the overhead for the 10% of
+applications where it matters (and probably for the 5% of POs in that 10%)
+would make far more sense.
+
+Anyway, it is water under the dam at this point. (And I chose that broken
+metaphor carefully -- too much water under the dam causes it to be washed
+away -- which is I fear the potential result if we give too many loopholes
+to implementers, especially dubious ones.)
+
+I don't suppose it makes sense to change the wording from "(nested)
+protected action" to "additional protected action" (we could put it into the
+presentation AI if we did do so), but an AARM note would be called for. Can
+you craft one?; you don't have any open action items for the first time in
+my memory, so you must have plenty of spare time. :-) :-) :-)
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Friday, May 13, 2005  6:15 AM
+
+> Weeell... truth be told, you did read it right. I wasn't too worried,
+> because I was hoping that no implementer would have the irresponsible
+> attitude to use the loophole. The more I am thinking about it, the more
+> I worry.
+
+Despite a good night's sleep, the issue won't leave my mind. In reflecting
+on it some more, I realized that 6 months ago I was confronted with a
+system, in which blocking operations inside improperly synchronized critical
+regions caused unbelievable system behaviour. (Not the "blib once in a blue
+moon" failures, which one knows from missing snchronizations, but the "every
+second we loose our marbles in the most amazing ways" kind. These blocking
+operations - which weren't recognizable as such, because the blocking
+happened deep down a call chain inside a library support - were really bad
+news.) It took me about 3 weeks of redesign to get them outside the now
+synchronized critical regions and, boy, was it painful, since logically they
+were supposed to be synchronous with the critical regions. (In case you
+wonder, the impl.language was Java.)
+
+Why this story? Well, the very same thing would happen, if I used an Ada
+implementation that subscribed to the "user-beware, we rely on priority
+to guarantee mutual exclusion" model that we have been discussing.
+
+I want to take the position to, at best, let sleeping dogs lie, i.e., do not
+change anything. That is, I no longer suggest to delete the word "nested".
+
+Which gives (Randy and) me the freedom to believe that the word "nested"
+saves the day. I really don't want the language to acknowledge the
+possibility of a fundamentally unsafe implementation, causing the problems
+that I have seen.
+
+Frankly, the argument that a check against actual blocking inside a
+protected operation is too expensive, is amazingly bogus, especially since
+the assumption is already that no such call is ever issued or else you are
+seriously dead. And yes, there is a two instructions overhead on any
+protected operation to set and unset the "inside" bit in the TCB, but that
+is it. The rest is completely neglegible. Two instructions vs loss of
+safety? )
+
+Note that I am not taking away the lock-less implementation. It merely has
+to come with a guarantee of absence of blocking inside protected ops by
+Profile, Switch, Assertion, or pure Magic; excluded is only the option of
+Silent Assumption that there won't be any blocking.
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Friday, May 13, 2005  7:06 AM
+
+Presumably it is a count, not just a bit, indicating being "inside."
+And I agree it is implementable, but I don't believe this
+is fixing something for which there was any AI, nor any
+ARG discussion during a meeting.  I agree with letting
+sleeping dogs lie...
+
+****************************************************************
+
+From: Bob Duff
+Sent: Friday, May 13, 2005  8:28 AM
+
+I agree with Tucker on this point.  Namely, that the intent of the design was:
+
+    Protected records can be implemented (on a uniprocessor) using the
+    priority-based locking method.
+
+    It is wrong to put a potentially-blocking operation inside.
+
+    Implementations should not be required to have any overhead for
+    checking that rule, whether or not they use the prio-based method.
+
+If I had designed this part of the language, I would probably have done
+what Randy suggests -- *require* an exception to be raised, but then
+allow it to be suppressed with pragma Suppress.  [I know how to
+implement check suppression inside the run-time system.  I also know how
+to implement inlining of protected operations.  But these things are not
+simple, and Offer and Ted probably did not trust implementations to
+actually suppress such checks; hence the permission to suppress them
+without any pragma Suppress.  Hence, bounded error.]
+
+However, I think it should be considered out-of-bounds to change the
+semantics at this point.
+
+I understand what Tucker means by "nested", and that's clearly the only
+sensible interpretation (since the task is going to sleep, it can't be
+the one calling the PO).
+
+But I also understand why Randy and Erhard are confused by the term
+"nested".  It makes one think of the call stack -- a recursive
+invocation of the same protected operation, which is nonsense.
+Hence confusion.  How about the following re-wording:
+
+    If not detected, the bounded error might result in deadlock, or
+    another task might start an additional protected action on the same
+    target object, despite the fact that the current task holds the
+    lock.
+
+Does that make it clearer?
+
+[It's interesting that Ravenscar requires the check!  The people using
+Ravenscar are the very ones Offer and Ted were trying to satisfy
+efficiency-wise, and yet they say they don't want this little bit of
+efficiency.]
+
+P.S. I think it was *not* the intent that some implementations might
+allow blocking inside protected records, and that this would be a useful
+feature that people would actual use.  But this is in fact what has
+happened.  People write code all the time that does I/O inside protected
+records, and it works fine on some implementations.  It's unfortunate
+to have the language split into two dialects like this.  But I don't
+think we should try to fix that now.
+
+P.P.S. I still call them "protected records" when I'm not writing
+RM-ese.  But then, I still say "rep spec".  ;-)
+
+****************************************************************
+
+From: Stephen Michell
+Sent: Friday, May 13, 2005  9:46 AM
+
+I agree with Tuck's statement that his interpretation of "nested" was as he
+stated it. It was not many of the rest of our interpretations, however, and the
+language chosen was left this way because of the underlying disagreement that
+we had at the time.
+
+It is clear that the execution of any protected operation by a task while some
+other task holds the execution resource for that PO is erroneous, whether or
+not the task which holds the resource suspends. As Erhard points out, the
+object is inconsistent while a task holds the resource and any execution of
+Protected operations using that resource by another task can be disasterous.
+
+Para 17 discusses bounded errors, and the situation that we are considering is
+not a bounded error. I (and others) requested that that wording be removed but
+the mapping team refused. We agreed to leave it as it was because the term
+"nesting" here made the sentence essentially vacuous (precisely because nesting
+is a static lexical concept and of course another task can't call a nested
+protected operation without first obtaining the lock).
+
+****************************************************************
+
+From: Arnaud Charlet
+Sent: Friday, May 13, 2005  2:25 AM
+
+> The history behind protected objects was *all*
+> about efficiency.  Being able to have a construct
+> that only required raising and lowering the
+> priority with no queuing whatsoever on a
+> monoprocessor was one of the "raison d'etre" of
+> the design.  I will object strongly if we try
+> to make the priority-based implementation inappropriate,
+> or require additional checks.
+
+Strongly agreed.
+
+As an implementor of such model for some GNAT bare targets I can only
+confirm that the model works very nicely and very efficiently, as
+intended.
+
+I was not there during the design meetings, however I clearly
+recall discussing several times with both Robert Dewar and
+Ted Baker about this model and this discussion, so at least the two
+of them weren't sleeping during that meeting ;-)
+Ted also implemented such approach a few years ago for
+e.g. RT Linux and GNAT.
+
+****************************************************************
+
+From: Alan Burns
+Sent: Sunday, May 15, 2005  3:16 AM
+
+There has been a lot of email about the general issue of
+9.5.1 (17) - the conclusion of which seems to be stay as
+we are (with perhaps an AARM note to be writen by Tuck).
+For what its worth I agree fully with the line Tuck has
+been running.
+
+So as Erhard says
+
+>
+> Alan, to come back to D.2.6 ....
+>
+
+Although it is a bounded error be blocked in a PO, Erhard
+wants the model for EDF to be correct in this circumstance.
+Fine, I think it is for the reason I'll give in a moment.
+I would appreciate the views of Tuck, Pascal, Randy on this.
+
+If you have EDF you must have Ceiling_Locking.
+Under D.3 (12) a task always inherits the ceiling priority when executing
+in a PO. So this rule applies additonally to the EDF rules and hence
+if a ready queue is identified by D.2.6 (20/2-23/2) but you
+are also inheriting a ceiling priority then the ceiling is clearly
+higher and wins.
+At worst I feel a note to make this clear is all that is needed.
+
+If people disagree, then wording such as that proposed by Erhard
+below seems OK
+
+****************************************************************
+
+From: Alan Burns
+Sent: Sunday, May 15, 2005  3:30 AM
+
+> On a more academic side: I am completely unconvinced that sensible RTA
+> predictions can come from this scheduling model: the semantics in (20-23)
+> resp.  rule 2 of the AI of enqueing a readied task T on the highest priority
+> queue less than the preemption level of T and currently occupied by at least
+> one task creates a significant race condition: arrival of such other task
+> just prior or just after task T makes the active priority of T
+> non-deterministic within the range Low to T'BasePriority. How RTA prediction
+> can survive that is a miracle to me -- don't I get the possibility of
+> starvation despite a very near deadline and a very high preemption level? I
+> certainly can draw timelines where a task happens to drop into the LOW
+> bucket and now needs to wait until all other tasks have completed all
+> protected operations, with additionally started protected operations
+> receiving
+> preferential treatment even for tasks with remote deadlines.
+
+I agree that the active ready queue will change but the actual order
+of executions is the same. Baker argues very convincing;y for this
+model, we have just fitted it into the Ada ready queue descrition.
+
+One way to consider this is to see a dynamic set of levels
+for the tasks. Initially the priority'first level is the one that
+all tasks join - this remains the only level until an executing
+task (T) calls a PO. Now a new level is introduced, and this
+splits the world. Any newly arrived task should either run
+before T (as it has shorter deadline and higher preemption level),
+or after T.
+
+If it should run before T (and hence before all other tasks,
+as T was running before them) it joins the new level. If it must
+wait until after T has finished it joins the initial lower level.
+
+The new level remains until T actually executes and leaves the PO.
+While the new level exists no task in the lower level should execute,
+and all tasks that join the new level execute before T. This
+is exactly the required behavior. Further levels can be introduced
+if other POs are called.
+
+I hope this helps convince you.
+
+****************************************************************
+
+From: Bob Duff
+Sent: Sunday, May 15, 2005  6:44 AM
+
+> There has been a lot of email about the general issue of
+> 9.5.1 (17) - the conclusion of which seems to be stay as
+> we are (with perhaps an AARM note to be writen by Tuck).
+
+Alan, did you see my suggested rewording of that para?
+
+It seems clear that the para is unclear as is, given that
+Tuck and I were the only ones who admitted to understanding
+what was meant by "nested".  ;-)  I think it deserves rewording
+(but no change in (intended) meaning).
+
+****************************************************************
+
+From: Alan Burns
+Sent: Monday, May 16, 2005  3:20 AM
+
+>Alan, did you see my suggested rewording of that para?
+
+yes that seemed fine - but it seemed that the tone of the emails was that there
+is no AI on this and that a minimum AARM note was all that was required. I'm
+sure the editors will decide.
+
+By the way, for Ravenscar which is high integrity as well as real time, we
+went for detection rather than absolute efficiency.
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Tuesday, May 17, 2005  7:49 AM
+
+> I agree that the active ready queue will change but the actual order of
+> executions is the same. Baker argues very convincingly for this model, we
+> have just fitted it into the Ada ready queue description.
+
+I am worried that Ted's model has (silent) premises that are not expressed
+here.
+
+I would love to be convinced that the first sentence about the actual
+execution order were true. However, I can definitively disprove it
+   - if blocking in protected actions occurs (probably a dont care :-); or
+   - if nested protected actions are allowed (which are not a bounded
+        error presently)
+
+The 2. case is absolutely worrisome, isn't it?
+And I can show an unbounded delay for the affected task despite its near
+deadline.
+
+Should I spend the time to write the proof? Will it make a difference to how
+the EDF rules are specified?
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Tuesday, May 17, 2005  8:26 AM
+
+I figured it is better to present the example, not just claim its
+existence :-)
+
+So what's wrong in my time line? If nothing, then the EDF+Ceilings has
+a serious problem with nested monitor calls.
+
+Erhard
+
+------------------------
+
+Task A  has a long deadline and preemption level H;
+Task B has a short deadline and a preemption level b, H > b > L
+
+Sequence of events:
+
+t0: A starts
+t1: A grabs PO-L (L is its ceiling, L > bottom Prio)
+t2: A grabs PO-H, too
+
+from here, two alternative time-lines:
+
+-------------------
+1. Timeline:
+
+t3: B wakes up; it goes into the bottom queue, since its preemption
+    level is not sufficient to preempt an A holding PO-H, and there
+    are no tasks in the ready queues in between
+
+t4: A gives up PO-H
+t5: A gives up PO-L
+
+with no other tasks involved, B is scheduled at this point
+
+however...
+between t4 and t5, an arbitrary number of tasks can arrive with rather long
+deadlines and preemption level b. They go on queue L and are executed in
+preference to B, although their deadlines are much later than B's.
+They don't block, so they run to conclusion if no other tasks arrive.
+It follows that B can be delayed unboundedly, despite its near deadline.
+
+---------------------
+
+2. Timeline:
+
+t3: A gives up PO-H
+t4: B wakes up; it goes onto the L queue and is immediately scheduled,
+    since it deadline is shorter than A's; the subsequently arriving
+    other tasks cannot influence B
+    (the desired behaviour)
+....
+---------------------
+
+Conclusion:
+   -  Certainly the execution orders are different.
+   -  A rather serious race condition (t3 - t4 = Eps) decides between
+      EDF-ness of the scheduling and unbounded delays breaking deadlines.
+
+****************************************************************
+
+From: Alan Burns
+Sent: Wednesday, May 18, 2005  3:11 AM
+
+>Task A  has a long deadline and preemption level H;
+>Task B has a short deadline and a preemption level b, H > b > L
+
+You are missing a key part of the overall picture. To get the behaviour you
+require you have to choose the right values for the preemption levels. This is
+just the same as fixed priority systems. If you assigned priority following
+rate montonic then you get optimal performance, it you choose the wrong order
+then timeliness is reduced.
+
+What Baker provides is a mechanism and a policy. Ada05 supports the
+mechanism but the policy comes from the preemption levels chosen by the user.
+
+The strong result from Baker is that: if you assign preemption levels in
+inverse relative deadline order (ie rate monotonic for deadline equals period
+systems) then you get the single block no deadlock result. In your example, B
+with its short deadline would have a high preemption level - so the behaviour
+you describe would not occur.
+
+Just to repeat. In Fixed Priority Dispatching and EDF, priority is assigned in
+exactly the same way (for optimal performance). This is one of the nice
+properties we have. And if you assign priorities inappropriately you get
+sub-optimal behaviour
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Wednesday, May 18, 2005  6:31 AM
+
+> You are missing a key part of the overall picture. To get the behaviour
+> you require you have to choose the right values for the preemption
+> levels.    ....
+
+Indeed, I did not use that. So, here is my time line fixed up in accordance
+with this rule (which actually has no real bearing on the problem).
+
+Still the same problem of unbounded blocking.
+
+Next premise that I missed ?
+
+[I am not arguing about the "block only once" claim, which is rather
+ believable, given ceiling locking and only nested monitor calls.
+ I am arguing about unacceptable unbounded delays, much akin to priority
+ inversion, which clearly is a no-no in real-time scheduling.]
+
+------------------------
+
+Task A  has a very short deadline and preemption level H;
+Task B has a short deadline and a preemption level H-1, H-1 > L
+
+Sequence of events:
+
+t0: A starts
+t1: A grabs PO-L (L is its ceiling, L > bottom Prio)
+t2: A grabs PO-H, too
+
+from here, two alternative time-lines:
+
+-------------------
+1. Timeline:
+
+t3: B wakes up; it goes into the bottom queue, since its preemption
+    level is not sufficient to preempt an A holding PO-H, and there
+    are no tasks in the ready queues in between
+
+t4: A gives up PO-H
+t5: A gives up PO-L
+
+with no other tasks involved, B is scheduled at this point (o.k.)
+
+however...
+between t4 and t5, an arbitrary number of tasks can arrive with medium
+deadlines and preemption level H-2, H-2 >= L. They go on queue L and are
+executed in preference to B, although their deadlines are much later than
+B's.  They don't block, so they run to conclusion if no other tasks arrive.
+It follows that B can be delayed unboundedly, despite its near deadline.
+
+---------------------
+
+2. Timeline:
+
+t3: A gives up PO-H
+t4: B wakes up; it goes onto the L queue and, after A is finished, will
+    be scheduled in preference to the subsequently arriving
+    other tasks (o.k.)
+---------------------
+
+Conclusion:
+   -  Certainly the execution orders are different.
+   -  A rather serious race condition (t3 - t4 = Eps) decides between
+      EDF-ness of the scheduling and unbounded delays breaking deadlines.
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Wednesday, May 18, 2005  12:37 PM
+
+Ignore my last message with the revised timelime. This was too fast a
+response. I see that A cannot grab PO-L. I need to work on the example.
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Friday, May 20, 2005  7:58 AM
+
+Alan writes:
+> I would appreciate the views of Tuck, Pascal, Randy on this.
+
+So would I.
+
+Alan continues:
+> If you have EDF you must have Ceiling_Locking.
+> Under D.3 (12) a task always inherits the ceiling priority
+> when executing in a PO.
+> So this rule applies additonally to the EDF rules and hence
+> if a ready queue is identified by D.2.6 (20/2-23/2) but you
+> are also inheriting a ceiling priority then the ceiling is clearly
+> higher and wins.
+> At worst I feel a note to make this clear is all that is needed.
+> If people disagree, then wording such as that proposed by Erhard
+> below seems OK.
+
+My reaction... NO. We do not specify rules like "A = 5", "A = 6", and "if in
+doubt, the first rule wins". We try to never have contradicting
+rules (and the current rules are contradictory in their wording).
+The wording does need to be fixed.
+
+****************************************************************
+
+From: Alan Burns
+Sent: Tuesday, May 24, 2005  9:03 AM
+
+There has been a series of emails concerning Annex D, which
+has now gone quiet. I think there is one open issue, some
+closed issues and a list of possible edits to the current
+text.
+
+The open issue concerns the rules for EDF. If a task becomes
+unblocked in a protected operation the current wording seems
+to be be wrong. I feel that as Ceiling_Locking is required
+then the unblocked task must run with ceiling priority. Erhard
+feels that this is not enough and that rewoding is needed.
+I'll leave this issue for now.
+
+The main point of this email is to put in one place what I
+think are the edits needed to Annex D following Erhard and Tullio's
+comments, my replies and subsequent emails.
+Perhaps Randy has all this in place and has already
+done the edits - but the following might help. I am assuming
+that Erhard being quiet on an issue means he has agreed with me
+(I'm sure he will shout it that is not the case).
+
+
+Alan
+
+--
+
+
+EPD1: D.2.1, 1.3/2: "with dispatching" -> "with task dispatching".
+	OK
+
+EPD2: D.2.1, 9/2: implementation[-]defined manner
+	OK
+
+EPD3: D.2.2 2.2/2: may have a formatting problem (line split)
+	OK
+
+EPD4: D.2.2 3/2 and 3.1/2 could be easily combined to read "The
+policy_identifier used in either pragma shall...
+
+	OK, but current wording is very clear
+
+
+EPD9: D.2.2, 6.3/2 Presumably not intended but right now this says that
+setting a base priority unconditionally preempts the caller since the
+affected
+task "is immediately dispatched". It should say "is
+immediately subject to the new dispatching policy".
+
+	Yes that is probably better
+
+
+EPD11: D.2.5 6/2:  "for a single [priority] level"
+
+	OK
+
+
+EPD13: D.2.5 14/2:  WRONG!!!! APPLIES ONLY TO READY TASKS.
+But I am not sure whether simply adding "ready" here is sufficient.
+        OK, could add 'ready' or use esiting text such as:
+     When the setting of the base priority of a running task takes
+     effect and the new priority is a Round Robin priority the
+     task is moved to the tail of the ready queue for its new priority
+
+
+
+EPD16: D.2.6 18/2 presumably should read : "...than the [active] priority"
+
+	Yes
+
+
+
+EPD17: D.2.6 20/2 BIG BUG !?! This model does not work.
+
+        This is the remaining open issue
+
+
+EPD18: D.2.6 22/2 BUG!! In a mixed mode, there is no guarantee that P is
+an EDF-Priority and that the tasks in the P-queue have deadlines at
+all. This looks like a workable model only if paras 20-24 are
+subjected to the restriction of P being within the same EDF-priority
+range. Note also that multiple ranges may be present.
+
+        I agree this clarification is needed, suggest add after 'highest
+priority P' (in 20/2) the words 'within the priority range for the policy
+that applies to T'
+
+
+EPD20: D.2.6 24/2: Wording nit: "if no such ready queue exists" is always
+false; the queue exists for sure. "if no such priority P
+exists" is more like what is intended here.
+
+        Agreed
+
+
+
+EPD21: D.2.6 24/2: BUG. in the case, where multiple priority ranges are
+specified as EDF-priorities (which presently is allowed), the para is
+ill-defined, since it doesn't say of which EDF-range.
+
+        Yes some added words needed - would 'for task T' at the end be OK?
+
+
+
+EPD23: D.2.6 24.a/2 1. BIG BUG!!! interesting... shorter deadlines by
+themselves do not cause preemption ???  True by the above words in the RM,
+but this is fundamentally wrong, isn't it? AI-357 agrees: the words
+earlier in the RM are fundamentally wrong: a shorter deadline (just now
+unblocked from some queue or delay) should preempt within the same
+priority, the AI says so explicitly, but this preemption rule is not there
+in the RM. Note that the rule is needed, since otherwise you may end up
+with EDF for non-communicating tasks being equal to Nonpreemptive
+scheduling!
+
+        After much thought I agree. Add after 18/2 as a 4th bullet
+point: 'there is a task on the ready queue for the active priority
+of T with a deadline shorter than the deadline of T.'
+
+
+
+EPD26: D.2.6 25/2: WRONG!!!! APPLIES ONLY TO READY TASKS. But I am not
+sure whether simply adding "ready" here is sufficient.
+
+        Yes adding ready is needed here, and is sufficinet I think,
+or use words similar to EDP13 above.
+
+
+
+EPD28: D.2.6 26/2: what is an "active priority of the ready queue"?
+Should read "the active priority of a task chosen for execution is the
+priority of the ready queue from which it was taken."
+
+
+        Yes this is better or 'active priority set to the priority
+of the ready queue ...'
+
+
+
+EPD29: D.2.5 27/2 "in this package" -> in package Ada.Dispatching.EDF
+
+        OK
+
+
+
+EPD31: D.5.1. 10/2 The new verbage is definitely insufficient. Consider
+that the call on Set_Priority is issued by some other task not presently
+involved in a protected operation. Hence the setting of the priority needs
+to happen immediately (since "the first point..." is now). This is not the
+intent, is it? It certainly would contradict what 10.a/2 is saying and
+what AI-188-2 wants to achieve. The words are plain wrong, since they do
+not refer to the task whose priority is being changed.
+However, just adding that task context to the words still seems wrong,
+since the AI seems to try for an immediate change on all ready queues (on
+which I can be, while preempted in a protected operation) and postponed
+change on entry queues. (The stuff about abortion doesn't help me.)
+
+        Yes this rule applies to the designated task, not the one calling
+Set_Priority; this needs to be clear if Erhard read this the other way
+round. But the wording used here is the same as in existing RM
+(D.5.1(10)). So I'm not sure if re-wording is needed, happy to
+leave that to Randy
+
+
+
+EPD35: D.14 25/2 superfluous blank in "execution -time"
+
+        Agreed
+
+
+EPD37: D.14.1 21/2 "were a handler [of at least that ceiling priority] to
+be executed." Actually, I would prefer less conditionality:
+"The constant Min_Handler_Ceiling is the priority value that ensures that
+no ceiling violation will occur if a handler of at least this priority is
+executed."
+
+        I leave that up to the Editor
+
+
+EPD39: D.14.2 29/2 "were a handler [of at least that ceiling priority] to
+be executed." Actually, I would prefer less conditionality:
+"The constant Min_Handler_Ceiling is the priority value that ensures that
+no ceiling violation will occur if a handler of at least this priority is
+executed." see EPD37 for an ident. comment
+
+        I leave that up to Editor
+
+
+
+EPD41: D.15 15/2 Why not as the first step? I would be really worried, if
+an already mostly finalized Timing_Event fired.
+
+        I cannot remember why it says final
+
+
+
+D.2.1(9.a): typo: "The affect of" for "The effect of"
+
+        OK
+
+
+D.2.6(18/2): Again, we use the term "priority" without qualifying it with
+"active", as we should, also given 19/2.
+
+        Agree we could add active
+
+
+
+D.2.6(30/2): typo: "procressor" for "processor".
+
+        OK
+
+
+
+
+D.4(12): typo: "if more than one such call has" --> "have" ?
+
+        ?
+
+
+D.6.1(3.b/2): typo: "processorshall" --> "processor shall"
+
+        OK
+
+
+
+D.14(25/2): typo: "execution -time" --> "execution-time"
+
+        OK
+
+
+
+D.14.2(6/2): typo: "range <})" --> "range <>)"
+
+        OK
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Wednesday, May 25, 2005  6:25 AM
+
+I have updated the example so that it now assigns base priorities in
+deadline order. The problem is still there. The scheduling is subject to
+unbounded delays for "high priority" tasks, which is completely
+unacceptable.  An analysis of why this is so (and a way to fix it)
+is added at the bottom.
+
+------------------------
+
+Task A  has a long deadline and preemption level LOW
+Task B has a short deadline and a preemption level b, H > b > L > LOW
+
+Sequence of events:
+
+t0: A starts
+t1: A grabs PO-L (L is its ceiling)
+t2: A grabs PO-H, too
+
+from here, two alternative time-lines:
+
+-------------------
+1. Timeline:
+
+t3: B wakes up; it goes into the bottom queue, since its preemption
+    level is not sufficient to preempt an A holding PO-H, and there
+    are no tasks in the ready queues in between
+
+t4: A gives up PO-H
+t5: A gives up PO-L
+
+with no other tasks involved, B is scheduled at this point
+
+however...
+
+between t4 and t5, an arbitrary number of tasks can arrive with medium
+deadlines and preemption level x, b > x > L. They go on queue L and are
+executed in preference to B, although their deadlines are later than
+B's.  If they don't block and no other tasks arrive, they run to conclusion
+which will be away as far as their own deadline.
+
+It follows that B can be delayed unboundedly, despite its near deadline.
+Note that no task after t5 accesses a PO.
+
+---------------------
+
+2. Timeline:
+
+t3: A gives up PO-H
+t4: B wakes up; it goes onto the L queue and is immediately scheduled (see
+    footnote *** below), since it deadline is shorter than A's;
+    the subsequently arriving other tasks cannot influence B
+    (the desired behaviour)
+....
+---------------------
+
+Conclusion:
+   -  Certainly the execution orders are different.
+   -  A rather serious race condition (t3 - t4 = Eps) decides between
+      EDF-ness of the scheduling and unbounded delays breaking deadlines.
+
+*** actually, by current rules, it is not immediately scheduled. Present
+rules 15/2-18/2 do not make this a task dispatching point, so B has to
+wait until A is done with PO-L. Arguably, a break with the notion that
+a higher-priority task preempts any task of lower active priority.
+This is a side-issue, though (but it does play a role in the fix proposed
+below).
+
+---------------------
+
+Analysis:
+   The hole that I drove the truck through is the fact that the current
+   rules allow for tasks to be queued at preemption levels and to retain
+   the active priority thus acquired after the PO that caused it all has
+   been released.
+
+   For a while, I thought that the fix would be a loss of active priority
+   for a queue members once the causing PO is released. I could not believe
+   that this was reasonable semantics, due to the distrivbuted overhead on
+   PO-operations.
+
+   Then, for a while, I thought that 20/2-23/2 were just a very round-about
+   way of saying that the new task preempts and that it is impossible to get
+   any task to stay on a queue at levels higher than LOW other than a
+   preempted task. I.e., 20/-23/2 only put something on these queues for
+   immediation selection by the scheduler.
+
+   However, that's not the case. See also the *** footnote.
+   (If someone does find the words that say so, please also check
+   the case of equal base priorities, because in that case, 23/2 disallows
+   EDF-scheduling.)
+
+   If that were the case, the problem would go away and EDF would work (and
+   replacing 20/2-23/2 by a "preempts" rule would make a lot more sense
+   to the reader.
+
+****************************************************************
+
+From: Alan Burns
+Sent: Wednesday, May 25, 2005  7:28 AM
+
+>I have updated the example so that it now assigns base priorities in
+>deadline order. The problem is still there. The scheduling is subject to
+>unbounded delays for "high priority" tasks, which is completely
+>unacceptable.  An analysis of why this is so (and a way to fix it)
+>is added at the bottom.
+>
+
+Sorry to disagree ;-)
+
+>Task A  has a long deadline and preemption level LOW
+>Task B has a short deadline and a preemption level b, H > b > L > LOW
+>
+>Sequence of events:
+>
+>t0: A starts
+>t1: A grabs PO-L (L is its ceiling)
+>t2: A grabs PO-H, too
+>
+>from here, two alternative time-lines:
+>
+>-------------------
+>1. Timeline:
+>
+>t3: B wakes up; it goes into the bottom queue, since its preemption
+>    level is not sufficient to preempt an A holding PO-H, and there
+>    are no tasks in the ready queues in between
+
+No, I have not got the words in front of me, but L does have a task executing
+within it (ie A - the fact that it is also in H does not stop it being in L as
+well). So B joins (is the only member of) ready queue at level L; and the right
+behaviour follows.
+
+Interestingly, it was when I did a formal proof of the protocol that this case
+came out. Before that the situation was as you describe (we talked about
+non-empty ready queues).
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Wednesday, May 25, 2005  10:13 AM
+
+> No, I have not got the words in front of me, but L does have a task
+> executing within it (ie A - the fact that it is also in H does not stop it
+> being in L as well).
+
+I stand corrected. I did not think to interpret 21/2 in the transitive way.
+(And I am begining to believe in the semantics, well, up to wording :-)
+
+> So B joins (is the only member of) ready queue at level
+> L; and the right behaviour follows.
+
+Agreed, given DMPO.
+
+Minor question, quite possibly only for my education:
+
+why doesn't 23/2 say "the base priority of T is greater than or equal to P"?
+I realize that a DMPO would not allow this for a t with an earlier
+deadline, but it sure seems harmless and more in the spirit of EDF to let
+the task with the earlier deadline take over at equal preemption level.
+
+And, the related secondary question: Is "adding a task to a ready queue"
+always a dispatching point? (For a ready queue, whose level is higher than
+that of the running task, it is per 18/2.) -- For my suggestion above, this
+would have to include equal as well upon changes to the queue.
+
+****************************************************************
+
+From: Tullio Vardanega
+Sent: Wednesday, May 25, 2005  9:30 AM
+
+I reckon that the right behaviour should be warranted anyway
+if preemption levels were assigned inverserly proportional
+to the respective deadline.
+This does not seem to be the case in Erhard's example, does it?
+
+In timeline 1. (the problematic one), at time t3, task B gets into
+queue L because task A sits in there (but also in queue H, which
+is however higher than b); B gets ahead of A in L because it has
+an earlier deadline, so that when A releases PO-H, B preempts it
+and the right behaviour follows.
+
+I suppose that Alan did already point this out, but you'll excuse my
+being slower ;-)
+
+*****************************************************************
+
+From: Erhard Ploedereder
+Sent: Wednesday, May 25, 2005  12:47 PM
+
+On the semi-open issues....
+
+
+> EPD13: D.2.5 14/2:  WRONG!!!! APPLIES ONLY TO READY TASKS.
+         But I am not sure whether simply adding "ready" here is sufficient.
+
+Alan:
+>        OK, could add 'ready' or use esiting text such as:
+>     When the setting of the base priority of a running task takes
+>     effect and the new priority is a Round Robin priority the
+>     task is moved to the tail of the ready queue for its new priority
+
+I agree with Alan's wording suggestion. (and note that the "ready, not
+running" case is covered by D.2.4 (6/2)) I knew "ready" was not enough :-)
+
+-------
+
+> EPD21: D.2.6 24/2: BUG. in the case, where multiple priority ranges are
+> specified as EDF-priorities (which presently is allowed), the para is
+> ill-defined, since it doesn't say of which EDF-range.
+>
+>        Yes some added words needed - would 'for task T' at the end be OK?
+
+If Alan agrees with changing the sentence anyway to refer to the active
+priority (as discussed in a separate thread), the issue is moot. If not,
+then this becomes a worm of a sentence, since "for task T" doesn't really
+help - more like "the range in which the base priority of the task T is
+included" , but since I would disagree on intent, anyway, I won't suggest
+wording ;-)
+Nota bene the obvious contradiction of this sentence with another sentence
+in the RM that says that all tasks are in the queues of their active
+priority, which Alan simply wants to "win" over this contradicting sentence.
+
+-----------
+
+> EPD26: D.2.6 25/2: WRONG!!!! APPLIES ONLY TO READY TASKS. But I am not
+> sure whether simply adding "ready" here is sufficient.
+
+Alan:
+>        Yes adding ready is needed here, and is sufficinet I think,
+>or use words similar to EDP13 above.
+
+On this one, I agree with the "ready". Note that the suggested EDP13 wording
+would not work, since there is then no rule around for "ready, not running"
+tasks, is there?
+
+*****************************************************************
+
+From: Erhard Ploedereder
+Sent: Wednesday, May 25, 2005  7:02 PM
+
+A postscript to :
+> Minor question, quite possibly only for my education:
+
+> why doesn't 23/2 say "the base priority of T is greater than or equal to P"?
+> I realize that a DMPO would not allow this for a t with an earlier
+> deadline, but it sure seems harmless and more in the spirit of EDF to let
+> the task with the earlier deadline take over at equal preemption level.
+
+> And, the related secondary question: Is "adding a task to a ready queue"
+> always a dispatching point? (For a ready queue, whose level is higher than
+> that of the running task, it is per 18/2.) -- For my suggestion above, this
+> would have to include equal as well upon changes to the queue.
+
+I just noticed that Alan's response to EPD23 addresses the second half of
+this question already with the asked-for change.
+Alan, can I convince you of the first one, too? It's only logical to do at
+preemption levels what you do at base level.
+
+Here is the EPD23 exchange for easier reference:
+
+> EPD23: D.2.6 24.a/2 1. BIG BUG!!! interesting... shorter deadlines by
+> themselves do not cause preemption ???  True by the above words in the RM,
+> but this is fundamentally wrong, isn't it? AI-357 agrees: the words
+> earlier in the RM are fundamentally wrong: a shorter deadline (just now
+> unblocked from some queue or delay) should preempt within the same
+> priority, the AI says so explicitly, but this preemption rule is not there
+> in the RM. Note that the rule is needed, since otherwise you may end up
+> with EDF for non-communicating tasks being equal to Nonpreemptive
+> scheduling!
+
+>         After much thought I agree. Add after 18/2 as a 4th bullet
+> point: 'there is a task on the ready queue for the active priority
+> of T with a deadline shorter than the deadline of T.'
+
+*****************************************************************
+
+From: Alan Burns
+Sent: Thursday, May 26, 2005  2:48 AM
+
+> I reckon that the right behaviour should be warranted anyway
+> if preemption levels were assigned inverserly proportional
+> to the respective deadline.
+> This does not seem to be the case in Erhard's example, does it?
+
+
+I think we do get the 'right' behaviour. Remember with fixed priority
+scheduling if the priorities are assigned in the wrong order some tasks will
+suffer unacceptable delays
+
+*****************************************************************
+
+From: Erhard Ploedereder
+Sent: Thursday, May 26, 2005 12:33 AM
+
+Mostly as a postscript to Randy, the Editor, in case he is keeping track of
+rationales of changes:
+
+> EPD23: D.2.6 24.a/2 1. BIG BUG!!! interesting... shorter deadlines by
+> themselves do not cause preemption ???  True by the above words in the RM,
+> but this is fundamentally wrong, isn't it? AI-357 agrees: the words
+> earlier in the RM are fundamentally wrong: a shorter deadline (just now
+> unblocked from some queue or delay) should preempt within the same
+> priority, the AI says so explicitly, but this preemption rule is not there
+> in the RM. Note that the rule is needed, since otherwise you may end up
+> with EDF for non-communicating tasks being equal to Nonpreemptive
+> scheduling!
+
+>         After much thought I agree. Add after 18/2 as a 4th bullet
+> point: 'there is a task on the ready queue for the active priority
+> of T with a deadline shorter than the deadline of T.'
+
+Here is the wooden nickel example that shows that much more would have been
+broken without this added rule:
+
+Task A  has a long deadline and preemption level LOW
+Task B has a short deadline and a preemption level b, H > b > L > LOW
+
+Sequence of events:
+
+t0: A starts
+t1: A grabs PO-L (L is its ceiling)
+t2: A grabs PO-H, too
+t3: B wakes up; it goes into L queue, since its preemption
+    level is not sufficient to preempt an A holding PO-H
+
+t4: A gives up PO-H
+since A now goes back to level L, it MUST be that B with its lesser
+deadline takes over, or else....
+
+t5: A grabs PO-(L+1); b > L+1
+now many tasks arrive, with medium deadlines and preemption level L+1
+(and I can worsen the picture to all levels x, b < x < L,  by A grabing
+ PO-H after t5 before arrival of these tasks)
+t6: A gives up PO-(L+1)
+
+Now all the medium deadline tasks at level L+1 are executed in preference to
+B, although their deadlines are later than B's.  If they don't block and no
+other tasks arrive, they run to conclusion which will be away as far as
+their own deadline. Again, we would have unbounded starvation despite
+deadline monotonic priorities/preemption levels.
+
+t7: A gives up PO-L
+t8: finally B's turn
+--------------------
+
+****************************************************************
+
+From: Tullio Vardanega
+Sent: Thursday, May 26, 2005  5:03 AM
+
+I am commenting on:
+
+(a):
+Erhard's comment on Alan's response to EPD21
+"[...] Nota bene the obvious contradiction of this sentence
+[TV: i.e. D2.6(24/2)] with another sentence in the RM that
+says that all tasks are in the queues of their active priority [...]"
+
+(b):
+Alan's recommendation to:
+"[...] Add after 18/2 as a 4th bullet point: 'there is a task on
+the ready queue for the active priority of T with a deadline
+shorter than the deadline of T.' "
+
+Regarding (a):
+AI-357 makes it clear that tasks are initially placed in the ready
+queue for the lowest priority level in their EDF range of reference.
+This is what 20/2 says. And this, intentionally and legitimately,
+overrides the previous RM rule.
+The whole point of this overriding is that tasks be ordered by
+earliest deadline, whereas priorities are used for ruling on
+PO locking (Baker's SRP).
+I suppose that an explicit note to this effect would do, in lieu
+of the ramblings in 8.a/2.
+
+Regarding (b):
+If I understand how the EDF scheme works (which I hope
+I do ;-), then I *cannot* see -- in force of (a) above and of
+[20/2-24/2] -- how 17/2 can ever occur.
+Instead I very much see the point of the new (4th bullet) clause
+that Alan suggests to add and I suspect that it really should
+replace 17/2.
+In other words, 17/2 seems to imply priority-based dispatching
+irrespective of deadlines, which does not seem right.
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Friday, May 27, 2005  7:26 AM
+
+> AI-357 makes it clear that tasks are initially placed in the ready
+> queue for the lowest priority level in their EDF range of reference.
+> This is what 20/2 says.  ....
+
+No, that's not (all) what 20/2 says. It does say what you claim,
+but it also says that this is true for any task which becomes ready for any
+reason, and for all the latter tasks the sentence is wrong, wrong, wrong.
+
+A second observation is that "active priority" for EDF-scheduling is
+presently not defined by the RM. We all think we know what it means, but
+actually, we're not being told by the RM (except that it is a function of
+the base priority and any inherited priority; but which function, we're not
+being told -- D.1(15)). Luckily for this case, because this does allow us to
+define "active priority" (which we have to do anyway, since D.1 forces us to
+do so) to ignore the base priority.
+
+Somehow, I seem to be unable to communicate my RM point (which has nothing
+to do with which rule is right or wrong):
+       "The RM shall not have contradicting statements".
+
+The notion that one rule somehow "overrides" another rule is an impossible
+notion, unless the rule says so. And we have precise terminology for that.
+And we all hate it when we need to apply it.
+It is spelled "Notwithstanding what this International Standard says
+elsewhere", the backside of the moon is made of green cheese after all.
+Luckily we don't need this here.
+
+
+> If I understand how the EDF scheme works (which I hope
+> I do ;-), then I *cannot* see -- in force of (a) above and of
+> [20/2-24/2] -- how 17/2 can ever occur.
+
+E.g., a call on Set_Deadline. (You did mean 17/2, right, since you mention
+it thrice ? But then, I don't get the last point which seems to be more
+about 18/2 than 17/2).
+
+So, to answer your question above for 18/2 instead...
+a) a task that blocks inside a protected op, upon wakeup  (o.k., its a
+   bounded error, but still...)
+b) on a multi-processor (by virtue of 20/2-23/2 on another processor)
+c) on a uni-processor .... -- I can't think of one, neither ... Alan??
+
+****************************************************************
+
+From: Alan Burns
+Sent: Tuesday, May 31, 2005  5:14 AM
+
+>Minor question, quite possibly only for my education:
+>
+>why doesn't 23/2 say "the base priority of T is greater than or equal to P"?
+>I realize that a DMPO would not allow this for a t with an earlier
+>deadline, but it sure seems harmless and more in the spirit of EDF to let
+>the task with the earlier deadline take over at equal preemption level.
+>
+
+The preemption level control protocols (including the ceiling protocol of Ada
+95) always has the rule of strictly greater - this ensures mutual exclusion
+when no blocking inside the object.
+
+****************************************************************
+
+From: Alan Burns
+Sent: Tuesday, May 31, 2005  5:22 AM
+
+>If Alan agrees with changing the sentence anyway to refer to the active
+>priority (as discussed in a separate thread), the issue is moot. If not,
+>then this becomes a worm of a sentence, since "for task T" doesn't really
+>help - more like "the range in which the base priority of the task T is
+>included" , but since I would disagree on intent, anyway, I won't suggest
+>wording ;-)
+
+Yes this wording is better.
+
+>Nota bene the obvious contradiction of this sentence with another sentence
+>in the RM that says that all tasks are in the queues of their active
+>priority, which Alan simply wants to "win" over this contradicting sentence.
+
+
+I do not see the contradiction - ready queue remains equal to active
+priority - but the rules for which ready
+queue (and hence the resulting active priority) are different for EDF
+
+****************************************************************
+
+From: Alan Burns
+Sent: Tuesday, May 31, 2005  5:26 AM
+
+>I just noticed that Alan's response to EPD23 addresses the second half of
+>this question already with the asked-for change.
+>Alan, can I convince you of the first one, too? It's only logical to do at
+>preemption levels what you do at base level.
+
+No - in fixed priority scheduling (and EDF) you need to have a strictly
+higher priority to preempt.
+- see my previous email.
+
+the following does not concern preemption levels, just a newly released
+task with a shorted deadline than the running task - and hence preemption. My
+'much thought' was was not the rule but whether it was covered elsewhere (which
+I convincedmyself it was not)
+
+****************************************************************
+
+From: Alan Burns
+Sent: Tuesday, May 31, 2005  5:31 AM
+
+> In other words, 17/2 seems to imply priority-based dispatching
+> irrespective of deadlines, which does not seem right.
+
+
+17/2 is there to cover the case that the running task sets the deadline
+of some other
+task, and the new level is shorter than the running task. This is unlikely
+but has to be covered. However saying that, the new bullet covers
+this case as well and hence 17/2 could now be dropped (I think)
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Saturday, November  5, 2005  2:19 PM
+
+
+collected final comments....
+
+-----
+Editorials:
+
+D.2.1, 9/2 superfluous blank "implementation- defined"
+D.2.2, 2.2/2 formatting:  why are two lines needed ?
+
+-----
+BUG:
+
+D.2.6. 25/2
+The para reads:
+When the setting of the base priority of a task takes effect and the
+new priority is in a range specified as EDF_Across_Priorities, the
+task is added to the ready queue corresponding to its new active
+priority, as determined above.
+
+This is wrong, as it would make blocked tasks ready. In earlier
+discussion of this (see e-mail dated 25 May 05, 19:46:53), Alan agreed
+to put "ready" in the sentence as in...
+
+"When the setting of the base priority of a ready task takes effect and
+the.."
+
+Please do put it in.
+
+-----
+Editorial:
+EPD29: D.2.5 27/2 "in this package" -> in package Ada.Dispatching.EDF
+
+Alan wonders whether this is "too much of an edit".
+But, just read it in context of the RM (not the AI). "this package" in
+this RM place lacks any kind of textual binding.
+
+------
+BUG:
+
+Tullio writes:
+> D.14(17/2 and 19/2): these two clauses disagree on the effect of calling
+> Clock on tasks that be in between terminated and no longer existing.
+(and similar complaints on paragraphs cited below.)
+
+Erhard writes:
+> EPD34: D.14 17/2: kill the half-sentence dealing with a terminated task
+> T. Is covered by 19/2 (erroneous). ... As it is, there is a rather nasty
+> race condition between getting an exception or being erroneous.
+
+> EPD38: D.14.1 22/2 kill the half-sentence dealing with a terminated
+> task T. It is covered by 24/2 (erroneous).  See EPD34 for more detail.
+
+> EPD40: D.14.2 33/3 kill the half-sentence dealing with a terminated
+> task T. It is covered by 35/2 (erroneous). See EPD34 for more detail.
+
+Randy writes:
+> As Alan points out, this makes no sense; these rules work the same as the
+> ones for the operations in Task_Identification itself (such as Terminated).
+> Surely we aren't going to have stricter requirements here than there??
+
+Indeed, but we do right now because Alan is plain wrong...in
+Task_Identification, there is no Tasking_Error being raised on
+terminated tasks (just search for the word). In C.7.1., calling for a
+terminated task is erroneous. Period. The same should hold here.
+
+Hence our comments stand. The fix ought to be made in all these places
+to avoid a nasty race condition.
+--------------------
+BUG:
+
+EPD42: D.15 26/2 The Note is in direct contradiction of 22/2. Delete it or
+make it work by adding rules in the context of 22/2.  And even if it were
+not contradictory, it could not be a Note, since it cannot be derived from
+the RM.
+
+Nobody seems to have picked up/responded on this issue (para. numbers
+updated to the current version)
+
+(Why is it contractory? Imagine two tasks issuing such calls; how can you
+possibly satisfy atomicity required by 22/2 without risk of blocking ? )
+
+I ask for deletion, given the status of Notes. vs. IRs. The Note is not
+derivable at all, so a change would be necessary anyway. (But, if Alan
+thinks that the semantics are needed, fine, make it an IR, but somehow
+resolve the contradiction then.)
+
+------
+BUG/Disagreement
+
+D.2.6(1/2) states:
+> ... Unless otherwise specified, whenever tasks compete for processors or
+> other implementation-defined resources, the resources are allocated to
+> the task with the earliest deadline.
+
+Erhard writes:
+> EPD15: D.2.6 1/2: insert in second sentence: "if Earliest Dedline First
+> (EDF) scheduling is in effect," because otherwise this surely doesn't
+> apply. Or, more formally, "if the pragma EDF_Across_Priorities applies,".
+
+Tullio writes:
+> D.2.6(1/2): The last sentence of the clause is rather tricky, because
+> clause D.1(15) states that resource allocation is decided on the highest
+> priority level and D.1 should presumably be valid for all dispatching
+> policies (as amended by local rules, of course). Hence, either this
+> sentence is explicitly placed in the context of the EDF dispatching
+> policy or we have to look back at D.1(15).
+
+Randy writes:
+> This introductory text was dicussed extensively at an ARG meeting, and there
+> is no reason to revisit that.
+
+Sorry, but I am saying it is clearly wrong, since it mandates
+deadline-ordered queues in all places that do not say otherwise. Are
+you claiming it says something different?
+
+****************************************************************
+
+From: Alan Burns
+Sent: Sunday, November 13, 2005  4:08 AM
+
+- -----
+>BUG:
+>
+>D.2.6. 25/2
+>The para reads:
+>When the setting of the base priority of a task takes effect and the
+>new priority is in a range specified as EDF_Across_Priorities, the
+>task is added to the ready queue corresponding to its new active
+>priority, as determined above.
+>
+>This is wrong, as it would make blocked tasks ready. In earlier
+>discussion of this (see e-mail dated 25 May 05, 19:46:53), Alan agreed
+>to put "ready" in the sentence as in...
+>
+>"When the setting of the base priority of a ready task takes effect and
+>the.."
+>
+>Please do put it in.
+
+OK
+
+>- -----
+>Editorial:
+>EPD29: D.2.5 27/2 "in this package" -> in package Ada.Dispatching.EDF
+>
+>Alan wonders whether this is "too much of an edit".
+>But, just read it in context of the RM (not the AI). "this package" in
+>this RM place lacks any kind of textual binding.
+>
+
+OK - obviously Randy's call
+
+...
+>>As Alan points out, this makes no sense; these rules work the same as the
+>>ones for the operations in Task_Identification itself (such as Terminated).
+>>Surely we aren't going to have stricter requirements here than there??
+>>
+>>
+>
+>Indeed, but we do right now because Alan is plain wrong...in
+>Task_Identification, there is no Tasking_Error being raised on
+>terminated tasks (just search for the word). In C.7.1., calling for a
+>terminated task is erroneous. Period. The same should hold here.
+>
+>Hence our comments stand. The fix ought to be made in all these places
+>to avoid a nasty race condition.
+
+Perhaps I quoted the wrong 'example'. I refer you to D.11 in Ada 95. Here
+tasking_error is raised if task has terminated ( D.11(8)) and program is
+erroneous if task no longer exists (para 9). I think this is fine as a task
+moves from terminated to no longer existing in a clear defined way. So I do not
+see a race condition and think we can stay with these words. In fact I seem to
+remember (and this is some years ago now) Erhard was the person who drafted
+these words for me!
+
+
+...
+>I ask for deletion, given the status of Notes. vs. IRs. The Note is not
+>derivable at all, so a change would be necessary anyway. (But, if Alan
+>thinks that the semantics are needed, fine, make it an IR, but somehow
+>resolve the contradiction then.)
+
+It is important that 26/2 is true as a number of algorithms of use will
+need this. Also note that the handler is executed at priority
+Interrupt_Priority'last, so on a single processor atomicity comes for free.
+
+I assumed that a Note was correct as we are making use of the lack of a
+statement that a call of Set_Priority is potential blocking.
+
+Blocking is an Ada term. I do not feel it follows that to implement
+atomicity the effected task needs to be blocked in the Ada sense of the term.
+Moreover to implement atomicity I would execute Set_Priority at priority
+Interrupt_Priority'last so we get serialization without any form of blocking
+(just preemption)
+
+I conclude no need to change.
+
+...
+>Randy writes:
+>>This introductory text was dicussed extensively at an ARG meeting, and
+>>there is no reason to revisit that.
+>
+>Sorry, but I am saying it is clearly wrong, since it mandates
+>deadline-ordered queues in all places that do not say otherwise. Are
+>you claiming it says something different?
+
+I assumed that the introductory paragraph was just that - introductory. It
+gives the basic property of the algorithm. I was asked to reword this many
+times with final agreement on the current words - so I tend to agree with Randy
+
+PS my apologies for not attending forthcoming meeting
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Tuesday, November 15, 2005  11:30 PM
+
+Erhard writes:
+
+> collected final comments....
+>
+> -----
+> Editorials:
+>
+> D.2.1, 9/2 superfluous blank "implementation- defined"
+
+I don't see this blank.
+
+> D.2.2, 2.2/2 formatting:  why are two lines needed ?
+
+Because one line wouldn't fit on the page. (Remember, the RM is smaller than
+the AARM - look at the RM-Final.PDF file.)
+
+> -----
+> BUG:
+>
+> D.2.6. 25/2
+...
+> "When the setting of the base priority of a ready task takes effect and
+> the.."
+>
+> Please do put it in.
+
+OK.
+
+> -----
+> Editorial:
+> EPD29: D.2.5 27/2 "in this package" -> in package Ada.Dispatching.EDF
+>
+> Alan wonders whether this is "too much of an edit".
+> But, just read it in context of the RM (not the AI). "this package" in
+> this RM place lacks any kind of textual binding.
+
+You mean D.2.6(26), right? This change was already made there.
+
+> ------
+> BUG:
+>
+> Tullio writes:
+> > D.14(17/2 and 19/2): these two clauses disagree on the effect of calling
+> > Clock on tasks that be in between terminated and no longer existing.
+> (and similar complaints on paragraphs cited below.)
+...
+> Indeed, but we do right now because Alan is plain wrong...in
+> Task_Identification, there is no Tasking_Error being raised on
+> terminated tasks (just search for the word). In C.7.1., calling for a
+> terminated task is erroneous. Period. The same should hold here.
+
+Huh? Calling for a terminated (but existing task) in C.7.1 is legal and had
+better work. Are you saying that an implementation of Is_Terminated that
+always returns False is correct? I don't think so.
+
+In any case, I should have pointed out C.7.2 (Task Attributes), which has
+*exactly* these rules. (And always has, see C.7.2(13)). And Alan points out
+that D.11 has these rules, too.
+
+> Hence our comments stand. The fix ought to be made in all these places
+> to avoid a nasty race condition.
+
+As Alan says in his reply, these are transitions that happen in some random
+way. A task goes from running to terminated and then eventually to not
+existing. Tullio talks about a task that's "in between terminated and not
+existing", but I don't know what that means: either the task still exists in
+the standard form, or it doesn't. It's not like objects gradually fade
+away!!
+
+And I don't see that the "race condition" here matters in implementation
+terms; we have a defined result for a terminated task that the
+implementation knows about. It's certainly not testable for a "non-existent"
+task, anyway, so I don't see any impact.
+
+There's nothing wrong here, I've made no change here.
+
+> --------------------
+> BUG:
+>
+> EPD42: D.15 26/2 The Note is in direct contradiction of 22/2. Delete it or
+> make it work by adding rules in the context of 22/2.  And even if it were
+> not contradictory, it could not be a Note, since it cannot be derived from
+> the RM.
+>
+> Nobody seems to have picked up/responded on this issue (para. numbers
+> updated to the current version)
+>
+> (Why is it contractory? Imagine two tasks issuing such calls; how can you
+> possibly satisfy atomicity required by 22/2 without risk of blocking ? )
+>
+> I ask for deletion, given the status of Notes. vs. IRs. The Note is not
+> derivable at all, so a change would be necessary anyway. (But, if Alan
+> thinks that the semantics are needed, fine, make it an IR, but somehow
+> resolve the contradiction then.)
+
+I'm following Alan's resolution here. Especially as I see no reason to think
+that atomicity requires blocking: surely pragma Atomic doesn't require
+blocking, and set handler is just a pointer copy anyway - it would be hard
+for it to be *non-atomic*. And, as Alan says, predefined routines are not
+potentially blocking unless we say so.
+
+Note that Task Attributes require atomicity, but are not defined to be
+potentially blocking. (Humm, that might be a bug. Well, whatever.)
+
+> ------
+> BUG/Disagreement
+>
+> D.2.6(1/2) states:
+> > ... Unless otherwise specified, whenever tasks compete for processors or
+> > other implementation-defined resources, the resources are allocated to
+> > the task with the earliest deadline.
+>
+> Erhard writes:
+> > EPD15: D.2.6 1/2: insert in second sentence: "if Earliest Dedline First
+> > (EDF) scheduling is in effect," because otherwise this surely doesn't
+> > apply. Or, more formally, "if the pragma EDF_Across_Priorities
+> applies,".
+>
+> Tullio writes:
+> > D.2.6(1/2): The last sentence of the clause is rather tricky, because
+> > clause D.1(15) states that resource allocation is decided on the highest
+> > priority level and D.1 should presumably be valid for all dispatching
+> > policies (as amended by local rules, of course). Hence, either this
+> > sentence is explicitly placed in the context of the EDF dispatching
+> > policy or we have to look back at D.1(15).
+>
+> Randy writes:
+> > This introductory text was dicussed extensively at an ARG meeting, and
+> > there is no reason to revisit that.
+>
+> Sorry, but I am saying it is clearly wrong, since it mandates
+> deadline-ordered queues in all places that do not say otherwise. Are
+> you claiming it says something different?
+
+OIC. Yes, that is goofy, and something needs to be done. The deadline values
+are meaningless unless a dispatching policy that uses them is in effect. The
+"unless otherwise specified" is exactly backwards for that purpose.
+
+I changed it to:
+
+The deadline of a task is an indication of the urgency of the task; it
+represents a point on an ideal physical time line. For policies that use
+deadlines, whenever tasks compete for processors or other
+implementation-defined resources, the resources are allocated to the task with
+the earliest deadline.
+
+Using the vague "policies" to cover imp-def task dispatching policies using
+deadlines, and possibly even locking or queuing policies.
+
+****************************************************************
+
+From: Alan Burns
+Sent: Wednesday, November 16, 2005  4:14 AM
+
+As I will not be at the meeting, just wanted to throw in my view that I
+agree with all of Randy's thoughts
+above (especially when he agrees with me!). The re-wording in the final
+part of above seems to usefully
+cover this and any imp-def related policy.
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Saturday, November 19, 2005  6:21 AM
+
+We are trying to be sure there are sufficient rules
+to determine what dispatching policy applies to a task,
+and to cover how tasks move from one dispatching policy
+to another.  In particular, we have debated whether
+the base priority or the active priority of a task
+determines which dispatching policy it obeys.
+
+D.2.1(5) links dispatching policies to ready queues,
+which seems to favor active priority as determining the
+dispatching policy.
+
+D.2.2(6.3) talks about changes to base priority as being
+something that might affect what dispatching policy applies,
+even though setting a base priority might not affect
+active priority if there are priorities being inherited;
+furthermore, if a task inherits a high-enough priority presumably
+it could become subject to another dispatching policy.
+
+D.2.6(20-23) imply that a task's base priority must
+be within an EDF range for them to apply, but it seems
+possible that through inheritance a task's active
+priority could be in an EDF range even though it's base
+priority isn't.
+
+What happens when an EDF task is held?  The effect of "Hold"
+is described in terms of removing the base priority as a
+source of inheritance, but base priority isn't a source
+of inheritance in EDF, and instead acts as an upper limit.
+
+Comments appreciated!  I'll try to send more info later.
+
+****************************************************************
+
+From: Alan Burns
+Sent: Sunday, November 20, 2005  6:49 AM
+
+Sorry for slow reply - broadband failed at home so I've had
+to come to work to see if there were any ARG emails!
+
+...
+> D.2.1(5) links dispatching policies to ready queues,
+> which seems to favor active priority as determining the
+> dispatching policy.
+
+That is not quite my reading of this paragraph. I feel it is saying the whole
+model of dispatching is described in terms of ready queues. And that policies
+when defined will need to refer to their impact on ready queues.
+
+> D.2.2(6.3) talks about changes to base priority as being
+> something that might affect what dispatching policy applies,
+> even though setting a base priority might not affect
+> active priority if there are priorities being inherited;
+> furthermore, if a task inherits a high-enough priority presumably
+> it could become subject to another dispatching policy.
+
+To stop inherence being the cause of a permanent policy change we link
+policy to base priority. In a multi-policy system in which tasks interact
+across the policies (by for example sharing access to a protected
+object) a task will 'obey' the rules for the ready queue it is on (ordered
+by EDF or Deadline).
+
+> D.2.6(20-23) imply that a task's base priority must
+> be within an EDF range for them to apply, but it seems
+> possible that through inheritance a task's active
+> priority could be in an EDF range even though it's base
+> priority isn't.
+
+Yes this is intended. Assume a band of EDF on top of a round
+robin low priority band. A RR task shares an object with an EDF
+task. So when the RR enters the PO its active priority will rise to a priority
+in the EDF range, It is the fundamental priority level that keeps it
+executing; if it was eligible to run and then has its priority raised it
+must still be the most eligible task to run unless and until some other task
+is released - if it is preempted it will be placed on the ready
+queue for this active priority in a position determined by its 'deadline'.
+Note all tasks have deadlines, even if their base priority is not in an EDF
+band. However the rules preemptive dispatching imply that the ready
+queue at that time will only have the RR task on it.
+
+> What happens when an EDF task is held?  The effect of "Hold"
+> is described in terms of removing the base priority as a
+> source of inheritance, but base priority isn't a source
+> of inheritance in EDF, and instead acts as an upper limit.
+
+When a task is held its base priority is changed to be below that of
+the idle task. So if it was EDF before being held it is no longer an EDF
+task when held. Later when 'continued' its base priority is changed back to
+the EDF level and it continues as an EDF task.
+
+> Comments appreciated!  I'll try to send more info later.
+
+I do not see any contradictions in the paragraphs you  quote
+
+1) The base priority of a task determines the basic policy under which
+it is dispatched
+2) A dispatching policy determines the rules for the behavior of the
+ready queues under its control
+3) If the active priority of a task is in the same priority (policy)
+band as its base priority, no problem at all
+4) If the active priority is higher (it cannot be lower) then if it is
+preempted it will join an empty ready queue
+and if that ready queue has later tasks added then the policy for the
+queue applies.
+5) Note all tasks have deadlines (default), and the rules for Round
+Robin tasks make it clear that
+they cannot have their quantum exhausted while inheriting a priority.
+6) All non-EDF queues are order by FIFO and hence defined for all tasks
+
+Seems alright to me!
+I hope this helps
+
+****************************************************************
+
+From: Stephen Michell
+Sent: Sunday, November 20, 2005  7:39 AM
+
+Perhaps you will available to join us by phone this morning. Joyce has
+net-phone on her laptop and will call you if you are available and give
+a number. We start meeting in 1/2 hour.
+
+I have some comments.
+
+At the end, I also have a few issues that need addressing.
+
+...
+>> D.2.2(6.3) talks about changes to base priority as being
+>> something that might affect what dispatching policy applies,
+>> even though setting a base priority might not affect
+>> active priority if there are priorities being inherited;
+>> furthermore, if a task inherits a high-enough priority presumably
+>> it could become subject to another dispatching policy.
+>
+> To stop inherence being the cause of a permanent policy change we link
+> policy to base priority. In a multi-policy system in which tasks interact
+> across the policies (by for example sharing access to a protected
+> object) a task will 'obey' the rules for the ready queue it is on
+> (ordered by EDF or Deadline).
+>
+Agreed. It took a while to come around to this, but we now are in agreement.
+
+>> D.2.6(20-23) imply that a task's base priority must
+>> be within an EDF range for them to apply, but it seems
+>> possible that through inheritance a task's active
+>> priority could be in an EDF range even though it's base
+>> priority isn't.
+>
+> Yes this is intended. Assume a band of EDF on top of a round
+> robin low priority band. A RR task shares an object with an EDF
+> task. So when the RR enters the PO its active priority will rise to a
+> priority in the EDF range, It is the fundamental priority level that keeps it
+> executing; if it was eligible to run and then has its priority raised it
+> must still be the most eligible task to run unless and until some
+> other task is released - if it is preempted it will be placed on the ready
+> queue for this active priority in a position determined by its
+> 'deadline'. Note all tasks have deadlines, even if their base priority is
+> not in an EDF band. However the rules preemptive dispatching imply that
+> the ready queue at that time will only have the RR task on it.
+
+It certainly is true on a single-cpu system that raising a higher
+priority implies that the que for that priority is currently empty, but
+that does not imply that the queue will remain empty until the task
+finishes executing at the priority. Since the task has an effective
+infinite deadline, it could be very adversely affected by a call to a PO
+in an EDF priority range.
+
+I think that we need to say that the priority of protected types must be
+above the EDF range, unless EDF is the only policy on the system.
+
+...
+
+Here are the other issues that I identified.
+
+D.1(20) [AI-357/11]
+   This paragraph was updated as suggested at the Burlington meeting. The minutes of
+   that meeting say "Alan will update the AARM note". Since that didn't happen
+   (so far as I can tell - the Annex D comments got very confused), I tried to
+   update it.              (LOOK AT THIS & NEXT FEW, & FOR POLICIES)
+
+We need to make it clear what the connection is between active priority and
+base priority. Here is possible wording.
+
+      Unless otherwise specified for a task dispatching policy, the
+     active priority is the maximum of the base priority and any
+     priority inherited by T.
+
+
+ D.2.6(17-18)
+   Current wording says that a dispatching point happens when a task is
+in a queue. The actual point is the event of the other task being added
+to a queue. Here is suggested wording
+
+15 A task Dispatching... (same)
+16 a change to the deadline... (same)
+17 a task is added to the ready queue with the same priority as the
+active priority of the executing task but has an earlier deadline than
+the executing task
+18 a task is added to a ready queue of the same processor as the
+executing task but with a higher priority than the active priority of
+the executing task
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Sunday, November 20, 2005  8:08 AM
+
+We went ahead and decided the following:
+
+   The base priority determines the policy that computes
+   the active priority.  The active priority determines
+   what ready queue the task ends up in.
+
+I think that essentially agrees with what you are saying.
+
+As far as "held" tasks, it seems like their active
+priority should be computed using the FIFO_Within_Priorities
+policy, excluding the base priority from the calculation.
+
+Does that make sense?
+
+****************************************************************
+
+From: Alan Burns
+Sent: Monday, November 21, 2005  3:07 AM
+
+> We went ahead and decided the following:
+>
+>   The base priority determines the policy that computes
+>   the active priority.  The active priority determines
+>   what ready queue the task ends up in.
+>
+> I think that essentially agrees with what you are saying.
+
+yes that fine
+
+ As far as "held" tasks, it seems like their active
+> priority should be computed using the FIFO_Within_Priorities
+> policy, excluding the base priority from the calculation.
+>
+> Does that make sense?
+
+yes - as I said I feel the definition of held is 'change base priority to this
+minimum value'. With a multi-policy system we say that any priority level
+that is not explicitly defined to have a policy has 'FIFO_Within_Priority'
+(D.2.2 3.5/2), so I assumed we already covered this situation. However
+if extra words are needed to say this, fine
+
+*****************************************************************
+

Questions? Ask the ACAA Technical Agent