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

1、3.3 進(jìn) 程 調(diào) 度進(jìn)程調(diào)度是OS中必不可少的一種調(diào)度。因此在三種類型的OS中，都無(wú)一例外地配置了進(jìn)程調(diào)度。此外它也是對(duì)系統(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)場(chǎng)信息。(2) 按某種算法選取進(jìn)程。(3) 把處理器分配給進(jìn)程。 3.3.1 進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式 1. 進(jìn)2. 進(jìn)程調(diào)度機(jī)制為了實(shí)現(xiàn)進(jìn)程調(diào)度，在進(jìn)程調(diào)度機(jī)制中，應(yīng)具有如下三個(gè)基本部分，如圖3-1所示。(1) 排隊(duì)器。 (2) 分派器。 (3) 上下文切換器。

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

3、方式，這是因?yàn)椋簩?duì)于批處理機(jī)系統(tǒng)，可以防止一個(gè)長(zhǎng)進(jìn)程長(zhǎng)時(shí)間地占用處理機(jī)，以確保處理機(jī)能為所有進(jìn)程提供更為公平的服務(wù)。在分時(shí)系統(tǒng)中，只有采用搶占方式才有可能實(shí)現(xiàn)人機(jī)交互。在實(shí)時(shí)系統(tǒng)中，搶占方式能滿足實(shí)時(shí)任務(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策略排成一個(gè)就緒隊(duì)列。系統(tǒng)可設(shè)置每隔一定時(shí)間(如30ms)便產(chǎn)生一次中斷，去激活進(jìn)程調(diào)度程序進(jìn)行調(diào)度，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。當(dāng)它運(yùn)行完畢后，又把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)

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

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

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

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

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

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

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