0
$\begingroup$

enter image description here Let $C_i$ be the execution time for task i, $T_i$ be the task period and utilization rate $U = \frac{C_i}{T_i}$

Then $U$ must be less or equal to $1$ for the task to be schedulable

Proof:

Let $\hat T$ be the lcm of task $T_1,...T_n$ i.e. $\hat T = \prod_i > T_i$. Define $\hat L_i = \hat T/T_i$ the number of times the task is run. Then the total number of execution is $\sum_i C_i/\hat L_i = \sum_i \frac{C_i \hat T} {T_i}$. Suppose utilization rate $U >1$, then $\sum_i \frac{C_i \hat T} {T_i} > \hat T$ which is impossible. End of proof.

I am confused about several things in the proof.

First, what is the physical quantity representing the product or lcm of all the task periods $T_i$? It would make more sense if it was the sum of all the $T_i$ which represents the total task period.

Second, $\sum_i C_i/\hat L_i$ represents the total time spent on execution, I do not get how if this time is larger than $\hat T$, then the tasks would not be schedulable. This goes back to my misunderstanding of what $\hat T$ is.

Can anyone help?

$\endgroup$
  • $\begingroup$ Note that the truth of that statement depends on the exact scheduling problem at hand. (IIRC, there are variants in which $U > 1$ is possible, but still $U \leq m$.) Please check the definition of $U$; as it stands it does not seem to make sense of fit the proof. Shouldn't it depend on $i$? Did you miss some operator there? $\endgroup$ – Raphael Mar 23 '15 at 6:30
2
$\begingroup$

It appears that you have a periodic scheduling system on a single processor where task $i$ must run for $C_i$ seconds out of every $T_i$.

If this is the case, then the requirement that $\tfrac{C_i}{T_i}\le1$ is just saying that $C_i\le T_i$, i.e., you're not saying something like "Task 3 must run for 15 seconds out of every 10 seconds", which is physically impossible.

It looks like there's actually a mistake in the statement of the theorem. I think it should say that the utilization of task $i$ is given by $U_i=\tfrac{C_i}{T_i}$, then define the total utilization to be $U = \sum_{i=1}^n U_i$ and then require the stronger condition that this $U$ satisfies $U\leq 1$. That is, you don't just require each task individually to use at most 100% of your resources: you require the whole ensemble to use at most 100%. You can think of it this way: if I'm supposed to spend $p_1\%$ of my time on task 1, ..., and $p_n\%$ of my time on task $n$, I'd better not be committing more than 100% of my time!

The physical significant of defining $\hat{T} = \mathrm{lcm}(T_1, \dots, T_n)$ is that it's the shortest period of time in which every task is supposed to run an integer number of times. It's not essential that you consider the shortest such period: the proof would work fine if you used any period in which every task needs to run an integer number of times. Perhaps it would be conceptually easier to set $\hat{T} = \prod_{i=1}^n T_i$ instead.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.