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

research-article

Release enforcement in resource-oriented partitioned scheduling for multiprocessor systems

Authors:

Georg von der Brüggen,

Wen-Hung Huang,

Maolin YangAuthors Info & Claims

RTNS '17: Proceedings of the 25th International Conference on Real-Time Networks and Systems

Pages 287 - 296

https://doi.org/10.1145/3139258.3139287

Published: 04 October 2017 Publication History

Abstract

When partitioned scheduling is used in real-time multiprocessor systems, access to shared resources can jeopardize the schedulability if the task partition is not done carefully. To tackle this problem we change our view angle from focusing on the computing tasks to focusing on the shared resources by applying resource-oriented partitioned scheduling. We use a release enforcement technique to shape the interference from the higher-priority jobs to be sporadic, analyze the schedulability, and provide strategies for partitioning both the critical and the non-critical sections of tasks onto processors individually. Our approaches are shown to be effective, both in the evaluations and from a theoretical point of view by providing a speedup factor of 6, improving previously known results.

References

[1]

B. Andersson and A. Easwaran. Provably good multiprocessor scheduling with resource sharing. Real-Time Systems, 46(2):153--159, 2010.

Digital Library

[2]

B. Andersson and G. Raravi. Real-time scheduling with resource sharing on heterogeneous multiprocessors. Real-Time Systems, 50(2):270--314, 2014.

Digital Library

[3]

T. P. Baker. Stack-based scheduling of realtime processes. Real-Time Systems, 3(1):67--99, 1991.

Digital Library

[4]

S. Baruah, D. Chen, S. Gorinsky, and A. Mok. Generalized multiframe tasks. Real-Time Systems, 17:5--22, 1999.

Digital Library

[5]

R. Bettati and J. W. Liu. End-to-end scheduling to meet deadlines in distributed systems. In ICDCS, pages 452--459, 1992.

[6]

A. Block, H. Leontyev, B. Brandenburg, and J. Anderson. A flexible real-time locking protocol for multiprocessors. In RTCSA, pages 47--56, 2007.

Digital Library

[7]

B. Brandenburg. Improved analysis and evaluation of real-time semaphore protocols for P-FP scheduling. In RTAS, 2013.

Digital Library

[8]

B. B. Brandenburg. Blocking optimality in distributed real-time locking protocols. LITES, 1(2):01:1--01:22, 2014.

[9]

B. B. Brandenburg. The FMLP+: an asymptotically optimal real-time locking protocol for suspension-aware analysis. In Euromicro Conference on Real-Time Systems (ECRTS), pages 61--71, 2014.

[10]

B. B. Brandenburg and J. H. Anderson. Optimality results for multiprocessor real-time locking. In Real-Time Systems Symposium (RTSS), pages 49--60, 2010.

Digital Library

[11]

B. B. Brandenburg and J. H. Anderson. The OMLP family of optimal multiprocessor real-time locking protocols. Design Autom. for Emb. Sys., 17(2):277--342, 2013.

Digital Library

[12]

A. Burns and A. J. Wellings. A schedulability compatible multiprocessor resource sharing protocol - MrsP. In Euromicro Conference on Real-Time Systems (ECRTS), pages 282--291, 2013.

Digital Library

[13]

J.-J. Chen and B. B. Brandenburg. A note on the period enforcer algorithm for self-suspending tasks. LITES, 4(1):01:1--01:22, 2017.

[14]

J.-J. Chen, G. Nelissen, W.-H. Huang, M. Yang, B. Brandenburg, K. Bletsas, C. Liu, P. Richard, F. Ridouard, Neil, Audsley, R. Rajkumar, D. de Niz, and G. von der Brüggen. Many suspensions, many problems: A review of self-suspending tasks in real-time systems. Technical Report 854, 2nd version, Faculty of Informatik, TU Dortmund, 2017. http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2017-chen-techreport-854-v2.pdf.

[15]

J.-J. Chen, G. von der Brüggen, W.-H. Huang, and R. I. Davis. On the pitfalls of resource augmentation factors and utilization bounds in real-time scheduling. In Euromicro Conference on Real-Time Systems, ECRTS, pages 9:1--9:25, 2017.

[16]

J.-J. Chen, G. von der Brüggen, W.-H. Huang, and C. Liu. State of the art for scheduling and analyzing self-suspending sporadic real-time tasks. In 23rd IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA, 2017.

[17]

R. Davis and A. Burns. Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. In Real-Time Systems, Volume 47, Issue 1, pages 1--40, 2010.

Digital Library

[18]

R. I. Davis and A. Burns. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv., 43(4):35, 2011.

Digital Library

[19]

A. Easwaran and B. Andersson. Resource sharing in global fixed-priority preemptive multiprocessor scheduling. In Real-Time Systems Symposium (RTSS), pages 377--386, 2009.

Digital Library

[20]

P. Emberson, R. Stafford, and R. I. Davis. Techniques for the synthesis of multiprocessor tasksets. In International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS 2010), pages 6--11, 2010.

