第4章排程(Scheduling)

電腦所執行的程式在執行時稱為「處理元(process)」,處理元使用電腦的資源來進行程式所描述的工作,特別是電腦的CPU,在程式執行時擔當大任。由於現代的電腦上有許多程式一起在執行,但是CPU同時只能處理一個處理元的工作,因此作業系統必須安排處理元使用CPU的順序,這項任務稱為CPU的排程(scheduling),要透徹了解排程時發生的大小細節,必須先深入了解處理元的一些相關資訊。

排程是用來管理CPU的資源,排程的政策(policy)決定處理元使用CPU的順序,排程的機制(mechanism)則決定CPU配置給處理元使用的方法。

1. 不可間斷的(nonpreemptive)：不可間斷的排程演算法會讓取得CPU的處理元一直執行到結束,不被打斷。

2. 可間斷的(preemptive)：可間斷的排程演算法則以間隔計時器(interval timer)來控制一個處理元能夠佔用CPU的時間,然後用排程管理員(scheduler)中斷執行中的處理元,把CPU重新分配給有更高優先權的處理元。

CPU的工作狀況,當使用CPU的程式進行I/O的時候,CPU就會被閒置,假如這段時間的空檔可以拿來處理其他處理元的工作,顯然電腦系統的效能就會大幅地提昇。

從機制(mechanism)上來看排程所得到的結果:

1. 將執行中的處理元從CPU中移出。

2. 依照某種政策(policy)選擇要移入的處理元。

CPU 的使用權在兩個處理元之間轉換: 每個處理元執行時並不是一直占有CPU到完成為止,必須跟其他的處理元輪流使用CPU來執行指令,所以處理元進入「ready」的狀態之後等於是在排隊等待執行,而正占用CPU的處理元在分配使用的時間用完之後就會讓出CPU。

當處理元在CPU執行時假如沒有執行完成必須先讓出CPU時,可能產生的情況有很多種:

處理元移出CPU與移出記憶體的差異,主要是在於移出CPU的處理元可以馬上再回到ready queue排隊等待使用CPU。

排程的機制會將處理元從CPU中移出,然後依據某種策略來將另一個處理元移入CPU中執行。

分派員 (dispatcher): 處理元移出CPU之後,分派員程式馬上移入CPU執行,分派員程式從 ready list 中選擇要移入的處理元,分派員程式隨後移出CPU,讓新選擇的處理元移入CPU 執行

對CPU做多工處理的時機

1. 自願性的多工(voluntary multiplexing) : 執行中的處理元自願讓出CPU的使用權,主動呼叫context switcher。

2. 非自願性的多工(involuntary multiplexing) : 利用中斷(interrupt)使執行中的處理元讓出CPU的使用權, 由中斷處理碼(interrupt handler code)做環境切換(context switch) 。

1. 服務時間(service time) : 處理元執行完成所需要停留在running狀態的時間。

2. 等待時間(wait time) : 處理元第一次進入running state在ready state等待的時間。

3. 輪轉時間(turnaround time) : 處理元第一次進入ready state到最後一次離開running state所經歷的時間。

不可間斷的(nonpreemptive) 排程策略會讓一個處理元在取得CPU的使用權以後一直執行到結束才交出CPU,所以不會有process從CPU移出而回到ready list。

FCFS的排程法依照處理元請求使用CPU的順序來指定優先權(priority),做法是由enqueuer提供一個時間戳記(timestamp)給每一個請求使用CPU的處理元,存在最久的時間戳記擁有最高的優先權。由於佇列(queue)資料結構有先進先出的特性,很適合用來描述FCFS排程法中等待的處理元串列。

最短工作優先(SJF, Shortest Job First) 的排程法選擇服務時間需求最短的處理元先執行,SJF使平均的等待時間縮短了,但是對於服務時間需求大的處理元來說比較不公平,因為會一直被服務時間需求短的處理元往後排擠。

指定優先權的排程法(priority scheduling)依照外部指定的優先權來排程,優先權低的處理元有可能遭遇飢餓(starvation)的問題,但系統可以依據處理元等待時間的加長來調整其優先權。

截止時間的排程法(deadline scheduling)以截止時間(deadline)做為排程的基礎,在硬性即時(hard real-time)的系統裡,我們所在乎的是處理元能否在時限內完成,一旦處理元進入ready list,代表該處理元將能在其截止時間之前完成。

在可間斷的排程演算法中,擁有最高優先權處理元以占用CPU,只要有最高優先權的處理元請求使用CPU,其他優先權較低的處理元都要讓出CPU。在可間斷的排程演算法中,環境切換(context switching)可能會耗用可觀的系統資源。

輪替式的排程法(Round Robin scheduling)是所有排程法中最常用的,輪替式排程法的精神是將CPU的處理時間平均分配給所有的處理元,這很符合互動式多工(interactive multiprogramming)系統的需求,因為眾多的使用者在互動過程中都需要得到一點系統的回應。

多層佇列(multiple-level queues)的排程法是priority scheduling的延伸,把優先順序(priority)一樣的所有處理元放在同一個佇列上。排程程式(scheduler)依據某種排程政策將CPU分配給某個queue上的處理元來使用,至於是該queue上的那個處理元使用,則需要依據另外一種排程政策來決定。等於是在一般的排程順序上多加了一個層次,這麼做是否更好,必須看實際的狀況而定

當處理元產生的時候所進行的是長程的排程處理元一旦產生以後,就會在系統中活動,長程排程安排處理元進入準備執行的狀態。中程的排程是交換功能(swapping function)的一部分,排程時決定是否將處理元移入主記憶體,所以這時候處理元基本上已經處於可以被執行的狀態。短程的排程是指實際選定處理元執行的功能。處理元一產生就在長程排程處理的範圍內,進入中程排程的範圍之後,處理元已經在記憶體中占有位置,一旦接近執行的時刻,就會在短程排程的安排下開始執行,執行完成之後直接到exit的狀態。以佇列(queue)來表示處理元的排程,排程透過這些佇列的管理來降低等待的時間,同時讓整體的效能達到最佳化(optimized)的狀態。

長程排程決定那些程式可以進入系統接受處理,所以長程排程控制了多工的程度,越多的處理元進入了系統表示每個處理元平均分配到的處理時間減少了,對於活動中的處理元來說,會受到影響,當處理器經常閒置時,顯然更多的處理元可以安排進入系統準備執行。處理元的特性不同時對於CPU的使用情形也不一樣,偏向於進行運算的處理元也稱為processor bound的處理元,常進行I/O作業的處理元則稱為I/O bound的處理元。

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

佇列系統(queuing system),其中的server是提供服務的,接受服務的個體不斷進入系統,假如server處於閒置狀態,則進來的個體立即得到服務,不然就要排隊等待。在作業系統中,server可能代表CPU、I/O設備等

假如佇列的容量沒有限制,則進入的個體不會消失,會一一地等待接受服務。當server 的使用率增加時,代表server 更忙碌,佇列也比較長,使用率ρ=1時表示server 飽和,因此系統能接受的最大抵達速率為: λ_max=1/T_s

使用多個相同的server,則對於每個server 來說,抵達速率變成ρ/N,只有在所有servers 都忙碌的情況下,佇列才會開始形成,不管servers 有多少個,佇列中的個體如何分派給server 處理,必須有一定的規則,這種規則也稱為dispatching discipline。但是對應於每個server都各有一個佇列，等於個體在到達之後就要分配到不同的佇列中。