操作系統(tǒng)第六章 處理機調(diào)度

1、第六章 處理機調(diào)度 為了提高處理機的效率，處理機采用多級 調(diào)度。 用戶作業(yè)從進入系統(tǒng)成為后備作業(yè)開始， 直到運行結(jié)束退出系統(tǒng)為止，需要經(jīng)過不 同級別的調(diào)度。 批處理OS可能經(jīng)歷作業(yè)調(diào)度、進程調(diào)度、 線程調(diào)度 分時OS 可能經(jīng)歷進程調(diào)度、線程調(diào)度 6.2作業(yè)調(diào)度作業(yè)調(diào)度 作業(yè)可以是一次計算，一個控制過程。 作業(yè)的狀態(tài)： 1. 后備狀態(tài)：作業(yè)在輔存上，并建立JCB，等待調(diào)度； 2. 執(zhí)行狀態(tài)：作業(yè)進入主存，到作業(yè)計算完成為止； 3. 完成狀態(tài)：從作業(yè)計算完成開始，到善后處理完畢并退 出系統(tǒng)為止。 例如： 1. 后備狀態(tài)：在家拿到大學(xué)錄取通知書 2. 執(zhí)行狀態(tài)：到大學(xué)報道注冊 3. 完成狀態(tài)：完成答

2、辯后，歸還資源到畢業(yè)離校 6.2作業(yè)調(diào)度作業(yè)調(diào)度 作業(yè)調(diào)度的功能主要是完成作業(yè)從后備執(zhí)行和執(zhí)行完 成狀態(tài)的轉(zhuǎn)變。 其中主要的是按一定的調(diào)度算法，從后備作業(yè)隊列中選出 一個作業(yè)投入運行。 執(zhí)行 就緒等待后備 完成 作業(yè)調(diào)度 作業(yè)調(diào)度 執(zhí)行狀態(tài) 當(dāng)作業(yè)處于執(zhí)行狀態(tài)時，其對應(yīng)的進程不一定處于執(zhí)行狀態(tài)。 進程調(diào)度 6.2.4調(diào)度算法性能的衡量 調(diào)度目標主要有一下四點： 1. 對所有作業(yè)應(yīng)該是公平合理的； 2. 應(yīng)使設(shè)備有高的利用率； 3. 系統(tǒng)吞吐量大； 4. 有較快的響應(yīng)時間； 但這些目標本身有些是相互沖突的。 6.2.4調(diào)度算法性能的衡量 通常用平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間 衡量作業(yè)調(diào)度算法的好

3、壞。 1、平均周轉(zhuǎn)時間t= 其中：ti=tcitsi ti是作業(yè)的周轉(zhuǎn)時間; tci是作業(yè)i的完成時間(closure); tsi是作業(yè)i進入系統(tǒng)的時間; i=1 n ti 1 n 6.2.4調(diào)度算法性能的衡量 通常用平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間 衡量作業(yè)調(diào)度算法的好壞。 2、平均帶權(quán)周轉(zhuǎn)時間w= 其中：wi=ti/tri ti是作業(yè)i的周轉(zhuǎn)時間 tri是作業(yè)i的執(zhí)行時間 i=1 n wi 1 n 6.2.5作業(yè)調(diào)度算法 1.先來先服務(wù)調(diào)度算法（FCFS算法） 思想：作業(yè)按來到的先后次序進行調(diào)度 例如：下列作業(yè)序列采用FCFS算法（為方便計算采用十 進制），分別計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)

4、時間。 作業(yè)作業(yè) 進入系統(tǒng)時間進入系統(tǒng)時間 tsi 執(zhí)行時間執(zhí)行時間 tri 開始時間開始時間完成時間完成時間 tci 周轉(zhuǎn)時間周轉(zhuǎn)時間 ti=tci-tsi 帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 Wi=ti/tri 18.002.008.0010.002.001.00 28.500.5010.0010.502.004.00 39.000.1010.5010.601.6016 49.500.2010.6010.801.306.6 調(diào)度次序1234 t=1.725 w=6.875 特點：對短作業(yè)不利 6.2.5作業(yè)調(diào)度算法 2.短作業(yè)優(yōu)先調(diào)度算法（SJF算法） 思想：從后備作業(yè)中選擇執(zhí)行時間最短的作業(yè)作為下

