第14講 第4章 處理機(jī)調(diào)度.ppt

1、,DOS,Windows9X,WindowsNT,Linux,UNIX,WindowsCE,第4章 處理機(jī)調(diào)度,主講：曾孝文,本課程內(nèi)容,第1章 緒論 第2章 操作系統(tǒng)用戶界面 第3章 進(jìn)程管理 第4章 處理機(jī)調(diào)度 第5章 存儲(chǔ)管理 第8章 文件系統(tǒng) 第9章 設(shè)備管理,進(jìn)程調(diào)度的算法較多，在設(shè)計(jì)進(jìn)程調(diào)度算 法時(shí)應(yīng)考慮的因素多，比如：盡量提高資源利 用率，減少處理機(jī)的空閑時(shí)間，對(duì)于用戶作業(yè) 要較合理的平均響應(yīng)時(shí)間，以及盡可能地增強(qiáng) CPU的處理能力。,選擇調(diào)度算法時(shí)應(yīng)考慮的問(wèn)題,4.4 調(diào)度算法,基本要求： 算法應(yīng)盡可能簡(jiǎn)單、不讓進(jìn)程長(zhǎng)久等待。,一. FCFS(先來(lái)先服務(wù)調(diào)度算法) 最簡(jiǎn)單的調(diào)度

2、原則是先進(jìn)先出(FIFO) 就緒隊(duì)列,A,B,C,D,CPU,完成,根據(jù)進(jìn)程到達(dá)就緒隊(duì)列的時(shí)間來(lái)分配中央處理機(jī)，一旦一個(gè)進(jìn)程獲得了中央處理機(jī)，就一直運(yùn)行到結(jié)束，先來(lái)先服務(wù)是非剝奪調(diào)度。 這種調(diào)度從形式上講是公平的，但它使短作業(yè)要等待長(zhǎng)作業(yè)的完成，重要的作業(yè)要等待不重要作業(yè)的完成。從這個(gè)意義上講又是不公平的。 先進(jìn)先出調(diào)度使響應(yīng)時(shí)間的變化較小，因此它比其它大多數(shù)調(diào)度都可預(yù)測(cè)。由于這種調(diào)度方法不能保證良好的響應(yīng)時(shí)間，在處理交互式用戶時(shí)很少用這種方法。,在當(dāng)今系統(tǒng)中，先進(jìn)先出很少作為調(diào)度 模式，而是常常嵌套在其它的調(diào)度模式中。 例如，許多調(diào)度模式根據(jù)優(yōu)先級(jí)將處理機(jī)分 配給進(jìn)程，但具有相同優(yōu)先級(jí)的進(jìn)程

3、卻按先 進(jìn)先出進(jìn)行分配。,關(guān)于平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間的計(jì)算與作業(yè)中的FCFS的計(jì)算一樣。,先來(lái)先服務(wù)(FCFS)算法,先來(lái)先服務(wù)(FCFS)算法,該算法總是把處理機(jī)分配給最先進(jìn)入就緒隊(duì) 列的進(jìn)程，一個(gè)進(jìn)程一旦分得處理機(jī)，便執(zhí)行 下去，直到該進(jìn)程完成或阻塞時(shí)，才釋放處理 機(jī)。 優(yōu)點(diǎn):實(shí)現(xiàn)簡(jiǎn)單。 缺點(diǎn):沒(méi)考慮進(jìn)程的優(yōu)先級(jí)。,二. 循環(huán)輪轉(zhuǎn)調(diào)度算法 目的：讓所有的進(jìn)程，均衡地使用CPU。 方法： 當(dāng)CPU空閑時(shí)，選取就緒隊(duì)列首元素，賦予一個(gè)時(shí)間片，當(dāng)時(shí)間片用完時(shí)，該進(jìn)程轉(zhuǎn)為就緒態(tài)并進(jìn)入就緒隊(duì)列的末端。 問(wèn)題：時(shí)間片如何定？ (1) 簡(jiǎn)單循環(huán)輪轉(zhuǎn)調(diào)度(時(shí)間片 q 固定) 即：就緒隊(duì)列中的所有進(jìn)

