[OS] 證明：Shortest Job First [SJF] is the optimal scheduling algorithm

修改自 http://computing.dcu.ie/~humphrys/Notes/OS/processes.html

What is the optimal schedule?

In general, if in-order bursts are x1, x2, ..., xn, then:

For each dispatched process, waiting time = (好像計網概題目XD)
1st: 0
2nd: x1
3rd: x1 + x2
4th: x1 + x2 + x3
...
nth: x1 + x2 + ... + xn-1

=> Total waiting time
= (n-1) x1 + (n-2) x2 + ... + (2) xn-2 + (1) xn-1 + (0) xn

Obviously this sum is minimized if the xi's that are multiplied the most times are the smallest ones, i.e., x1 < x2 < ... < xn-1 < xn.
Thus, in non-preemptive scheduling, "Shortest Job First" (actually Shortest Next CPU burst) is optimal for the purpose of minimizing Average Waiting Time. #

算是個淺顯又不失嚴謹的證明法 希望有幫助囉^^
P.S.王家祥老師說他喜歡考這個。