第三章+處理機調(diào)度_new.ppt

1、1,處理機調(diào)度的層次 進程調(diào)度,第3章 處理機調(diào)度*,2,高級調(diào)度 低級調(diào)度 中級調(diào)度,（一）處理機調(diào)度的層次,3,1、高級調(diào)度,高級調(diào)度又稱為作業(yè)調(diào)度，主要功能是根據(jù)某種算法，把外存上處于后備隊列中的那些作業(yè)調(diào)入內(nèi)存，調(diào)度的對象是作業(yè)。 作業(yè)：作業(yè)是比程序更為廣泛的概念，它不僅包含了通常的程序和數(shù)據(jù)，還配有一個作業(yè)說明書，系統(tǒng)根據(jù)作業(yè)說明書來對程序的運行進行控制。 在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。,4,1、高級調(diào)度,作業(yè)控制塊JCB：它包括作業(yè)名、作業(yè)類型、資源要求、當前狀態(tài)、資源使用情況以及該作業(yè)的優(yōu)先級等。,每當作業(yè)進入系統(tǒng)時，系統(tǒng)便為每個作業(yè)建立一個JCB，根據(jù)作業(yè)

2、類型把它插入相應的后備隊列中，作業(yè)調(diào)度程序根據(jù)一定的調(diào)度算法來調(diào)度它們，被調(diào)度到的作業(yè)將會裝入內(nèi)存。進入內(nèi)存的作業(yè)，將為它們創(chuàng)建進程，分配必要的資源，然后將新創(chuàng)建的進程插入到就緒隊列中。,5,1、高級調(diào)度,在每次執(zhí)行作業(yè)調(diào)度時，都須做出以下兩個決定。 1) 接納多少個作業(yè)：即允許多少個作業(yè)同時在內(nèi)存中運行。當內(nèi)存中同時運行的作業(yè)數(shù)目太多時，可能會影響到系統(tǒng)的服務(wù)質(zhì)量。 2) 接納哪些作業(yè)：應將哪些作業(yè)從外存調(diào)入內(nèi)存，這取決于所采用的調(diào)度算法。,6,2、低級調(diào)度,低級調(diào)度也稱為進程調(diào)度。 低級調(diào)度用于決定就緒隊列中的哪個進程獲得處理機。,7,3、中級調(diào)度,中級調(diào)度又稱中程調(diào)度。 引入中級調(diào)度的主

3、要目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。 為此，應使那些暫時不能運行的進程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待，把此時的進程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當這些進程重又具備運行條件、且內(nèi)存又稍有空閑時，由中級調(diào)度來決定把外存上的哪些又具備運行條件的就緒進程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊列上等待進程調(diào)度。,8,（二）進程調(diào)度*,進程調(diào)度需要解決三個主要問題： （1）什么時候分配處理機，即需要確定處理機調(diào)度時機； （2）按什么原則分配處理機，即需要確定處理機調(diào)度算法； （3）如何分配處理機，即需要給出處理機調(diào)度過程。,9,進程調(diào)度,進程調(diào)度的任務(wù)是控制協(xié)調(diào)進程

4、對CPU的競爭，即按一定的調(diào)度算法從就緒隊列中選中一個進程，把CPU的使用權(quán)交給被選中的進程。,10,衡量調(diào)度策略的最常用的幾個指標是： 周轉(zhuǎn)時間：指將一個作業(yè)提交給計算機系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔。 吞吐量：指在單位時間內(nèi)，一個計算機系統(tǒng)所完成的作業(yè)數(shù)。 響應時間：指從用戶向計算機提交一個請求開始，直至系統(tǒng)首次產(chǎn)生響應為止的時間。,11,1. 周轉(zhuǎn)時間： 作業(yè)i的周轉(zhuǎn)時間Ti為 Ti=Tei-Tsi 其中Tei為作業(yè)i的完成時間，Tsi為作業(yè)的提交時間。 對于被測定作業(yè)流所含有的n（n=1）個作業(yè)來說，其平均周轉(zhuǎn)時間為： 一個作業(yè)的周轉(zhuǎn)時間說明了該作業(yè)在系統(tǒng)內(nèi)停留的時間，包含兩部

