【第5回】元東大教員から学ぶリアルタイムシステム「リアルタイムシステムのタスクモデル」

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

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

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

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

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

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

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

リアルタイムシステムのタスクモデル

今回はリアルタイムシステムのタスクモデルを紹介します．

このタスクモデルは，1973年にLiu and Laylandが「Scheduling Algorithms for Multiprogramming in a Hard- Real-Time Environment」という論文で提案しました．

最近のリアルタイムシステムの論文では，Liu and Layland's model（LiuとLaylandのモデル）と記載して引用しています．

この論文はとても有名なので，興味があれば是非読みましょう！

これから以下の項目を紹介します．

• LiuとLaylandのモデルで使われる記号
• スケジュール可能性解析を簡略化するための想定
• 周期タスクでよく使われる他のパラメータ

LiuとLaylandのモデルで使われる記号

記号	説明
\(\Gamma\)	タスクセット（周期タスクの集合）．
\(\tau_i\)	i番目の周期タスク．
\(\tau_{i,j}\)	タスク\( \tau_i\)のj番目のインスタンス（ジョブ）．
\(r_{i,j}\)	タスク\(\tau_i\)のj番目のジョブのリリース時刻．
\(\Phi_i\)	タスク\(\tau_i\)の位相．すなわち，最初のジョブのリリース時刻（\(\Phi_i=r_{i,1}\)）．
\(T_i\)	タスク\(\tau_i\)の周期．
\(C_i\)	タスク\(\tau_i\)の最悪実行時間．
\(D_i\)	タスク\(\tau_i\)の相対デッドライン．
\(d_{i,j}\)	タスク\(\tau_i\)のj番目のジョブの絶対デッドライン（\(d_{i,j}=\Phi_i+(j-1)T_i+D_i\)）．
\(s_{i,j}\)	タスク\(\tau_i\)のj番目のジョブの開始時刻．
\(f_{i,j}\)	タスク\(\tau_i\)のj番目のジョブの終了時刻．
\(U_i\)	タスク\(\tau_i\)のCPU利用率（\(U_i=\frac{C_i}{T_i}\)）．
\(n\)	タスクセット\(\Gamma\)のタスク数．
\(U\)	タスクセット\(\Gamma\)の合計CPU利用率（\(U=\sum_{i=1}^n U_i\)）．

スケジュール可能性解析を単純化するための想定

スケジュール可能性解析とは，タスクセットの全てのタスクがデッドラインまでに実行を完了できるかを起動前（オフライン）に判定する手法です．

例えば，ハードリアルタイムタスクだと実行中（オンライン）にデッドラインミスしてシステムに致命的な損害を与えるかどうかをオフラインで判定できます．

もしハードリアルタイムタスクのスケジュール可能性解析の結果，デッドラインミスすることがわかったら実行しない方が良いですよね！

ここで，周期タスク\(\tau_i\)が実行可能（feasible）というのは，\(\tau_i\)の全てのジョブがデッドラインまでに完了できることを意味します．

タスクセット\(\Gamma\)がスケジュール可能（schedulable）というのは，\(\Gamma\)にある全てのタスクが実行可能（feasible）であることを意味します．

スケジュール可能性解析を単純化するために以下の内容を想定します．

• A1：周期タスク\(\tau_i\)のジョブは一定の周期で起動する．2つの連続した起動の間の間隔\(T_i\)はタスクの周期である．
• A2：全ての周期タスク\(\tau_i\)のジョブは同じ最悪実行時間\(C_i\)を持つ．
• A3：全ての周期タスク\(\tau_i\)のジョブは同じ相対デッドライン\(D_i\)を持ち，周期\(T_i\)と同じである．
• A4：タスクセット\(\Gamma\)にある全ての周期タスクは独立している．すなわち，タスク間の依存関係やリソース制約がない．

A1とA2は不要な制限ではなく，実用的な想定です．

多くの制御アプリケーションでは，周期的な起動は一定の間隔で同じルーチンを実行することを要求します．

なので，\(T_i\)と\(C_i\)は各々のジョブで一定です．

また，A3とA4の制限を緩めることで，より実用的（汎用的）なケースになります．

具体的には，A3では相対デッドラインが周期より短い場合，A4ではタスク間の依存関係やリソース制約がある場合を想定します．

追加で，以下の内容も暗黙的に想定します．

• A5：タスクはI/O処理などで自分自身を中断できない．
• A6：全てのタスクは到着したらリリースされる．
• A7：カーネルの全てのオーバヘッドは0と想定する．

A5，A6，A7の制限を緩める場合もありますが，今後の応用編で解説します．

まずは，A5，A6，A7の制限を満たす基本から学びましょう．

