#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2009
    Posts
    5
    Rep Power
    0

    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
    circular buffer,.

    "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:

    An example that could possibly use an overwriting circular buffer is with multimedia. If the buffer is used as the bounded buffer in the producer-consumer problem then it is probably desired for the producer (e.g., an audio generator) to overwrite old data if the consumer (e.g., the sound card) is unable to momentarily keep up.
    [...]
    Use a Fill Count The second simplest solution [to tell an empty from a full buffer] is to use a fill count. The fill count is implemented as an additional variable which keeps the number of readable bytes in the buffer. This variable has to be increased if the write (end) pointer is moved, and to be decreased if the read (start) pointer is moved. In the situation if both pointers pointing at the same location, you consider the fill count to distinguish if the buffer is empty or full.
    * Note: When using semaphores in a Producer-consumer model, the semaphores act as a fill count.
    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
    vice versa.

    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?

    Many thanks,
    Kind regards,

    Chris.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Jul 2005
    Location
    Bay Area, California
    Posts
    841
    Rep Power
    1681
    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.
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    May 2004
    Posts
    3,417
    Rep Power
    886
    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.
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2009
    Posts
    5
    Rep Power
    0
    Originally Posted by jwdonahue
    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?
    Not exactly, but a code example would be fine.
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Mar 2009
    Posts
    837
    Rep Power
    527
    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.

IMN logo majestic logo threadwatch logo seochat tools logo