5、分：等待時間；執(zhí)行時間，即： Ti=TwiTri 這里，Twi主要指作業(yè)i等待處理機的時間。,12,2. 帶權(quán)周轉(zhuǎn)時間 作業(yè)的周轉(zhuǎn)時間包含了兩個部分，即等待時間和執(zhí)行時間。為了更進一步反映調(diào)度性能，使用帶權(quán)周轉(zhuǎn)時間的概念。帶權(quán)周轉(zhuǎn)時間是作業(yè)周轉(zhuǎn)時間與作業(yè)執(zhí)行時間的比： Wi=Ti/Tri 對于被測定作業(yè)流所含有的幾個作業(yè)來說，其平均帶權(quán)周轉(zhuǎn)時間為： 對于分時系統(tǒng)，除了要保證系統(tǒng)吞吐量大、資源利用率高之外，還應保證有用戶能夠容忍的響應時間。因此，在分時系統(tǒng)中，僅僅用周轉(zhuǎn)時間或帶權(quán)周轉(zhuǎn)時間來衡量調(diào)度性能是不夠的。,13,一、何時調(diào)度進程調(diào)度的原因,(1) 正在執(zhí)行的進程執(zhí)行完畢。 (2) 執(zhí)行中進

6、程自己調(diào)用阻塞原語將自己阻塞起來進入睡眠等待狀態(tài)。 (3) 執(zhí)行中進程調(diào)用了P原語操作，從而因資源不足而被阻塞；或調(diào)用了V原語操作激活了等待資源的進程隊列進入就緒隊列，并請求重新調(diào)度。 (4) 執(zhí)行中進程提出IO請求后被阻塞。,14,以上都是在CPU執(zhí)行不可剝奪方式下所引起進程調(diào)度的原因。在CPU執(zhí)行方式是可剝奪時，還有： (5) 在分時系統(tǒng)中時間片已經(jīng)用完。 (6) 就緒隊列中的某進程的優(yōu)先級變得高于當前執(zhí)行進程的優(yōu)先級，從而也將引發(fā)進程調(diào)度。,15,二、調(diào)度時需要做什么進程調(diào)度的功能,1保存“下降”進程現(xiàn)場 2選擇將要運行的進程“上升”進程 3恢復“上升”進程的現(xiàn)場,16,三、調(diào)度算法,引

7、入多道程序系統(tǒng)的直接目的就是想讓處理機“忙”，一直以來處理機都是計算機系統(tǒng)中的瓶頸資源之一，特別是在單處理機系統(tǒng)中，處于就緒狀態(tài)的多個進程競爭使用一臺處理機，所以當處理機空閑時，系統(tǒng)需要從多個就緒進程中挑選一個使其投入運行。選擇哪一個呢？這需要按某一種算法。調(diào)度算法的實質(zhì)就是一種資源分配。 從資源的角度來看，該算法確定了處理機的分配策略，故稱其為處理機調(diào)度算法； 而從資源使用者的角度看，該算法確定了進程運行的次序，故也稱進程調(diào)度算法。,17,不可搶占方式：在這種方式下，一旦把處理機分配給某進程后，便讓他一直運行下去，直到進程完成或發(fā)生某事件而阻塞時，才把處理機分配給另一進程。但存在明顯的缺點：

8、如當一個緊急任務(wù)到達時，不能立即投入運行，實時性差。,進程調(diào)度有兩種基本方式：,不可搶占方式與可搶占方式,18,可搶占方式：在這種方式下，某個進程正在運行時可以被系統(tǒng)以某種原則搶占已分配給它的處理機，將處理機分配給其他進程。搶占原則可以是優(yōu)先權(quán)原則，即高優(yōu)先級進程可以剝奪低優(yōu)先級的進程運行，也可以是時間片原則，在運行進程的時間片用完后被剝奪處理機，重新參與調(diào)度。,19,基本的處理機調(diào)度算法有先來先服務(wù)法、優(yōu)先級法和時間片輪轉(zhuǎn)法等，現(xiàn)在也有些操作系統(tǒng)使用綜合性的調(diào)度算法，比如多級反饋隊列調(diào)度算法等。,20,1先來先服務(wù)調(diào)度算法（First Come First Served，F(xiàn)CFS）,該算法按

9、照進程進入就緒隊列的先后順序選擇最先進入該隊列的進程，把處理機分配給它，使之投入運行。一旦一個進程占有了處理機就一直運行下去，直到該進程完成或因等待某事件而不能繼續(xù)運行才釋放處理機。,D,C,B,A,CPU,完成,21,在單道環(huán)境下，某批處理有四道作業(yè)，已知他們的進入系統(tǒng)的時刻、估計運算時間如下：,進程,到達時刻,執(zhí)行時間,開始時刻,完成時刻,周轉(zhuǎn)時間,帶權(quán)周轉(zhuǎn),A,B,C,D,0,1,2,3,1,100,1,100,0,1,101,102,1,101,102,202,1,100,100,199,1,1,100,1.99,短作業(yè)C的帶權(quán)周轉(zhuǎn)時間高達100。 長作業(yè)D的帶權(quán)周轉(zhuǎn)時間僅為1.99,

