0

一連のタスクが与えられた場合：

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

ここで、i番目のタスクの新しい期限は、i番目のタスクの元の期間であり、把握したい要素であるDi = f * Piため、期限を短縮したいと思います。タスクがレートモノトニックスケジューラを使用して期限を守り続けることの最小値はどれくらいですか？DiPiff

4

1 に答える 1

2

このスキーマは、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 時間単位ごとに繰り返され、完了するまでに同じ時間が必要です。

ちょっとした単純化: factor を計算するとき、期間-時間は相殺されます。これは、係数を取得するために期間を実際に計算する必要がないことを意味します。

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)で、 は最小公倍数です。

于 2012-09-30T10:42:34.060 に答える