Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
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)\(\dots \)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.
Advertisement
We consider a set of implicit-deadline periodic tasks \({\mathbb {T}} = \{\tau _1, \dots , \tau _n\}\), in which each task \(\tau _i\) has its period \(T_i\), worst-case self-suspension time \(S_i\), and worst-case execution time \(C_i\). The relative deadline \(D_i\) is set to \(T_i\). 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 \(\tau _i\) can suspend arbitrarily as long as the total amount of suspension time of the job is not more than \(S_i\).
Devi’s analysis for implicit-deadline task systems is rephrased as follows:
Theorem 1
(Devi 2003) Let\({\mathbb {T}} = \left\{ {\tau _1, \tau _2, \ldots , \tau _n}\right\} \)be a system ofnimplicit-deadline periodic tasks, arranged in order of non-decreasing periods. The task set\({\mathbb {T}}\)is schedulable using preemptive EDF if for allkwith\(1 \le k \le n\)inequality\( \frac{B_k+B_k'}{T_k} + \sum _{i=1}^{k}\frac{C_i}{T_i} \le 1 \)holds, where\( B_k = \sum _{i=1}^{k} \min \{S_i, C_i\}\)and\( B_k' = \max _{1 \le i \le k}\left( \max \{0, S_i - C_i\}\right) \).
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.
Advertisement
2 Counterexample for Devi’s analysis
The following task set \({\mathbb {T}}\) with only two tasks provides a counterexample for Devi’s analysis:
\(\tau _1: (T_1=D_1=6, C_1=5, S_1=1)\) and
\(\tau _2: (T_2=D_2=8, C_2=\epsilon , S_2=0)\), for any \(0 <\epsilon \le 1/3\).
When \(k=1\), we have \(B_1 = 1\) and \(B_1'=0\). Therefore, when \(k=1\), we obtain \(\frac{B_k+B_k'}{T_k} + \sum _{i=1}^{k}\frac{C_i}{T_i} = 1\).
When \(k=2\), we have \(B_2 = 1\) and \(B_2'=0\). Therefore, when \(k=2\), we obtain \(\frac{B_k+B_k'}{T_k} + \sum _{i=1}^{k}\frac{C_i}{T_i} = \frac{1}{8} + \frac{\epsilon }{8} + \frac{5}{6} = \frac{23+3\epsilon }{24} \le 1\), since \(\epsilon \le 1/3\).
Therefore, Devi’s schedulability test concludes that the task set is feasibly scheduled by preemptive EDF. But, a concrete schedule as demonstrated in Figure 1 shows that one of the jobs of task \(\tau _1\) misses its deadline even when both tasks release their first jobs at the same time.
Fig. 1
A concrete EDF schedule with a deadline miss
×
The example in Fig. 1 shows that a job of task \(\tau _1\) may be blocked by a job of task \(\tau _2\), which results in a deadline miss of the job of task \(\tau _1\). The counterexample only requires task \(\tau _1\) to suspend once. It shows that applying Devi’s analysis in Devi (2003) is unsafe even for the segmented self-suspension model under EDF scheduling. We note that the above counterexample is only for Theorem 8 in Devi (2003). We do not examine any other schedulability tests in Devi (2003).
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
