TY - JOUR
T1 - Speeding up the Schedulability Analysis and Priority Assignment of Sporadic Tasks under Uniprocessor FPNS
AU - Zhang, Weizhe
AU - Bai, Enci
AU - Li, Jing
N1 - Funding Information:
Manuscript received July 23, 2019; revised November 21, 2019; accepted December 28, 2019. Date of publication January 22, 2020; date of current version June 22, 2020. This work was supported in part by the National Science Foundation (NSF) of China under Grants 61672186 and 61872110, and in part by the NSF of the United States provided under Grant CNS-1948457. Paper no. TII-19-3292. (Corresponding author: Weizhe Zhang.) W. Zhang is with the School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China, and with the Cyberspace Security Research Center, Peng Cheng Laboratory, Shenzhen 518000, China (e-mail: wzzhang@hit.edu.cn).
Publisher Copyright:
© 2005-2012 IEEE.
PY - 2020/10
Y1 - 2020/10
N2 - Fixed-priority non-preemptive scheduling (FPNS) is widely used in practice because of its simplicity and predictability. This article aims to enhance the efficiency of the schedulability analysis and priority assignment of sporadic tasks under uniprocessor FPNS. To speed-up the schedulability analysis, we first improve the state-of-the-art worst-case response time analysis for uniprocessor fixed-priority non-preemptive scheduling. In addition, we present two special conditions under which the worst-case response time of a task can be analyzed from its first job, which further improves the efficiency of the analysis. To accelerate the priority assignment, we present two priority-assignment algorithms based on the improved Audsley's algorithm: improved Audsley-based longest deadline first (IA-LDF) and improved Audsley-based longest worst-case execution time first (IA-LCF). The numerical experiments show that IA-LDF and IA-LCF can lead to 31.2% and 36% decrease in runtime compared to longest deadline first (LDF) and longest worst-case execution time first (LCF), respectively.
AB - Fixed-priority non-preemptive scheduling (FPNS) is widely used in practice because of its simplicity and predictability. This article aims to enhance the efficiency of the schedulability analysis and priority assignment of sporadic tasks under uniprocessor FPNS. To speed-up the schedulability analysis, we first improve the state-of-the-art worst-case response time analysis for uniprocessor fixed-priority non-preemptive scheduling. In addition, we present two special conditions under which the worst-case response time of a task can be analyzed from its first job, which further improves the efficiency of the analysis. To accelerate the priority assignment, we present two priority-assignment algorithms based on the improved Audsley's algorithm: improved Audsley-based longest deadline first (IA-LDF) and improved Audsley-based longest worst-case execution time first (IA-LCF). The numerical experiments show that IA-LDF and IA-LCF can lead to 31.2% and 36% decrease in runtime compared to longest deadline first (LDF) and longest worst-case execution time first (LCF), respectively.
KW - Fixed priority
KW - non-preemptive scheduling
KW - priority assignment
KW - real-time scheduling
KW - schedulability analysis
UR - http://www.scopus.com/inward/record.url?scp=85088137718&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85088137718&partnerID=8YFLogxK
U2 - 10.1109/TII.2020.2968590
DO - 10.1109/TII.2020.2968590
M3 - Article
AN - SCOPUS:85088137718
SN - 1551-3203
VL - 16
SP - 6382
EP - 6392
JO - IEEE Transactions on Industrial Informatics
JF - IEEE Transactions on Industrial Informatics
IS - 10
M1 - 8966460
ER -