Version 1.6 of ais/ai-00092.txt

Unformatted version of ais/ai-00092.txt version 1.6
Other versions for file ais/ai-00092.txt

!standard RM-D.11 (05) 99-09-15 AI95-00092/08
!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

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 difficulty 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)

Replace the paragraph:

During activation, a task being activated inherits the active priority of the its activator (see 9.2).

by:

During activation, a task being activated inherits the active priority that its activator (see 9.2) had at the time the activation was initiated.

!corrigendum D.01(22)

Replace the paragraph:

During rendezvous, the task accepting the entry call inherits the active priority of the caller (see 9.5.3).

by:

During rendezvous, the task accepting the entry call inherits the priority of the entry call (see 9.5.3 and D.4).

!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.


****************************************************************

Questions? Ask the ACAA Technical Agent