1 Introduction
1.1 Impact of self-suspending behavior
1.2 Purpose and organization of this paper
-
Incorrect quantification of jitter for dynamic self-suspending task systems (Audsley and Bletsas 2004a, b; Kim et al. 1995; Ming 1994). This misconception was unfortunately carried forward in Zeng and di Natale (2011), Brandenburg (2013), Yang et al. (2013), Kim et al. (2014), Han et al. (2014), Carminati et al. (2014), Yang et al. (2014), and Lakshmanan et al. (2009) in the analysis of worst-case response times under partitioned multiprocessor real-time locking protocols.
-
Incorrect quantification of jitter for segmented self-suspending task systems (Bletsas and Audsley 2005).
-
Incorrect assumptions on the critical instant as defined in Lakshmanan and Rajkumar (2010).
-
Incorrectly counting highest-priority self-suspension time to reduce the interference on the lower-priority tasks (Kim et al. 2013).
-
Incorrect conversion of higher-priority self-suspending tasks into sporadic tasks with release jitter (Nelissen et al. 2015).
-
summarize the existing self-suspending task models (Sect. 3);
-
explain the misconceptions in the literature, their consequences, and potential solutions to fix those flaws (Sect. 5);
-
examine the inherited flaws in multiprocessor synchronization, due to a flawed analysis in self-suspending task models (Sect. 6);
-
provide the summary of the computational complexity classes of different self-suspending task models and systems (Sect. 8).
2 Examples of self-suspending task systems
3 Real-time sporadic self-suspending task models
3.1 Assumptions and terminology
3.1.1 Scheduling
3.1.2 Analysis
3.1.3 Platform
4 General design and analysis strategies
Papers/methods | Suspension and scheduling model | Interfered task (\(\tau _k\)) | Interfering tasks (hp(k) under FP) |
---|---|---|---|
Ming (1994) | Dynamic, FP | Suspension-oblivious, Sect. 4.1.1 | As release jitter, Sect. 4.2.3 |
Kim et al. (1995) | Dynamic, FP | Suspension-oblivious, Sect. 4.1.1 | As release jitter, Sect. 4.2.3 |
Palencia and Harbour (1998) | Segmented, FP | Split (see footnote 1), Sect. 4.1.2 | Segmented structures with dynamic offsets, Sect. 4.2.6 |
Liu (2000, pp. 164–165) | Dynamic, FP | Suspension-oblivious, Sect. 4.1.1 | As blocking, Sect. 4.2.4 |
Devi (2003, Sect. 4.5) | Dynamic, EDF | Suspension-oblivious, Sect. 4.1.1 | As blocking, Sect. 4.2.4 |
Dynamic, FP | Suspension-oblivious, Sect. 4.1.1 | As release jitter, Sect. 4.2.3 | |
Bletsas and Audsley (2005) | Segmented, FP | Suspension-oblivious, Sect. 4.1.1 | Segmented structures with fixed offsets, Sect. 4.2.6 |
Bletsas (2007, Chapter 5.4) | Dynamic or segmented, FP | Hybrid, Sect. 4.1.3 | Segmented structures with fixed offsets, Sect. 4.2.6 |
Lakshmanan and Rajkumar (2010) | Segmented, FP | Revised critical instant, Sect. 4.1.4 | (Only ordinary sporadic tasks) |
Liu and Anderson (2013) | Multiprocessor, global FP and EDF | Suspension-oblivious, Sect. 4.1.1 | Carry-in jobs in multiprocessor scheduling, Sect. 4.4 |
Liu et al. (2014a) | Dynamic, FP (harmonic) | Suspension-oblivious, Sect. 4.1.1 | No additional impact due to self-suspension |
Liu and Chen (2014) | Dynamic, FP | suspension-oblivious, Sect. 4.1.1 | As carry-in, Sect. 4.2.2 |
Huang and Chen (2015b) | Segmented, FP | Segmented structures with dynamic offsets, Sect. 4.2.6 | |
Huang et al. (2015) | Dynamic, FP | Suspension-oblivious, Sect. 4.1.1 | As carry-in, Sect. 4.2.2 |
Nelissen et al. (2015) | Segmented, FP | Based on a revised critical instant, Sect. 4.1.4 | Suspension by modeling proper release jitter (Sect. 4.2.3) and enumerating the worst-case interferences |
Chen et al. (2016c) | Dynamic, FP | Suspension-oblivious, Sect. 4.1.1 | A unifying framework based on more precise release jitter, Sect. 4.2.5 |
Interfered task (\(\tau _k\)) | ||||
---|---|---|---|---|
Suspension-oblivious (Sect. 4.1.1) | Split (Sect. 4.1.2) | Hybrid (Sect. 4.1.3) | Critical instant (Sect. 4.1.4) | |
Interfering tasks | ||||
Suspension-oblivious (Sect. 4.2.1) | Used as base-lines in many papers | – | – | |
Carry-in jobs (Sect. 4.2.2) |
Huang and Chen (2015b) |
Huang and Chen (2015b) | – | |
Suspension as blocking (Sect. 4.2.4) | – | – | – | |
Segmented structures (Sect. 4.2.6) | – |
Palencia and Harbour (1998) (footnote 1) | – |
4.1 Modeling the interfered task
4.1.1 Modeling suspension as computation
4.1.2 Modeling each computation segment as an independent task
4.1.3 Hybrid approaches
4.1.4 Exact schedulability analysis
4.2 Modeling the interfering tasks
-
suspension-oblivious analysis in Sect. 4.2.1,
-
interference analysis based on carry-in jobs in Sect. 4.2.2,
-
interference analysis based on release jitter in Sect. 4.2.3,
-
modeling self-suspensions as blocking in Sect. 4.2.4, and
-
unifying interference analysis based on more precise jitter in Sect. 4.2.5.
4.2.1 Suspension-oblivious analysis
4.2.2 Modeling self-suspensions with carry-in jobs
4.2.3 Modeling self-suspensions as release jitter
4.2.4 Modeling self-suspensions as blocking
4.2.5 A unifying analysis framework
-
If \(x_i\) is 1 for task \(\tau _i\), then the release jitter of task \(\tau _i\) is \(\sum _{j=i}^{k-1} (S_j \times x_j)\).
-
If \(x_i\) is 0 for task \(\tau _i\), then the release jitter of task \(\tau _i\) is \((\sum _{j=i}^{k-1} (S_j \times x_j)) + R_i-C_i\).
\(C_i\)
|
\(S_i\)
|
\(D_i\)
|
\(T_i\)
| |
---|---|---|---|---|
\(\tau _1\)
| 4 | 5 | 10 | 10 |
\(\tau _2\)
| 6 | 1 | 19 | 19 |
\(\tau _3\)
| 4 | 0 | 50 | 50 |
\({\varvec{x}}\)
| Condition of Eq. (3) | Upper bound of \(R_3\) | ||
---|---|---|---|---|
Case 1: (0, 0) |
\(4+ \left\lceil {\frac{t+0+5}{10}}\right\rceil 4 + \left\lceil {\frac{t+0+9}{19}}\right\rceil 6 \le t\)
| 42 | ||
Case 2: (0, 1) |
\(4+ \left\lceil {\frac{t+1+5}{10}}\right\rceil 4 + \left\lceil {\frac{t+1+0}{19}}\right\rceil 6 \le t\)
| 32 | ||
Case 3: (1, 0) |
\(4+ \left\lceil {\frac{t+5+0}{10}}\right\rceil 4 + \left\lceil {\frac{t+0+9}{19}}\right\rceil 6 \le t\)
| 42 | ||
Case 4: (1, 1) |
\(4+ \left\lceil {\frac{t+6+0}{10}}\right\rceil 4 + \left\lceil {\frac{t+1+0}{19}}\right\rceil 6 \le t\)
| 32 |
4.2.6 Improving the modeling of segmented self-suspending tasks
4.2.7 Remarks on the methods without enforcement
4.3 Period enforcement mechanisms
4.3.1 Dynamic online period enforcement
4.3.2 Static period enforcement
4.3.3 Slack enforcement
4.4 Multiprocessor scheduling for self-suspending tasks
5 Existing misconceptions in the state of the art
5.1 Incorrect quantifications of jitter (dynamic self-suspension)
\(\tau _i\)
|
\(C_i\)
|
\(S_i\)
|
\(T_i\)
|
---|---|---|---|
\(\tau _1\)
| 1 | 0 | 2 |
\(\tau _2\)
| 5 | 5 | 20 |
\(\tau _3\)
| 1 | 0 |
\(\infty \)
|
5.2 Incorrect quantifications of jitter (segmented self-suspension)
\(\tau _i\)
|
\((C_i^1, S_i^1, C_i^2)\)
|
\(D_i\)
|
\(T_i\)
|
---|---|---|---|
\(\tau _1\)
| (2, 0, 0) | 5 | 5 |
\(\tau _2\)
| (2, 0, 0) | 10 | 10 |
\(\tau _3\)
| (1, 5, 1) | 15 | 15 |
\(\tau _4\)
| (3, 0, 0) | ? |
\(\infty \)
|
5.3 Incorrect assumptions regarding the critical instant
-
the scheduling algorithm is fixed-priority;
-
\(\tau _k\) is the lowest-priority task; and
-
all the higher-priority tasks are sporadic and non-self-suspending.
-
every task releases a job simultaneously with \(\tau _k\);
-
the jobs of higher-priority tasks that are eligible to be released during the self-suspension interval of \(\tau _k\) are delayed to be aligned with the release of the subsequent computation segment of \(\tau _k\); and
-
all the remaining jobs of the higher-priority tasks are released with their minimum inter-arrival time.
\((C_i^1, S_i^1, C_i^2)\)
|
\(D_i=T_i\)
| |
---|---|---|
\(\tau _1\)
| (1, 0, 0) | 4 |
\(\tau _2\)
| (1, 0, 0) | 50 |
\(\tau _3\)
| (1, 2, 3) | 100 |
5.3.1 A counterexample to the synchronous release
5.3.2 A counterexample to the minimum inter-release time
\((C_i^1, S_i^2, C_i^2)\)
|
\(D_i=T_i\)
| |
---|---|---|
\(\tau _1\)
| (4, 0, 0) | 8 |
\(\tau _2\)
| (1, 0, 0) | 10 |
\(\tau _3\)
| (1, 0, 0) | 17 |
\(\tau _4\)
| (265, 2, 6) | 1000 |
5.4 Counting highest-priority self-suspension time to reduce the interference
-
there is only one self-suspending task with the highest priority, i.e., \(\tau _1\),
-
the self-suspension time is fixed, i.e., early return of self-suspension has to be controlled by the scheduler, and
-
the actual execution time of the self-suspending task is always equal to its worst-case execution time.
\((C_i^1, S_i^1, C_i^2)\)
|
\(D_i=T_i\)
| |
---|---|---|
\(\tau _1\)
|
\((\epsilon , 1, 1)\)
|
\(4+10\epsilon \)
|
\(\tau _2\)
| (\(2+2\epsilon \), 0, 0) | 6 |
\(\tau _3\)
| (\(2+2\epsilon \), 0, 0) | 6 |
Counter example of Theorem 3 in Kim et al. (2013) Suppose that the self-suspending task \(\tau _1\) has two computation segments, with \(C_1^1 = C_1-\epsilon \), \(C_1^2 = \epsilon \), and \(S_1=S_1^1 > 0\) with very small \(0 < \epsilon \ll C_1^1\). For such an example, it is obvious that this self-suspending highest-priority task is like an ordinary sporadic task, i.e., self-suspension does not matter. In this counterexample, the utilization bound is still Liu and Layland bound \(n(2^{\frac{1}{n}}-1)\) (Liu and Layland 1973), regardless of the ratio of \(S_1/T_1\).Theorem 3 in Kim et al. (2013) For a taskset \(\varGamma _{1s}\) with implicit deadlines, \(\varGamma _{1s}\) is schedulable if the total utilization of the taskset is less than or equal to \(n((2+2\gamma )^{\frac{1}{n}}-1)-\gamma \), where n is the number of tasks in \(\varGamma _{1s}\), and \(\gamma \) is the ratio of \(S_1\) to \(T_1\) and lies in the range of 0 to \(2^{\frac{1}{n-1}}-1\).
5.5 Incorrect analysis of segmented fixed-priority scheduling with periodic enforcement
\((C_i^1, S_i^1, C_i^2)\)
|
\(D_i=T_i\)
| |
---|---|---|
\(\tau _1\)
| (10, 0, 0) | 30 |
\(\tau _2\)
| (5, 5, 16) | 40 |
5.6 Incorrect conversion of higher priority self-suspending tasks
\((C_i^1, S_i^1, C_i^2)\)
|
\(D_i\)
|
\(T_i\)
| |
---|---|---|---|
\(\tau _1\)
| (5, 0, 0) | 10 | 10 |
\(\tau _2\)
| (3, 12, 3) | 28 | 1000 |
\(\tau _3\)
| (3, 4, 3) | 35 | 1000 |
6 Self-suspending tasks in multiprocessor synchronization
6.1 Semaphores in uniprocessor systems
6.2 Semaphores in partitioned multiprocessor systems
\(\tau _k\)
|
\(C_k\)
| \(T_k\) (\(= D_k\)) |
\(s_k\)
|
\(C_{k,1}^{\prime }\)
| Processor |
---|---|---|---|---|---|
\(\tau _1\)
| 2 | 6 | 0 | − | 1 |
\(\tau _2\)
|
\(4+6\epsilon \)
| 13 | 1 |
\(5\epsilon \)
| 1 |
\(\tau _3\)
|
\(\epsilon \)
| 14 | 0 | − | 1 |
\(\tau _4\)
| 7 | 14 | 1 |
\(4-4\epsilon \)
| 2 |
6.3 Incorrect contention bound in interface-based analysis
6.4 A safe response-time bound
7 Soft real-time self-suspending task systems
7.1 Suspension-oblivious analysis
7.2 Suspension-aware analysis
8 Computational complexity and approximations
Task Model | Feasibility | Schedulability | ||
---|---|---|---|---|
Fixed-priority scheduling | Dynamic-priority scheduling (constrained-deadline) | Dynamic-priority scheduling (implicit-deadline) | ||
Segmented self-suspension models | co\({\mathcal {NP}}\)-hard in the strong sense (Chen 2016) | co\({\mathcal {NP}}\)-hard in the strong sense (Chen 2016) | ||
Dynamic self-suspension models | Unknown | (At least) \({\mathcal {NP}}\)-hard in the weak sense (Ekberg and Yi 2017) | co\({\mathcal {NP}}\)-hard in the strong sense (Chen 2016) | Unknown |
8.1 Computational complexity of designing scheduling policies
8.1.1 Segmented self-suspending tasks
8.1.2 Dynamic self-suspending tasks
-
\(C_1=1-2\epsilon \), \(S_1=0\), \(T_1=1\)
-
\(C_2=\epsilon \), \(S_2=T-1-\epsilon \), \(T_2=T\)
8.2 Computational complexity of schedulability tests
8.2.1 Segmented self-suspending tasks
8.2.2 Dynamic self-suspending tasks
Type of arguments | Affected papers and statements | Potential solutions | (Flaw/issue) status |
---|---|---|---|
Conceptual flaws | Solved | ||
Ming (1994): wrong quantification of jitter | See Sect. 5.1 | Solved | |
Bletsas and Audsley (2005): wrong quantification of jitter | Solved | ||
Lakshmanan and Rajkumar (2010): critical instant theorem in Section III and the response time analysis are incorrect | Solved | ||
Kim et al. (2013): incorrect accounting for the highest-priority interference in Theorems 2 and 3 | See Sect. 5.4 | Solved | |
See Sect. 5.5 | Solved | ||
Nelissen et al. (2015): incorrect combination of techniques in Section VI by converting a higher priority self-suspending task in a single non-self-suspending task with jitter | See Sect. 5.6 | Solved | |
Inherited flaws | See Sect. 6.4 | Solved | |
See the erratum Liu and Anderson (2015) filed by the authors | Solved | ||
Closed issues | (Liu 2000, pp. 164–165): schedulability test without any proof | See (Chen et al. 2016b) for a proof | Solved |
Rajkumar (1991): period enforcer can be used for deferrable task systems. It may result in deadline misses for self-suspending tasks and is not compatible with existing multiprocessor synchronization analyses | See (Chen and Brandenburg 2017) for the explanations. | Solved | |
Open issues |
Devi (2003): Proof of Theorem 8 for considering suspension as blocking in EDF is incomplete | ? | Unresolved |
Lakshmanan and Rajkumar (2010): proofs for slack enforcement in Sections IV and V are incomplete | ? | Unresolved |
9 Final discussion
9.1 Unresolved issues
-
Devi (in Theorem 8 in Devi 2003, Section 4.5) extended the analysis proposed by Jane W.S. Liu in her book (Liu 2000, Page 164-165) to EDF scheduling. This method quantifies the additional interference due to self-suspensions from the higher-priority jobs by setting up the blocking time induced by self-suspensions. However, there is no formal proof in Devi (2003). The proof made by Chen et al. in Chen et al. (2016b, c) for fixed-priority scheduling cannot be directly extended to EDF scheduling. The correctness of Theorem 8 in Devi (2003), Section 4.5 should be supported with a rigorous proof, since self-suspension behavior has induced several non-trivial phenomena.
-
For segmented self-suspending task systems with at most one self-suspension interval, Lakshmanan and Rajkumar (2010) proposed two slack enforcement mechanisms to shape the demand of a self-suspending task so that the task behaves like an ideal ordinary periodic task. From the scheduling point of view, this means that there is no scheduling penalty when analyzing the interferences of the higher-priority tasks. However, the suspension time of the task under analysis has to be converted into computation. The correctness of the dynamic slack enforcement in Lakshmanan and Rajkumar (2010) is heavily based on the statement of their Lemma 4. However, the proof is not rigorous for the following reasons:For similar reasons, the static slack enforcement algorithm in Lakshmanan and Rajkumar (2010) also requires a more rigorous proof.
-
Firstly, the proof argues: “Let the durationRunder consideration start from timesand finish at time\(s + R\). Observe that ifsdoes not coincide with the start of the Level-ibusy period ats, thenscan be shifted to the left to coincide with the start of the Level-ibusy period. Doing so will not decrease the Level-iinterference overR.” This argument has to be expanded to also handle cases in which a task suspends before the \(Level-i\) busy period. This results in the possibility that a higher-priority task \(\tau _j\) starts with the second computation segment in the Level-i busy period. Therefore, the first and the third paragraphs in the proof of Lemma 4 (Lakshmanan and Rajkumar 2010) require more rigorous reasoning.
-
Secondly, the proof argues: “The only property introduced by dynamic slack enforcement is that under worst-case interference from higher-priority tasks there is no slack available to\(J_j^p\)between\(f_j^p\)and\(\rho _j^p + R_j\). [...]The second segment of\(\tau _j\)is never delayed under this transformation, and is released sporadically.” In fact, the slack enforcement may make the second computation segment arrive earlier than its worst case. For example, we can greedily start with the worst-case interference of task \(\tau _j\) in the first iteration, and do not release the higher-priority tasks of task \(\tau _j\) after the arrival of the second job of task \(\tau _j\). This can immediately create some release jitter of the second computation segment \(C_j^2\).
-
9.2 Non-implicated approaches
-
For segmented self-suspending task systems:1.Rajkumar’s period enforcer (Rajkumar 1991) if a self-suspending task can only suspend at most once and only before any computation starts;2.the result by Palencia and Harbour (1998) using the arrival jitter of a higher-priority task properly with an offset (also for multiprocessor partitioned scheduling);3.the proof of \({\mathcal {NP}}\)-hardness in the strong sense to find a feasible schedule and negative results with respect to the speedup factors, provided by Ridouard et al. (2004);4.the result by Nelissen et al. (2015) by enumerating the worst-case interference from higher-priority sporadic tasks with an exhaustive search;5.6.the result by Huang and Chen (2015b) exploring the priority assignment problem and analyzing the carry-in computation segments together;
-
For dynamic self-suspending task systems on uniprocessor platforms: