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

1、第六章 處理機調(diào)度 為了提高處理機的效率，處理機采用多級調(diào)度。 用戶作業(yè)從進入系統(tǒng)成為后備作業(yè)開始，直到運行結束退出系統(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)：在家拿到大學錄取通知書2. 執(zhí)行狀態(tài)：到大學報道注冊3. 完成狀態(tài)：完成答辯后，歸還資源到畢業(yè)離校6.2

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)當作業(yè)處于執(zhí)行狀態(tài)時，其對應的進程不一定處于執(zhí)行狀態(tài)。進程調(diào)度6.2.4調(diào)度算法性能的衡量 調(diào)度目標主要有一下四點：1. 對所有作業(yè)應該是公平合理的；2. 應使設備有高的利用率；3. 系統(tǒng)吞吐量大；4. 有較快的響應時間； 但這些目標本身有些是相互沖突的。6.2.4調(diào)度算法性能的衡量 通常用平均周轉(zhuǎn)時間和平均帶權周轉(zhuǎn)時間衡量作業(yè)調(diào)度算法的好壞。1、平均周轉(zhuǎn)時間t= 其中：ti=tcitsiti是作業(yè)的周轉(zhuǎn)時間

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

4、時間周轉(zhuǎn)時間 ti=tci-tsi帶權周轉(zhuǎn)時間帶權周轉(zhuǎn)時間Wi=ti/tri18.002.008.0010.002.001.0028.500.5010.0010.502.004.0039.000.1010.5010.601.601649.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è)作為下一次服務的對象。例如：下列作業(yè)序列采用SJF算法（為方便計算采用十進制），分別計算平均周轉(zhuǎn)時間和平均帶權周轉(zhuǎn)時間。作業(yè)作業(yè)進入系統(tǒng)時間進入系統(tǒng)時間

5、tsi執(zhí)行時間執(zhí)行時間tri開始時間開始時間完成時間完成時間 tci周轉(zhuǎn)時間周轉(zhuǎn)時間 ti=tci-tsi帶權周轉(zhuǎn)時間帶權周轉(zhuǎn)時間Wi=ti/tri18.002.008.0010.002.001.0028.500.5010.3010.802.34.6039.000.1010.0010.101.101149.500.2010.1010.300.84調(diào)度次序1342 t=1.55 w=5.15缺點：只照顧短作業(yè)的利益，而不考慮長作業(yè)的利益。6.2.5作業(yè)調(diào)度算法作業(yè)調(diào)度算法3、響應比高者優(yōu)先調(diào)度算法（介于二者之間的一種折中算法）響應比rp=響應時間/執(zhí)行時間響應時間=等待時間+執(zhí)行時間rp=1+等

