1、2022年5月24日星期二12時49分17秒計算機操作系統3.1 3.1 3.1 3.1 3.1 3.1 3.2 3.2 3.2 3.2 3.2 3.2 3.3 3.3 3.3 3.3 3.3 3.3 3.4 3.4 3.4 3.4 3.4 3.4 3.5 3.5 3.5 3.5 3.5 3.5 3.63.63.63.63.63.6 2022年5月24日星期二12時49分18秒計算機操作系統3.1.1 調度的意義調度的意義調度策略有兩個最根本的目標：調度策略有兩個最根本的目標： 1、合理性合理性：在多道作業在多道作業(進程進程)并發時，使各道作并發時，使各道作業合理地分配到處理機份額。業合理地

2、分配到處理機份額。 2、有效性：有效性： 使處理機和使處理機和I/O設備得到合理有效的設備得到合理有效的分配，從而使系統資源得到充分的利用。分配，從而使系統資源得到充分的利用。 2022年5月24日星期二12時49分18秒計算機操作系統3.1.2 調度模式調度模式調度一般分為三級：調度一般分為三級： 1、高級調度高級調度又稱為作業調度。其主要功能是按照又稱為作業調度。其主要功能是按照某種原則從批作業隊列或交互作業中選取某種原則從批作業隊列或交互作業中選取某一作業進入主存，并為作業做好運行前某一作業進入主存，并為作業做好運行前的準備工作和作業完成后的后期處理。的準備工作和作業完成后的后期處理。

3、2022年5月24日星期二12時49分18秒計算機操作系統3.1.2 調度模式調度模式2、低級調度低級調度又稱為處理器調度，其主要功能是按又稱為處理器調度，其主要功能是按照調度策略將處理器分配給就緒進程或線照調度策略將處理器分配給就緒進程或線程。完成此功能的程序稱之為程。完成此功能的程序稱之為“進程（或進程（或線程）調度程序線程）調度程序”，是操作系統內核的主，是操作系統內核的主要部分。要部分。 2022年5月24日星期二12時49分18秒計算機操作系統3.1.2 調度模式調度模式3、中級調度中級調度又稱中程調度，對換調度。為提高內又稱中程調度，對換調度。為提高內存的利用率和系統的呑吐量，中級

4、調度決存的利用率和系統的呑吐量，中級調度決定哪些進程被允許參與競爭處理器資源，定哪些進程被允許參與競爭處理器資源，哪些進程調至外存上去等待，在合適的情哪些進程調至外存上去等待，在合適的情況下，再重新調入內存，并將其掛在就緒況下，再重新調入內存，并將其掛在就緒隊列上，以恢復對處理器資源的競爭。隊列上，以恢復對處理器資源的競爭。 2022年5月24日星期二12時49分18秒計算機操作系統3.1.2 調度模式調度模式2022年5月24日星期二12時49分18秒計算機操作系統3.1.3 選擇調度策略的依據選擇調度策略的依據 選擇調度策略時一般要考慮到以下幾方面選擇調度策略時一般要考慮到以下幾方面的問題

5、：的問題： 1、系統設計目標系統設計目標 是決定調度策略的主要依據。批處理是決定調度策略的主要依據。批處理系統以效率為目的；實時系統保證不要丟系統以效率為目的；實時系統保證不要丟失并及時處理實時信息；而分時系統確保失并及時處理實時信息；而分時系統確保用戶的請求能夠及時予以響應。用戶的請求能夠及時予以響應。 2022年5月24日星期二12時49分18秒計算機操作系統3.1.3 選擇調度策略的依據選擇調度策略的依據 2 2、資源利用率、資源利用率選擇調度策略時，應該考慮在實現設選擇調度策略時，應該考慮在實現設計目標的前提下，盡可能地發揮各種資源計目標的前提下，盡可能地發揮各種資源的效能。的效能。2

6、022年5月24日星期二12時49分18秒計算機操作系統3.1.3 選擇調度策略的依據選擇調度策略的依據 3 3、均衡系統與用戶的要求、均衡系統與用戶的要求 系統的性能與用戶要求在有些時候是系統的性能與用戶要求在有些時候是沖突的，系統必須均衡并協調兩者之間的沖突的，系統必須均衡并協調兩者之間的關系。關系。2022年5月24日星期二12時49分18秒計算機操作系統3.1.4 作業與進程的關系作業與進程的關系 1 1、什么是作業？、什么是作業？作業是用戶一次提交給計算機系統的作業是用戶一次提交給計算機系統的一件具有獨立性的工作，是在這一次上機一件具有獨立性的工作，是在這一次上機活動中要求計算機系統

7、所做的一系列工作活動中要求計算機系統所做的一系列工作的集合，由三部分組成：源程序（或程的集合，由三部分組成：源程序（或程序）、數據、及加工步驟。序）、數據、及加工步驟。 2022年5月24日星期二12時49分18秒計算機操作系統3.1.4 作業與進程的關系作業與進程的關系 2 2、作業有四個狀態、作業有四個狀態 從用戶提交給到完成后離開系統，作從用戶提交給到完成后離開系統，作業的整個活動過程常被劃分為四個階段，業的整個活動過程常被劃分為四個階段，通常稱之為四種狀態：提交狀態、就緒狀通常稱之為四種狀態：提交狀態、就緒狀態、運行狀態和完成狀態。態、運行狀態和完成狀態。2022年5月24日星期二12

