Anticipatory scheduling: a disk scheduling framework to overcome deceptive idleness in synchronous I/O

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.

REFERENCES

• 1: J. Almeida, M. Dabu, A. Manikutty, and P. Gao. Providing differentiated quality of service in web hosting services. In WISP, June 1998.
• 2: Mohit Aron , Peter Druschel, Soft timers: efficient microsecond software timer support for network processing, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.232-246, December 12-15, 1999, Charleston, South Carolina, United States
• 3: M. Aron, S. Iyer, and P. Druschel. A resource management framework for predictable quality of service in web servers, July 2001. Submitted. http://www.cs.rice.edu/-ssiyer/r/mbqos/.
• 4: Gaurav Banga , Peter Druschel , Jeffrey C. Mogul, Resource containers: a new facility for resource management in server systems, Proceedings of the third symposium on Operating systems design and implementation, p.45-58, February 1999, New Orleans, Louisiana, United States
• 5: J. Bennett and H. Zhang. WF2Q: Worst-case fair weighted fair queueing. In IEEE Infocom, Mar. 1996.
• 6: HTTP log files at the University of California, Berkeley. http: //www.cs.berkeley.edu/logs/http /.
• 7: John Bruno , Jose Brustoloni , Eran Gabber , Banu Ozden , Abraham Silberschatz, Disk Scheduling with Quality of Service Guarantees, Proceedings of the IEEE International Conference on Multimedia Computing and Systems Volume II-Volume 2, p.400, June 07-11, 1999
• 8: J. Bruno, E. Gabber, B. ()zden, and A. Silberschatz. The Eclipse operating system: Providing quality of service via reservation domains. In USENIX 1998 Annual Technical Conference, June 1998.
• 9: S. Chen, J. A. Stankovic, J. F. Kurose, and D. Towsley. Performance evaluation of two new disk scheduling algorithms for real-time systems. Journal of Real-Time Systems, 3(3):307-336, Sept. 1991.
• 10: Leana Golubchik , John C. S. Lui , Edmundo de. Souza e. Silva , H. Richard Gail, Evaluation of Tradeoffs in Resource Management Techniques for Multimedia Storage Servers, Proceedings of the IEEE International Conference on Multimedia Computing and Systems Volume II-Volume 2, p.292, June 07-11, 1999
• 11: Pawan Goyal , Xingang Guo , Harrick M. Vin, A hierarchial CPU scheduler for multimedia operating systems, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.107-121, October 29-November 01, 1996, Seattle, Washington, United States
• 12: John H. Howard , Michael L. Kazar , Sherri G. Menees , David A. Nichols , M. Satyanarayanan , Robert N. Sidebotham , Michael J. West, Scale and performance in a distributed file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.51-81, Feb. 1988 [doi>10.1145/35037.35059]
• 13: L. Huang and T. Chiueh. Implementation of a rotation latency sensitive disk scheduler. Technical Report ECSL-TR81, SUNY, Stony Brook, Mar. 2000.
• 14: S. Iyer and P. DruscheL The effect of deceptive idleness on disk schedulers. Technical Report CSTR01-379, Rice University, June 2001.
• 15: D. Jacobson and J. Wilkes. Disk scheduling algorithms based on rotational position. Technical Report HPL-CSP-91-Trevl, Hewlett-Packard, Feb. 1991.
• 16: C. Lumb, J. Schindler, G. Ganger, D. Nagle, and E. Riedel. Towards higher disk head utilization: Extracting free bandwidth from busy disk drives. In 4th USENIX OSDI, Oct. 2000.
• 17: Todd C. Mowry , Angela K. Demke , Orran Krieger, Automatic compiler-inserted I/O prefetching for out-of-core applications, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.3-17, October 29-November 01, 1996, Seattle, Washington, United States
• 18: R. H. Patterson , G. A. Gibson , E. Ginting , D. Stodolsky , J. Zelenka, Informed prefetching and caching, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.79-95, December 03-06, 1995, Copper Mountain, Colorado, United States
• 19: D. Roselli, J. R. Lorch, and T. E. Anderson. A comparison of file system workloads. In USENIX Annual Technical Conference, June 2000.
• 20: Emilia Rosti , Evgenia Smirni , Giuseppe Serazzi , Lawrence W. Dowdy, Analysis of Non-Work-Conserving Processor Partitioning Policies, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.165-181, April 25, 1995
• 21: Chris Ruemmler , John Wilkes, An introduction to disk drive modeling, Computer, v.27 n.3, p.17-28, March 1994 [doi>10.1109/2.268881]
• 22: M. Seltzer, P. Chen, and J. Ousterhout. Disk scheduling revisited. In USENIX Winter Technical Conference, Jan. 1990.
• 23: Prashant J. Shenoy , Harrick M. Vin, Cello: a disk scheduling framework for next generation operating systems, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.44-55, June 22-26, 1998, Madison, Wisconsin, United States
• 24: E. Shriver, C. Small, and K. Smith. Why does file system prefetching work? In USENIX Annual Technical Conference, June 1999.
• 25: J. B. Siegal, Jan. 2000. http://www.cs.rice.edu/~ssiyer/r/antsched/linux.html.
• 26: D. Sullivan and M. Seltzer. Isolation with flexibility: A resource management framework for central servers. In USENIX Annual Technical Conference, June 2000.
• 27: Transaction Processing Performance Council. TPC-B standard specification, revision 2.0, 1994.
• 28: Raj Vaswani , John Zahorjan, The implications of cache affinity on processor scheduling for multiprogrammed, shared memory multiprocessors, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.26-40, October 13-16, 1991, Pacific Grove, California, United States
• 29: Ben Verghese , Anoop Gupta , Mendel Rosenblum, Performance isolation: sharing and isolation in shared-memory multiprocessors, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.181-192, October 02-07, 1998, San Jose, California, United States
• 30: Werner Vogels, File system usage in Windows NT 4.0, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.93-109, December 12-15, 1999, Charleston, South Carolina, United States
• 31: C. Waldspurger and W. Weihl. Lottery scheduling: Flexible proportional-share resource management. In 1st USENIX OSDI, Nov. 1994.
• 32: C. A. Waldspurger , E. Weihl. W., Stride Scheduling: Deterministic Proportional- Share Resource Management, Massachusetts Institute of Technology, Cambridge, MA, 1995
• 33: Frank Waters, AIX performance tuning, Prentice Hall Press, Upper Saddle River, NJ, 1995
• 34: Bruce L. Worthington , Gregory R. Ganger , Yale N. Patt, Scheduling algorithms for modern disk drives, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.241-251, May 16-20, 1994, Nashville, Tennessee, United States
• 35: X. Yu, B. Gum, Y. Chen, R. Wang, K. Li, A. Krishnamurthy, and T. Anderson. Trading capacity for performance in a disk array. In 4th USENIX OSDI, Oct. 2000.
• 36: H. Zhang. Providing end-to-end performance guarantees using non-work-conserving disciplines. Computer Communications, 18(10), Oct. 1995.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Secondary storage

General Terms:
Experimentation, Performance