Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

From: Nick Piggin (
Date: Mon Feb 10 2003 - 02:39:18 EST

Andrea Arcangeli wrote:

>On Mon, Feb 10, 2003 at 01:42:28AM -0200, Rik van Riel wrote:
>>On Sun, 9 Feb 2003, Andrea Arcangeli wrote:
>>>The only way to get the minimal possible latency and maximal fariness is
>>>my new stochastic fair queueing idea.
>>"The only way" ? That sounds like a lack of fantasy ;))
>you can do more but you'd need to build additional APIs, to allow the
>highlevel (possibly userspace too) to give hints to the lowlevel.
>This only requires the pid and checking current->mm which is trivial. So
>without adding a complex API I think this is the best/only thing you can
>do to get close to the minimal possible I/O latency from a process point
>of view.
>>On the contrary, once we have SFQ to fix the biggest elevator
>>problems the difference made by the anticipatory scheduler should
>>be much more visible.
>>Think of a disk with 6 track buffers for reading and a system with
>>10 active reader processes. Without the anticipatory scheduler you'd
>>need to go to the platter for almost every OS read (because each
>>process flushes out the track buffer for the others), while with the
>>anticipatory scheduler you've got a bigger chance of having the data
>>you want in one of the drive's track buffers, meaning that you don't
>>need to go to the platter but can just do a silicon to silicon copy.
>>If you look at the academic papers of an anticipatory scheduler, you'll
>>find that it gives as much as a 73% increase in throughput.
>>On real-world tasks, not even on specially contrived benchmarks.
>>The only aspect of the anticipatory scheduler that is no longer needed
>>with your SFQ idea is the distinction between reads and writes, since
>>your idea already makes the (better, I guess) distinction between
>>synchronous and asynchronous requests.
>I'm not saying anticipatory scheduling is going to be obsoleted by SFQ,
>especially because SFQ has to be an option to use only when absolutely
>your only care to get the lowest possible I/O latency from a per-process
>point of view (like while playing an mpeg or mp3).
>But I still definitely think that if you run an anticipatory scheduling
>benchmark w/ and w/o SFQ, the effect w/o SFQ (i.e. right now) is going
>to be much more visible than w/ SFQ enabled. The reason is the size of
>the queue that w/o SFQ can be as large as several seconds in time and
>several dozen mbytes in bytes.
You are addressing a fundamentally different problem. In the 2.5
elevator we can have whatever queue size we like. I get great
contest results with a 8192 request queue size. We track each
request submission time so we can impose a soft upper limit on
service times which provides fine latency, and the sync nature
of reads ensures pretty good fairness.

What your scheduler is good for obviously is providing a much
stronger per process fairness solution which is obviously very
useful for some tasks.

The problems each are trying to solve are different. I don't
think your idea solves anything that anticipatory scheduling
solves (tries to).


To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

This archive was generated by hypermail 2b29 : Sat Feb 15 2003 - 22:00:25 EST