Re: stochastic fair queueing in the elevator [Re: [BENCHMARK]

[Rik van Riel]

On Mon, 10 Feb 2003, Nick Piggin wrote:
> Andrea Arcangeli wrote:
>
> >The only way to get the minimal possible latency and maximal fariness is
> >my new stochastic fair queueing idea.
>
> Sounds nice. I would like to see per process disk distribution.

Sounds like the easiest way to get that fair, indeed.  Manage
every disk as a separately scheduled resource...

> However dependant reads can not merge with each other obviously so
> you could end up say submitting 4K reads per process.

Considering that one medium/far disk seek counts for about 400 kB
of data read/write, I suspect we'll just want to merge requests or
put adjacant requests next to each other into the elevator up to
a fairly large size. Probably about 1 MB for a hard disk or a cdrom,
but much less for floppies, opticals, etc...

> But your solution also does nothing for sequential IO throughput in
> the presence of more than one submitter.

> I think you should be giving each process a timeslice,

That is the anticipatory scheduler.  A good complement to the SFQ
part of the IO scheduler.  I'd really like to see both ideas together
in one scheduler, they sound like a winning pair.

> For reads, anticipatory scheduling can be very helpful in theory
> however it remains to be seen if I can make it work without adding
> too much complexity. Your fair queueing should go nicely on top
> if I can make it work. I do like your idea though!

The anticipatory scheduler can just remain "on" while the priority
difference of the requests of the current process aren't too big
when compared to the priority of the other requests.  Once the SFQ
part of the scheduler sends down requests with a really big priority
difference the anticipatory scheduler can "skip a beat" and switch
to another process.

Note that Andrea's distinction between synchronous and asynchronous
requests may be more appropriate than the distinction between read
and write requests ...

The only remaining question is how do we know which requests are
synchronous and which are asynchronous ?   Ie. which requests have
a process waiting on their completion and which requests don't have
a process waiting on their completion ?

regards,

Rik
-- 
Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/		http://guru.conectiva.com/
Current spamtrap:  <a href=mailto:"[e-mail]">[e-mail]</a>