Demand値を求める数式

Presentation on theme: "Demand値を求める数式 "— Presentation transcript:

1 Demand値を求める数式 𝐷𝑒𝑚𝑎𝑛𝑑 𝑡 = 𝑖=1 𝑛 {(1+ 𝑡− 𝐷 𝑖 𝑇 𝑖 )× 𝐶 𝑖 }
𝐷𝑒𝑚𝑎𝑛𝑑 𝑡 = 𝑖=1 𝑛 {(1+ 𝑡− 𝐷 𝑖 𝑇 𝑖 )× 𝐶 𝑖 } タスク 𝜏 𝑖 の時刻𝑡までのデッドライン数 　𝑡< 𝐷 𝑖 : 0 　 𝐷 𝑖 ≤𝑡< 𝑇 𝑖 + 𝐷 𝑖 : 1 　 𝑇 𝑖 + 𝐷 𝑖 ≤𝑡< 2𝑇 𝑖 + 𝐷 𝑖 : 2

2 3. 固定優先度のスケジューリング 前提条件 ・ハードリアルタイムシステム ・周期的タスクのみ ・プリエンプション可能 ・単一プロセッサ
　・ハードリアルタイムシステム 　・周期的タスクのみ 　・プリエンプション可能 　・単一プロセッサ 　・オフラインスケジューリング 　・各タスクの優先度は固定

3 ランダムなスケジューリング 𝜏 1 = 6,1,5 , 𝜏 2 = 12,3,7 , 𝜏 3 = (12,6,10) 𝜏1 𝜏2 𝜏3
𝜏 1 = 6,1,5 , 𝜏 2 = 12,3,7 , 𝜏 3 = (12,6,10) 𝜏1 𝜏2 𝜏3 𝜏 3 から実行するとデッドライン違反が発生

4 EDFスケジューリング 𝜏 1 = 6,1,5 , 𝜏 2 = 12,3,7 , 𝜏 3 = (12,6,10) 𝜏1 𝜏2 𝜏3
𝜏 1 = 6,1,5 , 𝜏 2 = 12,3,7 , 𝜏 3 = (12,6,10) OK OK 𝜏1 OK 𝜏2 OK 𝜏3 EDFでスケジュールするとうまくいった

5 DLMスケジューリング 𝜏 1 = 6,1,5 , 𝜏 2 = 12,3,7 , 𝜏 3 = (12,6,10) 高 𝜏1 中 𝜏2 低
𝜏 1 = 6,1,5 , 𝜏 2 = 12,3,7 , 𝜏 3 = (12,6,10) 高 中 低 OK 𝜏1 OK 𝜏2 OK 𝜏3 優先度固定 ここまではEDFといっしょ

6 DLMスケジューリング 𝜏 1 = 6,1,5 , 𝜏 2 = 12,3,7 , 𝜏 3 = (12,6,10) 高 𝜏1 横取り 中 𝜏2
𝜏 1 = 6,1,5 , 𝜏 2 = 12,3,7 , 𝜏 3 = (12,6,10) 高 中 低 OK OK 𝜏1 横取り OK 𝜏2 𝜏3 優先度固定 残念ながらEDFのようにはいかなかった

7 DLMスケジューリング 𝜏 1 = 6,1,5 , 𝜏 2 = 12,3,7 , 𝜏 3 = (12,6,11) 高 𝜏1 横取り 中 𝜏2
𝜏 1 = 6,1,5 , 𝜏 2 = 12,3,7 , 𝜏 3 = (12,6,11) 高 中 低 OK OK 𝜏1 横取り OK 𝜏2 OK 𝜏3 優先度固定 𝜏 3 の（相対）デッドラインが11ならなんとかなった

8 DLMスケジューリング 𝜏1 = 3,1,2 , 𝜏2= 8,2,7 , 𝜏3 = (11,4,10) 𝜏1 𝜏2 失敗する場合
𝜏1 = 3,1,2 , 𝜏2= 8,2,7 , 𝜏3 = (11,4,10) 𝜏1 OK OK OK OK 𝜏2 OK 失敗する場合 最初のジョブで 𝜏3　

