Boost logo

Boost Users :

Subject: Re: [Boost-users] [thread] multiple producers, single consumer - bosst-specific and generic questions
From: John Dlugosz (JDlugosz_at_[hidden])
Date: 2009-09-10 14:32:54


> Hello everyone!
> Thanks for all the help I already got. And excuse my poor
> understanding of
> of multithreading.
> I would like to implement a "multiple producer single consumer"
> pattern.
> My current solution is working with signals, which, I think is not very
> efficient. And also it doesn't work properly with the code I have, (see
> end of
> this mail). But besides that problem I have a generic question.
> If I worked with buffers and mutex, there are two choices, it seems:
> 1. Use one buffer, at the cost of deletion from the middle, when one
> producer
> terminates (so consumer won't communicate with a dead thread).
> 2. Have a buffer per producer, but also have a synchronisation per
> buffer and
> the consumer must look in several buffers, plus I don't know, how many
> producers there will be.
> This all should lead to a user interface, with different input-
> methods. So
> what would you suggest? It must be speedy and very CPU friendly.
> Thanks in advance for consideration. I'd also be happy for some
> suggested

That's a good point, in that having different queues for each thread would prevent contention there. But, with an unknown open-ended number of threads, I'd shy away from that.

I've developed (at work) a non-blocking and non-slow-atomic-instruction (I need a good term for that) queue that is the other way around -- one writer, many readers. But I've not had the chance to do the opposite. But much of what I learned can carry over.

You could use a ring buffer that the various writers access. Each does an atomic increment on the W index to obtain a unique index to use, and then populates that element of the buffer's array. The reader uses the R pointer to consume items. The trick is, you have several writers all filling their items at the same time, and the R comes along and tries to use one. The reader needs to know that the writer is done filling it. So, the reader sets a flag to indicate "not-ready" after it is done using it and before changing R. The writer populates the fields and then clears the flag, indicating "ready", last. Now the reader knows to wait if it gets to an element where the flag is still set, even though W has moved ahead.

To preserve the atomicness of the increment-and-read, the W is always incrementing, and never resets. Instead, the writer has to do the modulo of the ring buffer size when it uses it.

The other hard part is watching for empty or full states. Decide how to tell them apart, and how to test for them asynchronously and without possibility of a deadlock.

The one I just did like that is specialized, and will never be full. I just sized the buffer to know how many entries are even possible in my application.

Let me know if you want to discuss it further.

--John

TradeStation Group, Inc. is a publicly-traded holding company (NASDAQ GS: TRAD) of three operating subsidiaries, TradeStation Securities, Inc. (Member NYSE, FINRA, SIPC and NFA), TradeStation Technologies, Inc., a trading software and subscription company, and TradeStation Europe Limited, a United Kingdom, FSA-authorized introducing brokerage firm. None of these companies provides trading or investment advice, recommendations or endorsements of any kind. The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer.


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net