From owner-freebsd-threads@FreeBSD.ORG  Fri May 16 20:35:55 2008
Return-Path: <owner-freebsd-threads@FreeBSD.ORG>
Delivered-To: freebsd-threads@freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34])
	by hub.freebsd.org (Postfix) with ESMTP id 53099106567A;
	Fri, 16 May 2008 20:35:55 +0000 (UTC)
	(envelope-from bright@elvis.mu.org)
Received: from elvis.mu.org (elvis.mu.org [192.203.228.196])
	by mx1.freebsd.org (Postfix) with ESMTP id 2B72D8FC2C;
	Fri, 16 May 2008 20:35:55 +0000 (UTC)
	(envelope-from bright@elvis.mu.org)
Received: by elvis.mu.org (Postfix, from userid 1192)
	id 7BDE41A4D8D; Fri, 16 May 2008 13:15:55 -0700 (PDT)
Date: Fri, 16 May 2008 13:15:55 -0700
From: Alfred Perlstein <alfred@freebsd.org>
To: Andriy Gapon <avg@icyb.net.ua>
Message-ID: <20080516201555.GL32532@elvis.mu.org>
References: <482B0297.2050300@icyb.net.ua> <482BBA77.8000704@freebsd.org>
	<482BF5EA.5010806@icyb.net.ua>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <482BF5EA.5010806@icyb.net.ua>
User-Agent: Mutt/1.4.2.3i
Cc: Daniel Eischen <deischen@freebsd.org>, David Xu <davidxu@freebsd.org>,
	Brent Casavant <b.j.casavant@ieee.org>, freebsd-threads@freebsd.org
Subject: Re: thread scheduling at mutex unlock
X-BeenThere: freebsd-threads@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Threading on FreeBSD <freebsd-threads.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-threads>, 
	<mailto:freebsd-threads-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-threads>
List-Post: <mailto:freebsd-threads@freebsd.org>
List-Help: <mailto:freebsd-threads-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-threads>,
	<mailto:freebsd-threads-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Fri, 16 May 2008 20:35:55 -0000

[[ -stable removed, additional cc' to interested parties ]]

Guys,

Andriy's issue appears to actually be severe.

The main issue is that we have a starvation situation for heavily
contended mutexes.

If I am reading the test case, any heavily contented mutex will
exhibit this problem.

You do NOT need a sleep(3) call to provoke it, you just need the
following scenario:

thread A:
10:
  gets mutex
  does heavy processing (N (99%) of its time)
  releases mutex
  does something else (M (1%) of the time)
  goto 10;

thread B...:
  tries to get mutex...
  do not care.


The way that scheduling works means that you can do a back of a
napkin calculation to figure out that this sort of situation will
certainly starve threads without some support from the underlying
locking mechanism to fix it.

Let's say that that "thread A" spends N (99%) of it's time doing
"heavy processing" then that means that only M (1%) of the time the
scheduler will preempt it at the correct time so that it is not
holding the lock.

Clearly this will lead to starvation where "thread A" has a
99% chance per-quantum of being left holding the lock when it
is preempted.

I think it's time that people look into the so-called "working"
implementations (linux/solaris) for ways to handle this sort of
thing.

. <- that's a period.

-Alfred