9 DLMスケジューリング 𝜏1 = 3,1,2 , 𝜏2= 8,2,7 , 𝜏3 = (10,3,8) 𝜏1 𝜏2 𝜏3 これで 大丈夫 OK
𝜏1 = 3,1,2 , 𝜏2= 8,2,7 , 𝜏3 = (10,3,8) 𝜏1 OK OK OK 𝜏2 OK これで 大丈夫 二つ目は レスポンスが 良くなった 𝜏3　 OK

10 DLMスケジューリング図の描画手順 𝜏 1 = 3,1,2 , 𝜏 2 = 8,2,7 , 𝜏 3 = 10,3,8 , 𝜏 4 =(20,1,20) 最長DL外 𝜏1 OK

11 DLMスケジューリング図の描画手順 𝜏 1 = 3,1,2 , 𝜏 2 = 8,2,7 , 𝜏 3 = 10,3,8 , 𝜏 4 =(20,1,20) 最長DL外 𝜏1 OK 𝜏2 OK

12 DLMスケジューリング図の描画手順 𝜏 1 = 3,1,2 , 𝜏 2 = 8,2,7 , 𝜏 3 = 10,3,8 , 𝜏 4 =(20,1,20) 最長DL外 𝜏1 OK 𝜏2 OK 𝜏3　 OK

13 DLMスケジューリング図の描画手順 𝜏 1 = 3,1,2 , 𝜏 2 = 8,2,7 , 𝜏 3 = 10,3,8 , 𝜏 4 =(20,1,20) 最長DL外 𝜏1 OK 𝜏2 OK 𝜏3　 OK 𝜏4　 OK

14 描画手順を定式化し定理化 しばらく板書します

15 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖−1 (𝑡) と𝐽𝑖1の関係 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖 𝑡 = 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖−1 𝑡 + 𝐶 𝑖
- タスク 𝜏 𝑖 の最初のジョブ 𝐽 𝑖 1 は時刻 0 にリリースされる - 0,𝑡 で 𝜏 1 ~ 𝜏 𝑖−1 の処理時間は高々（すべてが完了してる場合） 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖−1 (𝑡) 0,𝑡 で、 𝐽 𝑖 1 は少なくとも 𝑡− 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖−1 (𝑡) 時間、処理をうけることができ、 𝐶 𝑖 ≤𝑡− 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖−1 𝑡 ならば完了しているはず 𝐶 𝑖 ≤𝑡− 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖−1 (𝑡) を満たす 𝑡 0≤𝑡≤ 𝐷 𝑖 が存在すれば 𝐽 𝑖 1 は時刻 𝑡 までに完了しているはず 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖 𝑡 = 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖−1 𝑡 + 𝐶 𝑖 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖 𝑡 ≤𝑡

16 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑の概形（𝑖=3の場合） 𝐶1 𝐶2 𝐶1 𝐶2 𝐶1 𝐶 1 + 𝐶 2 + 𝐶 3 𝑇 1 𝑇 2 2𝑇 1 2𝑇 2
𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑(𝑡) 𝐶1 𝐶2 𝐶1 𝐶2 𝐶1 𝐶 1 + 𝐶 2 + 𝐶 3 𝑇 1 𝑇 2 2𝑇 1 2𝑇 2 3𝑇 1 𝐷 3

17 例1 𝜏 1 = 100,40,80 , 𝜏 2 = 150,40,140 , 𝜏 3 =(350,100,330) 𝑆 1 = 80 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 =40≤80 𝑆 2 = 100 ∪ 140 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 =40+40=80≤100 𝑆 3 = 100,200,300 ∪ 150,300 ∪ 330 ={100,150,200,300,330} 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 = =180>100 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 =40× =220>150 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 =40×2+40×2+100=260>200 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 =40×3+40×2+100=300≤300 スケジュール可

18 例2 𝜏 1 = 100,40,80 , 𝜏 2 = 150,40,140 , 𝜏 3 =(350,101,330) 𝑆 1 = 80 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 =40≤80 𝑆 2 = 100 ∪ 140 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 =40+40=80≤100 𝑆 3 = 100,200,300 ∪ 150,300 ∪ 330 ={100,150,200,300,330} 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 = =181>100 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 =40× =221>150 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 =40×2+40×2+101=261>200 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 =40×3+40×2+101=301>300 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 =40×4+40×3+101=381>330 スケジュール不可

