[9fans] OT: cannonical set of queue ops - Plan9

This is a discussion on [9fans] OT: cannonical set of queue ops - Plan9 ; 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 ...

+ Reply to Thread
Results 1 to 6 of 6

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

  1. [9fans] OT: cannonical set of queue ops

    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

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

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

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

    >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

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

    On 12/6/06, LiteStar numnums 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.

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

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

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

    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

+ Reply to Thread