RMZLに基づく擬似デッドラインを用いた スケジューリングアルゴリズムの

情報処理学会第 75 回全国大会
2L-5
RMZL に基づく擬似デッドラインを用いた
スケジューリングアルゴリズムの提案
箭内 健†
東京都市大学†
1
兪 明連†
序論
近年，組み込みリアルタイムシステムにおいてマルチ
横山 孝典†
る．図 1 にグローバル RM と RMZL によるスケジュー
リング例を示す．ただし，実行するタスクセット及び
プロセッサの利用が一般化してきている．しかし，マル
プロセッサ数は τ は τ = {τ1 = (2, 3), τ2 = (2, 3), τ3 =
チプロセッサ環境における最適なスケジューリングアル
(2, 3)}, M = 2 とする．
ゴリズムは確立しておらず，さまざまな研究がされてい
る．本研究ではシングルプロセッサ環境で最適であった
RM(Rate Monotonic) [1] にゼロ余裕時間ルールを追加
した RMZL(Rate Monotonic until Zero Laxity) [2] を
1
1
2
2
3
3
基に擬似デッドラインを追加したアルゴリズムを提案
デッドラインミス
し，スケジュール成功率が向上していることをシミュ
レーション評価により示す． 2
0
1
2
Time
3
1
2
3 Time
(b) グローバルRM
0
(a) RMZL
システムモデル
図 1: RMZL(a) とグローバル RM(b) のスケジュール例
本研究では，周期的タスクから成るタスクセットの
スケジューリングを対象とし，マルチプロセッサ環境
図 1 から分かるように，グローバル RM では τ1 , τ2
でのリアルタイムスケジューリングの研究における一
が優先され，τ3 の実行が遅れるため τ3 がデッドライン
般的なシステムモデル [2] を仮定する．
ミスを起こしている．しかし，RMZL では時刻 1 にお
システムは M 個のプロセッサを持ち，N 個のタスク
から構成されるタスクセット τ は τ = {τ1 , τ2 , ...τi ，
...，
いて τ3 の余裕時間が 0 となり，最高優先度を獲得する
ことでスケジュールに成功している．
τN } が与えられる．各タスク τi は最悪実行時間 Ci と周
期 Ti により，τi = (Ci , Ti ) と構成される．Ui = Ci /Ti
をタスク τi の利用率と呼ぶ．また，U (τ )/M をシステ
大幅に向上させたが，周期の長いタスクは最高優先度
ム利用率と呼ぶ．各タスク τi は周期 Ti の間隔でジョブ
ラインミスを起こす可能性がある．
RMZL はグローバル RM よりスケジュール成功率を
を獲得するのが遅く，後半に処理が偏ることでデッド
を生成する．タスク τi が生成する k 番目のジョブを τik
LP-RMZL(Limited Preemptive-RMZL) [3]
LP-RMZL は，一度実行を開始したジョブは余裕時
と表す．τik は時刻 rik でリリースされ，デッドライン
dik は次のジョブのリリース時刻とする．ある時刻 t に
おいて，ジョブ τik の残り実行時間を Cik (t) とすると
間 0 のジョブにしかプリエンプトされないというルー
き，
τik の余裕時間 (Laxity) を Lik = dik − t − Cik (t)
と定義する． RMZL と LP-RMZL によるスケジューリング例を示す．
3
ルを RMZL に追加したアルゴリズムである．図 2 に
ただし，実行するタスクセット及びプロセッサ数は τ は
τ = {τ1 = (1, 2), τ2 = (1, 2), τ3 = (1, 4), τ4 = (6, 8)},
関連研究
グローバル RM
周期の短いジョブを優先して実行する RM をマルチ
M = 2 とする．
プロセッサ環境に適用させたグローバル方式の RM(以
降グローバル RM) が提案されたが，スケジュール成功
1
1
2
2
3
3
4
4
率が低いという問題点がある．
RMZL(RM until Zero Laxity)
デッドラインミス
RMZL は，グローバル RM において，余裕時間がゼロ
となったジョブに最高優先度を与えるアルゴリズムであ
0
1
2
3
4
5
6
7
(a) LP-RMZLのスケジュール例
8 Time
0
1
2
3
4
5
6
7
8 Time
(b) RMZLのスケジュール例
図 2: LP-RMZL(a) と RMZL(b) のスケジュール例
A Proposal of Scheduling Algorithm using Pseudo Deadline
Based on RMZL
† Tokyo City University
1-227
Copyright 2013 Information Processing Society of Japan.
All Rights Reserved.
情報処理学会第 75 回全国大会
図 2 のように，LP-RMZL では一度実行を開始した
τ4 がプリエンプトされず連続して実行することができ
るため，スケジュールに成功している．LP-RMZL では
各々1000 セットずつ投入し，各アルゴリズムでシミュ
RMZL よりスケジュール成功率を向上したが，RMZL
でスケジュールに成功したタスクセットがスケジュー
ルできなくなる場合がある．
ルしたタスクセットの総数) とする．なお，プロセッ
4
レーションを行う．比較する項目はスケジュール成功率
(スケジュールに成功したタスクセット数 / スケジュー
サ数は 4 とした．以下の図 4 にスケジュール成功率の
グラフを示す．図 4 からスケジュール成功率が RMZL，
LP-RMZL より向上しているのがわかる． LP-RMZLPD
(LP-RMZL add Psuedo Deadline)
1
LP-RMZL を基にスケジュール成功率を向上するア
ルゴリズム LP-RMZLPD を提案する．LP-RMZLPD
0.8
Success Ratio
とは擬似デッドラインと擬似実行時間を使用して，周
期の前半にゼロ擬似余裕時間ルールを LP-RMZL に適
用したものである．タスクの周期の半分の位置に擬似
0.6
0.4
的なデッドラインを設定し，それを擬似デッドライン
0.2
と呼ぶ．また，各タスクの実行時間の半分を擬似実行
LP-RMZLPD
LP-RMZL
RMZL
RM
時間とし，擬似デッドラインまでの余裕時間 (擬似余裕
時間) が 0 のジョブに準最高優先度を擬似デッドライン
まで与える．準最高優先度は最高優先度の次に高い優
先度を意味する．つまり，余裕時間が 0 のジョブは，擬
似余裕時間が 0 のジョブに実行を妨げられない．また
LP-RMZLPD では，一度実行を開始したジョブは，余
裕時間 0 のジョブ，または擬似余裕時間 0 のジョブに
しかプリエンプトされない．
図 4 に LP-RMZLPD でスケジューリングした例を示
す．ただし，実行するタスクセット及びプロセッサ数は τ
は τ = {τ1 = (2, 4), τ2 = (2, 4), τ3 = (1, 4), τ4 = (6, 8)},
M = 2 とする．
0
0.3
6
0.4
0.5
0.6
0.7
System Utilization
0.8
0.9
1
図 4: スケジュール成功率
結論及び今後の課題
本研究では，LP-RMZL に擬似デッドラインを設定
した LP-RMZLPD を提案し，シミュレーションにより
有効性を示した．しかし，提案したアルゴリズムはス
ケジュール可能性が解析されていないため，一般的な
評価がされてるとは言えない．また，余裕時間の検出
など実装面で問題が発生する可能性がある．これらは
今後の課題とする．
謝辞
擬似デッドライン
1
1
2
2
3
3
本研究は JSPS 科研費 24500046 の助成を受けたもので
す． 参考文献
デッドラインミス
4
4
0
1
2
3
4
5
6
7
8 Time
0
(a) LP-RMZLPDのスケジュール例
1
2
3
4
5
6
7
[1] C. L. Liu and J. Layland,“ Scheduling algorithms
for multiprogramming in a hard real-time envi-
8 Time
(b) LP-RMZLのスケジュール例
図 3: LP-RMZLPD(a) と LP-RMZL(b) のスケジュー
ronment ”,Journal of the ACM, Vol. 20, No. 1,
pp. 46-61, 1973.
ル例
τ4 が時刻 1 において擬似余裕時間が 0 となり，準最
高優先度を獲得して実行している．このようにするこ
[2]
Monotonic に基づくマルチプロセッサ用リアルタ
イムスケジューリング”, 情報処理学会, コンピュー
とで，周期の長いタスクが早い時刻において実行する
ことができるためデッドラインミスを起こすことなく
ティングシステム，Vol.2，No.1，pp.64-74，2009.
スケジュールできている．
5
[3]
評価
武田 瑛，船岡 健司，加藤 真平，山崎 信行“
, Rate
シミュレーションにより評価する．ランダムに生成し
たタスクセットをシステム利用率 30%から 100%まで
西垣公平，兪明連，横山孝典“
, RM に基づいたリア
ルタイムスケジューリングアルゴリズムの提案と
可能性解析 ”, 電子情報通信学会, D，Vol. J95-D，
No. 6，pp. 1347-1355，2012．
1-228
Copyright 2013 Information Processing Society of Japan.
All Rights Reserved.