JAIST Repository
https://dspace.jaist.ac.jp/Title

動的要因を考慮したリアルタイムスケジューリング理論の構築と実装

Author(s)田中, 清史Citation

科学研究費助成事業研究成果報告書: 1‑6

Issue Date

2018‑06‑01

TypeResearch Paper

Text version

publisher

URL

http://hdl.handle.net/10119/15394

RightsDescription

基盤研究(C)（一般）, 研究期間：2015〜2017, 課題番
号：15K00073, 研究者番号：20333445, 研究分野：計算機システム

Japan Advanced Institute of Science and Technology

２版

様式

Ｃ−１９、Ｆ−１９−１、Ｚ−１９ （共通）

科学研究費助成事業

研究成果報告書
平成 ３０ 年

６ 月

１ 日現在

機関番号： １３３０２
研究種目： 基盤研究(C)（一般）
研究期間： 2015 〜 2017
課題番号： １５Ｋ０００７３
研究課題名（和文）動的要因を考慮したリアルタイムスケジューリング理論の構築と実装

研究課題名（英文）Building and Implementing of Real‑time Scheduling Theory with Runtime Factors

研究代表者
田中清史（TANAKA, KIYOFUMI）

北陸先端科学技術大学院大学・先端科学技術研究科・准教授

研究者番号：２０３３３４４５
交付決定額（研究期間全体）：（直接経費）

3,600,000 円

研究成果の概要（和文）：目的の異なる多数のタスクからなるクリティカリティ混在システムが増加しつつある．本研究ではタスク群のスケジューリングにおいて従来の理論では理想化されていた動的要因である「タスクの実行時間の変動」，「タスクの非同期的起動・終了」，および「スケジューリングオーバヘッド」を導入した，リアルタイムスケジューリングの定式化，スケジューラビリティ解析，および実用化方式を提案・評価した．これにより，今後の複雑化・多様化する組込みアプリケーションタスクの異なるリアルタイム性要求に対し，最適なスケジューリングアルゴリズムの選択を可能とした．

研究成果の概要（英文）：Mixed‑criticality systems which consists of many tasks with different aims
are increasing. This research proposed and evaluated practical methods as well as formalization ofreal‑time scheduling and schedulability analysis, introducing runtime factors which have been
idealized in the former theories; "fluctuation of tasks' execution times", "asynchronous invocationand termination", and "scheduling overheads". This made it possible to select an optimal schedulingalgorithm for each of different real‑time requirements, where embedded application tasks arebecoming more complicated and diversified.

研究分野： 計算機システム
キーワード： リアルタイム

スケジューリング実行時間

組込みシステム様 式 Ｃ−１９、Ｆ−１９−１、Ｚ−１９、ＣＫ−１９（共通）１．研究開始当初の背景
組込みシステムの複雑化と多様化に伴い，異なる性質のタスクが混在するシステム（Mixed‑Criticality）が主流になりつつある．例えば，完全なリアルタイム性が要求される対象機器の制御タスク（ハードタスク）と，ある程度の応答性能は要求されるが完全なリアルタイム処理は要求されないユーザインタフェース等のタスク（ソフトタスク）の混在が挙げられる．このようなシステムで要求されるリアルタイム処理を実現するためには，ハードタスク，ソフトタスクの両方を対象とし，タスク群のスケジューラビリティ（特にハードタスクの実行が締切時刻制約を満たすこと）を保証できるリアルタイムスケジューリングアルゴリズムを使用する必要がある．しかしこれまでに提案されてきた様々なアルゴリズムでは，理想化されたタス
ク実行モデル上での最適性およびスケジューラビリティ解析方法が数学的に証明されてきたが，実際のシステムに適用した場合の優位性は不明であった．その要因として，以下の 3 つの点が挙げられる．
(1) タスクの実行時間が変動する
一般に一つのタスクはシステム稼働中に複数回実行され，その実行時間は実行毎に変動するが，従来の理論ではタスクの実行時間としてタスク毎に固定の最悪実行時間（Worst‑Case Execution Time: WCET）が仮定されてきた．実際の実行時間は入力値や実行パス，キャッシュヒット／ミス等によって変動し，最悪の場合は WCET の時間を費やすが，ほとんどの場合ではそれ以下の時間で終了する．実行時間として WCET を仮定することは，締切時刻（デッドライン）を確実に守ることを保証するために必須とされてきたが，研究代表者による過去の研究において，WCET よりも短い実行時間を仮定した場合でも全てのデッドラインを完全に守ることが保証され，応答時間をより短縮することが可能であることが示された．
(2) タスク実行の開始・終了タイミングは OSのティックタイミングとは一致しない
従来のスケジューリング理論では，タスク実行の開始，中断，終了のタイミングは OSが設定する周期的ティックのタイミングと一致する．（このことは過去のスケジューリ
ング理論の文献で明確には記述されてこな
かったが，実装を考慮すると自明である．）
これはタスク実行のモデルを単純化するためであるが，実際のシステムでは割込み機能の利用等により，開始，中断，終了はティックと異なるタイミングで発生しうる．また，タスクの実行時間が短い場合は，1 ティック内で複数回のタスク切替が起こりうる．理論と実用の差を埋めるためには，このタイミン
グのずれを考慮したスケジューリングアルゴリズムとスケジューラビリティ解析が必要である．

