操作系統(tǒng)-進(jìn)-程-調(diào)-度課件

1、3.3 進(jìn) 程 調(diào) 度進(jìn)程調(diào)度是OS中必不可少的一種調(diào)度。因此在三種類型的OS中，都無一例外地配置了進(jìn)程調(diào)度。此外它也是對系統(tǒng)性能影響最大的一種處理機(jī)調(diào)度，相應(yīng)的，有關(guān)進(jìn)程調(diào)度的算法也較多。3.3 進(jìn) 程 調(diào) 度進(jìn)程調(diào)度是OS中3.3.1 進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式 1. 進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)主要有三：(1) 保存處理機(jī)的現(xiàn)場信息。(2) 按某種算法選取進(jìn)程。(3) 把處理器分配給進(jìn)程。 3.3.1 進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式 1. 進(jìn)2. 進(jìn)程調(diào)度機(jī)制為了實現(xiàn)進(jìn)程調(diào)度，在進(jìn)程調(diào)度機(jī)制中，應(yīng)具有如下三個基本部分，如圖3-1所示。(1) 排隊器。 (2) 分派器。 (3) 上下文切換器。

2、 2. 進(jìn)程調(diào)度機(jī)制為了實現(xiàn)進(jìn)程調(diào)度，在進(jìn)程調(diào)度機(jī)制圖3-1 進(jìn)程調(diào)度機(jī)制圖3-1 進(jìn)程調(diào)度機(jī)制3. 進(jìn)程調(diào)度方式1) 非搶占方式(Nonpreemptive Mode)在采用這種調(diào)度方式時，一旦把處理機(jī)分配給某進(jìn)程后，就一直讓它運行下去，決不會因為時鐘中斷或任何其它原因去搶占當(dāng)前正在運行進(jìn)程的處理機(jī)，直至該進(jìn)程完成，或發(fā)生某事件而被阻塞時，才把處理機(jī)分配給其它進(jìn)程。3. 進(jìn)程調(diào)度方式1) 非搶占方式(Nonpree2) 搶占方式(Preemptive Mode)這種調(diào)度方式允許調(diào)度程序根據(jù)某種原則，去暫停某個正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。在現(xiàn)代OS中廣泛采用搶占

3、方式，這是因為：對于批處理機(jī)系統(tǒng)，可以防止一個長進(jìn)程長時間地占用處理機(jī)，以確保處理機(jī)能為所有進(jìn)程提供更為公平的服務(wù)。在分時系統(tǒng)中，只有采用搶占方式才有可能實現(xiàn)人機(jī)交互。在實時系統(tǒng)中，搶占方式能滿足實時任務(wù)的需求。但搶占方式比較復(fù)雜，所需付出的系統(tǒng)開銷也較大。2) 搶占方式(Preemptive Mode)這3.3.2 輪轉(zhuǎn)調(diào)度算法1. 輪轉(zhuǎn)法的基本原理在輪轉(zhuǎn)(RR)法中，系統(tǒng)將所有的就緒進(jìn)程按FCFS策略排成一個就緒隊列。系統(tǒng)可設(shè)置每隔一定時間(如30ms)便產(chǎn)生一次中斷，去激活進(jìn)程調(diào)度程序進(jìn)行調(diào)度，把CPU分配給隊首進(jìn)程，并令其執(zhí)行一個時間片。當(dāng)它運行完畢后，又把處理機(jī)分配給就緒隊列中新的隊