19 Demand値とWorkLoad値 𝜏 1 = 3,1,2 , 𝜏 2 = 8,1,6 , 𝜏 3 = (10,5,9) 𝜏 1 𝜏 2
𝜏 1 = 3,1,2 , 𝜏 2 = 8,1,6 , 𝜏 3 = (10,5,9) 𝜏 1 𝜏 2 𝜏 3 1 2 3 4 9 Demand 7 8 9 10 11 Work Load 16

20 レートモノトニックスケジューリング 周期の短いタスクに高い優先度を付与 レート（ジョブの発生率）： 周期の逆数（ 1 𝑇 𝑖 ）
レート（ジョブの発生率）：　周期の逆数（ 1 𝑇 𝑖 ） 𝑇𝑖 < 𝑇𝑗 ⇒ 𝑝𝑖 > 𝑝𝑗 優先度 レート

21 レートモノトニックスケジューリング 𝜏1 = 3,1,3 , 𝜏2= 8,1,8 , 𝜏3 = (10,4,10) 𝜏1 𝜏2 𝜏3
𝜏1 = 3,1,3 , 　𝜏2= 8,1,8 , 　𝜏3 = (10,4,10) 𝜏1 高優先度 𝜏2 中優先度 𝜏3 低優先度

22 プロセッサ利用率 個々のタスクの利用率 𝑈= 𝑖=1 𝑛 𝐶 𝑖 𝑇 𝑖
𝑈= 𝑖=1 𝑛 𝐶 𝑖 𝑇 𝑖 ・𝜏1 = (3,1,3)、𝜏2= (4,1,4)、𝜏3 = (10,5,10) の場合 𝑈 = = = 65 60 過負荷のためスケジューリング不可能 ・𝜏1 = (3,1,3)、𝜏2= (8,1,8)、𝜏3 = (10,3,10) の場合 𝑈 = = = = 0.758 過負荷ではない でも本当にスケジューリングできるかは不明

23 RMスケジューリングのプロセッサ利用率 タスク数 1 2 3 4 5 𝑛( 2 1 𝑛 －1) 1.000 0.828 0.780
𝑛( 2 1 𝑛 －1) 1.000 0.828 0.780 0.757 0.743 タスク数 6 7 8 9 ∞ 𝑛( 2 1 𝑛 －1) 0.735 0.729 0.724 0.721 0.693

24 プロセッサ利用率 個々のタスクの利用率 𝑈= 𝑖=1 𝑛 𝐶 𝑖 𝑇 𝑖
𝑈= 𝑖=1 𝑛 𝐶 𝑖 𝑇 𝑖 ・𝜏1 = (3,1,3)、𝜏2= (4,1,4)、𝜏3 = (10,5,10) の場合 𝑈 = = = 65 60 過負荷のためスケジューリング不可能 ・𝜏1 = (3,1,3)、𝜏2= (8,1,8)、𝜏3 = (10,3,10) の場合 𝑈 = = = = 0.758 過負荷ではない でも本当にスケジューリングできるかは不明 定理3.2より　𝑛=3のとき 𝑛( 2 1 𝑛 －1)=0.780なのでＯＫ

25 レートモノトニックスケジューリング 𝜏1 𝜏2 𝜏3 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 3 190 =2×30+2×60+11=191>190
𝜏1 = 100,30,100 , 𝜏2= 130,60,130 , 𝜏3=(190,11,190) ⇒　𝑈=0.819 𝜏1 𝜏2 あと1 足りない 𝜏3　 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 =2×30+2×60+11=191>190

26 まとめ ・デッドラインモノトニック（DLM）スケジューリング 相対デッドライン（𝐷𝑖）の短いタスクに高い優先度
𝑆 𝑖 のいずれかで 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖 (𝑡)≤𝑡 ・レートモノトニック(RM)スケジューリング 𝐷 𝑖 = 𝑇 𝑖 の場合のDLMスケジューリング ・RMスケジュール可能性の十分条件（定理3.2） 𝑈≤𝑛( 2 1 𝑛 −1)