!standard D.4(7/2) 16-04-21 AI12-0163-1/04 !standard D.4(12) !standard D.4(13) !standard D.4(14) !class Amendment 15-06-04 !status Amendment 1-2012 16-02-29 !status WG9 Approved 16-06-13 !status ARG Approved 5-0-3 15-10-17 !status work item 15-06-04 !status received 15-04-23 !priority Low !difficulty Easy !subject Deterministic queue servicing for FIFO_Queueing !summary A new queuing policy, Ordered_FIFO_Queuing is defined. !problem For analyzability, it would be preferable to have determinism in queue selection for the FIFO_Queueing queuing policy when multiple queues are eligible for selection. The definition of FIFO_Queuing is not appropriate to ensure determinism, because it does not specify which entry queue is serviced first (see RM 9.5.3(17)). A configuration pragma to select deterministic queue selection is desired. !proposal Add a new queuing policy Ordered_FIFO_Queuing. The rules for this policy are the same as those for FIFO_Queuing (as described in 9.5.3 and 9.7.1) except that when multiple queues are eligible for selection, the selected entry chosen is the one that was queued first, that is, the selection is FIFO across all queues to the same PO or selective_accept, instead of just within a single queue. !wording Modify D.4(7/2) [Two]{Three} queuing policies, FIFO_Queuing{, Ordered_FIFO_Queuing,} and Priority_Queuing, are language defined. If no Queuing_Policy pragma applies to any of the program units comprising the partition, the queuing policy for that partition is FIFO_Queuing. The rules for this policy are specified in 9.5.3 and 9.7.1. Append after D.4(7/2) The Ordered_FIFO_Queuing policy is defined as follows: Calls are selected on a given entry queue in order of arrival. When more than one condition of an entry_barrier of a protected object becomes True, and more than one of the respective queues is nonempty, the call that arrived first is selected. If the expiration time of two or more open delay_alternatives is the same and no other accept_alternatives are open, the sequence_of_statements of the delay_alternative that is first in textual order in the selective_accept is executed. When more than one alternative of a selective_accept is open and has queued calls, the alternative whose queue has the call that arrived first is selected. !discussion Changing the default behavior of FIFO_Queuing is not a good idea. Queue selection has been non-deterministic since Ada 83, and there have been many opportunities to change that. Indeed, textual order of select can lead to starvation in cases where there are many requests reaching an object. And it could reduce opportunities for parallelism on some targets. Ada already has a configuration pragma for selecting the details of queuing -- pragma Queuing_Policy. That the requested semantics are appropriate for a queuing policy is easily seen in that Priority_Queuing has exactly these semantics when all calls have the same priority. So it's clear that this is actually a request for a new queuing policy that combines parts of the two existing policies. It would be madness to create a new configuration pragma with the same sort of effect as an existing one. The name Ordered_FIFO_Queuing was chosen, to reflect that the FIFO ordering applies not only within a single queue, but across all the queues of a protected object or selective_accept. The FIFO ordering provided by this queuing policy provides stronger guarantees for FIFO ordering than the default FIFO_Queuing policy which only defines the ordering within a single entry queue. One possible implementation for this policy would be to assign a sequence number to each queued entry call, where the sequence number is incremented globally across all queues associated with the protected object or selective_accept. We considered just applying textual order for the case when multiple queues are selectable, but this can lead to unfair queue servicing, since the queues in earlier textual order can end up starving the later ones. Applying arrival first as the selector provides fairness. !corrigendum D.4(7/2) @drepl Two queuing policies, FIFO_Queuing and Priority_Queuing, are language defined. If no Queuing_Policy pragma applies to any of the program units comprising the partition, the queuing policy for that partition is FIFO_Queuing. The rules for this policy are specified in 9.5.3 and 9.7.1. @dby Three queuing policies, FIFO_Queuing, Ordered_FIFO_Queuing, and Priority_Queuing, are language defined. If no Queuing_Policy pragma applies to any of the program units comprising the partition, the queuing policy for that partition is FIFO_Queuing. The rules for this policy are specified in 9.5.3 and 9.7.1. The Ordered_FIFO_Queuing policy is defined as follows: @xbullet @xbullet of a protected object becomes True, and more than one of the respective queues is nonempty, the call that arrived first is selected.> @xbullets is the same and no other @fas are open, the @fa of the @fa that is first in textual order in the @fa is executed.> @xbullet is open and has queued calls, the alternative whose queue has the call that arrived first is selected.> !ASIS No ASIS effect. !ACATS test An ACATS C-Test is needed to check that the new policy is supported. !appendix From: Brad Moore Sent: Thursday, April 23, 2015 8:15 PM A couple of issues were raised at the recent IRTAW, and I volunteered to bring these issues forward for ARG consideration. The first issue relates to adding determinism in queue selection for the FIFO_Queueing queuing policy when multiple queues are eligible for selection. The current definition of FIFO_Queuing is not appropriate to ensure determinism, because it does not specify which entry queue is serviced first (see ARM 9.5.3, par. 17). It was suggested that a textual ordering would likely be the most appropriate choice (as defined for Priority_Queuing in ARM D.4, par. 12) for this policy. If we decide to proceed in this direction, it might make sense to define a new representation aspect that would select the desired ordering for each protected type and object. **************************************************************** From: Tucker Taft Sent: Thursday, April 23, 2015 8:36 PM ... > The first issue relates to adding determinism in queue selection for > the FIFO_Queueing queuing policy when multiple queues are eligible for > selection. The current definition of FIFO_Queuing is not appropriate > to ensure determinism, because it does not specify which entry queue > is serviced first (see ARM 9.5.3, par. 17). > It was suggested that a textual ordering would likely be the most > appropriate choice (as defined for Priority_Queuing in ARM D.4, par. 12) for > this policy. Yes, that seems the only reasonable choice to achieve determinism. Essentially FIFO_Queuing should be equivalent to Priority_Queuing when all calls are considered to have the same priority. > If we decide to proceed in this direction, it might make sense to > define a new representation aspect that would select the desired ordering for > each protected type and object. Having this level of granularity seems like a separate decision. Fixing the definition of FIFO_Queuing seems like a very simple change, and I would recommend we just do it. I would be surprised if there would be any significant implementation burden. On the other hand, having queuing policies on a per-type, per-object, or per-entry basis will almost certainly involve an implementation burden. **************************************************************** From: Stephen Michell Sent: Thursday, April 23, 2015 9:47 PM Textual order is not quite enough. If we are imposing order, we must also impose order on entry family. I would recommend that if two or more entries of an entry family are open, then the entry with the lowest index is selected. **************************************************************** From: Randy Brukardt Sent: Thursday, April 23, 2015 10:48 PM > > A couple of issues were raised at the recent IRTAW, and I > > volunteered to bring these issues forward for ARG consideration. There only seems to be one issue here. Is there another one coming? (I can't wait. ;-) > > The first issue relates to adding determinism in queue selection for > > the FIFO_Queueing queuing policy when multiple queues are eligible > > for selection. The current definition of FIFO_Queuing is not > > appropriate to ensure determinism, because it does not specify which > > entry queue is serviced first (see ARM 9.5.3, par. 17). > > It was suggested that a textual ordering would likely be the most > > appropriate choice (as defined for Priority_Queuing in ARM D.4, par. > > 12) for this policy. > > Yes, that seems the only reasonable choice to achieve determinism. > Essentially FIFO_Queuing should be equivalent to Priority_Queuing when > all calls are considered to have the same priority. > > > > If we decide to proceed in this direction, it might make sense to > > define a new representation aspect that would select the > desired ordering for each protected type and object. > > Having this level of granularity seems like a separate decision. > Fixing the definition of FIFO_Queuing seems like a very simple change, > and I would recommend we just do it. Humm. I'm not sure that this is a "fix". The fact that queue selection for FIFO_Queuing is non-deterministic is explicitly written in the RM text; there were many opportunities to change that during the Ada 9x work and later and that was not done. It's not like this behavior is some sort of accident or a mistake - 9.5.3 explicitly says "the default entry queuing policy does not specify which queue is serviced first". I would be very wary of changing that behavior unless we (a) know why the original choice was made and (b) know that it isn't going to cause any problems with existing implementations. > I would be surprised if there would be any significant implementation > burden. That depends on whether this particular property is handled in the Ada runtime (in which case the burden is likely to be minimal) or somewhere else. If it's handled in an RTOS, making it deterministic in an Ada sense could be difficult. (Note: I don't have any personal knowledge of problematic implementations, it just seems likely to me.) Keep in mind that this is a core property (it's in 9.5.3). It's not solely about what Annex D-supporting compilers do. Do we really want to force compilers to change that will never be used by IRTAW-types? The safe thing would be to define a deterministic queuing policy, and have the customers in question use that. Of course, Priority_Queuing is already that. One wonders why someone wants to fit a square peg (a purposely non-deterministic policy) into a round hole (deterministic behavior). And then essentially take away that possibility from everyone, even those that might benefit from it. **************************************************************** From: Randy Brukardt Sent: Thursday, April 23, 2015 11:02 PM ... > Humm. I'm not sure that this is a "fix". The fact that queue selection > for FIFO_Queuing is non-deterministic is explicitly written in the RM > text; there were many opportunities to change that during the Ada 9x > work and later and that was not done. It's not like this behavior is > some sort of accident or a mistake - 9.5.3 explicitly says "the > default entry queuing policy does not specify which queue is serviced > first". FYI, this has always been explicitly in the RM. I looked at 9x drafts back to version 2.0, and they all have explicitly nondeterministic behavior for queue servicing. (The wording changed several times, so surely people were aware of it.) So, that's been the rule for at least 23 years (it probably was in Ada 83, too, but not so obviously). Why change and make everyone work (and possibly change the behavior of programs)? What the heck has changed that this is suddenly so important? **************************************************************** From: Jean-Pierre Rosen Sent: Friday, April 24, 2015 12:15 AM > Humm. I'm not sure that this is a "fix". The fact that queue selection > for FIFO_Queuing is non-deterministic is explicitly written in the RM > text; there were many opportunities to change that during the Ada 9x > work and later and that was not done. It's not like this behavior is > some sort of accident or a mistake - 9.5.3 explicitly says "the > default entry queuing policy does not specify which queue is serviced first". And it was already the case in Ada 83 > I would be very wary of changing that behavior unless we (a) know why > the original choice was made and (b) know that it isn't going to cause > any problems with existing implementations. The idea was that different use cases need different choice algorithms. For example, textual preference is a terrible choice if you have a continuous flow of incoming requests: the first queue will always be served, and the others will starve (round robin choice is the best thing to do here). The idea in Ada83 was to not specify the choice algorithm in order to allow other means (pragmas at that time) for the selection of the appropriate policy. I think the argument still holds today. Let's not change the default behaviour; OTOH, defining an aspect/pragma to specify the choice algorithm (either as a global option, or on a per PO/Task aspect) would be welcome. And we could make it illegal to specify a policy which is not supported (rather than force all algorithms to all implementations). This way, if the user depends on a selection algorithm, and this algorithm is not supported, it will simply not compile. And (almost) no change required to compilers (just allow the currently supported policy). **************************************************************** From: Bob Duff Sent: Friday, April 24, 2015 7:58 PM I agree with Randy: > I would be very wary of changing that behavior unless we (a) know why > the original choice was made and (b) know that it isn't going to cause > any problems with existing implementations. And (c) we need evidence that users actually want such a feature. IRTAW has a history of proposing features that might or not actually end up being used. For example, I think "processor affinity" is used, but I don't think anybody is using the "per-task execution time" feature. The intent/history is that the policies in the core language should be loose, allowing existing implementations to do more-or-less whatever they like. And the RT annex can nail things down further. It seems to me that if you want more nailed-down semantics, you should use Priority_Queuing. If you only want one priority level, then nothing is stopping you from doing that. If Priority_Queuing is unsuitable, ask your compiler vendor for a different policy. If it actually gets implemented and used, THEN we can consider adding it to the RT annex. I'm a big fan of determinism, and if I were designing Ada 83 from scratch today, I might nail down the semantics. But I see no reason to change the language at this point. **************************************************************** From: Randy Brukardt Sent: Friday, April 24, 2015 8:30 PM > I agree with Randy: > > "Randy Brukardt" wrote: > > > I would be very wary of changing that behavior unless we (a) know > > why the original choice was made and (b) know that it isn't going to > > cause any problems with existing implementations. > > And (c) we need evidence that users actually want such a feature. > IRTAW has a history of proposing features that might or not actually > end up being used. For example, I think "processor affinity" is used, > but I don't think anybody is using the "per-task execution time" > feature. I agree with your basic point, but (ahem) I did want to use the "per-task execution time" in Janus/Ada. The only reason I didn't was that I would have had to implement it first. ;-) I needed to get some profiling information on a set of tasks, and the regular profiler (which uses wall-clock time) was getting confused by task swaps. (Since all of the tasks are in a single process from a Windows perspective, that's invisible to standard profilers.) But I agree that that is a non-critical need; I was thinking of building something when I remembered that Ada already had it. (And then never implemented it as it appeared to be too much work for that particular project.) > It seems to me that if you want more nailed-down semantics, you should > use Priority_Queuing. If you only want one priority level, then > nothing is stopping you from doing that. > If Priority_Queuing is unsuitable, ask your compiler vendor for a > different policy. > If it actually gets implemented and used, THEN we can consider adding > it to the RT annex. Right. If IRTAW had asked for a new queuing policy, I would had no problem. Since Brad tells us that it for the next generation of Ravenscar (Steelerscar? Bengalscar? [OK, sorry for the American football references, maybe better to use a large scavenger bird...] Condorscar? :-), that's precisely how it should be defined (new aspects and pragmas). Leave the core alone. > I'm a big fan of determinism, and if I were designing Ada 83 from > scratch today, I might nail down the semantics. But I see no reason > to change the language at this point. Many decades too late. **************************************************************** From: Brad Moore Sent: Saturday, April 25, 2015 10:44 AM Apparently I didn't capture the desired intent from IRTAW quite right. IRTAW was not asking for the default behaviour of FIFO_Queueing to be changed to specify textual order for selecting eligible entry calls. Rather, they were asking for a configuration pragma that could alter the default behaviour to specify that textual ordering be used for selecting eligible entry calls. >> I would be very wary of changing that behavior unless we (a) know why >> the original choice was made and (b) know that it isn't going to cause >> any problems with existing implementations. > And (c) we need evidence that users actually want such a feature. > IRTAW has a history of proposing features that might or not > actually end up being used. For example, I think "processor > affinity" is used, but I don't think anybody is using the > "per-task execution time" feature. > It seems to me that if you want more nailed-down semantics, > you should use Priority_Queuing. If you only want one > priority level, then nothing is stopping you from doing that. > If Priority_Queuing is unsuitable, ask your compiler vendor > for a different policy. > If it actually gets implemented and used, THEN we can > consider adding it to the RT annex. It's a bit of a catch-22 situation though. During the discussions at IRTAW, someone made the point that to some extent, Ravenscar is successful because it is part of a standard that people can reference. Something like; "we use Ravenscar because a bunch of experts said it was a good thing to use, and we place a level of trust in these experts." If it weren't defined in some sort of standardized form, the thought is that it likely wouldn't have been adopted to the extent it has. Perhaps it would make sense for the initial "standardization" for such as feature to appear in the form of a technical specification, which might be enough for users to justify its use, and then through that use provide the eventual justification for adding the feature to the Ada standard? Using one priority level I think is not going to be satisfactory, as the intent is to provide a run-time that is less-restrictive than Ravenscar. Requiring only one priority for all tasks seems to be going in the other direction. Presumably, the appeal of the FIFO_Queueing policy is that it allows for a simpler run-time, and possibly simpler analysis, than Priority_Queueing. I've asked for clarification on this from the authors, to provide any additional motivation for the use of this policy. > Right. If IRTAW had asked for a new queuing policy, I would had no problem. > Since Brad tells us that it for the next generation of Ravenscar > (Steelerscar? Bengalscar? [OK, sorry for the American football references, > maybe better to use a large scavenger bird...] Condorscar? :-), that's > precisely how it should be defined (new aspects and pragmas). Leave the core > alone. Given the desired intent from IRTAW described above, (a) seems relatively unimportant since we would not be changing the existing default. Presumably such a configuration pragma could be confined to the real time annex? In that case, the core would be unaffected. As for (b), I don't know about other implementations, but considering the analysis for this capability came from a paper from Adacore, it suggests that the idea is likely workable for the GNAT compiler at least. I agree we should collect more inputs if possible from other implementations though. As for (c), I've requested the group in IRTAW looking at this feature to provide more evidence of user demand, if possible. Looking at the original position paper, (which is not yet in its final form), it describes the motivation for applications requiring predictability. It suggests that application developers have worked around limitations in restricted runtimes, by implementing precluded functionality in the application space, thereby introducing complexity, in a form of abstraction inversion. It is the belief of the authors that some of these missing features may be implemented in the run-time library without loss of predictability, and with no more complexity than that of an implementation at the application level using profile-approved constructs. The presumption is that a degree of complexity that is acceptable at the application level would be acceptable at the run-time library level instead, for applications in this domain. **************************************************************** From: Erhard Ploedereder Sent: Sunday, April 26, 2015 4:48 PM I agree with JPR there. Anybody who wants a fair scheduling approach would immediately see the flaw of textual order. So, let us not specify a default to be imposed on everyone. Let the IRTAW propose an aspect or pragma (pragma Deterministic_but_Unfair_Textual_Order comes to mind.) **************************************************************** From: Jean-Pierre Rosen Sent: Thursday, April 21, 2016 9:46 AM In two places in the !wording section: the call that arrive[s]{d} first => Since the sentence starts with "when...", the calls arrived before the time described in the sentence. **************************************************************** From: Randy Brukardt Sent: Thursday, April 21, 2016 5:07 PM Got it. Thanks. That wording seemed wrong to me, but I couldn't explain why and I thought enough people had vetted it that I must have been imagining things. Apparently not. ****************************************************************