A way to avoid starvation while retaining the performance benefits is to
force requests to the front of the queue once they get "too old." In
effect, you give the sorting algorithm a change to service the requests
quickly in some 'optimal' order (which it usually will) but after a
while you revert to FIFO (or 'fair' algorithm such as elevator) for
stale requests.
Taking this one step further, you could view the entire sorting problem
as a scheduling problem. Larry McVoy proposed priority sorting. What
you really want to do is weigh the various factors when deciding how to
order the requests. For example, you might prefer a request originating
with a high-priority process over one originating with a low-priority
process, but not if the low-priority request is "much" closer to the
current head position (or in between the current head position and the
high-priority request), or of the low-priority request has been witing
too long. Similarly, you'd ordinarily like to give preference to reads
over writes, since reads are synchronous, but you would prefer writes if
memory is low.
Essentially, you sort requests according to a goodness() function which
might be as simple as FIFO or ascending (one-way elevator) but it might
also be something else.
One more thing to consider is that in certain situations it might be
better to delay a request for a short time even if the queue is empty,
because you want to be able to service another request near the current
head position before moving elsewhere on the disk, and you suspect that
another request near the current head position might be received soon.
This is similar to delayed ack.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/