Queue of zero length
Does it make sense to have a queue whose maximum length is zero?
I thought it didn't, so when I wrote
(ref:util.queue) I defined the range of
be one or more. (Zero means the queue has unlimited length,
which is a bit kludgy in retrospect).
A queue with zero max length would be always empty and full.
It seemed that it'd be no use.
Now it occurs me that actually it may be useful as a synchronization device.
The multi-thread queue
<mtqueue> can be used to synchronize
consumer threads and producer threads. A consumer thread blocks on
dequeue/wait! when there's no data in the queue, and unblocks
when some data is put in the queue.
A producer thread blocks on
enqueue/wait! when the queue is
full, and unblocks when the data in the queue is consumed and
there is some room in it. So,
<mtqueue> with max-length == 1 can be used as
a synchronizing variable, like
MVar in Haskell.
If we had an
<mtqueue> with max-length == 0, how would it
work? A possible behavior would be as follows:
A consumer thread would block on
unless there's a producer thread waiting on
A producer thread would block on
there's a consumer thread waiting on
That is, it allows passing data from the producer to the consumer directly, without putting the data into a buffer.
It can be useful, since once a piece of data is put in the queue, it is left untouched until a consumer consumes it. When there's something happens in consumer threads, such that all of them are taking extremely long computation, the queued data will be held in the queue indefinitely. If you want to guarantee that a piece of data is either processed timely or otherwise timeout, you need to put a separate logic to watch the queue.
With a zero-length queue, the producer can set timeout, so it is easy to implement the behavior to timeout when consumers are busy.
This is a kind of special interpretation of the behavior of
<mtqueue>. With a simple definition---
blocks when the queue is full, and
when the queue is empty---a straightforward interpretation
is that both enqueue and dequeue always block and do nothing
useful. So it is arguable that we should provide a different
data structure for this non-buffering synchronization.
Besides, the current implementation interpretes zero max-length as "unlimited length". It would be an incomaptibile change if we support zero-length queue.
I'm still undecided, but for now, I feel non-buffering synchronization
is a natural extension for the behavior of
and will be better to have it than to have different synchronization
<mtqueue> was just introduced in 0.9.1,
it may be not too late to change it.
However, I might be overlooking something. I'm open for discussion. Also I'm curious if other implementations/languages have this non-buffering synchronization primitives.
(Added on 2011/01/08 01:17:47 UTC): Rui pointed me Java's
SynchronousQueue. This is probably
the same as I expect in zero-length mtqueue. In Java it appears
its tradition to separate classes if implementations differ,
but in Gauche I think it's more natural to implement it as
an extention of existing
Tags: util.queue, mtqueue, threads