これらのケースでは，A1，A2，A3，A4を満たす場合，周期タスク\(\tau_i\)は以下の3つのパラメータを持ちます．

• \(\Phi_i\)：位相
• \(T_i\)：周期
• \(C_i\)：最悪実行時間

周期タスクのセットは以下のように示します．

$$\Gamma = \{\tau_i(\Phi_i,T_i,C_i), i = 1, ..., n\}$$

タスク\(\tau_i\)のk番目のジョブのリリース時刻\(r_{i,k}\)と絶対デッドライン\(d_{i,k}\)は以下のように示します．

\begin{eqnarray}
r_{i,k}&=&\Phi_i+(k-1)T_i \\
d_{i,k}&=&r_{i,k}+T_i=\Phi_i+kT_i
\end{eqnarray}

周期タスクでよく使われる他のパラメータ

タスクセットにある周期タスクの性質を示す他のパラメータとして以下が挙げられます．

• ハイパーピリオド（Hyperperiod）
• ジョブの応答時間（Job Response Time）
• タスクの応答時間（Task Response Time）
• タスクのクリティカルインスタント（Critical Instant）
• タスクのクリティカルタイムゾーン（Critical Time Zone）
• タスクの相対開始ジッタ（Relative Start Time Jitter）
• タスクの絶対開始ジッタ（Absolute Start Time Jitter）
• タスクの相対終了ジッタ（Relative Finishing Jitter）
• タスクの絶対終了ジッタ（Absolute Finishing Jitter）

ハイパーピリオド（Hyperperiod）

ハイパーピリオドは，スケジュールを繰り返すまでの間隔の最小値です．

Hが間隔の長さの場合，区間\([0, H)\)のスケジュールは\([kH, (k+1)H) (kは自然数)\)と同じになります．

周期タスクのセットは時刻\(t=0\)に同期して起動しますので，ハイパーピリオドは全てのタスクの周期の最小公倍数になります．

$$H=\operatorname{lcm}(T_1,...,T_n)$$

ジョブの応答時間（Job Response Time）

ジョブの応答時間は，ジョブがリリースしてから終了するまでの時間です．

$$R_{i,k}=f_{i,k}-r_{i,k}$$

タスクの応答時間（Task Response Time）

タスクの応答時間は全てのジョブの応答時間の最大値です．

$$R_i=\underset{k}{\max}\ R_{i,k}$$

タスクのクリティカルインスタント（Critical Instant）

タスクのクリティカルインスタントは，タスクの応答時間が最大値になる時刻のことです．

タスクセットに周期タスクしかない場合では，システムの起動時刻（\(t=0\)）がタスクのクリティカルインスタントになります．

非周期タスク（周期処理をしないタスク）がある場合は，システムの起動時刻がタスクのクリティカルインスタントになるとは限りません．

こちらの内容は，今後詳しく説明します．

タスクのクリティカルタイムゾーン（Critical Time Zone）

タスクのクリティカルゾーンは，タスクのクリティカルインスタントと応答時間の間にある間隔のことです．

タスクの相対開始ジッタ（Relative Start Time Jitter）

タスクの相対開始ジッタは2つの連続したジョブの開始時刻の最大偏差です．

$$RSJ_i=\underset{k}{\max}|(s_{i,k+1}-r_{i,k+1})-(s_{i,k}-r_{i,k})|\ (kは自然数)$$

タスクの絶対開始ジッタ（Absolute Start Time Jitter）

タスクの絶対開始ジッタは全てのジョブの開始時刻の最大偏差です．

$$ASJ_i=\underset{k}{\max}(s_{i,k}-r_{i,k}) - \underset{k}{\min}(s_{i,k}-r_{i,k})\ (kは自然数)$$

タスクの相対終了ジッタ（Relative Finishing Time Jitter）

タスクの相対終了ジッタは2つの連続したジョブの終了時刻の最大偏差です．

$$RFJ_i=\underset{k}{\max}|(f_{i,k+1}-r_{i,k+1})-(f_{i,k}-r_{i,k})|\ (kは自然数)$$

タスクの絶対終了ジッタ（Absolute Finishing Time Jitter）

タスクの絶対終了ジッタは全てのジョブの終了時刻の最大偏差です．

$$AFJ_i=\underset{k}{\max}(f_{i,k}-r_{i,k}) - \underset{k}{\min}(f_{i,k}-r_{i,k})\ (kは自然数)$$

まとめ

リアルタイムシステムのタスクモデル「LiuとLaylandのモデル」を紹介しました．

具体的には，以下の内容になります．

• LiuとLaylandのモデルに使われる記号
• スケジュール可能性解析を単純化するための想定
• 周期タスクでよく使われる他のパラメータ

今後は，このタスクモデルを引用して説明しますので，きちんと理解しましょう！

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

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

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

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

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