Article

Free access

Borrowed-virtual-time (BVT) scheduling: supporting latency-sensitive threads in a general-purpose scheduler

Authors:

Kenneth J. Duda,

David R. CheritonAuthors Info & Claims

SOSP '99: Proceedings of the seventeenth ACM symposium on Operating systems principles

Pages 261 - 276

https://doi.org/10.1145/319151.319169

Published: 12 December 1999 Publication History

PDF eReader

Abstract

Systems need to run a larger and more diverse set of applications, from real-time to interactive to batch, on uniprocessor and multiprocessor platforms. However, most schedulers either do not address latency requirements or are specialized to complex real-time paradigms, limiting their applicability to general-purpose systems.In this paper, we present Borrowed-Virtual-Time (BVT) Scheduling, showing that it provides low-latency for real-time and interactive applications yet weighted sharing of the CPU across applications according to system policy, even with thread failure at the real-time level, all with a low-overhead implementation on multiprocessors as well as uniprocessors. It makes minimal demands on application developers, and can be used with a reservation or admission control module for hard real-time applications.

References

[1]

S. Brin. Personal communication. www. google, corn, 1999.]]

Google Scholar

[2]

A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queueing algorithm. Proceedings ACM SIGCOMM, pages 1-12, September 1989.]]

Digital Library

Google Scholar

[3]

K. J. Duda and D. R. Cheriton. Borrowedvirtual-time (BVT) scheduling, ht t p: / / wwwdsg. stanford, edu/pub/bvt, html, 2000.]]

Google Scholar

[4]

I. Stoika et al. A proportional-share resource allocation algorithm for real-time, time-shared systems. In Proceedings of the 17th IEEE Real-Time Systems Symposium, pages 51-59, December 1996.]]

Digital Library

Google Scholar

[5]

P. Goyal, X. Guo, and H. Vin. A hierarchical CPU scheduler for multimedia operating systems. Proceedings of the Usenix Symposium on Operating System Design and Implementation '96, pages 107-122, October 1996.]]

Digital Library

Google Scholar

[6]

M. Jones, J. Barrera, A. Forin, P. Leach, D. Rosu, and M. Rosu. An overview of the Rialto real-time architecture. Microsoft Research Technical Report MSR-TR- 96-13, July 1996. Microsoft Inc., Redmond, WA.]]

Google Scholar

[7]

M. Jones, D. Rosu, and M. Rosu. CPU reservations and time constraints: Efficient, predictable scheduling of independent activities. Proceedings of the 16th ACM Symposium on Operating System Principles, pages 198-211, October 1997.]]

Digital Library

Google Scholar

[8]

C. W. Mercer, S. Savage, and H. Tokuda. Processor capacity reserves for multimedia operating systems. Proceedings of the IEEE International Conference on Multimedia Computing and Systems, pages 90-99, May 1994.]]

Crossref

Google Scholar

[9]

J. Mogul and K. Ramakrishnan. Eliminating receive livelock in an interrupt-driven kernel. ACM Trans. on Computer Systems, 15(3):217-252, August 1997.]]

Digital Library

Google Scholar

[10]

J. Nieh, J. Hanko, J. Northcutt, and G. Wall. SVR4 UNIX scheduler unacceptable for multimedia applications. Proceedings of the IEEE International Conference on Multimedia Computing and Systems, pages 35-48, November 1993.]]

Digital Library

Google Scholar

[11]

J. Nieh and M. Lam. The design, implementation, and evaluation of SMART: A scheduler for multimedia applications. Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, pages 184-197, October 1997.]]

Digital Library

Google Scholar

[12]

L. Rowe, K. Patel, and B. Smith. Performance of a software MPEG video decoder. Proc. ACM Multimedia 93, pages 31-39, August 1993.]]

Digital Library

Google Scholar

[13]

J. Stankovic and K. Ramamritham. The Spring Kernel: A new paradigm for real-time systems. IEEE Software, 8(3):62-73, 1991.]]

Digital Library

Google Scholar

[14]

C. Waldspurger and W. Weihl. Lottery scheduling: Flexible proportional-share resource mangement. Proceedings of the First Symposium on Operating System Design and Implementation, pages 1-11, November 1994.]]

Digital Library

Google Scholar

Cited By

View all

Zhang DWu QZhao YLi ZHe PZhang YDuan XZhang YMiao GTong JXie G(2023)MALT: Fine-Grained Microservice Profiling for Request Latency Anomaly Localization2023 IEEE International Conference on High Performance Computing & Communications, Data Science & Systems, Smart City & Dependability in Sensor, Cloud & Big Data Systems & Application (HPCC/DSS/SmartCity/DependSys)10.1109/HPCC-DSS-SmartCity-DependSys60770.2023.00025(114-121)Online publication date: 17-Dec-2023
https://doi.org/10.1109/HPCC-DSS-SmartCity-DependSys60770.2023.00025
Demoulin HFried JPedisich IKogias MLoo BPhan LZhang I(2021)When Idling is IdealProceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles10.1145/3477132.3483571(621-637)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3477132.3483571
Kaffes KChong THumphries JBelay AMazières DKozyrakis CLorch JYu M(2019)ShinjukuProceedings of the 16th USENIX Conference on Networked Systems Design and Implementation10.5555/3323234.3323264(345-359)Online publication date: 26-Feb-2019
https://dl.acm.org/doi/10.5555/3323234.3323264
Show More Cited By

