!standard RM-D.11 (05) 99-08-31 AI95-00092/07 !standard RM-D.01 (21) !standard RM-D.01 (22) !class binding interpretation 95-09-29 !status Corrigendum 2000 99-05-25 !status WG9 approved 96-12-07 !status ARG approved 9-0-0 96-06-17 !status work item 95-11-01 !status received 95-09-29 !priority High !difficulty Hard !qualifier Clarification !subject Priority changes due to Set_Priority and Hold are not transitive !summary If Set_Priority or Hold is called on a task, other tasks that are currently inheriting priority from the first task do not have their active priorities modified. !question D.1(21-22) says: 21 During activation, a task being activated inherits the active priority of the its activator (see 9.2). 22 During rendezvous, the task accepting the entry call inherits the active priority of the caller (see 9.5.3). But this implies that if Set_Priority or Hold is called on a task, other tasks that are currently inheriting priority from the first task, would have to have their active priorities modified. Is this asynchronous priority inheritance the intent? (No.) !recommendation (See summary.) !wording Modify D.1(21-22) as follows: 21 During activation, a task being activated inherits the active priority that its activator (see 9.2) had at the time the activation was initiated. 22 During rendezvous, the task accepting the entry call inherits the priority of the entry call (see 9.5.3 and D.4). Note that "priority of the entry call" is defined in D.4(9-11) in such a way that it doesn't change during rendezvous -- it can only change when the call is still queued. !discussion Note: This AI subsumes AI95-00090. D.1(21-22) seem to imply that asynchronous priority inheritance is required, meaning that when Set_Priority is called on a task, the active priority of other tasks must be modified. It was clearly not the intent to require asynchronous priority inheritance. Set_Priority is inherently asynchronous -- the task being affected may be doing anything when Set_Priority is called. However, we do not wish to require this asynchronous behavior to extend to *other* tasks -- asynchronous priority inheritance -- because it would be an implementation burden, and it is not clearly useful, given that priority inheritance is not uniformly transitive in all cases. D.4(8-11) supports the above as the "intent": 11 When the base priority of a task is set (see D.5), if the task is blocked on an entry call, and the call is queued, the priority of the call is updated to the new active priority of the calling task. This causes the call to be removed from and then reinserted in the queue at the new active priority. If Set_Priority on an entry caller were really intended to affect the active priority of a rendezvous-in-progress, then why would D.4(11) go to the trouble to say "and the call is queued"? This intent is also supported by the NOTE in D.11(17): 17 If a task becomes held while waiting (as a caller) for a rendezvous to complete, the active priority of the accepting task is not affected. There are two possible solutions: Alternative 1: Asynchronous priority inheritance does not happen. This is the interpretation given in the summary and wording above. In this alternative, if Set_Priority is applied to a task, then other tasks that are currently inheriting priority from the first task do not have their active priorities modified. Alternative 2: Asynchronous priority inheritance is not required, but an implementation may do it. In this alternative, when Set_Priority is applied to a task, it is implementation-defined whether or not other tasks that are currently inheriting priority from the first task have their active priorities modified. Inheritance due to activation and rendezvous should be treated the same, and for rendezvous, it shouldn't make a difference whether the call is the trigger of an ATC or not. Both alternatives obey this principle. The advantage of Alternative 1 is that it requires more uniformity across implementations. However, Alternative 2 seems to allow a fairly harmless implementation variation. Clearly, Alternative 2 is not harder to implement than Alternative 1. It is conceivable that Alternative 2 might be easier in some environments. Note that either alternative allows an implementation to support asynchronous priority inheritance as a non-standard policy. Alternative 1 implies that if asynchronous priority inheritance is supported, the implementation must support two mechanisms, whereas Alternative 2 allows the asynchronous case to be the only one. The implementation variation allowed by Alternative 2 is not entirely harmless. If a program is written assuming transitive priority inheritance, it could miss real-time deadlines when ported to an implementation that does not support transitive priority inheritance. When porting in the other direction, a working program could fail because of a violation of the ceiling rule in D.3(13): 13 When a task calls a protected operation, a check is made that its active priority is not higher than the ceiling of the corresponding protected object; Program_Error is raised if this check fails. In fact, Alternative 2 would allow an implementation to cause a "retroactive" violation of D.3(13). Presumably, the implementation would have to resolve this difficultly if it chose to implement asynchronous priority inheritance. Note that D.5(10) only talks about the task being directly affected, not other inheritors: 10 Setting the task's base priority to the new value takes place as soon as is practical but not while the task is performing a protected action. Presumably, the implementation would extend this deferral of priority changes to apply to the inheritors as well. The discussion above refers to Set_Priority. The same arguments apply to Hold -- the whole point of defining Hold in terms of priorities was to avoid having to spell out all kinds of interactions between Hold and other tasking features. Presumably, programs will not typically use both Hold and other features (like rendezvous) together. Therefore, the efficiency of Hold on a task in rendezvous doesn't matter. It's just important that there be little or no distributed overhead (in either direction). Note that the issue does not arise for protected entry calls (the case in D.1(23)), because ceiling priorities can never change. Given the advantages of implementation uniformity, Alternative 1 is chosen. Implementations that wish to support asynchronous priority inheritance must do so via a non-standard policy. !corrigendum D.01(21) @drepl @xindent @dby @xindent !corrigendum D.01(22) @drepl @xindent @dby @xindent !ACATS test A test is needed to check that the priority doesn't change when it shouldn't (using Set_Priority and/or Hold). Check that existing test CXDB005 does not violate this ruling. !appendix !section RM-D.1(22) !subject Priority inheritance in rendezvous from async select !reference RM95-D.1(22) !reference RM95-D.4(8-11) !from Tucker Taft 95-09-08 !reference as: 95-5275.a Tucker Taft 95-9-8>> !discussion D.1(22) states: During rendezvous, the task accepting the entry call inherits the active priority of the caller (see 9.5.3). I believe this should say: During rendezvous, the task accepting the entry call inherits the active priority of the caller while the caller is blocked on the entry call; for a call due to an asynchronous select, it inherits the priority that was the active priority of the caller at the time the entry call was issued. This could be simplified to say simply "the task accepting the entry call inherits the priority of the entry call" which is defined in D.4(9), but the priority of a "call" does not change when the caller's priority changes due to priority inheritance. We presumably want indirect priority inheritance to work, whereas there was a conscious decision to not require priority inheritance to cause entry queue reordering, so that priority inheritance could be implemented more efficiently (and "implicitly" using some kind of chained ready-queue structure) -- see the discussion of dynamic priorities in the Ada 95 Rationale. -Tuck **************************************************************** !section RM-D.1(22) !subject Priority inheritance in rendezvous from async select !reference RM95-D.1(22) !reference RM95-D.4(8-11) !reference 95-5275.a Tucker Taft 95-9-8 !from Ted Baker 95-09-09 !reference as: 95-5278.a Ted Baker 95-9-9>> !discussion Tucker is right. No one intended that the cited sentence constitute a requirement that the priority of an entry call be updated to track changes to the active priority of the caller. The "active priority of the caller" refers to the active priority of the caller at the time the call is made. In retrospect, it would have been cleaner to refer to the priority of the call, here, rather than the priority of the caller. --Ted Baker **************************************************************** !section RM-D.11(05) !subject Async Task Control while caller in rendezvous !reference RM95-D.11(5,17) !from Tucker Taft 95-09-11 !reference as: 95-5282.a Tucker Taft 95-9-11>> !discussion The note in paragraph D.11(17) seems wrong. It says: If a task becomes held while waiting (as a caller) for a rendezvous to complete, the active priority of the accepting task is not affected. This is true if the active priority of the acceptor was originally higher than that of the caller. But per D.1(20,22), if the active priority of the acceptor was originally lower than that of the caller, then the acceptor's active priority should drop to that old value when the caller is held, since the caller's active priority has effectively dropped to minus infinity. -Tuck **************************************************************** !section RM-D.11(05) !subject Async Task Control while caller in rendezvous !reference RM95-D.11(5,17) !reference 95-5282.a Tucker Taft 95-9-11 !from Ted Baker 95-09-12 !reference as: 95-5284.a Ted Baker 95-9-12>> !discussion Tucker said: | The note in paragraph D.11(17) seems wrong. It says: | If a task becomes held while waiting (as a caller) for a rendezvous | to complete, the active priority of the accepting task is not affected. | This is true if the active priority of the acceptor was originally higher | than that of the caller. But per D.1(20,22), if the active priority of | the acceptor was originally lower than that of the caller, then the acceptor's | active priority should drop to that old value when the caller is held, | since the caller's active priority has effectively dropped to minus | infinity. We intentionally did not require adjustment of active priority, because we wanted to allow flexibility for efficient implementation of the low-level tasking operations. The only reason those "low-level" tasking operations are in the language is because some people were concerned that the semantics of the existing scheduling and synchronization operations (protected objects, rendezvous) are sufficiently complex that they will incur runtime overhead that is unacceptable for some applications. Far from being unfounded, the wisdom of those concerns is becoming clearer as we more completely understand the ramifications of implementing the full protected entry semantics in an asynchronous priority scheduling environment. Therefore, we should take care not to impose any additional implementation weight on the low-level tasking operations. Interestingly, the alternative semantics Tucker proposes works efficiently in one implementation model. In this implementation of priority inheritance, a queue is kept of all tasks, ordered by base priority. The active priority of a task is never recorded anywhere. The effect of priority inheritance is achieved because the dispatcher just searches down the priority queue for a task that can run, chaining forward along wait-for relationships if it finds a high-priority task that is waiting for another task. (If a "blocked" task is encountered, the dispatcher drops to the next lower base-priority task, and chains again if necessary.) In this model, the way you implement "hold" on a task is about the same as blocking it, i.e. mark it as held/blocked, meaning that it cannot be waiting for any other task. This effectively terminates any wait-for chain involving this task, and so it does not have the effect of loaning any priority to any other task. On the other hand, if an implementation keeps track of active priority explicitly, the hold operation for a task is going to have to some complicated and potentially time consuming work. In case this is not obvious, suppose some task A is held. The RTS will have to check whether A is involved as caller in any rendezvous. This will involve locking the state of the acceptor of the rendezvous, if there is one, so that this information does not change while we are examining it. We will then have to check whether the acceptor's current priority is dependent on inheritance from the held task, and then perhaps lower the acceptor's active priority. This priority-lowering may cause ready-queue deletion and reinsertion, and a task switch. All this gets reversed when the held task is released. The net effect is that the low-level operation has now become very heavy-weight. To preserve the intent of these operations, I suggest that if there is any change/interpretation it be toward allowing a wider range of efficient implementations, e.g. | It is implementation defined whetehr when a task becomes held | while waiting (as a caller) for a rendezvous to complete, the | active priority of the accepting task is affected. --Ted Baker **************************************************************** !section RM-D.11(05) !subject Async Task Control while caller in rendezvous !reference RM95-D.11(5,17) !reference 95-5282.a Tucker Taft 95-9-11 !reference 95-5284.a Ted Baker 95-09-12 !from Tucker Taft 95-09-12 !reference as: 95-5285.a Tucker Taft 95-9-12>> !discussion > Tucker said: > > | The note in paragraph D.11(17) seems wrong. It says: > > | If a task becomes held while waiting (as a caller) for a rendezvous > | to complete, the active priority of the accepting task is not affected. > > | This is true if the active priority of the acceptor was originally higher > | than that of the caller. But per D.1(20,22), if the active priority of > | the acceptor was originally lower than that of the caller, then the acceptor's > | active priority should drop to that old value when the caller is held, > | since the caller's active priority has effectively dropped to minus > | infinity. > > We intentionally did not require adjustment of active priority, > because we wanted to allow flexibility for efficient > implementation of the low-level tasking operations. > ... I don't find this "flexibility" in the RM, except in note D.11(17), which does not imply flexibility, but rather implies that you must *not* propagate the change in active priority to the acceptor. Can you cite any non-note paragraphs which indicate this "flexibility" or which specify exactly what should happen when an entry caller in rendezvous is held? D.1(20,22) seems to indicate that the active priority of the caller is relevant throughout the rendezvous. We all seem to agree that this means the priority of the "call" when the call was from an async-select, but I don't find any basis for deciding what to do in the case of a synchronous call from a task that is then held. In the case where both the caller and the acceptor are held, then I would expect that both tasks would stop running immediately, whereas if only one of them is held, then the rendezvous would complete before the held task stops. This implies that when a task is held, it's base priority no longer contributes to itself nor to any other task (indirectly, via its active priority). > ... > To preserve the intent of these operations, I suggest that if there > is any change/interpretation it be toward allowing a wider range > of efficienct implementations, e.g. > > | It is implementation defined whetehr when a task becomes held > | while waiting (as a caller) for a rendezvous to complete, the > | active priority of the accepting task is affected. Seems reasonable, but I don't find any sign of this in the current RM, other than the note in D.11(17), which doesn't imply any flexibility. The Rationale for Hold/Continue definitely talks about using the priority equivalence to ensure that the semantics are well defined. Also, the argument about overhead seems a bit weak in the case where a rendezvous is already involved ;-). Finally, for an acceptor, it is clear that you have to recompute the active priority for the rendezvous when the acceptor is held, so it doesn't seem very surprising that if the caller is held, then the priority of the rendezvous also needs to be recomputed. > --Ted Baker -Tuck **************************************************************** !section RM-D.11(05) !subject Async Task Control while caller in rendezvous !reference RM95-D.11(5,17) !reference 95-5282.a Tucker Taft 95-9-11 !reference 95-5284.a Ted Baker 95-09-12 !from Offer Pazy 95-09-12 !reference as: 95-5287.a Offer Pazy 95-9-13>> !discussion Please look at the rationale (D.1.2) for a discussion of the issues for when to have priority inheritance and where not to. Quite early in the process, we have decided not to have transitive priority inheritance for many reasons mostly because of implementation difficulties and "not-essential-when-we-have-protected-objects" argumnets. Having a task inherit the priority of the caller *after* the rendezvous has started really falls under transitive priority inheritance since the event that may cause the priority change is asynchronous to teh executing task. (I'm a bit lazy to repeat all the issues, they are sumarized quite nicely in the rationale's section mentioned above). That my view with respect to our design principles, and therefore I think that the note in D.11(17) is correct and should stay this way. (Note also that D.4(11) talk only about the case when the calling task in on the queue, not when the rendesvous/entry body has started.) I agree that we have a problem with the word "during" in D.1(22), but it is clear to me that if something has to change, this is the rule that needs to change. Doing otherwise, will have *very heavy* implememetation cost and is a big deviation from the Ada 83 rules (and is not needed). > We all seem to agree that this means the priority of > the "call" when the call was from an async-select, Not all of us... If you stick with D.1 (22) I don't see any basis (or need or benefit) to distinguish between the two cases. But I really think that we shoudl try very hard not to require implementations to support transitive-priority-inheritance. This will be unfortunate, since it will require vendors to do a lot of work which we have not intented to require, just because of a "typo". > In the case where both the caller and the acceptor are held, then > I would expect that both tasks would stop running immediately, > whereas if only one of them is held, then the rendezvous would complete > before the held task stops. This is a ramification of the current rules. I hope you don't suggest a new rule here. > > | It is implementation defined whetehr when a task becomes held > > | while waiting (as a caller) for a rendezvous to complete, the > > | active priority of the accepting task is affected. > > Seems reasonable, but I don't find any sign of this in the > current RM, other than the note in D.11(17), which doesn't imply > any flexibility. I don't know based on what you see it is impl-defined, and I really don't like it to be impl-defined here. I think it's not a useful way-out. We have a contradiction, but there is no hint of impl-definedness here. > Finally, for an acceptor, it is clear that you have to recompute the > active priority for the rendezvous when the acceptor is held, so it > doesn't seem very surprising that if the caller is held, then the > priority of the rendezvous also needs to be recomputed. It's a big difference. For the acceptor: You change its base (or make it held) and then you recompute its active priority. If you chnage the base (or make held) of the caller, then you have to recompute the active priority of another task (the acceptor) which makes it an asynchronous change. Finally, note that all this discussion has nothing to do with the related discussion of queue reordering as a result of changing the base priority since in neither PO queue no task entry queue, the priorities of the tasks on the queue do not serve as a source of PI. Furthermore, for PO's the ceiling is static so it does not matter. In summary, this is another argument all together. Offer Pazy 31 Robinwood Ave. Boston, MA 02130 USA (617)522-5988 pazy@world.std.com **************************************************************** !section RM-D.11(05) !subject Async Task Control while caller in rendezvous !reference RM95-D.11(5,17) !reference 95-5282.a Tucker Taft 95-9-11 !reference 95-5284.a Ted Baker 95-09-12 !reference as: 95-5285.a Tucker Taft 95-9-12 !from Ted Baker 95-09-12 !reference as: 95-5288.a Ted Baker 95-9-13>> !discussion | > We intentionally did not require adjustment of active priority, | > because we wanted to allow flexibility for efficient | > implementation of the low-level tasking operations. | > ... | I don't find this "flexibility" in the RM, except in note | D.11(17), which does not imply flexibility, but rather implies | that you must *not* propagate the change in active priority to the | acceptor. Can you cite any non-note paragraphs which indicate | this "flexibility" or which specify exactly what should happen | when an entry caller in rendezvous is held? D.1(20,22) seems to | indicate that the active priority of the caller is relevant | throughout the rendezvous. We all seem to agree that this means | the priority of the "call" when the call was from an async-select, | but I don't find any basis for deciding what to do in the case of | a synchronous call from a task that is then held. No, I think we presumed incorrectly that it would always be less efficient to propagate the change in priority. | Seems reasonable, but I don't find any sign of this in the | current RM, other than the note in D.11(17), which doesn't imply | any flexibility. Right. The current RM seems pretty clear, and it does not say what either you or I would prefer, in our present enlighted states. | The Rationale for Hold/Continue definitely | talks about using the priority equivalence to ensure that the | semantics are well defined. Also, the argument about overhead seems | a bit weak in the case where a rendezvous is already involved ;-). You may dismiss it, but there will still be some overhead on the hold and release operations even when no rendezvous is involved, just to check for whether there is a rendezvous involved. By itself this may not be much, but the cumulative effect of all such checks can be significant. (Having concluded that the async. hold cannot be implemented in any reasonable fashion over POSIX threads, I have no experience on which say authoritatively how much extra work would be involved.) | Finally, for an acceptor, it is clear that you have to recompute the | active priority for the rendezvous when the acceptor is held, so it | doesn't seem very surprising that if the caller is held, then the | priority of the rendezvous also needs to be recomputed. I don't see why you would want to recompute the active priority of the rendezvous if the acceptor is held. The acceptor can't execute, and it is not giving priority to anybody else. What does the active priority matter, until the acceptor is released again? --Ted Baker **************************************************************** !section RM-D.11(05) !subject Async Task Control while caller in rendezvous !reference RM95-D.11(5,17) !reference 95-5282.a Tucker Taft 95-9-11 !reference 95-5284.a Ted Baker 95-09-12 !referemce 95-5287.a Offer Pazy 95-09-12 !from Mike Kamrad 95-09-14 !reference as: 95-5295.a j.m.kamrad.ii 95-9-14>> !discussion My two cents worth: I side with both Ted and Offer on this issue. Historically, they are both right dropping transitive priority inheritance due to its costs and the "not-essential-when-we-have-protected-objects" argumnets. This decision is well documented in DR meetings and in ARTEWG meetings. When it comes to more real-time features, like transitive priority inheritance, versus better performance I think that you would find that most users would vote for the latter. So I would look for opportunities for flexibility to promote lightweight implementations wherever possible. I think that Offer has pinpointed the source of this problem with "During" in D.1(22) and I endorse his recommendations. >I agree that we have a problem with the word "during" in D.1(22), but it is >clear to me that if something has to change, this is the rule that needs to >change. Doing otherwise, will have *very heavy* implememetation cost and is >a big deviation from the Ada 83 rules (and is not needed). ------------------------------------ Mike Kamrad Computing Devices International kamrad@cdev.com M/S BLC W2J 1.612.921.6908 8800 Queen Avenue South FAX: 1.612.921.6165 Bloomington MN 55431 **************************************************************** !section D.1(21) !subject Priority inheritance, rendezvous and the "held" state !reference AI95-00090/00 !reference AI95-00092 !reference RM95-D.1(21) !reference RM95-D.1(22) !reference RM95-D.11(17) !from Offer pazy 95-10-11 !reference as: 95-5327.a Offer Pazy 95-10-11>> !discussion I believe that the problem described in the referenced two AIs is one and had to do with the word "during" used incorrectly in D.1. I strongly recommend against separating the case of sync vs async calls. If we leave the word "during" for sync calls, then we basically introduce transitive priority inheritance (TPI), something that we very clearly have decided against (with a lot of consensus). This will be very expensive in terms of implementations and not very useful since the TPI rules are not consistently followed (on the contrary, they are never required except of what is implied by this typo). Some explanations: If you do change the priority of the acceptor, than you may need to follow the chain of rendezvous and maybe change the priority of other acceptors. This represents an asynchronous recomputation of an active priority, again, something that we have consciously avoided. There may be an arbitrary number of queues which you will have to visit (locking them all). Also, We have given the same treatment (and hopefully a consistent one) to rendezvous and task activation, to allow users to play with agent tasks freely with the same set of rules. If you change rendezvous, you will have to do the same here. You may also run into logical races: Assume the accept body declares a task. For the accept body to complete, the task needs to finish. The priority of the task can be determined based on the activator's (the acceptor in this case) only at the time of activation. If the acceptor priority changes later, there is no way to "rush" the inside task. Finally, the Held state is defined in terms of dynamic priorities and should stayed consistent with their rules. Fixing "during" will address the (hopefully) only error in this area. Offer Pazy 31 Robinwood Ave. Boston, MA 02130 USA (617)522-5988 pazy@world.std.com **************************************************************** !section D.1(22) !subject Priority inheritance in rendezvous from async select !reference RM95-D.1 (22) !reference RM95-D.1 (21) !reference AI95-00090 !reference AI95-00092 !from Offer pazy 95-10-11 !reference as: 95-5329.a Offer Pazy 95-10-12>> !discussion I don't think that this issue should be treated as async vs sync calls. It is closely related to the general problem introduced by the word "during" in (22) *and* (21). Please look also at AI-00090 which, in my opinion, is the same issue (or closely related to it) Leaving the word "during" for the sync call case will necessitate the same kind of impl difficulty, inconsistency with no added user value. The discussion section says: > We want indirect priority inheritance to work, I don't know what "indirect priorty inheritance" means since it is not defined anywhere. But I would guess that quite on the contrary, we do *not* want to require such inheritance. Tucker says: > I believe this should say: > > During rendezvous, the task accepting the entry call inherits the > active priority of the caller while the caller is blocked on > the entry call; for a call due to an asynchronous select, it inherits > the priority that was the active priority of the caller at the time > the entry call was issued. Again, I think that it will be a mistake to solve the problem jsut for the async case, the sync case is as problematic. Offer Pazy 31 Robinwood Ave. Boston, MA 02130 USA (617)522-5988 pazy@world.std.com **************************************************************** !section 1.1(01) !subject comments on draft tasking AIs !reference AI95-00045, AI95-0059, AI95-0069, AI95-0092, AI95-00101, AI95-00103 !from Ted Baker 95-10-16 !reference 95-5342.a Ted Baker 95-10-16>> !discussion I have looked over the draft AIs related to tasking that have come across the net, and have the following comments: AI95-00045...I have not see this yet. Did I miss it? AI95-00059...looks OK AI95-00069...looks OK AI95-00090...an acceptable compromise, but I would prefer to specify less I don't think we can claim that there is one best semantic for this situation, which is both rarely occurring and potentially costly if we specify it in a way that turns out to be unnatural for a given implementation. In such situations, overspecification can be harmful. AI95-00091...looks OK AI95-00092...look OK, except for the following: Change "inherits the active priority of the entry call" to "inherits the priority of the entry call". This will make it consistent with AI95-00090. AI95-00101...looks OK AI95-00103...looks OK --Ted Baker **************************************************************** !section D.1(21) !subject Priority inheritance in rendezvous from async select !reference AI95-00090 !reference RM95-D.1(21, 22) !from Tucker Taft 95-10-30 !reference 95-5373.i Tucker Taft 95-10-30>> !discussion I believe there are three separate issues: a) Whether or not dynamic priority changes should apply transitively via priority inheritance; that is, when you change the priority of a task using Set_Priority (or via Hold), is the priority of any other task that is inheriting priority from this task indirectly affected at the same time. b) Whether a priority change in a task blocked on a queued entry call should affect the position of the call in the entry queue (presuming the Priority_Queuing policy is in effect). c) Whether a priority change in a task with a pending asynchronous entry call should have any effect on the position of the entry call in the entry queue (presuming the Priority_Queuing policy is in effect). The answers to (b) and (c) are given quite clearly in RM95 D.4(10,11). The answer to (c) is that the position in an entry queue never changes for an asynchronous call, and to (b) is that the position only changes for a synchronous call due to a direct setting of the base priority of the caller. The answer to (a) is more difficult to determine from the RM. Based on assurances from Offer, Ted, and Mike Kamrad, it seems clear to me now that there was no intent for dynamic priority changes to "ripple" through many tasks via transitive application of priority inheritance. However, paragraphs D.1(20..24) are clearly written in terms of continuous and ongoing transitive priority inheritance. Furthermore, Ted acknowledges that there are efficient implementations of priority inheritance that are inherently transitive. Given the above, it seems best to liberalize the rule, rather than to go hard over to no transitive priority inheritance. Hence I recommend that we make it implementation-defined (that is, it must be documented) whether changes to the priority of a (synchronous) caller on a task entry have any effect on the acceptor's priority, and similarly whether changes to the priority of an activator have any effect on the tasks being activated, if these changes happen after the rendezvous begins, or after activation begins. The rationale for this recommendation is that, presumably, transitive priority inheritance can have at least a modest benefit via reducing priority inversion, and we should not actively discourage implementations from providing this capability. However, by not requiring such transitive priority inheritance, we allow the implementor (presumably in consultation with the relevant customers) to tradeoff implementation burden and efficiency against the advantages of reduced priority inversion. It would certainly be unfortunate if the most efficient implementation of priority inheritance turns out to be inherently transitive, and we disallow the use of this approach because we fear it is too inefficient. In any case, to be consistent with D.4(11), it seems clear that changing the priority of an asynchronous caller of a task entry should have no effect on the acceptor, nor on the position of the entry call in the entry queue, after the entry call has been queued and the caller is off on its merry way asynchronously executing the abortable part. **************************************************************** !section D.11(05) !subject Async Task Control while caller in rendezvous !reference AI95-00092 !reference RM95-D.11(5) !from Tucker Taft 95-10-30 !reference 95-5373.j Tucker Taft 95-10-30>> !discussion It seems highly desirable that Hold and Set_Priority have consistent effects. Holding a task should be considered essentially equivalent to dropping its base priority to sub-idle, from the point of view of priority inheritance, etc. We describe it as removing the base priority as a source of inheritance because we don't want to actually affect the value returned by Get_Priority, and we want Continue to restore the original state without having the Hold-er have to remember the old base priority. This AI is stating the case for not requiring asynchronous transitive priority inheritance. However, as I argued in my comment on AI95-00090, I believe it is better at this point to allow the choice between transitive and nontranstive priority inheritance to be implementation-defined. There are efficient approaches to priority inheritance that are inherently transitive, and it would be unfortunate if we effectively outlaw their use. It also may be that existing kernels already implement one or the other approach to priority inheritance, and it seems desirable to be able to capture these efforts. It seems hard to imagine how an application could become dependent on priority inheritance being *not* asynchronously transitive, given the numerous race conditions which could mask this distinction. Hence, there seems no serious portability issue in allowing priority inheritance to be asynchronously transitive. Note that the reverse is not true -- it does seem possible for an application to become dependent on an implementation supporting asynchronous transitive priority inheritance. However, this is similar to becoming dependent on an efficient implementation. We can never prevent such portability problems. The important thing is to define a standard that allows a portable application to be built that depends on only the minimum set of guarantees, while still allowing implementations to innovate by going beyond this minimum set to achieve higher performance. -Tuck **************************************************************** !section D.11(05) !subject Priority inheritance in rendezvous from async select !reference AI95-00090 !reference AI95-00092 !reference RM95-D.11(5) !reference RM95-D.1(21, 22) !reference Ted Baker 95-10-31 !reference 95-5374.a Tucker Taft 95-10-31>> !discussion > Tucker Taft (95-10-30) argues for allowing transitive priority > inheritance for protected objects, as an implementation option. ^^^^^^^^^ ??? > This is the wrong way to do it. I didn't think I was talking about protected objects at all. I was talking about transitive priority inheritance in rendezvous and during activation. > ... > It seems Tucker is arguing we should change the whole approach of > Annex D, that the pragmas should not mean anything in particular, > i.e. so that CEILING_LOCKING somehow is allowed to really mean > priority inheritance locking. I didn't mean to be talking about protected object locking at all. As far as I can see, there is no defined policy pragma relating to priority inheritance for rendezvous and activation. > This would be really dangerous. These are semantically two > different things, with many ramifications. For example, what does > the priority ceiling of a protected object mean, if the locking > policy does not use ceilings? Is Program_Error still required to > be raised (I did not want it, but it a requirement) if the ceiling > is violated? This seems irrelevant to the discussion of priority inheritance during rendezvous and activation. > --Ted Baker -Tuck **************************************************************** !section D.11(05) !subject Priority inheritance in rendezvous from async select !reference AI95-00090 !reference AI95-00092 !reference RM95-D.11(5) !reference RM95-D.1(21, 22) !from Ted Baker 95-10-31 !reference 95-5375.a Ted Baker 95-10-31>> !discussion In general, I'm in favor of allowing implementations freedom to do the "right thing" to meet a user's requirements and to use the facilities provided by a particular COTS OS or real-time kernel. However, we need to make sure this freedom is limited to the core language and to implementation-defined extensions, rather than to the specified default real-time scheduling model and options of Annex D. I'm still concerned about Tucker's attempts to dismiss my criticisms of his arguments (95-10-31): | I didn't think I was talking about protected objects at all. | I was talking about transitive priority inheritance in rendezvous | and during activation. I apologize for jumping to conclusions, but quite a bit of the text in the message to which I was replying does not make sense except in the context of a general discussion of priority inheritance, which includes protected objects. If the intent is not to propose more asynchronously dynamic semantics for priority inheritance in general, then how should the following be interpreted? | ... I believe it is better at this point to | allow the choice between transitive and nontranstive priority | inheritance to be implementation-defined. There are efficient | approaches to priority inheritance that are inherently transitive, | and it would be unfortunate if we effectively outlaw their use. | It also may be that existing kernels already implement one or the | other approach to priority inheritance, and it seems desirable to | be able to capture these efforts. | It seems hard to imagine how an application could become dependent | on priority inheritance being *not* asynchronously transitive, given | the numerous race conditions which could mask this distinction. | Hence, there seems no serious portability issue in allowing | priority inheritance to be asynchronously transitive. | Note that the reverse is not true -- it does seem possible for | an application to become dependent on an implementation supporting | asynchronous transitive priority inheritance. However, this is | similar to becoming dependent on an efficient implementation. | We can never prevent such portability problems. The important | thing is to define a standard that allows a portable application | to be built that depends on only the minimum set of guarantees, | while still allowing implementations to innovate by going beyond | this minimum set to achieve higher performance. All this talk about "transitivity" is very confusing. What is the real issue? I guess it is that implementations should be allowed to do more dynamic and asynchronous updating of priority inheritance effects for rendezvous and task activation, but not for protected objects. I don't like this arbitrary separation into two kinds of inheritance. I also have some misgivings about potential ramifications. [ASIDE: The semantics and implementation of rendezvous (task entry calls) and protected objects (protected entry calls) are very closely connected. With dequeue, the caller of an entry cannot in general predict whether it will eventually end up as a rendezvous or a protected entry call. Thus, when one introduces a new asynchronously dynamic priority inheritance rule for service of task entry calls there will be lots of interesting ramifications. For example, what happens when a task entry call is requeued on a protected object, or vice versa? I guess the proposal is to allow the implementation to ] For discussion, let's assume from here on we are ONLY talking about priority inheritance via task entry calls and task activation. | a) Whether or not dynamic priority changes should apply transitively | via priority inheritance; that is, when you change the priority | of a task using Set_Priority (or via Hold), is the priority of | any other task that is inheriting priority from this task | indirectly affected at the same time. | b) Whether a priority change in a task blocked on a queued entry | call should affect the position of the call in the entry queue | (presuming the Priority_Queuing policy is in effect). | c) Whether a priority change in a task with a pending asynchronous | entry call should have any effect on the position of the | entry call in the entry queue (presuming the Priority_Queuing | policy is in effect). | The answers to (b) and (c) are given quite clearly in RM95 | D.4(10,11). The answer to (c) is that the position in an entry | queue never changes for an asynchronous call, and to (b) is that | the position only changes for a synchronous call due to a direct | setting of the base priority of the caller. These paragraphs apply only if Priority_Queuing is specified. The behavior may be different if the implementation supports another queuing policy. | The answer to (a) is more difficult to determine from the RM. | Based on assurances from Offer, Ted, and Mike Kamrad, it seems | clear to me now that there was no intent for dynamic priority | changes to "ripple" through many tasks via transitive | application of priority inheritance. However, paragraphs | D.1(20..24) are clearly written in terms of continuous and | ongoing transitive priority inheritance. Furthermore, Ted | acknowledges that there are efficient implementations of | priority inheritance that are inherently transitive. The above mis-quotes me and the ARM to support a position that I do not support. The cited paragraphs of the ARM use the same wording ("during") for protected actions as they do for activation and rendezvous. Tucker seems to be claiming that this choice of wording somehow implies inheritance is DYNAMICALLY transitive in the case of task activation and rendezvous. I disagree. That is only an unfortunate consequence of someone's editorial attempt to parallel style of wording. Moreover, in my earlier correspondence to which Tucker seems to refer I was presuming an implementation that uses a consistent technique for protected object locking. | Given the above, it seems best to liberalize the rule, rather | than to go hard over to no transitive priority inheritance. | Hence I recommend that we make it implementation-defined (that | is, it must be documented) whether changes to the priority of a | (synchronous) caller on a task entry have any effect on the | acceptor's priority, and similarly whether changes to the | priority of an activator have any effect on the tasks being | activated, if these changes happen after the rendezvous begins, | or after activation begins. I don't see much gain here unless you also provide dynamic transitive priority inheritance for the locks that are used to implement protected objects, and for mutual exclusion within the runtime system --- unless you "round up" the "ceiling" of all such and treat them all as one global lock. It sounds an awful lot like this all is an unfortunate ramification of the "white lie" about the asynch. hold operation having priority-change semantics. If so, could we perhaps just get by more simply by making a change that is local to D.11, rather than opening up the basic priority model? | The rationale for this recommendation is that, presumably, | transitive priority inheritance can have at least a modest ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^? | benefit via reducing priority inversion, and we should not | actively discourage implementations from providing this | capability. However, by not requiring such transitive priority ^^^^^^^^^^^^^^^^^^^ | inheritance, we allow the implementor (presumably in ^^^^^^^^^^^? | consultation with the relevant customers) to tradeoff | implementation burden and efficiency against the advantages of | reduced priority inversion. It would certainly be unfortunate | if the most efficient implementation of priority inheritance | turns out to be inherently transitive, and we disallow the use | of this approach because we fear it is too inefficient. I guess the underlined phrases are meant to mean "asynchronously dynamic transitive priority inheritance", meaning that asynchronous changes to the active priority of a task may have a transitive effect via any task-to-task inheritance relations that are in effect. | In any case, to be consistent with D.4(11), it seems clear that | changing the priority of an asynchronous caller of a task entry | should have no effect on the acceptor, nor on the position of | the entry call in the entry queue, after the entry call has been | queued and the caller is off on its merry way asynchronously | executing the abortable part. Yes. | As far as I can see, there is no defined policy pragma relating to | priority inheritance for rendezvous and activation. Right. However, ARM D.1 (29) allows an implementation to provide a non-standard mode in which tasks inherit priorities under conditions other than those specified above. I guess this means an implementation can define a new pragma for this purpose, at least. See also the dependence on Queueing_Policy on the D.4 paragraphs cited above. ****************************************************************