"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..."
