lkml.org 
[lkml]   [1998]   [Nov]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
Subjectelevator algorithm bug in ll_rw_blk.c
Hi all,

as v2.2 is expected soon I better bring this topic up now. As you know the
"elevator algorihm" is employed for disk I/O, but -- it *looks* broken to me.
What's actually being done is to always serve the block with the lowest
number. This starves high block numbers. See drivers/block/ll_rw_blk.c,
line ~333, search for IN_ORDER.

I don't completely understand what's going on, and maybe I'm all wrong...

What could be done:

- add a second queue; one is sorted upwards, the other downwards. Add new
requests to one queue, process the other. Swap when the processed queue is
empty.

- don't sort the queue, but select the next block to read dynamically by
looking at each, computing a dynamic priority, and selecting the best. This
priority might depend on the nice value of the process that made the
request, the age of the request, and the current elevator position and
direction.

- any other suggestions?

I'm not quite able to reproduce this now, but I remember that during heavy I/O
loads a "ps" command on another console would do almost nothing until the load
dropped. Also this probably doesn't apply to SCSI devices.

-- Wolfgang


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:45    [from the cache]
©2003-2011 Jasper Spaans