[Tinyos-devel] Queues with remove(element), isEnqueued(element), and other commands

Matt Welsh mdw at eecs.harvard.edu
Sat Jun 23 05:37:37 PDT 2007

David, I have some thoughts on this as well. 

Queues are tricky for a lot of reasons. Getting the interface right is
tough, and adding new behaviors is not always an easy matter of
providing different implementations of the same interface.

Example: What happens when a queue is "full"? Some queues might never
"fill" in the conventional sense; but they might reject a new insertion
for some reason (e.g., if they are rate-limited). 

Another example: An app might want to enqueue a batch of elements
together, atomically, with all-or-nothing semantics. And sometimes you
want to avoid doing some work at all if you knew in advance that the
queue would reject the entries. You end up wanting to have a kind of
transactional insertion: first 'reserve' space in the queue, do the
work, then insert the batch atomically (the latter being guaranteed to
succeed if the prior reservation succeeded). This suggests you need a
way to reclaim reservations that are not committed due to a failure
between the reservation and the commit: perhaps a lease model.

In SEDA we started off with the simplest Queue interface (insert,
remove, length) but as we went along we found that it was necessary to
add richer semantics to support the things that real applications would
need. I expect the same will hold for TinyOS.

On Fri, 2007-06-22 at 22:11 -0700, David Moss wrote:
> Hugo -
> I agree that Queue interfaces could be more useful by stepping back and
> looking at all the different use cases to combine them into one set of
> useful interfaces.  Since Queueing and other infrastructure building blocks
> are essential for quick development of TinyOS applications, it would be wise
> to make a unified queue interface as useful and robust as possible.
> After talking with Phil some more about this, what we'll do is pull the new
> FifoQueue component out of the baseline for now so its interface is not
> permanently cast into TinyOS.  Then, we'll define some broad, useful Queue
> interface to support many the types of behavior, including the ones you are
> mentioning.  Finally, we (anybody) can implement various Queues using the
> unified Queue interfaces.  
> -David
> -----Original Message-----
> From: tinyos-devel-bounces at Millennium.Berkeley.EDU
> [mailto:tinyos-devel-bounces at Millennium.Berkeley.EDU] On Behalf Of Hugo
> Sousa
> Sent: Friday, June 22, 2007 4:45 PM
> To: tinyos-devel at Millennium.Berkeley.EDU
> Subject: [Tinyos-devel] Queues with remove(element), isEnqueued(element),and
> other commands
> Hello tinyos devel team
> I would like to know what to do think of this suggestion. I've been
> using modified queue-type components in some applications, I find them
>  very useful, as they provide both queue and simple list
> functionality.
> For example, with RoundRobinResourceQueueC, since it uses only one bit
> per client (like a check box), the command remove(element) would allow
> a checklist funcionality.
> I think QueueC and the new FifoQueueC would also gain with
> remove(element) and isEnqueued(element) commands, useful for priority
> removal from queue (for example, that's what I use it for). FifoQueueC
> already has the reset() command, very useful, but the others don't.
> What do you think?
> Best regards
> Hugo Sousa
> _______________________________________________
> Tinyos-devel mailing list
> Tinyos-devel at Millennium.Berkeley.EDU
> https://mail.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-devel
> _______________________________________________
> Tinyos-devel mailing list
> Tinyos-devel at Millennium.Berkeley.EDU
> https://mail.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-devel

More information about the Tinyos-devel mailing list