[linuxkernelnewbies] Anticipatory Disk Scheduling

[Peter Teoh]

http://www.cs.rice.edu/~ssiyer/r/antsched/ Anticipatory scheduling: A disk scheduling framework to overcome deceptive idleness in synchronous I/O Sitaram Iyer Peter Druschel ScalaServer umbrella project Dept. of Computer Science Rice University Abstract Disk schedulers in current operating systems are generally work-conserving, i.e., they schedule a request as soon as the previous request has finished. Such schedulers often require multiple outstanding requests from each process to meet system-level goals of performance and quality of service. Unfortunately, many common applications issue disk read requests in a synchronous manner, interspersing successive requests with short periods of computation. The scheduler chooses the next request too early; this induces deceptive idleness, a condition where the scheduler incorrectly assumes that the last request issuing process has no further requests, and becomes forced to switch to a request from another process. We propose the anticipatory disk scheduling framework to solve this problem in a simple, general and transparent way, based on the non-work-conserving scheduling discipline. Our FreeBSD implementation is observed to yield large benefits on a range of microbenchmarks and real workloads. The Apache webserver delivers between 29% and 71% more throughput on a disk-intensive workload. The Andrew filesystem benchmark runs faster by 8%, due to a speedup of 54% in its read-intensive phase. Variants of the TPC-B database benchmark exhibit improvements between 2% and 60%. Proportional-share schedulers are seen to achieve their contracts accurately and efficiently. News: The Linux anticipatory scheduler got slashdotted! Anticipatory scheduling is default in linux-2.5.62-mm3 as of 2/26/03. Two KernelTrap articles covering this potential kernel feature: Linux: Where The Anticipatory Scheduler Shines     [local copy] .. Offering a succinct "executive summary" of his results, Andrew [Morton] said, "the anticipatory scheduler is wiping the others off the map, and 2.4 is a disaster." .. Linux: Anticipatory I/O Scheduler     [local copy] .. So what anticipatory scheduling does is very simple: if an application has performed a read, do *nothing at all* for a few milliseconds. .. SOSP 2001 - [HTML] - [PS.gz] - [PDF] - [BibTeX] Anticipatory scheduling: A disk scheduling framework to overcome deceptive idleness in synchronous I/O SOSP talk slides - [PPT] - [HTML] - [HTML.zip] - (these three need the [Trebuchet MS font]) Also in handout form - [PDF] - [PS.gz] Poster (42"x48") - [JPG] - [Letter-size printable PDF] - [PS.gz] Masters thesis - [HTML] - [PS.gz] - [PDF] - [BibTeX] The effect of Deceptive Idleness on Disk Schedulers      .. this is a detailed version with full pseudocode. This is also Rice-CS-TR01-379 Pizza talk slides (slightly simplified for a general audience) - [PPT] Masters thesis defense slides - [PPT] - [PDF] Warning: These slides are quite dated, and incorrect in places. Source code - [tar.gz] - [browse] - [readme] - [license] Our prototype implementation of Anticipatory Scheduling on FreeBSD 4.3.