article

Free access

Bringing real-time scheduling theory and practice closer for multimedia computing

Authors:

R. Gopalakrishnan,

Gurudatta M. ParulkarAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 24, Issue 1

Pages 1 - 12

https://doi.org/10.1145/233008.233017

Published: 15 May 1996 Publication History

Abstract

This paper seeks to bridge the gap between theory and practice of real-time scheduling in the domain of high speed multimedia networking. We show that the strict preemptive nature of real-time scheduling leads to more context switching, and requires system calls for concurrency control. We present our scheduling scheme called rate-monotonic with delayed preemption (rmdp) and show how it reduces both these overheads. We then develop the analytical framework to analyze rmdp and other scheduling schemes that lie in the region between strict (immediate) preemption and no preemption. Our idealized scheduler simulation methodology accounts for the blocking introduced by these schemes under the usual assumption that the time for context switching and preemption is zero. We derive simpler schedulability tests for non-preemptive scheduling, and prove a variant of rate-monotonic scheduling that has fewer preemptions. Our measurements on Sparc and Pentium platforms, show that for the workloads we considered, Rmdp increases useful utilization by as much as 8%. Thus our scheduling policies have the potential to improve performance over existing methods.

References

[1]

Chen, J.B., et. aI., "The Measured Performance of Personal Computer Operating Systems," 15th ACM SOSP, Dec. 1995.

Digital Library

[2]

Gopalakrishnan R., Parulkar G.M., "Real-time Upcalls: A Mechanism to Provide Real-time Processing guarantees," Tech. Rep. WUCS-95-06, Washington University, St.Louis, 1995.

[3]

Gopalakrishnan R., Parulkar G.M., "A Generalized Preemption Model for Real-time Scheduling," Tech. Rep. WUCS-96-04, Washington University, St.Louis, 1996.

[4]

Gopalakrishnan R., Parulkar G.M., "A Real-time Upcall Facility for Protocol Processing with QoS Guarantees," (Poster) 15th ACM SOSP, Dec. 1995.

Digital Library

[5]

Jeffay, K., Stanat, D.F., Martel, C.U., "On Non- Preemptive Scheduling of Periodic and Sporadic Tasks," 12th IEEE Real-Time @stems Symposium, Dec 1991.

[6]

Jeffay, K., Stone, D.L., "Accounting for Interrupt Handling Costs in Dynamic Priority Task Systems," 14th IEEE Real-Time Systems Symposium, Dec 1993.

[7]

Katcher et. aI., "Engineering and Analysis of Fixed Priority Schedulers," IEEE Transactions on Software Engineering, Sep 1993.

Digital Library

[8]

Katcher, D.I., "Engineering and Analysis of Realtime Operating Systems," PhD Thesis, Carnegie Mellon University, 1994.

Digital Library

[9]

Khanna, S., et. al., "Reaitime Scheduling in SunOS5.0," USENIX, Winter 1992, pp.375-390.

[10]

Lehoczky, J.P., Sha, L., "Performance of Real- Time Bus Scheduling Algorithms," A CM Performance Evaluation Review, Vol.14, No.l, May 1986.

Digital Library

[11]

Liu, C.L. and Layland, J.W., "Scheduling Algo= rithms for Multiprogramming in a Hard-Real-Time Environment," JACM, Vol. 20,No. 1, January 1973.

Digital Library

[12]

Pingali, S., "Protocol and Real Time Scheduling Issues for Multimedia Applications," PhD Thesis, University of Massachusetts, Amherst, Sep 1994.

Digital Library

[13]

Sha, L. et. al., "Priority Inheritance Protocols: An Approach to Real:Time Synchronization," IEEE Transactions on Computers, Vol.39, No.9, Sep 1990.

Digital Library

[14]

Sha, L., Lehoczky, J.P., Rajkumar, R., "Solutions for Some Practical Problems in Prioritized Preemptive Scheduling," IEEE Real-Time Systems Symposium, Dec 1986.

[15]

Tokuda, H., Nakajima, T., Rao, P., "Real-Time Mach: Towards Predictable Real-time Systems," USENIX Mach Workshop, Oct 1990.

Cited By

Bhura SAlvi A(2015)Scheduling Real-Time Transactions Using Deferred Preemptive TechniqueProceedings of the Second International Conference on Computer and Communication Technologies10.1007/978-81-322-2523-2_61(631-638)Online publication date: 4-Sep-2015
https://doi.org/10.1007/978-81-322-2523-2_61
Baid PPrashanth SRaveendran B(2014)LLFRP: An Energy Efficient Variant of LLF with Reduced Pre-emptions for Real – Time SystemsGSTF Journal on Computing (JoC)10.7603/s40601-013-0043-83:4Online publication date: 26-May-2014
https://doi.org/10.7603/s40601-013-0043-8
Ardagna DGibilisco GCiavotta MLavrentev A(2014)A Multi-model Optimization Framework for the Model Driven Design of Cloud ApplicationsSearch-Based Software Engineering10.1007/978-3-319-09940-8_5(61-76)Online publication date: 2014
https://doi.org/10.1007/978-3-319-09940-8_5
Show More Cited By