Index Terms

Borrowed-virtual-time (BVT) scheduling: supporting latency-sensitive threads in a general-purpose scheduler
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems

Recommendations

Borrowed-virtual-time (BVT) scheduling: supporting latency-sensitive threads in a general-purpose scheduler

Systems need to run a larger and more diverse set of applications, from real-time to interactive to batch, on uniprocessor and multiprocessor platforms. However, most schedulers either do not address latency requirements or are specialized to complex ...
Real-Time Job Scheduling in Hypercube Systems
ICPP '97: Proceedings of the international Conference on Parallel Processing

In this paper, we present the problem of scheduling real-time jobs in a hypercube system and propose a scheduling algorithm. The goals of the proposed scheduling algorithm are to determine whether all jobs can complete their processing before their ...
Scheduling issues in real-time systems

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SOSP '99: Proceedings of the seventeenth ACM symposium on Operating systems principles

December 1999

300 pages

ISBN:1581131402

DOI:10.1145/319151

Chairmen:
David Kotz
Dartmouth College, Hanover, NH
,
John Wilkes
HP Laboratories

ACM SIGOPS Operating Systems Review Volume 33, Issue 5
Dec. 1999
291 pages
ISSN:0163-5980
DOI:10.1145/319344
Editors:
David Kotz
Dartmout College, Hanover, NH
,
John Wilkes
HP Laboratories
Issue’s Table of Contents

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: 12 December 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SOSP99

Sponsor:

SIGOPS

SOSP99: 17th Symposium on Operating Systems Principles

December 12 - 15, 1999

South Carolina, Charleston, USA

Acceptance Rates

SOSP '99 Paper Acceptance Rate 19 of 90 submissions, 21%;

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

196
Total Citations
View Citations
2,684
Total Downloads

Downloads (Last 12 months)306
Downloads (Last 6 weeks)40

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhang DWu QZhao YLi ZHe PZhang YDuan XZhang YMiao GTong JXie G(2023)MALT: Fine-Grained Microservice Profiling for Request Latency Anomaly Localization2023 IEEE International Conference on High Performance Computing & Communications, Data Science & Systems, Smart City & Dependability in Sensor, Cloud & Big Data Systems & Application (HPCC/DSS/SmartCity/DependSys)10.1109/HPCC-DSS-SmartCity-DependSys60770.2023.00025(114-121)Online publication date: 17-Dec-2023
https://doi.org/10.1109/HPCC-DSS-SmartCity-DependSys60770.2023.00025
Demoulin HFried JPedisich IKogias MLoo BPhan LZhang I(2021)When Idling is IdealProceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles10.1145/3477132.3483571(621-637)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3477132.3483571
Kaffes KChong THumphries JBelay AMazières DKozyrakis CLorch JYu M(2019)ShinjukuProceedings of the 16th USENIX Conference on Networked Systems Design and Implementation10.5555/3323234.3323264(345-359)Online publication date: 26-Feb-2019
https://dl.acm.org/doi/10.5555/3323234.3323264
Zhao YSuo KWu XRao JWu SJin HWeissman JButt ASmirni E(2019)Preemptive Multi-Queue Fair QueuingProceedings of the 28th International Symposium on High-Performance Parallel and Distributed Computing10.1145/3307681.3326605(147-158)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3307681.3326605
Hoganson KWong KShen CBrown D(2018)Multi-core real-time scheduling in multilevel feedback queue with starvation mitigation (MLFQ-RT)Proceedings of the 2018 ACM Southeast Conference10.1145/3190645.3190668(1-6)Online publication date: 29-Mar-2018
https://dl.acm.org/doi/10.1145/3190645.3190668
Wang ZYang JMelhem RChilders BZhang YGuo M(2017)Quality of Service Support for Fine-Grained Sharing on GPUsACM SIGARCH Computer Architecture News10.1145/3140659.308020345:2(269-281)Online publication date: 24-Jun-2017
https://dl.acm.org/doi/10.1145/3140659.3080203
Prekas GKogias MBugnion E(2017)ZygOSProceedings of the 26th Symposium on Operating Systems Principles10.1145/3132747.3132780(325-341)Online publication date: 14-Oct-2017
https://dl.acm.org/doi/10.1145/3132747.3132780
Wang ZYang JMelhem RChilders BZhang YGuo M(2017)Quality of Service Support for Fine-Grained Sharing on GPUsProceedings of the 44th Annual International Symposium on Computer Architecture10.1145/3079856.3080203(269-281)Online publication date: 24-Jun-2017
https://dl.acm.org/doi/10.1145/3079856.3080203
Hoganson KBrown J(2017)Intelligent Mitigation in Multilevel Feedback QueuesProceedings of the 2017 ACM Southeast Conference10.1145/3077286.3077319(158-163)Online publication date: 13-Apr-2017
https://dl.acm.org/doi/10.1145/3077286.3077319
Li NJiang HFeng DShi Z(2017)Customizable SLO and Its Near-Precise Enforcement for Storage BandwidthACM Transactions on Storage10.1145/299845413:1(1-25)Online publication date: 16-Feb-2017
https://dl.acm.org/doi/10.1145/2998454
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Borrowed-virtual-time (BVT) scheduling: supporting latency-sensitive threads in a general-purpose scheduler

Real-Time Job Scheduling in Hypercube Systems

Scheduling issues in real-time systems