Anticipatory scheduling: a disk scheduling framework to overcome deceptive idleness in synchronous I/O
Sitaram Iyer, Peter Druschel
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 \em{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.