第3章_調(diào)度20050722

1、2022年5月24日星期二12時49分17秒計算機操作系統(tǒng)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秒計算機操作系統(tǒng)3.1.1 調(diào)度的意義調(diào)度的意義調(diào)度策略有兩個最根本的目標(biāo)：調(diào)度策略有兩個最根本的目標(biāo)： 1、合理性合理性：在多道作業(yè)在多道作業(yè)(進程進程)并發(fā)時，使各道作并發(fā)時，使各道作業(yè)合理地分配到處理機份額。業(yè)合理地

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

22、計算機操作系統(tǒng)3.3.3 3.3.3 進程上下文切換進程上下文切換 一個進程的執(zhí)行是在進程的上下文中進行。當(dāng)一個進程的執(zhí)行是在進程的上下文中進行。當(dāng)正在執(zhí)行的進程由于種原因要讓出處理機時，系統(tǒng)正在執(zhí)行的進程由于種原因要讓出處理機時，系統(tǒng)要做進程上下文切換，以使另一個進程得以執(zhí)行。要做進程上下文切換，以使另一個進程得以執(zhí)行。切換時，包括進程的狀態(tài)、有關(guān)變量和數(shù)據(jù)結(jié)切換時，包括進程的狀態(tài)、有關(guān)變量和數(shù)據(jù)結(jié)構(gòu)的值、機器寄存器的值和構(gòu)的值、機器寄存器的值和PCBPCB以及有關(guān)程序、數(shù)以及有關(guān)程序、數(shù)據(jù)等的上下文需要切換。據(jù)等的上下文需要切換。2022年5月24日星期二12時49分19秒計算機操作系統(tǒng)3

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

24、eemptive ModeNon-Preemptive Mode）也稱非剝奪調(diào)度。這是一種較為簡單的調(diào)度方也稱非剝奪調(diào)度。這是一種較為簡單的調(diào)度方式。在該調(diào)度方式下，當(dāng)進程分配到處理機時，其式。在該調(diào)度方式下，當(dāng)進程分配到處理機時，其他進程不可以搶占，只有在進程自動放棄處理機時，他進程不可以搶占，只有在進程自動放棄處理機時，才進行調(diào)度。才進行調(diào)度。2022年5月24日星期二12時49分19秒計算機操作系統(tǒng)3.3.4 進程調(diào)度有兩種基本方式進程調(diào)度有兩種基本方式方式：非搶占方式（方式：非搶占方式（Non-Preemptive Mode）優(yōu)點：系統(tǒng)開銷?。徊捎梅菗屨挤绞綍r，程序優(yōu)點：系統(tǒng)開銷?。徊?/p>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

42、方式來處理。應(yīng)用較多的一種方式是規(guī)定好每個隊列的優(yōu)先應(yīng)用較多的一種方式是規(guī)定好每個隊列的優(yōu)先權(quán)，優(yōu)先權(quán)高的隊列優(yōu)先獲得調(diào)度。如在具有前、權(quán)，優(yōu)先權(quán)高的隊列優(yōu)先獲得調(diào)度。如在具有前、后臺隊列的系統(tǒng)中，是優(yōu)先調(diào)度前臺隊列中的進程后臺隊列的系統(tǒng)中，是優(yōu)先調(diào)度前臺隊列中的進程執(zhí)行；僅當(dāng)前臺隊列中已無可運行的進程時，方才執(zhí)行；僅當(dāng)前臺隊列中已無可運行的進程時，方才調(diào)度后臺隊列中的進程運行。另一種處理各隊列間調(diào)度后臺隊列中的進程運行。另一種處理各隊列間關(guān)系的方式是為各隊列分配一定的占用關(guān)系的方式是為各隊列分配一定的占用CPUCPU的時間的時間比例。比如，可為前臺隊列分配比例。比如，可為前臺隊列分配8080

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

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

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

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

47、個時間片仍未完成，再依法將它輸入第三隊列三隊列依此規(guī)律，直至進程全部完成。依此規(guī)律，直至進程全部完成。 2022年5月24日星期二12時49分19秒計算機操作系統(tǒng)3.4.6 多級反饋隊列多級反饋隊列調(diào)度算法調(diào)度算法4. 僅當(dāng)?shù)谝魂犃锌臻e時，調(diào)度程序才調(diào)度第二僅當(dāng)?shù)谝魂犃锌臻e時，調(diào)度程序才調(diào)度第二隊列中的進程運行；僅當(dāng)?shù)冢犃兄械倪M程運行；僅當(dāng)?shù)冢?i-1）隊列為空時，隊列為空時，才調(diào)度第才調(diào)度第i隊列的進程運行。如果處理機正在運行隊列的進程運行。如果處理機正在運行第第i隊列的進程，而此時又有新的進程進入優(yōu)先權(quán)隊列的進程，而此時又有新的進程進入優(yōu)先權(quán)較高的任一隊列（較高的任一隊列（1i-1隊列）

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

49、來先服務(wù)先來先服務(wù)(FCFS)分析該調(diào)度實例，得到如下相關(guān)參數(shù)：分析該調(diào)度實例，得到如下相關(guān)參數(shù)：從上表可以看出：優(yōu)先到達的作業(yè)最先得到調(diào)度，從上表可以看出：優(yōu)先到達的作業(yè)最先得到調(diào)度，有著最優(yōu)的帶權(quán)響應(yīng)時間；但其后到的長作業(yè)有著最優(yōu)的帶權(quán)響應(yīng)時間；但其后到的長作業(yè)D也也有較優(yōu)的帶權(quán)周轉(zhuǎn)時間，僅為有較優(yōu)的帶權(quán)周轉(zhuǎn)時間，僅為1.99。帶權(quán)周轉(zhuǎn)時間。帶權(quán)周轉(zhuǎn)時間最長的是后到的短作業(yè)最長的是后到的短作業(yè)C，高達高達100。 2022年5月24日星期二12時49分19秒計算機操作系統(tǒng)3.5.1 先來先服務(wù)先來先服務(wù)(FCFS)因此，因此，F(xiàn)CFS算法比較有利于優(yōu)先到達的作業(yè)算法比較有利于優(yōu)先到達的作業(yè)

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

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

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

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

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

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

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

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

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

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

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