pthread_{mutex,cond} & fifo/starvation/scheduling policy

[Pieter de Goeje]

On Thursday 21 January 2010 11:27:23 Bernard van Gastel wrote:
> In real world application such a proposed queue would work almost always,
>  but I'm trying to exclude all starvation situations primarily (speed is
>  less relevant). And although such a worker can execute it work and be
>  scheduled fairly, the addition of the work to the queue can result in
>  starvation (one of the threads trying to add to the queue could stall
>  forever if the lock is heavily contested).

This is not possible. The worker threads unlock the mutex during 
pthread_cond_wait(). So when the queue is empty, threads can add new items 
without blocking.

So for a worker we have:
while(1) {
pthread_mutex_lock(&m)
while(queue_empty()) {
	// this atomically unlocks and locks the mutex
	pthread_cond_wait(&c, &m)
}
w = fetch_work();
pthread_mutex_unlock(&m);
do_work(&w);
}

And a provider does this:
pthread_mutex_lock(&m);
add_work(&w);
pthread_cond_signal(&c);
pthread_mutex_unlock(&m);

- Pieter de Goeje