[21]

P. Gai, G. Lipari, and M. D. Natale. Minimizing memory utilization of real-time task sets in single and multi-processor systems-on-a-chip. In Real-Time Systems Symposium (RTSS), pages 73--83, 2001.

Digital Library

[22]

W.-H. Huang and J.-J. Chen. Self-suspension real-time tasks under fixed-relative-deadline fixed-priority scheduling. In Design, Automation, and Test in Europe (DATE), pages 1078--1083, 2016.

Digital Library

[23]

W.-H. Huang, M. Yang, and J.-J. Chen. Resource-oriented partitioned scheduling in multiprocessor systems: How to partition and how to share? In Real-Time Systems Symposium, RTSS, pages 111--122, 2016.

[24]

K. Lakshmanan, D. de Niz, and R. Rajkumar. Coordinated task scheduling, allocation and synchronization on multiprocessors. In Real-Time Systems Symposium, (RTSS), pages 469--478, 2009.

Digital Library

[25]

F. Nemati, T. Nolte, and M. Behnam. Partitioning real-time systems on multiprocessors with shared resources. In Principles of Distributed Systems - International Conference, OPODIS, pages 253--269, 2010.

Digital Library

[26]

J. C. Palencia and M. G. Harbour. Schedulability analysis for tasks with static and dynamic offsets. In Real-Time Systems Symposium (RTSS), pages 26--37, 1998.

Digital Library

[27]

R. Rajkumar. Real-time synchronization protocols for shared memory multiprocessors. In 10th International Conference on Distributed Computing Systems (ICDCS), pages 116--123, 1990.

[28]

R. Rajkumar. Dealing with Suspending Periodic Tasks. Technical report, IBM T.J. Watson Research Center, 1991. http://www.cs.cmu.edu/afs/cs/project/rtmach/public/papers/period-enforcer.ps.

[29]

R. Rajkumar, L. Sha, and J. P. Lehoczky. Real-time synchronization protocols for multiprocessors. In Real-Time Systems Symposium (RTSS), pages 259--269, 1988.

[30]

L. Sha, R. Rajkumar, and J. P. Lehoczky. Priority inheritance protocols: An approach to real-time synchronization. IEEE Trans. Computers, 39(9):1175--1185, 1990.

Digital Library

[31]

J. Sun and J. W.-S. Liu. Synchronization protocols in distributed real-time systems. In Proceedings of the 16th International Conference on Distributed Computing Systems, pages 38--45, 1996.

Digital Library

[32]

H. Takada and K. Sakamura. Schedulability of generalized multiframe task sets under static priority assignment. In Real-Time Computing Systems and Applications (RTCSA), pages 80--86, 1997.

Digital Library

[33]

G. von der Brüggen, J.-J. Chen, and W.-H. Huang. Schedulability and optimization analysis for non-preemptive static priority scheduling based on task utilization and blocking factors. In 27th Euromicro Conference on Real-Time Systems, ECRTS, pages 90--101, 2015.

Digital Library

[34]

G. von der Brüggen, W.-H. Huang, and J.-J. Chen. Hybrid self-suspension models in real-time embedded systems. In 23rd IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA, 2017.

[35]

G. von der Brüggen, W.-H. Huang, J.-J. Chen, and C. Liu. Uniprocessor scheduling strategies for self-suspending task systems. In International Conference on Real-Time Networks and Systems, RTNS '16, pages 119--128, 2016.

Digital Library

[36]

A. Wieder and B. Brandenburg. On spin locks in AUTOSAR: blocking analysis of FIFO, unordered, and priority-ordered spin locks. In RTSS, 2013.

Digital Library

[37]

A. Wieder and B. B. Brandenburg. Efficient partitioning of sporadic real-time tasks with shared resources and spin locks. In International Symposium on Industrial Embedded Systems, (SIES), pages 49--58, 2013.

[38]

M. Yang, J.-J. Chen, and W.-H. Huang. A misconception in blocking time analyses under multiprocessor synchronization protocols. Real-Time Systems, 53(2):187--195, 2017.

Digital Library

[39]

M. Yang, A. Wieder, and B. B. Brandenburg. Global real-time semaphore protocols: A survey, unified analysis, and comparison. In Real-Time Systems Symposium (RTSS), pages 1--12, 2015.

Digital Library

Cited By

Chen JShi Jvon der Bruggen GUeter N(2022)Scheduling of Real-Time Tasks With Multiple Critical Sections in Multiprocessor SystemsIEEE Transactions on Computers10.1109/TC.2020.304374271:1(146-160)Online publication date: 1-Jan-2022
https://doi.org/10.1109/TC.2020.3043742
der Bruggen GBurns AChen JDavis RReineke J(2022)On the Trade-offs between Generalization and Specialization in Real-Time Systems2022 IEEE 28th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA55878.2022.00022(148-159)Online publication date: Aug-2022
https://doi.org/10.1109/RTCSA55878.2022.00022
Brandenburg B(2022)Multiprocessor Real-Time Locking ProtocolsHandbook of Real-Time Computing10.1007/978-981-287-251-7_10(347-446)Online publication date: 9-Aug-2022
https://doi.org/10.1007/978-981-287-251-7_10
Show More Cited By

