Workload-Aware Harmonic Partitioned Scheduling for Probabilistic Real‐Time Systems

Jiankang Ren1, Ran Bi1, Xiaoyan Su2, Qian Liu1, Guowei Wu3 and Guozhen Tan1
1School of Computer Science and Technology, Dalian University of Technology, China
2Faculty of Management and Economics, Dalian University of Technology, China
3School of Software Technology, Dalian University of Technology, China

ABSTRACT


Multiprocessor platforms, widely adopted to realize real‐time systems nowadays, bring the probabilistic characteristic to such systems because of the performance variations of complex chips. In this paper, we present a harmonic partitioned scheduling scheme with workload awareness for periodic probabilistic real time tasks on multiprocessors under the fixed‐priority preemptive scheduling policy. The key idea of this research is to improve the overall schedulability by strategically arranging the workload among processors based on the exploration of the harmonic relationship among probabilistic real‐time tasks. In particular, we define a harmonic index to quantify the harmonicity among probabilistic real‐time tasks. This index can be obtained via the harmonic period transformation and probabilistic cumulative worst case utilization calculation of these tasks. The proposed scheduling scheme first sorts tasks with respect to the workload, then packs them to processors one by one aiming at minimizing the increase of harmonic index caused by the task assignment. Experiments with randomly generated task sets show significant performance improvement of our proposed approach over the existing harmonic partitioned scheduling algorithm for probabilistic real‐time systems.



Full Text (PDF)