5、一 次服務(wù)的對象。 例如：下列作業(yè)序列采用SJF算法（為方便計算采用十 進制），分別計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。 作業(yè)作業(yè) 進入系統(tǒng)時間進入系統(tǒng)時間 tsi 執(zhí)行時間執(zhí)行時間 tri 開始時間開始時間完成時間完成時間 tci 周轉(zhuǎn)時間周轉(zhuǎn)時間 ti=tci-tsi 帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 Wi=ti/tri 18.002.008.0010.002.001.00 28.500.5010.3010.802.34.60 39.000.1010.0010.101.1011 49.500.2010.1010.300.84 調(diào)度次序1342 t=1.55 w=5.15 缺點：只照顧短作業(yè)的利益，

6、而不考慮長作業(yè)的利益。 6.2.5作業(yè)調(diào)度算法作業(yè)調(diào)度算法 3、響應(yīng)比高者優(yōu)先調(diào)度算法（介于二者之間的一種折中算法） 響應(yīng)比rp=響應(yīng)時間/執(zhí)行時間 響應(yīng)時間=等待時間+執(zhí)行時間 rp=1+等待時間/執(zhí)行時間 或rp=等待時間/執(zhí)行時間 當(dāng)調(diào)度時，需計算后備作業(yè)的響應(yīng)比，然后選擇響應(yīng)比最高者投入運 行。 作業(yè)作業(yè) 進入系統(tǒng)時間進入系統(tǒng)時間 tsi 執(zhí)行時間執(zhí)行時間 tri 開始時間開始時間完成時間完成時間 tci 周轉(zhuǎn)時間周轉(zhuǎn)時間 ti=tci-tsi 帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 Wi=ti/tri 18.002.008.0010.002.001.00 28.500.50 39.000.10 4

7、9.500.20 開始時，調(diào)度作業(yè)1投入運行。 當(dāng)作業(yè)1結(jié)束時，需要計算后備隊列作業(yè)的響應(yīng)比。 當(dāng)作業(yè)1結(jié)束時： rp2=(10.00-8.50)/0.5=3 rp3=(10.00-9.00)/0.1=10 rp4=(10.00-9.50)/0.2=2.5 作業(yè)3投入運行 作業(yè)作業(yè) 進入系統(tǒng)時間進入系統(tǒng)時間 tsi 執(zhí)行時間執(zhí)行時間 tri 開始時間開始時間完成時間完成時間 tci 周轉(zhuǎn)時間周轉(zhuǎn)時間 ti=tci-tsi 帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 Wi=ti/tri 18.002.008.0010.002.001.00 28.500.50 39.000.1010.0010.101.111 49

8、.500.20 當(dāng)作業(yè)3結(jié)束時： rp2=(10.10-8.50)/0.5=3.2 rp4=(10.10-9.50)/0.2=3 作業(yè)2投入運行， 最后作業(yè)4運行 作業(yè)作業(yè) 進入系統(tǒng)時間進入系統(tǒng)時間 tsi 執(zhí)行時間執(zhí)行時間 tri 開始時間開始時間完成時間完成時間 tci 周轉(zhuǎn)時間周轉(zhuǎn)時間 ti=tci-tsi 帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 Wi=ti/tri 18.002.008.0010.002.001.00 28.500.5010.1010.602.14.2 39.000.1010.0010.101.111 49.500.2010.6010.801.36.5 調(diào)度次序1324 t=1.62

9、5 w=5.675 缺點：每次需要調(diào)度時都要計算響應(yīng)比，較復(fù)雜。 2、在一個多道程序設(shè)計系統(tǒng)中，有3個作業(yè)A,B,C，到達輸入井的時間如 下： 進程 到達時間 運行時間（小 時） 開始執(zhí)行時間完成時間周轉(zhuǎn)時間 （分） A7：501.5（(90分) B8：000.4（24分） C8：301（60分） 系統(tǒng)在9:00開始按響應(yīng)比高者優(yōu)先算法對它們進行調(diào)度，請計算該作業(yè)序列 的平均響應(yīng)時間。 3、有j1,j2,j3三個作業(yè)同時到達，執(zhí)行時間分別為a,b,c且abc,試證明SJF算法 能夠獲得最小的平均周轉(zhuǎn)時間。 課堂練習(xí)課堂練習(xí) 1、P 157 6.6 FCFS算法：t=2.025 w=4.225