4、程，等速度向前推進(jìn)。,ti,ti+1,當(dāng)前的響應(yīng)時(shí)間 : t i=q * n i (n i為當(dāng)前進(jìn)程數(shù)) ,p1,p1,p4,即：響應(yīng)時(shí)間 t 是變化的，它即隨進(jìn)程數(shù)而變化，又受到時(shí)間片的影響。 那么時(shí)間片應(yīng)選多大才合適呢？ 時(shí)間片q的確定： 設(shè)t為響應(yīng)時(shí)間，n為進(jìn)程數(shù)，由tqn 有： q=tmax/n =3000ms/(6 60)= 50 500 ms 問(wèn)題：q選定后，響應(yīng)時(shí)間是變化的。 太長(zhǎng)，用戶不滿意；太短，浪費(fèi)切換時(shí)間。 例如：設(shè)q=0.1秒 當(dāng)ni=30時(shí)： ti=3秒 當(dāng)nj=3時(shí)： tj=0.3秒 ,即：響應(yīng)時(shí)間 t 是變化的，它即隨進(jìn)程數(shù)而變化，又受到時(shí)間片的影響。,當(dāng)時(shí)間片很

5、大時(shí)，每個(gè)進(jìn)程得到比完成該進(jìn)程多的處理機(jī)時(shí)間，此時(shí)輪轉(zhuǎn)調(diào)度模式退化為先進(jìn)先出模式。 當(dāng)時(shí)間片非常小時(shí)，上下文切換開(kāi)銷(xiāo)就成了決定因素，系統(tǒng)性能降低，大多數(shù)時(shí)間都消耗在處理機(jī)的轉(zhuǎn)換上，只有少許用在用戶的計(jì)算上。,分時(shí)系統(tǒng)中常用時(shí)間片輪轉(zhuǎn)法,時(shí)間片選擇問(wèn)題： 固定時(shí)間片 可變時(shí)間片 與時(shí)間片大小有關(guān)的因素(q=tmax/n) 系統(tǒng)響應(yīng)時(shí)間 就緒進(jìn)程個(gè)數(shù) CPU能力,(2)可變時(shí)間片循環(huán)輪轉(zhuǎn)調(diào)度(響應(yīng)時(shí)間T固定) 響應(yīng)時(shí)間T固定為用戶所能接受的時(shí)間(如3秒)。 每一輪開(kāi)始前，根據(jù)當(dāng)前的就緒進(jìn)程數(shù)Ni，預(yù)先決定該輪的時(shí)間片Qi 。即： 不同輪的時(shí)間片可能不同；同一輪中各進(jìn)程的時(shí)間片相同。 Qi =T/

6、Ni,進(jìn)一步的問(wèn)題：能否同時(shí)又考慮進(jìn)程的優(yōu)先權(quán)呢？ ,P4 P1 P2 P3,P4(等下一輪),3.多重時(shí)間片循環(huán)輪轉(zhuǎn)調(diào)度算法,是優(yōu)先數(shù)和循環(huán)輪轉(zhuǎn)調(diào)度算法的綜合。 根據(jù)優(yōu)先數(shù)的分布采用多個(gè)就緒隊(duì)列，進(jìn)程按優(yōu)先數(shù) 排在相應(yīng)的就緒隊(duì)列中。,Windows NT采用類(lèi)似的結(jié)構(gòu)；UNIX的思想也與此類(lèi)似。 例： UNIX的進(jìn)程調(diào)度 ,1)簡(jiǎn)單輪轉(zhuǎn)法的調(diào)度模型,2)多隊(duì)列反饋調(diào)度算法,將就緒隊(duì)列分為N級(jí)，每個(gè)就緒隊(duì)列分配給不同的時(shí)間片，隊(duì)列級(jí)別越高，時(shí)間片越小，級(jí)別越小，時(shí)間片越長(zhǎng)，最后一級(jí)采用時(shí)間片輪轉(zhuǎn)，其他隊(duì)列采用先進(jìn)先出； 系統(tǒng)從第一級(jí)調(diào)度，當(dāng)?shù)谝患?jí)為空時(shí)，系統(tǒng)轉(zhuǎn)向第二個(gè)隊(duì)列，.當(dāng)運(yùn)行進(jìn)程用完一個(gè)

