research-article

Optimal RM scheduling for simply periodic tasks on uniform multiprocessors

Authors:

Myoung-Jo Jung,

Yeong Rak Seong,

Cheol-Hoon LeeAuthors Info & Claims

ICHIT '09: Proceedings of the 2009 International Conference on Hybrid Information Technology

Pages 383 - 389

https://doi.org/10.1145/1644993.1645064

Published: 27 August 2009 Publication History

Abstract

The problem of scheduling simply periodic task systems upon a uniform multiprocessor is considered. Each processor in a uniform multiprocessor is characterized by the speed or computing capacity, with the interpretation that a job executing on a processor with speed s for t time units completes (s x t) units of execution. In the partitioned approach to scheduling periodic tasks upon multiprocessors, each task is assigned to a specific processor and all jobs generated by a task are required to execute upon the same processor to which the task is assigned. However, the partitioning of periodic task systems requires solving the bin-packing problem, which is known to be intractable (NP-hard in the strong sense). This paper presents a global scheduling algorithm which transforms a given simply periodic task system into another using a "task-splitting" technique. Each transformed simply periodic task system is guaranteed to be successfully scheduled upon any uniform multiprocessor using a partitioned scheduling algorithm. The rate-monotonic (RM) algorithm is chosen for scheduling tasks on each processor. It is proven that the proposed algorithm achieves the theoretical maximum utilization bound upon any uniform multiprocessor platform. Therefore, the proposed algorithm is optimal in the sense of maximizing achievable utilization for simply periodic task system on uniform multiprocessors.

References

[1]

J. Anderson and A. Srinivasan, \Early-Release Fair Scheduling", Proc. of the Euromicro Conference on Real-Time Systems, pp. 35--43, June 2000.

Digital Library

[2]

B. Andersson and E. Tovar, \Multiprocessor Scheduling with Few Preemptions", Proc. of the IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, pp. 322--334. Aug. 2006.

Digital Library

[3]

B. Andersson and J. Jonsson, \The Utilization Bounds of Partitioned and Pfair Static-Priority Scheduling on Multiprocessors are 50%", Proc. of the Euromicro Conference on Real-Time Systems, pp. 33--40, July 2003.

[4]

T. P. Baker, \An Analysis of EDF Schedulability on a Multiprocessor", IEEE Tranactions on Parallel and Distributed Systems, vol. 16, pp. 760--768, Aug. 2005.

Digital Library

[5]

S. Baruah, J. Gehrke, and C. G. Plaxton, \Fast Scheduling of Periodic Tasks on Multiple Resources", Proc. of the International Parallel Processing Symposium, pp. 280--288, April 1995.

Digital Library

[6]

S. Baruah, et al., \Proportionate Progress: A Notion of Fairness in Resource Allocation", Algorithmica, vol. 15, pp. 600--625, 1996.

Digital Library

[7]

S. Baruah and Goossens. J, \Rate-Monotonic Scheduling on Uniform Multiprocessors", IEEE Transactions on Computers, vol. 52, pp. 966--970, July 2003

Digital Library

[8]

H. Cho, B. Ravindran, and E. D. Jensen, \An Optimal Real-Time Scheduling Algorithm for Multiprocessors", Proc. of the IEEE Real-Time Systems Symposium, pp. 101--110, Dec. 2006.

Digital Library

[9]

M. Cirinei and T. P. Baker, \EDZL Scheduling Analysis", Proc. of the Euromicro Conference on Real-Time Systems, pp. 9--18, July 2007.

Digital Library

[10]

M. Detouzos, \Control Robotics: The Procedural Control of Physical Processors", Proc. IFIP Congress, pp. 807--813, 1974.

[11]

S. K. Dhall and C. L. Liu, \On a Real-Time Scheduling Problem", Operations Research, vol. 26, pp. 127--140, 1978.

Digital Library

[12]

J. R. Ellis, \A new approach to ensuring deterministic processing in a integrated avionics software systems" Proc. IEEE NAECON, pp. 756--764, 1985.

[13]

D. Johnson, \Fast Algorithms for Bin Packing", Jounal of Computer and Systems Science, vol. 8, no. 3, pp. 272--314, 1974.

Digital Library

[14]

S. Kato and N. Yamasaki, \Portioned Static-Priority Scheduling on Multiprocessors" Proc. of the IEEE International Symposium on Parallel and Distributed Processing, pp. 1--12, April 2008.

[15]

S. Kato and N. Yamasaki, \Real-Time Scheduling with Task Splitting on Multiprocessors", Proc. of the IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, pp. 441--450, Aug. 2007.

Digital Library

[16]

C. L. Liu and J. W. Layland, \Scheduling algorithms for multi-programming for a hard real-time environment" JACM, vol. 20, no. 1, pp. 46--61, Jan. 1973.

