Version 1.2 of ais/ai-00321.txt

Unformatted version of ais/ai-00321.txt version 1.2
Other versions for file ais/ai-00321.txt

!standard D.02.01 (04)          03-01-07 AI95-00321/01
!standard D.02.01 (06)
!standard D.02.01 (08)
!standard D.02.02 (03)
!standard D.02.02 (07)
!standard D.02.02 (13)
!class amendment 03-01-07
!status work item 03-01-07
!status received 03-01-07
!priority Medium
!difficulty Medium
!subject Definition of dispatching policies
!summary
New wording is proposed for paragraphs within D.2.1 and D.2.2 to remove a problem and to enable further dispatching policies to be added to Annex D.
!problem
As it is currently worded the general model for dispatching (as defined in D.2.1) does not define the required behaviour. Specifically the current running task is not considered as a candidate for the next running task as it is not on a ready queue. Rewording of D.2.1 (6) is necessary. In addition, some of the specific rules necessary for defining the FIFO_Within_Priority policy in D.2.2 are, unnecessarily, given in Section D.2.1 where only the general dispatching policy should be defined. This makes it difficult to specify other policies within the annex (for example, non-preemptive dispatching).
!proposal
Some wording changes are proposed for the annex. Those deal with the problems defined above. Wording changes are also proposed to facilitate the definition of other dispatching policies in the Annex.
!wording
Remove 'the completion of an accept_statement (see 9.5.2),' from D.2.1(4).
Replace D.2.1(6) last sentence with: If the current running task has a priority greater or equal to the task at the head of the highest priority non-empty ready queue it continues to be the running task; otherwise the task at the head of the highest priority non-empty ready queue is selected, this task is then removed from all ready queues to which it belongs.
Replace D.2.1(8) with: A task reaches a task dispatching point whenever the task dispatching policy requires a running task to go back to a ready queue.
Replace D.2.2(3) with: The policy-identifier shall be FIFO_Within_Priority, an alternative policy from D.14 or an implementation-defined identifier.
Replace D.2.2 (7): When FIFO_Within_Priorities is in effect, modifications to the ready queues occur only as follows.
Add after D.2.2(13): A new running task is selected whenever there is a non-empty ready queue with a higher priority than the priority of the running task. This is also a task dispatching point for this policy.
!discussion
The inclusion of 'completion of an accept_statement (see 9.5.2),' in D.2.1(4) does not seem to be justified. It is not the only case in which a task changes priority and/or unblocks another task. It has not been moved to D.2.2 as the overriding rule of higher priority task always preempting covers this and all similar cases.
!example
An example does not seem valuable for this proposal.
!ACATS test
!appendix

From: Randy Brukardt
Sent: Wednesday, January 15, 2003  6:55 PM

Alan:

A comment on "AINew", which I've assigned number AI-321.

The current D.2.1(6) says:

"Each processor also has one running task, which is the task currently being
executed by that processor. Whenever a task running on a processor reaches a
task dispatching point, one task is selected to run on that processor. The
task selected is the one at the head of the highest priority nonempty ready
queue; this task is then removed from all ready queues to which it belongs."

This text implies round-robin scheduling at task dispatching points.

The new AI, however, is written assuming that run-until blocked scheduling
is used. For instance, the new D.2.1(6) says:

"If the current running task has a priority greater or equal to the task at the
head of the highest priority non-empty ready queue it continues to be the
running task; otherwise the task at the head of the highest priority non-empty
ready queue is selected, this task is then removed from all ready queues to
which it belongs."

Moreover, the justification for removing "the end of an accept statement" as
an explicit task dispatching point is "It is not the only case in which a
task changes priority and/or unblocks another task. It has not been moved to
D.2.2 as the overriding rule of higher priority task always preempting
covers this and all similar cases." Clearly, however, it does have an effect
if the scheduling is round-robin within the current priority.

My own understanding has been that the dispatching policy within a priority
is not specified. That's necessary if Ada is to run on standard operating
systems, which typically use some sort of time slicing for threads of the
same priority. Saying that compilers for such targets are not Annex D
compliant (or forcing the use of impractical modes to make them compliant,
such as the version of GNAT that had to run as root) is not helpful.

In any case, this wording is supposed to be inclusive, not exclusive -- it
is defining the general task dispatching policy, not any specific one. To
write the wording such that a round-robin or time-slicing policy is wrong
(as an implementation of FIFO_within_priorities) is just not going to fly --
it would be very incompatible with existing practice.