10、22,這是一種不可搶占方式的調(diào)度算法，優(yōu)點是實現(xiàn)簡單，缺點是后來的進程等待CPU的時間較長。即有利于長進程，不利于短進程。 在當今系統(tǒng)中，先進先出很少作為調(diào)度模式，而是常常嵌套在其它的調(diào)度模式中。 例如，許多調(diào)度模式根據(jù)優(yōu)先級將處理機分配給進程，但具有相同優(yōu)先級的進程卻按先進先出進行分配。,23,2.最短進程優(yōu)先法（Shortest Process/Job First，SPF/SJF）,SPF/SJF:從就緒隊列中選擇估計運行時間最短的進程，先將處理機分配給它，使它立即執(zhí)行。 非搶占式。 優(yōu)點：減少了在就緒隊列中等待的進程數(shù)，同時也降低了進程的平均等待時間，提高了系統(tǒng)的吞吐量。 缺點：沒有考慮

11、到某些進程的緊迫程度。 用戶作出的估計時間并不準確，帶有很大的主觀性。,24,例：,假設(shè)有5道作業(yè)，它們的提交時間及運行時間由下表給出：作業(yè) 提交時間（時） 運行時間（小時）1 9 2 2 925 13 1005 0754 1225 055 125 025若采用FCFS和SJF兩種調(diào)度算法，指出作業(yè)被調(diào)度順序及平均周轉(zhuǎn)時間。,25,3.最高響應比優(yōu)先算法（ Highest Response Ratio Next， HRN）,是對FCFS方式和SJF方式的一種綜合平衡響應比。 FCFS只考慮了每個作業(yè)的等待時間而未考慮執(zhí)行時間的長短，而SJF只考慮執(zhí)行時間而未考慮等待時間的長短。 HRN算法同時

12、考慮每個作業(yè)的等待時間長短和估計需要的執(zhí)行時間長短，從中選出響應比最高的作業(yè)投入執(zhí)行。,26,3.最高響應比優(yōu)先算法,響應比： R(作業(yè)等待時間需運行時間)/ 需運行時間 1已等待時間 / 需運行時間 1W/T 由于R與要求運行時間成反比，故對短作業(yè)是有利的，另一方面，因R與等待時間成正比，故長作業(yè)隨著其等待時間的增長，也可獲的較高的響應比。這就克服了短作業(yè)優(yōu)先數(shù)法的缺點，既照顧了先來者，又優(yōu)待了短作業(yè)，是上述兩種算法的一種較好的折中。,27,4優(yōu)先級調(diào)度算法（Priority Driven，PD）,總是選擇具有最高優(yōu)先級的進程首先使用處理機。在這種算法中，首先考慮的問題是如何確定進程的優(yōu)先數(shù)

13、。 分為： 靜態(tài)優(yōu)先級：在創(chuàng)建進程的時候便確定的，且在進程的運行期間保持不變。（簡單易行，系統(tǒng)開銷小，但不夠精確，很可能出現(xiàn)優(yōu)先權(quán)低的進程長期不被調(diào)度的情況。所以只在要求不太高的系統(tǒng)中，才使用靜態(tài)優(yōu)先級） 動態(tài)優(yōu)先級：在創(chuàng)建進程時所賦予的優(yōu)先級，可以隨進程的推進而改變，以便獲得更好的調(diào)度性能,28,這是一種可搶占方式的調(diào)度算法，可防止一個長進程長期的壟斷處理機。,若所有的進程具有相同的優(yōu)先級初值，則按照FCFS算法，最先進入就緒隊列的進程最先獲得處理機。若所有的就緒進程具有各不相同的優(yōu)先級初值，對于優(yōu)先級初值低的進程，在等待足夠的時間后，其優(yōu)先級可能升為最高，從而獲得處理機執(zhí)行。,29,進程的

14、靜態(tài)優(yōu)先級確定原則可以是：,(1) 系統(tǒng)根據(jù)進程要求資源情況確定優(yōu)先級。例如根據(jù)估計所需處理機時間、內(nèi)存量大小、IO設(shè)備類型及數(shù)量等，確定進程的優(yōu)先級。 (2) 按進程的類型給予不同的優(yōu)先級。例如，在有些系統(tǒng)中，進程被劃分為系統(tǒng)進程和用戶進程。系統(tǒng)進程享有比用戶進程高的優(yōu)先級。,30,進程的動態(tài)優(yōu)先級一般根據(jù)以下原則確定：,(1) 根據(jù)進程占有CPU時間的長短來決定。一個進程占有處理機的時間愈長，則在被阻塞之后再次獲得調(diào)度的優(yōu)先級就越低，反之，其獲得調(diào)度的可能性就會越大。 (2) 根據(jù)就緒進程等待CPU的時間長短來決定。一個就緒進程在就緒隊列中等待的時間越長，則它獲得調(diào)度選中的優(yōu)先級就越高。

