Messages in this thread | | | Date | Tue, 19 Sep 2000 23:20:47 +0200 | From | Andrea Arcangeli <> | Subject | Re: (reiserfs) Re: An elevator algorithm (patch) |
| |
On Tue, Sep 19, 2000 at 10:38:52PM +0200, Jens Axboe wrote: > I haven't had a chance to really look at Peter's mods yet, but surely > the current elevator can have many entries with 0 sequence. As an > example, say the start sequence is 3 and we received request sector > 10...1 in descending order. The sorted order would then be > > 7[3] 8[2] 9[1] 10[0] 3[3] 4[2] 5[1] 6[0] 1[3] 2[2] p With point `p' I mean the request after last barrier in the queue.
With the current algorithm we can trivially account for p each time we do elevator_sequence--. elevator_sequence can't go below zero and we never play with stuff before the last barrier. So the first time !--req->elevator_sequence is true we would know that req->next is the new p (if it's not real_head).
Then we would insert at the left of p if the new req is lower than p.
With the modification instead we could have this queue:
100[0]
Then we insert 102 103 and 104:
100[0] 102[3] 103[3] 104[3] p
Then when we try to insert 99 it goes here:
100[0] 102[3] 103[3] 104[3] 99[3] p
So we have two low peaks in the not starving queue and we should move the p to the latest on the right.
Also we should make different cases in function of what p->prev is (barrier/head/real_head/normalreq).
I don't think it's worthwhile (even with the current algorithm where it's easy to account for p).
Andrea - 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/
| |