skip to main content
article

Idletime scheduling with preemption intervals

Published: 20 October 2005 Publication History

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.]]

Cited By

View all
  • (2019)Overload control for virtual network functions under CPU contentionFuture Generation Computer Systems10.1016/j.future.2019.04.007Online publication date: Apr-2019
  • (2016)Workload interleaving with performance guarantees in data centersNOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium10.1109/NOMS.2016.7502934(967-972)Online publication date: Apr-2016
  • (2012)Queue Modeling of Semiconductor Test Equipment Using Effective Background ProcessComputer Applications for Modeling, Simulation, and Automobile10.1007/978-3-642-35248-5_3(15-19)Online publication date: 2012
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGOPS Operating Systems Review
ACM SIGOPS Operating Systems Review  Volume 39, Issue 5
SOSP '05
December 2005
290 pages
ISSN:0163-5980
DOI:10.1145/1095809
Issue’s Table of Contents
  • cover image ACM Conferences
    SOSP '05: Proceedings of the twentieth ACM symposium on Operating systems principles
    October 2005
    259 pages
    ISBN:1595930795
    DOI:10.1145/1095810
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 October 2005
Published in SIGOPS Volume 39, Issue 5

Check for updates

Author Tags

  1. background processing
  2. disk scheduler
  3. idletime scheduling
  4. network scheduler
  5. preemption interval
  6. queuing
  7. resource scheduler

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)15
  • Downloads (Last 6 weeks)1
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2019)Overload control for virtual network functions under CPU contentionFuture Generation Computer Systems10.1016/j.future.2019.04.007Online publication date: Apr-2019
  • (2016)Workload interleaving with performance guarantees in data centersNOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium10.1109/NOMS.2016.7502934(967-972)Online publication date: Apr-2016
  • (2012)Queue Modeling of Semiconductor Test Equipment Using Effective Background ProcessComputer Applications for Modeling, Simulation, and Automobile10.1007/978-3-642-35248-5_3(15-19)Online publication date: 2012
  • (2010)Optimality analysis of energy-performance trade-off for server farm managementPerformance Evaluation10.1016/j.peva.2010.08.00967:11(1155-1171)Online publication date: 1-Nov-2010
  • (2007)DiscNice: User-level Regulation of Disk BandwidthIPSJ Digital Courier10.2197/ipsjdc.3.8003(800-815)Online publication date: 2007
  • (2020)A Smart Background Scheduler for Storage Systems2020 28th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS)10.1109/MASCOTS50786.2020.9285967(1-8)Online publication date: 17-Nov-2020
  • (2019)Row reduction process for matrices of scalar operatorsACM Communications in Computer Algebra10.1145/3363520.336352253:1(23-30)Online publication date: 18-Sep-2019
  • (2019)Spatial Auto-regressive Dependency Interpretable Learning Based on Spatial Topological ConstraintsACM Transactions on Spatial Algorithms and Systems10.1145/33398235:3(1-28)Online publication date: 12-Aug-2019
  • (2017)Reasoning on data partitioning for single-round multi-join evaluation in massively parallel systemsCommunications of the ACM10.1145/304106360:3(93-100)Online publication date: 21-Feb-2017
  • (2016)PREFiguREACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/28723311:3(1-27)Online publication date: 7-May-2016
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media