調度：提前截止隱含截止日率單調算法

Question

給定一組任務：

T1(20,100) T2(30,250) T3(100,400) (execution time, deadline=peroid) 

現在我想以收縮期限爲Di = f * Pi其中Di是第i個任務的新的最後期限，Pi是原始時期對於ith任務和f是我想弄清楚的因素。什麼是f的最小值，這些任務將使用速率單調調度器繼續滿足其最後期限？

Answer 1

該模式將每隔2000個時間單位重複（同步）。在此期間

• T1必須運行20次，需要400個時間單位。
• T2必須運行8次，需要240個時間單位。
• T3必須運行5次，需要500個時間單位。

總計爲每2000個時間單位間隔1140個時間單位。

f = 1140/2000 = 0.57 

這假定長時間運行的任務可以被中斷和恢復，以允許短期運行的任務在兩者之間運行。否則，一旦T3開始，T1將無法滿足截止日期。

更新的截止日期爲：

T1(20,57) 
T2(30,142.5) 
T3(100,228) 

這些會重複每1851930個時間單位，而需要相同的時間才能完成。

---

小簡化：計算因子時，週期時間抵消。這意味着你並不真的需要計算週期，以獲得因素：

Period = 2000 
Required time = (Period/100) * 20 + (Period/250) * 30 + (Period/400) * 100 
f = Required time/Period = 20/100 + 30/250 + 100/400 = 0.57 

f = Sum(Duration[i]/Period[i]) 

---

爲計算週期，你可以這樣做：

Period(T1,T2) = lcm(100, 250) = 500 
Period(T1,T2,T3) = lcm(500, 400) = 2000 

其中lcm(x,y)是Least Common Multiple。