research-article

An exact schedulability test for global FP using state space pruning

Authors:

Artem Burmyakov,

Enrico Bini,

Eduardo TovarAuthors Info & Claims

RTNS '15: Proceedings of the 23rd International Conference on Real Time and Networks Systems

Pages 225 - 234

https://doi.org/10.1145/2834848.2834877

Published: 04 November 2015 Publication History

Get Access

Abstract

We propose an exact schedulability test for sporadic real-time tasks with constrained deadlines, scheduled by Global Fixed Priority (GFP). Our test is faster and less memory consuming than other state-of-the-art exact tests. We achieve such results by employing a set of techniques that cut down the state space of the analysis, which extend the prior work by Bonifaci and Marchetti-Spaccamela. Our test is implemented in C++ code, and it is publicly available.

References

[1]

C. Liu and J. Layland, "Scheduling algorithms for multiprogramming in a hard real-time environment." Journal of the ACM (JACM), vol. 20, January 1973.

Digital Library

Google Scholar

[2]

M. Joseph and P. K. Pandya, "Finding response times in a real-time system," The Computer Journal, vol. 29, no. 5, pp. 390--395, Oct. 1986.

Crossref

Google Scholar

[3]

E. Bini and G. C. Buttazzo, "Schedulability analysis of periodic fixed priority systems," IEEE Transactions on Computers, vol. 53, no. 11, pp. 1462--1473, Nov. 2004.

Digital Library

Google Scholar

[4]

N. Guan, M. Stigge, W. Yi, and G. Yu, "New response time bounds for fixed priority multiprocessor scheduling," in RTSS, 2009.

Digital Library

Google Scholar

[5]

V. Bonifaci and A. Marchetti-Spaccamela, "Feasibility analysis of sporadic real-time multiprocessor task systems," Algorithmica, 2012.

Digital Library

Google Scholar

[6]

T. Baker and M. Cirinei, "Brute-force determination of multiprocessor schedulability for sets of sporadic hard-deadline tasks," Principles of Distributed Systems, Lecture Notes in Computer Science, 2007.

Digital Library

Google Scholar

[7]

G. Geeraerts, J. Goossens, and M. Lindström, "Multiprocessor schedulability of arbitrary-deadline sporadic tasks: complexity and antichain algorithm," Real-Time Systems, 2013.

Digital Library

Google Scholar

[8]

Y. Sun and G. Lipari, "A weak simulation relation for real-time schedulability analysis of global fixed priority scheduling using linear hybrid automata," in Proceedings of the 22nd International Conference on Real-Time Networks and Systems, 2014.

Digital Library

Google Scholar

[9]

N. Guan, Z. Gu, Q. Deng, S. Gao, and G. Yu, "Exact schedulability analysis for static-priority global multiprocessor scheduling using model-checking," Springer Lecture Notes in Computer Science, vol. 4761, pp. 263--272, 2007.

Digital Library

Google Scholar

[10]

S. Baruah, "Techniques for multiprocessor global schedulability analysis," in Proceedings of the IEEE Real-Time Systems Symposium, 2007.

Digital Library

Google Scholar

[11]

R. Davis and A. Burns, "Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems," Real-Time Systems, vol. 47, no. 1, pp. 1--40, 2011.

Digital Library

Google Scholar

[12]

R. Davis and A. Burns, "A survey of hard real-time scheduling for multiprocessor systems," ACM Computing Surveys, 2011.

Digital Library

Google Scholar

Cited By

View all

Garanina N(2024)An Exact Schedulability Test for Real-Time Systems with Abstract Scheduler on Multiprocessor PlatformsModeling and Analysis of Information Systems10.18255/1818-1015-2024-4-474-49431:4(474-494)Online publication date: 13-Dec-2024
https://doi.org/10.18255/1818-1015-2024-4-474-494
Deng XRaja SZhao YZeng H(2024)Priority Assignment for Global Fixed Priority Scheduling on MultiprocessorsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.337658843:9(2538-2550)Online publication date: Sep-2024
https://doi.org/10.1109/TCAD.2024.3376588
Verucchi MOlmedo IBertogna M(2023)A survey on real-time DAG scheduling, revisiting the Global-Partitioned Infinity WarReal-Time Systems10.1007/s11241-023-09403-359:3(479-530)Online publication date: 14-Aug-2023
https://doi.org/10.1007/s11241-023-09403-3
Show More Cited By

Recommendations

A Unified Hard/Soft Real-Time Schedulability Test for Global EDF Multiprocessor Scheduling
RTSS '08: Proceedings of the 2008 Real-Time Systems Symposium

