algorithm - 调度:隐式期限率单调算法的提前期限

Question

给定一组任务:

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

现在我想将截止日期限制为 Di = f * Pi 其中 Di 是第 i 个任务的新截止日期，Pi 是原始截止日期第 i 个任务的周期和 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 .