Hans Reiser wrote:
> 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,
Sounds promising. :-)
> and it probably isn't hard to code. Maybe I can talk Xuan into giving it a
> try?:-)
How do mean that? I do not know wether I've got enough knowledge for Linux-Kernel hacking
(implementation), my practical experience is not beyond fixing some kernel bugs. Also my time is
limited. :-( Maybe some experienced kernel hacker can implement this algorithm as his|her breakfast
instead of waiting for me to do that. :o)
Xuân.
>
>
> 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 30 2000 - 21:00:12 EST