[ Thanks to Jeremy
Andrews for this link. ]
“Following the recent release of an anticipatory IO scheduler,
Andrea Arcangeli started a lengthy thread in which he proposed an
SFQ (Stochastic Fair Queuing) disk scheduler. The idea was picked
up by Jens Axboe who had evidently worked on a similar idea
earlier. Jens quickly posted two different disk schedulers
utilizing “fair queuing” algorithms, more commonly used in handling
network traffic. When someone suggested he was reinventing the
wheel, Jens replied, ‘There’s no wheel reinventing here, just
applying the goodies from network scheduling to disk
scheduling.’“Jens’ first disk scheduler utilizes SFQ, or Stochastic Fair
Queuing. Fair queuing would allow many processes demanding large
levels of disk IO to each get fair access to the device, preventing
any one process from denying the others. SFQ is one of the simpler
and less accurate fair queuing algorithms that works well on
average, its primary benefit being that it requires very minimal
overhead. Essentially, SFQ works by dividing IO requests among a
large number of queues using a frequently changing hash algorithm,
then serving the requests round robin. The term ‘stochastic’ is
used as each process does not get its own queue, leaving some of
the derived benefit to random chance. In other words, the queues
are stored in a hash table, and it is possible for processes
requesting IO to hash to the same bucket, or collide, thus sharing
a queue…”
Related Story:
QLinux: A QoS enhanced Linux Kernel for Multimedia
Computing(Jun 06, 1999)