CPU排班演算法CPUB1C6AFZBAtBAE2AAkCPU排班演算法CPUB1C6AFZBAtBAE2AAk.ppt

CPU排班演算法 組員:羅元隆 陳彥勳 CPU排班的方法 先到先處理演算法。 最短工時先處理演算法。 優先權排班演算法。 循序循環演算法：均分CPU時間。 多層佇列排班演算法：先分類再決定使用CPU時間的順序。 多層回饋佇列排班演算法：行程不固定在某個佇列中，可以機動轉移。 先到先處理 先到先處理:採用先進先出的方式,服務先到的程序 舉例: 先到先處理之甘特圖: 各程序等待時間 則甘特圖如下所示: 平均等待時間如下所示: 最短行程排班 工作方式─ 將每一個行程的下一個CPU分割長度與該行程相結合，當CPU有空的時候就指定給下一個CPU分割最短的行程，假如兩個行程的分割時間長度相同，則採用FCFS的方法。 最短工作先處理 舉例 甘特圖如下所示: 最短工作先處理 (cont) 不同的抵達順序及其平均等待時間 預測下一個 CPU 分割時間之公式 下一個 CPU 分割時間的預估值可以設定為前幾次 CPU 分割時間的指數平均值。 ?n+1 = ? * tn + (1 – ?) * ?n ?n = 上一次預估的 CPU 分割時間 tn = 上一次實際的 CPU 分割時間 ?n+1 = 此次預估的 CPU 分割時間 ?：參數 (加權機率), 0 ? ? ? 1(通常 ? = 1/2) 若上次猜的時間很準，則?下降 若上次猜的時間不準，則?上升 優先權排班 每一個行程結合一個優先權號碼（整數）。 CPU 被分配給最高優先權的行程。 可搶先 不可搶先 SJF 是一種以 CPU 分割時間為優先權的排班方式。 問題：飢餓，低優先權的行程可能永不被執行。 解法：老化，隨經過時間提高行程的優先權。 可搶先 vs.不可搶先 CPU的排班法則大致可以分為兩大類： 不可搶先(不可插隊)的排班 ： 當行程取得CPU在執行時，除非這個行程自行將CPU釋放出去 ，其它行程才有機會取得CPU，否則其它的行程無法取得CPU的使用權。 其它行程無法強迫該執行中的行程放棄CPU。 可搶先(可插隊)的排班 ： 當一個行程取得CPU在執行時，有可能被迫放棄CPU ，將CPU交給其它的行程執行。 優先權定義 內部─(使用一些可以測得的量來定義) 主要是針對每一個行程對資源的需求為考量，是O.S.可以掌控的。時間限制、記憶體需求、開啟檔案數量、平均I/O分割、平均CPU分割的比率來計算優先權。 外部─(由作業系統外部的一些標準所決定) 主要是針對政策面的考量，通常是由人來掌控。如：行程的重要性、行程重要性、支付使用電腦費用所使用的基金類型與數量、支助該項工作的部門和其它大多是政策性的因素。 優先權排班 優先權如下 甘特圖如下 依序循環排班 依序循環排班方式在使用時，先預設好經過多少時間CPU就該切換執行下一個程序，也就是設定好間隔時間(time slice)。所有的程序放在新進先出的佇列裡面，首先CPU排班從佇列裡挑第一個程序執行，然後開始進行倒數，時間到的時候就得讓CPU處理佇列裡下一個程序。 依序循環排班 每一個行程得到一小段 CPU 時間（時間量，10-100 ms）。在這時間過後，行程被取代並加到就緒佇列的最後。 假如有 n 行程及 q 時間量，則沒有行程等候超過 (n-1)q 時間單位。 效能 q 大 → FIFO q 小 → 太多內容轉換(context switch) 依序循環排班 (cont) 範例 甘特圖 turnaround time 回復時間 (turnaround time) 對某一個特定行程而言，我們所關心的是這個行程到底需要多少時間才能完成。從行程進入電腦，一直到該行程完成並且離開電腦，這整段時間稱為“回復時間”。包括等待主記憶體、在就緒佇列等待，以及CPU執行和輸出/入動作執行等時間。 response time 反應時間 (response time) 回復時間有時候並不是主要的衡量標準。通常行程可能很快地產生一個輸出結果，並且不等輸出結束就繼續計算下一個結果。因此另一個衡量的標準就是以提出一個要求到第一反應出現的時間間隔來計算，這就是所謂反應時間。這是指開始有所反應的時間，而不是指完成反應的時間。因為前面所說的回復時間經常會受到輸出裝置的速度限制。 RR範例 時間量 = 20 平均回復時間較高 反應時間較好 時間量對內容轉換 時間量越短，內容轉換負荷越重。 平均回覆時間也會增加。 時間量對回復時間 大部份行程在一個時間量內完成。 多層佇列 就緒佇列被分成幾個佇列： 前景和後景 系統任務行程、交談式行程、編修作業行程、整批作業行程、學生行程 每一個