7、時(shí)間片，放棄CPU時(shí)，進(jìn)入下一級(jí)隊(duì)列；等待進(jìn)程被喚醒時(shí)，進(jìn)入原來(lái)的就緒隊(duì)列；當(dāng)進(jìn)程第一次就緒時(shí)，進(jìn)入第一級(jí)隊(duì)列,* 首先系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列； * 每個(gè)就緒隊(duì)列分配給不同時(shí)間片，優(yōu)先級(jí)高的為第一級(jí)隊(duì)列，時(shí)間片最小，隨著隊(duì)列級(jí)別的降低，時(shí)間片加大； * 各個(gè)隊(duì)列按照先進(jìn)先出調(diào)度算法； * 一個(gè)新進(jìn)程就緒后進(jìn)入第一級(jí)隊(duì)列； * 進(jìn)程由于等待而放棄CPU后，進(jìn)入等待隊(duì)列，一旦等待的事件發(fā)生，則回到原來(lái)的就緒隊(duì)列； * 當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒時(shí)，可以搶占CPU，被搶占進(jìn)程回到原來(lái)一級(jí)就緒隊(duì)列末尾； * 當(dāng)?shù)谝患?jí)隊(duì)列空時(shí)，就去調(diào)度第二級(jí)隊(duì)列，如此類(lèi)推； * 當(dāng)時(shí)間片到后，進(jìn)程放棄CPU，回到下一

8、級(jí)隊(duì)列。,多隊(duì)列反饋調(diào)度算法,三.進(jìn)程優(yōu)先數(shù)調(diào)度算法 預(yù)先確定各進(jìn)程的優(yōu)先級(jí)(通常用優(yōu)先數(shù)表示)，系統(tǒng)總是把處理機(jī)分配給優(yōu)先級(jí)最高的就緒進(jìn)程。 .優(yōu)先數(shù)的形式 靜態(tài)優(yōu)先數(shù)：在進(jìn)程被創(chuàng)建時(shí)按某種策略確定，且在整個(gè)進(jìn)程的運(yùn)行期間不再改變。 動(dòng)態(tài)優(yōu)先數(shù)：在進(jìn)程被創(chuàng)建時(shí)先給出一個(gè)初始的優(yōu)先數(shù)(也稱(chēng)為基本優(yōu)先數(shù))，而在進(jìn)程運(yùn)行中的一些關(guān)鍵時(shí)刻，再按某種策略進(jìn)行調(diào)整。 ,2.優(yōu)先數(shù)的確定 基本的策略：占用CPU時(shí)間少的進(jìn)程優(yōu)先。 靜態(tài)優(yōu)先數(shù)的確定 根據(jù)作業(yè)所需使用的資源來(lái)估計(jì) (多者優(yōu)先，為什么？) 根據(jù)作業(yè)的運(yùn)行時(shí)間來(lái)估計(jì) 由用戶提出 優(yōu)點(diǎn)：簡(jiǎn)單，系統(tǒng)開(kāi)銷(xiāo)小。 問(wèn)題：不準(zhǔn)確、不靈活。 , 動(dòng)態(tài)優(yōu)先數(shù)的確

9、定 在進(jìn)程運(yùn)行期間，優(yōu)先數(shù)可以改變。常用的策略有： (1)對(duì)CPU的時(shí)間進(jìn)行估算，占用少的進(jìn)程優(yōu)先。 一種可行的公式為： k n+1 = a * t n + (1 - a) * k n 其中： k n ：本次估計(jì)的CPU占用時(shí)間 (即本次分配的時(shí)間片) t n ：本次實(shí)際的CPU占用時(shí)間 a 的取值通常為： a = 1： k n+1 = t n 為上一次的實(shí)際占用時(shí)間 a = 0： k n+1 = k n 估計(jì)時(shí)間不變(時(shí)間片固定) a = 1/2: k n+1 =(k n + t n ) / 2 取平均值 ,(2)因設(shè)備請(qǐng)求放棄CPU而等待的進(jìn)程，喚醒后 優(yōu)先提高。以提高設(shè)備的利用率。 因時(shí)