8、時49分18秒計算機操作系統3.1.4 作業與進程的關系作業與進程的關系 3 3、作業的四個狀態、作業的四個狀態 a提交狀態：當用戶將作業提交給機房提交狀態：當用戶將作業提交給機房或通過終端將其鍵入計算機，作業進入提或通過終端將其鍵入計算機，作業進入提交狀態。交狀態。b就緒狀態：通過輸入設備的輸入，操就緒狀態：通過輸入設備的輸入，操作系統將其存放到磁盤，作業進入就緒狀作系統將其存放到磁盤，作業進入就緒狀態，等待運行。態，等待運行。2022年5月24日星期二12時49分18秒計算機操作系統3.1.4 作業與進程的關系作業與進程的關系 c運行狀態：在調度規則的統一調度下，運行狀態：在調度規則的統一

9、調度下，某個作業調度進主存并為之建立了進程，某個作業調度進主存并為之建立了進程，投入了運行，作業便進入了運行狀態。投入了運行，作業便進入了運行狀態。d完成狀態：當作業全部運行完畢后，完成狀態：當作業全部運行完畢后，作業調度程序為其完成后期處理，作業進作業調度程序為其完成后期處理，作業進入完成狀態。入完成狀態。 2022年5月24日星期二12時49分18秒計算機操作系統3.1.4 作業與進程的關系作業與進程的關系 4 4、作業和進程、作業和進程 每一個作業將動態地轉換成了一組運每一個作業將動態地轉換成了一組運行實體行實體進程組，并由此來完成該作業進程組，并由此來完成該作業所需要完成的一系列加工步

10、驟。所需要完成的一系列加工步驟。進程組由根進程或終端進程根據需要進程組由根進程或終端進程根據需要來創建。來創建。2022年5月24日星期二12時49分18秒計算機操作系統3.1.4 作業與進程的關系作業與進程的關系 5 5、根進程與終端進程、根進程與終端進程 根進程是批處理作業形式下，作業調根進程是批處理作業形式下，作業調度程序為每一道后備作業所創建的一個度程序為每一道后備作業所創建的一個“進程進程”，稱為該作業的，稱為該作業的“根進程根進程”，該，該“進程進程”完成這一項作業所需進程組的創完成這一項作業所需進程組的創建工作，并最終完成該作業。建工作，并最終完成該作業。 2022年5月24日星

11、期二12時49分18秒計算機操作系統3.1.4 作業與進程的關系作業與進程的關系 5 5、根進程與終端進程、根進程與終端進程在終端交互型作業下，當用戶接通終端在終端交互型作業下，當用戶接通終端設備時，系統便為之建立一個進程，稱之為設備時，系統便為之建立一個進程，稱之為終端進程。終端進程執行命令解釋程序，解終端進程。終端進程執行命令解釋程序，解釋執行用戶交互鍵入的每一條命令。對于每釋執行用戶交互鍵入的每一條命令。對于每一條終端命令可以創建一個子進程去具體執一條終端命令可以創建一個子進程去具體執行，來完成的作業的一系列加工步驟。行，來完成的作業的一系列加工步驟。2022年5月24日星期二12時49

12、分18秒計算機操作系統3.1.4 作業與進程的關系作業與進程的關系 因此，進程是作業的執行狀態，一因此，進程是作業的執行狀態，一個作業實際上是由一組相應的進程來完個作業實際上是由一組相應的進程來完成的，當作業所對應的進程完成時，作成的，當作業所對應的進程完成時，作業便進入了完成狀態，整個作業也就完業便進入了完成狀態，整個作業也就完成了。成了。 2022年5月24日星期二12時49分18秒計算機操作系統3.2.1 作業調度的功能作業調度的功能 作業調度只在批處理系統中存在。因為批處理系作業調度只在批處理系統中存在。因為批處理系統的作業進入系統后，是先駐留在外存上的，因此需統的作業進入系統后，是先

13、駐留在外存上的，因此需要有作業調度，將它們分批裝入內存。要有作業調度，將它們分批裝入內存。而在分時系統中，為了能及時響應，用戶通過鍵而在分時系統中，為了能及時響應，用戶通過鍵盤輸入的命令或數據等，都是直接送入內存，因而無盤輸入的命令或數據等，都是直接送入內存，因而無需配置作業調度。需配置作業調度。類似地，在實時系統中，通常也不需要作業調度。類似地，在實時系統中，通常也不需要作業調度。 2022年5月24日星期二12時49分18秒計算機操作系統3.2.1 作業調度的功能作業調度的功能 1 1、記錄系統中各作業的狀況、記錄系統中各作業的狀況系統使用作業控制表系統使用作業控制表( (JCB)JCB)

14、對作業實施對作業實施管理。當作業進入后備狀態時，系統為之管理。當作業進入后備狀態時，系統為之建立建立JCBJCB，并記錄每一個作業在各階段所要并記錄每一個作業在各階段所要求的和已分配的資源以及該作業的狀態，求的和已分配的資源以及該作業的狀態，作業調度程序據此對作業進行調度和管理。作業調度程序據此對作業進行調度和管理。 2022年5月24日星期二12時49分18秒計算機操作系統3.2.1 作業調度的功能作業調度的功能 2 2、為作業做好執行前的準備工作、為作業做好執行前的準備工作作業調度程序為作業建立相應的進程，作業調度程序為作業建立相應的進程，并為這些進程分配它們所需要的系統資源，并為這些進程

15、分配它們所需要的系統資源，如內存、外存、外設等。如內存、外存、外設等。 2022年5月24日星期二12時49分18秒計算機操作系統3.2.2 作業調度的依據作業調度的依據作業調度依據的原則有兩條：作業調度依據的原則有兩條： 1 1接納多少個作業接納多少個作業 接納多少個作業進入內存取決于多道接納多少個作業進入內存取決于多道程序度（程序度（Degree of MultiprogrammingDegree of Multiprogramming），），即允許有多少個作業同時在內存中運行。即允許有多少個作業同時在內存中運行。而多道程序度的確定應根據系統的規模和而多道程序度的確定應根據系統的規模和運行

16、速度等參數，做適當折衷。運行速度等參數，做適當折衷。 2022年5月24日星期二12時49分18秒計算機操作系統3.2.2 作業調度的依據作業調度的依據2 2接納哪些作業接納哪些作業應將哪些作業從外存調入內存，將取應將哪些作業從外存調入內存，將取決于所采用的調度算法。因為系統要求的決于所采用的調度算法。因為系統要求的差異，各個系統可能采取的調度算法也各差異，各個系統可能采取的調度算法也各有其特點。有其特點。2022年5月24日星期二12時49分18秒計算機操作系統3.2.3 作業調度算法基于兩個因素作業調度算法基于兩個因素1 1基于作業優先級基于作業優先級考慮用戶的方便性，通常根據作業的考慮用

17、戶的方便性，通常根據作業的某些屬性為作業規定一個調度參數某些屬性為作業規定一個調度參數優優先級先級( (或稱作業運行優先級或稱作業運行優先級) )，作業調度程，作業調度程序則根據優先級的高低決定它們的調度順序則根據優先級的高低決定它們的調度順序。序。 2022年5月24日星期二12時49分18秒計算機操作系統3.2.3 作業調度算法基于兩個因素作業調度算法基于兩個因素 2 2基于作業對資源需求量基于作業對資源需求量考慮資源的利用率，把對資源需求量考慮資源的利用率，把對資源需求量有著互補性的作業搭配在一起進行調度。有著互補性的作業搭配在一起進行調度。比如：將短作業和長作業搭配，將內存需比如：將短

18、作業和長作業搭配，將內存需求少的作業和內存需求大的作業搭配，求少的作業和內存需求大的作業搭配，I/OI/O型作業與型作業與CPUCPU型作業搭配，等等。型作業搭配，等等。 2022年5月24日星期二12時49分18秒計算機操作系統3.2.3 作業調度的作業調度的三種常用調度算法：三種常用調度算法： 1.1.先來先服務（先來先服務（FCFSFCFS）算法算法 2. 2.最短作業優先（最短作業優先（SJFSJF）算法算法 3. 3.響應比高者優先（響應比高者優先（HRNHRN）調度算法。調度算法。 2022年5月24日星期二12時49分18秒計算機操作系統進程調度是低級調度（進程調度是低級調度（L

19、ow Level Low Level SchedulingScheduling），），又稱之為短程調度又稱之為短程調度（Short-Term SchedulingShort-Term Scheduling），），它決定就緒它決定就緒隊列中的哪個進程將獲得處理機，然后由隊列中的哪個進程將獲得處理機，然后由分派程序（分派程序（DispatcherDispatcher）執行把處理機分執行把處理機分配給該進程的操作。配給該進程的操作。2022年5月24日星期二12時49分18秒計算機操作系統進程調度是最基本的一種調度，不管進程調度是最基本的一種調度，不管是批處理，還是分時或實時操作系統中，是批處理，還

20、是分時或實時操作系統中，都必須配置這級調度。都必須配置這級調度。進程調度的頻率很高，在分時系統中，進程調度的頻率很高，在分時系統中，通常是幾十毫秒就要運行一次。通常是幾十毫秒就要運行一次。2022年5月24日星期二12時49分18秒計算機操作系統3.3.1 3.3.1 進程調度發生的條件進程調度發生的條件通常有以下幾種可能的情況：通常有以下幾種可能的情況：進程完成；進程完成；分配給進程的時間片用完；分配給進程的時間片用完；進程自身的原因如請求進程自身的原因如請求I/OI/O服務，暫時放棄服務，暫時放棄CPUCPU；在搶占式調度中，新建進程的優先級比運行進在搶占式調度中，新建進程的優先級比運行進

21、程的優先級；程的優先級；某些原語操作。某些原語操作。2022年5月24日星期二12時49分18秒計算機操作系統3.3.2 3.3.2 進程調度的功能進程調度的功能 進程調度完成以下幾方面的功能進程調度完成以下幾方面的功能 ： 記錄進程的相關信息記錄進程的相關信息進程的相關信息由進程的相關信息由PCBPCB表記錄。表記錄。 選擇進程以分配處理機選擇進程以分配處理機選擇依據調度策略來進行。選擇依據調度策略來進行。進行進程的上下文切換進行進程的上下文切換系統要經過進程上下文切換，才能使另一個進程系統要經過進程上下文切換，才能使另一個進程得以執行。得以執行。2022年5月24日星期二12時49分18秒

22、計算機操作系統3.3.3 3.3.3 進程上下文切換進程上下文切換 一個進程的執行是在進程的上下文中進行。當一個進程的執行是在進程的上下文中進行。當正在執行的進程由于種原因要讓出處理機時，系統正在執行的進程由于種原因要讓出處理機時，系統要做進程上下文切換，以使另一個進程得以執行。要做進程上下文切換，以使另一個進程得以執行。切換時，包括進程的狀態、有關變量和數據結切換時，包括進程的狀態、有關變量和數據結構的值、機器寄存器的值和構的值、機器寄存器的值和PCBPCB以及有關程序、數以及有關程序、數據等的上下文需要切換。據等的上下文需要切換。2022年5月24日星期二12時49分19秒計算機操作系統3

23、.3.3 3.3.3 進程上下文切換進程上下文切換 切換包括下以四個步驟：切換包括下以四個步驟：決定是否做上下文切換以及判斷是否允許做上下決定是否做上下文切換以及判斷是否允許做上下文切換。文切換。保存當前正在執行的進程的上下文。保存當前正在執行的進程的上下文。按照進程調度策略選擇適當的就緒進程。按照進程調度策略選擇適當的就緒進程。裝配所選進程的上下文，將處理機的控制權交給裝配所選進程的上下文，將處理機的控制權交給新選進程。新選進程。 2022年5月24日星期二12時49分19秒計算機操作系統3.3.4 進程調度有兩種基本方式進程調度有兩種基本方式方式：非搶占方式（方式：非搶占方式（Non-Pr