Digital Library

[17]

Jane W. S. Liu, Real-Time Systems, Prentice-Hall, 2000.

[18]

A. K. Mok, Fundamental Design Problems of Distributed Systems for Hard-Real-Time Environment, PhD thesis, Massachusetts Inst. of Technology, 1983, Technical Report No. MIT/LCS/TR-297.

Digital Library

Cited By

Mahmood BAhmad N(2023)An optimal semi-partitioned algorithm for scheduling real-time applications on uniform multicore processorsSustainable Computing: Informatics and Systems10.1016/j.suscom.2023.10085438(100854)Online publication date: Apr-2023
https://doi.org/10.1016/j.suscom.2023.100854
Mahmood BAhmad NKhan MAkhunzada A(2021)Dynamic Priority Real-Time Scheduling on Power Asymmetric Multicore ProcessorsSymmetry10.3390/sym1308148813:8(1488)Online publication date: 13-Aug-2021
https://doi.org/10.3390/sym13081488
Kim JLee SLee C(2021)A Scheduling Algorithm with RTiK+ for MIL-STD-1553B Based on Windows for Real-Time Operation SystemAdvances in Science, Technology and Engineering Systems Journal10.25046/aj0604436:4(385-394)Online publication date: Aug-2021
https://doi.org/10.25046/aj060443
Show More Cited By

Index Terms

Recommendations

The Non-preemptive Scheduling of Periodic Tasks upon Multiprocessors

The non-preemptive scheduling of periodic task systems upon processing platforms comprised of several identical processors is considered. The exact problem has previously been proven intractable even upon single processors; sufficient conditions are ...
Optimal Utilization Bounds for the Fixed-Priority Scheduling of Periodic Task Systems on Identical Multiprocessors

Abstract--In fixed-priority scheduling, the priority of a job, once assigned, may not change. A new fixed-priority algorthm for scheduling systems of periodic tasks upon identical multiprocessors is proposed. This algorithm has an achievable utilization ...
Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors

The scheduling of systems of periodic tasks upon multiprocessor platforms is considered. Utilization-based conditions are derived for determining whether a periodic task system meets all deadlines when scheduled using the earliest deadline first ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICHIT '09: Proceedings of the 2009 International Conference on Hybrid Information Technology

August 2009

687 pages

ISBN:9781605586625

DOI:10.1145/1644993

General Chairs:
Geuk Lee
Hannam University, Korea
,
Daniel Howard
QinetiQ, UK
,
Jeong Jin Kang
Dong Seoul University, Korea
,
Program Chairs:
Dominik Slezak
Infobright, Canada
,
Tae Nam Ahn
SERC, Korea
,
Chung-Huang Yang
National Kaohsiung Normal University, Taiwan

Copyright © 2009 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: 27 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

ICHIT '09

ICHIT '09: International Conference on Convergence and Hybrid Information Technology

August 27 - 29, 2009

Daejeon, Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
10
Total Downloads

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

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mahmood BAhmad N(2023)An optimal semi-partitioned algorithm for scheduling real-time applications on uniform multicore processorsSustainable Computing: Informatics and Systems10.1016/j.suscom.2023.10085438(100854)Online publication date: Apr-2023
https://doi.org/10.1016/j.suscom.2023.100854
Mahmood BAhmad NKhan MAkhunzada A(2021)Dynamic Priority Real-Time Scheduling on Power Asymmetric Multicore ProcessorsSymmetry10.3390/sym1308148813:8(1488)Online publication date: 13-Aug-2021
https://doi.org/10.3390/sym13081488
Kim JLee SLee C(2021)A Scheduling Algorithm with RTiK+ for MIL-STD-1553B Based on Windows for Real-Time Operation SystemAdvances in Science, Technology and Engineering Systems Journal10.25046/aj0604436:4(385-394)Online publication date: Aug-2021
https://doi.org/10.25046/aj060443
Brown JAfrin NKhan J(2016)Blocking analysis of persistent resource allocations for M2M applications in wireless systemsTransactions on Emerging Telecommunications Technologies10.1002/ett.309127:11(1513-1529)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1002/ett.3091
Fan MQuan G(2014)Harmonic-Aware Multi-Core Scheduling for Fixed-Priority Real-Time SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2013.7125:6(1476-1488)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1109/TPDS.2013.71
Müller DWerner M(2011)Genealogy of hard real-time preemptive scheduling algorithms for identical multiprocessorsOpen Computer Science10.2478/s13537-011-0023-z1:3Online publication date: 1-Jan-2011
https://doi.org/10.2478/s13537-011-0023-z

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.

Figures

Tables

Media

View Table of Conten