Correspondence Article: Counterexample for suspension-aware schedulability analysis of EDF scheduling
- PDF / 696,701 Bytes
- 4 Pages / 439.37 x 666.142 pts Page_size
- 63 Downloads / 158 Views
Correspondence Article: Counterexample for suspension‑aware schedulability analysis of EDF scheduling Mario Günzel1 · Jian‑Jia Chen1
© The Author(s) 2020
1 Introduction Self-suspension behavior has been demonstrated to appear in complex cyber-physical real-time systems, e.g., multiprocessor locking protocols, computation offloading, and multicore resource sharing, as demonstrated in (Chen et al. (2019), Section 2). Although the impact of self-suspension behavior has been investigated since 1990, the literature of this research topic has been flawed as reported in the review by Chen et al. (2019). Although the review by Chen et al. (2019) provides a comprehensive survey of the literature, two unresolved issues are listed in the concluding remark. One of them is regarding the “correctness of Theorem 8 in (Devi (2003), Section 4.5) … supported with a rigorous proof, since self-suspension behavior has induced several non-trivial phenomena”. This paper provides a counterexample of Theorem 8 in (Devi (2003), Section 4.5) and disproves the schedulability test. We consider a set of implicit-deadline periodic tasks 𝕋 = {𝜏1 , … , 𝜏n } , in which each task 𝜏i has its period Ti , worst-case self-suspension time Si , and worst-case execution time Ci . The relative deadline Di is set to Ti . There are two main models of self-suspending tasks: the dynamic self-suspension and segmented (or multi-segment) self-suspension models. Devi’s analysis in Devi (2003) considers the dynamic self-suspension model. That is, a task instance (job) released by a task 𝜏i can suspend arbitrarily as long as the total amount of suspension time of the job is not more than Si. Devi’s analysis for implicit-deadline task systems is rephrased as follows:
* Jian‑Jia Chen jian‑[email protected]‑dortmund.de Mario Günzel mario.guenzel@tu‑dortmund.de 1
Department of Informatics, TU Dortmund University, Dortmund, Germany
13
Vol.:(0123456789)
Real-Time Systems
{ } Theorem 1 (Devi 2003) Let 𝕋 = 𝜏1 , 𝜏2 , … , 𝜏n be a system of n implicit-deadline periodic tasks, arranged in order of non-decreasing periods. The task set 𝕋 is schedulable using preemptive EDF if for all k with 1 ≤ k ≤ n inequality ∑k ∑k C i Bk +B�k + i=1 T ≤ 1 holds, where and Bk = i=1 min{Si , Ci } Tk i( ) B�k = max1≤i≤k max{0, Si − Ci } . Note that the notation follows the survey paper by Chen et al. (2019) instead of the original paper by Devi (2003). Moreover, Devi considered arbitrary-deadline task systems with asynchronous arrival times. Our counterexample is valid by considering two implicit-deadline periodic tasks released at the same time and disproves also the general case.
2 Counterexample for Devi’s analysis The following task set 𝕋 with only two tasks provides a counterexample for Devi’s analysis: – 𝜏1 ∶ (T1 = D1 = 6, C1 = 5, S1 = 1) and – 𝜏2 ∶ (T2 = D2 = 8, C2 = 𝜖, S2 = 0) , for any 0 < 𝜖 ≤ 1∕3. The test of Theorem 1 is as follows:
k = 1 , we have B1 = 1 and B�1 = 0 . Therefore, when k = 1 , we obtain – When ∑k C Bk +B�k + i=1 T i = 1. T k
i
k
i
k = 2 , we have
Data Loading...