24、eemptive ModeNon-Preemptive Mode）也稱非剝奪調度。這是一種較為簡單的調度方也稱非剝奪調度。這是一種較為簡單的調度方式。在該調度方式下，當進程分配到處理機時，其式。在該調度方式下，當進程分配到處理機時，其他進程不可以搶占，只有在進程自動放棄處理機時，他進程不可以搶占，只有在進程自動放棄處理機時，才進行調度。才進行調度。2022年5月24日星期二12時49分19秒計算機操作系統3.3.4 進程調度有兩種基本方式進程調度有兩種基本方式方式：非搶占方式（方式：非搶占方式（Non-Preemptive Mode）優點：系統開銷??；采用非搶占方式時，程序優點：系統開銷?。徊?/p>

25、用非搶占方式時，程序員可以在某種程度上預知進程的運行軌跡，程序設員可以在某種程度上預知進程的運行軌跡，程序設計相應簡化。計相應簡化。缺點：損失了系統的并發性，使系統不能根據內缺點：損失了系統的并發性，使系統不能根據內部的并發事件及時實施進程調度，難以實現要求比部的并發事件及時實施進程調度，難以實現要求比較嚴格的實時調度要求。較嚴格的實時調度要求。2022年5月24日星期二12時49分19秒計算機操作系統3.3.4 進程調度有兩種基本方式進程調度有兩種基本方式方式方式：搶占方式（搶占方式（Preemptive Mode）也稱剝奪調度。這種調度方式，允許調度程序也稱剝奪調度。這種調度方式，允許調度

26、程序根據一定的原則，去停止某個正在執行的進程，將根據一定的原則，去停止某個正在執行的進程，將已分配給該進程的處理機，重新分配給另一進程。已分配給該進程的處理機，重新分配給另一進程。 2022年5月24日星期二12時49分19秒計算機操作系統3.3.4 進程調度有兩種基本方式進程調度有兩種基本方式方式方式：搶占的原則有三種：搶占的原則有三種：a.時間片原則：各進程按時間片運行，當一個時間片原則：各進程按時間片運行，當一個時間片用完后，便停止該進程的執行，重新調度。時間片用完后，便停止該進程的執行，重新調度。b.優先權原則：通常是對一些重要的和緊急的優先權原則：通常是對一些重要的和緊急的作業賦予較

27、高的優先權，系統將處理機分配給優先作業賦予較高的優先權，系統將處理機分配給優先權高的進程，使之執行。權高的進程，使之執行。c.短進程優先原則：當新到達的進程比正在執短進程優先原則：當新到達的進程比正在執行的進程明顯地短時，將剝奪長進程的執行，將處行的進程明顯地短時，將剝奪長進程的執行，將處理機分配給短進程，使之優先執行。理機分配給短進程，使之優先執行。 2022年5月24日星期二12時49分19秒計算機操作系統3.3.4 進程調度有兩種基本方式進程調度有兩種基本方式方式方式：搶占方式（搶占方式（Preemptive Mode）相對于非搶占調度方式而言，搶占方式的控制比較相對于非搶占調度方式而言

28、，搶占方式的控制比較復雜，但在該方式下，系統并發性強，能夠滿足系復雜，但在該方式下，系統并發性強，能夠滿足系統的多種要求，因此適應面很廣。統的多種要求，因此適應面很廣。2022年5月24日星期二12時49分19秒計算機操作系統3.3.5 進程調度算法進程調度算法針對系統的不同需求，應用上述兩種基本調度方式，針對系統的不同需求，應用上述兩種基本調度方式，常用的進程調度算法有如下常用的進程調度算法有如下6種：種： 1. 先來先服務算法；先來先服務算法； 2. 短進程優先算法；短進程優先算法； 3. 時間片輪轉算法；時間片輪轉算法； 4. 優先權調度算法；優先權調度算法； 5. 多隊列調度算法；多隊

29、列調度算法； 6. 多級反饋隊列調度算法。多級反饋隊列調度算法。 2022年5月24日星期二12時49分19秒計算機操作系統3.4.1 先來先服務調度算法先來先服務調度算法先來先服務調度算法從就緒隊列中，選擇一個先來先服務調度算法從就緒隊列中，選擇一個最先進入該隊列的進程，把處理機分配給它，使之最先進入該隊列的進程，把處理機分配給它，使之投入運行。投入運行。該調度方式屬于非搶占方式，獲得處理機的進該調度方式屬于非搶占方式，獲得處理機的進程將一直運行，直到該進程完成或因進程本身發生程將一直運行，直到該進程完成或因進程本身發生某事件而阻塞后，才放棄處理機。某事件而阻塞后，才放棄處理機。該算法能公平

30、地使每個作業該算法能公平地使每個作業(進程進程)獲得處理機。獲得處理機。 2022年5月24日星期二12時49分19秒計算機操作系統3.4.2 短作業短作業(進程進程)優先調度算法優先調度算法短作業優先調度算法短作業優先調度算法(SJF)是指對短作業優先是指對短作業優先調度，即從后備隊列中選擇一個或若干個估計運行調度，即從后備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存。時間最短的作業，將它們調入內存。短進程優先調度算法短進程優先調度算法(SPF)，是指對短進程優是指對短進程優先調度，即從就緒隊列中選擇一個或若干個估計運先調度，即從就緒隊列中選擇一個或若干個估計運行時間最短的進

