Then U must be less or equal to 1 for the task to be schedulable Proof: Let T^ b
ID: 647143 • Letter: T
Question
Then U must be less or equal to 1 for the task to be schedulable
Proof:
Let T^ be the lcm of task T1,...Tn i.e. T^=?i>Ti. Define L^i=T^/Ti the number of times the task is run. Then the total number of execution is ?iCi/L^i=?iCiT^Ti. Suppose utilization rate U>1, then ?iCiT^Ti>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 Ti? It would make more sense if it was the sum of all the Ti which represents the total task period.
Second, ?iCi/L^i represents the total time spent on execution, I do not get how if this time is larger than T^, then the tasks would not be schedulable. This goes back to my misunderstanding of what T^ is.
Can anyone help?
Let Ci be the execution time for task i, Ti be the task period and utilization rate U=CiTi Then U must be less or equal to 1 for the task to be schedulable Proof: Let T^ be the lcm of task T1,...Tn i.e. T^=?i>Ti. Define L^i=T^/Ti the number of times the task is run. Then the total number of execution is ?iCi/L^i=?iCiT^Ti. Suppose utilization rate U>1, then ?iCiT^Ti>T^ which is impossible. End of proof. what is the physical quantity representing the product or lcm of all the task periods Ti? It would make more sense if it was the sum of all the Ti which represents the total task period. Second, ?iCi/L^i represents the total time spent on execution, I do not get how if this time is larger than T^, then the tasks would not be schedulable. This goes back to my misunderstanding of what T^ is. Can anyone help?Explanation / Answer
It appears that you have a periodic scheduling system on a single processor where task i must run for Ci seconds out of every Ti.
If this is the case, then the requirement that CiTi?1 is just saying that Ci?Ti, 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 Ui=CiTi, then define the total utilization to be U=?ni=1Ui and then require the stronger condition that this U satisfies U?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 p1% of my time on task 1, ..., and pn% of my time on task n, I'd better not be committing more than 100% of my time!
The physical significant of defining T^=lcm(T1,
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.