速く終わることと、早く反応すること
サーバーが三つの仕事A、B、Cを処理します。到着時刻は順に0、1、2、必要なCPU時間は5、2、1です。CPUは一つで、今回の模型ではI/O待ちと切替費用を0とします。同じ総仕事量8でも、実行する順番によって各仕事が初めて動く時刻と完了時刻は変わります。最初に反応するまでを応答時間、到着から完了までをターンアラウンド時間として、別の値で追います。
実製品の応答時間は、通信や待ち行列、外部サービスを含む場合があります。ここではCPUスケジューリングの指標として範囲を限定します。平均が小さければ全ての仕事が快適とも限りません。長い仕事が待ち続けるか、短い仕事がすぐ開始できるか、期限のある仕事をいつまでに終えるかなど、選ぶ目的を先に明示します。単一の速さという言葉で評価を一つにしないことが、この教材の出発点です。
到着順では短い仕事も後ろへ並ぶ
FCFSではAが0〜5、Bが5〜7、Cが7〜8を使います。応答時間はAが0、Bが4、Cが5です。ターンアラウンドはAが5、Bが6、Cが6になります。BとCはCPU時間が短くても、既に動くAの後ろへ並びます。待ち時間の増加が、実行そのものの遅さと同じではないことが分かります。CPUが一度も空いていなくても、短い要求への最初の反応が遅れる場合があります。
非プリエンプティブな最短仕事優先では、最初に到着したAは途中で止めず、5の時点で待っているC、Bの順へ進みます。応答時間はAが0、Cが3、Bが5、完了までの時間はAが5、Cが4、Bが7です。新しい短い仕事が来るたびに今の仕事を止める方式とは違います。必要CPU時間を事前に知る仮定もあるため、この模型の選択を現実へ移すなら予測や分類の誤差を考えます。
時間片で最初の機会を分ける
時間片2のラウンドロビンでは、ここでは時刻2までの到着を再投入するAより先へ並べます。履歴はAが0〜2、Bが2〜4、Cが4〜5、Aが5〜7、Aが7〜8です。応答時間はAが0、Bが1、Cが2となり、最初の実行機会を早く分けられます。一方Aの完了は8へ遅れます。全員に最初の機会を与える目標と、最初の長い仕事を早く終える目標は同じではありません。
境界と同時刻の到着をどこへ入れるか、時間片を使い切らず終了した仕事をどう外すかを明示します。この規則が曖昧だと、同じ入力から異なる履歴が作られます。掲載したAの連続する二つの区間も、最後に他の実行可能な仕事がなくなった結果です。実CPUで同じプロセスが続く場合の切替処理まで、この区間表が測定したと解釈しないでください。ここでは比較用の決定的なスケジュールを使います。
| 方針 | A:応答 / 完了まで | B:応答 / 完了まで | C:応答 / 完了まで |
|---|---|---|---|
| FCFS | 0 / 5 | 4 / 6 | 5 / 6 |
| 非プリエンプティブSJF | 0 / 5 | 5 / 7 | 3 / 4 |
| RR、時間片2 | 0 / 8 | 1 / 3 | 2 / 3 |
履歴から指標を計算するコード
コードは三つの固定履歴を使い、各仕事へ割り当てた実行区間の長さが必要CPU時間と一致することをassertします。その後、各仕事の最初の開始と最後の終了を取り、到着時刻との差から二つの指標を出します。RRの応答0、1、2も検査します。OSのスケジューラを制御した実験ではなく、同じ仮定の履歴から指標を計算する模型です。実行出力を実機のスケジューラ性能として掲載しません。
手計算では平均も出せますが、仕事ごとの値を消さずに残します。FCFSの平均応答は3、今回のRRは1です。一方ターンアラウンドはFCFSで17/3、RRで14/3となります。この三件の結果だけで、任意の到着列へ同じ順位が成り立つとは結論できません。比較では到着、仕事量、時間片、境界規則、切替費用という入力を一緒に保存し、指標の名前と計算区間を対応させます。
from collections import deque
jobs={'A':(0,5),'B':(1,2),'C':(2,1)}
def report(trace):
first={};last={}
for start,end,name in trace:first.setdefault(name,start);last[name]=end
return {name:{'response':first[name]-arrival,'turnaround':last[name]-arrival} for name,(arrival,work) in jobs.items()}
fcfs=[(0,5,'A'),(5,7,'B'),(7,8,'C')]
sjf=[(0,5,'A'),(5,6,'C'),(6,8,'B')]
rr=[(0,2,'A'),(2,4,'B'),(4,5,'C'),(5,7,'A'),(7,8,'A')]
for name,trace in [('FCFS',fcfs),('nonpreemptive SJF',sjf),('RR q2',rr)]:
for key,(arrival,work) in jobs.items():assert sum(end-start for start,end,k in trace if k==key)==work
print(name,report(trace))
assert [report(rr)[k]['response'] for k in jobs]==[0,1,2]
print('fixed schedules; zero switch cost; no real OS scheduler measurement')
時間片を短くすれば常に良いわけではない
模型では切替費用を0にしましたが、実際には状態の保存と復元、実行の局所性などが関係します。時間片を極端に短くして切替ばかりになると、利用者の仕事へ使える時間の割合が下がる場合があります。逆に長くすれば、短い仕事が最初の機会を得るまでの時間が増えます。時間片と切替費用の比を考えず、「細かく分けるほど公平で速い」とまとめないでください。
優先度を設ける場合も、優先度の低い仕事を永久に後ろへ送らない工夫が必要になることがあります。待ち続けた時間を考慮する案や、資源の配分割合を制御する案など、要求する保証へ応じて選びます。締切を扱う方式では、到着だけでなく残り仕事量と期限が新たな入力です。ここでの三つの基本方式は、全てのリアルタイム性や優先度逆転を解決する機能ではありません。既存の飢餓や優先度逆転の記事へ戻って条件を分けます。
待つ理由を分類して観測する
実際のアプリが遅い場合、CPUの実行待ちなのか、ロックを待つのか、I/Oの完了を待つのかを分けます。CPU時間が短く経過時間だけ長い仕事を、必要CPU時間の長い仕事と同じ入力へ置くと、模型の意味が変わります。スレッドプールの待ち行列やDB接続待ちも、OSの実行可能な仕事の列とは別です。複数の待ち場所を一つの待ち時間へ集計する前に、どの層の順番を変えられるかを考えます。
観測では到着、受付、実行開始、外部待ち、完了などの時刻へ印を付けます。時計の範囲や単位を揃え、複数プロセスの壁時計を無条件に同じ順序の証拠としません。模型で定義した応答時間を、製品での最初のHTTPバイトの時刻などへ対応させるなら、その対応を説明します。計算した指標と利用者が感じる待ち時間の間にどの層が入るかを明らかにすると、必要な改善を選びやすくなります。
総仕事量が同じでも、待ちの配分が変わる
三方式のCPU仕事量は全て8です。今回のゼロ切替費用なら、最後の仕事が終わる時刻も8ですが、途中の応答と完了の配分が変わります。この例を見て、RRが総CPU仕事を減らしたと説明しないでください。入力の実行時間を勝手に小さくしたのではなく、誰にいつ時間を渡すかを変えました。全仕事の最終完了時刻と、各要求の待ち時間は別の目的です。
仕事の間にI/Oが加われば、別の仕事へCPUを渡して待ちと計算を重ねられる場合があります。そのときは、CPU要求量だけの三つの数では履歴を作れません。各仕事が実行可能、実行中、外部待ちのどこにあるかを新しい状態として加えます。もとの模型でCPUが常に埋まったことを、I/Oを含む仕事でも保証したと広げないようにします。モデルへ入れていない待ちを、結果の解釈だけで後から足さないことが重要です。
仕事の短さを事前に知るという条件も確認します。実際に必要なCPU時間を常に正確に予言できるという前提ではありません。
必要時間を知らない場合の予測
最短仕事優先の例は、各仕事の必要CPU時間を知る前提を使いました。実際には過去の履歴や要求の種類から予測する場合があり、その予測が外れると短いはずの仕事が長く枠を使うことがあります。真の仕事量を先に知る模型と、推定を使う実装の結果を同じものとして比較しません。予測値と実際の量を両方残し、分類の誤りが待ちへどう影響したかを調べます。
長い仕事が次々と来る短い仕事へ追い越される状況では、平均の改善と一部の飢餓が両立する場合もあります。待ち時間の上限や最低限の進行が必要かを先に決めます。今回の三仕事は有限で全て終わるので、無限に到着する仕事の下での飢餓を実証した試験ではありません。固定例、予測する方式、長期の公平性を別の問いにし、それぞれの成立条件に合う検査を用意してください。
違う目的で選ぶ課題
課題は今回の三仕事について、最初の実行機会を早く分けたい場合と、Aだけを最初に終えたい場合の選択を説明することです。解答では、ゼロ切替費用の今回の模型で前者にRR、後者ならAを途中で止めない方式が候補になります。ただし、平均値だけで全利用者の満足を証明せず、各仕事の応答と完了を表へ示してください。方式の名称より、その履歴から何が変わるかが大切です。
追加課題は切替一回に0.5の時間がかかるとした場合です。以前の区間をそのまま使うと、後続の開始と同時刻の到着の関係も変わり得るため、切替をどこへ入れるかを定めて履歴を再構築します。総仕事量8へ何を加えるか、同じ仕事が続く境界でも切替と数えるかも明示します。元の平均値へ適当な定数だけを加えず、仮定、履歴、指標を一式で更新してください。