pptファイル

RMスケジューリング
• 各タスクのジョブのリリース周期（𝑇𝑖 ）と相対デッドライン（𝐷𝑖 ）が
等しいことが前提
• 周期の短いタスクに高い優先度を与える
• あるタスクを実行中に、より優先度の高い（ジョブのリリース周
期の短い）タスクのジョブがリリースされるとプリエンプション
が発生
例題 𝜏1 = 6,2,6 , 𝜏2 = 5,1,5 , 𝜏3 = 10,4,10 からなるタスク
集合のRMスケジューリングについて、以下の問いに答えよ。
(1) 優先度の高い順にタスクを並べ替えよ
(2) このタスク集合のハイパー周期を求めよ
(3) ゼロフェージングを仮定した場合、1ハイパー周期中の各タス
クのそれぞれのジョブの応答時間を求めよ
(4) さらに、その間にプリエンプションが発生しているならば、発
生時刻をすべて求めよ
例題の解答
(1) 𝜏2 , 𝜏1 , 𝜏3 の順
(2) ハイパー周期は 𝐿𝐶𝑀 6,5,10 = 30
時刻30までのスケジュール図を描画してみると
𝜏2
𝜏1
𝜏3
10
(3) 𝜏2 : 全部1, 𝜏1 : 3, 2, 2, 2, 3
20
𝜏3 : 10, 8, 8
(4) プリエンプションは時刻 5, 12, 15, 24, 25に発生
30
2013年問題3
プリエン
プション
30
10
20
30
40
50
60
DLMスケジューリング
• 各タスクのジョブのリリース周期（𝑇𝑖 ）と相対デッドライン（𝐷𝑖 ）が
等しいことを前提としない（𝑇𝑖 ≥ 𝐷𝑖 ≥ 𝐶𝑖 ）
• 相対デッドラインの短いタスクに高い優先度を与える
• あるタスクを実行中に、より優先度の高い（相対デッドライン
の短い）タスクのジョブがリリースされるとプリエンプションが
発生
DLMスケジューリング可能性
定理2.4 T ={𝜏1, 𝜏2, … , 𝜏𝑛} は優先度順に整列済を仮定して
各1 ≤ 𝑖 ≤ 𝑛に対して
𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑𝑖 𝑡
min
≤1
𝑡∈𝑆𝑖
𝑡
が成り立つとき、かつそのときのみT はDLMスケジューリング可能で
ある（必要十分条件）。ただし、
𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑𝑖 𝑡 : 0, 𝑡 でリリースされた𝜏1 から𝜏𝑖 のジョブの仕事量の和
𝑖
𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑𝑖 𝑡 =
𝑗=1
𝑡
𝑇𝑗
× 𝐶𝑗
𝑆𝑖 : タスク𝜏𝑖 のスケジューリングポイントの集合
𝑖
𝑘 × 𝑇𝑗 | 𝑘 ∈ N , 𝑘 × 𝑇𝑗 ≤ 𝐷𝑖 ∪ {𝐷𝑖 }
𝑆𝑖 =
𝑗=1
DLMスケジューリング可能性
定理2.4 T ={𝜏1, 𝜏2, … , 𝜏𝑛} は優先度順に整列済を仮定して
各1 ≤ 𝑖 ≤ 𝑛に対して
𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑𝑖 𝑡
min
≤1
𝑡∈𝑆𝑖
𝑡
が成り立つとき、かつそのときのみT はDLMスケジューリング可能で
何箇所かのスケジューリングポイントのどこかで
ある（必要十分条件）。
ただし、
（自分以上の優先度のタスクのジョブの仕事量）≦（経過時間）
𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑
𝑖 𝑡 : 0, 𝑡 でリリースされた𝜏1 から𝜏𝑖 のジョブの仕事量の和
𝑖
が成り立てばよい
𝑡
𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑𝑖 𝑡 =
× 𝐶𝑗
𝑇𝑗
𝑗=1
𝑆𝑖 : タスク𝜏𝑖 のスケジューリングポイントの集合
𝑖
𝑘 × 𝑇𝑗 | 𝑘 ∈ N , 𝑘 × 𝑇𝑗 ≤ 𝐷𝑖 ∪ {𝐷𝑖 }
𝑆𝑖 =
𝑗=1
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
𝑆1 = 4 ,
= ≤1
OK
4
4
𝑖 = 2について
𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑2 (5)
3
𝑆2 = 5 ,
= ≤1
5
5
OK
𝑖 = 3について
𝑆3 = 𝑘 × 𝑇1 𝑘 × 𝑇1 ≤ 𝐷3 ∪ 𝑘 × 𝑇2 𝑘 × 𝑇2 ≤ 𝐷3 ∪ {𝐷3 }
= 5,10 ∪ 6,12 ∪ 13 = {5,6,10,12,13}
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
14
𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑3 (𝑡) 𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑3 12
min
=
=1≤1
OK
𝑡∈𝑆3
𝑡
12
DLMスケジューリング（例題２）
例題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}
𝑆𝑖
𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑1
3
4
5
6
8
12
13
1
𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑2
3
𝑊𝑜𝑟𝑘𝐿𝑜𝑎𝑑3
9
4
10
12
13
16
アーリーデッドラインファースト(EDF)スケジューリング
絶対デッドラインが最も近いジョブを持つタスクに最高の優先度を
与える動的優先度のスケジューリング
(4,1,3)
(6,2,5)
(15,6,13)
EDFスケジューリングの性質
定理3.1
𝐷𝑖 = 𝑇𝑖 の場合過負荷でないタスク集合はスケジュール可能
定理3.2
タスク集合T = 𝜏1 , … , 𝜏𝑛 は
𝐷𝑒𝑚𝑎𝑛𝑑(𝑡)
max
≤1
𝑡∈𝑆
𝑡
であるときかつそのときのみEDFスケジューリング可能
ただし
𝑆:
ハイパー周期内のデッドライン時刻の集合
𝐷𝑒𝑚𝑎𝑛𝑑(𝑡): 時刻 𝑡 までにデッドラインを迎える
ジョブの仕事量の和
EDFスケジューリング
𝜏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
3
4
7
13
14
16
17
20
21
27
29
31
35
39
41
43
47
51
53
55
58
59
29
30
33
34
36
43
46
47
49
50
58
59
DemandはSPを超えないのでOK

Download Report