research-article

Harmonic semi-partitioned scheduling for fixed-priority real-time tasks on multi-core platform

Authors:

Gang QuanAuthors Info & Claims

DATE '12: Proceedings of the Conference on Design, Automation and Test in Europe

Pages 503 - 508

Published: 12 March 2012 Publication History

Abstract

This paper presents a new semi-partitioned approach to schedule sporadic tasks on multi-core platform based on the Rate Monotonic Scheduling (RMS) policy. Our approach exploits the well known fact that harmonic tasks have better schedulablility than non-harmonic ones on a single processor. The challenge for our approach, however, is how to take advantage of this fact to assign and split appropriate tasks on different processors in the semi-partitioned approach. We formally prove that our scheduling approach can successfully schedule any task sets with system utilizations bounded by the Liu&Layland's bound. Our extensive experiment results demonstrate that the proposed algorithm can significantly improve the scheduling performance compared with the previous work.

References

[1]

S. Chaudhry, R. Cypher, M. Ekman, M. Karlsson, A. Landin, S. Yip, H. Zeffer, and M. Tremblay, "Rock: A high-performance sparc cmt processor," Micro, IEEE, vol. 29, no. 2, pp. 6--16, March-April 2009.

Digital Library

[2]

W. Wolf, "Multiprocessor system-on-chip technology," Signal Processing Magazine, IEEE, vol. 26, no. 6, pp. 50--54, November 2009.

[3]

J. Liu, Real-Time Systems. NJ: Prentice Hall, 2000.

[4]

B. Andersson, S. Baruah, and J. Jonsson, "Static-priority scheduling on multiprocessors," in Real-Time Systems Symposium, 2001. (RTSS 2001). Proceedings. 22nd IEEE, Dec 2001, pp. 193--202.

Digital Library

[5]

B. Andersson, "Global static-priority preemptive multiprocessor scheduling with utilization bound 38%," in Principles of Distributed Systems, ser. Lecture Notes in Computer Science, T. Baker, A. Bui, and S. Tixeuil, Eds. Springer Berlin/Heidelberg, 2008, vol. 5401, pp. 73--88, 10.1007/978-3-540-92221-6_7. {Online}. Available: http://dx.doi.org/10.1007/978-3-540-92221-6_7

Digital Library

[6]

S. Kato and N. Yamasaki, "Semi-partitioned fixed-priority scheduling on multiprocessors," in Real-Time and Embedded Technology and Applications Symposium, 2009. RTAS 2009. 15th IEEE, April 2009, pp. 23--32.

Digital Library

[7]

K. Lakshmanan, R. Rajkumar, and J. Lehoczky, "Partitioned fixed-priority preemptive scheduling for multi-core processors," in Real-Time Systems, 2009. ECRTS '09. 21st Euromicro Conference on, July 2009, pp. 239--248.

Digital Library

[8]

J. Carpenter, S. Funk, P. Holman, A. Srinivasan, J. Anderson, and S. Baruah, "A categorization of real-time multiprocessor scheduling problems and algorithms," in Handbook on Scheduling Algorithms, Methods, and Models. Chapman Hall/CRC, Boca, 2004.

[9]

J. Anderson, V. Bud, and U. Devi, "An edf-based scheduling algorithm for multiprocessor soft real-time systems," in Real-Time Systems, 2005. (ECRTS 2005). Proceedings. 17th Euromicro Conference on, July 2005, pp. 199--208.

Digital Library

[10]

S. Kato and N. Yamasaki, "Real-time scheduling with task splitting on multiprocessors," in Embedded and Real-Time Computing Systems and Applications, 2007. RTCSA 2007. 13th IEEE International Conference on, Aug. 2007, pp. 441--450.

Digital Library

[11]

B. Andersson, K. Bletsas, and S. Baruah, "Scheduling arbitrary-deadline sporadic task systems on multiprocessors," in Real-Time Systems Symposium, 2008, Dec 2008, pp. 385--394.

Digital Library

[12]

N. Guan, M. Stigge, W. Yi, and G. Yu, "Fixed-priority multiprocessor scheduling with liu and layland's utilization bound," in Real-Time and Embedded Technology and Applications Symposium (RTAS), 2010 16th IEEE, April 2010, pp. 165--174.

Digital Library

[13]

A. Bastoni, B. Brandenburg, and J. Anderson, "Is semi-partitioned scheduling practical?" in Real-Time Systems (ECRTS), 2011 23rd Euromicro Conference on, july 2011, pp. 125--135.

Digital Library

[14]

B. Andersson and J. Jonsson, "The utilization bounds of partitioned and pfair static-priority scheduling on multiprocessors are 50%," in Real-Time Systems, 2003. Proceedings. 15th Euromicro Conference on, July 2003, pp. 33--40.

[15]

