[lkml]   [2000]   [Sep]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: (reiserfs) Re: An elevator algorithm
On Sat, Sep 16, 2000 at 06:31:46PM +0200, Xuan Baldauf wrote:
> I do not understand you terminology. There is not one queue, there are two
> queues.

Two queues?

What elevator code are you guys refering to when refering to "current"
code? I just read the code for linux-2.4.0-test8 - that is the one I'm
comparing with.

> > 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.
> Which number? Do you mean the timeout? Do you mean decline = decrease?
Yes, decreased. elevator_sequence
But I now see I was wrong - forget that comment.

> It does look good. One active queue and one future active queue IIRC. It just
> does not take into account that after serving sector 2, the new sector 3 (in
> the second queue) could easily be served before sector 4. But because this is
> minor, I could live with that. Your algorithm guarantees serve time for the
> requests in the current queue.

I agree that requests should be attemted merged with the active queue.
This will not solve the problem you describe, but it will help.

I don't think it should be two queues - I think it should be a dynamic
number of queues. Each queue can have a maximum length (in time or
number of requests), and when a queue is full, you start adding to the
next one. The queues are served in the order they were created.

My original algorithm didn't include priorities. I now think this can be
fixed by having different ideas for "full" queues according to the
priority of the process.

This way you don't need one index by time and one by sector.

Ragnar Kjørstad
Big Storage
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
Please read the FAQ at

 \ /
  Last update: 2005-03-22 12:38    [W:0.073 / U:0.052 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site