Gauche Devlog

< Looking for alternative read-time constructor syntax | Bitten by floating point numbers again >

2011/01/07

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 <mtqueue> (ref:util.queue) I defined the range of mtqueue-max-length 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, an <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 dequeue/wait! unless there's a producer thread waiting on enqueue/wait!. A producer thread would block on enqueue/wait! unless there's a consumer thread waiting on dequeue/wait!.

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---enqueue/wait! blocks when the queue is full, and dequeue/wait! blocks 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 <mtqueue> with zero max-length, and will be better to have it than to have different synchronization primitives. Since <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 <mtqueue>.

Tags: util.queue, mtqueue, threads

Past comment(s)

Colton (2014/03/04 09:50:19):

Hello good day http://obutsonline.org/buyzithromax/ zithromax q-fever 7. Include a follow-up plan (interval and frequency)

 

Elijah (2014/03/05 03:15:48):

One moment, please http://www.nexlevsolutions.com/buyvigora/ buy vigora online MV Override – vacation supply (still subject to rules surrounding Vacation Supplies, see section 5)

 

Amelia (2014/03/05 04:12:13):

It's serious http://www.thedivinecomedy.org/buyfloxin/ floxin otic obtain emergency counseling and treatment, at their own expense, at

 

Wyatt (2014/03/05 05:07:45):

This site is crazy :) http://actionplumbingandheating.ca/buyacbilify/ 2mg abilify depression " Failure to offer negotiated prices: Occurs when a pharmacy does not offer a beneficiary the

 

Hayden (2014/03/05 16:59:08):

Have you got a current driving licence? http://georgiapioneers.com/buywellbutrin/ wellbutrin sr 150 price therapy and disease management · Construct an organized, · Critically appraise a clinical trial

 

Caleb (2014/03/05 16:59:10):

Canada>Canada http://fr.nigelkeay.com/buyvoltaren/ generic for voltaren diseases along with endless cases of HIV/AIDS. You will also see many familiar

 

Angel (2014/03/05 19:49:40):

Will I have to work on Saturdays? http://marshazart.com/buybimatoprost/ buy bimatoprost online (201-B1) as an NPI number to be used after August 31,

 

Ariana (2014/03/21 19:51:22):

I wanted to live abroad http://www.smartpraxis.com/index.php/beneficios/ mebendazole 100 mg Rarely respects the culture of others. Usually respects the

 

Emily (2014/04/17 08:10:08):

How much is a First Class stamp? http://braeburnsoftware.com/to-play-baccarat/ play baccarat online for fun Timely submission of the preceptor/site evaluation form is considered a practice experience

 

Post a comment

Name: