第7課作業調度算法

操作系統第7課作業調度算法內容回顧：進程和線程間的幾點不同地址空間：不同進程的地址空間相互獨立，進程各線程共享一個地址空間。通信關系：不同進程間使用系統提供的進程通信機制；同一進程各線程直接通過訪問共享的進程地址空間來實現。調度切換：不同進程間切換要花很大開銷，同一進程的線程切換開銷很少。PCB數據程序用戶棧系統棧寄存器單線程進程模型進程PCB數據程序用戶棧系統棧寄存器TCB用戶棧系統棧寄存器TCB用戶棧系統棧寄存器TCB線程1線程2線程3進程多線程進程模型(a)(b)內容回顧：用戶與操作系統的程序接口操作系統管理了計算機的軟硬件資源，當用戶要使用這些資源時必須通過操作系統來實現，操作系統通過系統調用命令來響應用戶的請求，這就是操作系統提供的程序接口。操作系統預先編寫了很多不同功能的子程序，這子程序完成相應資源的具體管理，用戶在自己的程序里通過調用這些子程序來得到系統提供的相應功能服務。這些子程序就是“系統功能調用程序”，簡稱“系統調用”。特權指令與非特權指令把CPU的指令分為兩類：一類是操作系統和用戶都能使用的指令，稱為“非特權指令”；一類是只能由操作系統使用的指令，稱為“特權指令”。管態與目態計算機可以執行這些“特權指令”的狀態，我們稱之為“管態”。管態下可以執行包括特權指令在內任何指令。當系統處于只能執行用戶自己程序而不能執行特權指令的狀態時，我們稱之為“目態”。CUP處于“管態”還是“目態”由硬件系統自動識別。內容回顧內容回顧訪管指令用戶程序在執行的過程中，通過系統提供的訪管指令由“目態”轉為“管態”，從而實現特殊指令的執行，而達到實現系統調用的目的。訪管指令是一條非特權指令，功能是執行它就會產生一個軟中斷，促使中央處理機由目態轉為管態，進入操作系統。內容回顧：作業作業：指用戶要求計算機系統做的一個計算問題或一次事務處理的完整過程。從作業提交給系統，到作業運行完畢被撤消，是一個作業的生命期。在這期間，作業隨著自己的推進及環境變化，狀態也在不斷變化。內容回顧：作業的生命期作業的四個基本狀態后備作業內容回顧：作業調度按某種規則從后備作業隊列里挑選作業進入內存，參與對處理機的競爭，稱為作業調度，它由作業調度程序完成。所采用的規則，稱作業調度算法。處理機調度高級調度（作業調度）低級調度（進程調度）今日內容選擇作業調度算法要考慮的要素作業調度原則衡量作業調度算法優劣的指標調度算法的詳細講解先來先服務作業調度算法短作業優先作業調度算法響應比高者優先作業調度算法選擇作業調度算法要考慮的要素設計目標作業調度算法要與系統的整體設計目標一致，如批處理系統應考慮的是提高計算機效率和增加系統的吞吐能力；分時系統應考慮的是對用戶的請求響應時間；實時系統應考慮信息的準確性以及保證及時響應。選擇作業調度算法要考慮的要素

資源利用率均衡的資源利用率是評價系統性能優劣的重要指標。在選擇作業調度算法時，在考慮系統設計目標的前提下，應最大限度地發揮各種資源的效能，注意考慮系統資源的均衡使用，使“I/O繁忙”的作業與“CPU繁忙”的作業搭配調度，例如將科學計算型（CPU型）作業和數據處理型（輸入輸出型）作業搭配運行就是一種方法。選擇作業調度算法要考慮的要素作業的周轉時間設法縮短作業的周轉時間以應保證提交的作業在規定的截止時間內完成，提高衡量調度性能的指標大多數操作系統都采用折中方案，盡量選擇算法比較簡單的調度算法。作業調度原則盡可能使后備作業隊列中每個作業都得到公平對待，避免一個作業無限期地延遲得不到執行。使進入內存中的作業均衡地使用系統各種資源，避免出現有的資源空閑，有的資源被爭搶的局面。盡可能提高吞吐能力，在單位時間內為多個作業提供服務。

衡量作業調度算法優劣的指標CPU利用率好的算法應盡可能地提高CPU利用率。CPU利用率=CPU有效工作時間/CPU總的運行時間吞吐量指單位時間內平均完成的作業數量。吞吐量=完成的作業道數/完成的時間作業周轉時間作業周轉時間是指一個作業從提交到完成總共花費的時間作業周轉時間=作業完成時間-作業提交時間作業周轉時間=作業運行時間+作業等待時間對于一批n個作業而言，它們的“平均周轉時間”T應該是：

T=(T1+T2+…+Tn)/n先來先服務作業調度算法以作業進入后備隊列中的先后次序作業選擇作業的依據。也就是說哪個作業在后備隊列中等待的時間最長，它就是下次調度選中者。但前提是這個作業的資源需求要得到滿足，否則就要被推遲選中例：有3個作業，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統，采用先來先服務的作業調度算法。求每個作業的周轉時間及它們的平均周轉時間。作業所需CPU時間1232433例：有3個作業，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統，采用先來先服務的作業調度算法。求每個作業的周轉時間及它們的平均周轉時間。作業所需CPU時間1232433提交時間開始時間完成時間周轉時間例：有3個作業，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統，采用先來先服務的作業調度算法。求每個作業的周轉時間及它們的平均周轉時間。作業所需CPU時間1232433提交時間開始時間000完成時間周轉時間例：有3個作業，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統，采用先來先服務的作業調度算法。求每個作業的周轉時間及它們的平均周轉時間。作業所需CPU時間1232433提交時間開始時間0000完成時間周轉時間24例：有3個作業，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統，采用先來先服務的作業調度算法。求每個作業的周轉時間及它們的平均周轉時間。作業所需CPU時間1232433提交時間開始時間00002427完成時間周轉時間242730例：有3個作業，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統，采用先來先服務的作業調度算法。求每個作業的周轉時間及它們的平均周轉時間。作業所需CPU時間1232433提交時間開始時間00002427完成時間周轉時間242730242730例：有3個作業，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統，采用先來先服務的作業調度算法。求每個作業的周轉時間及它們的平均周轉時間。作業所需CPU時間1232433開始時間024完成時間周轉時間24273024273024這三個作業的平均周轉時間為：

T=(T1+T2+T3)/3=(24+27+30)/3=81/3=27例：有五個作業如下表所示，采用先來先服務調度算法算出每個作業的周轉時間作業到達時間所需CPU時間18：00628：02238：03748：05358：064例：有五個作業如下表所示，采用先來先服務調度算法算出每個作業的周轉時間作業到達時間所需CPU時間開始時間完成時間周轉時間18：00628：02238：03748：05358：064例：有五個作業如下表所示，采用先來先服務調度算法算出每個作業的周轉時間作業到達時間所需CPU時間開始時間完成時間周轉時間18：0068：008：0628：02238：03748：05358：064例：有五個作業如下表所示，采用先來先服務調度算法算出每個作業的周轉時間作業到達時間所需CPU時間開始時間完成時間周轉時間18：0068：008：0628：0228：068：0838：0378：088：1548：0538：158：1858：0648：188：22例：有五個作業如下表所示，采用先來先服務調度算法算出每個作業的周轉時間作業到達時間所需CPU時間開始時間完成時間周轉時間18：0068：008：06628：0228：068：08638：0378：088：151248：0538：158：181358：0648：188：2216這五個作業的平均周轉時間為：（6+6+12+13+16）/5=10.6。短作業優先作業調度算法基本思想：要求每個用戶對自己作業所需CPU時間做出估計，填入作業說明書。作業調度程序工作時，是從后備作業隊列里挑需CPU時間最少、且資源能得到滿足的作業進入內存投入運行。例：有3個作業，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統，采用短作業優先的作業調度算法。求每個作業的周轉時間及它們的平均周轉時間。作業所需CPU時間1232433例：有3個作業，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統，采用短作業優先的作業調度算法。求每個作業的周轉時間及它們的平均周轉時間。作業所需CPU時間1232433提交時間開始時間000完成時間周轉時間作業所需CPU時間1232433完成時間周轉時間例：有3個作業，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統，采用短作業優先的作業調度算法。求每個作業的周轉時間及它們的平均周轉時間。作業所需CPU時間1232433提交時間開始時間0000完成時間周轉時間33作業所需CPU時間1232433完成時間周轉時間例：有3個作業，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統，采用短作業優先的作業調度算法。求每個作業的周轉時間及它們的平均周轉時間。作業所需CPU時間1232433提交時間開始時間00003完成時間周轉時間3636作業所需CPU時間1232433完成時間周轉時間例：有3個作業，所需CPU時間如下表所示。按1、2、3的順序，同時提交給系統，采用短作業優先的作業調度算法。求每個作業的周轉時間及它們的平均周轉時間。作業所需CPU時間1232433提交時間開始時間000603完成時間周轉時間30363036作業所需CPU時間1232433完成時間周轉時間這三個作業的平均周轉時間為：

T=(T1+T2+T3)/3=(30+3+6)/3=13例：有五個作業如下表所示，采用短作業優先調度算法算出每個作業的周轉時間作業到達時間所需CPU時間開始時間完成時間周轉時間18：00628：02238：03748：05358：064例：有五個作業如下表所示，采用短作業優先調度算法算出每個作業的周轉時間作業到達時間所需CPU時間開始時間完成時間周轉時間18：0068：008：0628：02238：03748：05358：064例：有五個作業如下表所示，采用短作業優先調度算法算出每個作業的周轉時間作業到達時間所需CPU時間開始時間完成時間周轉時間18：0068：008：0628：0228：068：0838：03748：05358：064例：有五個作業如下表所示，采用短作業優先調度算法算出每個作業的周轉時間作業到達時間所需CPU時間開始時間完成時間周轉時間18：0068：008：0628：0228：068：0838：0378：158：2248：0538：088：1158：0648：118：15例：有五個作業如下表所示，采用短作業優先調度算法算出每個作業的周轉時間作業到達時間所需CPU時間開始時間完成時間周轉時間18：0068：008：06628：0228：068：08638：0378：158：221948：0538：088：11658：0648：118：159這五個作業的平均周轉時間為：（6+6+19+6+9）/5=9.2。響應比高者優先作業調度算法基本思想：在進行作業調度時，先計算每個作業當時的響應比：響應比=(已等待時間)/(所需CPU時間)

然后從中挑選出響應比最高的作業作為調度的對象。作業到達時間所需時間A8：005B8：023C8：031D8：042例：有四個作業如下表所示，采用響應比高者優先調度算法算出作業的周轉時間在剛開始時，只有作業A，因此先運行作業A。當A于8：05運行完成時，其它三個作業B、C、D都已到達，按響應比高者優先算法要求，現在要計算這三個作業的響應比。此時在8:05時狀態如下表所示：作業到達時間所需時間等待時間響應比B8：023C8：031D8：042此時在8:05時狀態如下表所示：作業到達時間所需時間等待時間響應比B8：0233C8：0312D8：0421此時在8:05時狀態如下表所示：作業到達時間所需時間等待時間響應比B8：02331C8：03122D