Concurrent Priorit Queues

[Tim McIver]

Hello,

I took the class at MIT last summer. It was great; thanks! I have a
project that is very parallelizable and I'm looking for some advice.
I believe I'm dealing with a fairly typical producer-consumer issue.
I want to have many separate producers placing ordered data into a
concurrent priority queue and a single consumer removing data from
it. I have a fear that the consuming thread will remove data when
there are gaps in it because I assume that there is no guarantee that
the data in the queue will not have gaps. My first thought was to
make the consuming thread wait if there were less than some minimum
number of data elements in the queue. The problem then becomes: how
can the consuming thread ever finish if it is blocked before the
priority queue is empty?

[Jason Swearingen]

A bit of a disclaimer first: I don't know really what your problem is (For example if I fully understood it, the best answer might be to rearchitect)  and second I am a self-taught async architect so there are probably gaps in my logic others may be more capable of helping with.  Thirdly, I'm a .NET developer so you'll have to translate my suggestions to whatever language you deem needed.

That said,  I think an "easy" solution to the problem you described is for your producer to set a magic variable "isDone==true;" when it's finished. The consumer can spin if it waits for too long, and during the spin it can check the value of .isDone.  and if isDone==true, it knows it should consume all remaining input, ignoring your "required buffer"

Another potential solution is for your consumer to consume as fast as possible, but setup your "sub-packets" in a way so that the consumer can identify if a packet is incomplete, and not actually "process" the sub-packets until it gets everything needed.

Another suggestion would be to make each enqueue atomic, and not split your packets so the consumer doesnt have the additional complexity of determining "data gaps" from the enqueued data.




And finally, maybe there is a more sexy way of using a waitEvent instead of isDone (for example, AutoResetEvent will allow 1 consumer through per producer .Set() call)  but that is up to you to decide.

hope that helps!


--
- Jason

================================
Jason Swearingen  Executive Director: Novaleaf Game Studios
--------------------------------------------------------------
Jas...@Novaleaf.com  Cell: +66-089-775-0111
Office: +66-02-234-3031  Fax: +66-02-234-3032
================================

[Tim McIver]

Thanks Jason. That does help. I was also thinking of some kind of
"isDone" flag. I don't love that solution because it requires global
data accessible to both producers and consumers and since I want many
producers, it would have to be true when they are ALL done (perhaps by
ORing). I like your suggestion of ensuring that the data isn't enqued
out of order and I think I could do that by simply numbering them.

Thanks for the input.

Tim