31、程，這它們分配處理機，使之投入行時間最短的進程，這它們分配處理機，使之投入運行。運行。該算法是一個非搶占方式的算法該算法是一個非搶占方式的算法. 2022年5月24日星期二12時49分19秒計算機操作系統3.4.3 時間片輪轉調度算法時間片輪轉調度算法時間片輪轉法的基本原理是將處理機時間劃分時間片輪轉法的基本原理是將處理機時間劃分成若干的時間片，以時間片為單位，進程依次輪流成若干的時間片，以時間片為單位，進程依次輪流(即按先來先服務的原則即按先來先服務的原則)使用處理機一個時間片。使用處理機一個時間片。算法多用于進程調度，以提高進程的并發性，算法多用于進程調度，以提高進程的并發性，縮短每一個進

32、程的響應時間，從而提高系統的資源縮短每一個進程的響應時間，從而提高系統的資源利用率。利用率。 2022年5月24日星期二12時49分19秒計算機操作系統3.4.3 時間片輪轉調度算法時間片輪轉調度算法時間片的大小是該算法中的一個重要因素。應時間片的大小是該算法中的一個重要因素。應綜合考慮以下幾個因素來確定：綜合考慮以下幾個因素來確定：系統對響應時間的要求。系統對響應時間的要求。就緒隊列中進程的數目。就緒隊列中進程的數目。系統的處理能力系統的處理能力 2022年5月24日星期二12時49分19秒計算機操作系統3.4.4 優先權調度算法優先權調度算法優先權調度算法的基本原理優先權調度算法的基本原理

33、使用該算法前，系統將根據某些因素賦予每一個使用該算法前，系統將根據某些因素賦予每一個作業或進程一個對應的優先權，當用于作業調度時，作業或進程一個對應的優先權，當用于作業調度時，從后備隊列中選擇若干個優先權最高的作業調入內存；從后備隊列中選擇若干個優先權最高的作業調入內存；當用于進程調度時，則把處理機分配給就緒隊列中優當用于進程調度時，則把處理機分配給就緒隊列中優先權最高的進程。先權最高的進程。優先權在調度過程中所起的作用與系統對進程調優先權在調度過程中所起的作用與系統對進程調度采用非搶占式調度策略還是搶占式調度策略有關。度采用非搶占式調度策略還是搶占式調度策略有關。 2022年5月24日星期二

34、12時49分19秒計算機操作系統3.4.4 優先權調度算法優先權調度算法 優先權調度算法的基本原理優先權調度算法的基本原理在非搶占式優先權策略下，系統一旦把處理機在非搶占式優先權策略下，系統一旦把處理機分配某一高優先權的進程后，該進程對處理機的占分配某一高優先權的進程后，該進程對處理機的占有不會受新進程的高優先級的影響，該進程將一直有不會受新進程的高優先級的影響，該進程將一直執行下去，直到完成，或因發生某事件而進程自身執行下去，直到完成，或因發生某事件而進程自身阻塞，使該進程放棄處理機。而高優先級的新進程阻塞，使該進程放棄處理機。而高優先級的新進程只能等待正在運行的進程自動放棄處理機后，才能只

35、能等待正在運行的進程自動放棄處理機后，才能得到調度。得到調度。 2022年5月24日星期二12時49分19秒計算機操作系統3.4.4 優先權調度算法優先權調度算法 優先權調度算法的基本原理優先權調度算法的基本原理而在搶占式優先權調度策略下，系統同樣是把而在搶占式優先權調度策略下，系統同樣是把處理機分配給優先權最高的進程，使之執行。但一處理機分配給優先權最高的進程，使之執行。但一旦出現了另一個優先權更高的進程時，進程調度程旦出現了另一個優先權更高的進程時，進程調度程序就停止原最高優先權進程的執行序就停止原最高優先權進程的執行(而不會等待該而不會等待該進程自動放棄處理機進程自動放棄處理機)，而將處

36、理機分配給新出現，而將處理機分配給新出現的優先權最高的進程。的優先權最高的進程。2022年5月24日星期二12時49分19秒計算機操作系統3.4.4 優先權調度算法優先權調度算法優先權的類型優先權的類型優先權值是該調度算法的重要依據。優先權涉優先權值是該調度算法的重要依據。優先權涉及的因素比較多，優先權也依據這些因素分為兩大及的因素比較多，優先權也依據這些因素分為兩大類型：類型：a.a.靜態優先權：創建進程時確定的，與運行無關。靜態優先權：創建進程時確定的，與運行無關。b.b.動態優先權：動態優先權：創建進程時所賦予的優先權，可創建進程時所賦予的優先權，可以隨進程的推進而改變。以隨進程的推進而

37、改變。2022年5月24日星期二12時49分19秒計算機操作系統3.4.4 優先權調度算法優先權調度算法優先權的類型優先權的類型a.a.靜態優先權靜態優先權依賴于以下幾個方面：依賴于以下幾個方面：進程類型進程類型進程對資源的需求進程對資源的需求根據用戶要求根據用戶要求靜態優先權法簡單易行、系統開銷小，但不夠精靜態優先權法簡單易行、系統開銷小，但不夠精確，很有可能出現優先權低的作業確，很有可能出現優先權低的作業( (進程進程) )，得不到，得不到合適的調度的情況。合適的調度的情況。2022年5月24日星期二12時49分19秒計算機操作系統3.4.4 優先權調度算法優先權調度算法優先權的類型優先權

38、的類型b.b.動態優先權：動態優先權：除了包含靜態優先權所包含的內容外，還可以除了包含靜態優先權所包含的內容外，還可以根據根據系統的實際狀況合理地調整進程的調度。系統的實際狀況合理地調整進程的調度。如，為防止長作業長等待，我們可以規定，在就緒如，為防止長作業長等待，我們可以規定，在就緒隊列中的進程，隨其等待時間的增長，其優先權以隊列中的進程，隨其等待時間的增長，其優先權以速率速率增加；或為了防止一個長作業長期地壟斷處增加；或為了防止一個長作業長期地壟斷處理機，可以規定正在執行的進程，其優先權以速率理機，可以規定正在執行的進程，其優先權以速率下降，使其他作業有可能搶占處理機。下降，使其他作業有可

