Date: Thu, 15 May 2008 23:56:18 +0300 From: Andriy Gapon <avg@icyb.net.ua> To: davids@webmaster.com Cc: freebsd-stable@freebsd.org, freebsd-threads@freebsd.org Subject: Re: thread scheduling at mutex unlock Message-ID: <482CA372.3000400@icyb.net.ua> In-Reply-To: <MDEHLPKNGKAHNMBLJOLKIEKLMKAC.davids@webmaster.com> References: <MDEHLPKNGKAHNMBLJOLKIEKLMKAC.davids@webmaster.com>
next in thread | previous in thread | raw e-mail | index | archive | help
on 15/05/2008 22:29 David Schwartz said the following: >> what if you have an infinite number of items on one side and finite >> number on the other, and you want to process them all (in infinite >> time, of course). Would you still try to finish everything on one >> side (the infinite one) or would you try to look at what you have >> on the other side? >> >> I am sorry about fuzzy wording of my original report, I should have >> mentioned "starvation" somewhere in it. > > There is no such thing as a "fair share" when comparing an infinite > quantity to a finite quantity. It is just as sensible to do 1 then 1 > as 10 then 10 or a billion then 1. > > What I would do in this case is work on one side for one timeslice > then the other side for one timeslice, continuuing until either side > was finished, then I'd work exclusively on the other side. This is > precisely the purpose for having timeslices in a scheduler. > > The timeslice is carefully chosen so that it's not so long that you > ignore a side for too long. It's also carefully chosen so that it's > not so short that you spend all your time switching swides. > > What sane schedulers do is assume that you want to make as much > forward progress as quickly as possible. This means getting as many > work units done per unit time as possible. This means as few context > switches as possible. > > A scheduler that switches significantly more often than once per > timeslice with a load like this is *broken*. The purpose of the > timeslice is to place an upper bound on the number of context > switches in cases where forward progress can be made on more than one > process. An ideal scheduler would not switch more often than once per > timeslice unless it could not make further forward progress. > > Real-world schedulers actually may allow one side to pre-empt the > other, and may switch a bit more often than a scheduler that's > "ideal" in the sense described above. This is done in an attempt to > boost interactive performance. > > But your basic assumption that strict alternation is desirable is > massively wrong. That's the *worst* *possible* outcome. David, thank you for the tutorial, it is quite enlightening. But first of all, did you take a look at my small test program? There are 1 second sleeps in it, this is not about timeslices and scheduling at that level at all. This is about basic expectation about fairness of acquiring a lock at macro level. I know that when one thread acquires and releases and reacquires a mutex during 10 seconds while the other thread is blocked on that mutex for 10 seconds, then this is not about timeslices. -- Andriy Gapon
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?482CA372.3000400>