N. Guan, M. Stigge, W. Yi, and G. Yu, "Fixed-priority multiprocessor scheduling: Beyond liu and layland's utilization bound," in Real-Time Systems Symposium, 2010, Work In Progress, Dec 2010.

[16]

C. L. Liu and J. W. Layland, "Scheduling algorithms for multiprogramming in a hard-real-time environment," J. ACM, vol. 20, pp. 46--61, January 1973. {Online}. Available: http://doi.acm.org/10.1145/321738.321743

Digital Library

[17]

C.-C. Han and H.-Y. Tyan, "A better polynomial-time schedulability test for real-time fixed-priority scheduling algorithms," in Real-Time Systems Symposium, 1997. Proceedings., The 18th IEEE, Dec 1997, pp. 36--45.

Digital Library

[18]

T.-W. Kuo and A. Mok, "Load adjustment in adaptive real-time systems," in Real-Time Systems Symposium, 1991. Proceedings., Twelfth, Dec 1991, pp. 160--170.

[19]

C.-C. Han, K.-J. Lin, and C.-J. Hou, "Distance-constrained scheduling and its applications to real-time systems," Computers, IEEE Transactions on, vol. 45, no. 7, pp. 814--826, Jul 1996.

Digital Library

[20]

J. Lehoczky, L. Sha, and Y. Ding, "The rate monotonic scheduling algorithm: exact characterization and average case behavior," in Real Time Systems Symposium, 1989., Proceedings., Dec 1989, pp. 166--171.

Cited By

Wang TNiu LRen SQuan GNebel WAtienza D(2015)Multi-core fixed-priority scheduling of real-time tasks with statistical deadline guaranteeProceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition10.5555/2755753.2757123(1335-1340)Online publication date: 9-Mar-2015
https://dl.acm.org/doi/10.5555/2755753.2757123
Yang KAnderson JJan MBen Hedia BGoossens JMaiza C(2014)Soft Real-Time Semi-Partitioned Scheduling with Restricted Migrations on Uniform Heterogeneous MultiprocessorsProceedings of the 22nd International Conference on Real-Time Networks and Systems10.1145/2659787.2659808(215-224)Online publication date: 8-Oct-2014
https://dl.acm.org/doi/10.1145/2659787.2659808

Index Terms

Harmonic semi-partitioned scheduling for fixed-priority real-time tasks on multi-core platform
1. Computer systems organization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

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, ...
Analysis on quantum-based fixed priority scheduling of real-time tasks
ICUIMC '09: Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication

Fixed priority schedulers are widely used for real-time systems, and there were efforts to improve the schedulability. Preemption threshold scheduling is one of such efforts with a dual priority scheme. It increases the schedulability by introducing ...
Harmonic-Aware Multi-Core Scheduling for Fixed-Priority Real-Time Systems

This paper presents a new semipartitioned approach to schedule sporadic tasks on multicore platforms based on the Rate Monotonic Scheduling policy. To improve the schedulability, our approach exploits the fact that the utilization bound of a task set ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DATE '12: Proceedings of the Conference on Design, Automation and Test in Europe

March 2012

1690 pages

ISBN:9783981080186

General Chairs:
Wolfgang Rosenstiel
University of Tuebingen and edacentrum, DE
,
Enrico Macii
Politecnico di Torino, IT

Sponsors

EDAA: European Design Automation Association
ECSI
EDAC: Electronic Design Automation Consortium
SIGDA: ACM Special Interest Group on Design Automation
IEEE CEDA
The Russian Academy of Sciences: The Russian Academy of Sciences

Publisher

EDA Consortium

San Jose, CA, United States

Publication History

Published: 12 March 2012

Check for updates

Qualifiers

Research-article

Conference

DATE '12

Sponsor:

EDAA
EDAC
SIGDA
The Russian Academy of Sciences

DATE '12: Design, Automation and Test in Europe

March 12 - 16, 2012

Dresden, Germany

Acceptance Rates

Overall Acceptance Rate 518 of 1,794 submissions, 29%

Upcoming Conference

DATE '25

Sponsor:
sigda

Design, Automation and Test in Europe

March 31 - April 2, 2025

Lyon , France

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
77
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang TNiu LRen SQuan GNebel WAtienza D(2015)Multi-core fixed-priority scheduling of real-time tasks with statistical deadline guaranteeProceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition10.5555/2755753.2757123(1335-1340)Online publication date: 9-Mar-2015
https://dl.acm.org/doi/10.5555/2755753.2757123
Yang KAnderson JJan MBen Hedia BGoossens JMaiza C(2014)Soft Real-Time Semi-Partitioned Scheduling with Restricted Migrations on Uniform Heterogeneous MultiprocessorsProceedings of the 22nd International Conference on Real-Time Networks and Systems10.1145/2659787.2659808(215-224)Online publication date: 8-Oct-2014
https://dl.acm.org/doi/10.1145/2659787.2659808

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