10、SJF算法： t=1.8375 w=3.2875 2.在一個多道程序設(shè)計系統(tǒng)中，有3個作業(yè)A,B,C，到達輸入井的時間如下： 進程到 達 時 間 運行時間（小 時） 開始執(zhí)行時間完成時間周 轉(zhuǎn) 時 間 （分） A7：501.5（(90分)9:2410:543:04（184分) B8：000.4（24分）9:009:241:24（84分） C8：301（60分）10:5411:543:24（204分） 系統(tǒng)在9:00開始按響應(yīng)比高者優(yōu)先算法對它們進程調(diào)度，請計算該作業(yè)序列 的平均響應(yīng)時間。 分析： 響應(yīng)比=等待時間/執(zhí)行時間 9:00時，rpA=70/90=7/9，rpB=60/24=5/2，r

11、pC=30/60=1/2，作業(yè)B執(zhí)行 9:24時，rpA=94/90=47/45， rpC=54/60=9/10，作業(yè)A執(zhí)行 周轉(zhuǎn)時間=完成時間到達時間， t=（184+84+204）/3=157分。 6.3進程調(diào)度 一：進程調(diào)度的功能 將進程按一定的策略從就緒隊列中移出并建立它 執(zhí)行的機器狀態(tài)。 二、進程調(diào)度的時機可能有以下幾種情況 1.正在執(zhí)行的進程執(zhí)行完畢； 2.執(zhí)行的進程因中斷調(diào)用、自陷、請求I/O服務(wù)等 而阻塞； 3.在分時系統(tǒng)中，進程分配的時間片用完； 4.在可剝奪方式中，有優(yōu)先級更高的進程要求處 理； 6.3進程調(diào)度 三：進程調(diào)度方式 當(dāng)有優(yōu)先級更高的進程進入就緒隊列時，如何分配

12、處理機？ 1、非剝奪方式：讓正在執(zhí)行的進程繼續(xù)執(zhí)行，直到該進程完成或因某 事件而進入“等待”時，才把處理機分配給優(yōu)先級更高的進程。 2、可剝奪方式：當(dāng)優(yōu)先級更高的進程一到，便暫停正在執(zhí)行的進程，立 即把處理機分配給它。 3、選擇可搶占策略： 每個進程不僅有優(yōu)先級，而且還有一對標志（U、V） U=1，表示該進程可以搶占另一進程 U=0，表示該進程不可搶占另一進程 V=1，表示該進程可以被另一進程搶占 V=0，表示該進程不可被另一進程搶占 U、V的值可根據(jù)進程的動態(tài)特征由系統(tǒng)臨時提交，這樣，就使搶 占方式具有一定的靈活性。 例如： :表示該進程可以搶占另一進程，但不 能被其它的進程搶占。 UV 1

13、0 6.3.4進程優(yōu)先數(shù)調(diào)度算法 思想：把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進程。 1.不可搶占優(yōu)先權(quán)算法 2.可搶占優(yōu)先權(quán)算法 優(yōu)先權(quán)的處理較為關(guān)鍵 一靜態(tài)優(yōu)先權(quán) 在進程建立時確定，且規(guī)定它在進程的整個運行期間保持 不變。確定優(yōu)先權(quán)的依據(jù)有： 進程所需資源的要求。如進程的執(zhí)行時間及內(nèi)存需要 量少的應(yīng)賦予較高的優(yōu)先權(quán)。 進程類型。如系統(tǒng)進程的優(yōu)先權(quán)應(yīng)高于用戶進程。 根據(jù)用戶類型。如按用戶付費用的多少來確定優(yōu)先權(quán)。 6.3.4進程優(yōu)先數(shù)調(diào)度算法 二 . 動態(tài)優(yōu)先權(quán) 在進程創(chuàng)建時所賦予的優(yōu)先權(quán)，可以隨著進 程的推進而改變，以便獲得更好的調(diào)度性能。 P155 UNIX系統(tǒng)中優(yōu)先數(shù)的計算 優(yōu)先數(shù)P_p

14、ri=min127,P_cpu/16-P_nice+PUSER 優(yōu)先數(shù)P_pri越大，則優(yōu)先級越小。 PUSER是固定偏置常數(shù)，定為100 P_nice的值默認為20，可以用命令nice設(shè)置 P_cpu的值可變，當(dāng)時鐘信號到來時，當(dāng)前進程的P_cpu+1,直到255， 而每過1S，內(nèi)核中計算優(yōu)先數(shù)的程序又將所有進程的P_cpu-10，當(dāng) P_cpu10時，P_cpu置0。 這樣的負反饋過程使系統(tǒng)中在用戶態(tài)下運行的各個進程都能比較均衡地享 用處理機。 P_cpu P_pri 進程優(yōu)先級 進程被調(diào)度的機會 進程被調(diào)度的機會 進程優(yōu)先級 P_pri P_cpu 6.3.5循環(huán)輪轉(zhuǎn)調(diào)度 在分時系統(tǒng)中，