The issue of deadline tardiness is considered under globalearliest-deadline-first (GEDF) multiprocessor scheduling. Newschedulability tests are presented for determining whether a setof sporadic tasks with arbitrary relative deadlines can be ...
Improved multiprocessor global schedulability analysis

A new technique was recently introduced by Bonifaci et al. for the analysis of real-time systems scheduled on multiprocessor platforms by the global Earliest Deadline First (EDF) scheduling algorithm. In this paper, this technique is generalized so that ...
An exact schedulability test for fixed-priority preemptive mixed-criticality real-time systems

The current literature of fixed-priority scheduling algorithms relies on sufficient tests to determine if a set of mixed-criticality sporadic tasks is schedulable on a single processor. The drawback of these safe tests is their pessimism, a matter that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

RTNS '15: Proceedings of the 23rd International Conference on Real Time and Networks Systems

November 2015

320 pages

ISBN:9781450335911

DOI:10.1145/2834848

General Chair:
Julien Forget
Université de Lille, France

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: 04 November 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

RTNS '15

RTNS '15: 23rd International Conference on Real-Time Networks and Systems

November 4 - 6, 2015

Lille, France

Acceptance Rates

RTNS '15 Paper Acceptance Rate 31 of 66 submissions, 47%;

Overall Acceptance Rate 119 of 255 submissions, 47%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
107
Total Downloads

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

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Garanina N(2024)An Exact Schedulability Test for Real-Time Systems with Abstract Scheduler on Multiprocessor PlatformsModeling and Analysis of Information Systems10.18255/1818-1015-2024-4-474-49431:4(474-494)Online publication date: 13-Dec-2024
https://doi.org/10.18255/1818-1015-2024-4-474-494
Deng XRaja SZhao YZeng H(2024)Priority Assignment for Global Fixed Priority Scheduling on MultiprocessorsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.337658843:9(2538-2550)Online publication date: Sep-2024
https://doi.org/10.1109/TCAD.2024.3376588
Verucchi MOlmedo IBertogna M(2023)A survey on real-time DAG scheduling, revisiting the Global-Partitioned Infinity WarReal-Time Systems10.1007/s11241-023-09403-359:3(479-530)Online publication date: 14-Aug-2023
https://doi.org/10.1007/s11241-023-09403-3
Qiao LYang MChen ZLiao YLei HSang N(2022)Global Fixed-Priority Scheduling for Parallel Real-Time Tasks with Constrained ParallelismJournal of Circuits, Systems and Computers10.1142/S021812662250150X31:08Online publication date: 3-Mar-2022
https://doi.org/10.1142/S021812662250150X
Burmyakov ABini ELee C(2022)Towards a Tractable Exact Test for Global Multiprocessor Fixed Priority SchedulingIEEE Transactions on Computers10.1109/TC.2022.314254071:11(2955-2967)Online publication date: 1-Nov-2022
https://doi.org/10.1109/TC.2022.3142540
Burmyakov ANikolić B(2021)An exact comparison of global, partitioned, and semi-partitioned fixed-priority real-time multiprocessor schedulersJournal of Systems Architecture10.1016/j.sysarc.2021.102313(102313)Online publication date: Nov-2021
https://doi.org/10.1016/j.sysarc.2021.102313
Sun JLi FGuan NZhu WXiang MGuo ZYi W(2020)On Computing Exact WCRT for DAG Tasks2020 57th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC18072.2020.9218744(1-6)Online publication date: Jul-2020
https://doi.org/10.1109/DAC18072.2020.9218744
Yalcinkaya BNasri MBrandenburg B(2019)An Exact Schedulability Test for Non-Preemptive Self-Suspending Real-Time Tasks2019 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE.2019.8715111(1228-1233)Online publication date: Mar-2019
https://doi.org/10.23919/DATE.2019.8715111
Sun YDi Natale MHaddad HWainwright RChbeir R(2018)Assessing the pessimism of current multicore global fixed-priority schedulability analysisProceedings of the 33rd Annual ACM Symposium on Applied Computing10.1145/3167132.3167195(575-583)Online publication date: 9-Apr-2018
https://dl.acm.org/doi/10.1145/3167132.3167195
Biondi ASun Y(2018)On the ineffectiveness of 1/m-based interference bounds in the analysis of global EDF and FIFO schedulingReal-Time Systems10.1007/s11241-018-9303-154:3(515-536)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s11241-018-9303-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.

Cited By

Recommendations

A Unified Hard/Soft Real-Time Schedulability Test for Global EDF Multiprocessor Scheduling

Improved multiprocessor global schedulability analysis

An exact schedulability test for fixed-priority preemptive mixed-criticality real-time systems