10、間片到而被剝奪CPU的進(jìn)程，應(yīng)如何處理呢？ (3) 進(jìn)程使用CPU超過(guò)一定時(shí)間后，降低優(yōu)先級(jí) 優(yōu)先級(jí)分配存在的問(wèn)題： 有的進(jìn)程可能會(huì)長(zhǎng)時(shí)間等待。 ,四. 短進(jìn)程優(yōu)先調(diào)度算法 (1) 策略：按進(jìn)程運(yùn)行的時(shí)間長(zhǎng)短進(jìn)行調(diào)度。 (2) 特點(diǎn)： 易實(shí)現(xiàn)，系統(tǒng)吞吐量高。 只照顧短進(jìn)程，而沒(méi)有考慮長(zhǎng)進(jìn)程的利益。 (3) 討論周轉(zhuǎn)時(shí)間與帶權(quán)周轉(zhuǎn)時(shí)間 進(jìn)程 提交時(shí)間 執(zhí)行時(shí)間 開(kāi)始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間,8.00 9.10 1.10 1 9.10 9.40 0.40 1.33,問(wèn)題： 長(zhǎng)進(jìn)程可能會(huì)餓死。如何解決呢？,1 8.00 .10 2 8.50 0.50 3 9.00 0.30 4 9.5

11、0 0.10,平均周轉(zhuǎn)時(shí)間 t = 0 . 825 平均帶權(quán)周轉(zhuǎn)時(shí)間 w = 2 . 532,9.40 9.90 1.40 2.8,9.90 10.00 0.50 5,1.下表給出作業(yè)1，2，3的到達(dá)時(shí)間和運(yùn)行時(shí)間。采用FCFS和SJF調(diào)度算法，試問(wèn)平均周轉(zhuǎn)時(shí)間各為多少？是否還有更好的調(diào)度策略存在？,1.【解答】 FCFS：10.53 SJF：9.53 未來(lái)知識(shí)調(diào)度（FKS）:6.86,2.一批五個(gè)作業(yè)A、B、C、D、E幾乎同時(shí)到達(dá)一個(gè)計(jì)算中心，其運(yùn)行時(shí)間分別為10、6、2、4、8分鐘，優(yōu)先數(shù)分別為3、5、2、1、4。對(duì)下列每種調(diào)度算法，確定諸作業(yè)平均周轉(zhuǎn)時(shí)間（相互間切換不計(jì)開(kāi)銷(xiāo)，都不考慮I/

12、O）： RR(每個(gè)時(shí)間片為1分鐘） 優(yōu)先級(jí) FCFS SJF,2.【解答】 RR 21.2分鐘 優(yōu)先級(jí) 16分鐘 FCFS 19.2分鐘 SJF 14分鐘,思考題：,3.某多道程序設(shè)計(jì)系統(tǒng)配有一臺(tái)處理器和兩臺(tái)外設(shè)IO1、IO2，現(xiàn)有3個(gè)優(yōu)先級(jí)由高到低的作業(yè)J1、J2和J3都已裝入了主存，它們使用資源的先后順序和占用時(shí)間分別是： J1:IO2(30ms),CPU(10ms),IO1(30ms),CPU(10ms). J2:IO1(20ms),CPU(20ms),IO2(40ms). J3:CPU(30ms),IO1(20ms). 處理器調(diào)度采用可搶占的優(yōu)先數(shù)算法，忽略其他輔助操作時(shí)間，回答下列問(wèn)題： （1)分別計(jì)算作業(yè)J1、J2和J3從開(kāi)始到完成所用的時(shí)