RMスケジューリング 各タスクのジョブのリリース周期（

Presentation on theme: "RMスケジューリング 各タスクのジョブのリリース周期（ "— Presentation transcript:

1 RMスケジューリング 各タスクのジョブのリリース周期（ 𝑇 𝑖 ）と相対デッドライン（ 𝐷 𝑖 ）が等しいことが前提
周期の短いタスクに高い優先度を与える あるタスクを実行中に、より優先度の高い（ジョブのリリース周期の短い）タスクのジョブがリリースされるとプリエンプションが発生 例題 𝜏 1 = 6,2,6 , 𝜏 2 = 5,1,5 , 𝜏 3 = 10,4,10 からなるタスク集合のRMスケジューリングについて、以下の問いに答えよ。 優先度の高い順にタスクを並べ替えよ このタスク集合のハイパー周期を求めよ ゼロフェージングを仮定した場合、1ハイパー周期中の各タスクのそれぞれのジョブの応答時間を求めよ さらに、その間にプリエンプションが発生しているならば、発生時刻をすべて求めよ　

2 例題の解答 (1) 𝜏 2 , 𝜏 1 , 𝜏 3 の順 (2) ハイパー周期は 𝐿𝐶𝑀 6,5,10 =30
(1) 𝜏 2 , 𝜏 1 , 𝜏 3 の順 (2) ハイパー周期は 𝐿𝐶𝑀 6,5,10 =30 時刻30までのスケジュール図を描画してみると (3) 𝜏 2 : 全部1, 𝜏 1 : 3, 2, 2, 2, 3 𝜏 3 : 10, 8, 8 (4) プリエンプションは時刻 5, 12, 15, 24, 25に発生　 𝜏 2 𝜏 1 𝜏 3 10 20 30

3 2013年　問題3 プリエン プション 10 20 30 30 40 50 60

4 DLMスケジューリング 各タスクのジョブのリリース周期（ 𝑇 𝑖 ）と相対デッドライン（ 𝐷 𝑖 ）が等しいことを前提としない（ 𝑇 𝑖 ≥ 𝐷 𝑖 ≥ 𝐶 𝑖 ） 相対デッドラインの短いタスクに高い優先度を与える あるタスクを実行中に、より優先度の高い（相対デッドラインの短い）タスクのジョブがリリースされるとプリエンプションが発生

5 DLMスケジューリング可能性 定理2.4 T ={𝜏1, 𝜏2, …, 𝜏𝑛} は優先度順に整列済を仮定して 各1≤𝑖≤𝑛に対して
min 𝑡∈ 𝑆 𝑖 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖 𝑡 𝑡 ≤1 が成り立つとき、かつそのときのみT はDLMスケジューリング可能である（必要十分条件）。 ただし、 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖 𝑡 : 0,𝑡 でリリースされた 𝜏 1 から 𝜏 𝑖 のジョブの仕事量の和 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖 𝑡 = 𝑗=1 𝑖 𝑡 𝑇 𝑗 × 𝐶 𝑗 𝑆 𝑖 : タスク 𝜏 𝑖 のスケジューリングポイントの集合 𝑆 𝑖 = 𝑗=1 𝑖 𝑘× 𝑇 𝑗 | 𝑘∈N , 𝑘× 𝑇 𝑗 ≤ 𝐷 𝑖 ∪{ 𝐷 𝑖 }

6 DLMスケジューリング可能性 定理2.4 T ={𝜏1, 𝜏2, …, 𝜏𝑛} は優先度順に整列済を仮定して 各1≤𝑖≤𝑛に対して
min 𝑡∈ 𝑆 𝑖 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖 𝑡 𝑡 ≤1 が成り立つとき、かつそのときのみT はDLMスケジューリング可能である（必要十分条件）。 ただし、 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖 𝑡 : 0,𝑡 でリリースされた 𝜏 1 から 𝜏 𝑖 のジョブの仕事量の和 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖 𝑡 = 𝑗=1 𝑖 𝑡 𝑇 𝑗 × 𝐶 𝑗 𝑆 𝑖 : タスク 𝜏 𝑖 のスケジューリングポイントの集合 𝑆 𝑖 = 𝑗=1 𝑖 𝑘× 𝑇 𝑗 | 𝑘∈N , 𝑘× 𝑇 𝑗 ≤ 𝐷 𝑖 ∪{ 𝐷 𝑖 } 何箇所かのスケジューリングポイントのどこかで 　（自分以上の優先度のタスクのジョブの仕事量）≦（経過時間） が成り立てばよい

