Shortest Job First(SJF)と実生活

たぶん2010年くらいに書いた H.Shirouzu

「Shortest Job First(SJF)は、OSのプロセススケジューリング用アルゴリズムの一つ
ですが、意外と実生活にも活用可能かも?というお話です。

まず、ジョブを一つづつしか処理できないマシンに対して、処理完了時間が、
 60分のジョブA、3分のジョブB、30分のジョブC、1分のジョブD の4つが
ほぼ同時に到着したとします。(なおI/O時間等は無視)

これらを上記の順番で処理したとすると、
 60 + 3 + 30 + 1 = 94分後
にすべての処理を終えることになります。

短いジョブ優先の SJF方式(D,B,C,Aの順)で処理したとしても、
 1 + 3 + 30 + 60 = 94分後
にすべての処理を終えることになり、その点までは全く一緒です。


このとき、各ジョブ開始までの平均待ち時間を考えて見ます。
最初の処理方式では、
 ジョブA =  0分
 ジョブB = 60分(60)
 ジョブC = 63分(60+3)
 ジョブD = 93分(60+3+30)
となり、(0+60+63+93)/4 = 54分が平均待ち時間となります。

それに対し、SJF方式では、
 ジョブD =  0分
 ジョブB =  1分(1)
 ジョブC =  4分(1+3)
 ジョブA = 34分(1+3+30)
となり、(0+1+4+34)/4 = 9.75分が平均待ち時間となります。

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


さて、これを日常生活に応用すると、
お客さんや他のメンバが、受付開始や処理完了を待っているような仕事については、
 (入れ替え可能な仕事の場合は)早く終わりそうなものから処理すると、平均の
 お待たせ時間を最小にしやすい」という話になります。
(ただし、待たせる時間平均を最小にすることが、そのまま顧客満足度の合計を最大
 にすることに等しいとは限らないので、念のため)

余談ですが、個人的には、病院などの待ち行列で病院側に活用してほしいアルゴリズム
だったりします。

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



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