js> we need to reduce the granularity of I/O scheduling: to
    js> reduce the *latency* in servicing the low-rate, but 
    js> real-time jobs like Manuel's xterm.

    js> An analogy with with CPU scheduling may help: in essence, our 
    js> quantum is far, far too large.  A more accurate analogy would 
    js> take the cost of disk movement into account. 

The network packet scheduling algorithms in ALTQ are described in their 
respective papers as approximations of ``a GPS algorithm'':  
generalized processor sharing.  The papers don't consider it very 
relevant that they're scheduling network packets rather than CPU 
timeslices.  The ``approximation'' comes from the fact that you can't 
schedule half a network packet, while in the GPS model packets and 
timeslices have infinite granularity.

It seems that a very long time ago engineers used to argue late into 
the night about the best way to schedule timesharing CPUs, and then 
they got bored and spit-taped together the BSD scheduler.  So this 
term ``GPS'' accurately captures their irritation when the old CPU 
scheduling problem emerges once again from the depths of the earth 
in some vaguely different way.

I definitely think this is the relevant model.  It's not perfect, 
since seeking and zoning means you can't know the exact bandwidth of 
a disk like you can a CPU or point-to-point network interface.  But 
it's good.  For example, HFSC is supposed to let you allocate 
bandwidth and latency separately.

One problem with the ALTQ camp is that the fancy algorithms usually 
schedule packets out of multiple simple (ex. FIFO) queues onto the 
wire, while what the disk wants is more like the reverse 
arrangement---scheduling into an elevator queue.

TCP congestion control is not really the right analogy because it must 
work within the limitation if inaccessible queues in the intervening 
routers.  That might be a good analogy if you were trying to schedule 
fair access to a memory bus, but with a slow disk your algorithm can 
attain and afford omniscience right up to the tiny queue inside the 
disk.  Also, the notion of dropping packets is missing from disk 
scheduling, but it's fundamental to congestion control (on TCP link 
A->B->C, it's bad if half of packets drop at B, because this wastes 
space on the A->B link that could be used for someone else's A->B->D 
session.).