[lkml]   [1998]   [Nov]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
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

- 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

- 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
Please read the FAQ at

 \ /
  Last update: 2005-03-22 13:45    [from the cache]
©2003-2014 Jasper Spaans. hosted at Digital Ocean