Maintain two queues which will be sorted in ascending order using RedWhy both queues sorting in ascending order? I would think that one should be in descending order, which would reduce the seek distance between the last i/o on one queue and the first on the next.
Black Trees. When a disk request arrives and if the block number it
refers to is greater than the block number of the current request
being served add (merge) it to the first sorted queue or else add
(merge) it to the second sorted queue. Keep on servicing the requests
from the first request queue until it is empty after which switch over
to the second queue and now reverse the roles of the two queues.
Simple and Sweet. Many thanks for the awesome block I/O layer in the
2.6 kernel.