The Effect of Deceptive Idleness on Disk Schedulers

Sitaram Iyer

Abstract

Disk schedulers in operating systems are generally work-conserving; they schedule a request immediately after the previous request has finished. Such schedulers need multiple outstanding requests to make good decisions. Unfortunately, many applications issue synchronous, almost-continuous streams of read requests. This forces the scheduler into making decisions too early, falsely assuming that the process has become momentarily idle. This phenomenon of deceptive idleness causes significant degradation in performance and quality of service objectives on current systems. We solve deceptive idleness by designing and implementing a transparent, non-work-conserving scheduling framework for various scheduling policies. We evaluate this solution on microbenchmarks and real workloads, and observe large benefits. The Apache webserver delivers 56% and 16% more throughput for two configurations. The Andrew Benchmark runs faster by 8% (54% for the read-intensive phase). Variants of the TPC-B database benchmark exhibit improvements between 4% and 60%. Proportional-share schedulers become empowered to efficiently deliver application-desired proportions.

Acknowledgements

I wish to thank a number of people who have contributed to the making of this thesis. First and foremost, I thank my advisor Dr. Peter Druschel for his visionary supervision throughout the project, and the freedom and flexibility that he allowed me at every stage. The driving force can be rightly attributed to his adamant insistence, especially during the formative days, that this project can actually be pulled off. I cannot sufficiently thank Juan Navarro and Karthick Rajamani for the marvellous feedback-based sounding boards that they have both been. Mohit Aron gave me useful advice regarding the choice and usage of timing mechanisms. I had countless lunchtime conversations with Sanjeeb Dash about the material in this thesis. Martin DeMello coined the phrase ``deceptive idleness'' after hearing a boring description of the same; it sounds so much cuter than the originally conceived ``apparent idleness''. Sameer Siruguri helped print and submit the thesis when I wasn't physically around. Both Rice University and MIT have provided computational resources used for this project; I thank them for that. Finally, I express sincere thanks to my family for their continued support over the years.