7 DLMスケジューリング可能性（例題1） 例題1 𝜏 1 = 5,1,4 , 𝜏 2 = 6,2,5 , 𝜏 3 = 15,5,13 からなるタスク集合のDLMスケジュール可能性を以下の手順により定理2.4を用いて判定せよ。 　𝑖=1~3について (a) 𝑆 𝑖 を求める (b) min 𝑡∈ 𝑆 𝑖 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 𝑖 (𝑡) 𝑡 ≤1の成立を確認する 𝑖=1について 𝑆 1 = 4 , 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 1 (4) 4 = 1 4 ≤1 𝑖=2について 𝑆 2 = 5 , 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 2 (5) 5 = 3 5 ≤1 𝑖=3について 𝑆 3 = 𝑘× 𝑇 1 𝑘× 𝑇 1 ≤ 𝐷 3 ∪ 𝑘× 𝑇 2 𝑘× 𝑇 2 ≤ 𝐷 3 ∪{ 𝐷 3 } = 5,10 ∪ 6,12 ∪ 13 ={5,6,10,12,13} OK OK

8 DLMスケジューリング可能性（例題1） 例題1 𝜏 1 = 5,1,4 , 𝜏 2 = 6,2,5 , 𝜏 3 = 15,5,13 からなるタスク集合のDLMスケジュール可能性を以下の手順により定理2.4を用いて判定せよ。 𝑆 3 5 6 10 12 13 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 3 8 9 11 12 12 14 min 𝑡∈ 𝑆 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 3 (𝑡) 𝑡 = 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 =1≤1 OK

9 DLMスケジューリング（例題２） 例題2 𝜏 1 = 4,1,3 , 𝜏 2 = 6,2,5 , 𝜏 3 = 15,6,13 の場合
例題2 𝜏 1 = 4,1,3 , 𝜏 2 = 6,2,5 , 𝜏 3 = 15,6,13 の場合 𝑆 1 = 3 𝑆 2 = 4, 5 𝑆 3 = 𝑘× 𝑇 1 𝑘× 𝑇 1 ≤ 𝐷 3 ∪ 𝑘× 𝑇 2 𝑘× 𝑇 2 ≤ 𝐷 3 ∪{ 𝐷 3 } = 4,8,12 ∪ 6,12 ∪ 13 ={4,6,8,12,13} 𝑆 𝑖 3 4 5 6 8 12 13 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 1 1 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 2 3 4 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑 3 9 10 12 13 16

10 アーリーデッドラインファースト(EDF)スケジューリング
絶対デッドラインが最も近いジョブを持つタスクに最高の優先度を与える動的優先度のスケジューリング (4,1,3) (6,2,5) (15,6,13)

11 EDFスケジューリングの性質 定理3.1 𝐷 𝑖 = 𝑇 𝑖 の場合過負荷でないタスク集合はスケジュール可能 定理3.2
タスク集合T = 𝜏 1 , …, 𝜏 𝑛 は max 𝑡∈𝑆 𝐷𝑒𝑚𝑎𝑛𝑑(𝑡) 𝑡 ≤1 であるときかつそのときのみEDFスケジューリング可能 ただし 𝑆: ハイパー周期内のデッドライン時刻の集合 𝐷𝑒𝑚𝑎𝑛𝑑(𝑡): 時刻 𝑡 までにデッドラインを迎える ジョブの仕事量の和

12 EDFスケジューリング DemandはSPを超えないのでOK
𝜏 1 = 4,1,3 , 𝜏 2 = 6,2,5 , 𝜏 3 = 15,6,13 の場合 ハイパー周期は𝐿𝐶𝑀 4,6,15 =60なので 𝑆= 3,7,11,15,19,23,27,31,35,59,43,47,51,55,59 ∪ 5,11,17,23,29,35,41,47,53,59 ∪{13,28,43,58} SP 3 5 7 11 13 15 17 19 23 27 28 Demand 1 4 14 16 20 21 29 31 35 39 41 43 47 51 53 55 58 59 30 33 34 36 46 49 50 DemandはSPを超えないのでOK