(3) スケジューラおよびディスパッチャの実行オーバヘッドが存在する
従来のスケジューリング方式の説明では，スケジューラやディスパッチャ等の OS 実行のオーバヘッドがゼロとみなされていた．一方，実際のシステム上ではオーバヘッドが存在する．CPU 使用率に基づく簡単なスケジューラビリティ解析ではこのオーバヘッドを考慮する研究が存在するが，オーバヘッド要因をタスク実行モデルに明に導入したリア
ルタイムスケジューリングアルゴリズムは提案されてこなかった．
これまでの研究で，実環境モデルにおいてオーバヘッドを考慮しない場合は理論通りの結果にならないことを経験し，逆に，オーバヘッドを考慮したスケジューリングを行うことにより，ソフトタスクの実行を抑制し，ハードタスクのデッドラインミスが削減され，理論と近い結果が得られることがわかった．オーバヘッドに加え，上記(1)，(2)の要因を導入したスケジューリング方式および解析手法を実現することが，理論と実用のギャップを埋めるためには必要であることが理解でき，このことが本研究の着想に至った第一の理由である．更に，(1)の要因である実行時間の変動を予測し，最悪実行時間の代わりに予測時間を利用することにより，ソフトタスクの応答時間とハードタスクのジッタ（完了タイミングのずれ）を短縮できることが確認された．この実行時間変動に加え，タイミングのずれと OS オーバヘッドを導入することにより実際のシステム上での効果が期待できる新しいアルゴリズムの着想に至っており，本研究において提案・評価を行う．
２．研究の目的
スマートフォンや車載 ECU 統合のように，目的の異なる多数のタスクからなるクリティカリティ混在システムが増加しつつある．
本研究ではタスク群のスケジューリングにおいて従来の理論では理想化されていた（考慮されていなかった）動的要因である「タスクの実行時間の変動」，「タスクの非同期的起動・終了」，および「スケジューリングオーバヘッド」を導入した，リアルタイムスケジューリングの定式化，スケジューラビリティ解析，および実用化方式を提案・評価する．
これにより，今後の複雑化・多様化する組込みアプリケーションタスクの異なるリアルタイム性要求に対し，最適なスケジューリングアルゴリズムの選択を可能とする．動的要因の利用により，従来の理論モデル上でのリアルタイム性能を超える実用化方式を実証することが革新的である．
３．研究の方法
初年度は主に，（１）動的要因を導入した拡張モデルの定義，（２）各調査対象アルゴ