15、由于動態(tài)優(yōu)先級隨時間的推移而變化，系統(tǒng)要經(jīng)常計算各進程的優(yōu)先級，因此，系統(tǒng)要為此付出一定的開銷。,31,例： 有5個進程P1、P2、P3、P4、P5，它們同時依次進入就緒隊列，它們的優(yōu)先數(shù)和需要的處理機時間如下：,進程 處理機時間 優(yōu)先數(shù) P1 10 3 P2 1 1 P3 2 3 P4 1 4 P5 5 2,32,忽略進程調(diào)度所花的時間，要求：,（1）分別寫出采用先來先服務(wù)調(diào)度算法和靜態(tài)優(yōu)先級調(diào)度算法中進程的執(zhí)行次序； （2）分別計算各進程在就緒隊列中的等待時間和平均等待時間。 解：（1）采用先來先服務(wù)調(diào)度算法時各進程的執(zhí)行次序為：P1P2P3P4P5。 采用靜態(tài)優(yōu)先級調(diào)度算法時各進程的執(zhí)行

16、次序為： P4P1P3P5P2。,33,（2）FCFS中，平均等待時間（0+10+11+13+14）/59.6；靜態(tài)優(yōu)先級法中，平均等待時間（1+18+11+0+13）/58.6,進程 處理機時間 FCFS等待時間 靜態(tài)優(yōu)先級法等待時間 P1 10 0 1 P2 1 10 18 P3 2 11 11 P4 1 13 0 P5 5 14 13,34,5時間片輪轉(zhuǎn)調(diào)度算法Round-Robin (RR),基本思想：系統(tǒng)把所有的就緒進程按FCFS原則排成一個隊列，且規(guī)定一個時間片作為進程每次使用處理機的最長時間單位，按時間片把處理機輪流分配給當前位于就緒隊列隊首的進程使用，當該進程的時間片用完以后，

17、系統(tǒng)產(chǎn)生時鐘中斷，剝奪該進程的執(zhí)行，將它送到就緒隊列隊尾，等待下一輪次的調(diào)度。同時處理機調(diào)度程序又去調(diào)度當前就緒隊列的隊首進程，也讓它運行給定的時間片，如此循環(huán)往復。,35,F,C,B,A,.,CPU,完成,A,B C,時間片輪轉(zhuǎn)算法圖示,這就使得就緒隊列中所有的進程，都能在一有限的時間內(nèi)，輪流獲得一個時間片的執(zhí)行時間。 該算法適合分時系統(tǒng)使用。,36,時間片選擇,在輪轉(zhuǎn)法中，時間片長度的選取非常重要。首先，時間片長度的選擇會直接影響系統(tǒng)開銷和響應時間。如果時間片長度過短，則調(diào)度程序剝奪處理機的次數(shù)增多。這將使進程上下文切換次數(shù)也大大增加，從而加重系統(tǒng)開銷。反過來，如果時間片長度選擇過長，比方

18、說一個時間片能保證就緒隊列中所需執(zhí)行時間最長的進程能執(zhí)行完畢，則輪轉(zhuǎn)法變成了先來先服務(wù)法。,37,最佳時間片的確定,這個最佳的時間片值是多少呢？顯然，它將隨系統(tǒng)而異。隨負載而異，同時也隨進程而異。 時間片的選取是實現(xiàn)各種調(diào)度算法的關(guān)鍵之處，而時間片的選定通常應考慮終端數(shù)目，處理機能力、各終端任務(wù)的急迫程度、外存?zhèn)鬏斔俣鹊确矫娴囊蛩亍?38,例： 有5個進程P1、P2、P3、P4、P5，它們同時依次進入就緒隊列，請寫出使用輪轉(zhuǎn)法調(diào)度時的調(diào)度次序，各進程的周轉(zhuǎn)時間和等待時間，其中時間片為2：,進程 處理機時間 P1 10 P2 1 P3 2 P4 1 P5 5,39,RR算法,每個進程被分配一個時間段，稱作它的時間片，即該進程允許運行的時間。如果在時間片結(jié)束時進程還在運行，則CPU將被剝奪并分配給另一個進程。如果進程在時間片結(jié)束前阻塞或結(jié)束，則CPU當即進行切換。,40,習題1：假設(shè)有4道作業(yè)，它們的提交時刻及執(zhí)行時間由下表給出： 計算采用先來先服務(wù)調(diào)度算法和最短作業(yè)優(yōu)先調(diào)度算法時的平均周