138 lines
5.1 KiB
Markdown
138 lines
5.1 KiB
Markdown
|
||
# Week 1.6
|
||
|
||
## Assginment 6.1
|
||
|
||
> A program consists of four tasks, $T_1$ through $T_4$. These tasks do not use shared resources. In the table, $i$ represents the task number, $T_i$ represents the period of task , and $C_i$ represents the maximum execution time of task $i$. The deadline of each task is equal to it's period.
|
||
>
|
||
> | i | $T_i$ | $C_i$ |
|
||
> |---|---------|--------|
|
||
> | 1 | $100ms$ | $50ms$ |
|
||
> | 2 | $280ms$ | $45ms$ |
|
||
> | 3 | $200ms$ | $20ms$ |
|
||
> | 4 | $300ms$ | $40ms$ |
|
||
>
|
||
> A) Determine the schedulability of these tasks using the "Utilization based schedulability test" Provide the necessary calculations and draw your conclusions.
|
||
|
||
$$
|
||
U=\sum_{i=1}^N{\frac{C_i}{T_i}}\le N(2^{1/N}-1)
|
||
$$
|
||
|
||
$$
|
||
U=\frac{C_1}{T_1}+\frac{C_2}{T_2}+\frac{C_3}{T_3}+\frac{C_4}{T_4}\le 4\cdot(2^{1/4}-1)
|
||
$$
|
||
|
||
$$
|
||
U=\frac{0.05}{0.1}+\frac{0.045}{0.28}+\frac{0.02}{0.2}+\frac{0.04}{0.3}\le N(2^{1/4}-1)
|
||
$$
|
||
|
||
$$
|
||
U=0.894047619048\le0.756828460011=false
|
||
$$
|
||
|
||
This equetion cannot say if all the deadline are possible to make in this case.
|
||
|
||
> B) Determine the priorities $P_i$ of the various tasks when using FPS-RMPA (Fixed-priority Preemptive Scheduling – Rate Monotonic Priority Assignment). The system has four different priorities (1 through 4), with 4 being the highest.
|
||
|
||
The task with the shortest deadline should get the highest priority. The deadline are equal to $T_i$, this result in the following priorities:
|
||
|
||
| i | $T_i$ | $C_i$ | $P_i$ |
|
||
| --- | ------- | ------ | ----- |
|
||
| 1 | $100ms$ | $50ms$ | 4 |
|
||
| 2 | $280ms$ | $45ms$ | 2 |
|
||
| 3 | $200ms$ | $20ms$ | 3 |
|
||
| 4 | $300ms$ | $40ms$ | 1 |
|
||
|
||
> C) Calculate for all tasks whether the deadline will be met, and if the deadline is met, provide the response time $R_i$.
|
||
|
||
$$
|
||
R_i=C_i+\sum_{j∈hp(i)}{\left\lceil \frac{R_i}{T_j} \right\rceil} C_j
|
||
$$
|
||
|
||
$$
|
||
R_1=C_1+\sum_{j∈hp(1)}{\left\lceil \frac{R_1}{T_j} \right\rceil} C_j=C_1=50ms
|
||
$$
|
||
|
||
$$
|
||
R_3=C_3+\sum_{j∈hp(3)}{\left\lceil \frac{R_3}{T_j} \right\rceil} C_j=C_3+\left\lceil \frac{R_3}{T_1} \right\rceil C_1
|
||
$$
|
||
$$
|
||
\Rightarrow w_{3,1}=C_3+\left\lceil \frac{C_3}{T_1} \right\rceil C_1=0.02+\left\lceil \frac{0.02}{0.1} \right\rceil 0.05=0.07
|
||
$$
|
||
$$
|
||
\rightarrow w_{3,2}=C_3+\left\lceil \frac{w_{3,1}}{T_1} \right\rceil C_1=0.02+\left\lceil \frac{0.02}{0.1} \right\rceil 0.05=0.07
|
||
$$
|
||
$$
|
||
R_3=70ms
|
||
$$
|
||
$w_{3,2}$ is the same as $w_{3,1}$ so $R_3$ is equal to both. This is lower then $T_3$ ($200ms$) so this is still possible.
|
||
|
||
|
||
$$
|
||
R_2=C_2+\sum_{j∈hp(2)}{\left\lceil \frac{R_2}{T_j} \right\rceil C_j}=C_2+\left\lceil \frac{R_2}{T_1} \right\rceil C_1+\left\lceil \frac{R_2}{T_3} \right\rceil C_3
|
||
$$
|
||
$$
|
||
\Rightarrow w_{2,1}=C_2+\left\lceil \frac{C_2}{T_1} \right\rceil C_1+\left\lceil \frac{C_2}{T_3} \right\rceil C_3=0.045+\left\lceil \frac{0.045}{0.1} \right\rceil 0.05+\left\lceil \frac{0.045}{0.2} \right\rceil 0.02=0.115
|
||
$$
|
||
$$
|
||
\Rightarrow w_{2,2}=C_2+\left\lceil \frac{w_{2,1}}{T_1} \right\rceil C_1+\left\lceil \frac{w_{2,1}}{T_3} \right\rceil C_3=0.045+\left\lceil \frac{0.115}{0.1} \right\rceil 0.05+\left\lceil \frac{0.115}{0.2} \right\rceil 0.02=0.165
|
||
$$
|
||
$$
|
||
\Rightarrow w_{2,3}=C_2+\left\lceil \frac{w_{2,2}}{T_1} \right\rceil C_1+\left\lceil \frac{w_{2,2}}{T_3} \right\rceil C_3
|
||
=0.045+\left\lceil \frac{0.165}{0.1} \right\rceil 0.05+\left\lceil \frac{0.165}{0.2} \right\rceil 0.02=0.165
|
||
$$
|
||
$$
|
||
R_2=165ms
|
||
$$
|
||
|
||
$w_{2,2}$ is the same as $w_{2,1}$ so $R_2$ is equal to both. This is lower then $T_2$ ($280ms$) so this is still possible.
|
||
|
||
$$
|
||
R_4=C_4+\sum_{j∈hp(4)}{\left\lceil \frac{R_4}{T_j} \right\rceil C_j}=C_4+\left\lceil \frac{R_4}{T_1} \right\rceil C_1+\left\lceil \frac{R_4}{T_3} \right\rceil C_3+\left\lceil \frac{R_4}{T_2} \right\rceil C_2
|
||
$$
|
||
$$
|
||
\Rightarrow w_{4,1}=
|
||
C_4+\left\lceil \frac{C_4}{T_1} \right\rceil C_1
|
||
+\left\lceil \frac{C_4}{T_3} \right\rceil C_3
|
||
+\left\lceil \frac{C_4}{T_2} \right\rceil C_2
|
||
=0.04+\left\lceil \frac{0.04}{0.1} \right\rceil 0.05
|
||
+\left\lceil \frac{0.04}{0.2} \right\rceil 0.02
|
||
+\left\lceil \frac{0.04}{0.28} \right\rceil 0.045
|
||
=0.155
|
||
$$
|
||
$$
|
||
\Rightarrow w_{4,2}=
|
||
C_4+\left\lceil \frac{w_{4,1}}{T_1} \right\rceil C_1
|
||
+\left\lceil \frac{w_{4,1}}{T_3} \right\rceil C_3
|
||
+\left\lceil \frac{w_{4,1}}{T_2} \right\rceil C_2
|
||
=0.04+\left\lceil \frac{0.155}{0.1} \right\rceil 0.05
|
||
+\left\lceil \frac{0.155}{0.2} \right\rceil 0.02
|
||
+\left\lceil \frac{0.155}{0.28} \right\rceil 0.045
|
||
=0.205
|
||
$$
|
||
$$
|
||
\Rightarrow w_{4,3}=
|
||
C_4+\left\lceil \frac{w_{4,2}}{T_1} \right\rceil C_1
|
||
+\left\lceil \frac{w_{4,2}}{T_3} \right\rceil C_3
|
||
+\left\lceil \frac{w_{4,2}}{T_2} \right\rceil C_2
|
||
=0.04+\left\lceil \frac{0.205}{0.1} \right\rceil 0.05
|
||
+\left\lceil \frac{0.205}{0.2} \right\rceil 0.02
|
||
+\left\lceil \frac{0.205}{0.28} \right\rceil 0.045
|
||
=0.275
|
||
$$
|
||
$$
|
||
\Rightarrow w_{4,4}=
|
||
C_4+\left\lceil \frac{w_{4,3}}{T_1} \right\rceil C_1
|
||
+\left\lceil \frac{w_{4,3}}{T_3} \right\rceil C_3
|
||
+\left\lceil \frac{w_{4,3}}{T_2} \right\rceil C_2
|
||
=0.04+\left\lceil \frac{0.275}{0.1} \right\rceil 0.05
|
||
+\left\lceil \frac{0.275}{0.2} \right\rceil 0.02
|
||
+\left\lceil \frac{0.275}{0.28} \right\rceil 0.045
|
||
=0.275
|
||
$$
|
||
$$
|
||
R_4=275ms
|
||
$$
|
||
|
||
$w_{4,3}$ is the same as $w_{4,4}$ so $R_4$ is equal to both. This is lower then $T_4$ ($300ms$) so FPS-RMPA will not miss any deadlines.
|