【第11回】元東大教員から学ぶリアルタイムシステム「RMとEDFの比較」

こういった私から学べます．

前回を読んでいない方はこちらからどうぞ．

リアルタイムシステムの記事一覧はこちらからどうぞ．

リアルタイムシステムで使われているリアルタイムOSは，主にC言語で書かれています．

私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．

私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！

独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！

RMとEDFの比較

今回は，Rate Monotonic（RM）とEarliest Deadline First（EDF）スケジューリングを比較します．

独立したプリエンプティブな周期タスクセットのスケジューリングの問題は，RMに代表される固定優先度スケジューリングとEDFに代表される動的優先度スケジューリングによって解決されました．

リアルタイムOSやリアルタイムLinuxにおける固定優先度と動的優先度スケジューラの実装を比較します．

固定優先度スケジューリングの利点は，実装がシンプルなことです．

実際，レディーキュー（実行可能状態のタスクを扱うキュー）が優先度レベルを\(P\)個持つ優先度キューによって実装されている場合，タスクの挿入と削除は\(\mathcal{O}(1)\)の計算量で実現できます．

他方，動的優先度スケジューラでは，レディーキューのベストな実装方法は，ヒープキュー（例：平衡木）を利用することです．

ヒープキューはタスク操作に\(\mathcal{O}(\log n)\)の計算量が必要になります．

※Linuxは赤黒木という平衡木でレディーキューを実装しています．

とても多くのタスク数を持つタスクセットや，とても遅いCPUに強く関連する実装上の課題を除いては，動的優先度スケジューラは固定優先度スケジューラと比較して多くの利点があります．

詳細はButtazzoの論文に記載してあります．

スケジュール可能性解析の観点からは，RMの正確な必要十分条件のテストには，準多項式の計算量が必要になります（DMの応答時間解析をRMに適用）．

これに対して，EDFは\(\mathcal{O}(n)\)の計算量でスケジュール可能性解析ができます．

一般的には，相対デッドラインが周期より短いか同じ場合のタスクセットにおいて，固定優先度スケジューリング（DM）と動的優先度スケジューリング（EDF）の両方とも準多項式の計算量が必要になります．

固定優先度スケジューリングは応答時間解析，動的優先度スケジューリングはProcessor Demandを使います．

CPU利用率において，EDFは100%利用することができますが，RMは最悪の場合69%以下のCPU利用率しかタスクセットのスケジュール可能性を保証することができません．

平均の場合では，Lehoczkyらはランダムなパラメータで生成されたタスクセットにおいて，RMは最大88%までタスクセットがスケジュール可能であることを示しました．

しかし，この結果は統計に基づくもので，正確な保証テストによる絶対的な上限ではないことに注意して下さい．

各々のジョブの起動で絶対デッドラインを更新するためにEDFは別に計算処理が必要になるにも関わらず，EDFはRMよりコンテキストスイッチが発生する際のオーバヘッドが小さいです．

実際，固定優先度スケジューリングを強制するために，RMはEDFよりプリエンプションの数が多くなります．

永久的な過負荷におけるEDFの面白い性質は，周期を変更することで，タスクは長い間隔で実行しているかのように振る舞うことです．

この性質は，Cervinの博士論文の下記の定理で証明されています．

定理11.1：\(n\)個の周期タスクセットにおいて，各々のタスクは固定された周期\(T_i\)，固定された最悪実行時間\(C_i\)，相対デッドライン\(D_i\)，リリースの位相\(\Phi_i\)により表現されるとする．\(U > 1\)かつタスクがEDFでスケジュールされる場合，定常性において，各々のタスク\(\tau_i\)の平均周期\(\overline{T_i}\)は\(\overline{T_i} = T_iU\)になる．

ここで，固定優先度スケジューリングにおいて，永久的な過負荷は低優先度タスクの完全なブロッキングを引き起こすことに注意して下さい．

固定優先度スケジューリングに対する動的優先度スケジューリングの利点は，非周期タスクを扱う場合に応答時間が短くなることです．（詳細は後の回で解説します．）

この理由は，EDFのスケジュール可能上限が高いからです．

実際，RMのスケジュール可能上限は低いので，非周期タスクの最大CPU利用率（\(U_s = C_s / T_s\)）は周期タスクのスケジュール可能性が保証できる範囲内でしか非周期サーバ（非周期タスクの実行時間を確保するために振る舞うタスク）を割り当てることができません．

結果として，非周期サーバに割り当てることができなくなった余ったCPU利用率はバックグラウンドの実行になるので，無駄になってしまいます．

