1、第3章 處理機調度,1 調度級別 2 調度的功能、時機及方式 3 調度原則與評估標準 4 調度算法 5 調度的實現, 調 度 級 別,.高級調度 即作業(yè)調度。它決定允許哪些作業(yè)可參與競爭和其它系統(tǒng)資源，從狀態(tài)觀點，就是將一個或一批作業(yè)從后備狀態(tài)變?yōu)檫\行狀態(tài)。一個作業(yè)一旦被高級調度選中，便可獲得所需要的基本內存和設備資源，并被裝入內存，此后就以進程形式參與并發(fā)運行，與其它進程競爭。換言之，高級調度決定給哪個作業(yè)分配一臺虛擬處理機，獲得虛擬處理機的作業(yè)將在該虛擬處理機上順序執(zhí)行。從這個意義上說，高級調度進行的是虛擬處理機的分配，即的宏觀調度，故高級調度亦稱宏觀調度。,中級調度 中級調度決定哪些進程

2、可參與競爭，從狀態(tài)觀點，就是將進程從活動態(tài)變?yōu)殪o止的掛起態(tài)，或者將進程從掛起態(tài)變?yōu)榫途w態(tài)或等待態(tài)。這主要是為了短期調整系統(tǒng)負荷，以緩和內存使用緊張的矛盾。中級調度的實質是執(zhí)行“掛起”和“激活”操作；掛起一個進程是把該進程的實體（程序和數據）從內存遷移到外存的專門區(qū)域，稱為交換區(qū)，并釋放該進程占用的用戶內存區(qū)，這稱為“換出”；反之，激活一個進程是把該進程的實體從外存交換區(qū)遷移到內存，這稱為“換進”。故中級調度也常稱為進程交換，通常僅用于分時系統(tǒng)。,低級調度 即進程調度。它決定哪個進程可獲得物理，從狀態(tài)觀點，就是將某個進程從就緒態(tài)變?yōu)閳?zhí)行態(tài)。被低級調度選中的進程將實際獲得，并可立即在物理上執(zhí)行它的

3、程序。因此，低級調度是處理機三級調度中的終結調度，亦稱的微觀調度。,圖- 處理機的三級調度, 調度的功能、時機及方式,. 作業(yè)調度的功能與時機,（）按照某種調度算法（即調度策略），根據系統(tǒng)資源的當前使用情況和后備作業(yè)對資源的需求，挑選一個或多個后備作業(yè)投入運行； （）為選中的作業(yè)分配基本的內存和設備資源，這通過調用內存分配程序和設備分配程序來完成； （）為選中的作業(yè)建立進程，將進程實體裝入內存，這通過調用建立進程原語來實現。,一般來說，在下列情況下將啟動作業(yè)調度： （）設為系統(tǒng)支持的在主機上運行的最大作業(yè)數（也稱道數），為在主機上運行的當前作業(yè)數。如果，且存在后備作業(yè)，則啟動作業(yè)調度； （）當

4、一作業(yè)運行終止而被撤銷后，如果存在后備作業(yè)，則立即啟動作業(yè)調度崐； （）在分時系統(tǒng)中，當一用戶在某終端上通過交互會話被核準其注冊的登錄作業(yè)名及其口令后，立即啟動作業(yè)調度。,. 進程調度的功能與時機,啟動進程調度的時機可歸結為： （）現行進程執(zhí)行完它的當前時值時，這包括現行進程執(zhí)行完畢而終止或現行進程因等待某個事件而自行阻塞，此時需要將分配給一個新的就緒進程； （）在采用剝奪調度方式的系統(tǒng)中，當發(fā)生了某種剝奪事件，例如，當發(fā)生了時間片中斷或有比現行進程具有更高優(yōu)先級的進程進入了就緒隊列時，此時系統(tǒng)要回收現行進程占用的并進行重新調度。,. 調度方式,一進程在上的一次連續(xù)執(zhí)行過程稱為該進程的一個周期

