SJF（処理時間順）方式

📌

SJF方式とは

SJF（Shortest Job First）方式とは、処理時間（＝CPUを使い続ける長さ）が短いタスクから先に実行するスケジューリング方式のことです。CPU（＝計算を担当する頭脳）にどのタスクを次に割り当てるかを決める順序づけの一つです。

身近な例で考えると、スーパーのレジに似ています。買い物カゴの中身が1〜2個だけの人を先に通すと、後ろに並ぶ大勢の待ち時間が一気に短くなります。逆に大量買いの人を先頭にすると、全員が長く待つことになります。

上のツールで▶ボタンを押すと、待ち行列のタスクを処理時間の短い順に並べ替え、B→D→A→Cの順で実行してガントチャートが組み上がる流れを確認できます。

🔀

短い処理を優先する仕組み

SJFの動きは単純です。CPUが空いたとき、待ち行列の中から残り処理時間がもっとも小さいタスクを選んで実行する、これだけです。

今回の例では、待ち行列にあるタスクの処理時間は次のとおりです。
・B：処理時間 2（最短）
・D：処理時間 3
・A：処理時間 6
・C：処理時間 8（最長）

この中から毎回いちばん短いものを選ぶので、実行順は B → D → A → C になります。途中で実行中のタスクを中断しない「非プリエンプティブ（横取りしない）SJF」と、より短いタスクが来たら中断する「プリエンプティブSJF（SRT）」があります。

📉

平均待ち時間の短縮効果

待ち時間とは、タスクが届いてから実際にCPUを使い始めるまで待たされた時間のことです。SJFは短いタスクを先に片付けるため、平均待ち時間が理論上もっとも短くなることが知られています。

SJF　B:0 D:2 A:5 C:11 → (0+2+5+11)/4 = 4.5
FCFS A:0 B:6 C:8 D:16 → (0+6+8+16)/4 = 7.5

同じ4つのタスクでも、到着順に処理するFCFS（先着順）では平均7.5、短い順のSJFでは平均4.5と、SJFの方が短くなりました。ただし良いことばかりではありません。
・処理時間の予測が必要：実行前に各タスクの長さを正確に見積もるのは難しい
・飢餓状態が起こりうる：短いタスクが次々来ると、長いタスクがいつまでも実行されない

上のツールの最後のステップで、SJFとFCFSの平均待ち時間を見比べてみてください。短い順に並べるだけで全体の待ち時間が縮む様子が分かります。

📌

飢餓状態——長いタスクが後回しになり続けるのはなぜか

SJFの最大の弱点が飢餓状態（スタベーション）です。これは処理時間の長いタスクが、次々と到着する短いタスクに割り込まれ続け、いつまでも実行されない状態のことです。

なぜ起きるのかというと、SJFは常に「今いる中でいちばん短いもの」を選ぶルールだからです。長いタスクCが待っているとき、それより短い新しいタスクが次々到着すると、Cは毎回後回しにされます。この状態がいつまでも続くと、Cは永遠に実行されません。レストランで「少ない注文のお客さんを先に」というルールで接客していると、注文の多いお客さんがずっと待たされるのと同じ状況です。

これを防ぐ工夫としてエイジング（aging）という方法があります。待ち時間が長くなるほど優先度を少しずつ上げていき、いつかは必ず実行されるようにするものです。長く待ったタスクを「年齢が上がったから優先」と考えるイメージです。

📌

SJFとFCFSの選び方

FCFSとSJFはどちらが「正解」ではなく、何を重視するかで使い分けるものです。それぞれの強みと弱みを整理しておきましょう。

「公平さ・シンプルさ → FCFS、平均待ち時間を短くしたい → SJF」と押さえておくと判断しやすいです。実際のOSは単純なFCFSやSJFだけでなく、優先度・ラウンドロビンなど複数の方式を組み合わせてバランスをとっています。FCFSとSJFはその基礎となる考え方として重要です。

🎯

基本情報技術者 練習問題