article

Free access

Scheduling periodic and aperiodic tasks in hard real-time computing systems

Authors:

Tein-Hsiang Lin,

Wernhuar TarngAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 19, Issue 1

Pages 31 - 38

https://doi.org/10.1145/107972.107976

Published: 02 April 1991 Publication History

PDF eReader

Abstract

Scheduling periodic and aperiodic tasks to meet their time constraints has been an important issue in the design of real-time computing systems. Usually, the task scheduling algorithms in such systems must satisfy the deadlines of periodic tasks and provide fast response times for aperiodic tasks. A simple and efficient approach to scheduling real-time tasks is the use of a periodic server in a static preemptive scheduling algorithm. Periodic tasks, including the server, are scheduled at priori to meet their deadlines according to the knowledge of their periods and computation times. The scheduling of aperiodic tasks is then managed by the periodic server during its service time. In this paper, a new scheduling algorithm is proposed. The new algorithm creates a periodic server which will have the highest priority but not necessarily the shortest period. The server is suspended to reduce the overhead if there are no aperiodic tasks waiting, and is activated immediately upon the arrival of the next aperiodic task. After activated, the server performs its duty periodically until all waiting aperiodic tasks are completed. For a set of tasks scheduled by this algorithm, the deadlines of periodic tasks are guaranteed by a deterministic feasibility check, and the mean response time of aperiodic tasks are estimated using a queueing model. Based on the analytical results, we can determine the period and service time of the server producing the minimum mean response time for aperiodic tasks. The analytical results are compared with simulation results to demonstrate the correctness of our model.

References

[1]

C. Liu and J. Layland, "Scheduling algorithms for multip~ogramming in a hard real-time environment," J. ACM, vol. 20, Jan. 1973.

Digital Library

Google Scholar

[2]

,l. Lehoczky, L. Sha, and J. Strosnider, "Enhanced aperiodic responsiveness in hard real-time environments," Proc. t987 Real- T~rne System Syrup., 1987.

Google Scholar

[3]

B. Sprunt, J. Lehoczky, and L. Sha, "Exploiting unused peiiodic time for aperiodic service using the exte,~ded priority exchange algorithm," Proc. 1988 Real- Time System Syrnp., 1988.

Google Scholar

[4]

Lehoczky, Sha, and Ding, "The rate monotonic scheduli,lg algorithm- exact characterization and average case bchavior," Technical Report Dept. Statistics, Carnegie- A/ellon f/_, Mar. 1988.

Google Scholar

[5]

