More Web Proxy on the site http://driver.im/

research-article

Soft Real-Time Semi-Partitioned Scheduling with Restricted Migrations on Uniform Heterogeneous Multiprocessors

Authors:

James H. AndersonAuthors Info & Claims

RTNS '14: Proceedings of the 22nd International Conference on Real-Time Networks and Systems

Pages 215 - 224

https://doi.org/10.1145/2659787.2659808

Published: 08 October 2014 Publication History

Abstract

We present EDF-sh, which is the first soft real-time scheduling algorithm with restricted migrations for heterogeneous multiprocessors. EDF-sh does not restrict total utilization as long as the system is not overutilized. However, it requires a per-task utilization constraint, which is not too constraining but nonetheless renders EDF-sh non-optimal. We evaluate the effectiveness of EDF-sh by means of schedulability experiments. In these experiments, more than 87% of the feasible task sets that were considered were soft-real-time-schedulable under EDF-sh. Additionally, tardiness bounds for these task sets under EDF-sh were found to be quite low in almost all cases.

References

[1]

big.LITTLE Processing. http://www.arm.com/products/processors/technologies/biglittleprocessing.php.

[2]

Samsung's Exynos 5422 & The Ideal big.LITTLE: Exynos 5 Hexa (5260). http://www.anandtech.com/show/7811/samsungs-exynos-5422-the-ideal-biglittle-exynos-5-hexa-5260.

[3]

J. Anderson, V. Bud, and U. Devi. An EDF-based scheduling algorithm for multiprocessor soft real-time systems. In 17th ECRTS, 2005.

Digital Library

[4]

J. Anderson, J. Erickson, U. Devi, and B. Casses. Optimal semi-partitioned scheduling in soft real-time systems. In 20th RTCSA, 2014.

[5]

B. Andersson, K. Bletsas, and S. Baruah. Scheduling arbitrary-deadline sporadic task systems on multiprocessors. In 29th RTSS, 2008.

Digital Library

[6]

B. Andersson and E. Tovar. Multiprocessor scheduling with few preemptions. In 12th RTCSA, 2006.

Digital Library

[7]

S. Baruah, S. Funk, and J. Goossens. Robustness results concerning EDF scheduling upon uniform multiprocessors. IEEE Trans. on Computers, 52(9):1185--1195, 2003.

Digital Library

[8]

S. Baruah and J. Goossens. Rate-monotonic scheduling on uniform multiprocessors. IEEE Trans. on Computers, 52(7):966--970, 2003.

Digital Library

[9]

M. Bhatti, C. Belleudy, and M. Auguin. A semi-partitioned realtime scheduling approach for periodic task systems on multicore platforms. In 27th SAC, 2012.

Digital Library

[10]

K. Bletsas and B. Andersson. Notional processors: an approach for multiprocessor scheduling. In 15th RTAS, 2009.

Digital Library

[11]

K. Bletsas and B. Andersson. Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound. Real-Time Sys., 47(4):319--355, 2011.

Digital Library

[12]

B. Brandenburg. Scheduling and Locking in Multiprocessor Real-Time Operating Systems. PhD thesis, The University of North Carolina, Chapel Hill, NC, 2011.

Digital Library

[13]

U. Devi and J. Anderson. Tardiness bounds under global EDF sched-uling on a multiprocessor. Real-Time Sys., 38(2):133--189, 2008.

Digital Library

[14]

F. Dorin, P. Yomsi, J. Goossens, and P. Richard. Semi-partitioned hard real-time scheduling with restricted migrations upon identical multiprocessor platforms. Cornell University Library Archives, arXiv:1006.2637 {cs.OS}, 2010.

[15]

J. Erickson, U. Devi, and S. Baruah. Improved tardiness bounds for global EDF. In 22nd ECRTS, 2010.

Digital Library

[16]

J. Erickson and J. Anderson. Fair lateness scheduling: reducing maximum lateness in G-EDF-like Scheduling. In 24th ECRTS, 2012.

Digital Library

[17]

M. Fan and G. Quan. Harmonic semi-partitioned scheduling for fixed-priority real-time tasks on multi-core platform. In DATE, 2012.

Digital Library

[18]

S. Funk, J. Goossens, and S. Baruah. On-line scheduling on uniform multiprocessors. In 22nd RTSS 2001.

Digital Library

[19]

S. Funk. EDF Scheduling on Heterogeneous Multiprocessors. PhD thesis, The University of North Carolina, NC, 2004.

Digital Library

[20]

J. Goossens, P. Richard, M. Lindström, I. Lupu, and F. Ridouard. Job partitioning strategies for multiprocessor scheduling of real-time periodic tasks with restricted migrations. In 20th RTNS, 2012.

Digital Library

[21]

N. Guan, M. Stigge, W. Yi, and G. Yu. Fixed-priority multiprocessor scheduling with Liu and Layland's utilization bound. In 16th RTAS, 2010.

Digital Library

[22]

E. Horvath, S. Lam, and R. Sethi. A level algorithm for preemptive scheduling. Journal of the ACM, 24(1):32--43, 1977.

Digital Library

[23]

S. Kato and N. Yamasaki. Real-time scheduling with task splitting on multiprocessors. In 13th RTCSA, 2007.

Digital Library

[24]

S. Kato and N. Yamasaki. Portioned EDF-based scheduling on multiprocessors. In 8th EMSOFT, 2008.

Digital Library

[25]