As a practical matter, we've decided that we have to allow validation for
Annex D when running on operating systems like Windows and VxWorks which do
not exactly meet the letter of rules for task dispatching and queuing. That
because Ada is not in a position of strength here; we cannot say that Ada is
incompatible with Windows, since that simply will cause people to abandon
Ada, not Windows. We should not add more rules that are impossible to
implement on popular platforms.

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

From: Alan Burns
Sent: Thursday, January 16, 2003  11:55 AM

Some points arising from Randy's note on new AI - AI-321

My motivation is to remove rules from D.2.1 not add some; hence
new D.2.2 has the strong rules for FIFO_Within_Priority, and
other policies can be defined.

I did not realise that current D.2.1(6) implies round-robin scheduling.
First, I don't think it does (see next point). But D.2.1 should
not imply any scheme (and should not disallow either I agree). I have
attempted to remove the non-essential dispatching points so that
D.2.1 only has the rules that must apply for all Ada programs.

As the AI says, D.2.1(6) is broken; strictly it requires a lower
priority task to take over a higher one at a task dispatching point
if there is no other task at the higher level (as the current
running task is not on a ready queue). No implementation (on
whatever OS) should do this.

The need to allow round robin implementation is facilitates by:

>Replace D.2.1(8) with:
>A task reaches a task dispatching point whenever the task
>dispatching policy requires a running task to go back to a ready queue.

An implementation's `policy' can send a task to the back of
it's ready queue whenever it wishes.

There will actually be a specific round_robin dispatching policy coming
forward for consideration by ARG soon!

