第4章 排程(Scheduling)

排程(Scheduling) 排程是用來管理CPU的資源，排程的政策(policy)決定處理元使用CPU的順序 排程的機制(mechanism)則決定CPU配置給處理元使用的方法 一個電腦系統中可能有很多處理元都等著要執行，排程的政策決定那個處理元應該先執行，排程的機制則實際地落實這樣的順序

排程演算法(scheduling algorithm) 可間斷的(preemptive) 不可間斷的(nonpreemptive)

排程的由來 多工的作業系統可以讓多個處理元同時載入到可執行記憶體(executable memory)中，然後以時間多工(time-multiplexing)的方式讓這些處理元共用CPU 多工是現代作業系統不可缺少的特色 ，因為作業系統本身很可能就是由好幾個處理元所組成的，有必要讓多個程式隨時都處於可以馬上執行的狀態 另一個主要的考量是讓正要進行I/O的處理元先讓出CPU，避免因I/O時間過長造成CPU長時間被閒置

CPU的工作狀況

排程機制的實作 佇列管理員(enqueuer) 分派員(dispatcher) 環境切換程式(context switcher)

排程程式(scheduler)的構造

處理元的排程

多工技術 自願性的多工(voluntary multiplexing) 非自願性的多工(involuntary multiplexing)

Windows XP的[工作管理員]顯示的CPU使用率

與排程相關的時間定義 服務時間(service time) 等待時間(wait time) 輪轉時間(turnaround time)

處理器排程的模型

不可間斷的(nonpreemptive) 排程策略 先來先做(FCFS, First-Come-First-Served)的排程法 最短工作優先(SJN, Shortest Job Next) 的排程法 指定優先權的排程法 截止時間的排程法

先來先做(FCFS, First-Come-First-Served)的排程法

先來先做(FCFS, First-Come-First-Served)的排程法 (L代表服務時間，T代表turnaround time。) T(P1) = L(P1) = 300 T(P2) = L(P2) + T(P1) = 150 + 300 = 450 T(P3) = L(P3) + T(P2) = 430 + 450 = 880 T(P4) = L(P4) + T(P3) = 230 + 880 = 1110 T(P5) = L(P5) + T(P4) = 92 + 1110 = 1202 Average turnaround time AT = (300 + 450 + 880 + 1110 + 1202) / 5 = 788.4 Average waiting time AW = (0 + 300 + 450 + 880 + 1110)/5 = 548

最短工作優先(SJN, Shortest Job Next) 的排程法

最短工作優先(SJN, Shortest Job Next) 的排程法 T(P1) = L(P1) + T(P4) = 300 + 472 = 772 T(P2) = L(P2) + T(P5) = 150 + 92 = 242 T(P3) = L(P3) + T(P1) = 430 + 772 = 1202 T(P4) = L(P4) + T(P2) = 230 + 242 = 472 T(P5) = L(P5) = 92 Average turnaround time AT = (772 + 242 + 1202 + 472 + 92) / 5 = 556 T(W1) = 472 T(W2) = 92 T(W3) = 772 T(W4) = 242 T(W5) = 0 Average waiting time AW = (472 + 92 + 772 + 242 + 0)/5 = 315.6

指定優先權的排程法

指定優先權的排程法 T(P1) = L(P1) + T(P3)= 300 + 430 = 730 Average turnaround time AT = (730 + 1202 + 430 + 1052 + 822) / 5 = 847.2 T(W1) = 472 T(W2) = 1052 T(W3) = 0 T(W4) = 822 T(W5) = 730 Average waiting time AW = (472 + 1052 + 0 + 822 + 730)/5 = 615.2

截止時間的排程法

截止時間的排程法 T(P1) = L(P1) + T(P2)= 300 + 242 = 542 Average turnaround time AT = (542 + 242 + 972 + 1202 + 92) / 5 = 610 T(W1) = 242 T(W2) = 92 T(W3) = 542 T(W4) = 972 T(W5) = 0 Average waiting time AW = (242 + 92 + 542 + 972 + 0)/5 = 369.6

可間斷的(preemptive) 排程策略 輪替式的排程法 (Round Robin scheduling) 多層佇列(multiple-level queues)的排程法

輪替式的排程法 (Round Robin scheduling)

輪替式的排程法 (Round Robin scheduling) T(P1) = 1022 T(P2) = 592 T(P3) = 1202 T(P4) = 972 T(P5) = 492 Average turnaround time AT = (1022+592+1202+972+492) / 5 = 856 T(W1) = 0 T(W2) = 50 T(W3) = 100 T(W4) = 150 T(W5) = 200 Average waiting time AW = (0 + 50 + 100 + 150 + 200)/5 = 100

輪替使用50個時間單位並考量context switching的排程結果

輪替使用50個時間單位並考量context switching的排程結果 T(P1) = 1212 T(P2) = 692 T(P3) = 1432 T(P4) = 1152 T(P5) = 572 Average turnaround time AT = (1212 + 692 + 1432 + 1152 + 572) / 5 = 1012 T(W1) = 0 T(W2) = 60 T(W3) = 120 T(W4) = 180 T(W5) = 240 Average waiting time AW = (0 + 60 + 120 + 180 + 240)/5 = 120

多處理器的排程(multiple-processor scheduling) 現在很多電腦已經使用多處理器與多核心的架構，假如在作業系統的層次上沒有對應的改變，可能無法完全發揮這些硬體的功能

作業系統中排程的類型

處理元排程的種類

以另外一種觀點來觀察各種排程

以佇列(queue)來表示 處理元的排程

回應時間(response time) 所謂的回應時間是指系統對某個輸入產生回應所花費的時間，例如使用者輸入一個指令，從完成輸入到看到系統回應之間所等待的時間就可以算是一種回應時間 我們可以把回應時間想像成要求系統完成某項工作所需要的時間。回應時間越短似乎使用者越滿意，但是要付出的成本相對地也比較高，因為顯然電腦的配備要好，而且某個處理元的回應時間短，可能也造成了另一個處理元的回應時間變長了

回應時間(response time) 從使用者與作業系統互動的觀點來看，當使用者收到回應，到輸入下一個指令之間所花的時間稱為使用者回應時間(user response time) 使用者輸入一個指令，到系統呈現回應之間的時間則稱為系統回應時間(system response time)

簡單的佇列系統

multiserver queue

multiple single-server queues