39、能搶占處理機。2022年5月24日星期二12時49分19秒計算機操作系統3.4.5 高響應比優先高響應比優先調度算法調度算法此算法的優先權定義如下：此算法的優先權定義如下：優先權優先權( (等待時間要求服務時間等待時間要求服務時間)/)/要求服務時間要求服務時間該優先權的分子是等待時間加上要求服務時間，該優先權的分子是等待時間加上要求服務時間，即是系統對該作業的響應時間，而響應時間與服務即是系統對該作業的響應時間，而響應時間與服務時間的比值稱之為響應比，故該優先權又相當于響時間的比值稱之為響應比，故該優先權又相當于響應比。應比。 2022年5月24日星期二12時49分19秒計算機操作系統3.4

40、.5 高響應比優先高響應比優先調度算法調度算法該算法將優先調度高響應比的進程，因此，從該算法將優先調度高響應比的進程，因此，從響應比計算可以看出：響應比計算可以看出：如果作業的等待時間相同，該算法有利于短作如果作業的等待時間相同，該算法有利于短作業，保持了短作業優先的特點；業，保持了短作業優先的特點；當要求服務的時間相同時，則先來先服務，滿當要求服務的時間相同時，則先來先服務，滿足了用戶的分時要求；足了用戶的分時要求；對于長作業，隨著等待時間增加，其優先權便對于長作業，隨著等待時間增加，其優先權便可升到很高，從而也可獲得處理機，避免了長作業可升到很高，從而也可獲得處理機，避免了長作業長時間得不

41、到服務的現象。長時間得不到服務的現象。 2022年5月24日星期二12時49分19秒計算機操作系統3.4.6 多級隊列多級隊列調度算法調度算法在多級隊列調度下，就緒隊列被分為若干個獨在多級隊列調度下，就緒隊列被分為若干個獨立子隊列。立子隊列。作業則根據其性質或類型，固定地分屬于一個作業則根據其性質或類型，固定地分屬于一個隊列。隊列。多級隊列調度包括隊列間調度和隊列內調度兩多級隊列調度包括隊列間調度和隊列內調度兩部分內容。部分內容。2022年5月24日星期二12時49分19秒計算機操作系統3.4.6 多級隊列多級隊列調度算法調度算法隊列之間的關系可以采取多種方式來處理。隊列之間的關系可以采取多種

42、方式來處理。應用較多的一種方式是規定好每個隊列的優先應用較多的一種方式是規定好每個隊列的優先權，優先權高的隊列優先獲得調度。如在具有前、權，優先權高的隊列優先獲得調度。如在具有前、后臺隊列的系統中，是優先調度前臺隊列中的進程后臺隊列的系統中，是優先調度前臺隊列中的進程執行；僅當前臺隊列中已無可運行的進程時，方才執行；僅當前臺隊列中已無可運行的進程時，方才調度后臺隊列中的進程運行。另一種處理各隊列間調度后臺隊列中的進程運行。另一種處理各隊列間關系的方式是為各隊列分配一定的占用關系的方式是為各隊列分配一定的占用CPUCPU的時間的時間比例。比如，可為前臺隊列分配比例。比如，可為前臺隊列分配8080

43、的的CPUCPU時間，時間，給后臺隊列給后臺隊列2020的的CPUCPU時間。時間。 2022年5月24日星期二12時49分19秒計算機操作系統3.4.6 多級隊列多級隊列調度算法調度算法隊列之間的關系的另一種處理方式是：為各隊隊列之間的關系的另一種處理方式是：為各隊列分配一定的占用列分配一定的占用CPUCPU的時間比例。比如，可為前的時間比例。比如，可為前臺隊列分配臺隊列分配8080的的CPUCPU時間，給后臺隊列時間，給后臺隊列2020的的CPUCPU時間。時間。 2022年5月24日星期二12時49分19秒計算機操作系統3.4.6 多級反饋隊列多級反饋隊列調度算法調度算法在多級反饋隊列調

44、度下，就緒隊列也是被分為在多級反饋隊列調度下，就緒隊列也是被分為若干個獨立子隊列若干個獨立子隊列。調度也分成隊列間調度和隊列。調度也分成隊列間調度和隊列內調度兩部分。內調度兩部分。但進程不是根據其性質或類型固定地分屬于一但進程不是根據其性質或類型固定地分屬于一個隊列，而是根據其使用個隊列，而是根據其使用CPUCPU時間的長短來動態地時間的長短來動態地決定作業屬于那級隊列。決定作業屬于那級隊列。2022年5月24日星期二12時49分19秒計算機操作系統3.4.6 多級反饋隊列多級反饋隊列調度算法調度算法調度實施過程如下：調度實施過程如下：1.就緒隊列分為若干個獨立子隊列就緒隊列分為若干個獨立子隊

45、列，各個隊列，各個隊列賦予不同的優先權賦予不同的優先權。第一個隊列的優先權最高，第第一個隊列的優先權最高，第二隊列次之，其余隊列的優先權逐個降低。二隊列次之，其余隊列的優先權逐個降低。 2.2.其次，賦予各個隊列中進程執行時間片大小其次，賦予各個隊列中進程執行時間片大小也各不相同，在優先權愈高的隊列中，每個進程的也各不相同，在優先權愈高的隊列中，每個進程的執行時間片就規定得愈小，而優先權低的隊列會分執行時間片就規定得愈小，而優先權低的隊列會分配成倍于高一級優先級的隊列的時間片。配成倍于高一級優先級的隊列的時間片。 2022年5月24日星期二12時49分19秒計算機操作系統3.4.6 多級反饋隊

