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

[Andrea Arcangeli]

On Mon, Feb 10, 2003 at 02:44:59AM -0200, Rik van Riel wrote:
> 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. ;)

The file level is worthless IMHO, you have no idea of what is going on
in the I/O queue from there, the queue can be filled with 64M in some
msec. If you really thing the above can be nearly as good at SFQ at the
queue level, implement your alternate solution, benchmark it against SFQ
with a seeking tiotest 1 with a cp /dev/zero .  in background, if it
works better than SFQ we'll use it.

Andrea