Semi-Fixed-Priority Scheduling

(邦訳:準固定優先度スケジューリング)

千代 浩之
慶應義塾大学理工学部訪問研究員 /ノースカロライナ大学チャペルヒル校客員研究員/日本学術振興会特別研究員(PD)


[背景]自律移動ロボットに必要なリアルタイムシステムの構築
[問題]タスクのデッドラインの保証と計算結果の精度の向上
[貢献]マルチプロセッサに対応したインプリサイス計算向けリアルタイムスケジューリングの提案

自律移動ロボットのようなマルチプロセッサリアルタイムシステムでは,動的に環境が変化するため,オーバーロードの問題に直面している.インプリサイス計算は,タスクをデッドラインまでに完了させる性質であるリアルタイム性を要求する部分(必須部分)とリアルタイム性を要求しない部分(付加部分)にタスクを分割するモデルである.タスクのオーバーロードが発生した場合,付加部分を中断することで,必須部分のデッドラインミスを回避することが可能である.自律移動ロボットは画像処理タスクやモータ制御タスクを持つ.画像処理タスクでは,リアルタイム性だけでなく計算結果の精度も要求される.さらに,モータ制御タスクは,デッドラインをミスしない範囲内で,可能な限り一定の間隔で実行することを要求する性質(ジッタ)を持つ.これらの要求を満たすリアルタイムシステムを構築するため,本研究ではリアルタイムスケジューリングに焦点を当てる.

既存のリアルタイムスケジューリングとして,固定優先度スケジューリングであるRate Monotonic(RM)アルゴリズムと動的優先度スケジューリングであるMandatory-First with Wind-up Part(M-FWP)アルゴリズムがある.RMアルゴリズムはジッタが低いだけでなくマルチプロセッサに対応している利点がある.しかしながら,RMアルゴリズムでは,タスクの優先度が固定されるため,付加部分のオーバーロードが原因でデッドラインミスを過剰に発生させてしまう問題がある.従って,RMアルゴリズムは,インプリサイス計算に対応できない欠点がある.これに対して,M-FWPアルゴリズムはインプリサイス計算に対応している利点があるが,ジッタが高いだけでなくマルチプロセッサに対応できない欠点がある.

本研究では,リアルタイム性の保証と計算結果の精度を向上させるためのリアルタイムスケジューリングとして,準固定優先度スケジューリングの概念を提案した.そして,準固定優先度スケジューリングアルゴリズムであるRate Monotonic with Wind-up Part(RMWP)を提案した.準固定優先度スケジューリングは,マルチプロセッサに対応するだけでなく,インプリサイス計算にも対応する手法である.スケジュール可能性解析では,RMWPアルゴリズムは必ずRMアルゴリズムより優位であることを数学的に証明した.さらに,準固定優先度スケジューリングをサポートしたリアルタイムオペレーティングシステムRT-Estを開発した.シミュレーション評価では,RMWPアルゴリズムはRMアルゴリズムよりスケジュール成功率が高いだけでなく,M-FWPアルゴリズムよりジッタが低いことを示した.x86マルチプロセッサを用いた実機評価では,RMWPアルゴリズムはインプリサイス計算をサポートすることによるオーバーヘッドの増加がRMと比較して小さいことやジッタを抑制できることを示した.本研究で開発したリアルタイムスケジューリングやリアルタイムオペレーティングシステムが,自律移動ロボットにおけるモータ制御タスクのジッタを低減することや画像処理タスクの解析精度を向上させることを期待する.


 
 (2012年8月28日受付)
 
取得年月日:2012年3月
学位種別 :博士(工学)
大  学 :慶應義塾大学

推薦文:(組込みシステム研究会)


本論文では低ジッタと高スケジュール可能性を達成するために,準固定優先度スケジューリングの概念を提案し, RMを基調とした準固定優先度スケジューリングアルゴリズムRate Monotonic with Wind-up Part(RMWP)を提案している.本論文は,本研究会での重要トピックスであるリアルタイム実現についての論文であり,研究会推薦博士論文として推薦します.

著者からの一言


博士論文を執筆するに当たり,研究だけでなく生活においても,さまざまな方々に支えて頂きました.今後は,本研究で開発したリアルタイムスケジューリングとリアルタイムオペレーティングシステムを,自律移動ロボット等のような応用アプリケーションに適応させるための環境整備や普及活動を推進していきたいと思います.