Producer-Consumer problem, but the producer updates the old buffers.
janesco...@gmail.com
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 reading 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.
This scenery may sound a little strange, but imagine the producer is
acquiring video frames from a CCD 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
all the frames.
Is there a way to do this kind of thing with semaphores? Is it a well-
known concurrency scenario? And, in case, is it possible to extend
this problem to n > 2 buffers?
Thanks,
Chris.
Eric Sosman
It sounds straightforward, unless I'm failing to understand
something. I think you can do it with any plural number of
buffers (but I'd recommend at least three) and a pair of queues,
one for "filled" buffers and one for "empty" buffers:
Consumer: Remove the first buffer from the "filled" queue
(if there isn't one yet, wait). Process the buffer, then
append it to the "empty" queue. Repeat.
Producer: Remove the first buffer from the "empty" queue.
If there isn't one, remove the first (oldest) buffer from
the "filled" queue. Fill the buffer (wherever it came from),
then append it to the "filled" queue. Repeat.
janesco...@gmail.com
to use posix-semaphores).
On 4 Giu, 22:56, Eric Sosman <Eric.Sos...@sun.com> wrote:
Eric Sosman
make sense of a discussion that runs backwards.
By the way, top-posting is really annoying, because it's hard to
semaphore. When it's finished adding or removing a buffer, sem_post().
consumer wants access to the queue, do a sem_wait() on the appropriate
for each queue, initialized to one. When either the producer or the
So go ahead and use them; nobody's stopping you. Use one semaphore
janesco...@gmail.com
Surinder Singh
Hi Chris,
let FQ is a FIFO Q of size N
LQ is lock to protect integrity of FQ by
SEMC is a semaphore used as counting semaphore set to 0
send on FQ blocks if full, recv blocks if empty
--- producer thread:
1: prepare buffer msg
2: lock LQ
3: try non blocking send to FQ
if (send msg fails)
recv message from FQ and keep in msgx
try non blocking msg send to FQ
if (resend msg fails)
drop the msg
else
sem_post(&SEMC)
endif
else
sem_post(&SEMC)
endif
4: unlock LQ
5: free msgx memory if any ; msgx = null
6: go to 1
--- consumer thread:
1: lock LQ
2: recv msg in non blocking manner
3: if (recv msg fails)
unlock LQ
sem_wait(&SEM)
goto 1
endif
4: unlock LQ
5: process msg
6: goto 1
if you use SYSV Q (msgget) or posix Q (mq_open),
you do not need explicit lock LQ as they do
required synchronization inside the API/implementation.
consumer thread will be much simpler with either.
1. recv msg in blocking manner
2: consume msg ; goto 1
Thanks
- Surinder
--
My writings here has nothing to do with my employer Vegayan Systems.
Surinder Singh
FQ is a FIFO Q of size N
LQ is lock to protect integrity of FQ
SEMC is a posix semaphore to signal putting of msg to waiter
--- producer thread:
1: prepare buffer msg
2: lock LQ
3: try non blocking send to FQ
if (send msg fails due to qfull)