1 Introduction
1.1 Background and motivation
1.2 Contributions
1.2.1 Extended version
1.3 Outline
2 Related work
2.1 Limited pre-emptive scheduling
2.2 Cache-related pre-emption delays (CRPDs)
3 Models and notation
3.1 Basic model for FPPS
3.2 Refined model for FPTS
Classic notations for FPPS | Additional notations for FPTS |
---|---|
\({\text{ hep }}({\pi }) \mathop {=}\limits ^{\mathrm {def}}\{h| {\pi }_h \ge {\pi }\}\)
|
\({\text{ het }}({\pi }) \mathop {=}\limits ^{\mathrm {def}}\{h| {\theta }_h \ge {\pi }\}\)
|
\({\text{ lp }}({\pi }) \mathop {=}\limits ^{\mathrm {def}}\{\ell | {\pi }> {\pi }_{\ell }\}\)
|
\({\mathrm{lt}}({\pi }) \mathop {=}\limits ^{\mathrm {def}}\{\ell | {\pi }> {\theta }_{\ell }\}\)
|
\({\text{ hp }}({\pi }) \mathop {=}\limits ^{\mathrm {def}}\{h| {\pi }_h > {\pi }\}\)
|
\(\mathrm{b}(i) \mathop {=}\limits ^{\mathrm {def}}{\text{ lp }}({\pi }_i) \setminus {\mathrm{lt}}({\pi }_i)\)
|
\({\text{ lep }}({\pi }) \mathop {=}\limits ^{\mathrm {def}}\{\ell | {\pi }\ge {\pi }_{\ell }\}\)
|
3.3 A memory model
3.4 A model for cache-related pre-emption costs
3.5 Concluding remarks
4 Recap of response time analysis for FPPS and FPTS
4.1 FPTS with arbitrary deadlines (without CRPD)
4.2 FPPS with constrained deadlines and CRPD
4.2.1 Pre-empting tasks
4.2.2 Pre-empted tasks
4.2.3 Pre-empting and pre-empted tasks
5 FPTS with CRPD: Preliminaries and challenges
5.1 Distinguishing executing and affected tasks
Interval | Execute | Affected by \(\tau _j\)
| #-jobs | |
---|---|---|---|---|
FPPS |
\([0, R_i)\)
|
\({\text{ hep }}({\pi }_i)\)
|
\({\text{ hep }}({\pi }_i) \cap {\text{ lp }}({\pi }_j)\)
|
\( \left\{ \begin{array}{ll} E_h(R_i) &{}\quad \mathrm{if}\; h \in {\text{ hep }}({\pi }_i) \\ 0 &{}\quad \mathrm{otherwise} \\ \end{array} \right. \)
|
FPTS |
\([0, H_i)\)
|
\(\{i\} \cup {\text{ hp }}({\theta }_i)\)
|
\((\{i\} \cup {\text{ hp }}({\theta }_i)) \cap {\mathrm{lt}}({\pi }_j)\)
|
\( \left\{ \begin{array}{ll} E_h(H_i) &{}\quad \mathrm{if}\; h \in {\text{ hp }}({\theta }_i) \\ 1 &{}\quad \mathrm{if}\; i \\ 0 &{}\quad \mathrm{otherwise} \\ \end{array} \right. \)
|
\([0, L_i)\)
|
\(\{b\} \cup {\text{ hep }}({\pi }_i)\)
|
\((\{b\} \cup {\text{ hep }}({\pi }_i)) \cap {\mathrm{lt}}({\pi }_j)\)
|
\( \left\{ \begin{array}{ll} E_h(L_i) &{}\quad \mathrm{if}\; h \in {\text{ hep }}({\pi }_i) \\ 1 &{}\quad \mathrm{if}\; b \\ 0 &{} \quad \mathrm{otherwise} \\ \end{array} \right. \)
| |
\([0, S_{i,k})\)
|
\(\begin{array}{c} \text{ As } \text{ above } \text{ for }\\ {[0, L_i)}\\ \end{array}\)
|
\(\begin{array}{c} \text{ As } \text{ above } \text{ for }\\ {[0, L_i)}\\ \end{array}\)
|
\( \left\{ \begin{array}{ll} E_h(S_{i,k}) &{}\quad \mathrm{if}\; h \in {\text{ hp }}({\pi }_i) \\ k &{}\quad \mathrm{if}\; i \\ 1 &{}\quad \mathrm{if}\; b \\ 0 &{}\quad \mathrm{otherwise} \\ \end{array} \right. \)
| |
\([0, F_{i,k})\)
|
\(\begin{array}{c} \text{ As } \text{ above } \text{ for }\\ {[0, L_i)}\\ \end{array}\)
|
\(\begin{array}{c} \text{ As } \text{ above } \text{ for }\\ {[0, L_i)}\\ \end{array}\)
|
\( \left\{ \begin{array}{ll} E_h(F_{i,k}) &{}\quad \mathrm{if}\;h \in {\text{ hp }}({\theta }_i) \\ E_h(S_{i,k}) &{}\quad \mathrm{if}\; h \in {\text{ hp }}({\pi }_i) \setminus {\text{ hp }}({\theta }_i) \\ k+1 &{}\quad \mathrm{if}\; i \\ 1 &{}\quad \mathrm{if}\; b \\ 0 &{}\quad \mathrm{otherwise} \\ \end{array} \right. \)
|
-
Interval: A description of an interval under consideration, being \([0, R_i)\);
-
Execute: The tasks that can execute jobs in the interval, being tasks with a priority higher than or equal to the priority of \(\tau _i\), i.e. \({\text{ hep }}({\pi }_i)\);
-
Affected by \(\tau _j\): The set of tasks that (i) can execute jobs in the interval and (ii) can be pre-empted by task \(\tau _j\), i.e. \({\text{ hep }}({\pi }_i) \cap {\text{ lp }}({\pi }_j)\);
-
\(\#\)-jobs: The number of job activations of a task that can execute in the interval, i.e. \(E_h(R_i)\) for each task \(\tau _h \in {\text{ hep }}({\pi }_i)\).
5.2 Bounding the number of pre-emptions using hold times
T
|
D
|
C
|
\({\pi }= {\theta }\)
|
R
|
H
| |
---|---|---|---|---|---|---|
\(\tau _1\)
| 5 | 5 | 2 | 2 | 2 | 2 |
\(\tau _2\)
| 7 | 9 | 4.2 | 1 | 8.6 | 8.2 |
\(T = D\)
|
C
|
\({\pi }\)
|
\({\theta }\)
|
R
|
H
| |
---|---|---|---|---|---|---|
\(\tau _1\)
| 6 | 1 | 4 | 4 | 3 | 1 |
\(\tau _2\)
| 7 | 2 | 3 | 4 | 5 | 2 |
\(\tau _3\)
| 9 | 2 | 2 | 3 | 8 | 3 |
\(\tau _4\)
| 11 | 2 | 1 | 3 | 8 | 3 |
5.3 Determining the tasks that can execute and are affected by \(\tau _j\)
5.4 Determining the number of job activations “ \(\#\)-jobs”
5.4.1 \(\#\)-jobs for \([0,H_i)\)
5.4.2 \(\#\)-jobs for \([0,L_i),[0,S_{i,k})\), and \([0,F_{i,k})\) when \(B_i \ne 0\)
5.4.3 \(\#\)-jobs for \([0,L_i),[0,S_{i,k})\), and \([0,F_{i,k})\) when \(B_i = 0\)
5.5 Identifying the task causing the largest blocking delay
5.6 Termination of the iterative procedure for \(L_i\)
5.7 Applying the results
-
apply the notion of worst-case hold time by using \(E_j(H_h)\) rather than \(E_j(R_h)\) to tighten the number of times that \(\tau _j\) may pre-empt a job of \(\tau _h\) for approaches considering pre-empted tasks. This influences the definition of the multiset \(M_{i,j}\) for the UCB-Only Multiset approach, the ECB-Union Multiset approach, and the UCB-Union Multiset approach.
-
apply the derived “affected by \(\tau _j\)” information in the definitions of \(\gamma _{i,j}\) and \(M_{i,j}\) for the various approaches. This requires an extension of the subscripts of \(S_{i,k}\), \(F_{i,k},\gamma _{i,j}\) and \(M_{i,j}\) with b for those cases where a task \(\tau _b\) may block a task \(\tau _i\).
-
apply the derived “\(\#\)-jobs” information for approaches considering pre-empted tasks. This requires a case distinction following the information in Table 2 in the definition of the multiset \(M_{i,j}\). Moreover, it requires a further extension of the subscripts of \(\gamma _{i,j}\) and \(M_{i,j}\) with k, and the introduction of an additional parameter for both \(\gamma _{i,j}\) and \(M_{i,j}\) to cater for the pre-emptions in the intervals corresponding to the worst-case start-time and the worst-case finalization time.
-
take the maximum value over all tasks that may block \(\tau _i\) to determine \(L_i\) and \(F_{i,k}\), when \(\tau _i\) can be blocked.
6 FPTS with CRPD: pre-empting tasks
6.1 Worst-case length \(L_i\)
6.2 Worst-case start time \(S_{i,k}\)
6.3 Worst-case finalization time \(F_{i,k}\)
7 FPTS with CRPD: pre-empted tasks
7.1 Worst-case hold time \(H_i\)
7.2 Worst-case length \(L_i\)
7.3 Worst-case start time \(S_{i,k}\)
7.4 Worst-case finishing time \(F_{i,k}\)
8 FPTS with CRPD: pre-empting and pre-empted tasks
8.1 ECB-Union Multiset approach
8.2 UCB-Union Multiset approach
8.3 Composite approach
9 An optimal threshold assignment algorithm
9.1 Algorithm description
9.2 Correctness and proof of OTA algorithm
9.3 Algorithmic complexity
10 Layout of tasks in memory
10.1 Influence of task layout on CRPD
10.2 Determining ECBs and UCBs for a given task layout
10.3 An algorithm to search for a schedulable task layout
10.4 Algorithmic complexity
10.5 Instantiating the algorithm
11 Evaluation
-
those in Lunniss et al. (2012) using the algorithm searching for a schedulable layout of tasks in memory.
11.1 Experimental setup
11.2 Task-sets’ utilization
11.2.1 CRPD approaches and deadline types
11.2.2 Schedulable task-layout search (STLS) algorithm
Scheduling algorithm | Weighted schedulability ratio | Notation | ||
---|---|---|---|---|
Constrained | Implicit | Arbitrary | ||
FPTS with CRPD (layout search) | 0.762431 | 0.857890 | 0.974838 |
\(W_{\mathrm{FPTS}_\mathrm{LS}}\)
|
FPTS with CRPD (initial layout) | 0.711737 | 0.818222 | 0.948140 |
\(W_{\mathrm{FPTS}_\mathrm{IL}}\)
|
FPPS with CRPD (layout search) | 0.647439 | 0.724327 | 0.792571 |
\(W_{\mathrm{FPPS}_\mathrm{LS}}\)
|
FPPS with CRPD (initial layout) | 0.593637 | 0.644919 | 0.722304 |
\(W_{\mathrm{FPPS}_\mathrm{IL}}\)
|
# | Metric | Weighted schedulability ratio | ||
---|---|---|---|---|
Constrained | Implicit | Arbitrary | ||
1 | Layout search with FPPS | 0.09 | 0.12 | 0.10 |
2 | Layout search with FPTS | 0.07 | 0.05 | 0.03 |
3 | FPTS instead of FPPS with initial layout | 0.20 | 0.27 | 0.31 |
4 | FPTS instead of FPPS with layout search | 0.18 | 0.18 | 0.23 |
5 | Both FPTS and layout search over FPPS | 0.28 | 0.33 | 0.35 |