Version 1.9 of ai05s/ai05-0166-1.txt
!standard D.2.1(1.2/2) 10-06-07 AI05-0166-1/07
!standard D.2.1(6/2)
!standard D.2.4(2/2)
!standard D.2.4(9/2)
!class Amendment 09-10-22
!status Amendment 2012 10-04-05
!status WG9 Approved 10-06-18
!status ARG Approved 9-0-2 10-02-26
!status work item 09-10-22
!status received 09-10-22
!priority Medium
!difficulty Easy
!subject Yield for non-preemptive dispatching
!summary
A support package for non-preemptive dispatching is introduced that
allows a task to offer to be preempted by a higher priority task,
but not by one of equal priority. A further 'yield' procedure is
included to improve the readability and maintainability of programs.
It replaces the current need to include 'delay 0.0' to force a
preemption.
!problem
With non-preemptive dispatching the only current non-blocking
dispatching point is a non-blocking delay_statement. We need another
kind so that a task in a system scheduled by non-preemptive dispatching
can indicate that it is prepared to be preempted by tasks of higher
priority but not by those of equal priority.
!proposal
Add to package Ada.Dispatching:
procedure Yield;
--
--
Add the following library package:
package Ada.Dispatching.Non_Preemptive is
pragma Preelaborate(Non_Preemptive);
procedure Yield_To_Higher;
procedure Yield_To_Same_Or_Higher renames Yield;
end Ada.Dispatching.Non_Preemptive;
With non-preemptive dispatching the only current non-blocking
dispatching point is a non-blocking delay_statement - D.2.4(9/2).
With this new package a call to Yield_To_Higher will
cause a task switch if there is a runnable task with an active
priority higher than the calling task's active priority. Note this
can be called from within a protected object.
To program cooperative scheduling a task explicitly includes the
points at which it is able to be preempted. It does this by using
either 'delay 0.0' or 'delay until Ada.Real_Time.Time_First' (the
latter being the one available with Ravenscar). As these statements
are not actually concerned with delaying the task they are potentially
misleading (to the human reader/maintainer of the code). The procedure
Yield is equivalent to these delay statements; and would therefore
cause the same bounded error if called from within a protected
action.
!wording
Modify package Ada.Dispatching (D.2.1(1.2/2)):
package Ada.Dispatching is
pragma {Preelaborate}[Pure](Dispatching);{
procedure Yield;
} Dispatching_Policy_Error : exception;
end Ada.Dispatching;
Add after D.2.1(6/2):
A call of Yield is a task dispatching point. Yield is a potentially blocking
operation (see 9.5.1).
Add after D.2.4(2/2):
The following language-defined library package exists:
package Ada.Dispatching.Non_Preemptive is
pragma Preelaborate(Non_Preemptive);
procedure Yield_To_Higher;
procedure Yield_To_Same_Or_Higher renames Yield;
end Ada.Dispatching.Non_Preemptive;
A call of Yield_To_Higher is a task dispatching point for this policy. If the
task at the head of the highest priority ready queue has a higher active
priority than the calling task then the calling task is preempted.
AARM Ramification: For language-defined policies other than Non_Preemptive, a
higher priority task should never be on a ready queue while a lower priority
task is executed. Thus, for such policies, Yield_To_Higher does nothing.
Yield_To_Higher is not a potentially blocking operation; it can be used during
a protected operation. That is allowed as any task with a higher priority than
the protected operation cannot call the operation (that would violate the ceiling
locking policy). An implementation-defined locking policy may need to define
the semantics of Yield_To_Higher differently.
End Ramification.
Replace D.2.4(9/2):
For this policy, blocking or termination of a task, a delay_statement,
a call to Yield_To_Higher, and a call to Yield_To_Same_Or_Higher or
Yield are the only task dispatching points (see D.2.1).
!discussion
This AI was raised by an industrial user of non-preemptive scheduling,
and was discussed and endorsed by the 14th IRTAW. Details are
contained in the workshop paper: Providing Additional Real-Time
Capability and Flexibility for Ada 2005, by Rod White.
Since Yield has a side-effect, it is inappropriate to have it in a Pure
package (the optimization rules for Pure packages would allow calls to it
to be omitted, which would be bad). Thus we change the categorization of
Ada.Dispatching to Preelaborate. This is potentially incompatible, but
since the exception (the only preexisting contents of the package) is
only raised by operations defined in "normal" (not Pure or Preelaborated)
packages, it is unlikely to occur in practice.
!example
A task that iterates through an algorithm, but offers to be preempted
by a higher priority task after each iteration would take the form:
with Ada.Dispatching.Non_Preemptive;
...
task Iterator;
task body Iterator is
...
Improving : boolean := True;
begin
...
while Improving loop
--
--
Ada.Dispatching.Non_Preemptive.Yield_To_Higher;
end loop;
...
end Iterator;
!corrigendum D.2.1(1.2/2)
Replace the paragraph:
package Ada.Dispatching is
pragma Pure(Dispatching);
Dispatching_Policy_Error : exception;
end Ada.Dispatching;
by:
package Ada.Dispatching is
pragma Preelaborate(Dispatching);
procedure Yield;
Dispatching_Policy_Error : exception;
end Ada.Dispatching;
!corrigendum D.2.1(6/2)
Insert after the paragraph:
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 it goes back to one or more ready queues; a task (possibly the
same task) is then 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.
the new paragraph:
A call of Yield is a task dispatching point. Yield is a potentially blocking operation
(see 9.5.1).
!corrigendum D.2.4(2/2)
Insert after the paragraph:
The policy_identifier Non_Preemptive_FIFO_Within_Priorities is a task
dispatching policy.
the new paragraphs:
The following language-defined library package exists:
package Ada.Dispatching.Non_Preemptive is
pragma Preelaborate(Non_Preemptive);
procedure Yield_To_Higher;
procedure Yield_To_Same_Or_Higher renames Yield;
end Ada.Dispatching.Non_Preemptive;
A call of Yield_To_Higher is a task dispatching point for this policy. If the
task at the head of the highest priority ready queue has a higher active
priority than the calling task then the calling task is preempted.
!corrigendum D.2.4(9/2)
Replace the paragraph:
For this policy, a non-blocking delay_statement is the only non-blocking event
that is a task dispatching point (see D.2.1).
by:
For this policy, blocking or termination of a task, a delay_statement,
a call to Yield_To_Higher, and a call to Yield_To_Same_Or_Higher or
Yield are the only task dispatching points (see D.2.1).
!ACATS test
Add an ACATS C-Test of this package.
!appendix
From: Randy Brukardt
Sent: Monday, April 5, 2010 11:44 AM
In AI05-0166-1 (which defines Yield and Yield_to_Higher), we added a bullet to
9.5.1 (in the list of potentially blocking operations):
* a call to Ada.Dispatching.Yield;
But this is weird. First, it doesn't include
Ada.Dispatching.Non_Preemptive.Yield_to_Higher, which surely can be blocking
(for a non-preemptive policy, at least).
Second, it is handled differently than all other language-defined subprograms.
9.5.1(18) says that language-defined subprograms are not potentially blocking
unless they "are identified where they are defined" (or are a file I/O routine,
not relevant here). So, by including Ada.Dispatching.Yield in this list and *not*
identifying it where defined, we have a contradiction.
Compare how Yield is defined to how Suspend_Until_True is defined: D.10(10) says
specifically that it is a "potentially blocking operation".
So I think those words need to be added after the other changes for Yield and
Yield_to_Higher: "Yield is a potentially blocking operation (see 9.5.1)." and
the same for Yield_to_Higher. And the bullet added to 9.5.1 should be dropped.
Do we have to reopen the AI to do this, or just have the editor make the needed
changes??
****************************************************************
From: Randy Brukardt
Sent: Monday, April 5, 2010 11:59 AM
I see another oddity. The definition of Yield in D.2.1:
"A call of Yield is a task dispatching point (see D.2.1). It is a bounded error
to call Yield from within a protected action."
First, a cross-reference to the same clause is bogus. Second, saying something is a
bounded error without any definition of the bounds is garbage. Besides, the definition
of this as a potentially blocking operation (however that is done, preferably the way
the Ada 9X team intended as outlined previously) has the right effect. So there should
be a period after "point" and the rest should be dropped. (With the additional wording
as noted previously added after.)
P.S. John would prefer to say that there should be a point after "point", which sounds
like the department of redundancy dept.
****************************************************************
From: Randy Brukardt
Sent: Monday, April 5, 2010 12:28 PM
Apparently, we didn't look very carefully at this wording.
The new wording for D.2.4(9/2) says:
For this policy, a non-blocking @fa<delay_statement>, a call to Yield_To_Higher and a
call to Yield_To_Same_Or_Higher or Yield are the only non-blocking events that are task
dispatching points (see D.2.1).
This doesn't make much sense, since a call to Yield, et. al. can be a blocking operation
(and clearly need to be "potentially blocking operations"). Since it explicitly mentions
"non-blocking" for a delay statement, maybe it ought to mention "non-blocking" for the
other two as well.
But really the entire statement is bogus. No one cares about "non-blocking" anything,
because by definition it didn't block. It's only interesting if the task dispatching point
changes the running task, and in that case the task is blocked (stops running). So this
isn't helpful, and there is no AARM note to explain what it is talking about.
I'm sure I've forgotten what this is about, but the fact that that is possible is really
bad.
****************************************************************
From: Bob Duff
Sent: Tuesday, April 6, 2010 10:43 AM
> Do we have to reopen the AI to do this, or just have the editor make
> the needed changes??
OK with me for the editor to do it.
There's no change in intent here.
****************************************************************
From: John Barnes
Sent: Wednesday, April 7, 2010 5:18 AM
> P.S. John would prefer to say that there should be a point after
> "point", which sounds like the department of redundancy dept.
John would see no point in saying that there should be a point after "point".
It should be a stop.
But after a period such discussion seems pointless so we should stop.
****************************************************************
From: Alan Burns
Sent: Wednesday, April 14, 2010 4:15 AM
> Apparently, we didn't look very carefully at this wording.
This certainly seems to be true! There are a number of points in the three
emails you sent Randy, all but one I agree with:
> In AI05-0166-1 (which defines Yield and Yield_to_Higher), we added a
> bullet to 9.5.1 (in the list of potentially blocking operations):
>
> * a call to Ada.Dispatching.Yield;
>
> But this is weird. First, it doesn't include
> Ada.Dispatching.Non_Preemptive.Yield_to_Higher, which surely can be
> blocking (for a non-preemptive policy, at least).
>
> Second, it is handled differently than all other language-defined
> subprograms. 9.5.1(18) says that language-defined subprograms are not
> potentially blocking unless they "are identified where they are
> defined" (or are a file I/O routine, not relevant here). So, by
> including Ada.Dispatching.Yield in this list and *not* identifying it
> where defined, we have a contradiction.
>
> Compare how Yield is defined to how Suspend_Until_True is defined:
> D.10(10) says specifically that it is a "potentially blocking operation".
>
> So I think those words need to be added after the other changes for
> Yield and Yield_to_Higher: "Yield is a potentially blocking operation
> (see 9.5.1)." and the same for Yield_to_Higher. And the bullet added
> to 9.5.1 should be dropped.
First for Yield - I agree that the fact that it is a potentially blocking
operation should be stated where it is defined. And if that is done then there
is no need to add to 9.5.1.
But Yield_to_Higher is not, in the sense of 9.5.1, a potentially blocking
operation. Yes it could lead to dispatching but it cannot cause any problems to
a PO. If there is a task with a strictly higher active priority (and the system
switches to that task) then this task will not call the PO (ceiling violation).
So a call to Yield_to_Higher from within a PO is just the same (in a preemptive
world) as switching to a higher priority task that become runnable while the PO
is being executed.
> I see another oddity. The definition of Yield in D.2.1:
>
> "A call of Yield is a task dispatching point (see D.2.1). It is a
> bounded error to call Yield from within a protected action."
>
> First, a cross-reference to the same clause is bogus. Second, saying
> something is a bounded error without any definition of the bounds is
> garbage. Besides, the definition of this as a potentially blocking
> operation (however that is done, preferably the way the Ada 9X team
> intended as outlined previously) has the right effect. So there should
> be a period after "point" and the rest should be dropped. (With the
> additional wording as noted previously added after.)
Agree this should just say 'A call of Yield is a task dispatching point.'
> The new wording for D.2.4(9/2) says:
>
> For this policy, a non-blocking @fa<delay_statement>, a call to
> Yield_To_Higher and a call to Yield_To_Same_Or_Higher or Yield are the
> only non-blocking events that are task dispatching points (see D.2.1).
>
> This doesn't make much sense, since a call to Yield, et. al. can be a
> blocking operation (and clearly need to be "potentially blocking
> operations"). Since it explicitly mentions "non-blocking" for a delay
> statement, maybe it ought to mention "non-blocking" for the other two
> as well.
>
> But really the entire statement is bogus. No one cares about "non-blocking"
> anything, because by definition it didn't block. It's only interesting
> if the task dispatching point changes the running task, and in that
> case the task is blocked (stops running). So this isn't helpful, and
> there is no AARM note to explain what it is talking about.
Agree this should say:
For this policy, a non-blocking @fa<delay_statement>, a call to Yield_To_Higher
and a call to Yield_To_Same_Or_Higher or Yield are the only task dispatching
points (see D.2.1).
****************************************************************
From: Randy Brukardt
Sent: Tuesday, April 20, 2010 6:01 PM
> This certainly seems to be true! There are a number of points in the
> three emails you sent Randy, all but one I agree with:
Thanks for straightening out my confusion.
...
> > So I think those words need to be added after the other changes for
> > Yield and Yield_to_Higher: "Yield is a potentially blocking
> > operation (see 9.5.1)." and the same for Yield_to_Higher. And the
> > bullet added to 9.5.1 should be dropped.
> >
> First for Yield - I agree that the fact that it is a potentially
> blocking operation should be stated where it is defined. And if that
> is done then there is no need to add to 9.5.1.
>
> But Yield_to_Higher is not, in the sense of 9.5.1, a potentially
> blocking operation. Yes it could lead to dispatching but it cannot
> cause any problems to a PO. If there is a task with a strictly higher
> active priority (and the system switches to that task) then this task
> will not call the PO (ceiling violation). So a call to Yield_to_Higher
> from within a PO is just the same (in a preemptive
> world) as switching to a higher priority task that become runnable
> while the PO is being executed.
OK, I've added a Ramification that this is *not* a potentially blocking
operation. I worry a bit whether this would be true for other locking policies
than ceiling locking, but I suppose since those aren't defined by the language
it's impossible to reason about them.
...
> > The new wording for D.2.4(9/2) says:
> >
> > For this policy, a non-blocking @fa<delay_statement>, a call to
> > Yield_To_Higher and a call to Yield_To_Same_Or_Higher or Yield are
> > the only non-blocking events that are task dispatching points (see D.2.1).
> >
> > This doesn't make much sense, since a call to Yield, et. al. can be
> > a blocking operation (and clearly need to be "potentially blocking
> > operations"). Since it explicitly mentions "non-blocking" for a
> > delay statement, maybe it ought to mention "non-blocking" for the
> > other two as well.
> >
> > But really the entire statement is bogus. No one cares about "non-blocking"
> > anything, because by definition it didn't block. It's only
> > interesting if the task dispatching point changes the running task,
> > and in that case the task is blocked (stops running). So this isn't
> > helpful, and there is no AARM note to explain what it is talking about.
>
> Agree this should say:
>
> For this policy, a non-blocking @fa<delay_statement>, a call to
> Yield_To_Higher and a call to Yield_To_Same_Or_Higher or Yield are the
> only task dispatching points (see D.2.1).
I don't think this works. I was confused about the meaning of "blocking" vs.
"ready but not running". (The Janus/Ada runtime treats these as the same thing -
a task is either running or blocked on some queue, but clearly the language does
not.)
D.2.1(4/2) says that anytime a task is blocked is a task dispatching point, and
surely we mean that to be true for the non-premptive policy. Your proposed wording
seems to say otherwise. I think we either need to stay closer to the original
wording:
For this policy, a non-blocking @fa<delay_statement>, a non-blocking call to
Yield_To_Higher, and a non-blocking call to Yield_To_Same_Or_Higher or Yield
are the only non-blocking events that are task dispatching points (see D.2.1).
or simplify by listing everything:
For this policy, blocking or termination of a task, a @fa<delay_statement>,
a call to Yield_To_Higher and a call to Yield_To_Same_Or_Higher or
Yield are the only task dispatching points (see D.2.1).
AARM Ramification: The last three items are task dispatching points even if non-blocking.
The latter wording isn't quite as clearly talking about non-blocking cases,
which seems to be the point of the paragraph, so I suspect that the first wording is
better.
****************************************************************
From: Alan Burns
Sent: Thursday, April 22, 2010 4:24 AM
...
> D.2.1(4/2) says that anytime a task is blocked is a task dispatching
> point, and surely we mean that to be true for the non-premptive
> policy. Your proposed wording seems to say otherwise. I think we
> either need to stay closer to the original wording:
>
> For this policy, a non-blocking @fa<delay_statement>, a non-blocking call to
> Yield_To_Higher, and a non-blocking call to Yield_To_Same_Or_Higher or Yield
> are the only non-blocking events that are task dispatching points (see D.2.1).
>
> or simplify by listing everything:
>
> For this policy, blocking or termination of a task, a @fa<delay_statement>,
> a call to Yield_To_Higher and a call to Yield_To_Same_Or_Higher or
> Yield are the only task dispatching points (see D.2.1).
I would prefer this. The current wording makes a point about a 'non-blocking' delay statement.
I guess this was to emphasis that 'delay 0;' is a dispatching point. Of course any blocking
delay statement is a task dispatching point. Hence it follows that the a 'delay_statement' is
a task dispatching point. I was asked to remove 'non-blocking call the Yield_To_Higher' etc
as they are not really blocking in the sense that a delay statement in blocking. Being
blocked is not the same as being preempted - blocking usually means that the task can not
make progress until some change to the system (such as a PO becoming free) or
until the 'time is right'. Preemption is just waiting one turn. If the high priority task
did not exist (or on a multiprocessor was executing elsewhere) then the task is question
could immediate make progress - as it is not blocked.
So above words do it for me
****************************************************************
From: Christoph Grein
Sent: Friday, October 8, 2010 3:46 AM
!reference Ada 2005 D.2(7/3), D2.4(9.a/3)
!from Author Grein 2010-10-98
!keywords keywords Yield
!discussion
D.2(7/3) says "Yield is a potentially blocking operation". So it must not be called in POs.
D2.4(9.a/3) says "calls to any of the Yield procedures are never blocking".
While this is true for Yield_To_Higher (they can be called in POs), it is a contradiction
to D.2(7/3) for Yield and its renaming Yield_To_Same_Or_Higher.
Or am I missing something? I've read AI05-0166-1 and there is no mention that
Yield_To_Same_Or_Higher is not a potentially blocking operation.
****************************************************************
From: Randy Brukardt
Sent: Tuesday, October 19, 2010 12:05 AM
I noticed that that note didn't make any sense last April and engaged Alan in a long
discussion about how it should be worded. It's filed in AI05-0166-1 at the end. But
apparently, I never actually put the corrected wording into the Standard. Thanks for
pointing it out.
****************************************************************
From: Randy Brukardt
Sent: Tuesday, October 19, 2010 12:09 AM
That's not quite right: the wording that I discussed with Alan was changed, but the
note wasn't. Anyway, it's fixed now.
****************************************************************
Questions? Ask the ACAA Technical Agent