On Wed, Sep 13, 2000 at 08:08:12PM -0300, Rik van Riel wrote:
> On Thu, 14 Sep 2000, Ragnar Kjørstad wrote:
> > On Wed, Sep 13, 2000 at 06:57:21PM -0300, Rik van Riel wrote:
> > > > Another potentially stupid question:
> > > > When the queue gets too long/old, new requests should be put in
> > > > a new queue to avoid starvation for the ones in the current
> > > > queue, right?
> > >
> > > Indeed. That would solve the problem...
> >
> > I think something like this: (I don't know the current code, so maybe
> > this suggestion is really stupid.....)
> >
> > struct request_queue {
> > int4 start_time;
> > struct request *list;
> > struct request_queue *next;
> > }
> >
> > struct request_queue *current_queue;
> >
> > function too_old (struct request_queue *q) {
> > /* can actually easily be implemented using time, nr of requests
> > or any other messure of amount of work */
> > if (current_time > q->start_time + MAXTIME)
> > return 1;
> > else
> > return 0;
> > }
> >
> > function insert_request(struct request *new) {
> > struct request_queue *q=current_queue;
> > if (new->sectornr < current_sector);
> > q=q->next;
> > while (too_old(q))
> > q=q->next;
> > insert_request(q->list, new);
> > }
>
> This (IMHO) is wrong. When the drive has trouble keeping up
> with requests in FCFS order, we should do some elevator sorting
> to keep throughput high enough to deal with the requests we get.
The "list" in each queue should be sorted. So, even if the queue is
too old, the requests will still be sorted, but only within each queue.
> Jeff's idea would take care of this, together with a *limited*
> (say, 32 entries) queue size. Every time the "work" queue (the
> one the disk is working on) is empty, we switch queues.
OK, I called the "work" queue my "current" queue in the suggestion
above, but other than that it may not be so different.
> Processes get to put their request on the other queue, either
> until the disk takes their requests (the queues are switched)
> or until the queue is full. That way only the N highest priority
> processes can get access to the disk if we're really overloaded
> in a bad way.
I'm not sure I understand this.
New requests should always be put in the first queue that has room (is
not too old). This means that no requests will be shifted too far off
it's original order. (in other words, it is not too unfair)
> > I don't think you should allow merges. If one process is doing a big
> > IO operation on a big file it would still get _all_ capacity, right?
>
> Only if you were to allow unlimited merges ;)
>
> I guess a 'decent' maximum size for one request would
> be somewhere around 256kB, since this is the amount of
> data a drive can read in the time of one disk seek...
Yes, this sounds like a good idea. (Don't know about the size though,
but testing will show)
-- 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 : Fri Sep 15 2000 - 21:00:22 EST