Enhanced Harmonic Partitioned Scheduling of Periodic Real-Time Tasks Based on Slack Analysis

被引:0
作者
Ren, Jiankang [1 ,2 ,3 ]
Zhang, Jun [4 ]
Li, Xu [3 ]
Cao, Wei [3 ]
Li, Shengyu [1 ]
Chu, Wenxin [3 ]
Song, Chengzhang [3 ]
机构
[1] Dalian Univ Technol, Sch Comp Sci & Technol, Dalian 116024, Peoples R China
[2] Minist Educ, Key Lab Social Comp & Cognit Intelligence, Dalian 116024, Peoples R China
[3] Xinjiang Normal Univ, Sch Comp Sci & Technol, Urumqi 830054, Peoples R China
[4] Dalian Univ Technol, Grad Sch Educ, Dalian 116024, Peoples R China
基金
中国国家自然科学基金;
关键词
Internet of Things; real-time scheduling; partitioned scheduling; multiprocessor systems; periodic real-time tasks; slack analysis;
D O I
10.3390/s24175773
中图分类号
O65 [分析化学];
学科分类号
070302 ; 081704 ;
摘要
The adoption of multiprocessor platforms is growing commonplace in Internet of Things (IoT) applications to handle large volumes of sensor data while maintaining real-time performance at a reasonable cost and with low power consumption. Partitioned scheduling is a competitive approach to ensure the temporal constraints of real-time sensor data processing tasks on multiprocessor platforms. However, the problem of partitioning real-time sensor data processing tasks to individual processors is strongly NP-hard, making it crucial to develop efficient partitioning heuristics to achieve high real-time performance. This paper presents an enhanced harmonic partitioned multiprocessor scheduling method for periodic real-time sensor data processing tasks to improve system utilization over the state of the art. Specifically, we introduce a general harmonic index to effectively quantify the harmonicity of a periodic real-time task set. This index is derived by analyzing the variance between the worst-case slack time and the best-case slack time for the lowest-priority task in the task set. Leveraging this harmonic index, we propose two efficient partitioned scheduling methods to optimize the system utilization via strategically allocating the workload among processors by leveraging the task harmonic relationship. Experiments with randomly synthesized task sets demonstrate that our methods significantly surpass existing approaches in terms of schedulability.
引用
收藏
页数:24
相关论文
共 23 条
[1]   Multi-Core Time-Triggered OCBP-Based Scheduling for Mixed Criticality Periodic Task Systems [J].
Baciu, Marian D. ;
Capota, Eugenia A. ;
Stangaciu, Cristina S. ;
Curiac, Daniel-Ioan ;
Micea, Mihai V. .
SENSORS, 2023, 23 (04)
[2]   Measuring the performance of schedulability tests [J].
Bini, E ;
Buttazzo, GC .
REAL-TIME SYSTEMS, 2005, 30 (1-2) :129-153
[3]   Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption [J].
Bril, Reinder J. ;
Lukkien, Johan J. ;
Verhaegh, Wim F. J. .
REAL-TIME SYSTEMS, 2009, 42 (1-3) :63-119
[4]   Virtualization Over Multiprocessor Systems-on-Chip: An Enabling Paradigm for the Industrial Internet of Things [J].
Cilardo, Alessandro ;
Cinque, Marcello ;
De Simone, Luigi ;
Mazzocca, Nicola .
COMPUTER, 2022, 55 (10) :35-47
[5]   Efficient exact schedulability tests for fixed priority real-time systems [J].
Davis, Robert I. ;
Zabos, Attila ;
Burns, Alan .
IEEE TRANSACTIONS ON COMPUTERS, 2008, 57 (09) :1261-1276
[6]   Enhanced fixed-priority real-time scheduling on multi-core platforms by exploiting task period relationship [J].
Fan, Ming ;
Han, Qiushi ;
Liu, Shuo ;
Ren, Shaolei ;
Quan, Gang ;
Ren, Shangping .
JOURNAL OF SYSTEMS AND SOFTWARE, 2015, 99 :85-96
[7]   A better polynomial-time schedulability test for real-time fixed-priority scheduling algorithms [J].
Han, CC ;
Tyan, H .
18TH IEEE REAL-TIME SYSTEMS SYMPOSIUM, PROCEEDINGS, 1997, :36-45
[8]   On-Orbit Remote Sensing Image Processing Complex Task Scheduling Model Based on Heterogeneous Multiprocessor [J].
Jiang, Qiangqiang ;
Wang, Haipeng ;
Kong, Qinglei ;
Zhang, Yamin ;
Chen, Bo .
IEEE TRANSACTIONS ON GEOSCIENCE AND REMOTE SENSING, 2023, 61
[9]   FINDING RESPONSE-TIMES IN A REAL-TIME SYSTEM [J].
JOSEPH, M ;
PANDYA, P .
COMPUTER JOURNAL, 1986, 29 (05) :390-395
[10]  
Jugade C., 2024, P AM CONTR C TOR ON, P4470