On Sat, Sep 16, 2000 at 01:17:53PM +0200, Xuan Baldauf wrote:
> I'm not a kernel hacker (and therefore I'm not familiar with the kernel
> terminology), and maybe this idea is already old, but here is an
> algorithm for an elevator which tries to guarantee smoothness and no
> stalling:
>
> Every rw-request gets an expiry timeout (e.g. in jiffies) where it's
> completion must have started. Every request is member of two sorted
> lists which support fast add|remove and iterating to the previous|next
> member (linked list, binary tree, etc.):
> The request list sorted by expiry and the request list sorted by block
> number. When a rw-access is requested, the request gets its timeout and
> is inserted in those two lists. The elevator has a current request on
> which it is working. When the elevator is finished, it removes the
> current request from the two lists and gets the "current time" (in
> jiffies). If the head of the request list sorted by expiry has a time
> equal to or smaller than the current time, the elevator continues with
> that request. Else it continues with the next or previous request in the
> list sorted by block number. (It can decide which direction, wether to
> continue with the old direction or wether to always start with a
> definite direction)
>
> This way, you have good elevator characteristics while being somewhat
> able to guarantee maximum request duration. If the timeout expired, the
> requested block is served immediately. Only when the system is
> overloaded, so that the difference between the current time and the
> oldest expiry timout exceeds a given maximum, the elevator fails. In
> this case, the system should be throttled (inserting new requests should
> block), I think. Users could determine the expiry-timeouts so that
> important applications get shorter timeouts while not-so-important
> applications which can wait can request a longer timeout.
>
> This algorithm is, of course, only per low-level-device.
>
> What do you think?
If the load is to high to serve requests within the time-limit, the
elevator-code will stop working, and everything will slow down.
You should not serve a request imidiately when it's too old (because the
requests supposed to be served first according to the elevator is likely
to become too old soon, and then you only add more seeking), but only
stop inserting new requests before it.
If I understand the current code correctly, it works like this:
Current queue:
02:04:05:06:09:15 # sector to be written to
05:03:02:04:00:01 # request-nr
In this example the "timeout" is 5 requests, so a new request can never
be placed before a existing request with request-nr < new-request-nr-5;
One request is served (from the head of the queue) and a request to
sector 3 is added:
04:05:06:09:03:15 # sector to be written to
03:02:04:00:06:01 # request-nr
One request is served (from the head of the queue) and a request to
sector 2 is added:
05:06:09:03:15:02 # sector to be written to
02:04:00:06:01:07 # request-nr
One request is served (from the head of the queue) and a request to
sector 16 is added:
06:09:03:15:02:16 # sector to be written to
04:00:06:01:07:08 # request-nr
So we've ended up with a very silly queue....
Now, the description of the algorithm said that there was a number
within each request that was declined by one whenever a new request
passed it in the queue. This will never be used after it becomes
negative, so it would be the same to decline the number of all the
requests by 1, right? And comparing this changing number to 0 is the
same as comparing request-numbers, only more work, right? So I assume I
didn't understand the algorithm correctly :)
Now, lets do the same test with my suggested multiple queue approach:
Current queue (full):
02:04:05:06:09:15 # sector to be written to
05:03:02:04:00:01 # request-nr
In this example the "timeout" is 5 requests, so only 6 requests can be
inserted into each queue.
One request is served (from the head of the queue) and a request to
sector 3 is added:
Current queue (full)
04:05:06:09:15 # sector to be written to
03:02:04:00:01 # request-nr
Second queue:
03 # sector to be written to
06 # request-nr
One request is served (from the head of the queue) and a request to
sector 2 is added:
Current queue (full)
05:06:09:15 # sector to be written to
02:04:00:01 # request-nr
Second queue:
02:03 # sector to be written to
07:06 # request-nr
One request is served (from the head of the queue) and a request to
sector 16 is added:
Current queue (full)
06:09:15 # sector to be written to
04:00:01 # request-nr
Second queue:
02:03:16 # sector to be written to
07:06:08 # request-nr
looks much better, doesn't it?
But then again, maybe I just didn't understand how the current code
works... I'm going to shut up now..
-- Ragnar Kjørstad - 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 : Sat Sep 23 2000 - 21:00:12 EST