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    [W:2.218 / U:4.456 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site