L. I(leinrock, "Queueing systems," Volume 1: Theory, IV~lcg, New York, 1975.

Google Scholar

Cited By

View all

Su PTan SLiu ZYeh W(2022)A Mixed-Heuristic Quantum-Inspired Simplified Swarm Optimization Algorithm for scheduling of real-time tasks in the multiprocessor systemApplied Soft Computing10.1016/j.asoc.2022.109807131(109807)Online publication date: Dec-2022
https://doi.org/10.1016/j.asoc.2022.109807
Vijay RYadav RAgrawal S(2009)Online Speed Fine Tuning Technique for Energy Minimization of Mixed Task Set2009 Annual IEEE India Conference10.1109/INDCON.2009.5409451(1-4)Online publication date: Dec-2009
https://doi.org/10.1109/INDCON.2009.5409451
Asadi MMenhaj MYavari E(2009)A Modified BCE Algorithm for Fault-Tolerance Scheduling of Periodic Tasks in Hard Real-Time SystemsProceedings of the 2009 Third Asia International Conference on Modelling & Simulation10.1109/AMS.2009.63(287-291)Online publication date: 25-May-2009
https://dl.acm.org/doi/10.1109/AMS.2009.63
Show More Cited By

Index Terms

Scheduling periodic and aperiodic tasks in hard real-time computing systems

Recommendations

Scheduling periodic and aperiodic tasks in hard real-time computing systems
SIGMETRICS '91: Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems

Scheduling periodic and aperiodic tasks to meet their time constraints has been an important issue in the design of real-time computing systems. Usually, the task scheduling algorithms in such systems must satisfy the deadlines of periodic tasks and ...
Dynamic Real-time Scheduling of Firm Periodic Tasks with Hard and Soft Aperiodic Tasks

In this paper, we address the problem of the dynamic scheduling of skippable periodic task sets (i.e., period tasks allowing occasional skips of instances), together with aperiodic tasks. Scheduling of tasks is handled thanks to the merging of two ...
A Reservation-Based Algorithm for Scheduling Both Periodic and Aperiodic Real-Time Tasks

This paper considers the problem of scheduling both periodic and aperiodic tasks in real-time systems. A new, called reservation-based (RB), algorithm is proposed for ordering the execution of real-time tasks. This algorithm can guarantee all periodic-...

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 19, Issue 1

May 1991

223 pages

ISSN:0163-5999

DOI:10.1145/107972

Editor:
Tom W. Keller
IBM Corp., Austin, TX

Issue’s Table of Contents

SIGMETRICS '91: Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems
April 1991
228 pages
ISBN:0897913922
DOI:10.1145/107971
Chairman:
Tom W. Keller
IBM Corp, Austin, TX

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: 02 April 1991

Published in SIGMETRICS Volume 19, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
2,116
Total Downloads

Downloads (Last 12 months)185
Downloads (Last 6 weeks)37

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Su PTan SLiu ZYeh W(2022)A Mixed-Heuristic Quantum-Inspired Simplified Swarm Optimization Algorithm for scheduling of real-time tasks in the multiprocessor systemApplied Soft Computing10.1016/j.asoc.2022.109807131(109807)Online publication date: Dec-2022
https://doi.org/10.1016/j.asoc.2022.109807
Vijay RYadav RAgrawal S(2009)Online Speed Fine Tuning Technique for Energy Minimization of Mixed Task Set2009 Annual IEEE India Conference10.1109/INDCON.2009.5409451(1-4)Online publication date: Dec-2009
https://doi.org/10.1109/INDCON.2009.5409451
Asadi MMenhaj MYavari E(2009)A Modified BCE Algorithm for Fault-Tolerance Scheduling of Periodic Tasks in Hard Real-Time SystemsProceedings of the 2009 Third Asia International Conference on Modelling & Simulation10.1109/AMS.2009.63(287-291)Online publication date: 25-May-2009
https://dl.acm.org/doi/10.1109/AMS.2009.63
Toledo MJ. J(2007)Priority tasks allocation through the maximum entropy principleProceedings of the 8th Conference on 8th WSEAS International Conference on Automation and Information - Volume 810.5555/1347952.1347958(271-276)Online publication date: 19-Jun-2007
https://dl.acm.org/doi/10.5555/1347952.1347958
Abdelzaher TSharma VLu C(2004)A Utilization Bound for Aperiodic Tasks and Priority Driven SchedulingIEEE Transactions on Computers10.1109/TC.2004.126183953:3(334-350)Online publication date: 1-Mar-2004
https://dl.acm.org/doi/10.1109/TC.2004.1261839
Han CShin KWu J(2003)A Fault-Tolerant Scheduling Algorithm for Real-Time Periodic Tasks with Possible Software FaultsIEEE Transactions on Computers10.1109/TC.2003.118395052:3(362-372)Online publication date: 1-Mar-2003
https://dl.acm.org/doi/10.1109/TC.2003.1183950
Abdelzaher TAndersson BJonsson J(2002)The aperiodic multiprocessor utilization bound for liquid tasksProceedings. Eighth IEEE Real-Time and Embedded Technology and Applications Symposium10.1109/RTTAS.2002.1137392(173-184)Online publication date: 2002
https://doi.org/10.1109/RTTAS.2002.1137392
Abdelzaher TChenyang Lu (2001)Schedulability analysis and utilization bounds for highly scalable real-time servicesProceedings Seventh IEEE Real-Time Technology and Applications Symposium10.1109/RTTAS.2001.929862(15-25)Online publication date: 2001
https://doi.org/10.1109/RTTAS.2001.929862
Chang HChang RShih WChang R(2001)Reschedulable-Group-SCAN scheme for mixed real-time/non-real-time disk scheduling in a multimedia systemJournal of Systems and Software10.1016/S0164-1212(01)00058-959:2(143-152)Online publication date: 1-Nov-2001
https://dl.acm.org/doi/10.1016/S0164-1212%2801%2900058-9
Poledna S(1995)Tolerating Sensor Timing Faults in Highly Responsive Hard Real-Time SystemsIEEE Transactions on Computers10.1109/12.36453044:2(181-191)Online publication date: 1-Feb-1995
https://dl.acm.org/doi/10.1109/12.364530
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.

Abstract

References

Cited By

Index Terms

Recommendations