Article

Idletime scheduling with preemption intervals

Authors:

Joseph D. TouchAuthors Info & Claims

SOSP '05: Proceedings of the twentieth ACM symposium on Operating systems principles

Pages 249 - 262

https://doi.org/10.1145/1095810.1095835

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

[13]

Van Jacobson, Robert Braden and Dave Borman. TCP Extensions for High Performance. RFC 1323, May 1992.]]

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

[24]

Matt W. Mutka and Miron Livny. The available capacity of a privately owned workstation environment. Performance Evaluation, Vol. 12, 1991, pp. 269--284.]]

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

[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

Kachmar MKaeli D(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
https://doi.org/10.1109/MASCOTS50786.2020.9285967
Abramov SBarkatou M(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
https://dl.acm.org/doi/10.1145/3363520.3363522
Zhao LGkountouna OPfoser D(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
https://dl.acm.org/doi/10.1145/3339823
Show More Cited By

Index Terms

Idletime scheduling with preemption intervals
1. Software and its engineering
  1. Software creation and management
    1. Designing software
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Communications management
        Buffering
        Input / output
        Message passing
        Process management
        Concurrency control
        Scheduling

Recommendations

Idletime scheduling with preemption intervals
SOSP '05

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 ...
Improved feasibility of fixed-priority scheduling with deferred preemption using preemption thresholds for preemption points
RTNS '13: Proceedings of the 21st International conference on Real-Time Networks and Systems

This paper aims at advancing the relative strength of limited-preemptive schedulers by improving the feasibility of a task set and simultaneously limiting, or even precluding, arbitrary preemptions. In particular, we present a refinement of existing ...
On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals

We consider the problem of scheduling n unit-time jobs with multiple release time/deadline intervals, which are intervals of time in which the job can be scheduled. A feasible schedule is one in which each job is run in its entirety within one of its ...

Reviews

Reviewer: Ivan Flores

This study is aimed at reducing idle time in large computer systems. Unfortunately, the paper contains too much jargon and is obviously meant for a specialized few. The study seems to ignore the fact that large systems use multiprocessing and multitasking, allowing many tasks to run simultaneously; in contrast, small systems accept idle time as a given. The section on idle time scheduling introduces the preemptive interval that follows each foreground action during which no action takes place. Isn't this a waste of time, even though slight__?__ The discussion that follows leaves me in the dark. If work can be done during this period, how can it be called idle time__?__ The next section, "Implementation," uses a state diagram to display transitions that may occur between idle, foreground, background, and preemptive (when the system stops to check things out) tasks. In summary, this paper lacks clarity and, moreover, quantitative results. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

General Chair:
Andrew Herbert
Microsoft Research, UK
,
Program Chair:
Ken Birman
Cornell University, USA

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

Copyright © 2005 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 October 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SOSP05

Sponsor:

SOSP05: ACM SIGOPS 20th Symposium on Operating Systems Principles 2005

October 23 - 26, 2005

Brighton, United Kingdom

Acceptance Rates

Overall Acceptance Rate 174 of 961 submissions, 18%

Upcoming Conference

SOSP '25

Sponsor:
sigops

ACM SIGOPS 31st Symposium on Operating Systems Principles

October 13 - 16, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

68
Total Citations
View Citations
1,090
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kachmar MKaeli D(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
https://doi.org/10.1109/MASCOTS50786.2020.9285967
Abramov SBarkatou M(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
https://dl.acm.org/doi/10.1145/3363520.3363522
Zhao LGkountouna OPfoser D(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
https://dl.acm.org/doi/10.1145/3339823
Ameloot TGeck GKetsman BNeven FSchwentick T(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
https://dl.acm.org/doi/10.1145/3041063
Yan FMountrouidou XRiska ASmirni E(2016)PREFiguREACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/28723311:3(1-27)Online publication date: 7-May-2016
https://dl.acm.org/doi/10.1145/2872331
Amvrosiadis GBrown AGoel AMiller EHand S(2015)Opportunistic storage maintenanceProceedings of the 25th Symposium on Operating Systems Principles10.1145/2815400.2815424(457-473)Online publication date: 4-Oct-2015
https://dl.acm.org/doi/10.1145/2815400.2815424
Lin P(2015)Double Verification Secret Sharing Mechanism Based on Adaptive Pixel Pair MatchingACM Transactions on Multimedia Computing, Communications, and Applications10.1145/270029111:3(1-17)Online publication date: 5-Feb-2015
https://dl.acm.org/doi/10.1145/2700291
YAMADA HKONO K(2014)A VMM-Level Approach to Shortening Downtime of Operating Systems Reboots in Software UpdatesIEICE Transactions on Information and Systems10.1587/transinf.2014EDP7031E97.D:10(2663-2675)Online publication date: 2014
https://doi.org/10.1587/transinf.2014EDP7031
Yamada HKono K(2013)Traveling forward in time to newer operating systems using ShadowRebootACM SIGPLAN Notices10.1145/2517326.245153648:7(121-130)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2517326.2451536
Skowron PBiskup MHeldt ŁDubnicki CKat RBaker MToledo S(2013)Fuzzy adaptive control for heterogeneous tasks in high-performance storage systemsProceedings of the 6th International Systems and Storage Conference10.1145/2485732.2485737(1-11)Online publication date: 30-Jun-2013
https://dl.acm.org/doi/10.1145/2485732.2485737
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents