research-article

Scheduling and Analysis of Parallel Real-Time Tasks with Semaphores

Authors:

Xu Jiang,

Nan Guan,

Weichen Liu,

Maolin YangAuthors Info & Claims

DAC '19: Proceedings of the 56th Annual Design Automation Conference 2019

Article No.: 93, Pages 1 - 6

https://doi.org/10.1145/3316781.3317907

Published: 02 June 2019 Publication History

Get Access

Abstract

This paper for the first time studies the scheduling and analysis of parallel real-time tasks with semaphores. In parallel task systems, each task may issue multiple requests to a semaphore, which raises new challenges to the design and analysis problems. We propose a new locking protocol LPP that limits the maximal number of requests to a semaphore by a task that can block other tasks at any time. We develop analysis techniques to safely bound the task response times, with which we prove that the best real-time performance is achieved if only one request to a semaphore by a task is allowed to block other tasks at a time. Experiments under different parameter settings are conducted to compare our proposed protocol and analysis techniques with the state-of-the-art spinlock protocol and analysis techniques for parallel real-time tasks.

References

[1]

Sanjoy Baruah. 2015. Federated scheduling of sporadic dag task systems. In IPDPS.

Digital Library

Google Scholar

[2]

Aaron Block, Hennadiy Leontyev, Bjorn B Brandenburg, and James H Anderson. 2007. A flexible real-time locking protocol for multiprocessors. In RTCSA. IEEE, 47--56.

Digital Library

Google Scholar

[3]

Björn Brandenburg and James H Anderson. 2011. Scheduling and locking in multiprocessor real-time operating systems. Ph.D. Dissertation. Citeseer.

Google Scholar

[4]

Björn B Brandenburg and James H Anderson. 2010. Optimality results for multiprocessor real-time locking. In RTSS. IEEE, 49--60.

Digital Library

Google Scholar

[5]

Daniel Cordeiro, Grégory Mounié, and et.al. 2010. Random graph generation for scheduling simulations. In ICST.

Digital Library

Google Scholar

[6]

Son Dinh, Jing Li, Kunal Agrawal, Chris Gill, and Chenyang Lu. 2018. Blocking Analysis for Spin Locks in Real-Time Parallel Tasks. IEEE Transactions on Parallel and Distributed Systems 29, 4 (2018), 789--802.

Crossref

Google Scholar

[7]

Mike Jones. 1997. What really happened on mars rover pathfinder. The Risks Digest 19, 49 (1997), 1--2.

Google Scholar

[8]

Jing Li, Jian Jia Chen, and et.al. 2014. Analysis of federated and global scheduling for parallel real-time tasks. In ECRTS.

Digital Library

Google Scholar

[9]

Claudio Maia, Marko Bertogna, and et.al. 2014. Response-time analysis of synchronous parallel tasks in multiprocessor systems. In RTNS.

Digital Library

Google Scholar

[10]

Ragunathan Rajkumar. 1990. Real-time synchronization protocols for shared memory multiprocessors. In ICDCS. IEEE, 116--123.

Google Scholar

[11]

Ragunathan Rajkumar, Lui Sha, and John P Lehoczky. 1988. Real-time synchronization protocols for multiprocessors. In RTSS. IEEE, 259--269.

Google Scholar

[12]

Jiang Xu, Guan Nan, and et.al. 2017. Semi-federated scheduling of parallel real-time tasks on multiprocessors. In RTSS.

Google Scholar

Cited By

View all

Wang YLi YPeng XJi DGuan NWang Y(2023)Design and Blocking Analysis of Locking Protocols for Real-Time DAG Tasks Under Federated SchedulingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.326472942:11(3720-3732)Online publication date: Nov-2023
https://doi.org/10.1109/TCAD.2023.3264729
Jiang XChen ZYang MGuan NTang YWang Y(2023)A Unified Blocking Analysis for Parallel Tasks With Spin Locks Under Global Fixed Priority SchedulingIEEE Transactions on Computers10.1109/TC.2022.319863472:1(15-28)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TC.2022.3198634
Liang HJiang XGuan NHe QYi W(2023)Response Time Analysis and Optimization of DAG Tasks Exploiting Mutually Exclusive Execution2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247927(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247927
Show More Cited By

Scheduling and Analysis of Parallel Real-Time Tasks with Semaphores
1. Computer systems organization

Recommendations

Analyzing Parallel Real-Time Tasks Implemented with Thread Pools
DAC '19: Proceedings of the 56th Annual Design Automation Conference 2019

Despite several works in the literature targeted predictable execution models for parallel tasks, limited attention has been devoted to study how specific implementation techniques may affect their execution. This paper highlights some issues that can ...
Scheduling algorithm for parallel real-time tasks on multiprocessor systems

The purpose of this paper is to study the task scheduling problem of task sets on multiprocessor systems. In the task sets there are parallel tasks and sequential tasks. Parallel tasks can not meet their deadlines if they are executed by one unique ...
Mixed-criticality federated scheduling for parallel real-time tasks

A mixed-criticality system comprises safety-critical and non-safety-critical tasks sharing a computational platform. Thus, different levels of assurance are required by different tasks in terms of real-time performance. As the computational demands of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '19: Proceedings of the 56th Annual Design Automation Conference 2019

June 2019

1378 pages

ISBN:9781450367257

DOI:10.1145/3316781

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]

In-Cooperation

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 June 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

National Natural Science Foundation of China
Research Grants Council of Hong Kong
China Postdoctoral Science Foundation Funded Project

Conference

DAC '19

Sponsor:

SIGDA

DAC '19: The 56th Annual Design Automation Conference 2019

June 2 - 6, 2019

NV, Las Vegas, USA

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
273
Total Downloads

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

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wang YLi YPeng XJi DGuan NWang Y(2023)Design and Blocking Analysis of Locking Protocols for Real-Time DAG Tasks Under Federated SchedulingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.326472942:11(3720-3732)Online publication date: Nov-2023
https://doi.org/10.1109/TCAD.2023.3264729
Jiang XChen ZYang MGuan NTang YWang Y(2023)A Unified Blocking Analysis for Parallel Tasks With Spin Locks Under Global Fixed Priority SchedulingIEEE Transactions on Computers10.1109/TC.2022.319863472:1(15-28)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TC.2022.3198634
Liang HJiang XGuan NHe QYi W(2023)Response Time Analysis and Optimization of DAG Tasks Exploiting Mutually Exclusive Execution2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247927(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247927
ZHANG MWU JCUI XSUN J(2023)Research on schedulability analysis algorithm of airborne multi partition systemXibei Gongye Daxue Xuebao/Journal of Northwestern Polytechnical University10.1051/jnwpu/2023413055741:3(557-567)Online publication date: 1-Aug-2023
https://doi.org/10.1051/jnwpu/20234130557
Jiang XGuan NYang MWang YTang YYi W(2022)Real-Time Scheduling of Parallel Task Graphs With Critical Sections Across Different VerticesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.317932833:12(4117-4133)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TPDS.2022.3179328
Wang YJiang XGuan NTang YLiu W(2022)Locking Protocols for Parallel Real-Time Tasks With Semaphores Under Federated SchedulingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.311426141:9(2877-2890)Online publication date: Sep-2022
https://doi.org/10.1109/TCAD.2021.3114261
Bi RHe QSun JSun ZGuo ZGuan NTan G(2022)Response Time Analysis for Prioritized DAG Task with Mutually Exclusive Vertices2022 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS55097.2022.00046(460-473)Online publication date: Dec-2022
https://doi.org/10.1109/RTSS55097.2022.00046
Haqqi BJoshua Samuel Raj R(2022)A Decision Support System for Restricted Movement with Semaphores During Lockdown in COVID-19 PandemicDisruptive Technologies for Big Data and Cloud Applications10.1007/978-981-19-2177-3_76(815-824)Online publication date: 2-Aug-2022
https://doi.org/10.1007/978-981-19-2177-3_76
Chen ZLei HYang MLiao YQiao L(2021)A Hierarchical Hybrid Locking Protocol for Parallel Real-Time TasksACM Transactions on Embedded Computing Systems10.1145/347701720:5s(1-22)Online publication date: 31-Oct-2021
https://dl.acm.org/doi/10.1145/3477017
Chen ZLei HYang MLiao YQiao L(2021)A Finer-Grained Blocking Analysis for Parallel Real-Time Tasks with Spin-Locks2021 58th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC18074.2021.9586270(1177-1182)Online publication date: 5-Dec-2021
https://doi.org/10.1109/DAC18074.2021.9586270
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Analyzing Parallel Real-Time Tasks Implemented with Thread Pools

Scheduling algorithm for parallel real-time tasks on multiprocessor systems

Mixed-criticality federated scheduling for parallel real-time tasks