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

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

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

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

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

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

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

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

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

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

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

12、O）： RR(每個時間片為1分鐘） 優(yōu)先級 FCFS SJF,2.【解答】 RR 21.2分鐘 優(yōu)先級 16分鐘 FCFS 19.2分鐘 SJF 14分鐘,思考題：,3.某多道程序設(shè)計系統(tǒng)配有一臺處理器和兩臺外設(shè)IO1、IO2，現(xiàn)有3個優(yōu)先級由高到低的作業(yè)J1、J2和J3都已裝入了主存，它們使用資源的先后順序和占用時間分別是： 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ù)算法，忽略其他輔助操作時間，回答下列問題： （1)分別計算作業(yè)J1、J2和J3從開始到完成所用的時