[lkml]   [2000]   [Sep]   [13]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    Subject(reiserfs) Re: More on 2.2.18pre2aa2
    On Wed, 13 Sep 2000, Giuliano Pochini wrote:

    >I had a look at the new elevator. I hope I'm not wrong here... Requests
    >are added to the queue scanning it starting from the tail. When the
    >new request if found in-order with ad existing one, it's inserted int

    Right so that it works in O(1) if you're doing sequential I/O.

    >the queue, unless it finds an existing request out of latency units. In
    >that case the new rq is added before it (so it will be serviced after).

    Correct. The request out of latency units will become a barrier and
    nothing will be allowed to pass it.

    >After it have inserted the request it walks back and decrease all
    >latency counters.

    Yes, it have to tell to the other requests that they are being delayed.

    >So, the "unit" to measure latency is "number of requests". New requests

    Yes, in the sense of I/O request (not `struct request').

    >are not allowed to go before an existing one more than N times.


    >It's a good way to avoid stalls, but IMHO I thing the elevator should

    Here you're talking about the latency control logic.

    >not work this way. The main problem is that it doesn't minimize head
    >movement. For example, when comes a request for a sector at the

    The algorithm that control the latency and the one that enforce the
    ordering are two separate things.

    For example in 2.2.15 there's only the latter (2.2.15 was missing a
    latency control mechanism).

    >beginning of the disk it goes to the beginning of the queue (it's
    >ordered) so it will be serviced before other rqs (it picks up rqs from
    >the head). This way the higher is the block number, more likely that
    >rq will wait a lot.

    We're not using a SCAN ordering algorithm it's instead a CSCAN. The queue
    can be for istance:

    12 13 14 1 2 3

    Now insert 15 (assume 15 is the last sector of the disk):

    12 13 14 15 1 2 3

    as you can see the higher block number of the HD will wait less time than
    1 2 3 (it will pass 1 2 and 3, of course assuming they are fresh requests
    and they still have some latency unit to spend).

    SCAN instead would have a fairness problem where the middle of the disk
    gets less latency but SCAN as well goes backwards and it's not know how
    well it works in all the hardware out there. (I think that's one of the
    main reasons we use CSCAN instead)


    PS. Thanks for having read and understood the internals of the 2.4.x
    elevator before posting your comments, it simplifies very much the

    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 12:38    [W:0.025 / U:25.156 seconds]
    ©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site