15、系統(tǒng)規(guī)定1個時間片，每個 進程被調(diào)度時分得1個時間片，當(dāng)這一時間 片用完時，該進程就轉(zhuǎn)為就緒態(tài)并進入就 緒隊列的末端。 6.3.5循環(huán)輪轉(zhuǎn)調(diào)度 1. 簡單循環(huán)輪轉(zhuǎn)調(diào)度 時間片q固定，q=t/n t為用戶可接受的響應(yīng)時間 n為進入系統(tǒng)的最大進程數(shù) 如t=3s,n=100,則q=30ms 如果q太大，則退化為FIFO算法 如果q太小，則會導(dǎo)致系統(tǒng)開銷的增加。切換占 時間片10%。q的值通常為幾百ms 6.3.5循環(huán)輪轉(zhuǎn)調(diào)度循環(huán)輪轉(zhuǎn)調(diào)度 2、可變時間片輪轉(zhuǎn)調(diào)度 例如：t=3s,n=6如圖所示 此時q1=3s/6=500ms 在輪轉(zhuǎn)過程中，如果有新的進程到達，都暫時不進入就緒隊列。 如果此時到達24個

16、進程，經(jīng)過一輪后，n=24+6=30 此時q2=3/30=100ms。 可以減少系統(tǒng)開銷。 CPU PCB1PCB2PCB6 就緒隊列 6.3.6多級反饋隊列調(diào)度多級反饋隊列調(diào)度 1.當(dāng)上一個隊列空時，才調(diào)度下一個隊列； 2.當(dāng)1個進程的時間片用完時，進入下一個就緒隊列； 3.當(dāng)進程由等待變成就緒時，進入第1個隊列； 這種算法可以先用較小的時間片處理完那些需時間較短的進程，而給那些需 時間較長的進程分配較大的時間片，以免較長的進程頻繁中斷而影響處理機 的效率。 CPU 就緒隊列1 就緒隊列2 就緒隊列n 時間片 q 2q : 2nq 優(yōu)先權(quán) 高 低 : : 假設(shè)一個計算機系統(tǒng)具有如下特征： 處

17、理一次中斷，平均耗用1ms; 一次進程調(diào)度，平均需要2ms; 將CPU分配給選中的進程，又需要平均1ms; 再假設(shè)其定時器芯片每秒產(chǎn)生100次中斷，請回答： 操作系統(tǒng)將百分之幾的CPU數(shù)據(jù)用于時鐘中斷處理？ 如果操作系統(tǒng)采用輪轉(zhuǎn)法調(diào)度，10個時鐘中斷為1個時間片。那么，操作系 統(tǒng)將百分之幾的CPU時間用于進程調(diào)度（包括調(diào)度，分配CPU和引起調(diào)度時 的時鐘中斷處理時間）？ 解： 1001ms/1s10% 時間片的大小10（1S/100）=100ms /每10ms產(chǎn)生1個時鐘中斷信號 1個時間片要處理10個時鐘中斷，需要101ms=10ms 時間片到后再進行一次進程調(diào)度，需要2ms 再將CPU分配

18、給選中的進程，又需要平均1ms 系統(tǒng)將CPU時間的（1012）/10013%用于進程調(diào)度。 4.2.5線程概念及特點（threads） 自60年代提出進程的概念后，在OS中 一直都是以進程作為能獨立運行的基本單 位。直到80年代中期，人們又提出了一個 比進程更小的能獨立運行的基本單位線 程，用來提高系統(tǒng)的并發(fā)執(zhí)行程度，從而 提高系統(tǒng)的吞吐量。 4.2.5線程概念及特點（threads） 一什么是線程 進程的兩個基本屬性 1. 進程是一個可擁有資源的獨立單位。 2. 進程又是一個可以獨立調(diào)度和分配CPU的基本 單位。 由于進程是一個資源擁有者，因而在進程 的創(chuàng)建、撤銷和切換中，涉及資源的釋放，系

19、 統(tǒng)必須付出較大的時空開銷。正因如此，在系 統(tǒng)中所設(shè)置的進程數(shù)目不宜過多，進程切換的 頻率也不宜過高，但這也限制了并發(fā)程度的進 一步提高。 4.2.5線程概念及特點（threads） 如何使多個程序更好的并發(fā)執(zhí)行，同 時又盡量減少系統(tǒng)的開銷，成為設(shè)計操作 系統(tǒng)所追求的重要目標。 進程作為資源分配的基本單位 線程是在進程內(nèi)用于調(diào)度和占有CPU的基本 單位。 每個線程可以用一個現(xiàn)場（context）表示， 現(xiàn)場由PC,GR,PSW組成，這樣線程切換時， 就不涉及資源的分配和釋放。 二、二、線程的描述線程的描述 系統(tǒng)為每個線程都配置一張線程控制塊（TCB）。TCB 包括：Tid ,Context,棧