46、列多級反饋隊列調度算法調度算法3.當一個新進程進入內存后，首先將它放入第當一個新進程進入內存后，首先將它放入第一隊列的末尾，按一隊列的末尾，按FCFS原則排隊等待調度。當輪原則排隊等待調度。當輪到該進程執行時，如能在該時間片內完成，便可準到該進程執行時，如能在該時間片內完成，便可準備撤離系統；如果它在一個時間片結束時尚未完成，備撤離系統；如果它在一個時間片結束時尚未完成，調度程序便將該進程轉入第二隊列的末尾，再同樣調度程序便將該進程轉入第二隊列的末尾，再同樣地按照地按照FCFS原則等待調度執行；如果它在第二隊原則等待調度執行；如果它在第二隊列中運行一個時間片仍未完成，再依法將它輸入第列中運行一

47、個時間片仍未完成，再依法將它輸入第三隊列三隊列依此規律，直至進程全部完成。依此規律，直至進程全部完成。 2022年5月24日星期二12時49分19秒計算機操作系統3.4.6 多級反饋隊列多級反饋隊列調度算法調度算法4. 僅當第一隊列空閑時，調度程序才調度第二僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；僅當第（隊列中的進程運行；僅當第（1i-1）隊列為空時，隊列為空時，才調度第才調度第i隊列的進程運行。如果處理機正在運行隊列的進程運行。如果處理機正在運行第第i隊列的進程，而此時又有新的進程進入優先權隊列的進程，而此時又有新的進程進入優先權較高的任一隊列（較高的任一隊列（1i-1隊列）

48、，則此時新的進程隊列），則此時新的進程將搶占處理機，即調度程序將處理機重新分配給新將搶占處理機，即調度程序將處理機重新分配給新進入進入1i-1隊列的進程，并把被搶先的進程投入原隊列的進程，并把被搶先的進程投入原隊列的末尾。隊列的末尾。 2022年5月24日星期二12時49分19秒計算機操作系統3.5.1 先來先服務先來先服務(FCFS)先來先服務算法只是簡單地按照進程或作業到先來先服務算法只是簡單地按照進程或作業到達的先后次序來調度。達的先后次序來調度。例如：一組進程的例如：一組進程的FCFS調度結果如下表調度結果如下表 2022年5月24日星期二12時49分19秒計算機操作系統3.5.1 先

49、來先服務先來先服務(FCFS)分析該調度實例，得到如下相關參數：分析該調度實例，得到如下相關參數：從上表可以看出：優先到達的作業最先得到調度，從上表可以看出：優先到達的作業最先得到調度，有著最優的帶權響應時間；但其后到的長作業有著最優的帶權響應時間；但其后到的長作業D也也有較優的帶權周轉時間，僅為有較優的帶權周轉時間，僅為1.99。帶權周轉時間。帶權周轉時間最長的是后到的短作業最長的是后到的短作業C，高達高達100。 2022年5月24日星期二12時49分19秒計算機操作系統3.5.1 先來先服務先來先服務(FCFS)因此，因此，FCFS算法比較有利于優先到達的作業算法比較有利于優先到達的作業

50、和長作業，而不利于短作業。和長作業，而不利于短作業。所以，對于所以，對于CPU繁忙型的作業，由于它需要大繁忙型的作業，由于它需要大量的量的CPU時間進行計算，而很少請求時間進行計算，而很少請求I/O，先來先先來先服務型調度將獲得較好的效率。但對于服務型調度將獲得較好的效率。但對于I/O繁忙型繁忙型的作業的作業(進程進程)，需頻繁地請求，需頻繁地請求I/O，而每次而每次I/O的操的操作時間卻又很短，此時先來先服務型調度產生的效作時間卻又很短，此時先來先服務型調度產生的效果將難以接受。果將難以接受。 2022年5月24日星期二12時49分19秒計算機操作系統3.5.2 短作業短作業( (進程進程)

51、 )優先調度優先調度( (SJF/SPF) )該算法以作業該算法以作業( (進程進程) )所需要時間的長短作為調所需要時間的長短作為調度的唯一標準，它較好地照顧到了實際上在作業度的唯一標準，它較好地照顧到了實際上在作業( (進程進程) )中占很大比例的短作業中占很大比例的短作業( (進程進程) )，使它們能比，使它們能比長作業長作業( (進程進程) )優先執行。優先執行。2022年5月24日星期二12時49分19秒計算機操作系統3.5.2 短作業短作業( (進程進程) )優先調度優先調度( (SJF/SPF) )該調度算法使短作業該調度算法使短作業( (進程進程) )得到了很好的調度，得到了很

52、好的調度，但存在著以下幾方面的問題：但存在著以下幾方面的問題：該算法對長作業非常不利；該算法對長作業非常不利；該算法完全未考慮作業該算法完全未考慮作業( (進程進程) )的緊迫程度，因而的緊迫程度，因而不能保證緊迫性作業不能保證緊迫性作業( (進程進程) )會得到及時處理；會得到及時處理；作業作業( (進程進程) )的長短是根據用戶所提供的估計執行的長短是根據用戶所提供的估計執行時間而定，存在著一定的不合理。時間而定，存在著一定的不合理。2022年5月24日星期二12時49分19秒計算機操作系統3.5.3 時間片輪轉時間片輪轉 該調度算法中，系統將運行時間進行劃分成時該調度算法中，系統將運行時

53、間進行劃分成時間片，各個任務或進程之間采取先來先服務的原則間片，各個任務或進程之間采取先來先服務的原則進行調度，輪流分配一個時間片。進行調度，輪流分配一個時間片。時間片劃分后的輪轉使得短任務得到了較快的時間片劃分后的輪轉使得短任務得到了較快的響應，同時先來先服務的原則又使各個任務或進程響應，同時先來先服務的原則又使各個任務或進程獲得處理機的機會非常均等，因此這一算法較之前獲得處理機的機會非常均等，因此這一算法較之前兩種算法在調度效果上均有一些改善。兩種算法在調度效果上均有一些改善。 2022年5月24日星期二12時49分19秒計算機操作系統3.5.3 時間片輪轉時間片輪轉 該算法的調度效果依賴

