定義
動態優先權,也可以稱之為動態優先權,是指在創建進程時所賦予的優先權,是可以隨進程的推進或隨其等待時間的增加而改變的,以便獲得更好的調度性能。例如,我們可以規定,在就緒佇列中的進程,隨其等待時間的增長,其優先權以速率 a 提高。若所有的進程都具有相同的優先權初值,則顯然是最先進入就緒佇列的進程將因其動態優先權變得最高而優先獲得處理機,此即FCFS 算法。若所有的就緒進程具有各不相同的優先權初值,那么,對於優先權初值低的進程,在等待了足夠的時間後,其優先權便可能升為最高,從而可以獲得處理機。當採用搶占式優先權調度算法時,如果再規定當前進程的優先權以速率 b 下降,則可防止一個長作業長期地壟斷處理機。
動態優先權優點是使相應的優先權調度算法比較靈活、科學,可防止有些進程一直得不到調度,也可防止有些進程長期壟斷處理機。動態優先權缺點是需要花費相當多的執行程式時間,因而花費的系統開銷比較大。
靜態優先權
靜態優先權,也可以稱做靜態優先權,靜態優先權是在創建進程時確定的,且在進程的整個運行期間保持不變。一般地,優先權是利用某一範圍內的一個整數來表示的,例如,0~7 或 0~255 中的某一整數,又把該整數稱為優先數,只是具體用法各異:有的系統用“0”表示最高優先權,當數值愈大時,其優先權愈低;而有的系統恰恰相反。
確定進程優先權的依據有如下三個方面:
(1) 進程類型。通常,系統進程(如接收進程、對換進程、磁碟 I/O 進程)的優先權高於一般用戶進程的優先權。
(2) 進程對資源的需求。如進程的估計執行時間及記憶體需要量的多少,對這些要求少的進程應賦予較高的優先權。
(3) 用戶要求。這是由用戶進程的緊迫程度及用戶所付費用的多少來確定優先權的。靜態優先權法簡單易行,系統開銷小,但不夠精確,很可能出現優先權低的作業(進程)長期沒有被調度的情況。因此,僅在要求不高的系統中才使用靜態優先權。
靜態優先權法的優點是:①簡單易行;②系統開銷小。缺點是:①不太靈活,很可能出現低優先權的作業(進程),長期得不到調度而等待的情況。②靜態優先權法僅適用於實時要求不太高的系統。
調度算法
調度
調度在計算機中是分配工作所需資源的方法。資源可以指虛擬的計算資源,如執行緒、進程或數據流;也可以指硬體資源,如處理器、網路連線或擴展卡。
進行調度工作的程式叫做調度器。調度器通常的實現使得所有計算資源都處於忙碌狀態(在負載均衡中),允許多位用戶有效地同時共享系統資源,或達到指定的服務質量。調度是計算自身的基礎,同時也是程式語言計算模型固有的部分。調度器使得在單處理器上通過多任務處理,從而讓執行多個進程成為可能。
調度器可能會針對不同的目標設計,例如:吞吐率最大化、回響時間最小化、 最低延遲、或最大化公平。在實踐中,這些目標通常是互相衝突的,因此,調度器會實現一個權衡利弊的折中方案,而側重點則可能是前文提到的任何一種,這取決於用戶的需求和目的。
高回響比調度
在高回響比優先調度算法中,等待時間與服務時間之和就是系統對該作業的回響時間,優先權相當於回響比 RP =回響時間/服務時間。根據回響比的大小來決定系統優先訪問哪個進程。該算法既照顧了短作業,又考慮了作業到達的先後次序,不會使長作業長期得不到服務。
由上式可以看出:
(1) 如果作業的等待時間相同,則要求服務的時間愈短,其優先權愈高,因而該算法有利於短作業。
(2) 當要求服務的時間相同時,作業的優先權決定於其等待時間,等待時間愈長,其優先權愈高,因而它實現的是先來先服務。
(3) 對於長作業, 作業的優先權可以隨等待時間的增加而提高, 當其等待時間足夠長時,其優先權便可升到很高,從而也可獲得處理機。
多級反饋佇列
多級反饋佇列調度算法是一種CPU處理機調度算法,UNIX作業系統採取的便是這種調度算法。調度算法的實施過程如下所述:
(1) 應設定多個就緒佇列, 並為各個佇列賦予不同的優先權。 第一個佇列的優先權最高,第二個佇列次之,其餘各佇列的優先權逐個降低。該算法賦予各個佇列中進程執行時間片的大小也各不相同,在優先權愈高的佇列中,為每個進程所規定的執行時間片就愈小。例如,第二個佇列的時間片要比第一個佇列的時間片長一倍,……,第 i+1 個佇列的時間片要比第 i 個佇列的時間片長一倍。
(2) 當一個新進程進入記憶體後,首先將它放入第一佇列的末尾,按 FCFS 原則排隊等待調度。當輪到該進程執行時,如它能在該時間片內完成,便可準備撤離系統;如果它在一個時間片結束時尚未完成,調度程式便將該進程轉入第二佇列的末尾,再同樣地按 FCFS原則等待調度執行;如果它在第二佇列中運行一個時間片後仍未完成,再依次將它放入第三佇列,……,如此下去,當一個長作業(進程)從第一佇列依次降到第 n 佇列後,在第 n 佇列中便採取按時間片輪轉的方式運行。
(3) 僅當第一佇列空閒時,調度程式才調度第二佇列中的進程運行;僅當第 1~(i-1)佇列均空時,才會調度第 i 佇列中的進程運行。如果處理機正在第 i 佇列中為某進程服務時,又有新進程進入優先權較高的佇列(第 1~(i-1)中的任何一個佇列),則此時新進程將搶占正在運行進程的處理機, 即由調度程式把正在運行的進程放回到第 i 佇列的末尾,把處理機分配給新到的高優先權進程。