• German
German

Main Navigation

Brueggen/etal/2015a: Schedulability and Optimization Analysis for Non-Preemptive Static Priority Scheduling Based on Task Utilization and Blocking Factors

Bibtype Inproceedings
Bibkey Brueggen/etal/2015a
Author von der Brüggen, Georg and Chen, Jian-Jia and Huang, Wen-Hung
Title Schedulability and Optimization Analysis for Non-Preemptive Static Priority Scheduling Based on Task Utilization and Blocking Factors
Booktitle Euromicro Conference on Real-Time Systems (ECRTS) 2015
Organization IEEE
Abstract For real time task sets, allowing preemption is often considered to be important to ensure the schedulability, as it allows high-priority tasks to be allocated to the processor nearly immediately. However, preemptive scheduling also introduces some additional overhead and may not be allowed for some hardware components, which motivates the needs of non-preemptive or limited-preemptive scheduling. We present a safe sufficient schedulability test for non-preemptive (NP) fixed priority scheduling that can verify the schedulability for Deadline Monotonic (DM-NP) and Rate Monotonic (RM-NP) scheduling in linear time, if task orders according to priority and period are given. This test leads to a better upper bound on the speedup factor for DM-NP and RM-NP in comparison to Earliest Deadline First (EDF-NP) than previously known, closing the gab between lower and upper bound. We improve our test, resulting in interesting properties of the blocking time that allow to determine schedulability by only considering the schedulability of the preemptive case if some conditions are met. Furthermore, we present a utilization bound for RM-NP, based on the ratio gamma>0 of the upper bound of the maximum blocking time to the execution time, significantly improving previous results.
Note Revision 1: 14.08.2015
Year 2015
Projekt SFB876-B2
File
Bibtex Here you can get this literature entry as BibTeX format.