20、，用于調(diào)度的信息（優(yōu)先級、狀態(tài)） 和有關(guān)I/O活動的信息。 指針指針1 指針2 指針3 pid TCB1 TCB2 TCBn PCB 代碼段 數(shù)據(jù)段 堆棧段 PTDB段 (Per Threads Data Area) IBM OS/2系統(tǒng)中允許每個進程最多可 創(chuàng)建255個線程。 二、二、線程的描述線程的描述 1. 當(dāng)1個進程執(zhí)行時，它只有一個線程，如果需要進程可以繼續(xù)創(chuàng)建新的線程， 也就是一個進程可以包含多個控制線程，每個線程運行進程中的一個程序 段，這樣，進程就有多個執(zhí)行路徑，增強了并行處理能力。 2. 線程完全繼承父進程占有的資源，當(dāng)它活動時具有自己的運行現(xiàn)場。 指針指針1 指針2 指針3

21、 pid TCB1 TCB2 TCBn PCB 代碼段 數(shù)據(jù)段 堆棧段 PTDB段 (Per Threads Data Area) IBM OS/2系統(tǒng)中允許每個進程最多可 創(chuàng)建255個線程。 三、線程與進程的比較 1. 調(diào)度： 線程作為CPU調(diào)度的基本單位，進程作 為資源調(diào)度的基本單位。 在同一進程中，線程的切換不會引起進 程的切換；由一個進程的線程切換到另一 個進程的線程時，將會引起進程的切換。 三、線程與進程的比較 2. 并發(fā)性： 在引入線程的OS 中，不僅進程之間可 以并發(fā)執(zhí)行，而且一個進程中的多個線程 之間也可并發(fā)，因而使OS具有更好的并發(fā) 性，從而能更有效地使用系統(tǒng)資源和提高 系統(tǒng)

22、的吞吐量。 三、線程與進程的比較 3. 擁有資源： 進程是擁有資源的一個獨立單位；線 程自己不擁有系統(tǒng)資源（也有一點必不可 少的資源），但可訪問其隸屬進程的資源。 即一個進程的代碼段、數(shù)據(jù)段及系統(tǒng)資源 可供同一進程的所有線程共享。 三、線程與進程的比較 4. 系統(tǒng)開銷： 線程切換只需保存和設(shè)置少量寄存器 的內(nèi)容，并不涉及存儲器管理方面的操作。 進程切換的開銷遠大于線程切換的開銷。 四、四、線程的狀態(tài)及變遷線程的狀態(tài)及變遷 1. 創(chuàng)建：建立的新生線程處于新建狀態(tài)，已完成初始化。 2. 就緒：進入線程就緒隊列，一旦分到CPU時間，就可立 即運行。 3. 運行：一個線程正占用CPU，執(zhí)行它的程序。

23、4. 等待：讓出CPU，暫時終止自己的執(zhí)行，進入等待狀態(tài)。 5. 終止：一個線程已經(jīng)退出，但該信息還未被其他線程所 收集。 創(chuàng)建就緒 執(zhí)行 等待 終止 線程調(diào)度 6.4線程調(diào)度 線程調(diào)度采用優(yōu)先數(shù)調(diào)度算法 1. 當(dāng)優(yōu)先級不同時，采用可搶占式線程調(diào)度 2. 當(dāng)優(yōu)先級相同時，采用輪轉(zhuǎn)調(diào)度。 例題1.期末試題作業(yè)調(diào)度（響應(yīng)比）+進程調(diào) 度 例題2.期末試題作業(yè)調(diào)度（SJF）+進程調(diào)度 習(xí)題課： 1、在一個兩道批處理系統(tǒng)中，有一作業(yè)序列，其到達時刻/估計運行時間列表 及優(yōu)先數(shù)如下。 作業(yè) 到達時刻（時） 估計運行時間（分鐘） 優(yōu)先數(shù) JA 10:00 40 5 JB 10:20 30 3 JC 10:30 50 4 JD 10:50 20 6 JE 11:00 30 2 假設(shè)作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶 占式調(diào)度算法（表中所列優(yōu)先數(shù)即為