本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Assembler (x64，ARM)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
こういった私から学べます．
前回を読んでいない方はこちらからどうぞ．
リアルタイムシステムの記事一覧はこちらからどうぞ．
リアルタイムシステムで使われているリアルタイムOSは，主にC言語で書かれています．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
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\)は下式になります．
$$slack_i (t) = d_i - t - c_i (t) \tag{17.1}$$
Slack Stealingの主なアイデアは，周期タスクの早期終了において何も利益がないことです．
非周期タスクが到着した時，Slack Stealerは周期タスクからの全ての利用可能なスラックを盗み，できるだけ早く非周期タスクの実行にスラックを使います．
もし非周期タスクがない場合，周期タスクはRMでスケジュールされます．
上図に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)\)における非周期タスクに割り当て可能な計算時間の最大値を返します．
上図に前の例で利用した周期タスクセットの時刻\(s=0\)におけるスラック関数を示します．
\(s\)において，\(A(s, t)\)はハイパーピリオド毎に定義される非減少のステップ関数で，スラックが利用可能な区間の最初に対応するジャンプ地点を持ちます．
\(s\)が変化するにつれて，スラック関数は再計算する必要があります．
なので，特に長いハイパーピリオドの時に相対的に多くの計算時間を必要とします．
上図にスラック関数\(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言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
次回はこちらからどうぞ．