リズムの動的要因を導入したスケジューラ
ビリティ解析の定式化，および（３）拡張モデル上での，動的要因に確率分布を使用した場合のアルゴリズムの評価を行う．
上記（１）において「タスクの実行時間の変動」，「ティックと非同期的なタスクの起動・中断・終了」，および「OS のオーバヘッド」の 3 つの動的要因を導入して，従来のタスク実行モデルを拡張したモデルを定義する．続いて（２）において，定義した拡張モデル上でのスケジューリングアルゴリズムのスケジューラビリティ解析法を構築する．
この際，理論的に各種最適性が示されている従来のアルゴリズムから，複数の対象アルゴリズムを選定する．更に（３）において，動的要因に確率分布から得られる量を用いて対象アルゴリズムのリアルタイム性の評価を行う．
2 年目は，（４）シミュレーション環境の構
築，（５）実行バイナリのシミュレーションによる評価，（６）統計情報のスケジューラ
ビリティ解析方法へのフィードバックと実用性の評価，および（７）動的要因を利用するアルゴリズムの確立・実装を行う．
実際の実行状況を反映する評価を行う
ために，アプリケーションバイナリをターゲットとするシミュレーションを行う．このために，（４）においてシミュレーション環境を構築する．これについては研究代表者が行う．過去の研究で作成した CPU 命令実行シミ
ュレータを基にし，リアルタイム性に関する結果出力の機能を付加して使用する．シミュ
レーションは ITRON 仕様リアルタイム組込み
OS を含む実バイナリを対象とする．研究代表者が過去の研究で研究開発した組込み OS を使用し，このスケジューラ部分を置き換えることで様々なスケジューリングアルゴリズムが実現可能である．
続いて（５）において，実アプリケーションを使用したシミュレーション評価を行う．
シミュレーションではリアルタイム性の評価の他，本研究で動的要因として位置づけている「実行時間の変動」，「開始，中断，終了タイミング」，「OS のオーバヘッド」の 3 点について，シミュレーション実行から統計情報として抽出する．続いて（６）において，（５）で得られた統計情報を，前年度における（２）で確立したスケジューラビリティ解析方法に反映させる．これにより，各アルゴリズムの実用性が明らかになり，かつ実際の状況に基づいたスケジューラビリティ解析が可能となる．
（７）では，実行時間の変動等の動的要因を考慮し，それを利用するアルゴリズムを確立し，実装する．実行時間に依存して締切時刻が設定されるアルゴリズムに基づくこと
で，短い実行時間を仮定することにより締切時刻がより短くなり，結果的に平均応答時間やジッタが短縮されることが既に確認されている．これを拡張し，実行時間以外の 2 つの動的要因をアルゴリズムに導入することでリアルタイム性の向上を狙う．
最終年度は，（８）提案アルゴリズムと既存アルゴリズムの性能比較評価を行う．
2 年目の（７）で提案したアルゴリズムに対して実バイナリを使用したシミュレーシ
ョン評価を行い，既存のアルゴリズムと比較してタスク実行の平均応答時間とジッタが改善できることを示す．
本研究の 2 年目以降で行う評価では，実際のリアルタイム OS のコードを含むバイナリプログラムのクロックサイクルベースシミュレーションを行うが，研究代表者が過去の研究で開発した ITRON 仕様オペレーティングシステムを利用することにより，スケジューリングアルゴリズムの置換が容易となる．これにより，予定する期間内に実バイナリを用いる評価を行うことが十分に可能である．
４．研究成果
本研究は目的の異なる多数の重要度の異なるタスク群からなるリアルタイム組込みシステムにおいて，従来の理論では理想化されていた動的要因である「タスクの実行時間の変動」，「タスクの非同期的起動・終了」，および「スケジューリングオーバヘッド」を導入したリアルタイムスケジューリングの定式化，スケジューラビリティ解析，および実用化方式を提案・評価することを目的としてきた．これにより，今後の複雑化・多様化する組込みアプリケーションタスク群の異なるリアルタイム性要求に対し，最適なスケジューリングアルゴリズムの選択を可能とする．動的要因の利用により，従来の理論モデル上でのリアルタイム性能を超える実用化方式を実証することが革新的である．
初年度は主に，(1)動的要因を導入した拡張モデルの定義，(2)各調査対象アルゴリズムの動的要因を導入したスケジューラビリ
ティ解析の定式化，および(3)拡張モデル上での，動的要因に確率分布を使用した場合のアルゴリズムの評価を行う計画を立て，研究を進めた．上記(1)において，「タスクの実行時間の変動」，「システムティックと非同期的なタスクの起動・中断・終了」，および「OSのオーバヘッド」の 3 つの動的要因を導入して，従来のタスク実行モデルを拡張したモデルを定義した．これについては，国際会議 2件，国内会議 1 件の発表を行った．(2)に関して，固定優先度リアルタイムスケジューリングを前提としたシステムを対象とし，動的要因を含んだモデルに対するスケジューラビリティの十分条件式を確立し，国際会議 2件，国内会議 1 件において提案した．
同じく，(3)に関して，動的要因に対して確率分布（指数分布および正規分布）を使用して多数のタスクセットを生成し，シミュレーションによってリアルタイム性能を評価し，国際会議，国内会議にて発表を行った．
28 年度主に全体計画のうちの(4)シミュレ

