1. No category

Vol. 0
情報処理学会論文誌
No. 0
1959
拡張インプリサイスタスクの固定優先度スケジューリング
千 代 浩 之†
船 岡 健 司 ††
武 田
瑛 ††
山 崎 信 行†
インプリサイス計算モデルは，リアルタイム性と計算の品質のトレードオフを解決する効果的な手
法として知られている．しかしながら，インプリサイス計算モデルは，インプリサイスタスクの付
加部分を中断，完了する処理のリアルタイム性を保証できない．それゆえ，終端部分という第二の
必須部分を有する拡張インプリサイス計算モデルを用いる．拡張インプリサイス計算モデルを用い
た Mandatory-First with Wind-up Part （M-FWP）は動的優先度スケジューリングのためジッタが大き
い．本論文では，M-FWP よりジッタを最小限に抑えるため，拡張インプリサイス計算モデルを用い
た固定優先度スケジューリングアルゴリズム Rate Monotonic with Wind-up Part（RMWP）を提案す
る．RMWP は Rate Monotonic（RM）を基調としており，拡張インプリサイスタスクのジッタを最小
限に抑えるため，終端部分の実行可能範囲を制限する．スケジュール可能性解析では，RMWP は，あ
るタスクセットが RM でスケジュール可能ならば必ずスケジュール可能であることを証明した．シ
ミュレーションによる評価結果では，RMWP は RM より高いスケジュール成功率，RM，M-FWP よ
りジッタが小さいことを示した．
Fixed-Priority Scheduling of Extended Imprecise Tasks
H IROYUKI C HISHIRO ,† A KIRA TAKEDA ,†† K ENJI F UNAOKA ††
and N OBUYUKI YAMASAKI†
The imprecise computation model is known as an effective technique for resolving trade-offs between
real-time properties and qualities of calculations. However, the imprecise computation model cannot guarantee real-time properties of processings when the imprecise tasks terminate or complete their optional parts.
Therefore, we use the extended imprecise computation model with a second mandatory part, called wind-up
part. Mandatory-First with Wind-up Part (M-FWP) with the extended imprecise computation model has big
jitter due to dynamic-priority scheduling. This paper proposes Rate Monotonic with Wind-up Part (RMWP),
which is a fixed-priority scheduling algorithm with the extended imprecise computation model to minimize
jitter less than M-FWP. RMWP is based on Rate Monotonic and limits executable ranges of wind-up parts to
minimize jitter of extended imprecise tasks. The schedulability analysis proves that one task set is schedulable by RMWP if the task set is schedulable by RM. Simulation results show that RMWP has higher success
ratio than RM and the smallest jitter in three algorithms.
1. 序
い．最悪実行時間より実際実行時間が短い場合，余っ
論
た CPU 時間を利用するため，インプリサイス計算モ
自立移動型ロボット1),2) のようなリアルタイムシス
デル5) を用いる．
テムには，多様な環境で動作することが要求される．
インプリサイス計算モデルは，必須部分（mandatory
リアルタイム性を保証するため，タスクの最悪実行時
part）と付加部分（optional part）を持つ．必須部分は
間を用いたリアルタイムスケジューリングアルゴリズ
許容可能な最低限の品質を持つ結果を生成し，付加部
3),4)
ムが多く提案されている
．しかしながら，このよう
分は必須部分が生成した結果の品質を向上させる．イ
なリアルタイムシステムを実現するためには，経路選
ンプリサイス計算モデルを用いる場合，必須部分のリ
択タスクのように，障害物の数に依存して実際実行時
アルタイム性を保証すれば，過負荷状態に陥ったとし
間が大きく変動するタスクにも対処しなければならな
ても，付加部分を中断することでデッドラインミスを
回避することが可能である．従来のインプリサイス計
† 慶應義塾大学
Keio University
†† 株式会社東芝
Toshiba Corporation
算モデルは付加部分を中断，完了する際に補完的な処
理が必要ないことを仮定している．しかしながら，自
立移動型ロボットの制御には付加部分を中断，完了す
1
情報処理学会論文誌
2
1959
表 1 記号の定義
Table 1 Definition of symbols.
Discarded
Optional part Completed
Mandatory part
W ind-up part
記号
定義
τi
Γ
Γi
Γs
U
Ui
Ti
mi
oi
wi
Di
ODi
τi, j
ri, j
si, j
fi, j
oi, j
Di, j
ODi, j
Ri (t)
Terminated
図 1 拡張インプリサイス計算モデル
Fig. 1 Extended imprecise computation model.
る際に補完的な処理が必要である．例えば，画像処理
タスクでは画像データを入力（必須部分），演算の精度
を向上（付加部分），解析結果を出力（必須部分）のよ
うに終端にも第二の必須部分が要求される．この終端
部分（wind-up part）を有するモデルを拡張インプリ
サイス計算モデル6),7) と呼ぶ．拡張インプリサイス計算
モデルを用いたアルゴリズムには Mandatory-First with
Wind-up Part（M-FWP）6),7) があるが，Earliest Deadline
First（EDF）3) に基づく動的優先度アルゴリズムであ
り，ジッタが大きくなってしまう．モータ制御のよう
に許容するジッタが小さいタスクを持つ自立移動型ロ
ボットでは，M-FWP を用いることは望ましくない．
拡張インプリサイスタスク (i = 1, 2, ..., n)
タスク τ の集合
タスク τi より高優先度のタスクの集合
スケジュールが成功したタスクの集合
システム全体の CPU 利用率
タスク τi の CPU 利用率
タスク τi のジョブの到着周期
タスク τi の必須部分の最悪実行時間
タスク τi の付加部分の要求実行時間
タスク τi の終端部分の最悪実行時間
タスク τi の相対デッドライン
タスク τi の相対付加デッドライン
タスク τi の j 番目のジョブ ( j = 1, 2, .., )
ジョブ τi, j のリリース時刻
ジョブ τi, j の実行開始時刻
ジョブ τi, j の実行終了時刻
ジョブ τi, j の付加部分を実際実行時間
ジョブ τi, j の絶対デッドライン
ジョブ τi, j の絶対付加デッドライン
時刻 t でジョブ τi, j の残り実行時間
あるジョブ τi, j の ri, j から Di, j まで実行可能となる
NJik
これに対して，固定優先度アルゴリズムである Rate
τk の最大ジョブ数
τi が τk により妨害される最悪妨害時間
k 番目のタスクセットのハイパーピリオド
（全タスクの周期の最小公倍数）
Iik
3)
Monotonic（RM） は，M-FWP よりジッタが小さい利
Hk
点があるが，拡張インプリサイス計算モデルに未対応
である．
本論文では，拡張インプリサイス計算モデルを用い
た，M-FWP よりジッタが小さい固定優先度アルゴリズ
τ
1
r s
ム Rate Monotonic with Wind-up Part（RMWP）を
1,1
提案する．RMWP は RM を基調としており，拡張イ
1,1
f
r
1,1
Mandatory part
ンプリサイスタスクを固定優先度でスケジュール可能
1,2
s
f r s
1,2
1,2
1,3
Optional part
1,3
f
1,3
W ind-up part
図 2 RRJ と RFJ
Fig. 2 RRJ and RFJ.
になる．シミュレーションによる評価結果では，RM
より高いスケジュール成功率，RM，M-FWP よりジッ
タが小さいことを示す．
本論文の構成を以下に示す．第 2 章では，本論文で
仮定するシステムモデルと用語の定義を述べる．第 3
τ
τ
1
2
Mandatory part
章では，リアルタイムスケジューリングアルゴリズム
Optional part
W ind-up part
図 3 付加デッドライン
Fig. 3 Optional deadline.
に関する関連研究及びそれらの問題点について述べる．
第 4 章で提案するアルゴリズムを述べる．第 5 章でシ
ミュレーションによる評価結果を述べ，最後に第 6 章
けている．しかしながら，自立移動型ロボットによる
で結論を述べる．
モータ制御タスクを実行する場合，生成した結果をア
2. システムモデル
図 1 に拡張インプリサイス計算モデル6),7) を示す．
拡張インプリサイス計算モデルは，従来のインプリサ
5)
クチュエータに出力する処理が必要であるが，従来の
インプリサイス計算モデルに基づくタスクでは，付加
部分の中断，完了後にいかなる処理も実行できない．
この問題を解決するため，拡張インプリサイス計算モ
イス計算モデル に終端部分を追加したモデルである．
デルは終端部分を持つ．終端部分を付加部分の後に実
従来のインプリサイス計算モデルでは，付加部分を中
行することで中断，完了処理のリアルタイム性を保証
断，完了する際に生成した結果を出力する処理が不必
可能となる．
要であると仮定している．また，従来のインプリサイ
表 1 に本論文で使用する記号の定義を示す．システ
ス計算モデルを用いたアルゴリズムも，この仮定を設
ムは 1 個のプロセッサから構成されるものとする．n
Vol. 0
No. 0
拡張インプリサイスタスクの固定優先度スケジューリング
個の拡張インプリサイスタスクから構成されるタスク
3
Priority
セット Γ = {τi (Ti , Di , ODi , mi , oi , wi ), i = 1, 2, ..., n} がシ
MQ
ステムに与えられる．ただし，RM のような従来のア
ルゴリズムで拡張インプリサイスタスクをスケジュー
OQ
Scheduler
ルする場合，ODi = 0，oi = 0 となり，必須部分 mi と
終端部分 wi を連続して実行する．本論文では拡張イ
ンプリサイスタスクをタスクと呼ぶ．τi の CPU 利用
率 Ui = (mi + wi )/Ti とする．Ui には必須部分及び終端
SQ
Optional part
Mandatory part
Sleep
部分の最悪実行時間のみ含み，付加部分の要求実行時
W ind-up part
Empty
図 4 タスクキュー
Fig. 4 Task queue.
間を含まない．この理由は，付加部分の要求実行時間
を実行したか否かがタスクセットのスケジュール成功
とは無関係だからである．システム全体の CPU 利用
行開始する．この場合，τ2 の終端部分がデッドライン
率 U = ∑ni=1 Ui とする．タスクは，周期の短い順に整
列されているものとする．つまり，T1 ≤ T2 ≤ ... ≤ Tn
ミスを発生する可能性がある．τ2 の終端部分がデッド
が成り立つ．
してデッドラインで完了する時刻より早い時刻に付加
本論文では，ジッタはタスクの相対リリースジッ
ラインミスを発生しない理由は，終端部分が実行開始
デッドラインを設定したからである．
8)
タ（RRJ: Relative Release Jitter） ，相対終了ジッタ
（RFJ: Relative Finishing Jitter）8) の二つと定義する．
RRJ は二つの連続したジョブの開始時刻の最大偏差，
3. 関 連 研 究
従来のスケジューリングアルゴリズムは，RM3) ，
RFJ は二つの連続したジョブの終了時刻の最大偏差で
EDF3) がある．これらのアルゴリズムはタスクの実
ある．RRJ と RFJ を下式に示す．
際実行時間が最悪実行時間より短い場合を考慮してい
RRJi = max |(si, j+1 − ri, j+1 ) − (si, j − ri, j )|
j
RFJi = max |( fi, j+1 − ri, j+1 ) − ( fi, j − ri, j )|
j
ない．
従来のインプリサイス計算モデル5) は，タスクの実際
実行時間が最悪実行時間より短い場合，余った CPU 時
図 2 を用いて RRJ と RFJ を説明する．この場合，τ1
間を付加部分の実行に利用可能である．最悪実行時間
の RRJ は |(s1,2 − r1,2 ) − (s1,1 − r1,1 )| と |(s1,3 − r1,3 ) −
は実際実行時間より長く見積もってしまうので9) ，RM，
(s1,2 − r1,2 )| の最大値，RFJ は |( f1,2 − r1,2 ) − ( f1,1 −
EDF より実用的であると言える．従来のインプリサイ
r1,1 )| と |( f1,3 − r1,3 ) − ( f1,2 − r1,2 )| の最大値となる．
ス計算モデルを用いたスケジューリングアルゴリズム
ジッタを小さくすることは RRJ，RFJ を小さくするこ
は，Optimization with Least-Utilization（OPT-LU）10) ，
とを意味する．例えば，画像処理タスクでは，RRJ は
Mandatory-First Earliest Deadline（M-FED）11) がある．
画像データの入力時刻，RFJ は解析結果の出力時刻の
OPT-LU は付加部分の最悪実行時間が既知であること
最大偏差を表す．
を仮定しているので，本論文の対象とする，付加部分
本アルゴリズム固有のパラメータである付加デッド
の要求実行時間が未知である自立移動型ロボットに適
ラインは，付加部分が実行可能な期限及び終端部分の
応できない．M-FED は EDF に基づく動的優先度アル
実行開始時刻を表す．付加デッドライン以降では付加
ゴリズムでありジッタが大きくなってしまう．
部分を実行できない．付加デッドラインまでに必須部
拡張インプリサイス計算モデルを用いたアルゴリズ
分が完了していれば，終端部分がデッドラインミスを
ムは，M-FWP6),7) がある．M-FWP は M-FED を拡張イ
発生しない時刻に付加デッドラインを設定する．この
ンプリサイス計算モデルに対応した動的優先度アルゴ
具体例を図 3 を用いて説明する．実線の上矢印は必須
リズムである．M-FWP は必須部分の完了時に付加部
部分のリリース，実線の下矢印は終端部分のデッドラ
分の実行可能時間を動的に算出する．付加部分の実行
イン，破線の下矢印は付加デッドラインを表す．τ1 は
可能時間が有る場合，付加部分を実行開始するが，付
付加デッドライン以降では付加部分を実行せず，終端
加部分の実行可能時間が無い場合，終端部分を実行開
部分を実行する．これに対して，τ2 は付加デッドライ
始する．従って，付加部分の実行可能時間の有無に依
ン以降でも必須部分を実行する．τ2 のように付加デッ
存して，終端部分の完了時刻が変動してしまい，ジッ
ドライン以降で必須部分を実行する場合，付加デッド
タが大きくなってしまう問題がある．モータ制御のよ
ライン時刻ではなく必須部分の完了時に終端部分を実
うに許容するジッタが小さいタスクを持つ自立移動型
情報処理学会論文誌
4
When τi becomes ready, set Ri (t) to mi , dequeue τi
from SQ and enqueue τi to MQ.
(a)
If τi has the highest priority in MQ: preempt
the current task.
When τi completes its mandatory part:
(a)
If ODi expired, set Ri (t) to wi .
(b)
Otherwise set Ri (t) to oi , dequeue τi from
MQ and enqueue τi to OQ.
(i)
If there are one or multiple tasks in
MQ or OQ which have higher priority than τi , preempt τi .
When τi completes its optional part, dequeue τi from
OQ and enqueue τi to SQ.
When ODi expires:
(a)
If τi is in MQ and does not complete its
mandatory part, do nothing.
(b)
If τi is in OQ, terminate and dequeue τi from
OQ, set Ri (t) to wi and enqueue τi to MQ.
(i)
If τi has the highest priority in MQ,
preempt the current task.
(c)
If τi is in SQ, dequeue τi from SQ, set Ri (t)
to wi and enqueue τi to MQ.
When τi completes its wind-up part, dequeue τi from
MQ and enqueue τi to SQ.
When there are one or multiple tasks in MQ, perform
RM in MQ.
When there is no task in MQ and there are one or
multiples tasks in OQ, perform RM in OQ.
(1)
(2)
(3)
(4)
(5)
(6)
(7)
図 5 RMWP アルゴリズム
Fig. 5 RMWP algorithm.
1959
提案アルゴリズム RMWP は MQ，OQ，SQ の三つ
のキューを管理する．図 4 で示すように，MQ は必須
部分，終端部分，OQ は付加部分が実行可能状態のタ
スクをそれぞれ RM でスケジュールする．ただし MQ
にあるタスクは OQ にあるタスクより優先度が高く，
MQ にタスクがない場合のみ OQ にあるタスクを実行
する．あるタスク τi の必須部分，終端部分が両方 MQ
内に存在する場合はない．付加デッドライン ODi で
必須部分の実行が完了しない場合，図 3 の τ2 のよう
に終端部分を開始せず，必須部分を続けて実行する．
この場合，付加デッドラインではなく必須部分の実行
が完了した時刻で，終端部分が実行可能状態になる．
タスクの付加部分，終端部分が完了した場合，タスク
は SQ に格納される．付加デッドラインの算出手法は
4.1 節で述べる．
図 5 に RMWP アルゴリズムを示す．RMWP アルゴ
リズムのイベントは 7 種類あり，各々の条件が成り立
つ時に該当する処理を実行する．
図 6 に一般スケジュールと RMWP スケジュールを
示す．残り実行時間 Ri (t) を，一般スケジュールは破
線，RMWP スケジュールは実線で表す．付加部分の実
行は RMWP のみなので省略する．RM ような一般ス
ケジュールでは，τi のリリース時刻で，Ri (t) に mi + wi
を設定する．Ri (t) は 0 になるまで減少する．これに
対して，RMWP スケジュールでは，τi のリリース時
Ri(t)
mi+wi
mi
刻で，Ri (t) に mi を設定する．そして，付加デッドラ
general schedule
RMWP schedule
イン時刻 ODi で Ri (t) に wi を設定する．必須部分が
付加デッドライン時刻以降で実行する場合，必須部分
の実行が完了した時刻で Ri (t) に wi を設定する．
wi
4.1 付加デッドライン
general
τ
RMWP
τ
付加デッドラインは，必須部分が完了していれば終
i
端部分がデッドラインミスを発生しない時刻に設定し，
終端部分の実行可能範囲を制限することでジッタを抑
i
Mandatory part
Wi
nd-up part
図 6 一般スケジュールと RMWP スケジュール
Fig. 6 General schedule and RMWP schedule.
制する．タスク τi の付加デッドラインを設定するた
め，高優先度タスク τk による最悪妨害時間 Iik (k < i)
を求める．最悪妨害時間 Iik とは，τi が τk により実際
に実行を妨害される時間（実際妨害時間）の上限であ
ロボットでは，M-FWP を用いることは望ましくない．
4. RMWP アルゴリズム
本章では，提案アルゴリズム RMWP について述べ
る．RMWP は拡張インプリサイス計算モデルに対応
した M-FWP，ジッタが小さい RM の長所を活かした
る．まず，Iik を求めるため，以下の補題を利用する．
補題 1 (最大ジョブ数). あるジョブ τi, j の ri, j から Di, j
まで実行可能状態になる τk の最大ジョブ数 NJik (k < i)
は下式である．
» ¼ »
¹ º¼
Ti
Ti
Ti
NJik =
+
−
Tk
Tk
Tk
固定優先度アルゴリズムである．まず，RMWP の概
要について述べ，次に付加デッドラインの算出手法，
証明. k > i の場合，τi は τk より優先度が高く実行を
最後にスケジュール可能性解析について述べる．
妨害されないので考慮しなくてよい．図 7 のように τi
Vol. 0
拡張インプリサイスタスクの固定優先度スケジューリング
No. 0
5
証明. 定理 1 で求めた，τi より高優先度タスク τk に該
τ
当する最悪妨害時間 Iik の総和を減算するので，τi の必
Tk
k
須部分が付加デッドラインまでに完了していれば，終
τ
端部分がデッドラインミスを発生することはない．
Ti
i
ri,j
Di,j
ここで，M-FWP のような動的優先度アルゴリズム
図 7 パターン 1
Fig. 7 Pattern 1.
で付加デッドラインを静的に算出するためには，最悪
妨害時間を算出しなければならない．しかしながら，
M-FWP はジョブ毎に優先度が変動するので，何番目
τ
Tk
τ
Ti
k
のジョブで妨害時間が最悪になるのかを解析すること
は困難である．従って，RMWP は固定優先度でタス
i
ri,j
クをスケジュールすることで，定理 2 より付加デッド
Di,j
ラインを静的に算出可能にした．
4.2 スケジュール可能性解析
図 8 パターン 2
Fig. 8 Pattern 2.
RMWP のスケジュール可能性を，以下の定理によ
と τk のジョブが同時に実行開始する場合，τi, j の ri, j
から Di, j まで実行可能状態になる τk のジョブ数は少
なくとも下式である．
» ¼
Ti
Tk
り示す．
定理 3 (RMWP のスケジュール可能性). RMWP は，タ
スクセット Γ = {τi , i = 1, 2, ..., n} が RM でスケジュー
ル可能ならば必ずスケジュール可能である．
(1)
証明. 対偶を示すことにより定理を証明する．つまり，
図 7 のように，τi 内のジョブ数が式（1）で求めた
RMWP は，Γ がスケジュール不可能ならば RM でも
値より 1 多い場合がある．この発生条件は，Ti が Tk
必ずスケジュール不可能であることを示す．定理 2 よ
の整数倍とならない場合である．これを下式に示す．
¹ º¼
»
Ti
Ti
−
(2)
Tk
Tk
よって，式（1），
（2）より補題が示された．
次に，補題 1 を用いて最悪妨害時間を求める．
定理 1 (最悪妨害時間). タスク τi が，τi より高優先度
タスク τk による最悪妨害時間 Iik は下式である．
Iik = (mk + wk )NJik
り，タスク τi の付加デッドライン ODi までに，必須
部分が完了していれば，終端部分がデッドラインミス
を発生することはない．また，τi の終端部分がデッド
ラインミスを発生する場合は，必須部分が付加デッド
ライン以降で実行する時のみである．この場合，τi は
付加部分を実行せずに，必須部分，終端部分を連続し
て実行する．RM でも同様に，τi の必須部分，終端部
分を連続して実行するので，必ず τi の終端部分がデッ
ドラインミスを発生する．対偶が真なので定理は証明
された．
証明. RMWP は固定優先度なので，補題 1 より τi を
妨害する τk の実際妨害時間が，最悪妨害時間と定義
した τk の必須部分，終端部分の最悪実行時間の和と
最大ジョブ数の積より大きくなることはない．
そして，定理 1 を用いて，付加デッドラインを設定
図 9，図 10 にそれぞれ RMWP でスケジュール成
功，RM でスケジュール失敗の例を示す．タスクセッ
トは Γ = {τ1 = (10, 10, 7, 3, 0, 3), τ2 = (15, 15, 1, 3, 0, 2)}
である．付加デッドラインは，定理 2 を用いて算出し
た．付加部分の要求実行時間を実行したか否かがタス
クセットのスケジュール成功とは無関係なので，付加
する．
部分の要求実行時間を 0 とした．RMWP は付加デッド
定理 2 (付加デッドライン). タスク τi の付加デッドラ
イン ODi が下式の場合，必須部分が付加デッドライ
ラインで終端部分を開始することで，RM で発生する
ンまでに完了していれば終端部分がデッドラインミス
RMWP は，あるタスクセットが RM でスケジュール可
を発生しない．
能ならば必ずスケジュール可能であるだけでなく，RM
ODi = Di − wi −
∑
τk ∈Γi
Iik
τ2 のデッドラインミスを回避可能である．定理 3 より，
でスケジュール不可能なタスクセットをスケジュール
可能な場合がある．
情報処理学会論文誌
6
1959
τ
τ
1
1
deadline miss!
τ
τ
2
2
0
5
10
15
20
25
30
0
5
図 9 RMWP でスケジュール成功
Fig. 9 successful schedule produced by RMWP
Mandatory part
5. シミュレーション評価
10
15
20
25
30
図 10 RM でスケジュール失敗
Fig. 10 unsuccessful schedule produced by RM
Wi
nd-up part
ケジュール成功率（Success Ratio），付加部分の実行
割合（Reward Ratio），コンテキスト切り替えの頻度
本章では，RMWP の有効性を 6 種類の評価指標を
（Switch Ratio），プリエンプションの頻度（Preemption
用いて多角的に評価する．評価指標の詳細は 5.1 節で
Ratio），相対リリースジッタをタスクの周期で正規化
述べる．従来の固定優先度アルゴリズムである RM，
した RRJ Ratio，相対終了ジッタをタスクの周期で正
拡張インプリサイス計算モデルを用いた動的優先度ア
規化した RFJ Ratio を下式に示す．
ルゴリズムである M-FWP と比較評価する．ただし，
M-FWP には従来の手法
6),7)
Success Ratio =
より付加部分の実行可能
時間の見積もり精度を向上させた手法があるので12) ，
Reward Ratio =
こちらを採用する．評価には 1000 個のタスクセット
Switch Ratio =
を用いる．k 番目のタスクセットのシミュレーション
時間はタスクセット内の全タスクの周期の最小公倍数
Preemption Ratio =
であるハイパーピリオド Hk とする．本論文の対象と
RRJ Ratio =
する自立移動型ロボットでは，周期の短いモータ制御
タスクは 1ms，周期の長い画像処理による経路選択タ
RFJ Ratio =
スクは 30ms，他にも経路制御タスク等のように様々
# of successfully scheduled task sets
# of scheduled task sets
∑k ∑i
Ti
Hk
∑j
oi, j
oi
# of tasks in successfully scheduled task sets
∑k
# of context switches
Hk
# of successfully scheduled task sets
∑k
# of preemptions
Hk
# of successfully scheduled task sets
∑k ∑i
RRJi
Ti
# of tasks in successfully scheduled task sets
∑k ∑i
RFJi
Ti
# of tasks in successfully scheduled task sets
なタスクが存在する．従って，タスク τi の周期 Ti は
ただし，τi ∈ Γs である．Success Ratio が 0 の場合の
1ms から 30ms まで 1ms おきで，100 倍にスケーリン
CPU 利用率では，他の評価指標による評価結果はない．
グする．つまり，Ti は 100ms から 3000ms まで 100ms
また，Success Ratio に関して，RMWP-10，RMWP-
おきで設定する．CPU 利用率 Ui は 0.02 から 0.25 ま
20，RMWP-30 は RMWP，M-FWP-10，M-FWP-20，
で 0.01 おきで設定する．タスクの周期を 100 倍にス
M-FWP-30 は M-FWP と同じ評価結果なので省略する．
ケーリングすることで，タスクの周期や最悪実行時間
RRJ Ratio，RFJ Ratio に関しても，RMWP-10，RMWP-
を整数のみで表現可能となり，小数演算による誤差を
20，RMWP-30 は RMWP と同じ評価結果なので省略
無くすことが可能である．システム全体の CPU 利用
する．
率 U は 0.3 から 1 まで 0.05 おきで測定する．Ui 及び
5.2 評 価 結 果
U は必須部分，終端部分のみ含む．各々の Ui は一様
図 11 に Success Ratio の評価結果を示す．動的優先
分布により必須部分と終端部分に分割する．これらと
度である M-FWP の Success Ratio は常に 1 を保ってい
は別に，付加部分の要求実行時間 oi の CPU 利用率は
る．固定優先度である RMWP，RM は CPU 利用率が
0.1，0.2，0.3 の三種類を基準値として，各々の基準値
0.8 以上になると Success Ratio が低下する．RMWP が
の ±0.05 の範囲で，一様分布により生成する．つま
RM より Success Ratio が高い理由は，図 9，図 10 の
り，oi, j の CPU 利用率の範囲はそれぞれ [0.05, 0.15]，
ように RMWP でスケジュール成功，RM でスケジュー
[0.15, 0.25]，[0.25, 0.35] となる．評価結果にはそれぞ
ル失敗となる場合があるからである．
れ RMWP-10，RMWP-20，RMWP-30 のように表記す
図 12 に Reward Ratio の評価結果を示す．M-FWP-
る．ただし，oi, j が常に 0 の場合，評価結果には RMWP
10，M-FWP-20，M-FWP-30 はそれぞれ RMWP-10，
のように表記する．
RMWP-20，RMWP-30 より高い．RMWP は付加デッ
5.1 評 価 指 標
ドラインを静的に設定しているので，動的に付加部
評価指標として用いる，必須部分，終端部分のス
分の実行可能時間を算出する M-FWP より悪い結果に
拡張インプリサイスタスクの固定優先度スケジューリング
No. 0
RMWP
1.2
M-FWP
RM
1.2
Reward Ratio
Success Ratio
1
0.8
0.6
0.4
RMWP-10
RMWP-20
RMWP-30
M-FWP-10
M-FWP-20
M-FWP-30
1
0.8
0.6
0.4
0.03
RMWP-10
RMWP-30
M-FWP-10
M-FWP-30
0.02
0.01
0.2
0.2
0
0
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0
0.3
1
0.4
0.5
CPU Utilization
0.8
0.9
1
RMWP-10
RMWP-30
M-FWP-10
M-FWP-30
RMWP
M-FWP-20
0.6
M-FWP
M-FWP-30
M-FWP-10
RM
0.6
0.7
0.8
CPU Utilization
図 14 Preemption Ratio
Fig. 14 Preemption Ratio.
0.9
1
0.6
RMWP
M-FWP-20
0.6
0.7
0.8
0.9
1
M-FWP
M-FWP-30
M-FWP-10
RM
0.5
0.4
0.3
0.2
0.4
0.3
0.2
0.1
0
0
0.5
0.5
図 13 Switch Ratio
Fig. 13 Switch Ratio.
0.1
0.4
0.4
CPU Utilization
0.5
0.01
0.3
0.3
RFJ Ratio
0.02
0.7
図 12 Reward Ratio
Fig. 12 Reward Ratio.
RRJ Ratio
RMWP
RMWP-20
M-FWP
M-FWP-20
RM
0.03
0.6
CPU Utilization
図 11 Success Ratio
Fig. 11 Success Ratio.
Preemption Ratio
7
RMWP
RMWP-20
M-FWP
M-FWP-20
RM
0.04
Switch Ratio
Vol. 0
0
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0.3
0.4
0.5
0.6
0.7
CPU Utilization
CPU Utilization
図 15 RRJ Ratio
Fig. 15 RRJ Ratio.
図 16 RFJ Ratio
Fig. 16 RFJ Ratio.
なったと考えられる．
図 13 に Switch Ratio の評価結果を示す．RMWP，
0.8
0.9
1
の付加部分が完了した場合，続けて終端部分を実行す
るが，RMWP はタスクの付加部分が付加デッドライ
M-FWP は RM より Switch Ratio が高い理由は，タス
ン時刻までに完了した場合，付加デッドライン時刻ま
クを二つに分割することで，コンテキスト切り替えの
で終端部分の実行を遅らせることで，コンテキスト切
頻度が高くなったからである．RMWP-10，RMWP-20，
り替えが M-FWP より多く発生するからである．
RMWP-30 の順に Switch Ratio が低い理由は，付加部
図 15，図 16 に RRJ Ratio，RFJ Ratio の評価結果を
分の実行時間が長いほどコンテキスト切り替えをせ
示す．RMWP，RM の RRJ Ratio，RFJ Ratio に関して，
ずに，タスクの必須部分，付加部分，終端部分を連続
CPU 利用率が 0.95 の場合は 0.9 の場合より低い理由
して実行する場合が多いからである．M-FWP も同様
は，ジッタが小さくなるタスクセットのみスケジュー
に付加部分の実行時間が長いほど Switch Ratio が低く
ルが成功したからである．これに対して，M-FWP は
なる．
CPU 利用率が 0.95 以上になると RRJ Ratio が劇的に
図 14 に Preemption Ratio の 評 価 結 果 を 示 す．
上昇する理由は，ジッタが大きくなるタスクセットで
RMWP-10，RMWP-20，RMWP-30 が RM より高い理
もスケジュールが成功したからである．よって，RRJ
由は，付加部分の実行時に高優先度タスクにプリエン
Ratio と Success Ratio は高 CPU 利用率の場合，トレー
プションされるからである．RMWP-10，RMWP-20，
ドオフがあると言える．
RMWP-30 の順に Preemption Ratio が高い理由は，付
M-FWP-10，M-FWP-20，M-FWP-30 に関して，RRJ
加部分の実行時間が長いほど，高優先度タスクにプリエ
Ratio の場合，M-FWP とほぼ同じ評価結果を示してい
ンプションされる頻度が高くなるからである．M-FWP
る．しかしながら，RFJ Ratio の場合，M-FWP と大き
も同様に付加部分の実行時間が長いほど Preemption
く異なる評価結果になる．M-FWP では付加部分を実
Ratio が高い．
行する場合，必須部分の完了時に付加部分の実行可能
付加部分を実行した場合，RMWP では RM より
時間を算出する．付加部分の実行可能時間が有る場合，
Switch Ratio は約 1.5 倍，Preemption Ratio は約 5 倍，
付加部分を実行するが，付加部分の実行可能時間が無
M-FWP では RM より Switch Ratio は約 1.2 倍，Pre-
い場合，付加部分を破棄して終端部分を実行開始する．
emption Ratio は約 4.5 倍となってしまう．従って，拡張
なので，付加部分を実行可能時間の有無により RFJ
インプリサイスタスクをスケジュールすると，従来ス
Ratio が大きくなってしまう．これに対して，RMWP
ケジュールである RM よりオーバーヘッドは高くなっ
は付加部分の実行可能時間によらず，RRJ Ratio，RFJ
てしまう．Switch Ratio に関して，RMWP は M-FWP
Ratio ともにジッタを小さく維持できる．また，RMWP
より約 1.3 倍高い．この理由は，M-FWP ではタスク
は M-FWP だけでなく RM よりさらにジッタが小さい
情報処理学会論文誌
8
1959
ので，RM のジッタが小さい長所をさらに向上させた
よるものである．また，本研究を進めるにあたり，株
アルゴリズムである．
式会社東芝 船岡健司氏，武田瑛氏には大変お世話に
M-FWP は RMWP より Success Ratio，Reward Ratio
が高いので，スケジュール成功率及び付加部分の実行
割合が高いほど有効なアプリケーションに適している．
これに対して，RMWP は M-FWP より RRJ Ratio，RFJ
Ratio が低い．本論文では，モータ制御のように許容
するジッタが小さいタスクを持つ自立移動型ロボット
を対象としているので，RMWP は付加部分の実行可
能時間によりジッタが変動しないだけでなく，M-FWP
よりジッタが小さく安定した制御を行うことができる
ので，自立移動型ロボットに適している．
6. 結
論
本論文では，拡張インプリサイス計算モデルを用い
た固定優先度スケジューリング RMWP を提案した．
RMWP により拡張インプリサイスタスクを固定優先
度でスケジュール可能になった．RMWP では付加デッ
ドラインを設定することで，終端部分の実行可能範囲
を制限し，ジッタを抑制した．シミュレーションによ
る評価結果では，RMWP は RM より高いスケジュール
成功率であることを示した．また，そのトレードオフ
として RMWP はコンテキスト切り替えの頻度が RM
より約 1.5 倍，M-FWP より約 1.3 倍多く発生してし
まう．本論文で対象とする自立移動型ロボットでは，
モータ制御のように許容するジッタが小さいタスクを
持ち，その付加部分の実行時間はジョブ毎に変動して
しまうので，付加部分の実行時間に依存せず，ジッタ
が RM，M-FWP より小さい RMWP は自立移動型ロ
ボットに適している．
今後の課題を以下に示す．本論文における RMWP
のスケジュール可能性解析は，RMWP は，RM でスケ
ジュール可能なタスクセットは必ずスケジュール可能
であることを証明するにとどまったが，RMWP の厳密
なスケジュール可能性解析を行うためには，RMWP 用
のスケジュール可能性解析手法が要求される．RMWP
では全タスクが付加デッドラインまでに必須部分が完
了しない場合，RM と同じスケジュールとなる．従っ
て，RMWP 用のスケジュール可能性解析手法は，RM
で発生するケースと，RMWP のみで発生するケース
を解析することで，提案可能である．また，RMWP を
拡張インプリサイス計算モデル用のリアルタイム OS
である RT-Frontier13) に実装する．実用性を検証する
ため，RMWP のスケジューラやタスクのコンテキス
ト切り替えのオーバーヘッドを考慮した評価を行う．
謝辞 本研究は科学技術振興機構 CREST の支援に
なりました．ここに深く謝意を表します．
参
考
文
献
1) Kanehiro, F., Hirukawa, H. and Kajita, S.:
OpenHRP: Open Architecture Humanoid Robotics
Platform, The International Journal of Robotics Research, Vol. 23, No. 2 (2004).
2) Center, F. R. T.: http://www.furo.org/.
3) Liu, C. and Layland, J.: Scheduling Algorithms for
Multiprogramming in a Hard Real-Time Environment, Journal of the ACM, Vol.20, pp.46–61 (1973).
4) Leung, J. and Whitehead, J. W.: On the Complexity
of Fixed Priority Scheduling of Periodic Real-Time
Tasks, Performance Evaluation, Vol. 2, No. 4 (1982).
5) Lin, K., Natarajan, S. and Liu, J.: Imprecise Results: Utilizing Partial Computations in Real-Time
Systems, Proceedings of the 8th IEEE Real-Time
Systems Symposium, pp. 210–217 (1987).
6) Kobayashi, H. and Yamasaki, N.: An Integrated
Approach for Implementing Imprecise Computations, IEICE transactions on information and systems, Vol. 86, No. 10, pp. 2040–2048 (2003).
7) Kobayashi, H., Yamasaki, N. and Anzai, Y.:
Scheduling Imprecise Computations with Wind-up
Parts, Proceedings of the 18th International Conference on Computers and Their Applications, pp. 232–
235 (2003).
8) Buttazzo, G.C.: HARD REAL-TIME COMPUTING
SYSTEMS: Predictable Scheduling Algorithms and
Applications, Springer (2004).
9) 山本啓二, 石川裕, 松井俊浩: 移植性の高い実行時
間予測手法の設計と実装, 情報処理学会研究報告,
pp. 127–132 (2006).
10) Aydin, H., Melhem, R., Mosse, D. and MejfaAlvarez, P.: Optimal Reward-Based Scheduling of
Periodic Real-Time Tasks, Proceedings of the 20th
IEEE Real-Time Systems Symposium, pp. 79–89
(1999).
11) Baruah, S. K. and Hickey, M. E.: Competitive Online Scheduling of Imprecise Computations, IEEE
Transactions on Computers, Vol. 47, pp. 1027–1033
(1996).
12) Kobayashi, H.: REAL-TIME SCHEDULING OF
PRACTICAL IMPRECISE TASKS UNDER TRANSIENT AND PERSISTENT OVERLOAD, PhD Thesis, Keio University (2006).
13) Kobayashi, H. and Yamasaki, N.: RT-Frontier: A
Real-Time Operating System for Practical Imprecise
Computation, Proceedings of the 10th IEEE RealTime and Embedded Technology and Applications
Symposium, pp. 255–264 (2004).