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

Philip Levis pal at cs.stanford.edu
Sat Jun 23 10:07:45 PDT 2007

On Jun 23, 2007, at 5:37 AM, Matt Welsh wrote:

> 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.

This is absolutely true. Right now, TinyOS only has a very simple  
queue, whose interface is oriented towards internal component use  
rather than a data structure shared across components. David Moss is  
looking into a queue whose interfaces have a shared producer/consumer  
relationship in mind. I mean, I thought it was a big step forward  
when we even put a Queue interface into tos/interfaces. :)

The important thing is just that different queue semantics have  
different interfaces. The code using a queue that can reject items  
arbitrarily (from the perspective of an app) and the code using a  
queue which only rejects when full might be quite different.


More information about the Tinyos-devel mailing list