54、于時間片的合理劃分，該算法的調度效果依賴于時間片的合理劃分，如果時間片太大，每一個作業或進程只需要一個時如果時間片太大，每一個作業或進程只需要一個時間片便可以完成，那么這種形式的時間片輪轉則等間片便可以完成，那么這種形式的時間片輪轉則等同于先來先服務調度法；時間片如果劃分得太細，同于先來先服務調度法；時間片如果劃分得太細，則系統性能將在調度上嚴重損耗。則系統性能將在調度上嚴重損耗。 2022年5月24日星期二12時49分19秒計算機操作系統3.5.4 三種調度算法的調度結果比較三種調度算法的調度結果比較2022年5月24日星期二12時49分19秒計算機操作系統3.5.4 三種調度算法的調度結果

55、比較三種調度算法的調度結果比較從上表中看到：從上表中看到：長作業在長作業在FCSFFCSF中有著較優的參數，在三種調度方式中最中有著較優的參數，在三種調度方式中最優。優。SJ(P)SJ(P)下平均周轉時間和帶權平均周轉時間均較優，因此下平均周轉時間和帶權平均周轉時間均較優，因此系統效率較優，將有效地降低作業的平均等待時間，提高系統效率較優，將有效地降低作業的平均等待時間，提高系統的呑吐量。而短作業系統的呑吐量。而短作業D D的帶權周轉時間從的帶權周轉時間從5.55.5下降到下降到1.51.5，長作業長作業( (進程進程C)C)的帶權周轉時間的帶權周轉時間從從FCFSFCFS算法下的算法下的2.

56、02.0增加到增加到了了3.23.2，也就是說，短作業的優勢非常明顯，長作業有可能，也就是說，短作業的優勢非常明顯，長作業有可能得不到合適的調度。得不到合適的調度。2022年5月24日星期二12時49分19秒計算機操作系統3.5.4 三種調度算法的調度結果比較三種調度算法的調度結果比較RRRR方式下，表中數據顯示，在該形式下的各個作方式下，表中數據顯示，在該形式下的各個作業的帶權周轉時間比較均衡，先來后到的差別被消業的帶權周轉時間比較均衡，先來后到的差別被消除，充分體現了分時系統的需要。時間片的大小對除，充分體現了分時系統的需要。時間片的大小對效率參數起著非常大的影響作用，從表中看到，對效率參

57、數起著非常大的影響作用，從表中看到，對于某一組作業于某一組作業( (進程進程) )，當時間片足夠大時，它，當時間片足夠大時，它與與FCFSFCFS調度算法有著完全相同的調度效果。調度算法有著完全相同的調度效果。2022年5月24日星期二12時49分19秒計算機操作系統3.5.5 優先權調度算法優先權調度算法 優先權調度法加入了一個優先權參數，該參數的主觀優先權調度法加入了一個優先權參數，該參數的主觀可調性為操作者控制系統的調度性能提供了方便，對于緊可調性為操作者控制系統的調度性能提供了方便，對于緊急作業急作業(進程進程)，可以人為賦予高優先權，用搶占式優先調度，可以人為賦予高優先權，用搶占式優

58、先調度保證其實時性；而動態優先權法能夠運行過程中根據系統保證其實時性；而動態優先權法能夠運行過程中根據系統的狀況及時調整調度，因而，長短作業的狀況及時調整調度，因而，長短作業(進程進程)得到了很好地得到了很好地協調，既能避免短作業協調，既能避免短作業(進程進程)的長時間等待，又能使長作業的長時間等待，又能使長作業(進程進程)得到適時的調度，兼得了得到適時的調度，兼得了FCFS和和SJF/SPF的優點。的優點。 2022年5月24日星期二12時49分20秒計算機操作系統3.5.6 高響應比優先調度算法高響應比優先調度算法 高響應比優先調度算法也是一種優先權調度高響應比優先調度算法也是一種優先權調

59、度算法。在這一算法是在短作業優先的基礎上，對等算法。在這一算法是在短作業優先的基礎上，對等待時間長的作業動態地賦予它不斷增長的優先級。待時間長的作業動態地賦予它不斷增長的優先級。這種算法保留了短作業優先算法的優點，并通過優這種算法保留了短作業優先算法的優點，并通過優先級參數的動態修改，避免了長作業的長等待。先級參數的動態修改，避免了長作業的長等待。 2022年5月24日星期二12時49分20秒計算機操作系統3.5.7 多級隊列調度算法多級隊列調度算法 多級隊列調度對進程施行分級管理，同時也多級隊列調度對進程施行分級管理，同時也對隊列和隊列內的進程進行分級調度。這種分而治對隊列和隊列內的進程進行

60、分級調度。這種分而治之的調度策略使得不同類型的進程能夠得到更有效之的調度策略使得不同類型的進程能夠得到更有效的管理，使得系統對進程的管理更為合理，采用此的管理，使得系統對進程的管理更為合理，采用此算法的系統具有更強的適應能力。算法的系統具有更強的適應能力。2022年5月24日星期二12時49分20秒計算機操作系統3.5.8 多級反饋隊列調度算法多級反饋隊列調度算法多級隊列調度對進程施行分級管理，同時也多級隊列調度對進程施行分級管理，同時也對隊列和隊列內的進程進行分級調度。這種分而治對隊列和隊列內的進程進行分級調度。這種分而治之的調度策略使得不同類型的進程能夠得到更有效之的調度策略使得不同類型的