I have not assumed run-until blocked scheduling, because of above, but
"If the current running task has a priority greater or equal to
the task at the head of the highest priority non-empty ready queue .."
could have `or equal' removed if that would help (although other
changes would have to be made)

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

From: Ted Baker
Sent: Thursday, January 16, 2003  2:58 PM

You are misreading the current wording of D.2.1.
The words you quoted below were taken, nearly verbatim,
from the POSIX realtime scheduling standard.  They do *not*
imply round-robin scheduling.

Yes, the running task is nominally removed from the ready queue(s)
while it runs, and then put back onto the ready queue whenever
it is not running.

However, when it is put back onto the ready queue there is no
requirement that it be put back into the queue in round-robin
fashion.  Depending on the dispatching policy, the task may be
placed into the ready queue at the head, that the tail, or
any other place the policy dictates.

Please do not "fix" something that is not broken.  If you do,
you will actually break it.

All of the words in the real-time annex that address scheduling
were written are based on the above model, as is the POSIX model.
If you start changing the model you will have many unintended
consequences, and end up not being compatible with systems that
use POSIX threads.

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

From: Randy Brukardt
Sent: Thursday, January 16, 2003  3:19 PM

> ...
> Please do not "fix" something that is not broken.  If you do,
> you will actually break it.

*I* don't want to "fix" this; I want to make sure that needed corrections don't
accidentally make existing scheduling wrong.

Alan has proposed the changes in AI-321 for two reasons:
  -- To allow non-premptive scheduling policies (which isn't allowed by the
     current D.2.1);
  -- To fix the wording glitch which does not allow the running task to
     continue at a task dispatching point. (And I certainly agree with Alan
     that that is what the current wording says). It's unlikely that many, if
     any, implementations actually do this.

All of which he explains in the AI that he sent last week.

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

From: Robert Dewar
Sent: Friday, January 17, 2003  9:40 PM

> I did not realise that current D.2.1(6) implies round-robin scheduling.
> First, I don't think it does (see next point). But D.2.1 should
> not imply any scheme (and should not disallow either I agree). I have
> attempted to remove the non-essential dispatching points so that
> D.2.1 only has the rules that must apply for all Ada programs.

While we are at it, should we be so inflexible for the default dispatching
priority. It is somewhat annoying that you have to have a switch to change
the default behavior of the OS (e.g. in Windows) to ensure absolute priorities.

yes, you can take the viewpoint that Annex D is optional, but in fact all
the priority stuff maps fine into the default Windows behavior. I am not
sure we need to be so specific on the default dispatching method.

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

From: Robert Dewar
Sent: Sunday, January 19, 2003  7:23 AM

> > As a practical matter, we've decided that we have to allow validation for
> > Annex D when running on operating systems like Windows and VxWorks which do
> > not exactly meet the letter of rules for task dispatching and queuing. That
> > because Ada is not in a position of strength here; we cannot say that Ada is
> > incompatible with Windows, since that simply will cause people to abandon
> > Ada, not Windows. We should not add more rules that are impossible to
> > implement on popular platforms.

What does this mean exactly? That you are allowed to fail existing ACATS
tests on such targets? If so, I object. Certainly it is possible to pass
all existing Annex D tests on Windows. On the other hand, it would certainly
be possible to strengthen the tests so that this was not the case (e.g.
really strenuously test that there are 32 independent priority levels).

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

From: Randy Brukardt
Sent: Wednesday, January 22, 2003  6:33 PM

It means that the situation I inherited is unchanged: there are no "gold
stars" for annex validation, you usually cannot fail a validation because of
a failure in an annex, the grade can be "unsupported" rather than "failed"
for annex tests (although you have to get permission). Of course, vendors
can omit testing for any annex (as a whole), and most do.

That was decided before I took over conformity assessment, and certainly I
haven't changed it (or wanted to re-argue it, for that matter). There
certainly are implementations whose test reports show "unsupported" tests in
the various annexes where the tests were run. These are test failures, in
general. I don't believe that we've ever denied a petition for an
unsupported grade (I know we've discussed some of these on the FRT list).

        Randy Brukardt
        ACAA Technical Agent.

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

From: Dan Eilers
Sent: Wednesday, January 22, 2003  7:05 PM

I don't wish to re-argue this policy either, but I would point out that
it seems inconsistent with ISO/IEC 18009 section 8.2.1.1 which states
that Ada defines Specialized Needs Annexes to which a processor may
conform individually, and Ada conformity testing shall assess conformity
to these individual Specialized Needs Annexes.

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

From: Randy Brukardt
Sent: Wednesday, January 22, 2003  7:55 PM

Nothing in ISO/IEC 18009 defines how test grades are determined, or precisely
what a pass or fail situation is. That's left to the ACAP and ACATS. And
certainly, by running the tests, an ACAL is assessing conformity. So I don't
see any inconsistency here.

P.S. This is a bit off topic here; it would be better discussed on the ACAA
mailing list.

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

From: Robert Dewar
Sent: Wednesday, January 22, 2003  8:46 PM

> That was decided before I took over conformity assessment, and certainly I
> haven't changed it (or wanted to re-argue it, for that matter). There
> certainly are implementations whose test reports show "unsupported" tests in
> the various annexes where the tests were run. These are test failures, in
> general. I don't believe that we've ever denied a petition for an
> unsupported grade (I know we've discussed some of these on the FRT list).

I really think it is bad to consider a failed test to be a matter of
lack of support. We considered this during the language design, and agreed
that there was definitely not a license to do arbitrary wrong things when
trying to run annex tests.

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

From: Randy Brukardt
Sent: Wednesday, January 22, 2003  8:56 PM

It's done on a case-by-case basis, of course, so the implementor has to have
some rationale for it. But, as I said, I believe we've granted every request
that has been made. (And by "we", I mean the FRT, not me alone.)

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

From: Robert Dewar
Sent: Wednesday, January 22, 2003  9:02 PM

OK, that's fine, that means that implementors have been reasonable, which is
what you would expect. I thought you were stating this as a policy which
would be something else entirely.

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

From: Robert Dewar
Sent: Sunday, January 19, 2003  7:27 AM

> Alan has proposed the changes in AI-321 for two reasons:
>   -- To allow non-premptive scheduling policies (which isn't allowed by the
> current D.2.1);

I think this change is important, it really seems for example that we
should be able to allow the default scheduling policy of Win XP as an
*optional* scheduling policy without considering that we are violating
annex D. Right now with GNAT, we have to run the whole test suite with
a switch that sets FIFO_Within_Priorities, which works fine, but means
that the validation is less useful, since it is forced to run with a
rather peculiar non-standard switch. Of course we pass all the tests
that have the explicit pragma Dispatching_Policy, that's not the
issue, the issue is that there are tests without this pragma that
still require strict adherence to the premptive priority model of
Annex D.

>   -- To fix the wording glitch which does not allow the running task to
> continue at a task dispatching point. (And I certainly agree with Alan that
> that is what the current wording says). It's unlikely that many, if any,
> implementations actually do this.

Well that of course is just a typographical error (it obviously is not
intended, and a compiler that felt bound by this wording error would
be just as incorrect as an original Ada 83 compiler that thought that
all subtypes were non-static due to a wording error).

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


Questions? Ask the ACAA Technical Agent