I think Xuan's algorithm is good, so I want to add to it.:-)
Ragnar, I don't understand your objection to it. It is always the case that if you specify real
time constraints that are impossible then they aren't met.
If you want to get fancy you could sort all expired time limit requests by blocknr. This gives you
three lists: one list containing unexpired requests sorted by blocknr, another list containing
unexpired requests sorted by time, and a third containing expired requests sorted by blocknr. Throw
in Andrea's/Netware's optimization objective, and you could have four lists: list 1 contains
unexpired requests sorted by blocknr, list 2 contains unexpired requests sorted by time until
expiry, lists 3a and 3b if not empty contain expired requests and are alternating queues in which
one list is being fulfilled and the other list is being added to at any given time, with the the
queues switching roles whenever the list being fulfilled becomes empty.
I like this model, and it probably isn't hard to code. Maybe I can talk Xuan into giving it a
try?:-)
Hans
Ragnar Kjørstad wrote:
>
> 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:26 EST