!standard A.18.24 10-05-10 AI05-0159-1/06 !class Amendment 05-10-24 !status work item 10-04-29 !status ARG Approved 11-0-0 10-02-27 !status work item 06-03-15 !status received 05-10-02 !priority Medium !difficulty Hard !subject Queue containers !summary Add task-safe queues to the set of containers. !problem The Ada 2005 containers only allow a single task to access them at a time, leaving it to the users to manage access by multiple tasks. There is a need for task-safe containers. !proposal Add a synchronized interface and four implementations of task-safe queues. We have both regular queues and priority queues. There are bounded and unbounded versions of both kinds of queues. In addition, add another interface for indefinite queues, with two implementations: unbounded regular queues and priority queues. !wording A.18.23 Containers.Synchronized_Queue_Interfaces The language-defined generic package Containers.Synchronized_Queue_Interfaces provides interface type Queue, and a set of operations for that type. Interface Queue specifies a first-in, first-out queue. Static Semantics The generic library package Containers.Synchronized_Queue_Interfaces has the following declaration: generic type Element_Type is private; package Ada.Containers.Synchronized_Queue_Interfaces is pragma Pure; type Queue is synchronized interface; procedure Enqueue (Container : in out Queue; New_Item : Element_Type) is abstract; pragma Implemented (Enqueue, By_Entry); procedure Dequeue (Container : in out Queue; Element : out Element_Type) is abstract; pragma Implemented (Dequeue, By_Entry); function Current_Use (Container : Queue) return Count_Type is abstract; function Peak_Use (Container : Queue) return Count_Type is abstract; end Ada.Containers.Synchronized_Queue_Interfaces; procedure Enqueue (Container : in out Queue; New_Item : Element_Type) is abstract; A queue type that implements this interface may have a bounded *capacity*. If the queue object has a bounded capacity, and the number of existing elements equals the capacity, then Enqueue blocks until storage becomes available; otherwise Enqueue does not block. In any case, it then copies New_Item onto the queue. procedure Dequeue (Container : in out Queue; Element : out Element_Type) is abstract; If the queue is empty, then Dequeue blocks until an item becomes available. In any case, it then returns a copy of the element at the head of the queue, and removes it from the container. function Current_Use (Container : Queue) return Count_Type is abstract; Returns the number of elements currently in the queue. function Peak_Use (Container : Queue) return Count_Type is abstract; Returns the maximum number of elements that have been in the queue at any one time. A.18.24 Containers.Unbounded_Synchronized_Queues Static Semantics The language-defined generic package Containers.Unbounded_Synchronized_Queues provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue. with System; with Ada.Containers.Synchronized_Queue_Interfaces; generic with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>); Default_Ceiling: System.Any_Priority := System.Priority'Last; package Ada.Containers.Unbounded_Synchronized_Queues is pragma Preelaborate; protected type Queue (Ceiling: System.Any_Priority := Default_Ceiling) is new Queue_Interfaces.Queue with pragma Priority(Ceiling); entry Enqueue(Container: in out Queue; New_Item: Element_Type); entry Dequeue(Container: in out Queue; Element: out Element_Type); private -- not specified by the language end Queue; private -- not specified by the language end Ada.Containers.Unbounded_Synchronized_Queues; The type Queue is used to represent task-safe queues. The type Queue needs finalization (see 7.6). The capacity for instances of type Queue is unbounded. AARM Ramification: Enqueue never blocks; if more storage is needed for a new element, it is allocated dynamically. A.18.25 Containers.Bounded_Synchronized_Queues Static Semantics The language-defined generic package Containers.Bounded_Synchronized_Queues provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue. with System; with Ada.Containers.Synchronized_Queue_Interfaces; generic with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>); Default_Capacity : Count_Type := 1; Default_Ceiling: System.Any_Priority := System.Priority'Last; package Ada.Containers.Bounded_Synchronized_Queues is package Ada.Containers.Bounded_Synchronized_Queues is pragma Preelaborate; protected type Queue (Capacity : Count_Type := Default_Capacity; Ceiling: System.Any_Priority := Default_Ceiling) is new Queue_Interfaces.Queue with pragma Priority(Ceiling); entry Enqueue(Container: in out Queue; New_Item: Element_Type); entry Dequeue(Container: in out Queue; Element: out Element_Type); private -- not specified by the language end Queue; private -- not specified by the language end Ada.Containers.Bounded_Synchronized_Queues; The semantics are the same as for Unbounded_Synchronized_Queues, except: - The type Queue needs finalization (see 7.6) if and only if Element_Type needs finalization. - The capacity for instances of type Queue is bounded and specified by the discriminant Capacity. AARM Ramification: Since this type has a bounded capacity, Enqueue might block if the queue is full. Implementation Advice Bounded queue objects should be implemented without implicit pointers or dynamic allocation. A.18.26 Containers.Unbounded_Priority_Queues Static Semantics The language-defined generic package Containers.Unbounded_Priority_Queues provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue. with System; with Ada.Containers.Synchronized_Queue_Interfaces; generic with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>); type Queue_Priority is private; with function Get_Priority (Element: Queues.Element_Type) return Queue_Priority is <>; with function "<" (Left, Right : Queues.Element_Type) return Boolean is <>; Default_Ceiling: System.Any_Priority := System.Priority'Last; package Ada.Containers.Unbounded_Priority_Queues is pragma Preelaborate; protected type Queue (Ceiling: System.Any_Priority := Default_Ceiling) is new Queue_Interfaces.Queue with pragma Priority(Ceiling); entry Enqueue(Container: in out Queue; New_Item: Element_Type); entry Dequeue(Container: in out Queue; Element: out Element_Type); entry Dequeue_Only_High_Priority (Container : in out Queue; Minimum_Priority : Queue_Priority; Element : out Element_Type); private -- not specified by the language end Queue; private -- not specified by the language end Ada.Containers.Unbounded_Priority_Queues; The type Queue is used to represent task-safe priority queues. The type Queue needs finalization (see 7.6). The capacity for instances of type Queue is unbounded. Two elements E1 and E2 are equivalent if Get_Priority(E1) < Get_Priority(E2) and Get_Priority(E2) < Get_Priority(E1) both return False. Enqueue inserts an item according to the order specified by the "<" function. If the queue already contains elements equivalent to New_Item, then it is inserted after the existing equivalent elements. AARM Ramification: Enqueue never blocks; if more storage is needed for a new element, it is allocated dynamically. Dequeue_Only_High_Priority is the same as Dequeue, except that it blocks until the element E at the head of the queue satisfies not (Get_Priority(E) < Minimum_Priority). The actual functions for Get_Priority and "<" are expected to return the same value each time they are called with the same actuals, and should not modify their actuals. "<" should define a strict weak ordering relationship (see A.18). If the actual functions behave in some other manner, the behavior of Unbounded_Priority_Queues is unspecified. A.18.27 Containers.Bounded_Priority_Queues Static Semantics The language-defined generic package Containers.Bounded_Priority_Queues provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue. with System; with Ada.Containers.Synchronized_Queue_Interfaces; generic with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>); type Queue_Priority is private; with function Get_Priority (Element: Queues.Element_Type) return Queue_Priority is <>; with function "<" (Left, Right : Queues.Element_Type) return Boolean is <>; Default_Capacity : Count_Type := 1; Default_Ceiling: System.Any_Priority := System.Priority'Last; package Ada.Containers.Bounded_Priority_Queues is pragma Preelaborate; protected type Queue (Capacity : Count_Type := Default_Capacity; Ceiling: System.Any_Priority := Default_Ceiling) is new Queue_Interfaces.Queue with pragma Priority(Ceiling); entry Enqueue(Container: in out Queue; New_Item: Element_Type); entry Dequeue(Container: in out Queue; Element: out Element_Type); entry Dequeue_Only_High_Priority (Container : in out Queue; Minimum_Priority : Queue_Priority; Element : out Element_Type); private -- not specified by the language end Queue; private -- not specified by the language end Ada.Containers.Bounded_Priority_Queues; The semantics are the same as for Unbounded_Priority_Queues, except: - The type Queue needs finalization (see 7.6) if and only if Element_Type needs finalization. - The capacity for instances of type Queue is bounded and specified by the discriminant Capacity. AARM Ramification: Since this type has a bounded capacity, Enqueue might block if the queue is full. Implementation Advice Bounded priority queue objects should be implemented without implicit pointers or dynamic allocation. A.18.28 Indefinite Synchronized Queues There are three generic packages Containers.Indefinite_Synchronized_Queue_Interfaces, Containers.Indefinite_Unbounded_Synchronized_Queues, and Containers.Indefinite_Unbounded_Priority_Queues. These are identical to Containers.Synchronized_Queue_Interfaces, Containers.Unbounded_Synchronized_Queues, and Containers.Unbounded_Priority_Queues, respectively, except that Element_Type is indefinite. !discussion We considered making protected forms of all of the existing containers, but determined that there are various problems with such an approach: (1) What kind of protection is needed (multiread, single write vs. multi anything)? (2) Some of the operations (especially those with callbacks) could potentially deadlock. How do we handle those cases (allow a single task to do anything while it holds the lock vs. always locking). (3) Can we actually do better performance-wise than the user wrapping the operations that they need? Note that the existing containers are not potentially blocking, so they can be called from protected operations. A well-designed protected type will have much better abstraction than anything we could provide, and probably would not have as large a performance cost. Thus, we decided to provide task-safe queue abstractions (which are commonly needed) and let the users create any others that they need. !example declare -- First we create the queue interface. package Widgets is type Widget is new Integer; -- for example ... end Widgets; package Widget_Queue_Types is new Ada.Containers.Synchronized_Queues (Widgets.Widget); -- Now we design an algorithm around our interface. Here -- we have a set of assembly lines that fabricate widgets, -- adding them to a common queue. We also have a task that -- removes widgets from the queue for delivery. task type Assembly_Line_Task (Q : access Widget_Queue_Types.Queue'Class := null, N : Natural := 0) -- number of widgets is end; function New_Assembly_Line_Task (Q : not null access Widget_Queue_Types.Queue'Class; N : Natural) return Assembly_Line_Task is begin return T : Assembly_Line_Task (Q, N); end New_Assembly_Line_Task; type Assembly_Line_Task_Array is array (Positive range <>) of Assembly_Line_Task; task type Delivery_Service_Task (Q : not null access Widget_Queue_Types.Queue'Class; N : Natural) -- number of assembly lines is end; -- An assembly line task fabricates widgets until the -- requisite number have been made, and then it puts a -- distinguished value into the queue to indicate to -- the delivery service that there are no more widgets -- from this assembly line. task body Assembly_Line_Task is begin for I in 1 .. N loop delay 0.5; Q.Enqueue (Widget (I)); end loop; Q.Enqueue (Widget'(0)); -- no more widgets end Assembly_Line_Task; -- The delivery service task continually dequeues widgets -- from the queue (dispensing widget objects as necessary), -- and keeps track of how many assembly lines have -- finished making widgets. When all of the assembly lines -- are done, the delivery service task terminates. task body Delivery_Service_Task is W : Widget; Done : Natural := 0; begin loop Q.Dequeue (W); if W > 0 then Put_Line ("Delivering widget" & Widget'Image (W)); else Done := Done + 1; exit when Done >= N; end if; end loop; end Delivery_Service_Task; -- None of what we have done so far depends on any specific widget -- queue type. Here we instantiate the unbounded queue package -- for use as our widget queue object. package Widget_Queues is new Ada.Containers.Unbounded_Synchronized_Queues (Queues => Widget_Queue_Types); Q : aliased Widget_Queues.Queue; -- Now we elaborate our assembly line and delivery service task -- objects, binding them to the widget queue object. Assembly_Lines : Assembly_Line_Task_Array (1 .. 5) := (others => New_Assembly_Line_Task (Q'Access, 10)); Delivery_Service : Delivery_Service_Task (Q'Access, Assembly_Lines'Length); begin -- activate tasks null; end; !ACATS test ACATS Tests are needed for these new packages. !appendix From: Martin Dowie Date: Tuesday, July 28, 2009 2:53 AM 1. For the priority queue, what is the expected behaviour of trying to add 2 identical elements to the queue? It would seem that the 2nd would not be added (as "Before (x, x) = False"). I appreciate that to get both messages added would probably require "multiset" support - are "Multi" variants of the existing containers planned? 2. For the bounded variants, is the intent that they should not use dynamic memory (same as the new bounded containers)? If so, should there be some words added to state this? 3. The queues are all specified to be FIFO - could LIFO also be added relatively cheaply? Not as common but still useful. **************************************************************** From: Randy Brukardt Date: Tuesday, August 11, 2009 1:42 PM Sorry about the long delay on posting this one; it got blocked by a useless filter in the mailing list software (that unfortunately can't be turned off) and I was on vacation. > 1. For the priority queue, what is the expected behaviour of trying to > add 2 identical elements to the queue? It would seem that the 2nd > would not be added (as "Before (x, x) = False"). I appreciate that to > get both messages added would probably require "multiset" support - > are "Multi" > variants of the existing containers planned? I would have expected the reverse: that two identical elements get queued (probably in an unspecified order). That's how the queues in my mail filter work (the only time I've used priority queues in practice) [They're actually more like delay queues, as the "priority" is the retry time. Surely you don't want to loose a message just because it happens to have the same retry time as another.] In any case, this will need to be clarified. > 2. For the bounded variants, is the intent that they should not use > dynamic memory (same as the new bounded containers)? > If so, should there be some words added to state this? That is my understanding, and yes, of course, they will need all of the appropriate wording that AI05-0001-1 uses for bounded forms. > 3. The queues are all specified to be FIFO - could LIFO also be added > relatively cheaply? Not as common but still useful. Not sure it is worth it. We're really only trying to provide the most basic and common of protected containers because generally the "protection" needed is something that depends on the entire algorithm; naively dropping in protected containers could easily generate race or deadlock conditions. In any case, "LIFO" is a stack, which is generally thought of as a totally different data structure, with different names for the operations. Trying to use queue terminology for it would be pretty unnatural. So there wouldn't be much if any reuse potential here. **************************************************************** From: Simon Wright Date: Tuesday, August 11, 2009 3:45 PM >> 1. For the priority queue, what is the expected behaviour of trying >> to add 2 identical elements to the queue? It would seem that the 2nd >> would not be added (as "Before (x, x) = False"). I appreciate that to >> get both messages added would probably require "multiset" support - >> are "Multi" >> variants of the existing containers planned? > > I would have expected the reverse: that two identical elements get > queued (probably in an unspecified order). As a data point here, the BC ordered queue queues 'identical' items in FIFO order (preferring defined behaviour). Whether an unspecified order is satisfactory must, I think, depend on the application. **************************************************************** From: Jeffrey R. Carter Date: Tuesday, August 11, 2009 4:12 PM > I would have expected the reverse: that two identical elements get > queued (probably in an unspecified order). That's how the queues in my > mail filter work (the only time I've used priority queues in practice) > [They're actually more like delay queues, as the "priority" is the > retry time. Surely you don't want to loose a message just because it > happens to have the same retry time as another.] If they're specified as FIFO, the priority queue must really be FIFO-within-priorities, so it must queue the 2nd after the 1st. **************************************************************** From: Martin Dowie Date: Monday, August 24, 2009 7:03 AM Thanks for all that - making more sense now... Would it be useful to add a "Peek" operation too? One that returned the highest priority element in the queue without actually removing it from the queue? **************************************************************** From: Matthew Heaney Date: Thursday, October 8, 2009 12:28 AM > 1. For the priority queue, what is the expected behaviour of trying to > add 2 identical elements to the queue? It would seem that the 2nd > would not be added (as "Before (x, x) = False"). I appreciate that to > get both messages added would probably require "multiset" support - > are "Multi" > variants of the existing containers planned? There are two separate issues here. The first issue is the matter of the priority queue. Yes, you should be able to add multiple items that are equivalent. And yes, new elements that are equivalent to existing elements should probably go after existing elements. (But this will have to be decided at the ARG meeting next month.) The second issue is multiset support. This is orthogonal to priority queues (because the language doesn't specify how the queues are implemented). On the specific matter of multiset support, I lobbied last year for their inclusion in the language standard, but wasn't able to make my case with sufficient cogency, so they didn't make the cut. However, an unbounded multiset is part of the GNAT distribution, so if you're using GNAT then you have one already. I am in the process of integrating the bounded forms into GNAT, and so GNAT will have a bounded multiset too. For now I have implemented the bounded priority queues using the multisets, but eventually I'll probably replace that implementation with a proper heap. > 2. For the bounded variants, is the intent that they should not use > dynamic memory (same as the new bounded containers)? If so, should > there be some words added to state this? Right, the bounded forms do not use dynamic memory allocation. > 3. The queues are all specified to be FIFO - could LIFO also be added > relatively cheaply? Not as common but still useful. That's just a stack. Use a vector or a list container, wrapped in a protected object. **************************************************************** From: Randy Brukardt Date: Monday, April 5, 2010 8:29 PM I recently had a discussion with Martin Dowie. He was concerned that the lack of a Peek operation in the priority queues makes it difficult to implement some common situations. In particular, cases where the reader wants to defer processing until an item of sufficient priority is available. (Obviously, this case only applies to priority queues.) Using Peek requires a busy-wait loop of some sort, which is obviously suboptimal. In addition, Peek is very hard to use safely, as in general you can assume nothing at all about the item retrieved by a Dequeue after executing a Peek. (Another task may have put a higher-priority item on the queue, or another task may have removed the item at the head of the queue, between the Peek and a Dequeue.) As such, it's like leaving a loose razor blade in a toolchest. Moreover, in the bounded queue case (without any dynamic memory management) it is not any more efficient than doing a Dequeue (both require copying the element). So it probably is a wash in terms of efficiency and safer to do a Dequeue followed by a Enqueue if you don't want to process the element (the element will end up in the same relative place on the queue since it is sorted by priority). (Enqueue might be more expensive if the queue has a lot of elements on it or the Before function is unusually expensive, but in normal circumstances it costs about the same as a Peek would, one element copy.) I had a similar problem in my spam filter, for which Peek would not have worked (there are multiple readers). The "priority' is the time when an item ought to be processed (most are ready to process immediately, but after a failed operation you have to wait a random amount of time and try again). I used a combination of timed entry calls and a high-priority-only dequeue operations. For the AI05-0159-1 queues, this routine would look like: procedure Dequeue_Only_High_Priority (Container : in out Queue; Minimum_High_Priority : Element_Type; Element : out Element_Type); This routine would block if there wasn't an element with the minimum priority available. This was used like (I've left out some parts): type Queued_Item is tagged private; type Queued_Item_Ptr is access all Queue_Node'Class; type Queue_Node is record Item : Queued_Item_Ptr; Process_After : Ada.Calendar.Time; -- Use like "delay until". end record; function Before (Left, Right : Queue_Node) return Boolean is use type Ada.Calendar.Time; begin return Left.Process_After < Right.Process_After; end Before; package Message_Queue is Ada.Containers.Unbounded_Priority_Queues (Queue_Node, Before => Before); --- declare Node : Queue_Node; begin loop select accept Send_Queue.Dequeue_Only_High_Priority (Element => Node, Minimum_High_Priority => (Item => null, After => Ada.Calendar.Clock)); Send (Node); or accept Shutdown; or delay 10.0; end loop; end loop; end; Note that I had to use the timeout because the "high-priority" value is based on the clock, and thus has to be reevaluated occasionally. That wouldn't happen if the priority didn't involve an exterior actor (and barriers that depend on globals are bad practice for this reason). Since we don't need to do retries on any particular schedule, this is a non-issue in this application. Also note that I also used that code to handle shutdown requests, since blocking forever would prevent shutdowns from being recognized. --- Anyway, the lack of such an operation would make using the AI05-0159-1 priority queues suboptimal for this use. Without the Dequeue_Only_High_Priority operation, I would have to use a faster loop (so that newly queued operations are checked reasonably quickly). There also would be a reordering of nodes that have the same sending time (not a major problem in this use, but not optimal). This would look something like: declare Node : Queue_Node; begin loop select accept Send_Queue.Dequeue (Element => Node); if Node.Process_After < Ada.Calendar.Clock then Send (Node); else Send_Queue.Enqueue (Element => Node); end if; or accept Shutdown; or delay 1.0; end loop; end loop; end; While this is not great, it might be good enough. So, is this problem worth addressing? If so, do we want to add an operation like this to the priority queues (only)? Or is there some other idea (not involving a race condition)? **************************************************************** From: Bob Duff Date: Tuesday, April 6, 2010 12:43 PM > I recently had a discussion with Martin Dowie. He was concerned that > the lack of a Peek operation in the priority queues makes it difficult > to implement some common situations. In particular, cases where the > reader wants to defer processing until an item of sufficient priority is available. > (Obviously, this case only applies to priority queues.) I have mixed feelings about such race-condition-causing features. If we have Peek, there should probably be a NOTE warning of the danger. There is precedent: Function Current_Use in this package has the same property. (By the way, there's no rationale for why we have Current_Use and Peak_Use -- seems like we ought to say something.) And Ada.Synchronous_Task_Control has Current_State, with the mild AARM-only warning, "This state can change immediately after the operation returns." > procedure Dequeue_Only_High_Priority > (Container : in out Queue; > Minimum_High_Priority : Element_Type; > Element : out Element_Type); How about this: procedure Conditional_Dequeue (Container : in out Queue; Element : out Element_Type; Condition : function (Element_Type) return Boolean) is abstract; pragma Implemented (Conditional_Dequeue, By_Entry); ? where "function (Element_Type) return Boolean" of course stands for "not null access function (Element: Element_Type) return Boolean". It dequeues an element if and only if Condition returns True for the element to be dequeued. Never blocks. Hmm. I guess we'd need another Boolean 'out' param to indicate whether it succeeded. > select > accept Send_Queue.Dequeue_Only_High_Priority (Element => Node, > Minimum_High_Priority => (Item => null, After => Ada.Calendar.Clock)); That doesn't look right -- you can only "accept" your own entries. **************************************************************** From: Martin Dowie Date: Tuesday, April 6, 2010 1:12 PM There are certainly loads of precedents, e.g. the attributes wrt to tasking are race conditions ('Callable, 'Count and 'Terminated). Randy helpfully suggested alternatives without something akin to a 'peek' (e.g. a 2 queue solution; 1 high priority, 1 low priority) but they wouldn't work when using these in high-integrity systems - i.e. Ravenscar profile environments - as they required 'select' statements. I'm sure some version of 'peek' - either a blocking or a non-blocking-with-success or blocking-for-period-with-success - would help in such environments. **************************************************************** From: Bob Duff Date: Tuesday, April 6, 2010 2:36 PM What do you think of my Conditional_Dequeue suggestion? **************************************************************** From: Randy Brukardt Date: Tuesday, April 6, 2010 3:05 PM > What do you think of my Conditional_Dequeue suggestion? It's better than Peek (much less trouble with race conditions), but I think it has two negatives: * The need to write a function when the condition is likely to be a simple expression (Obj.After < Ada.Calendar.Clock in my example) is annoying; * The lack of blocking semantics means almost all uses will need a busy-wait loop. Neither of these is critically important, but they do suggest that there might be a better solution out there. For the first, the fact that we are talking about priority queues means we already have an ordering, so it isn't clear that there is any value to having a second one. For the second, I see the issue that Ravenscar uses will necessarily have to use a busy-wait loop, but it is annoying to force everyone to live by the limitations of Ravenscar. (Indeed, as with SPARK, I would hope that we be able to move to larger subsets of the language for verification purposes; we shouldn't be tied to these overly limiting subsets forever.) Peek itself is just too dangerous in normal use: it can only be used safely on a priority queue if there is only a single peeking/dequeuing task AND the peeked item is tested then immediately discarded (there can be no assumption that it will be the one dequeued) AND getting a higher-priority item from Dequeue than the one expected is OK. I'm sure there are applications that fit into that profile, but there are many that don't (such as my "flock of senders" problem). Moreover, there is no practical way to enforce safe use of Peek (since there is no way to enforce the immediate discarding of the retrieved value). I don't think it would even be possible for a static analysis tool to figure out Peek misuse (other than the obvious: "ERROR: Use of Peek detected" :-). So we need a better solution (or none, as we currently have). **************************************************************** From: Bob Duff Date: Tuesday, April 6, 2010 3:36 PM > It's better than Peek (much less trouble with race conditions), but I > think it has two negatives: I just had a discussion with someone at AdaCore who pointed out another negative: Presumably the implementation of these queues is a protected type. You normally want all operations of a protected type to have a short bounded time. Normally, you can determine that by analyzing the protected body. But if the protected body is calling my suggested Condition function, which is passed in by the client, you need to do a more global analysis. **************************************************************** From: Randy Brukardt Date: Tuesday, April 6, 2010 3:48 PM You could say that about any priority queue in general, however, as the ordering function (Before in this case) is passed in and could take an unknown amount of time. Moreover, the number of calls will depend (in some way) upon the number of items in the queue. In practice, both of these functions would be short and execute quickly, but there is a real concern if you need strong bounds. Of course, Before is fundamental to the Queue, while your Condition function is less so. Still, it seems that this is a problem with the entire idea of generic priority queues, and not specific to your suggestion. **************************************************************** From: Bob Duff Date: Tuesday, April 6, 2010 3:54 PM Good point. **************************************************************** From: Martin Dowie Date: Wednesday, April 7, 2010 3:24 AM > What do you think of my Conditional_Dequeue suggestion? It looks good to me! A 'kitchen-sink' addition could be: procedure Conditional_Dequeue (Container : in out Queue; Element : out Element_Type; Success : out Boolean; Condition : not null access function (Element : Element_Type) return Boolean; Timeout : Duration) is abstract; pragma Implemented (Conditional_Dequeue, By_Entry); Where this blocks for up to a 'Timeout' period. That also mitigates Randy's 2nd point ("The lack of blocking semantics means almost all uses will need a busy-wait loop"). [Alternative: 'Timeout : Duration := 0.0' offers non-blocking option.] Randy's 1st point ("The need to write a function when the condition is likely to be a simple expression (Obj.After < Ada.Calendar.Clock in my example) is annoying") is true and a small 'lamba' expression would be great here! ;-) But for (ordered) container use and, to a less extent, just using general ADTs with primary keys, we end up writing those little functions _all_the_time_. Still saves a heck of a time over rolling-your-own, so I know which I prefer. I'm not sure I understand Randy's point "it is annoying to force everyone to live by the limitations of Ravenscar" - this would be 'adding to' rather than 'replacing' any functionality, so it will be safely ignored by those who don't need it (I ignore entire packages of the standard library quite happily ;-). I appreciate there are concerns about how this could be used appropriately but you could say the same for 'goto' or ATC or Unchecked_ or overlaying with 'Address or etc...the above seems a lot less (potentially) harmful to me... **************************************************************** From: Randy Brukardt Date: Wednesday, April 7, 2010 1:06 PM ... > Where this blocks for up to a 'Timeout' period. That also mitigates > Randy's 2nd point ("The lack of blocking semantics means almost all > uses will need a busy-wait loop"). > [Alternative: 'Timeout : Duration := 0.0' > offers non-blocking option.] I thought of something like this, but I don't think it can be implemented with a standard Ada protected object. You'd have to have a subprogram with a timed or conditional entry call, but then it couldn't be an entry (so it couldn't be used in a requeue or conditional entry call). And the internal conditional entry call wouldn't be allowed by Ravenscar. My original idea (not posted to Ada Comment, just in our e-mail discussion) had the same problem. ... > I'm not sure I understand Randy's point "it is annoying to force > everyone to live by the limitations of Ravenscar" - this would be > 'adding to' rather than 'replacing' any functionality, so it will be > safely ignored by those who don't need it (I ignore entire packages of > the standard library quite happily ;-). I was referring to forcing everyone to use busy-wait loops because Ravenscar programs have to be coded that way (no conditional entry calls). If we have a non-blocking operation here (as Bob proposed), we're essentially forcing all uses to use busy-wait loops. That's a lack of capability caused by Ravenscar concerns, not *extra* capability (which I wouldn't have a concern about). > I appreciate there are concerns about how this could be used > appropriately but you could say the same for 'goto' or ATC or > Unchecked_ or overlaying with 'Address or etc...the above > seems a lot less (potentially) harmful to me... I agree, this is a lot less harmful than Peek. It strikes me, though, that the separate Condition function introduces a new race condition hazard that doesn't exist in the original ones. It's less serious than the original one, but it still exists. Consider a numeric priority with a Before function of Left.Priority > Right.Priority. Assume Condition is defined as Element.Priority in 10..15. Consider the following two execution orders: Task 2 inserts an item with priority 10. Task 1 executes Conditional_Dequeue, receiving success and the item with priority 10. Task 2 inserts an item with priority 20. vs. Task 2 inserts an item with priority 10. Task 2 inserts an item with priority 20. Task 1 executes Conditional_Dequeue, receiving failure. There is a race between task 1 reading the queue and task 2's insertion of the second item. Of course, one could say that such a condition is bad (it IS bad), but I suspect that in practice the problem could be much more subtle. It might be hard to detect. This implies to me that it is only safe to use the same comparison function for Conditional_Dequeue. Which makes me think that my original proposal is (slightly) better: procedure Dequeue_Only_High_Priority (Container : in out Queue; Minimum_High_Priority : Element_Type; Element : out Element_Type); because this race condition cannot happen here (meaning that there doesn't need to be any analysis to prove that). If we wanted to insist on a non-blocking version, that would be: procedure Dequeue_Only_High_Priority (Container : in out Queue; Minimum_High_Priority : Element_Type; Element : out Element_Type; Success : out Boolean); It would be nice to have both. (That goes for regular Dequeue as well, a non-blocking version would be usable in a Ravenscar context where a blocking one might not be.) Of course, this all might be considered feeping creaturism. :-) The need to construct a complete element here for just the priority portion is indeed annoying, but there isn't any alternative since Before takes elements. **************************************************************** From: Martin Dowie Date: Wednesday, April 7, 2010 1:18 PM Thankfully, we now have the 'others => <>' option to keep the construction of the element to a minimum... I don't mind the creeping...but I'm biased by having seen the need for this sort of operation! ;-) **************************************************************** From: Mark Lorenzen Date: Wednesday, April 7, 2010 3:14 PM > I thought of something like this, but I don't think it can be > implemented with a standard Ada protected object. You'd have to have a > subprogram with a timed or conditional entry call, but then it > couldn't be an entry (so it couldn't be used in a requeue or > conditional entry call). And the internal conditional entry call > wouldn't be allowed by Ravenscar. In my opinion, tasks and protected objects should not be a part of a re-usable library. I think it's better to provide functionality for registering a call-back subprogram, which will be called in case an element (that fulfills a certain condition) is put on the queue, and at the same time dequeue the element. procedure Set_Conditional_Pass_Through_Handler (Container : in out Queue; Condition : in not null access function (Element : Element_Type) return Boolean; Handler : in not null access procedure (Element : in Element_Type)); The idea is to enable elements to "pass through" the normal priority queue mechanism. The element is never stored in the queue, but passed directly to the user as parameter Element in subprogram Handler, if Condition is fulfilled. It is up to the user to implement an optional time-out mechanism, using whatever language constructs that are appropriate for the program in question. **************************************************************** From: Randy Brukardt Date: Wednesday, April 7, 2010 4:47 PM > In my opinion, tasks and protected objects should not be a part of a > re-usable library. It has to be in this case. We've defined the queue as s synchronized interface, in order to provide task-safe access. If it wasn't synchronized (or visibly protected), it wouldn't be task-safe by the definitions in the Ada Standard. In addition, the definition declares Enqueue and Dequeue to be blocking if items cannot be added or removed respectively. Note that a synchronized interface can only be implemented with a task or protected object. Even if we decided to redefine everything without the visible synchonization (and that by adding a bunch of wording to describe what operations have to be supported -- which would be a major pain to do), we also have a principle that the containers need to be implementable in standard Ada. That could only be done by implementing the queues as a protected object of some sort (pragma Atomic is only required to be supported on "small" types, so it could not be used on a generic element type). Thus, while I agree with your principle in general for the containers, the queue containers exist *only* for the purpose of multitasking (it is trivial to create a queue using of the list container if task safety isn't needed, just rename Append to be Enqueue, and define Dequeue to be First_Element followed by Delete_First), and thus must be task-safe. And that implies that they have to be implementable with a protected object. > I think it's better to provide functionality for registering a > call-back subprogram, which will be called in case an element (that > fulfills a certain condition) is put on the queue, and at the same > time dequeue the element. > > procedure Set_Conditional_Pass_Through_Handler > (Container : in out Queue; > Condition : in not null access function (Element : Element_Type) return Boolean; > Handler : in not null access procedure (Element : in Element_Type)); > > The idea is to enable elements to "pass through" the normal priority > queue mechanism. The element is never stored in the queue, but passed > directly to the user as parameter Element in subprogram Handler, if > Condition is fulfilled. It is up to the user to implement an optional > time-out mechanism, using whatever language constructs that are > appropriate for the program in question. This does not solve the use case in question, which is a delay queue (the "priority" is the time to process the element). In that case, the element will be on the queue for a while before it becomes high enough priority (the time is reached) to remove it. It also doesn't work when multiple high priority items are queued at about the same time and there is a single consumer (this is similar to Martin's original use case); the consumer will want to get one item and come back when it is finished to get the other high priority item. With the scheme you are proposing, you would have to have a second queue to store "extra" items in this case. If that is going to be the case, you might as well have used two queues in the first place. (Martin notes that such an extra queue would imply an extra task in a Ravenscar environment, as conditional entry calls aren't allowed.) **************************************************************** From: Mark Lorenzen Date: Thursday, April 8, 2010 8:50 AM > It has to be in this case. We've defined the queue as s synchronized > interface, in order to provide task-safe access. If it wasn't > synchronized (or visibly protected), it wouldn't be task-safe by the > definitions in the Ada Standard. In addition, the definition declares > Enqueue and Dequeue to be blocking if items cannot be added or removed > respectively. Note that a synchronized interface can only be > implemented with a task or protected object. > ... I recently wrote a re-useable module containing both POs and tasks. It worked as expected in my test setup, until it had to be used in an actual application. The problems were 1) the PO priorities were not configurable and 3) the task priorities were not configurable and 3) the task stack sizes were not configurable. So if the Synchronized_Queue makes use of either, it is important that the user is able to define priorities and stack sizes e.g. by supplying them as formal parameters. Unfortunately the formal generic parameters must then of course cater for all kinds of implementations using PO(s), task(s) or PO(s) + task(s). This is messy and may result in generic parameters not being used etc. A solution is to demand that an implementation uses e.g. exactly one PO and exactly one task if this is feasible and require that an implementation documents the necessary timings and task behavior (cyclic, sporadic etc.) for perfoming a schedulability analysis. Another approach is to use suspension objects, but that is probably not an acceptable solution to the Ravenscar users and suspension objects cannot implement a synchronized interface. I'm therefore still sceptical about the useability of the proposed generic package. **************************************************************** From: Randy Brukardt Date: Thursday, April 8, 2010 12:19 PM ... > So if the Synchronized_Queue makes use of either, it is important that > the user is able to define priorities and stack sizes e.g. by > supplying them as formal parameters. > Unfortunately the formal generic parameters must then of course cater > for all kinds of implementations using PO(s), > task(s) or PO(s) + task(s). This is messy and may result in generic > parameters not being used etc. A solution is to demand that an > implementation uses e.g. exactly one PO and exactly one task if this > is feasible and require that an implementation documents the necessary > timings and task behavior (cyclic, sporadic etc.) for perfoming a > schedulability analysis. Humm, I hadn't thought of priorities, and I don't think anyone else has either. (I personally have never used them in an Ada program, although I've used plenty of tasks.) Thanks for bringing that up. In any case, a queue (or other container) should use exactly zero tasks in general, so I wouldn't worry about that. Implementers could do stupid things, but I think their customers would set them straight in a hurry. So I think what you are saying is that the generic that defines the interface also needs a priority parameter (to set the ceiling priority of the protected object(s)); the parameter would presumably be defaulted so that it doesn't have to be given unless you care. [You also seem to be saying that the entire idea of synchronized interfaces is flawed because they don't include the priorities of the implementation, which makes it impossible to reason about the behavior.] None of the predefined containers are intended to be used when timing is critical (for that, you need visibility into the implementation, which is exactly what we don't want for the containers -- we want to allow implementers to make the best implementations possible and to be able to change them freely), so actually documenting timings does not make sense. But there are a lot of systems out there (like my web server and spam filter) that just need "good enough" implementations -- where timings aren't critical. > Another approach is to use suspension objects, but that is probably > not an acceptable solution to the Ravenscar users and suspension > objects cannot implement a synchronized interface. > > I'm therefore still sceptical about the useability of the proposed > generic package. Would you prefer no predefined queue at all? There is no value to a predefined queue that isn't implemented with protected objects (it's trivial to write yourself, as I showed yesterday), so we don't want to do that. I also think that the blocking semantics is important (although that is less clear-cut). **************************************************************** From: Jeffrey R. Carter Date: Thursday, April 8, 2010 2:45 PM > Humm, I hadn't thought of priorities, and I don't think anyone else > has either. (I personally have never used them in an Ada program, > although I've used plenty of tasks.) Thanks for bringing that up. I agree that client control of priorities is important. > In any case, a queue (or other container) should use exactly zero > tasks in general, so I wouldn't worry about that. Implementers could > do stupid things, but I think their customers would set them straight in a hurry. Then perhaps it should be a protected interface rather than synchronized? > Would you prefer no predefined queue at all? There is no value to a > predefined queue that isn't implemented with protected objects (it's > trivial to write yourself, as I showed yesterday), so we don't want to > do that. I also think that the blocking semantics is important > (although that is less clear-cut). It's also trivial to wrap a protected type around a list (or ordered set) and write your own protected (priority) queue, with blocking semantics if desired. I don't think that's a reason for a library not to provide them. FWIW, the protected data structures in the PragmAda Reusable Components (Ada 95) define a protected type with a defaulted Ceiling_Priority discriminant that is used to set the priority of objects of the type. **************************************************************** From: Randy Brukardt Date: Wednesday, April 7, 2010 9:36 PM We didn't define an indefinite version of the queues, unlike all other containers forms. This seems weird to me; I can't think of any good reason to not have an indefinite unbounded queue (other than that it doesn't fit well with the interface definition -- maybe another reason that the interface isn't that good of an idea??), and it surely is inconsistent. **************************************************************** From: Bob Duff Date: Monday, May 10, 2010 10:50 AM Here's a new version of AI05-0159-1, modified as per the April 29 telephone meeting. Everything is heavily modified, except the !example, which I didn't change (nor even read). One way in which I disobeyed my marching orders: I gave the Ceiling priority discriminant a default even in the Bounded case. This requires giving a default for Capacity. I chose 1. Most users will want to specify some other value, but I don't see that as a problem. Objections? There are two levels of default -- you pass in a Ceiling (and Capacity in the bounded case) as generic formals with defaults. Then these are used as the default for the discriminant(s). Anyway, a single-element queue is not entirely nonsensical. I also tried to remove some duplicated verbiage. For example, the "interfaces" part says that Enqueue blocks if and only of the thing is bounded and is full. We don't need to mention that again in AARM notes for the concrete types, which are only a small distance away. [This is version /06 - Editor.] ****************************************************************