Idletime scheduling with preemption intervals

Abstract

This paper presents the idletime scheduler; a generic, kernel-level mechanism for using idle resource capacity in the background without slowing down concurrent foreground use. Many operating systems fail to support transparent background use and concurrent foreground performance can decrease by 50% or more. The idletime scheduler minimizes this interference by partially relaxing the work conservation principle during preemption intervals, during which it serves no background requests even if the resource is idle. The length of preemption intervals is a controlling parameter of the scheduler: short intervals aggressively utilize idle capacity; long intervals reduce the impact of background use on foreground performance. Unlike existing approaches to establish prioritized resource use, idletime scheduling requires only localized modifications to a limited number of system schedulers. In experiments, a FreeBSD implementation for idletime network scheduling maintains over 90% of foreground TCP throughput, while allowing concurrent, high-rate UDP background flows to consume up to 80% of remaining link capacity. A FreeBSD disk scheduler implementation maintains 80% of foreground read performance, while enabling concurrent background operations to reach 70% throughput.

References

1. Mohit Aron and Peter Druschel. Soft timers: efficient microsecond software timer support for network processing. ACM Transactions on Computer Systems, Vol. 18, No. 3, August 2000, pp. 197--228.]]
2. Gene M. Amdahl. Validity of the single processor approach to achieving large scale computing capabilities. Proc. AFIPS Joint Computer Conference, Atlantic City, NJ, USA, April 18-20, 1967, pages 483--485.]]
3. John Bruno, Eran Gabber, Banu Özden, and Abraham Silberschatz. The Eclipse Operating System: Providing Quality of Service via Reservation Domains. Proc. USENIX Annual Technical Conference, New Orleans, LA, USA, June 15-19, 1998, pp. 235--246.]]
4. Kenjiro Cho. A Framework for Alternate Queuing: Towards Traffic Management by PC-UNIX Based Routers. Proc. USENIX Annual Technical Conference, New Orleans, LA, USA, June 15-19, 1998, pp. 247--258.]]
5. David Clark and Wenjia Fang. Explicit Allocation of Best-Effort Packet Delivery Service. IEEE/ACM Transactions on Networking, Vol. 6, August 1998, pp. 362--373.]]
6. Jon Crowcroft and Philippe Oechslin. Differentiated End-to-End Internet Services using a Weighted Proportional Fair Sharing TCP. ACM SIGCOMM Computer Communication Review, Vol. 28, No. 3, July 1998, pp. 53--67.]]
7. Brian D. Davison and Vincenzo Liberatore. Pushing Politely: Improving Web Responsiveness One Packet at a Time. Performance Evaluation Review, Vol. 28, No. 2, September 2000, pages 43--49.]]
8. John R. Douceur and William J. Bolosky. Progress-based regulation of low-importance processes. Proc. ACM Symposium on Operating Systems Principles (SOSP), Kiawah Island Resort, SC, USA, December 12-15, 1999, pp. 247--260.]]
9. Lars Eggert and Joseph D. Touch. End-System Support for Idletime Networking. ISI Technical Report ISI-TR-559, USC Information Sciences Institute, May 2001.]]
10. Lars Eggert. Background Use of Idle Resource Capacity. Ph.D. Thesis, Department of Computer Science, University of Southern California, 941 W 37th Pl, Los Angeles, CA 90089, USA, May 2004.]]
11. Darin Fisher. Mozilla Link Prefetching FAQ. October 14, 2002.]]
12. Sitaram Iyer and Peter Druschel. Anticipatory scheduling: A disk scheduling framework to overcome deceptive idleness in synchronous I/O. Proc. ACM Symposium on Operating Systems Principles (SOSP), October 21-24, 2001, Chateau Lake Louise, Banff, Alberta, Canada, pp. 117--130.]]
13. Van Jacobson, Robert Braden and Dave Borman. TCP Extensions for High Performance. RFC 1323, May 1992.]]
14. Eric Korpela, Dan Werthimer, David Anderson, Jeff Cobb and Matt Lebofsky. SETI@home: Massively Distributed Computing for SETI. IEEE Computing in Science and Engineering, Vol. 3, No. 1, January/February 2001, pp. 78--83.]]
15. Aleksandar Kuzmanovic and Edward W. Knightly. TCP-LP: A Distributed Algorithm for Low Priority Data Transfer. Proc. IEEE INFOCOM, San Francisco, CA, USA, April 2003, pp. 1691--1701.]]
16. Butler Lampson and David Redell. Experience with Processes and Monitors in Mesa. Communications of the ACM, Vol. 23, No. 2, February 1980, pp. 105--117.]]
17. Stefan M. Larson, Christopher D. Snow, Michael Shirts and Vijay S. Pande. Folding@Home and Genome@Home: Using distributed computing to tackle previously intractable problems in computational biology. Computational Genomics, Horizon Press, 2002.]]
18. Ian Leslie, Derek McAuley, Richard Black, Timothy Roscoe, Paul Bar-ham, David Evers, Robin Fairbairns and Eoin Hyden. The Design and Implementation of an Operating System to Support Distributed Multimedia Applications. IEEE Journal on Selected Areas In Communications (JSAC), Vol. 14, No. 7, September 1996, pp. 1280--1297.]]
19. Michael J. Liztkow, Miron Livny and Matt W. Mutka. Condor -- A Hunter of Idle Workstations. Proc. International Conference on Distributed Computing Systems (ICDCS), San Jose, CA, USA, June 13-17, 1988, pp. 104--111.]]
20. Microsoft Corporation. Background Intelligent Transfer Service. Microsoft Windows Server Technical Article, August 2002.]]
21. Ronald G. Minnich and David J. Farber. The Mether system: A distributed shared memory for SunOS 4.0. Proc. Summer USENIX Conference, Baltimore, MY, USA, June 12-16, 1989, pp. 51--60.]]
22. David Mosberger and Larry L. Peterson. Making Paths Explicit in the Scout Operating System. Proc. USENIX Symposium on Operating Systems Design and Implementation (OSDI), Seattle, WA, USA, October 28-31, 1996, pp. 153--168.]]
23. Matt W. Mutka and Miron Livny. Profiling Workstations' Available Capacity For Remote Execution. Proc. IFIP WG 7.3 Symposium on Computer Performance, Brussels, Belgium, December 7-9, 1987, pp. 529--544.]]
24. Matt W. Mutka and Miron Livny. The available capacity of a privately owned workstation environment. Performance Evaluation, Vol. 12, 1991, pp. 269--284.]]
25. Klara Nahrstedt, and Jonathan M. Smith. Design, Implementation and Experiences with the OMEGA End-point Architecture. IEEE Journal on Selected Areas in Communications (JSAC), Vol. 17, No. 7, September 1996, pp. 1263--1279.]]
26. Thomas Narten and Raj Yavatkar. Remote Memory as a Resource in Distributed Systems. Proc. IEEE Workshop on Operating Systems, Key Biscane, FL, USA, April 23-24, 1992, pp. 132--136.]]
27. Venkata N. Padmanabhan and Jeffrey C. Mogul. Using predictive prefetching to improve World-Wide Web latency. ACM SIGCOMM Computer Communication Review, Vol. 27, No. 3, 1996, pp. 22--36.]]
28. POSIX 1003.1b-1993. Portable Operating System Interface (POSIX) Part 1: System Application Program Interface Amendment 1: Realtime Extension {C Language}, 1993.]]
29. Jon Postel. Discard Protocol. RFC 863, May 1983.]]
30. Luigi Rizzo. Dummynet: A simple approach to the evaluation of network protocols. ACM SIGCOMM Computer Communication Review, Vol. 27, No. 1, January 1997 pp. 31--41.]]
31. Stanislav Shalunov and Benjamin Teitelbaum. QBone Scavenger Service (QBSS) Definition. Internet2 Technical Report, March 16, 2001.]]
32. John A. Stankovic and Krithi Ramamritham. The Spring Kernel: A New Paradigm for Realtime Systems. IEEE Software, Vol. 8, No. 4, May 1991, pp. 62--72.]]
33. Marvin M. Theimer, Keith A. Lantz and David R. Cheriton. Preemptable Remote Execution Facilities for the V-System. Proc. ACM Symposium on Operating Systems Principles (SOSP), Orcas Island, WA, USA, December 1985, pp. 2--12.]]
34. Hideyuki Tokuda, Tatsuo Nakajima and Prithvi Rao. Realtime Mach: Towards a Predictable Realtime System. Proc. USENIX Mach Symposium, Burlington, VT, USA, October 4-5, 1990, pp. 73--82.]]
35. Joseph D. Touch. Parallel Communication. Proc. IEEE INFOCOM, San Francisco, CA, USA, March 28 - April 1, 1993, pp. 506--512.]]
36. Joseph D. Touch and David J. Farber. An Experiment in Latency Reduction. Proc. IEEE INFOCOM, Toronto, Canada, June 12-16, 1994, pp. 175--181.]]
37. George Varghese and Anthony Lauck. Hashed and hierarchical timing wheels: efficient data structures for implementing a timer facility. IEEE/ACM Transactions on Networking, Vol. 5, No. 6, 1997, pp. 824--834.]]
38. Arun Venkataramani, Ravi Kokku and Mike Dahlin. TCP Nice: A Mechanism for Background Transfers. Proc. Symposium on Operating Systems Design and Implementation (OSDI), December 9-11, 2002, Boston, MA, USA.]]
39. Carl A. Waldspurger and William E. Weihl. Stride Scheduling: Deterministic Proportional-Share Resource Management. Technical Memorandum MIT/LCS/TM-528, MIT Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, USA, June 1995.]]
40. Bruce L. Worthington, Gregory R. Ganger, Yale N. Patt. Scheduling Algorithms for Modern Disk Drives. Proc. ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, Nashville, TN, USA, May 16-20, 1994, pp. 241--251.]]
41. Peter Wyckoff, Theodore Johnson and Karpjoo Jeong. Finding Idle Periods on Networks of Workstations. Technical Report TR1998-761, Computer Science Department, New York University, March 1998.]]
42. Marko Zec and Miljenko Mikuc. Real-Time IP Network Simulation at Gigabit Data Rates. Proc. International Conference on Telecommunications (ConTEL), Zagreb, Croatia, June 11--13, 2003.]]

Index Terms

• Software and its engineering

  • Software creation and management

    • Designing software

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Communications management

          • Buffering

          • Input / output

          • Message passing

        • Process management

          • Concurrency control

          • Scheduling