[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.181 / U:3.404 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site