Why can no task have a utilization rate greater than one?

Question

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?

Answer 1

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.