Hello,
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?
Xuân.
-
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 16 2000 - 07:18:05 EDT