Messages in this thread |  | | Date | Sat, 23 Sep 2000 22:31:03 +0200 | From | Xuan Baldauf <> | Subject | Re: (reiserfs) Re: An elevator algorithm |
| |
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/
|  |