Tag Archive 'CPU Scheduling'

Posted By Mr. Thursday 如果今天有一台機器,N個人要用,每個人使用的時間分別是t1, t2, …, tn,那麼怎樣子才能讓等待的時間最少呢?如果是以每個人的角度來說的話,當然是先搶先贏啦!不過如果是以這N個人所屬機構的角度來看,要讓全部人的等待時間最少,要如何安排使用機器的順序呢?這個時候作業系統 (OS: Operating System) 裡面的CPU Scheduling方法,就可以參考了! 首先我們先看看N個人不同的先後順序有幾種組合呢?答案是N!(N階層)種組合,譬如說5個人先後順序的組合方法就有5! = 120種組合,裡面包括第一個人先、然後第二個人、第三個人、第四個人、第五個人執行,也包括第一個人先、然後第三個人、第四個人、第五個人、最後才是第二個人執行,以及更多種組合的方法。因此我們排程的解答,就是在這麼多種組合(N!種)裡面,找到一個執行的順序,大家等待的時間加總起來是最小的。然而要怎麼找到這個解答呢?

Read Full Post »