S. Kato and N. Yamasaki. Semi-partitioned fixed-priority scheduling on multiprocessors. In 15th RTAS, 2009.

Digital Library

[26]

H. Leontyev and J. Anderson. Tardiness bounds for EDF scheduling on multi-speed multicore platforms. In 13th RTCSA, 2007.

Digital Library

[27]

H. Leontyev and J. Anderson. Generalized tardiness bounds for glo-bal multiprocessor scheduling. Real-Time Sys., 44(1):26--71, 2010.

Digital Library

[28]

A. Mills and J. Anderson. A multiprocessor server-based scheduler for soft real-time tasks with stochastic execution demand. In 17th RTCSA, 2011.

Digital Library

[29]

M. Pinedo. Scheduling, Theory, Algorithms, and Systems. Prentice Hall, 1995

[30]

M. Shekhar, A. Sarkar, H. Ramaprasad, and F. Mueller. Semipartitioned hard real-time scheduling under locked cache migration in multicore systems. In 24th ECRTS, 2012.

Digital Library

[31]

P. Sousa, P. Souto, E. Tovar, and K. Bletsas. The carousel-EDF scheduling algorithm for multiprocessor systems. In 19th RTCSA, 2013.

Cited By

He ZSun YFang HHuang YYang YZhang ZLiu D(2021)Energy-Efficient System Design of Asymmetric Multiprocessor for Real-Time Streaming Applications2021 International Conference on Intelligent Technology and Embedded Systems (ICITES)10.1109/ICITES53477.2021.9637078(44-51)Online publication date: 31-Oct-2021
https://doi.org/10.1109/ICITES53477.2021.9637078
Tong GLiu C(2016)Supporting Soft Real-Time Sporadic Task Systems on Uniform Heterogeneous Multiprocessors with No Utilization LossIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2015.250327827:9(2740-2752)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1109/TPDS.2015.2503278
Yang KAnderson J(2015)On the Soft Real-Time Optimality of Global EDF on MultiprocessorsProceedings of the 2015 IEEE 21st International Conference on Embedded and Real-Time Computing Systems and Applications10.1109/RTCSA.2015.14(1-10)Online publication date: 19-Aug-2015
https://dl.acm.org/doi/10.1109/RTCSA.2015.14

Index Terms

Soft Real-Time Semi-Partitioned Scheduling with Restricted Migrations on Uniform Heterogeneous Multiprocessors
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
  2. Real-time systems
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Scheduling
    2. Software system structures
      1. Embedded software
      2. Real-time systems software

Recommendations

Multiprocessor fixed-priority scheduling with restricted interprocessor migrations
Real-Time Systems (Euromicro RTS-03)

The priority-driven scheduling of periodic and sporadic task systems upon identical multiprocessor platforms is considered, under the restrictions that (i) each job may be assigned exactly one priority throughout its lifetime, and (ii) each job may ...
Competitive Analysis of Static-Priority Partitioned Scheduling on Uniform Multiprocessors
RTCSA '07: Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications

Consider the problem of scheduling a set of sporadically arriving tasks on a uniform multiprocessor with the goal of meeting deadlines. A processor p has the speed Sp. Tasks can be preempted but they cannot migrate between processors. On each processor, ...
Optimal Semi-Partitioned Scheduling in Soft Real-Time Systems

Semi-partitioned real-time scheduling algorithms extend partitioned ones by allowing a (usually small) subset of tasks to migrate. The first such algorithm to be proposed was directed at soft real-time (SRT) sporadic task systems where bounded deadline ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

RTNS '14: Proceedings of the 22nd International Conference on Real-Time Networks and Systems

October 2014

335 pages

ISBN:9781450327275

DOI:10.1145/2659787

General Chairs:
Mathieu Jan
CEA LIST, Gif-sur-Yvette, France
,
Belgacem Ben Hedia
CEA LIST, Gif-sur-Yvette, France
,
Program Chairs:
Joël Goossens
Université Libre de Bruxelles, Belgium
,
Claire Maiza
Grenoble INP / Verimag, France

Copyright © 2014 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 the author(s) 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].

In-Cooperation

CEA: Commissariat à l'énergie atomique et aux énergies alternatives
GDR ASR: GDR Architecture, Systèmes et Réseaux

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 October 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

RTNS '14

RTNS '14: 22nd International Conference on Real-Time Networks and Systems

October 8 - 10, 2014

Versaille, France

Acceptance Rates

Overall Acceptance Rate 119 of 255 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
114
Total Downloads

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

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

He ZSun YFang HHuang YYang YZhang ZLiu D(2021)Energy-Efficient System Design of Asymmetric Multiprocessor for Real-Time Streaming Applications2021 International Conference on Intelligent Technology and Embedded Systems (ICITES)10.1109/ICITES53477.2021.9637078(44-51)Online publication date: 31-Oct-2021
https://doi.org/10.1109/ICITES53477.2021.9637078
Tong GLiu C(2016)Supporting Soft Real-Time Sporadic Task Systems on Uniform Heterogeneous Multiprocessors with No Utilization LossIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2015.250327827:9(2740-2752)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1109/TPDS.2015.2503278
Yang KAnderson J(2015)On the Soft Real-Time Optimality of Global EDF on MultiprocessorsProceedings of the 2015 IEEE 21st International Conference on Embedded and Real-Time Computing Systems and Applications10.1109/RTCSA.2015.14(1-10)Online publication date: 19-Aug-2015
https://dl.acm.org/doi/10.1109/RTCSA.2015.14

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