RTS10_verslagen/report-2/week_1.6.md

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.