views:

551

answers:

1

Hi everybody,

Let's say I have two buffers. Producer fills buffer #1, then fills buffer #2. The consumer consumes one buffer a time, and it's very slow. While it is consuming buffer #1, the producer is ready to fill another buffer, but they are all full, and the consumer hasn't finished yet with #1. So, the producer waits.

Instead of waiting, I want the producer to update the "free" buffer. That is, while the consumer is consuming buffer #1, the producer should write new data on buffer #2 as soon as it has it ready (the "old" data is overwritten and lost). If the consumer hasn't finished yet with #1, and the producer has more data to write, it should write again on #2, and so on. When the consumer finally consumes all the data in #1, it should immediately start to consume the freshly-written data in buffer #2, and the producer should keep on updating #1.

(imagine the producer is acquiring video frames in realtime at high speed, while the consumer is slowly elaborating them; the consumer doesn't mind if it skips some frame, but it must always process the last frame acquired. The producer, instead, cannot slow down nor wait, because it must acquire every frame).

Is there a way to do this kind of thing with semaphores? Is it a well- known concurrency problem? And, in case, is it possible to extend this problem to n > 2 buffers?

Thanks!

A: 

Well, you could just have a buffer(queue) of buffers. Some type of synchronized queue structure to determine which buffers are being used. This would work for n >= 2 buffers.

I guess it would work like this: Producer starts writing to buffer 1, but doesn't remove it from the queue. Consumer starts consuming from buffer 1, and removes it from the queue. Once buffer 1 is full, the producer checks the queue to see which buffers are available, and it sees only buffer 2 is available. The producer starts writing to buffer 2. When buffer 2 is full, it will check the queue again and see that buffer 2 is still available, so it will write to it again. Once the consumer is done with buffer 1, it will remove buffer 2 from the queue and place buffer 1 back. Once the producer is done with 2, it will see only buffer 1 is available and start writing to it. I hope this is what you were describing. (I don't like dealing with just semaphores, I prefer to use higher data structures, eg. queues).

To deal with multiple producers, introduce another queue to determine which buffers are being used by a producer. So now you will have a producer queue and a consumer queue, and I think that handles all your situations.

CookieOfFortune
Unluckily, I need the solution also for the case n = 2 buffers (when the buffers are very large and the memory is not, I could be forced to use just two buffers, at the expense of consumer speed).
janesconference
I added some edits that might help.
CookieOfFortune