4、首進(jìn)程，也讓它執(zhí)行一個時間片。這樣，就可以保證就緒隊列中的所有進(jìn)程在確定的時間段內(nèi)，都能獲得一個時間片的處理機(jī)時間。3.3.2 輪轉(zhuǎn)調(diào)度算法1. 輪轉(zhuǎn)法的基本原理2. 進(jìn)程切換時機(jī)在RR調(diào)度算法中，應(yīng)在何時進(jìn)行進(jìn)程的切換，可分為兩種情況： 若一個時間片尚未用完，正在運行的進(jìn)程便已經(jīng)完成，就立即激活調(diào)度程序，將它從就緒隊列中刪除，再調(diào)度就緒隊列中隊首的進(jìn)程運行，并啟動一個新的時間片。 在一個時間片用完時，計時器中斷處理程序被激活。如果進(jìn)程尚未運行完畢，調(diào)度程序?qū)阉屯途w隊列的末尾。2. 進(jìn)程切換時機(jī)在RR調(diào)度算法中，應(yīng)在何時進(jìn)行進(jìn)3. 時間片大小的確定在輪轉(zhuǎn)算法中，時間片的大小對系統(tǒng)性能有很

5、大的影響。 圖3-2示出了時間片大小對響應(yīng)時間的影響，其中圖(a)是時間片略大于典型交互的時間，而圖(b)是時間片小于典型交互的時間。圖3-3示出了時間片分別為q=1和q=4時對平均周轉(zhuǎn)時間的影響。 3. 時間片大小的確定在輪轉(zhuǎn)算法中，時間片的大小對圖3-2 時間片大小對響應(yīng)時間的影響圖3-2 時間片大小對響應(yīng)時間的影響圖3-3 q=1和q=4時進(jìn)程的周轉(zhuǎn)時間圖3-3 q=1和q=4時進(jìn)程的周轉(zhuǎn)時間3.3.3 優(yōu)先級調(diào)度算法1. 優(yōu)先級調(diào)度算法的類型優(yōu)先級進(jìn)程調(diào)度算法，是把處理機(jī)分配給就緒隊列中優(yōu)先級最高的進(jìn)程。這時，又可進(jìn)一步把該算法分成如下兩種。(1) 非搶占式優(yōu)先級調(diào)度算法。(2) 搶占

6、式優(yōu)先級調(diào)度算法。 3.3.3 優(yōu)先級調(diào)度算法1. 優(yōu)先級調(diào)度算法的類型2. 優(yōu)先級的類型1) 靜態(tài)優(yōu)先級靜態(tài)優(yōu)先級是在創(chuàng)建進(jìn)程時確定的，在進(jìn)程的整個運行期間保持不變。優(yōu)先級是利用某一范圍內(nèi)的一個整數(shù)來表示的，例如0255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。確定進(jìn)程優(yōu)先級大小的依據(jù)有如下三個：(1) 進(jìn)程類型。(2) 進(jìn)程對資源的需求。(3) 用戶要求。2. 優(yōu)先級的類型1) 靜態(tài)優(yōu)先級靜態(tài)優(yōu)先級2) 動態(tài)優(yōu)先級動態(tài)優(yōu)先級是指在創(chuàng)建進(jìn)程之初，先賦予其一個優(yōu)先級，然后其值隨進(jìn)程的推進(jìn)或等待時間的增加而改變，以便獲得更好的調(diào)度性能。 2) 動態(tài)優(yōu)先級動態(tài)優(yōu)先級是指在創(chuàng)建進(jìn)程之初，先賦3.3.4 多

