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.
Correct.
>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)
Andrea
PS. Thanks for having read and understood the internals of the 2.4.x
elevator before posting your comments, it simplifies very much the
communication.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Fri Sep 15 2000 - 21:00:22 EST