ーション環境の構築，(5)実行バイナリのシミュレーションによる評価，(6)統計情報のスケジューラビリティ解析方法へのフィードバックと実用性の評価，および(7)動的要因を利用するアルゴリズムの確立・実装を行う計画を立て研究を進めた．上記(4)において，近年組込みシステム業界で標準となりつつある ARM プロセッサアーキテクチャを対象とした命令実行型シミュレータを構築した．
本シミュレータによりクロックサイクルレベルでの時間計測が可能となった．これについては(5)以降の研究項目で使用した．上記(5)において，実際の OS を含むバイナリコードに対して(5)で構築したシミュレータによるシミュレーション評価を行った．これについては，国際会議，国内会議において発表を行った．上記(6)に関して，各種シミュレーションによって得られた統計情報を前年度確率したスケジューラビリティ解析手法にフィードバックし，有効性を検証した．これについては国際会議において発表を行い，さらに国際ジャーナルに採録された．上記(7)に関して，動的要因を考慮する複数のスケジューリングアルゴリズムを確立し，かつ実装および評価を行った．これについては国際会
議，国内会議において発表を行った．
最終年度の 29 年度は主に全体計画のうちの「(8)提案アルゴリズムと既存アルゴリズムの性能比較評価」を進めた．多数の周期タスクおよび非周期タスクを含むタスクセッ
トに対して，前年度までに提案した各種スケジューリングアルゴリズムのシミュレーシ
ョン評価を行い，既存のアルゴリズムと比較してタスク実行の平均応答時間とジッタが改善できることを定量的に示した．提案方式と得られた結果についてまとめ，国際会議おいて発表を行い，さらに国際ジャーナルにおいて論文が掲載された．さらに，本研究にいて提案したスケジューリングの応用研究として，自動運転アプリケーション開発環境への適用，個々の組込みアプリケーションに適応する組込みオペレーティングシステムへの適用，パズルゲームアプリケーションへの適用，および消費電力削減を目的としたスケジューリングアルゴリズムへの適用に関する研究を行い，それぞれ国際会議，国内会議にて発表を行った．
５．主な発表論文等（研究代表者、研究分担者及び連携研究者には下線）〔雑誌論文〕（計 4 件）[1] Doan Duy, Kiyofumi Tanaka, Enhanced
Virtual Release Advancing Algorithm forReal‑Time Task Scheduling, Journal ofInformation and Telecommunication, Vol.2,
Issue 1(2018), pp.1‑‑19, online.(ISSN:2475‑1839 (Print) 2475‑1847 (Online)
Journalhomepage:

http://www.tandfonline.com/loi/tjit20)[2] Kazuki Hasegawa, Kiyofumi Tanaka,
Server Mechanisms for GuaranteeingSchedulability with RTOS Processing andImproving Application Responsiveness bySlackReclaiming, International
JournalofComputersandTheirApplications, Vol.23, No.2 (2016),
pp.116—123.(ISSN:1076‑5204)[3] Kiyofumi Tanaka,
Virtual Release
Advancing for Earlier Deadlines, ACM
SIGBED Review, Vol.12, No.3 (2015),
pp.28‑‑31.
[4] Kiyofumi Tanaka, Real‑Time Schedulingfor Reducing Jitters of PeriodicTasks, Journal of Information Processing,
査読有，Vol.23, No.5 (2015), pp.542‑‑552.
〔学会発表〕（計 26 件）
[1] Tetsuo Miyauchi, Kiyofumi Tanaka,"BuildingaFrameworkfor
anApplication‑Adaptive Processor System on
FPGA‑based SoC," 21st Workshop on
Synthesis And System Integration of Mixed
Information technologies, Mar 27, 2018,
Shimane (Japan).
[2] Boyu Tseng, Kiyofumi Tanaka,"Reducing
Jitter and Energy in Hard Real‑time
Systems
Using
Intra‑task
DVFS
Technique,"80th National Convention ofInformation Processing Society of Japan,
Mar 15, 2018, Tokyo (Japan).
[3] Kiyofumi Tanaka, "Adaptive Computing
Framework in the IoT Era," InternationalConference for Tips for Top and Emerging
Computer Scientists (IC‑TECS 2017), Dec 22,
2017, Taipei (Taiwan).
[4] 宮内 哲夫，田中 清史， SMT ソルバを用いた Slitherlink パズルの解法 ，第 22 回ゲーム・プログラミングワークショップ，2017
年 11 月 11 日，箱根山セミナーハウス（神奈川県・箱根町）[5] Yuranan Kitrungrotsakul, KiyofumiTanaka, Masanobu Hashimoto and Shuichi
Onishi, Virtual
Environmentfor
Developing Real‑Time Image Processing for
Vehicle Control,
Workshop on Virtual
Prototyping of Parallel and Embedded
Systems (ViPES), July 16, 2017, Samos(Greece).
[6] Doan Duy, Kiyofumi Tanaka,An
Effective
ApproachforImprovingResponsivenessofTotal
BandwidthServer,
International Conference on
Information and Communication Technologyfor Embedded Systems (IC‑ICTES), May 8,
2017, Chonburi Beach (Thailand).
[7] Doan Duy, Kiyofumi Tanaka, Hardware
Implementation of Enhanced Virtual

Release Advancing Algorithm for Real‑Time
Task
Scheduling,
International
Conference on Industrial Technology, Mar24, 2017, Toronto (Canada).
[8] Takaharu Suzuki, Kiyofumi Tanaka,
Execution Right Delegation: Beyond theRate
Monotonic,
International
Conference on Computers and TheirApplications ， Mar 21, 2017, Honolulu(Hawaii).
[9] Tetsuo Miyauchi, Kiyofumi Tanaka, A
Solution to Slitherlink Puzzles Using
FPGA,International Conference onComputers and Their Applications，Mar 20,
2017, Honolulu (Hawaii).
[10] 宮内 哲夫，田中 清史， RTOS の FPGAによるハードウェア化の検討 ，情報処理学会第 79 回全国大会, 2017 年 3 月 16 日，名古屋大学（愛知県・名古屋市）[11] 鈴木 隆元，田中 清史， 静的優先度ス
ケジューリングにおけるタスク分割によるジッタ削減の検討 ，情報処理学会第 79 回全国大会, 2017 年 3 月 16 日，名古屋大学（愛知県・名古屋市）[12] Tetsuo Miyauchi, Kiyofumi Tanaka, A
Framework for Automatic Generation ofApplication‑Specific
FPGA‑based
SoC, Workshop on Synthesis And System
IntegrationofMixed
Information
technologies, Oct 25, 2016, Kyoto (Japan).
[13] 鈴木 隆元，田中 清史， 仮想サーバによるタスクの応答時間短縮手法 ，情報処理学会組込みシステムシンポジウム，2016 年
10 月 22 日, 早稲田大学グリーン・コンピューティング・システム研究開発センター（東京都・新宿区）[14] 宮内 哲夫，田中 清史， アプリケーシ
ョンに適応した RTOS の細粒度コンフィギュ
レーション手法 ，情報処理学会組込みシス
テムシンポジウム，2016 年 10 月 22 日, 早稲
田大学グリーン・コンピューティング・シス
テム研究開発センター（東京都・新宿区）[15] Duy Doan, Kiyofumi Tanaka, Enhanced
Virtual Release Advancing for EDF‑based
Schedulingon
PreciseReal‑TimeSystems, International Conference on
Knowledge and Systems Engineering (KSE),
Oct 6, 2016, Hanoi (Vietnam).
[16] Tetsuo Miyauchi, Kiyofumi Tanaka,Configuration
Techniquefor
Adaptability of Multicore Processors on
FPGA, AnnualIEEEInternational
ConferenceonApplication‑specific
Systems, Architectures and Processors(ASAP), Jul 6, 2016, London (UK).
[17] Kiyofumi Tanaka, Kazuki Hasegawa,
Guaranteeing Schedulability with Server
Mechanisms for RTOS Processing andUtilizing Server Slack,
International
Conference on Computers and TheirApplications (CATA), April 6, 2016, Las
Vegas (USA).
[18] 宮内 哲夫，田中 清史， FPGA 用ソフト
プロセッサにおけるキャッシュメモリの適応的手法 ，情報処理学会第 78 回全国大会，
2016 年 3 月 10 日，慶應義塾大学（神奈川県・横浜市）[19] 森本 恵一，田中 清史， 実行時間予測による適応型リアルタイムスケジューリン
グ ，情報処理学会第 78 回全国大会，2016 年
3 月 11 日，慶應義塾大学（神奈川県・横浜市）[20] 鈴木 隆元，田中 清史， スラックを利用した実行権移譲スケジューリングアルゴ
リズム ，
情報処理学会第 78 回全国大会，
2016
年 3 月 11 日，慶應義塾大学（神奈川県・横浜市）[21] 宮内 哲夫，田中 清史， マルチプロセ
ッサの自動最適化環境の構築 ，情報処理学会組込みシステムシンポジウム，2015 年 10月 23 日，早稲田大学グリーン・コンピュー
ティング・システム研究開発センター（東京都・新宿区）[22] Kiyofumi Tanaka, Kazuki Hasegawa,Guaranteeing Schedulability with Server
Mechanisms for RTOS Overhead, Embedded
Operating Systems Workshop (EWiLi), Oct.
8, 2015, Amsterdam (Netherlands).
[23] 宮内 哲夫，田中 清史， FPGA を対象とした自動最適化によるマルチコアの実現 ，電気関係学会北陸支部連合大会，2015 年 9 月
13 日，金沢工業大学（石川県・金沢市）[24] 森本 恵一，田中 清史， 組込みアプリ
ケーションの実行時間予測 ，電気関係学会
北陸支部連合大会，2015 年 9 月 13 日，金沢工業大学（石川県・金沢市）[25] 長谷川 和輝，田中 清史， RTOS オーバ
ヘッドを考慮に入れたリアルタイムスケジューリング ，電気関係学会北陸支部連合大会，2015 年 9 月 13 日，金沢工業大学（石川県・金沢市）[26] Kiyofumi Tanaka,
Virtual Release
AdvancingforEarlier
Deadlines, Workshop on Adaptive andReconfigurable Embedded Systems (APRES),
Apr 13, 2015, Seattle (USA).
〔図書〕（計 0 件）〔産業財産権〕○出願状況（計 0 件）
○取得状況（計 0 件）
〔その他〕
ホームページ等

６．研究組織(1)研究代表者
田中 清史（TANAKA KIYOFUMI）
北陸先端科学技術大学院大学・先端科学技術研究科・准教授
研究者番号：20333445(2)研究分担者(3)連携研究者(4)研究協力者