Index Terms

Bringing real-time scheduling theory and practice closer for multimedia computing
1. Computing methodologies
  1. Modeling and simulation
    1. Simulation types and techniques
2. Software and its engineering
  1. Software creation and management
    1. Designing software
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Concurrency control
        Scheduling

Recommendations

Bringing real-time scheduling theory and practice closer for multimedia computing
SIGMETRICS '96: Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

This paper seeks to bridge the gap between theory and practice of real-time scheduling in the domain of high speed multimedia networking. We show that the strict preemptive nature of real-time scheduling leads to more context switching, and requires ...
Preference-oriented fixed-priority scheduling for periodic real-time tasks

A preference priority assignment (PPA) scheme that explicitly incorporates the ASAP and ALAP execution preferences of periodic real-time tasks is proposed.An online dual-queue based preference-oriented fixed- priority (POFP) scheduler is proposed 4, ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 24, Issue 1

May 1996

273 pages

ISSN:0163-5999

DOI:10.1145/233008

Editors:
Blaine E. Gaither
Hewlett-Packard, Fort Collins, CO
,
Daniel A. Reed
Univ. of Illinois, Urbana

Issue’s Table of Contents

SIGMETRICS '96: Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems
May 1996
279 pages
ISBN:0897917936
DOI:10.1145/233013
Chairman:
Daniel A. Reed
Univ. of Illinois, Urbana
,
Editor:
Blaine D. Gaither
Hewlett-Packard, Fort Collins, CO

Copyright © 1996 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 May 1996

Published in SIGMETRICS Volume 24, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

55
Total Citations
View Citations
546
Total Downloads

Downloads (Last 12 months)70
Downloads (Last 6 weeks)15

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bhura SAlvi A(2015)Scheduling Real-Time Transactions Using Deferred Preemptive TechniqueProceedings of the Second International Conference on Computer and Communication Technologies10.1007/978-81-322-2523-2_61(631-638)Online publication date: 4-Sep-2015
https://doi.org/10.1007/978-81-322-2523-2_61
Baid PPrashanth SRaveendran B(2014)LLFRP: An Energy Efficient Variant of LLF with Reduced Pre-emptions for Real – Time SystemsGSTF Journal on Computing (JoC)10.7603/s40601-013-0043-83:4Online publication date: 26-May-2014
https://doi.org/10.7603/s40601-013-0043-8
Ardagna DGibilisco GCiavotta MLavrentev A(2014)A Multi-model Optimization Framework for the Model Driven Design of Cloud ApplicationsSearch-Based Software Engineering10.1007/978-3-319-09940-8_5(61-76)Online publication date: 2014
https://doi.org/10.1007/978-3-319-09940-8_5
Bertogna MXhani OMarinoni MEsposito FButtazzo G(2011)Optimal Selection of Preemption Points to Minimize Preemption OverheadProceedings of the 2011 23rd Euromicro Conference on Real-Time Systems10.1109/ECRTS.2011.28(217-227)Online publication date: 5-Jul-2011
https://dl.acm.org/doi/10.1109/ECRTS.2011.28
Bertogna MBaruah S(2010)Limited Preemption EDF Scheduling of Sporadic Task SystemsIEEE Transactions on Industrial Informatics10.1109/TII.2010.20496546:4(579-591)Online publication date: Nov-2010
https://doi.org/10.1109/TII.2010.2049654
Craciunas SKirsch CSokolova A(2010)Response Time versus Utilization in Scheduler Overhead AccountingProceedings of the 2010 16th IEEE Real-Time and Embedded Technology and Applications Symposium10.1109/RTAS.2010.14(291-300)Online publication date: 12-Apr-2010
https://dl.acm.org/doi/10.1109/RTAS.2010.14
Bertogna MButtazzo GMarinoni MYao GEsposito FCaccamo M(2010)Preemption Points Placement for Sporadic Task SetsProceedings of the 2010 22nd Euromicro Conference on Real-Time Systems10.1109/ECRTS.2010.9(251-260)Online publication date: 6-Jul-2010
https://dl.acm.org/doi/10.1109/ECRTS.2010.9
Park MYoo HChae J(2009)Integration of Preemption Threshold and Quantum-Based Scheduling for Schedulability Enhancement of Fixed Priority TasksProceedings of the 2009 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications10.1109/RTCSA.2009.60(503-510)Online publication date: 24-Aug-2009
https://dl.acm.org/doi/10.1109/RTCSA.2009.60
Park MYoo HChae JKim C(2008)Quantum-Based Fixed Priority SchedulingProceedings of the 2008 International Conference on Advanced Computer Theory and Engineering10.1109/ICACTE.2008.162(64-68)Online publication date: 20-Dec-2008
https://dl.acm.org/doi/10.1109/ICACTE.2008.162
Kuhns FSchmidt DLevine D(1999)The design and performance of a real-time I/O subsystemProceedings of the Fifth IEEE Real-Time Technology and Applications Symposium10.1109/RTTAS.1999.777670(154-163)Online publication date: 1999
https://doi.org/10.1109/RTTAS.1999.777670
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Issue’s Table of Contents