Page 19 - ePC11110_資訊科技_課本PDF
P. 19
1-1-4 工作排程演算法
工作排程的目的是找出下一個可以使用 CPU 使用權的程序，也就是決定由「就緒」
狀態進入「執行」狀態的程序。為了提高系統的使用效率，依據不同的系統需求，會有
不同的排程演算法，通常有以下幾種排程方式：
˙ ઌ౸ઌʢFirst-Come First-Served, FCFSʣ
FCFS 的特性就像是排隊購票，採先到先買方 表 1-1.1 程序的處理時間
式處理，不須考慮購買張數、票別等因素，待處理
工作程序 需處理時間
完之後才能接著下一位購買；所以 FCFS 的作法是，
P1 21
最先進入的程序 CPU 會先進行運算，當有新的程
P2 6
序產生時，就會排到末端等待執行。舉例來說，如
P3 3
果有三個程序的分割時間，如表 1-1.1 所示：
進入的時間順序是 P1、P2、P3，以先到先服務的排程方式排列，則處理時間如圖
1-1.12 所示，平均等待時間為 16。
圖 1-1.12 順序為 P1、P2、P3 的處理程序
當進入佇列的順序改為 P3、P1、P2 時，則平均等待的時間為 9，如圖 1-1.13。
圖 1-1.13 順序為 P3、P1、P2 的處理程序
由此可以得知，先到先處理的演算法，平均等待時間並非最小，且可能隨著 CPU 分
割時間的變化，而有甚大差異。此外，當有一個需要長時間處理的程序在執行時，會造
成其它程序都在等待，必須等到該程序處理完，才能讓其它工作繼續進行，即產生所謂
的護送效應（Convoy Effect）。護送效應就像是一座寬度較窄的橋有大型車擋著，後面
的車必須等到大車過橋後才能通過。若能讓小車先走，再讓大車後行，則不會造成塞車。
Chapter 01 系統平台 9
