0

I am trying to prove Theorem 6.2 on page 127 of the book Real-Time Systems by Jane W. S. Liu:

http://www.cse.hcmut.edu.vn/~thai/books/2000%20_%20Liu-%20Real%20Time%20Systems.pdf

It is based on Early Deadline First(EDF) scheduling.

It says on the book that the proof is similar to the proof for Theorem 6.1 on page 124-126. However, I am still stuck.

Here is what I have so far:

enter image description here

Matt
  • 109
  • 3
  • This is not the right forum for this question. I would try stackoverflow.com or math.stackexchange.com – mhaselup Nov 03 '20 at 05:27
  • from a first look I noticed something that may be wrong in the sums indices. A sum index is bound not free. So how come you are using k =/= l while k is an index in a sum and l is an index in an independent sum? – Paul Ghobril Nov 03 '20 at 05:49
  • It is just showing the tasks in the three terms in 1st eq. are mutually exclusive – Matt Nov 03 '20 at 06:54
  • 1
    @mhaselup RTOS questions are on-topic here. – Lundin Nov 03 '20 at 07:18

1 Answers1

1

Yhe text you quote says it is only a sufficient condition not a necessary condition. If Δ>1 then that implies that t < tΔ + any positive number. Which is exactly what you've proved.

james
  • 1,662
  • 7
  • 12
  • No, it means that if its density(Δ) <= 1 then tasks can be feasibly scheduled, so density <= 1 is a sufficient condition for feasible scheduling. What I am proving is the contrapositive: if tasks CANNOT be feasibly scheduled(deadline(s) missed) then density > 1. – Matt Nov 04 '20 at 00:52
  • The second last sentence may be misleading. I changed it to "So I prove up to..." – Matt Nov 04 '20 at 01:27