REAL-TIME SYSTEMS TECHNOLOGY

【第17回】元東大教員から学ぶリアルタイムシステム「Slack Stealing」

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

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

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

第16回リアルタイムシステム
【第16回】元東大教員から学ぶリアルタイムシステム「Sporadic Server」

こういった私から学べます. 前回を読んでいない方はこちらからどうぞ. リアルタイムシステムの記事一覧はこちらからどうぞ. 目次1 Sporadic Server(SS)2 SSのスケジュール可能性解析 ...

続きを見る

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

リアルタイムシステム
元東大教員から学ぶリアルタイムシステム

こういった私から学べます. リアルタイムシステムとは,決められた時間(デッドライン)までに処理を完了しなければならない性質をもつシステムのことです. リアルタイムシステムは,ロボット,自動車や航空機な ...

続きを見る

Slack Stealing

Slack Stealingは,LehoczkyとRamos-Thuelにより提案された非周期サーバで,以前に紹介した非周期サーバ(PE,DS,SS)より応答時間を実質的に向上させることができます.

これらの非周期サーバとは異なり,Slack Stealingは非周期タスクのための周期サーバを作成しません.

むしろ,Slack StealingはSlack Stealerと呼ばれる受動タスクを生成します.

Slack Stealerは,周期タスクのデッドラインミスを引き起こさない範囲内で,周期タスクから全ての実行時間を盗んで,非周期タスクの実行時間を生成することを試みます.

これは,周期タスクからスラックを盗むことに相当します.

もし\(c_i (t)\)が時刻\(t\)における残り実行時間の場合,タスク\(\tau_i\)のスラックは下式になります.

$$slack_i (t) = d_i - t - c_i (t)$$

Slack Stealingの主なアイデアは,周期タスクの早期終了において何も利益がないことです.

非周期タスクが到着した時,Slack Stealerは周期タスクからの全ての利用可能なスラックを盗み,できるだけ早く非周期タスクの実行にスラックを使います.

もし非周期タスクがない場合,周期タスクはRMでスケジュールされます.

Example of Slack Stealer Behavior

上図に2つの周期タスクのSlack Stealerの振る舞いを示します.

タスク\(\tau_1\)と\(\tau_2\)は周期\(T_1=4\),\(T_2=5\),最悪実行時間\(C_1=1\),\(C_2=2\)を持ちます.

具体的には,上図の上部は非周期タスクがない場合のRMのスケジュールを示します.

上図の下部は時刻\(t=8\)で最悪実行時間が3の非周期タスクが到着し,すぐに実行するケースを示します.

このケースでは,最悪実行時間が3のスラックはタスク\(\tau_1\)と\(\tau_2\)の3番目のジョブを遅延することで獲得します.

上図の例では,他の非周期サーバ(PS,DS,PE,SS)は最高優先度で非周期タスクをスケジュールする場合,周期タスクのリアルタイム性を保証することができないことに注意して下さい.

例えば,\(U_1=1/4\),\(U_2=2/5\)なので,タスクセットの\(P\)は\(P=7/4\)になります.

したがって,式\((16.1)\)によると非周期サーバSSの最大CPU利用率は下式になります.

$$U_{SS}^{max} = \frac{2}{P} - 1 = \frac{1}{7} \simeq 0.14$$

\(C_s=1\)の場合,最短の非周期サーバの周期は\(T_s=\lceil C_s / U_s \rceil =7\)なので,両方の周期タスクの周期より長くなります.

非周期サーバの実行は,バックグラウンドサービスに相当するので,非周期タスクは時刻\(t=15\)に終了します.

Slack Stealingのスケジュール可能性解析

Slack Stealingで非周期タスク\(J_a (r_a, C_a)\)をスケジュールするためには,区間\([r_a, t)\)において少なくとも\(C_a\)のスラックが利用可能な最短時刻\(t\)を定める必要があります.

スラックの算出はスラック関数\(A(s, t)\)を利用して実行します.

スラック関数\(A(s, t)\)は周期タスクのスケジュール可能性を低下しない範囲内で区間\([s, t)\)における非周期タスクに割り当て可能な計算時間の最大値を返します.

Slack Function at Time s=0 for Periodic Task Set

上図に前の例で利用した周期タスクセットの時刻\(s=0\)におけるスラック関数を示します.

\(s\)において,\(A(s, t)\)はハイパーピリオド毎に定義される非減少のステップ関数で,スラックが利用可能な区間の最初に対応するジャンプ地点を持ちます.

\(s\)が変化するにつれて,スラック関数は再計算する必要があります.

なので,特に長いハイパーピリオドの時に相対的に多くの計算時間を必要とします.

Slack Function at Time s=6 for Periodic Task Set

上図にスラック関数\(A(s, t)\)が同じ周期タスクセットで時刻\(s=6\)の場合にどのように変化するのかを示します.

LehoczkyとRamos-Thuelが提案したオリジナルのSlack Stealerによると,スラック関数は時刻\(s=0\)であらかじめ計算し,テーブルに保存します.

実行時は,実際のスラック関数\(A(s, t)\)が,周期タスクの実行時間,非周期サーバの実行時間,アイドル時間をベースに\(A(0, t)\)を更新することで算出されます.

テーブルから現在のスラックを算出する計算量は\(\mathcal{O}(n)\)で,\(n\)は周期タスクの数になります.

しかし,タスクの周期に依存して,テーブルのサイズは実際の実装ではとても大きくなります.

Slack Stealingは以下の定理を証明しています.

定理17.1:固定優先度でスケジュールされるあらゆる周期タスクセットとFirst-In First-Out(FIFO)の順番で実行するあらゆる非周期タスクにおいて,Slack Stealingは全ての周期タスクがデッドラインまでに終了する範囲内で,あらゆる非周期タスクの応答時間を最も短くする(証明は省略).

まとめ

今回は,非周期サーバSlack Stealingを紹介しました.

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

  • Slack Stealingの特徴
  • Slack Stealingのスケジュール可能性解析

Slack Stealingは,固定優先度でスケジュールされる周期タスクがデッドラインミスしない範囲内で,最も応答時間を短くできることがわかりました.

最後まで読んで頂きありがとうございました.

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

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

友だち追加

独学が難しいあなたは,C言語を学べるおすすめのオンラインプログラミングスクール4社で自分に合うスクールを見つけましょう.

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

第18回リアルタイムシステム
【第18回】元東大教員から学ぶリアルタイムシステム「固定優先度の非周期サーバのまとめ」

こういった私から学べます. 前回を読んでいない方はこちらからどうぞ. リアルタイムシステムの記事一覧はこちらからどうぞ. 目次1 最適な固定優先度の非周期サーバは存在しない2 固定優先度の非周期サーバ ...

続きを見る

-REAL-TIME SYSTEMS, TECHNOLOGY
-, , , , , , , , , , , , , , , , , , , , , , , , , ,