Producer/Consumer Problem
Chaim Ackerman
I've got 1 producer and N consumers for the same resource.
Here's the scheme for making sure the consumers are
finished with the resource before the producer can get it.
The resource starts with sema_init() set to N.
Each time the producer starts doing his thing,
he calls sema_wait() N times in a tight loop to acquire it.
Every consumer, when he's finished, calls sema_post() once to give it back.
When the N'th consumer finishes, the producer can get it again.
Analysis:
Each sema_post() by a consumer trivially moves the producer
through one loop iteration of sema_wait() until the semaphore
hits 0, and the producer can start producing again.
Problem 1: It seems like a waste of N-1 system calls.
===== One more question ======
When the producer finishes producing, it's even worse.
Here's the scheme for making sure the producer is
finished with the resource before the consumers can get it.
Each of the N consumers calls sema_wait() waiting for the producer to finish.
When finished, the producer sits in a loop on a semaphore
calling sema_post() N times to let all the consumers begin.
Problem 2: Besides the N-1 seemingly wasted system calls,
every time the producer's sema_post() gets called,
it might start one consumer who calls sema_wait() and none of the other
consumers get called until the producer works its way through its loop!
================
Problem 1 doesn't bother me as much as Problem 2.
Another way to reword P1: Is there an "express" way to wait on a resource?
And for Problem 2: Is there an "express" way to give back resources?
The real problem is that I think there may be a better way to do this.
I've considered condition variables, but there are a lot of added system calls
for the mutexes. Even with the loops around sema_wait() and
sema_post(), they seem more efficient than condition variables.
Chaim Ackerman
IDT Corp.
Net2Phone Development
c...@net2phone.com
Joe Seigh
You need two separate semphores. One for consumer resources and the other
for producer resources.
|> ================
|> Problem 1 doesn't bother me as much as Problem 2.
|>
|> Another way to reword P1: Is there an "express" way to wait on a resource?
|> And for Problem 2: Is there an "express" way to give back resources?
|>
|> The real problem is that I think there may be a better way to do this.
|> I've considered condition variables, but there are a lot of added system calls
|> for the mutexes. Even with the loops around sema_wait() and
|> sema_post(), they seem more efficient than condition variables.
Stay away from semaphores. While they may seem useful in that the
semaphore count corresponds to the "number" of resources, they aren't.
The semaphore will only tell you the resource is available.
You still have to be able to safely access the shared resource and
that will require a mutex. Given that you have to use a mutex
anyhow, you'd be much better off using condition variables. producer/consumer
is classic constraint driven programming. The mutex guarded region
you are doing your wait in also lets you safely access the resource.
In pseudo java the logic would go
// producer
synchronized(emptyQueue) { // mutex_lock
while (emptyQueue.empty()) {
emptyQueue.wait();
}
buf = emptyQueue.dequeue(); // remove resource
}
// use resource
synchronized(fullQueue) {
fullQueue.enqueue(buf);
fullQueue.notifyAll();
}
vice versa for consumer
The semphore version would go
// producer with semphores
emptyQueueSemphore.sem_wait();
synchronized(emptyQueue) {
buf = emptyQueue.dequeue();
}
// use resource
synchronized(fullQueue) {
fullQueue.enqueue(buf);
}
fullQueue.sem_post();
The difference between the two may seem moot but it isn't.
The condition variable version is more robust. It's less likely
to get queue underflow since the queue is being tested directly.
The semaphore version requires the semphore be initialized with
the exact number of buffers initially on the queue. It also
requires all operations on the queue be closely coupled with
the semphore and that no race conditions exist. If the queue
ever gets out of sync with the semphore, you're toast.
The condition variable version is also more general. You just
state the constraint or condition directly. With semphores
you have to map the condition to an integer expression. The
logic for doing this can get pretty contorted at times.
Also advanced thread programmers can do things with condition
variables that have no equivalent in semaphores, e.g. you
can dequeue all the available buffers with a most one call
to wait(). You can't do that with at most one call to sem_wait()
in a semaphore version.
Joe Seigh