著者

千代 浩之 武田 瑛 船岡 健司 山崎 信行

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.52, no.8, pp.2365-2377, 2011-08-15

---

本論文では,低ジッタと高スケジュール可能性を達成するために,準固定優先度スケジューリングを提案する.準固定優先度スケジューリングは,終端部分という第2の必須部分を有する拡張インプリサイスタスクの各々の部分を固定優先度でスケジュールする.また,本論文では,Rate Monotonic(RM)を基調とした準固定優先度スケジューリングアルゴリズムRate Monotonic with Wind-upPart(RMWP)とRMWP++を提案する.スケジュール可能性解析では,RMWPはRMでスケジュール可能なタスクセットは必ずスケジュール可能であることを証明する.さらに,RMWP++は,タスクの実際実行時間に依存せず,最短周期タスクのジッタを0に抑制可能であることを証明する.シミュレーションによる評価結果では,準固定優先度スケジューリングは固定優先度スケジューリングと同程度のスケジュール成功率を発揮するだけでなく,従来のスケジューリングよりジッタを抑制したことを示した.This paper proposes semi-fixed-priority scheduling to achieve both low-jitter and high schedulability. Semi-fixed-priority scheduling schedules the part of each extended imprecise task, which has a wind-up part as a second mandatory part, by fixed-priority. This paper also proposes two novel semi-fixed-priority scheduling algorithms based on Rate Monotonic (RM), called Rate Monotonic with Wind-up Part (RMWP) and RMWP++. The schedulability analysis proves that one task set is feasible by RMWP if the task set is feasible by RM. In addition, we prove that the shortest period task in RMWP++ has zero-jitter, regardless of its actual case execution time. Simulation results show that semi-fixed-priority scheduling has approximately the same success ratio as fixed-priority scheduling and lower jitter than existing scheduling.

著者

千代 浩之 山崎 信行

出版者

情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.51, no.12, pp.2227-2237, 2010-12-15

---

Responsive Multithreaded Processor(RMTP)のアーキテクチャはSimultaneous Multithreading(SMT)にリアルタイム処理で用いる優先度を導入した優先度付きSMTアーキテクチャである.RMTPでは同時に実行するタスクの組合せにより,最高優先度以外のスレッドで実行するタスクの実行効率が変動してしまうので,これらのタスクのリアルタイム性を保証することは困難である.最高優先度以外のスレッドでリアルタイム性を要求しない拡張インプリサイスタスクの付加部分を実行させることで,付加部分の実行割合を向上させることが可能である.拡張インプリサイスタスクを用いた準固定優先度スケジューリングアルゴリズムRate Monotonic with Wind-up Part(RMWP)はシングルプロセッサ用なので,優先度付きSMTプロセッサに適用できない.本論文では,最高優先度以外のスレッドで実行するタスクの付加部分の実行割合を向上させるために,RMWPを拡張したResponsive RMWP(R-RMWP)を提案する.スケジュール可能性解析では,R-RMWPのスケジュール可能上限はRate Monotonicのスケジュール可能上限と等しいことを証明する.シミュレーション結果では,R-RMWPはRMWPより付加部分の実行割合が向上したことを示す.Responsive Multithreaded Processor (RMTP) has the Simultaneous Multithreading (SMT) architecture with priority for real-time processings, called prioritized SMT architecture. In RMTP, execution efficiencies of tasks executing in threads except the highest priority thread fluctuate by multiple combinations of tasks executing simultaneously so that it is difficult to guarantee real-time properties of the tasks. When optional parts of extended imprecise tasks not requiring real-time properties are executed in threads except the highest priority thread, reward ratios of optional parts can be improved. Rate Monotonic with Wind-up Part (RMWP), which is a semi-fixed-priority scheduling algorithm with extended imprecise tasks, is for a single processor and cannot be adapted to the prioritized SMT processor. This paper proposes Responsive RMWP (R-RMWP), which is an extension of RMWP to improve reward ratios of optional parts. The schedulability analysis shows that the least upper bound of R-RMWP is the same as that of Rate Monotonic. Simulation results show that R-RMWP improves more reward ratios of optional parts than RMWP.

著者

千代 浩之

出版者

慶應義塾大学

雑誌

特別研究員奨励費

巻号頁・発行日

2012

---

今年度は, リアルタイムLinuxであるLITMus^RTに最適なマルチプロセッサ向けリアルタイムスケジューリングであるRUNを実装する研究を行った. また, LITMUS^RTに実装されているリアルタイムスケジューリングの実行を追跡・可視化するツールであるsched_traceをインプリサイス計算モデル向けに拡張した. これにより, インプリサイス計算モデル向けリアルタイムスケジューリングの開発効率を向上させることが可能になった.インプリサイス計算モデルに3つ以上の必須部分を持つタスクを扱うことを可能にするリアルタイムスケジューリングを提案した. この手法により, より複雑なインプリサイス計算モデルにリアルタイムスケジューリングを適用可能になった. また, インプリサイス計算モデル向け最適なマルチプロセッサ向けリアルタイムスケジューリングであるRUN-RMWPを提案した. RUN-RMWPはRUNを基調としたインプリサイス計算モデル向けの最適なリアルタイムスケジューリングである. シミュレーション結果では, 従来のインプリサイス計算モデル向けリアルタイムスケジューリングであるG-RMWPやP-RMWPよりプリエンプションやマイグレーションの回数が少ない結果を示した. さらに, タスクの品質の評価結果では, G-RMWPやP-RMWPと比較して少なくとも同等もしくは高い評価結果となった. 従って, RUN-RMWPは従来のインプリサイス計算モデル向けリアルタイムスケジューリングよりオーバヘッドを減らしつつ, タスクの品質を改善することが可能になった.上記の研究は, 分散制御型ロボット向けリアルタイムオペレーティングシステムを研究開発する上で非常に重要であり, これらを研究する意義は十分にあると言える.