7、隊列調(diào)度算法如前所述的各種調(diào)度算法，尤其在應(yīng)用于進(jìn)程調(diào)度時，由于系統(tǒng)中僅設(shè)置一個進(jìn)程的就緒隊列，即低級調(diào)度算法是固定的、單一的，無法滿足系統(tǒng)中不同用戶對進(jìn)程調(diào)度策略的不同要求，在多處理機(jī)系統(tǒng)中，這種單一調(diào)度策略實現(xiàn)機(jī)制的缺點更顯突出，由此，多級隊列調(diào)度算法能夠在一定程度上彌補這一缺點。3.3.4 多隊列調(diào)度算法如前所述的各種調(diào)度算法，尤3.3.5 多級反饋隊列(multileved feedback queue)調(diào)度算法 1. 調(diào)度機(jī)制多級反饋隊列調(diào)度算法的調(diào)度機(jī)制可描述如下：(1) 設(shè)置多個就緒隊列。 圖3-4是多級反饋隊列算法的示意圖。3.3.5 多級反饋隊列(multileved fee

8、db圖3-4 多級反饋隊列調(diào)度算法圖3-4 多級反饋隊列調(diào)度算法(2) 每個隊列都采用FCFS算法。當(dāng)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊列的末尾，按FCFS原則等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時，如它能在該時間片內(nèi)完成，便可撤離系統(tǒng)。否則，即它在一個時間片結(jié)束時尚未完成，調(diào)度程序?qū)⑵滢D(zhuǎn)入第二隊列的末尾等待調(diào)度；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列，依此類推。當(dāng)進(jìn)程最后被降到第n隊列后，在第n隊列中便采取按RR方式運行。(2) 每個隊列都采用FCFS算法。當(dāng)新進(jìn)程進(jìn)入內(nèi)存后，(3) 按隊列優(yōu)先級調(diào)度。調(diào)度程序首先調(diào)度最高優(yōu)先級隊列中的諸進(jìn)程運行，僅當(dāng)?shù)谝魂犃锌臻e時才調(diào)度

9、第二隊列中的進(jìn)程運行；換言之，僅當(dāng)?shù)?(i-1)所有隊列均空時，才會調(diào)度第i隊列中的進(jìn)程運行。如果處理機(jī)正在第i隊列中為某進(jìn)程服務(wù)時又有新進(jìn)程進(jìn)入任一優(yōu)先級較高的隊列，此時須立即把正在運行的進(jìn)程放回到第i隊列的末尾，而把處理機(jī)分配給新到的高優(yōu)先級進(jìn)程。(3) 按隊列優(yōu)先級調(diào)度。調(diào)度程序首先調(diào)度最高優(yōu)先級隊列2. 調(diào)度算法的性能在多級反饋隊列調(diào)度算法中，如果規(guī)定第一個隊列的時間片略大于多數(shù)人機(jī)交互所需之處理時間時，便能較好地滿足各種類型用戶的需要。(1) 終端型用戶。(2) 短批處理作業(yè)用戶。(3) 長批處理作業(yè)用戶。2. 調(diào)度算法的性能在多級反饋隊列調(diào)度算法中，如果3.3.6 基于公平原則的調(diào)

10、度算法 1. 保證調(diào)度算法保證調(diào)度算法是另外一種類型的調(diào)度算法，它向用戶所做出的保證并不是優(yōu)先運行，而是明確的性能保證，該算法可以做到調(diào)度的公平性。一種比較容易實現(xiàn)的性能保證是處理機(jī)分配的公平性。如果在系統(tǒng)中有n個相同類型的進(jìn)程同時運行，為公平起見，須保證每個進(jìn)程都獲得相同的處理機(jī)時間1/n。 3.3.6 基于公平原則的調(diào)度算法 1. 保證調(diào)在實施公平調(diào)度算法時系統(tǒng)中必須具有這樣一些功能：(1) 跟蹤計算每個進(jìn)程自創(chuàng)建以來已經(jīng)執(zhí)行的處理時間。(2) 計算每個進(jìn)程應(yīng)獲得的處理機(jī)時間，即自創(chuàng)建以來的時間除以n。(3) 計算進(jìn)程獲得處理機(jī)時間的比率，即進(jìn)程實際執(zhí)行的處理時間和應(yīng)獲得的處理機(jī)時間之比。(4) 比較各進(jìn)程獲得處理機(jī)時間的比率。如進(jìn)程A的比率最低，為0.5，而進(jìn)程B的比率為0.8，進(jìn)程C的比率為1.2等。(5) 調(diào)度程序應(yīng)選擇比率最小的進(jìn)程將處理機(jī)分