EDFではこの問題が発生しません．

その理由は，\(U_p\)が周期タスクのCPU利用率の場合，残りの全てのCPU利用率\(1 - U_p\)が非周期サーバに割り当てることができるからです．

RMとEDFのシミュレーション評価

RMとEDFのスケジュール可能性を確認するため，シミュレーション評価を行います．

タスク\(\tau_i\)のパラメータと範囲は以下になります．

タスク\(\tau_i\)	範囲
タスクの周期\(T_i\)	[100, 200, 300, ..., 3000]
タスクのCPU利用率\(U_i = C_i / T_i\)	[0.02, 0.03, 0.04, ..., 0.25]

タスクセット\(\Gamma\)のCPU利用率\(U = \Sigma_i U_i\)が[0.6, 0.65, 0.7, ..., 1.0]となるようにタスクを生成します．

CPU利用率毎のタスクセット数はそれぞれ1,000（合計9,000），シミュレーションの長さはタスクセットのハイパーピリオド（最小公倍数）とします．

評価指標はスケジュール成功率（Success Ratio）とし，CPU利用率毎に評価します．

$$スケジュール成功率 = \frac{スケジュールが成功したタスクセット数}{スケジュールしたタスクセットの数}$$

上図にRMとEDFのシミュレーションの結果を示します．

CPU利用率が75%まではRMとEDFの両方ともスケジュール成功率が100%を維持しています．

CPU利用率が80%以上になるとRMのスケジュール成功率が低下し，CPU利用率が100%の時にスケジュール成功率が0%になってしまいます．

これに対して，EDFはCPUが100%でもスケジュール成功率が100%であることがわかります．

このように，シミュレーションでRMとEDFのスケジュール可能上限の関係を確認できました．

元東大教員による見解

ここから，元東大教員の私によるRMとEDFの議論に関する見解を述べます．

RMとEDFの議論が有用なのは，シングルプロセッサやマルチコアプロセッサ（コア数が2～16）の時代に場合においてのみでした．

昨今は，コンピュータの進歩により，リアルタイムシステムにおいてもメニーコアプロセッサ（コア数が16～）を導入することが主流になりつつあります．

例えば，代表的なメニーコアプロセッサは以下になります．

• Intel Xeon Platinum 8380：基本2.3GHz（最大3.4GHz），40コア/80スレッド
• AMD EPYC 7763：基本2.45GHz（最大3.5GHz），64コア/128スレッド
• ARM Altra MAX M128-30：基本2.8GHz（最大3.0GHz），128コア
• MPPA3-80 Coolidge：基本600MHz（最大1.2GHz），80コア

このような場合，タスクセットをスケジューリングする必要はあるのでしょうか？

実際，ロボットのような複雑なリアルタイムシステムでも数個～数十個程度しかリアルタイムスケジューリングでスケジュールするタスクは存在しません．

なので，現在のメニーコアプロセッサを搭載するリアルタイムシステムでは，RMとEDFのどちらのスケジューリングが良いかというよりは，1コアに1タスクのみを専有実行するのが現実的ではないでしょうか？

余ったコアでリアルタイム性を保証する必要がないノンリアルタイム処理を実行すれば良いと思います．

もちろん，Raspberry Pi 4に搭載されているARM Cortex-A72マルチコアプロセッサ（4個のコアを搭載）もまだまだ主流なので，RMやEDFスケジューリングは必要になります．

ですが，利用するシステムやコア数においては，RMやEDFスケジューリングが不要になる可能性があることを覚えておいて下さい．

リアルタイムシステムでリアルタイムスケジューリングを使うことは一つの手段でしかないことです．

参考までに，RMやEDFを含むマルチコアプロセッサ向けスケジューリングのシミュレータはSimSoがおすすめです！

まとめ

今回は，RMとEDFスケジューリングの比較を解説しました．

具体的には，以下の内容を解説しました．

• RMがEDFより優れている点
  • 実装がシンプルなことのみ
• EDFはRMより優れている点
  • CPU利用率の上限が高いこと（100%）
  • オーバヘッドが小さいこと
  • プリエンプション数が少ないこと
  • 永久的な過負荷における耐性が高いこと

C言語でLinuxにおけるリアルタイムスケジューリングRMとEDFの実装を知りたいあなたはこちらからどうぞ．

リアルタイムシステムで使われているリアルタイムOSは，主にC言語で書かれています．

私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．

私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！

独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！

次回はこちらからどうぞ．