!standard D.5      (10)                             04-11-08  AI95-00188-02/01
!class binding interpretation 04-11-08
!status work item 04-11-08
!status received 04-11-08
!priority Medium
!difficulty Medium
!subject Setting a task base priority is immediate

!summary

Setting a task's base priority becomes immediate, but the
reordering of entry queues is allowed to be deferred.

!question

Must the setting of a task base priority happen
"immediately" on a monoprocessor, in analogy with the
requirements for preemptive abort?

!recommendation

Rather than allow an implementation to change the priority of a task
"as soon as practical", the change is required to be immediate, but the
reordering of entry queues is allowed to be deferred. This deals with the
problem of entry queues and layered run-time kernels, but requires an immediate
change if the task is on a ready queue or the delay queue.

!wording

Replace D.5(10) with
Setting the task's base priority to the new value takes place immediately
unless the task is performing a protected action in which case it is postponed
until the protected action is completed.

Add new paragraph to D.4(15) under Implementation Permissions:
Implementations are allowed to defer the reordering of entry queues following
a change of base priority of a task blocked on the entry call if it is not
practical to reorder the queue immediately.

AARM Note:
The reordering should occur as soon
as the blocked task can itself perform the reinsertion into the entry queue.

!discussion

The questioner was expecting a response along the lines of:

  There seems no reason that the timing requirements for changing a task's
  priority and aborting a task on a single processor should differ
  significantly.  Hence, the term "immediately" should be used in the
  definition of when a task's base priority is changed on a single
  processor, once the task is outside a protected action.

  In particular, there seems no justification to allow real-time
  implementations to defer the change of base priority until the task
  wakes up on its own at its old priority, because the purpose
  of raising its priority may very well be to have the target
  task "immediately" preempt some intermediate priority task.

However, there is some justification for the difference. The difference is that
"completing" a construct is not the same as "exiting" the construct, and
priority change is closer to exiting, since it has a big nasty side-effect --
namely, removal and re-insertion of queued entry calls -- that may require
waiting for the caller-task to execute. This makes if difficult to implement
on a multi-threaded (multi-lock) run-time kernel, or on a layered (non-Ada)
kernel.

From an implementation point of view, we can have some other task
mark a given task as having "completed" a construct, but to
actually execute the finalization code and leave the construct we
need to wait for the affected task to run.

By analogy, here we can change the priority of a task, but if
we want the task's entry calls to be repositioned, we have to
wait until the task can be scheduled.

The abort statement is defined in the core language and the IRTAW
was concerned that a 'valid' implementation could postpone the effect
of abort indefinitely - hence the use of "immediate" in the Real-Time
Annex. By contrast, the dynamic priorities package is a Annex D facility
and hence it was be assumed that the implementation does the right thing,
and that "as soon as practical" is strong enough. However there is evidence
that implementations not only postpone the change of priority for a task
on an entry queue but also for those on ready queues and the delay queue.
This does undermine the fundamental purpose of changing another task's
priority; and hence some tightening of the language definition is justified.

!appendix

The discussion in the other alternative of this AI illustrates why entry
queues are problematic.

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

From: Alan Burns
Sent: Monday, November 8, 2004  4:41 AM

Following my suggestion, ARG voted AI-188 (Immediacy of Set_Priority) as
'reconfirmation' of existing ARM words/model.

I am sorry but I would like to reopen this AI. I attach a new version. (This is
AI-188-02/01 - ED)

The basic issue is that the change of a task's base priority is currently
defined to be 'as soon as is practical'. Ted Baker argues strongly for this as
the  need to reorder entry queues following a change in priority is very
difficult to achieve on either a mutli-lock kernel or when an Ada run-time is
layered on top of a RTOS.

Recently (since the ARG vote) I've looked at a number of implementations and
the 'as soon as is practical' is interpreted to mean, never bother to do it
immediately, just mark the task so that when it next executes it changes
its own priority. This makes the Set_Priority feature useless.

I've discussed this at length with Ted. He agrees that the priority change
can/should be immediate if the task is on a ready queue or on the delay queue.
His concern is entry queues.

We would now wish to propose the following:

1. priority changes are immediate
2. entry queue reordering is allowed to be deferred.

This proposal is in the new version of the AI.

My apologies for not understanding this issue properly earlier.

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

From: Robert A. Duff
Sent: Tuesday, November 9, 2004 11:59 AM

I don't understand the implementation issue.  I understand that a
run-time system layered on top of some threads implementation presents
the same issues as a "true" multiprocessor, assuming the threads support
doesn't provide primitives to "immediately" notify the target task.
But I don't understand why the issue is different for aborts than for
priority changes.  Why, for example, does the priority changing section
not include the wording about polling that appears in the abort section
(RM-D.6(10))?

It has been pointed out that the RM doesn't define "multiprocessor".  In
fact, it can't, really.  Modern chips make this even more confusing than
when Ada 95 first came out.  We bought a computer in the last year that
appears to have 3.5 CPUs.  ;-)

But it seems confusing (to non-language lawyers) to rely on that by
pretending that an underlying threads implementation is a "virtual"
multiprocessor.  If we want to exempt such systems from the rules, we
ought to say something like "multiprocessor or underlying multi-threaded
system".  That's equally undefined, but at least programmers can
understand the intent.

Alan wrote:

> !proposal
>
> Rather than allow an implementation to change the priority of a task
> "as soon as practical", the change is required to be immediate, but
> the reordering of entry queues is allowed to be deferred. This deals
> with the problem of entry queues and layered run-time kernels, but
> requires an immediate change if the task is on a ready queue or the
> delay queue.

Hmm.  It seems like the wording below also requires an immediate change
if the task is running, and not on any queues.  Isn't that precisely the
difficult-to-implement case (on multi-processors and layered run-time
systems) that Ted was worrying about?

Also, a task can be on entry queues and also running or ready (ATC).
I don't see how the fact that it's on some ready queue makes the
entry-queue reordering easier.

Also, a task can be on an entry queue and the delay queue (timed entry
call).  Same question.

What exactly is the new wording trying to accomplish?

> !wording
>
> Replace D.5(10) with
> Setting the task's base priority to the new value takes place
> immediately unless the task is performing a protected action in which
> case it is postponed until the protected action is completed.

What does "takes place" mean, here?  I would think it means that the
task has to start running (immediately) if the new priority makes that
appropriate.  But if it can start running immediately, why can't it
start doing the queue reordering (immediately)?

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