6、待時間/執(zhí)行時間 或rp=等待時間/執(zhí)行時間當調(diào)度時，需計算后備作業(yè)的響應比，然后選擇響應比最高者投入運行。作業(yè)作業(yè)進入系統(tǒng)時間進入系統(tǒng)時間tsi執(zhí)行時間執(zhí)行時間tri開始時間開始時間完成時間完成時間 tci周轉(zhuǎn)時間周轉(zhuǎn)時間 ti=tci-tsi帶權周轉(zhuǎn)時間帶權周轉(zhuǎn)時間Wi=ti/tri18.002.008.0010.002.001.0028.500.5039.000.1049.500.20開始時，調(diào)度作業(yè)1投入運行。當作業(yè)1結束時，需要計算后備隊列作業(yè)的響應比。當作業(yè)1結束時：rp2=(10.00-8.50)/0.5=3rp3=(10.00-9.00)/0.1=10rp4=(10.00-9.

7、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帶權周轉(zhuǎn)時間帶權周轉(zhuǎn)時間Wi=ti/tri18.002.008.0010.002.001.0028.500.5039.000.1010.0010.101.11149.500.20當作業(yè)3結束時：rp2=(10.10-8.50)/0.5=3.2rp4=(10.10-9.50)/0.2=3作業(yè)2投入運行，最后作業(yè)4運行作業(yè)作業(yè)進入系統(tǒng)時間進入系統(tǒng)時間tsi執(zhí)行時間執(zhí)行時間tri開始時間開始時間完成時間完成時間 tci周轉(zhuǎn)時間周

8、轉(zhuǎn)時間 ti=tci-tsi帶權周轉(zhuǎn)時間帶權周轉(zhuǎn)時間Wi=ti/tri18.002.008.0010.002.001.0028.500.5010.1010.602.14.239.000.1010.0010.101.11149.500.2010.6010.801.36.5調(diào)度次序1324t=1.625 w=5.675缺點：每次需要調(diào)度時都要計算響應比，較復雜。2、在一個多道程序設計系統(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開始按響應比高

9、者優(yōu)先算法對它們進行調(diào)度，請計算該作業(yè)序列的平均響應時間。3、有j1,j2,j3三個作業(yè)同時到達，執(zhí)行時間分別為a,b,c且abc,試證明SJF算法能夠獲得最小的平均周轉(zhuǎn)時間。課堂練習課堂練習1、P 157 6.6 FCFS算法：t=2.025 w=4.225 SJF算法： t=1.8375 w=3.28752.在一個多道程序設計系統(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、分）10:5411:543:24（204分）系統(tǒng)在9:00開始按響應比高者優(yōu)先算法對它們進程調(diào)度，請計算該作業(yè)序列的平均響應時間。分析：響應比=等待時間/執(zhí)行時間9:00時，rpA=70/90=7/9，rpB=60/24=5/2，rpC=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í)行的進程因中斷

11、調(diào)用、自陷、請求I/O服務等而阻塞；3.在分時系統(tǒng)中，進程分配的時間片用完；4.在可剝奪方式中，有優(yōu)先級更高的進程要求處理；6.3進程調(diào)度三：進程調(diào)度方式當有優(yōu)先級更高的進程進入就緒隊列時，如何分配處理機？1、非剝奪方式：讓正在執(zhí)行的進程繼續(xù)執(zhí)行，直到該進程完成或因某事件而進入“等待”時，才把處理機分配給優(yōu)先級更高的進程。2、可剝奪方式：當優(yōu)先級更高的進程一到，便暫停正在執(zhí)行的進程，立即把處理機分配給它。3、選擇可搶占策略：每個進程不僅有優(yōu)先級，而且還有一對標志（U、V）U=1，表示該進程可以搶占另一進程U=0，表示該進程不可搶占另一進程V=1，表示該進程可以被另一進程搶占V=0，表示該進程不

12、可被另一進程搶占U、V的值可根據(jù)進程的動態(tài)特征由系統(tǒng)臨時提交，這樣，就使搶占方式具有一定的靈活性。例如： :表示該進程可以搶占另一進程，但不 能被其它的進程搶占。UV106.3.4進程優(yōu)先數(shù)調(diào)度算法思想：把處理機分配給就緒隊列中優(yōu)先權最高的進程。1.不可搶占優(yōu)先權算法2.可搶占優(yōu)先權算法優(yōu)先權的處理較為關鍵一靜態(tài)優(yōu)先權在進程建立時確定，且規(guī)定它在進程的整個運行期間保持不變。確定優(yōu)先權的依據(jù)有： 進程所需資源的要求。如進程的執(zhí)行時間及內(nèi)存需要量少的應賦予較高的優(yōu)先權。 進程類型。如系統(tǒng)進程的優(yōu)先權應高于用戶進程。 根據(jù)用戶類型。如按用戶付費用的多少來確定優(yōu)先權。6.3.4進程優(yōu)先數(shù)調(diào)度算法二 .

13、 動態(tài)優(yōu)先權在進程創(chuàng)建時所賦予的優(yōu)先權，可以隨著進程的推進而改變，以便獲得更好的調(diào)度性能。P155 UNIX系統(tǒng)中優(yōu)先數(shù)的計算優(yōu)先數(shù)P_pri=min127,P_cpu/16-P_nice+PUSER優(yōu)先數(shù)P_pri越大，則優(yōu)先級越小。PUSER是固定偏置常數(shù)，定為100P_nice的值默認為20，可以用命令nice設置P_cpu的值可變，當時鐘信號到來時，當前進程的P_cpu+1,直到255，而每過1S，內(nèi)核中計算優(yōu)先數(shù)的程序又將所有進程的P_cpu-10，當P_cpu10時，P_cpu置0。這樣的負反饋過程使系統(tǒng)中在用戶態(tài)下運行的各個進程都能比較均衡地享用處理機。P_cpu P_pri 進

14、程優(yōu)先級 進程被調(diào)度的機會進程被調(diào)度的機會 進程優(yōu)先級 P_pri P_cpu6.3.5循環(huán)輪轉(zhuǎn)調(diào)度 在分時系統(tǒng)中，系統(tǒng)規(guī)定1個時間片，每個進程被調(diào)度時分得1個時間片，當這一時間片用完時，該進程就轉(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為用戶可接受的響應時間 n為進入系統(tǒng)的最大進程數(shù) 如t=3s,n=100,則q=30ms如果q太大，則退化為FIFO算法如果q太小，則會導致系統(tǒng)開銷的增加。切換占時間片10%。q的值通常為幾百ms6.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/

15、6=500ms在輪轉(zhuǎn)過程中，如果有新的進程到達，都暫時不進入就緒隊列。如果此時到達24個進程，經(jīng)過一輪后，n=24+6=30此時q2=3/30=100ms?？梢詼p少系統(tǒng)開銷。CPUPCB1PCB2PCB6就緒隊列6.3.6多級反饋隊列調(diào)度多級反饋隊列調(diào)度1.當上一個隊列空時，才調(diào)度下一個隊列；2.當1個進程的時間片用完時，進入下一個就緒隊列；3.當進程由等待變成就緒時，進入第1個隊列；這種算法可以先用較小的時間片處理完那些需時間較短的進程，而給那些需時間較長的進程分配較大的時間片，以免較長的進程頻繁中斷而影響處理機的效率。CPU就緒隊列1就緒隊列2就緒隊列n時間片 q 2q: 2nq優(yōu)先權高低

16、:假設一個計算機系統(tǒng)具有如下特征：處理一次中斷，平均耗用1ms;一次進程調(diào)度，平均需要2ms;將CPU分配給選中的進程，又需要平均1ms;再假設其定時器芯片每秒產(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再將

17、CPU分配給選中的進程，又需要平均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)建、撤銷和切換中，涉及資源的釋放，系統(tǒng)必須付出較大的時

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

19、O活動的信息。指針指針1指針2指針3 pid TCB1TCB2TCBnPCB代碼段數(shù)據(jù)段堆棧段 PTDB段(Per Threads Data Area)IBM OS/2系統(tǒng)中允許每個進程最多可創(chuàng)建255個線程。二、二、線程的描述線程的描述1. 當1個進程執(zhí)行時，它只有一個線程，如果需要進程可以繼續(xù)創(chuàng)建新的線程，也就是一個進程可以包含多個控制線程，每個線程運行進程中的一個程序段，這樣，進程就有多個執(zhí)行路徑，增強了并行處理能力。2. 線程完全繼承父進程占有的資源，當它活動時具有自己的運行現(xiàn)場。指針指針1指針2指針3 pid TCB1TCB2TCBnPCB代碼段數(shù)據(jù)段堆棧段 PTDB段(Per Th

20、reads 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)的吞吐量。三、線程與進程的比較3. 擁有資源： 進程是擁有資源的一個獨立單位；線程自己不擁有系統(tǒng)資源（也有一點必不可少的資源

21、），但可訪問其隸屬進程的資源。即一個進程的代碼段、數(shù)據(jù)段及系統(tǒng)資源可供同一進程的所有線程共享。三、線程與進程的比較4. 系統(tǒng)開銷： 線程切換只需保存和設置少量寄存器的內(nèi)容，并不涉及存儲器管理方面的操作。進程切換的開銷遠大于線程切換的開銷。四、四、線程的狀態(tài)及變遷線程的狀態(tài)及變遷1. 創(chuàng)建：建立的新生線程處于新建狀態(tài)，已完成初始化。2. 就緒：進入線程就緒隊列，一旦分到CPU時間，就可立即運行。3. 運行：一個線程正占用CPU，執(zhí)行它的程序。4. 等待：讓出CPU，暫時終止自己的執(zhí)行，進入等待狀態(tài)。5. 終止：一個線程已經(jīng)退出，但該信息還未被其他線程所收集。創(chuàng)建就緒執(zhí)行等待終止線程調(diào)度6.4線程

22、調(diào)度線程調(diào)度采用優(yōu)先數(shù)調(diào)度算法1. 當優(yōu)先級不同時，采用可搶占式線程調(diào)度2. 當優(yōu)先級相同時，采用輪轉(zhuǎn)調(diào)度。例題1.期末試題作業(yè)調(diào)度（響應比）+進程調(diào)度例題2.期末試題作業(yè)調(diào)度（SJF）+進程調(diào)度習題課：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假設作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進程調(diào)度采用以優(yōu)先數(shù)為基礎的搶占式調(diào)度算法（表中所列優(yōu)先數(shù)即為進程優(yōu)先數(shù)，數(shù)值越小優(yōu)先級越高）。 列出各作