5、。一個周期由進程自我終止。當進程需等待某個事件而進入等待態(tài)時，便終止了它的當前周期。待等待事件發(fā)生后，進程將開始下一個周期。進程執(zhí)行完畢進入停止狀態(tài)則終止了它的最后一個周期。一個進程在其并發(fā)運行過程中通常有若干個離散的且長短不等的周期。例如，一進程需要在上執(zhí)行的總時間為 ，在 、 、 的執(zhí)行點處它分別要等待三個事件而暫停執(zhí)行，即該進程有四個分別為 、 、 以及 的周期時值。當現行進程執(zhí)行完它的一個周期時，系統(tǒng)應及時把轉交給另一個進程去執(zhí)行它的周期，這是導致進程調度的基本原因，也是實現多部件并行和多進程并發(fā)的基本要求。,進程調度方式包括剝奪式與非剝奪式。在剝奪方式下，當現行進程正在執(zhí)行它的一個周

6、期期間，系統(tǒng)有權強行分割該進程的當前時值，即強行剝奪現行進程正占用的，并把分配給另一進程，換言之，如果一個進程的一個周期可能被分割成兩個或更多個周期，則系統(tǒng)采用的是剝奪式調度。反之，在非剝奪方式下，一個進程一旦獲得便一直執(zhí)行下去，直到完成它的當前周期，系統(tǒng)才重新調度，換言之，系統(tǒng)無權分割進程的任一周期。, 調度原則與評估標準,一般需綜合考慮以下四個基本調度原則： （）盡量提高系統(tǒng)的吞吐量，系統(tǒng)吞吐量是指在單位時間內完成的平均作業(yè)數； （）均衡利用資源，使與外設盡量都保持“忙”狀態(tài)； （）對所有的作業(yè)都應公平，任何一個作業(yè)的完成都不能被無限延遲； （）如果支持優(yōu)先級，應對優(yōu)先級高的作業(yè)或進程給予

7、優(yōu)先服務。,下面是幾項主要的評估標準： （） 平均周轉時間 作業(yè)從提交時刻is到完成時刻ic所經歷的時間稱為該作業(yè)的周轉時間，即icis；進程從進入就緒隊列的時刻ir到執(zhí)行完本次周期的時刻ic稱為該進程的周轉時間i，即iicir。于是，個作業(yè)的平均周轉時間或個進程的平均周轉時間為：,（） 平均帶權周轉時間 作業(yè)的周轉時間Ti與其實際運行時間i之比 稱為該作業(yè)的帶權周轉時間，即 ，同樣，進程的周轉時間與其本次周期的時值之比 稱為該進程的帶權周轉時間。于是，個作業(yè)或個進程的平均帶權周轉時間為：,（）平均等待時間 進程從進入就緒隊列那一時刻ir到獲得的那一時刻ip所經歷的時間稱為它的等待時間i，即i

8、ipir，那么個進程的平均等待時間為：,通常，用來衡量不同調度算法對同一作業(yè)流或同一進程集的調度性能，用來衡量不同進程調度算法對同一進程集的調度性能，而用來衡量同一調度算法對不同作業(yè)流或不同進程集的調度性能。, 調 度 算 法,. 先來先服務,假定有四個作業(yè)，它們的進入、估計運行和完成時間以 及平均周轉時間和平均帶權周轉時間如表-所示。,考慮三個進程、和，它們的本次周期的時值分別為 、 和 ，且以、的次序處于就緒隊列中，不妨認為它們進入就緒隊列的相對時刻均為。于是，在調度下，其執(zhí)行過程可表示如下：,0,21,27,30,、和的等待時間分別為、和，周轉時間分別為、和，故它們的平均等待時間和平均周

