C語言中文網
首頁 > 編程筆記 > 操作系統筆記 閱讀:2,487

先來先服務調度(FCFS)算法及優缺點

毫無疑問,最簡單的 CPU 調度算法是先來先服務(FCFS)調度箅法。釆用這種方案,先請求 CPU 的進程首先分配到 CPU。

FCFS 策略可以通過 FIFO 隊列容易地實現。當一個進程進入就緒隊列時,它的 PCB 會被鏈接到隊列尾部。當 CPU 空閑時,它會分配給位于隊列頭部的進程,并且這個運行進程從隊列中移去。FCFS 調度代碼編寫簡單并且理解容易。

FCFS 策略的缺點是,平均等待時間往往很長。假設有如下一組進程,它們在時間 0 到達,CPU 執行長度按 ms 計:

進程 執行時間
P1 24
P2 3
P3 3

如果進程按 P1、P2、P3 的順序到達,并且按 FCFS 順序處理,那么得到如下 Gantt 圖所示的結果(這種 Gantt 圖為條形圖,用于顯示調度情況,包括每個進程的開始與結束時間):


 
進程 P1 的等待時間為 0ms,進程 P2 的等待時間為 24ms,而進程 P3 的等待時間為 27ms。因此,平均等待時間為 (0 + 24 + 27)/3 = 171ms。不過,如果進程按 P2、P3、P1 的順序到達,那么結果如以下 Gantt 圖所示:


 
現在平均等待時間為 (6 + 0+3)/3 = 3ms。這個減少是相當大的。因此,FCFS 策略的平均等待時間通常不是最小,而且如果進程的 CPU 執行時間變化很大,那么平均等待時間的變化也會很大。

另外,考慮動態情況下的 FCFS 調度性能。假設有一個 CPU 密集型進程和多個 I/O 密集型進程。隨著進程在系統中運行,可能發生如下情況:CPU 密集型進程得到 CPU,并使用它。在這段時間內,所有其他進程會處理完它們的 I/O,并轉移到就緒隊列來等待 CPU。當這些進程在就緒隊列中等待時,I/O 設備空閑。最終,CPU 密集型進程完成 CPU 執行并且移到 I/O 設備。所有 I/O 密集型進程,由于只有很短的 CPU 執行,故很快執行完并移回到 I/O 隊列。這時,CPU 空閑。之后,CPU 密集型進程會移回到就緒隊列并分配到 CPU。再次,所有 I/O 進程會在就緒隊列中等待 CPU 密集型進程的完成。由于所有其他進程都等待一個大進程釋放 CPU,故稱之為護航效果。與讓較短進程先進行相比,這會導致 CPU 和設備的使用率降低。

也要注意,FCFS 調度算法是非搶占。一旦 CPU 分配給了一個進程,該進程就會使用 CPU 直到釋放 CPU 為止,即程序終止或是請求 I/O。FCFS 算法對于分時系統(每個用戶需要定時得到一定的 CPU 時間)是特別麻煩的。允許一個進程使用 CPU 過長將是個嚴重錯誤。

所有教程

優秀文章

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo