David Schwartz davids at webmaster.com
Thu May 15 19:30:18 UTC 2008

```> 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.

DS

```