Release enforcement in resource-oriented partitioned scheduling for multiprocessor systems
1. Computer systems organization
  1. Embedded and cyber-physical systems
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures

Recommendations

Global and Partitioned Multiprocessor Fixed Priority Scheduling with Deferred Preemption
Special Issue on Embedded Platforms for Crypto and Regular Papers

This article introduces schedulability analysis for Global Fixed Priority Scheduling with Deferred Preemption (gFPDS) for homogeneous multiprocessor systems. gFPDS is a superset of Global Fixed Priority Preemptive Scheduling (gFPPS) and Global Fixed ...
The Partitioned Multiprocessor Scheduling of Deadline-Constrained Sporadic Task Systems

A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks, each constrained to have its relative-deadline parameter be no larger than its period parameter, among the processors of an identical multiprocessor platform. ...
Multiprocessor Scheduling of Unit-Time Jobs with Arbitrary Release Times and Deadlines

We present a polynomial time algorithm for constructing an optimal schedule, if a feasible schedule exists, for tthe following multimachine scheduling problem. There are n unit-time jobs, with arbitrary release times and deadlines, and m identical ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

RTNS '17: Proceedings of the 25th International Conference on Real-Time Networks and Systems

October 2017

318 pages

ISBN:9781450352864

DOI:10.1145/3139258

Program Chairs:
Enrico Bini
University of Turin, Italy
,
Claire Pagetti
ONERA/ENSEEIHT/TUHH, Toulouse, France

Copyright © 2017 Owner/Author.

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 October 2017

Check for updates

Qualifiers

Research-article

Funding Sources

DFG

Conference

RTNS '17

RTNS '17: 25th International Conference on Real-Time Networks and Systems

October 4 - 6, 2017

Grenoble, France

Acceptance Rates

Overall Acceptance Rate 119 of 255 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
77
Total Downloads

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

Reflects downloads up to 11 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen JShi Jvon der Bruggen GUeter N(2022)Scheduling of Real-Time Tasks With Multiple Critical Sections in Multiprocessor SystemsIEEE Transactions on Computers10.1109/TC.2020.304374271:1(146-160)Online publication date: 1-Jan-2022
https://doi.org/10.1109/TC.2020.3043742
der Bruggen GBurns AChen JDavis RReineke J(2022)On the Trade-offs between Generalization and Specialization in Real-Time Systems2022 IEEE 28th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA55878.2022.00022(148-159)Online publication date: Aug-2022
https://doi.org/10.1109/RTCSA55878.2022.00022
Brandenburg B(2022)Multiprocessor Real-Time Locking ProtocolsHandbook of Real-Time Computing10.1007/978-981-287-251-7_10(347-446)Online publication date: 9-Aug-2022
https://doi.org/10.1007/978-981-287-251-7_10
Shi JUeter NBruggen GChen J(2021)Graph-Based Optimizations for Multiprocessor Nested Resource Sharing2021 IEEE 27th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA52859.2021.00023(129-138)Online publication date: Aug-2021
https://doi.org/10.1109/RTCSA52859.2021.00023
von der Brüggen G(2021)Realistic Scheduling Models and Analyses for Advanced Real-Time Embedded SystemsEchtzeit 202010.1007/978-3-658-32818-4_2(11-20)Online publication date: 30-Jan-2021
https://doi.org/10.1007/978-3-658-32818-4_2
Baek HShin KLee J(2020)Response-Time Analysis for Multi-Mode Tasks in Real-Time Multiprocessor SystemsIEEE Access10.1109/ACCESS.2020.29928688(86111-86129)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2992868
Shi JUeter Nvon der Bruggen GChen J(2019)Partitioned Scheduling for Dependency Graphs in Multiprocessor Real-Time Systems2019 IEEE 25th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA.2019.8864591(1-12)Online publication date: Aug-2019
https://doi.org/10.1109/RTCSA.2019.8864591
Shi JUeter Nvon der Bruggen GChen J(2019)Multiprocessor Synchronization of Periodic Real-Time Tasks Using Dependency Graphs2019 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS.2019.00031(279-292)Online publication date: Apr-2019
https://doi.org/10.1109/RTAS.2019.00031
Chen ZLei HYang MLiao YYu J(2019)Improved Task and Resource Partitioning Under the Resource-Oriented Partitioned SchedulingJournal of Computer Science and Technology10.1007/s11390-019-1945-534:4(839-853)Online publication date: 19-Jul-2019
https://doi.org/10.1007/s11390-019-1945-5
Brandenburg B(2019)Multiprocessor Real-Time Locking ProtocolsHandbook of Real-Time Computing10.1007/978-981-4585-87-3_10-1(1-99)Online publication date: 15-Nov-2019
https://doi.org/10.1007/978-981-4585-87-3_10-1
Show More Cited By

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