HOME IP Messenger FastCopy Tech-memo Diary Twitter [English]

Shortest Job First(SJF)と日常生活

白水啓章
作成 2010年頃?

概要

「SJF」 は、短いジョブ(タスク)から優先して処理する、OSスケジューリング用アルゴリズムの一つです。
これが意外と日常生活にも活用可能かも?というお話。

SJFで処理すると?

処理時間が違う4つのジョブ(タスク)が、ほぼ同時に到着したとします。

ジョブ名 処理時間
A 60分
B 3分
C 30分
D 1分

これらを上記の順番で処理したとすると 94分後に全ての処理を終えることになります。

A B C D 合計時間
60分 3分 30分 1分 94分後

短いジョブ優先の SJF方式(D,B,C,Aの順)で処理したとしても、同じく94分後に全ての処理を終えます。

D B C A 合計時間
1分 3分 30分 60分 94分後

待ち時間はどう変化したか?

各ジョブ開始までの待ち時間」を考えて見ます。

最初の処理方式では、

ジョブ名 待ち時間 処理時間
A 0分 60分
B 60分 3分
C 63分 30分
D 93分 1分

となり、(0+60+63+93)/4 = 54分が平均待ち時間となります。

それに対し、SJF方式では、

ジョブ名 待ち時間 処理時間
D 0分 1分
B 1分 3分
C 4分 30分
A 34分 60分

となり、(0+1+4+34)/4 = 9.75分が平均待ち時間となります。

つまり…

上記のように、SJF を使うと、全体の平均待ち時間が大きく改善することがわかります。
(なお、平均処理完了時間で比較しても、前者77分、後者33分となり、大きく改善します)

日常生活への活用

SJFを日常生活に活用する=下記のような法則になるかと思います。

複数の仕事/タスクを受けた場合早く終りそうな仕事から処理すると、平均の待ち時間を最小にしやすい

(ただし、待ち時間平均の最小化=価値最大化とは限らないので、念のため)

余談ですが、個人的には、病院などの待ち行列で活用してほしいアルゴリズムだったりします。
(定例通院で1分診療で終わると分かっていても、順番通りに1-2時間待たされる場面など)

図解

わかりやすい図があったので載せておきます。
SJF
図の引用元: https://scalingsoftwareagility.wordpress.com/2010/04/08/prioritizing-features/

備考

なお、大昔のバッチ処理全盛の時代とOSと違い、今時のOSでは
「ジョブ開始時に処理完了時間が判明しないこと」
「プリエンプティブ・マルチタスクであること」
という2点から、素のままの SJF を採用している例は、たぶん無いと思います。