October 15th, 2009, 09:54 AM
Synchronized producer consumer on a circular buffer.
Hi to everybody,
I was told to move my post here.
I'd like to pass data between a producer and a consumer thread using a
"Data" here stands for fixed-length real-time video frames.
Doing a little research on Circular_buffer page on wikipedia (sorry, I can't post urls) , I discovered that:
These characteristics seems to suit my problem.
So, here are the requirements of my producer-consumer routine:
1. There is only one consumer and only one producer, and the buffer and
the items you can put on the buffer are fixed in size, so we can
generalize with, for example, an array of integer of length n, with n > 1.
2. The producer and the consumer are in different processes or threads, so they must be synchronized, i.e. the writer
can't write on a item position (slot) that the consumer is reading from and
3 The producer can be faster than the consumer or it can be slower. In general, who is slower at a given moment is completely random.
4 If the producer is slower, the consumer must wait until there is
something (at least an item) on the buffer.
5 If the producer is faster, the producer must not block when the
buffer is full, but it must overwrite older items in order, (except the one the
consumer is reading at the moment, see point 2). I want to stress this
point: the producer must not wait for the consumer to free an item,
but it must overwrite the oldest item in the buffer. In other words,
the producer must never block for n > 1.
I already have the solution for the blocking consumer, so please,
I'm not interested on it.
Can someone give me some hint on this problem? Or point me to a
concrete implementation? I tought these producer-consumer problems
were common in multimedia real time programming (where you must
overwrite, for example, old video or audio frames when the consumer is
slower), but I only can find the blocking producer implementations.
Please note my problem is not implementing a ring buffer: I can use a STD dqueue or a boost ringbuffer. My problem is: how to implement a producer consumer synchronized solution with these requirements?
October 15th, 2009, 11:28 AM
At sounds like you want a blocking queue, which is a concurrent data structure, with a minor modification to allow the producer to overwrite. A blocking queue uses a lock condition to allow thread notification and mutual exclusion. If the STD/boost implementations are not concurrent, you can add a wrapper that encapsolates your locking logic. Java's ArrayBlockingQueue is almost what you'd want, except that it can't directly replace the oldest but would require a poll() if the offer() failed.
I guess I'm confused as to what you're confused by! Its a simple exercise in locking.
October 15th, 2009, 02:30 PM
It's probably been done many thousands of times. It seems you are looking for code, not a general description of a solution, is that correct?
I no longer wish to be associated with this site.
October 15th, 2009, 05:46 PM
Not exactly, but a code example would be fine.
Originally Posted by jwdonahue
October 15th, 2009, 07:32 PM
Check out the ffmpeg source code: it uses a ring buffer.
It may help to view this as a state machine (from a design and not necessarily implementation perspective): map out all possible states and transitions.
If you want a "cheap" lock, you may want to implement something similar to the "spinlock" construct found in SQL Server.
Last edited by MadDogBrown; October 15th, 2009 at 07:34 PM.