9、轉時間分別為：,算法本質上是非剝奪式的，如果可剝奪，則不能保證原則的實施。例如，對上述三個進程，若按時間片進行剝奪式調度，且規(guī)定時間片，則執(zhí)行過程可表示如下：,0,21,27,30,6,12,15,. 最短者優(yōu)先,. 最高響應比者優(yōu)先,HRN（Highest-Response-ratio-next)）算法是為了克服算法和算法的缺點而提出的，是這兩種算法的一種折衷。 一個作業(yè)或進程的響應比定義為： 響應時間需運行時間 （已等待時間需運行時間）需運行時間 已等待時間需運行時間,調度程序開始調度時，首先計算各個后備作業(yè)或各個就緒進程的響應比 ，然后選擇值最大的作業(yè)或進程。響應比既是需運行時間的函數，

10、也是等待時間的函數。由于與需運行時間成反比，故短作業(yè)或短進程可獲得較 高的響應比；另一方面，因與等待時間成正比，故長作業(yè)或長進程隨著其等待時間的增長，也可獲得較高的響應比。這就是說，算法既優(yōu)待了短作業(yè)或短進程，又照顧了先來者。,. 輪轉法,（ ）算法是一種剝奪式的進程調度算法，它依據公平服務的原則，將時間劃分成一個個的時間片（記為S），并以為單位，輪轉地為各個就緒進程一次分配一個時間片。,以前述的三個進程為例，考察算法的執(zhí)行情況及其調度性能。設 ，則有：,0,4,8,11,15,17,21,25,29,30,進程首先執(zhí)行一個時間片并被剝奪，其周期所剩余的 放到以后執(zhí)行；執(zhí)行一個時間片后也被剝奪

11、；的時值為 ，不足一個時間片。第二輪開始，又由先執(zhí)行一個時間片后被剝奪； 這次只執(zhí)行 。至此，和的周期已先后完成，故隨后連續(xù)個時間片都分給了，直至完成，在最后一個時間片里，只執(zhí)行了 。容易算出，該例的平均等待時間和平均周轉時間分別為：,其中，為系統(tǒng)的響應時間上限，為系統(tǒng)中的進程數目上限。例如，設 ，則0.1 。, . 最高優(yōu)先級法,優(yōu)先級通常是用一個整型數來表示，稱為優(yōu)先數。對于不同的系統(tǒng)，既可以用較大的數也可以用較小的數來表示較高的優(yōu)先級，這并無統(tǒng)一的規(guī)定。例如，中的優(yōu)先數的取值范圍為，且規(guī)定優(yōu)先數愈小其表示的優(yōu)先級愈高。 優(yōu)先級的設置分為靜態(tài)和動態(tài)兩種方式： （）靜態(tài)設置方式 （）動態(tài)設置

12、方式,設有五個就緒進程，它們各自的本次周期的長度、初始優(yōu)先數及進入就緒隊列的相對時刻如下所示：,在非剝奪的靜態(tài)設置方式下，執(zhí)行情況如下：,0,4,36,52,60,62,在進程執(zhí)行完時，已進入就緒隊列，因其優(yōu)先級較高，故先于和之前執(zhí)行?？伤愕眠@些進程的平均等待時間、平均周轉時間以 及平均帶權周轉時間分別為：,. 多級反饋隊列,多級反饋隊列就是綜合了、和的 一種進程調度算法，其基本思想如下： （）系統(tǒng)按優(yōu)先級別設置個就緒進程隊列，第一級隊列的優(yōu)先級最高，以下逐級降低，第級隊列的優(yōu)先級最低； （）每個就緒隊列對應有一個時間片Si（i，2, ，n），且有，一般有2Si； （）除對第級隊列按調度外，對其余各級隊列均按調度；,（）系統(tǒng)每次總是調度級別較高的隊列中的進程，僅當該隊列為空時，才去 調度下一級隊列中的進程； （）當現行進程正在執(zhí)行它的周期時，如果發(fā)生了時間片中斷或有進 程進入更高級的就緒隊列時將引起剝奪，對前一種情況，現行進程將進入下一 級隊列，對后一種情況，現行進程則進入本級隊列末尾。當一進程被喚醒時，它進入的是原先離開的那個隊列，即與其當前優(yōu)先級