[9fans] OT: cannonical set of queue ops

[9fans] OT: cannonical set of queue ops

[Steve Simon]

Hi,

Bit off topic

In an embedded system, we are trying to wrap up the specifics
of the RTOS we use and abstract it a little so we can switch
OS later (to a cheaper one :-)

We are therefore trying to come to a cannonical API, the only
part of this we are having problems are interlocked queues.

These are queues which the reader blocks if they are empty and
the writer blocks if full. They have an option for a timeout
which can be -1 to indicate forever or 0 for poll.

We have found a need for a either IsQueueEmpty() or PeekQueueHead()
entrypoint - a network driver is closing a connection a cleanup thread
needs to poll the queue so it can deallocate it once all the remaining data
has drained; we cannot just read the queue to see if its empty as this will
remove the head entry if there is one.

This is the one and only place we seem to need this so we are worried.

Are we suffering from a lack of vision, or is some way of checking the
number of items on a queue inevitable?

-Steve

Re: [9fans] OT: cannonical set of queue ops

[Richard Bilson]

> Are we suffering from a lack of vision, or is some way of checking the
> number of items on a queue inevitable?

The problem with these sorts of functions is that the results that
they give can't, in general, be used for much. For instance, if
IsQueueEmpty returns "true", that answer isn't worth very much if, by
the time you act on that information, some other thread could have
added an item to the queue.

They're dangerous functions to have around, since often people will be
tempted to use them inappropriately, relying on the answer even where
the potential exists for other threads to perform concurrent
operations on the same queue. But there are certainly cases where
their use is appropriate, and it sounds like you have one of those
cases here (assuming no thread or interrupt handler is going to add
more items to the queue as it drains).

In summary: it can be useful to have such a function, but it probably
won't (and shouldn't) be used often.

Re: [9fans] OT: cannonical set of queue ops

[LiteStar numnums]

>For instance, if IsQueueEmpty returns "true", that answer isn't worth
very much if, by
> the time you act on that information, some other thread could have
> added an item to the queue.

Wouldn't it be natural for such a function to block the active thread
until the desired
result is achieved? Since this clean up thread wouldn't really need to
be on a hard deadline, wouldn't WaitQueueEmpty make more sense then a
IsQueueEmpty? The writer may be more difficult, but again, if the
Queue is full, it must wait anyway, so blocking here wouldn't be too
problematic, methinks.

-- 
If work and leisure are soon to be subordinated to this one utopian
principle -- absolute busyness -- then utopia and melancholy will come
to coincide: an age without conflict will dawn, perpetually busy --
and without consciousness.

 -- Günter Grass

Re: [9fans] OT: cannonical set of queue ops

[Richard Bilson]

On 12/6/06, LiteStar numnums <litestar@gmail.com> wrote:
> >For instance, if IsQueueEmpty returns "true", that answer isn't worth
> very much if, by
> > the time you act on that information, some other thread could have
> > added an item to the queue.
>
> Wouldn't it be natural for such a function to block the active thread
> until the desired
> result is achieved? Since this clean up thread wouldn't really need to
> be on a hard deadline, wouldn't WaitQueueEmpty make more sense then a
> IsQueueEmpty? The writer may be more difficult, but again, if the
> Queue is full, it must wait anyway, so blocking here wouldn't be too
> problematic, methinks.

You could do that as well, but that doesn't address the fundamental
problem that I was pointing out regarding IsQueueEmpty: once you wake
up you don't really know anything about the state of the queue, unless
you are sure that no other thread could be adding items. All you know
in general is that the queue was recently empty.

I agree with you that it's usually better to block than to busy-wait.

Re: Re: [9fans] OT: cannonical set of queue ops

[David Leimbach]

> I agree with you that it's usually better to block than to busy-wait.
>

Oh how I wish most of the world understood the benefits of overlapping
I/O and computations.  Low latency appears to be a win when polling,
but being able to do more than one thing (even in a pseudo-sense) at a
time is often a huge win a lot of times.

Doing I/O as fast as possible for the sake of doing I/O as fast as
possible is sometimes not so important if you can schedule work tasks
to overlap the I/O.  Then I/O overheads can even sometimes be almost
completely masked out.

But we just gotta win those microbenchmarks!!

Re: [9fans] OT: cannonical set of queue ops

[Russ Cox]

I have had a similar problem in some applications
I have written using venti.  As Richard Bilson points out,
the tempting solution is not the best one.

I think that you want to have an explicit "no more sending will happen"
state, the same as a pipe where one end has been closed.
Then the receiving end can get the "EOF" once it has read the
remaining items and can close its side.  Once both sides are closed,
the queue is freed.

There are various ways you could frame things (for example,
you could require that the write side is always closed before
the read side), but no matter what you always end up with
a two-step: first the writer signals he is done (could write an
empty message instead), then the reader cleans up when he
sees he has gotten everything.  Can hide in a library or handle
explicitly.

One reason that having an IsQueueEmpty complicates things is
that allowing the *writer* to check whether the *reader* has gotten
all the messages yet causes information to flow backward
(from reader to writer).

Russ