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

[Rik van Riel]

On Mon, 10 Feb 2003, 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 ;))

Took about 30 minutes, but here is an alternative algorithm.
One that doesn't suffer from SFQ's "temporary unfairness due
to unlucky hashing" problem, which can be made worse with SQF's
"rehashing once every N seconds" policy, where N is too big
for the user, say 30 seconds.

It requires 2 extra fields in the struct files_struct:
	->last_request and
	->request_priority

where ->last_request is the time (jiffies value) when a
process associated with this files_struct last submitted
an IO request and ->request_priority is a floating average
of the time between IO requests, which can be directly used
to determine the request priority.

The floating priority is kept over (1 << RQ_PRIO_SHIFT) requests,
maybe 32 would be a good value to start ?  Maybe 128 ?

The request priority of the files_struct used by the current
process can be calculated in a simple O(1) way every time a
request is submitted:

{
	struct files_struct *files = current->files;
	unsigned long interval = jiffies - files->last_request;

	files->request_priority -= (files->request_priority >> RQ_SHIFT_PRIO);
	files->request_priority += interval;
}

The request_priority gets assigned as the priority of the
currently submitted request (or the request gets submitted
in the queue belonging to this priority range).  We don't
change the priority of already submitted requests, except
maybe when merging requests.

This idea should adapt faster to changing IO usage of tasks
and is O(1) scalable.  Dunno if it'll be better than SFQ in
practice too, but it just shows that SFQ isn't the only way. ;)

have fun,

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>