TY - GEN
T1 - On the optimality of RM and EDF for non-preemptive real-time harmonic tasks
AU - Nasri, Mitra
AU - Baruah, Sanjoy
AU - Fohler, Gerhard
AU - Kargahi, Mehdi
PY - 2014/10/8
Y1 - 2014/10/8
N2 - In this paper, we study non-preemptive uniprocessor realtime scheduling using the non-preemptive RM (npRM) and EDF (npEDF) scheduling algorithms. We discuss the limitations of existing studies, identifying pessimism in current schedulability analysis and inefficiencies in existing processor speedup results. Focusing on harmonic task sets, we show that even with restrictions placed on the execution times of the tasks, npRM and npEDF are not able to schedule all feasible task sets. We obtain necessary conditions for the feasibility of the harmonic tasks with arbitrary integer period ratios. Then we derive sufficient conditions for the schedulability of npRM and npEDF upon harmonic task sets. Based on these conditions, a superior speedup factor which guarantees the schedulability in cases where there are fewer restrictions on the execution times is derived. Results from simulation experiments show an average speedup factor three times less than the only existing feasible method to obtain speedup factor.
AB - In this paper, we study non-preemptive uniprocessor realtime scheduling using the non-preemptive RM (npRM) and EDF (npEDF) scheduling algorithms. We discuss the limitations of existing studies, identifying pessimism in current schedulability analysis and inefficiencies in existing processor speedup results. Focusing on harmonic task sets, we show that even with restrictions placed on the execution times of the tasks, npRM and npEDF are not able to schedule all feasible task sets. We obtain necessary conditions for the feasibility of the harmonic tasks with arbitrary integer period ratios. Then we derive sufficient conditions for the schedulability of npRM and npEDF upon harmonic task sets. Based on these conditions, a superior speedup factor which guarantees the schedulability in cases where there are fewer restrictions on the execution times is derived. Results from simulation experiments show an average speedup factor three times less than the only existing feasible method to obtain speedup factor.
UR - http://www.scopus.com/inward/record.url?scp=84953427020&partnerID=8YFLogxK
U2 - 10.1145/2659787.2659806
DO - 10.1145/2659787.2659806
M3 - Conference contribution
AN - SCOPUS:84953427020
T3 - ACM International Conference Proceeding Series
SP - 331
EP - 340
BT - Proceedings of the 22nd International Conference on Real-Time Networks and Systems, RTNS 2014
PB - Association for Computing Machinery, Inc
T2 - 22nd International Conference on Real-Time Networks and Systems, RTNS 2014
Y2 - 8 October 2014 through 10 October 2014
ER -