From owner-freebsd-hackers@FreeBSD.ORG  Thu Jan 21 11:47:18 2010
Return-Path: <owner-freebsd-hackers@FreeBSD.ORG>
Delivered-To: freebsd-hackers@freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34])
	by hub.freebsd.org (Postfix) with ESMTP id 9555C106566C
	for <freebsd-hackers@freebsd.org>; Thu, 21 Jan 2010 11:47:18 +0000 (UTC)
	(envelope-from pdegoeje@service2media.com)
Received: from s2m-is-001.service2media.com (rev-130-102.virtu.nl
	[217.114.102.130])
	by mx1.freebsd.org (Postfix) with ESMTP id 2F0548FC1C
	for <freebsd-hackers@freebsd.org>; Thu, 21 Jan 2010 11:47:17 +0000 (UTC)
Received: from pieter-dev-linux.localnet ([10.0.1.77] RDNS failed) by
	s2m-is-001.service2media.com with Microsoft SMTPSVC(6.0.3790.3959); 
	Thu, 21 Jan 2010 12:35:10 +0100
From: Pieter de Goeje <pieter@service2media.com>
Organization: Service2Media
To: freebsd-hackers@freebsd.org
Date: Thu, 21 Jan 2010 12:35:10 +0100
User-Agent: KMail/1.12.2 (Linux/2.6.31-17-generic; KDE/4.3.2; i686; ; )
References: <71A129DC-68A0-46C3-956D-C8AFF1BA29E1@bitpowder.com>
	<20100119184617.GB50360@dan.emsphone.com>
	<1B4E9B02-AA63-45BF-9BB7-3B0A2884CCB0@bitpowder.com>
In-Reply-To: <1B4E9B02-AA63-45BF-9BB7-3B0A2884CCB0@bitpowder.com>
MIME-Version: 1.0
Content-Type: Text/Plain;
  charset="utf-8"
Content-Transfer-Encoding: 7bit
Message-Id: <201001211235.10129.pieter@service2media.com>
X-OriginalArrivalTime: 21 Jan 2010 11:35:10.0715 (UTC)
	FILETIME=[CA3704B0:01CA9A8D]
X-Mailman-Approved-At: Thu, 21 Jan 2010 12:39:03 +0000
Cc: Dan Nelson <dnelson@allantgroup.com>
Subject: Re: pthread_{mutex,cond} & fifo/starvation/scheduling policy
X-BeenThere: freebsd-hackers@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Technical Discussions relating to FreeBSD
	<freebsd-hackers.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>, 
	<mailto:freebsd-hackers-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-hackers>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Help: <mailto:freebsd-hackers-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>,
	<mailto:freebsd-hackers-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Thu, 21 Jan 2010 11:47:18 -0000

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