1、第第4章章 處理機調度處理機調度4.1 分級調度分級調度4.2 作業調度作業調度4.3 進程調度進程調度4.4 調度算法調度算法4.5 算法評價算法評價4.6 實時系統調度方法實時系統調度方法本章小結本章小結習題習題CPU是計算機系統中一個十分重要的資源。在早期是計算機系統中一個十分重要的資源。在早期的計算機系統中，對它的管理是十分簡單的。隨著的計算機系統中，對它的管理是十分簡單的。隨著多道程序設計技術和各種不同類型的操作系統的出多道程序設計技術和各種不同類型的操作系統的出現，各種不同的現，各種不同的CPU管理方法得到啟用。不同的管理方法得到啟用。不同的CPU管理方法將為用戶提供不同性能的操作

2、系統。管理方法將為用戶提供不同性能的操作系統。例如：在多道批處理系統中，為了提高處理機的效例如：在多道批處理系統中，為了提高處理機的效率和增加作業吞吐率，當調度一批作業組織多道運率和增加作業吞吐率，當調度一批作業組織多道運行時，要盡可能使作業搭配合理。這樣，就能使系行時，要盡可能使作業搭配合理。這樣，就能使系統中的各種資源可充分利用。但由于是批處理，在統中的各種資源可充分利用。但由于是批處理，在用戶看來，這是一臺沒有交互、速度較慢的處理機。用戶看來，這是一臺沒有交互、速度較慢的處理機。在分時系統中，在調度作業執行時要首先考慮每個在分時系統中，在調度作業執行時要首先考慮每個用戶作業得到處理機的均

3、等性。這樣，系統資源的用戶作業得到處理機的均等性。這樣，系統資源的利用率就不如批處理系統。由此可以看到，根據操利用率就不如批處理系統。由此可以看到，根據操作系統的要求不同，處理機管理的策略是不同的。作系統的要求不同，處理機管理的策略是不同的。衡量調度策略的最常用的幾個指標是：周轉時間、衡量調度策略的最常用的幾個指標是：周轉時間、吞吐率、響應時間以及設備利用率等。周轉時間是吞吐率、響應時間以及設備利用率等。周轉時間是指將一個作業提交給計算機系統后到該作業的結果指將一個作業提交給計算機系統后到該作業的結果返回給用戶所需要的時間。吞吐率是指在給定的時返回給用戶所需要的時間。吞吐率是指在給定的時間內，

4、一個計算機系統所完成的總工作量。響應時間內，一個計算機系統所完成的總工作量。響應時間則是指從用戶向計算機發出一個命令到計算機把間則是指從用戶向計算機發出一個命令到計算機把相應的執行結果返回給用戶所需要的時間。設備利相應的執行結果返回給用戶所需要的時間。設備利用率主要指輸入輸出設備的使用情況。用率主要指輸入輸出設備的使用情況。本章將以本章將以CPU 管理為核心，討論管理、控制用戶進管理為核心，討論管理、控制用戶進程執行的方法。主要包括：程執行的方法。主要包括：(1) 作業與進程的關系；作業與進程的關系；(2) 作業調度策略與算法；作業調度策略與算法；(3) 進程調度策略與算法；進程調度策略與算法

5、；(4) 幾種調度策略的評價。幾種調度策略的評價。另外，還介紹實時調度系統。另外，還介紹實時調度系統。4.1 分分 級級 調調 度度4.1.1 作業的狀態及其轉換作業的狀態及其轉換在第在第2章中，介紹了用戶如何利用操作系統提供的手章中，介紹了用戶如何利用操作系統提供的手段與工具去組織和控制自己的作業運行。但是，一段與工具去組織和控制自己的作業運行。但是，一個作業從用戶提交開始到真正占有處理機而被執行，個作業從用戶提交開始到真正占有處理機而被執行，則要由系統經過多級調度才能實現（在有些系統，則要由系統經過多級調度才能實現（在有些系統，例如分時系統中，也可以由單級調度實現），下面例如分時系統中，也

6、可以由單級調度實現），下面以批處理系統為例看一個作業處理的大致過程。以批處理系統為例看一個作業處理的大致過程。如圖如圖4.1 所示，一個作業從提交給計算機系統到執行所示，一個作業從提交給計算機系統到執行結束退出系統，一般都要經歷提交、收容、執行和結束退出系統，一般都要經歷提交、收容、執行和完成等完成等4個狀態。個狀態。圖圖4.1 作業的狀態及其轉換作業的狀態及其轉換一個作業在其處于從輸入設備進入外部存儲設備的一個作業在其處于從輸入設備進入外部存儲設備的過程稱為提交狀態。處于提交狀態的作業，因其信過程稱為提交狀態。處于提交狀態的作業，因其信息尚未全部進入系統，所以不能被調度程序選取。息尚未全部進

7、入系統，所以不能被調度程序選取。收容狀態也稱為后備狀態。輸入管理系統不斷地將收容狀態也稱為后備狀態。輸入管理系統不斷地將作業輸入到外存中對應部分（或稱輸入井，即專門作業輸入到外存中對應部分（或稱輸入井，即專門用來存放待處理作業信息的一組外存分區）。若一用來存放待處理作業信息的一組外存分區）。若一個作業的全部信息已全部被輸入進輸入井，那么，個作業的全部信息已全部被輸入進輸入井，那么，在它還未被調度去執行之前，該作業處于收容狀態。在它還未被調度去執行之前，該作業處于收容狀態。作業調度程序從后備作業中選取若干個作業到內存作業調度程序從后備作業中選取若干個作業到內存投入運行。它為被選中作業建立進程并分

8、配必要的投入運行。它為被選中作業建立進程并分配必要的資源，這時，這些被選中的作業處于執行狀態。從資源，這時，這些被選中的作業處于執行狀態。從宏觀上看，這些作業正處在執行過程中，但從微觀宏觀上看，這些作業正處在執行過程中，但從微觀上看，在某一時刻，由于處理機總數少于并發執行上看，在某一時刻，由于處理機總數少于并發執行的進程數，因此，不是所有被選中作業都占有處理的進程數，因此，不是所有被選中作業都占有處理機，其中的大部分處于等待資源或就緒狀態中。那機，其中的大部分處于等待資源或就緒狀態中。那么，究竟哪個作業的哪個進程能獲得處理機而真正么，究竟哪個作業的哪個進程能獲得處理機而真正在執行，要依靠進程調

9、度來決定。在執行，要依靠進程調度來決定。當作業運行完畢，但它所占用的資源尚未全部被系當作業運行完畢，但它所占用的資源尚未全部被系統回收時，該作業處于完成狀態。在這種狀態下，統回收時，該作業處于完成狀態。在這種狀態下，系統需做諸如打印結果、回收資源等類的善后處理系統需做諸如打印結果、回收資源等類的善后處理工作。工作。4.1.2 調度的層次調度的層次處理機調度問題實際上也是處理機的分配問題。顯處理機調度問題實際上也是處理機的分配問題。顯然，只有那些參與競爭處理機所必需的資源都已得然，只有那些參與競爭處理機所必需的資源都已得到滿足的進程才能享有競爭處理機的資格。這時，到滿足的進程才能享有競爭處理機的

10、資格。這時，它們處于內存就緒狀態。這些必需的資源包括內存、它們處于內存就緒狀態。這些必需的資源包括內存、外設及有關數據結構等。從而，在進程有資格競爭外設及有關數據結構等。從而，在進程有資格競爭處理機之前，作業調度程序必須先調用存儲管理、處理機之前，作業調度程序必須先調用存儲管理、外設管理程序，并按一定的選擇順序和策略從輸入外設管理程序，并按一定的選擇順序和策略從輸入井中選擇出幾個處于后備狀態的作業，為它們分配井中選擇出幾個處于后備狀態的作業，為它們分配內存等資源和創建進程，使它們獲得競爭處理機的內存等資源和創建進程，使它們獲得競爭處理機的資格。資格。另外，由于處于執行狀態下的作業一般包含有多個

11、另外，由于處于執行狀態下的作業一般包含有多個進程，而在單機系統中，每一時刻只能有一個進程進程，而在單機系統中，每一時刻只能有一個進程占有處理機。那么，其他進程就只能處于準備搶占占有處理機。那么，其他進程就只能處于準備搶占處理機的就緒狀態或等待得到某種新資源的等待狀處理機的就緒狀態或等待得到某種新資源的等待狀態。為了提高資源的利用率，在有些操作系統中把態。為了提高資源的利用率，在有些操作系統中把一部分在內存中處于就緒狀態或等待狀態而在短時一部分在內存中處于就緒狀態或等待狀態而在短時期內又得不到執行的進程、作業換出內存，以讓其期內又得不到執行的進程、作業換出內存，以讓其他作業的進程競爭處理機。這樣

12、，在外存中，除了他作業的進程競爭處理機。這樣，在外存中，除了處于后備狀態的作業外，還存在有處于就緒狀態而處于后備狀態的作業外，還存在有處于就緒狀態而等待得到內存的作業。這就需要有一定的方法和策等待得到內存的作業。這就需要有一定的方法和策略為這部分作業分配空間。略為這部分作業分配空間。一般來說，處理機調度可以分為一般來說，處理機調度可以分為4級：級：(1) 作業調度：又稱宏觀調度，或高級調度。其主要作業調度：又稱宏觀調度，或高級調度。其主要任務是按一定的原則對外存輸入井上的大量后備作任務是按一定的原則對外存輸入井上的大量后備作業進行選擇，給選出的作業分配內存、輸入輸出設業進行選擇，給選出的作業分

13、配內存、輸入輸出設備等必要的資源，并建立相應的進程，以使該作業備等必要的資源，并建立相應的進程，以使該作業的進程獲得競爭處理機的權利。另外，當該作業執的進程獲得競爭處理機的權利。另外，當該作業執行完畢時，還負責回收系統資源。行完畢時，還負責回收系統資源。(2) 交換調度：又稱中級調度。其主要任務是按照給交換調度：又稱中級調度。其主要任務是按照給定的原則和策略，將處于外存交換區中的就緒狀態定的原則和策略，將處于外存交換區中的就緒狀態或就緒等待狀態的進程調入內存，或把處于內存就或就緒等待狀態的進程調入內存，或把處于內存就緒狀態或內存等待狀態的進程交換到外存交換區。緒狀態或內存等待狀態的進程交換到外

14、存交換區。交換調度主要涉及到內存管理與擴充。交換調度主要涉及到內存管理與擴充。(3) 進程調度：又稱微觀調度或低級調度。其主要任進程調度：又稱微觀調度或低級調度。其主要任務是按照某種策略和方法選取一個處于就緒狀態的務是按照某種策略和方法選取一個處于就緒狀態的進程占用處理機。在確定了占用處理機的進程后，進程占用處理機。在確定了占用處理機的進程后，系統必須進行進程上下文切換以建立與占用處理機系統必須進行進程上下文切換以建立與占用處理機進程相適應的執行環境。進程相適應的執行環境。(4) 線程調度。線程調度。上述上述4級調度的關系如圖級調度的關系如圖4.1。在多道批處理系統中，存在著作業調度和進程調度

15、。在多道批處理系統中，存在著作業調度和進程調度。但是，在分時系統和實時系統中，一般不存在作業但是，在分時系統和實時系統中，一般不存在作業調度，而只有進程調度、交換調度和線程調度。這調度，而只有進程調度、交換調度和線程調度。這是因為在分時系統和實時系統中，為了縮短響應時是因為在分時系統和實時系統中，為了縮短響應時間或為了滿足用戶需求的截止時間，作業不是建立間或為了滿足用戶需求的截止時間，作業不是建立在外存，而是直接建立在內存中。在這些系統中，在外存，而是直接建立在內存中。在這些系統中，一旦用戶和系統的交互開始，用戶馬上要進行控制。一旦用戶和系統的交互開始，用戶馬上要進行控制。因而，這些系統中沒有

16、作業提交狀態和后備狀態。因而，這些系統中沒有作業提交狀態和后備狀態。它們的輸入信息經過終端緩沖區為系統所接收，或它們的輸入信息經過終端緩沖區為系統所接收，或者立即處理，或者經交換調度暫存外存中。者立即處理，或者經交換調度暫存外存中。4.1.3 作業與進程的關系作業與進程的關系作業可被看作是用戶向計算機提交任務的任務實體，作業可被看作是用戶向計算機提交任務的任務實體，例如一次計算、一個控制過程等。反過來，進程則例如一次計算、一個控制過程等。反過來，進程則是計算機為了完成用戶任務實體而設置的執行實體，是計算機為了完成用戶任務實體而設置的執行實體，是系統分配資源的基本單位。顯然，計算機要完成是系統分

17、配資源的基本單位。顯然，計算機要完成一個任務實體，必須要有一個以上的執行實體。也一個任務實體，必須要有一個以上的執行實體。也就是說，一個作業總是由一個以上的多個進程組成就是說，一個作業總是由一個以上的多個進程組成的。那么，作業怎樣分解為進程呢？首先，系統必的。那么，作業怎樣分解為進程呢？首先，系統必須為一個作業創建一個根進程。然后，在執行作業須為一個作業創建一個根進程。然后，在執行作業控制語句時，根據任務要求，系統或根進程為其創控制語句時，根據任務要求，系統或根進程為其創建相應的子進程，然后，為各子進程分配資源和調建相應的子進程，然后，為各子進程分配資源和調度各子進程執行以完成作業要求的任務。

18、度各子進程執行以完成作業要求的任務。4.2 作作 業業 調調 度度作業調度主要是完成作業從后備狀態到執行狀態的作業調度主要是完成作業從后備狀態到執行狀態的轉變，以及從執行狀態到完成狀態的轉變。本節主轉變，以及從執行狀態到完成狀態的轉變。本節主要介紹作業調度的功能及調度性能的評價方法。要介紹作業調度的功能及調度性能的評價方法。4.2.1 作業調度功能作業調度功能(1) 記錄系統中各作業的狀況。作業調度程序要能挑記錄系統中各作業的狀況。作業調度程序要能挑選出一個作業投入執行，并且在執行中對其進行管選出一個作業投入執行，并且在執行中對其進行管理，它就必須掌握作業在各個狀態，包括執行階段理，它就必須掌

19、握作業在各個狀態，包括執行階段的有關情況。通常，系統為每個作業建立一個作業的有關情況。通常，系統為每個作業建立一個作業控制表控制表JCB記錄這些有關信息。系統通過記錄這些有關信息。系統通過JCB而感而感知作業的存在。系統在作業進入后備狀態時為該作知作業的存在。系統在作業進入后備狀態時為該作業建立它的業建立它的JCB，從而使得該作業可被作業調度程，從而使得該作業可被作業調度程序感知。當該作業執行完畢進入完成狀態之后，系序感知。當該作業執行完畢進入完成狀態之后，系統又撤消其統又撤消其JCB而釋放有關資源并撤消該作業。而釋放有關資源并撤消該作業。對于不同的批處理系統，其對于不同的批處理系統，其JCB

20、的內容也有所不同。的內容也有所不同。圖圖4.2給出了給出了JCB的主要內容。它包括作業名、作業的主要內容。它包括作業名、作業類型、資源要求、當前狀態、資源使用情況以及該類型、資源要求、當前狀態、資源使用情況以及該作業的優先級等。作業的優先級等。圖圖4.2 作業控制塊作業控制塊JCB作業名作業名作業類型作業類型資源要求資源要求資源使用情況資源使用情況優先級優先級(數數)當前狀態當前狀態其他其他其中，作業名由用戶提供并由系統將其轉換為系統其中，作業名由用戶提供并由系統將其轉換為系統可識別的作業標識符。作業類型指該作業屬于計算可識別的作業標識符。作業類型指該作業屬于計算型（要求型（要求CPU時間多）

21、還是管理型（要求輸入輸時間多）還是管理型（要求輸入輸出量大）出量大）,或圖形設計型（要求高速圖形顯示）等。或圖形設計型（要求高速圖形顯示）等。而資源要求則包括：該作業估計執行時間、要求最而資源要求則包括：該作業估計執行時間、要求最遲完成時間、要求的內存量和外存量、要求的外設遲完成時間、要求的內存量和外存量、要求的外設類型及臺數以及要求的軟件支持工具庫函數等。資類型及臺數以及要求的軟件支持工具庫函數等。資源要求均由用戶提供。資源使用情況包括有：作業源要求均由用戶提供。資源使用情況包括有：作業進入系統時間、開始執行時間、已執行時間、內存進入系統時間、開始執行時間、已執行時間、內存地址、外設臺數等。

22、優先級則被用來決定該作業的地址、外設臺數等。優先級則被用來決定該作業的調度次序。優先級既可以由用戶給定，也可以由系調度次序。優先級既可以由用戶給定，也可以由系統動態計算產生。狀態是指該作業當前所處的狀態。統動態計算產生。狀態是指該作業當前所處的狀態。顯然，只有當作業處于后備狀態時，該作業才可以顯然，只有當作業處于后備狀態時，該作業才可以被調度。被調度。(2) 從后備隊列中挑選出一部分作業投入執行。作業從后備隊列中挑選出一部分作業投入執行。作業調度程序根據選定的調度算法，從后備作業隊列中調度程序根據選定的調度算法，從后備作業隊列中挑選出若干作業去投入執行。挑選出若干作業去投入執行。(3) 為被選

23、中作業做好執行前的準備工作。作業調度為被選中作業做好執行前的準備工作。作業調度程序為選中的作業建立相應的進程，并為這些進程程序為選中的作業建立相應的進程，并為這些進程分配它們所需要的系統資源，如分配給它們內存、分配它們所需要的系統資源，如分配給它們內存、外存、外設等。外存、外設等。(4) 在作業執行結束時做善后處理工作。主要是輸出在作業執行結束時做善后處理工作。主要是輸出作業管理信息，例如執行時間等。再就是回收該作作業管理信息，例如執行時間等。再就是回收該作業所占用的資源，撤消與該作業有關的全部進程和業所占用的資源，撤消與該作業有關的全部進程和該作業的作業控制塊等等。該作業的作業控制塊等等。作

24、業從后備狀態到執行狀態，又從執行狀態到完成作業從后備狀態到執行狀態，又從執行狀態到完成狀態的轉換過程如圖狀態的轉換過程如圖4.3所示。所示。圖圖4.3 作業調度中狀態的轉換過程作業調度中狀態的轉換過程4.2.2 作業調度目標與性能衡量作業調度目標與性能衡量作業調度的功能最主要的是從后備作業隊列中選取作業調度的功能最主要的是從后備作業隊列中選取一批作業進入執行狀態。根據不同的目標，將會有一批作業進入執行狀態。根據不同的目標，將會有不同的調度算法。這里先介紹調度目標。不同的調度算法。這里先介紹調度目標。一般來說，調度目標主要是以下一般來說，調度目標主要是以下4點：點：(1) 對所有作業應該是公平合

25、理的；對所有作業應該是公平合理的；(2) 應使設備有高的利用率；應使設備有高的利用率；(3) 每天執行盡可能多的作業；每天執行盡可能多的作業；(4) 有快的響應時間。有快的響應時間。由于這些目標的相互沖突，任一調度算法要想同時由于這些目標的相互沖突，任一調度算法要想同時滿足上述目標是不可能的。滿足上述目標是不可能的。必須指出，如果考慮的因素過多，調度算法就會變必須指出，如果考慮的因素過多，調度算法就會變得非常復雜。其結果是系統開銷增加，資源利用率得非常復雜。其結果是系統開銷增加，資源利用率下降。因此，大多數操作系統都根據用戶需要，采下降。因此，大多數操作系統都根據用戶需要，采用兼顧某些目標的簡

26、單調度算法。用兼顧某些目標的簡單調度算法。那么，怎樣來衡量一個作業調度算法是否滿足系統那么，怎樣來衡量一個作業調度算法是否滿足系統設計的要求呢？對于批處理系統，由于主要用于計設計的要求呢？對于批處理系統，由于主要用于計算，對于作業的周轉時間要求較高。因此，作業的算，對于作業的周轉時間要求較高。因此，作業的平均周轉時間或平均帶權周轉時間，被作為衡量調平均周轉時間或平均帶權周轉時間，被作為衡量調度算法優劣的標準。但是，對于分時系統和實時系度算法優劣的標準。但是，對于分時系統和實時系統來說，外加平均響應時間被作為衡量調度策略優統來說，外加平均響應時間被作為衡量調度策略優劣的標準。劣的標準。1. 周轉

27、時間：周轉時間：作業作業i的周轉時間的周轉時間Ti為為Ti=Tei-Tsi其中其中Tei為作業為作業i的完成時間，的完成時間，Tsi為作業的提交時間。為作業的提交時間。對于被測定作業流所含有的對于被測定作業流所含有的n（n=1）個作業來說，）個作業來說，其平均周轉時間為：其平均周轉時間為：一個作業的周轉時間說明了該作業在系統內停留的一個作業的周轉時間說明了該作業在系統內停留的時間，包含兩部分：等待時間；執行時間，即：時間，包含兩部分：等待時間；執行時間，即：Ti=TwiTri這里，這里，Twi主要指作業主要指作業i由后備狀態到執行狀態的等待由后備狀態到執行狀態的等待時間，它不包括作業進入執行狀

28、態后的等待時間。時間，它不包括作業進入執行狀態后的等待時間。nii = 11T =Tn2. 帶權周轉時間帶權周轉時間作業的周轉時間包含了兩個部分，即等待時間和執作業的周轉時間包含了兩個部分，即等待時間和執行時間。為了更進一步反映調度性能，使用帶權周行時間。為了更進一步反映調度性能，使用帶權周轉時間的概念。帶權周轉時間是作業周轉時間與作轉時間的概念。帶權周轉時間是作業周轉時間與作業執行時間的比：業執行時間的比：Wi=Ti/Tri對于被測定作業流所含有的幾個作業來說，其平均對于被測定作業流所含有的幾個作業來說，其平均帶權周轉時間為：帶權周轉時間為：對于分時系統，除了要保證系統吞吐量大、資源利對于分

29、時系統，除了要保證系統吞吐量大、資源利用率高之外，還應保證有用戶能夠容忍的響應時間。用率高之外，還應保證有用戶能夠容忍的響應時間。因此，在分時系統中，僅僅用周轉時間或帶權周轉因此，在分時系統中，僅僅用周轉時間或帶權周轉時間來衡量調度性能是不夠的。時間來衡量調度性能是不夠的。nii=11W =Wn4.3 進進 程程 調調 度度無論是在批處理系統還是分時系統中，用戶進程數無論是在批處理系統還是分時系統中，用戶進程數一般都多于處理機數，這將導致用戶進程互相爭奪一般都多于處理機數，這將導致用戶進程互相爭奪處理機。另外，系統進程也同樣需要使用處理機。處理機。另外，系統進程也同樣需要使用處理機。這就要求進

30、程調度程序按一定的策略，動態地把處這就要求進程調度程序按一定的策略，動態地把處理機分配給處于就緒隊列中的某一個進程，以使之理機分配給處于就緒隊列中的某一個進程，以使之執行。本節介紹進程調度的功能、進程調度發生的執行。本節介紹進程調度的功能、進程調度發生的時機以及由進程調度引起的進程上下文切換等。時機以及由進程調度引起的進程上下文切換等。4.3.1 進程調度的功能進程調度的功能進程調度的具體功能可總結如下：進程調度的具體功能可總結如下：(1) 記錄系統中所有進程的執行情況記錄系統中所有進程的執行情況作為進程調度的準備，進程管理模塊必須將系統中作為進程調度的準備，進程管理模塊必須將系統中各進程的執

31、行情況和狀態特征記錄在各進程的各進程的執行情況和狀態特征記錄在各進程的PCB表中。并且，進程管理模式根據各進程的狀態特征表中。并且，進程管理模式根據各進程的狀態特征和資源需求，將各進程的和資源需求，將各進程的PCB表排成相應的隊列并表排成相應的隊列并進行動態隊列轉接。進程調度模塊通過進行動態隊列轉接。進程調度模塊通過PCB變化來變化來掌握系統中所有進程的執行情況和狀態特征，并在掌握系統中所有進程的執行情況和狀態特征，并在適當的時機從就緒隊列中選擇出一個進程占據處理適當的時機從就緒隊列中選擇出一個進程占據處理機。機。(2) 選擇占有處理機的進程選擇占有處理機的進程進程調度的主要功能是按照一定的策

32、略選擇一個處進程調度的主要功能是按照一定的策略選擇一個處于就緒狀態的進程，使其獲得處理機執行。根據不于就緒狀態的進程，使其獲得處理機執行。根據不同的系統設計目的，有各種各樣的選擇策略，例如同的系統設計目的，有各種各樣的選擇策略，例如系統開銷較少的靜態優先數調度法，適合于分時系系統開銷較少的靜態優先數調度法，適合于分時系統的輪轉法和多級反饋輪轉法等。這些選擇策略決統的輪轉法和多級反饋輪轉法等。這些選擇策略決定了調度算法的性能。定了調度算法的性能。(3) 進行進程上下文切換進行進程上下文切換一個進程的上下文（一個進程的上下文（context）包括進程的狀態、有）包括進程的狀態、有關變量和數據結構的

33、值、硬件寄存器的值和關變量和數據結構的值、硬件寄存器的值和PCB以以及有關程序等。一個進程的執行是在進程的上下文及有關程序等。一個進程的執行是在進程的上下文中執行。當正在執行的進程由于某種原因要讓出處中執行。當正在執行的進程由于某種原因要讓出處理機時，系統要做進程上下文切換，以使另一個進理機時，系統要做進程上下文切換，以使另一個進程得以執行。當進行上下文切換時，系統要首先檢程得以執行。當進行上下文切換時，系統要首先檢查是否允許做上下文切換（。然后，系統要保留有查是否允許做上下文切換（。然后，系統要保留有關被切換進程的足夠信息，以便以后切換回該進程關被切換進程的足夠信息，以便以后切換回該進程時，

34、順利恢復該進程的執行。在系統保留了時，順利恢復該進程的執行。在系統保留了CPU現現場之后，調度程序選擇一個新的處于就緒狀態的進場之后，調度程序選擇一個新的處于就緒狀態的進程，并裝配該進程的上下文，使程，并裝配該進程的上下文，使CPU的控制權轉換的控制權轉換到被選中進程中。到被選中進程中。4.3.2 進程調度的時機進程調度的時機進程調度發生在什么時機呢？這與引起進程調度的進程調度發生在什么時機呢？這與引起進程調度的原因以及進程調度的方式有關。原因以及進程調度的方式有關。引起進程調度的原因有以下幾類：引起進程調度的原因有以下幾類：(1) 正在執行的進程執行完畢。這時，如果不選擇新正在執行的進程執行

35、完畢。這時，如果不選擇新的就緒進程執行，將浪費處理機資源。的就緒進程執行，將浪費處理機資源。(2) 執行中進程自己調用阻塞原語將自己阻塞起來進執行中進程自己調用阻塞原語將自己阻塞起來進入睡眠等待狀態。入睡眠等待狀態。(3) 執行中進程調用了執行中進程調用了P原語操作，從而因資源不足原語操作，從而因資源不足而被阻塞；或調用了而被阻塞；或調用了V原語操作激活了等待資源的原語操作激活了等待資源的進程隊列。進程隊列。(4) 執行中進程提出執行中進程提出IO請求后被阻塞。請求后被阻塞。(5) 在分時系統中時間片已經用完。在分時系統中時間片已經用完。(6) 在執行完系統調用，在系統程序返回用戶進程時，在執

36、行完系統調用，在系統程序返回用戶進程時，可認為系統進程執行完畢，從而可調度選擇一新的可認為系統進程執行完畢，從而可調度選擇一新的用戶進程執行。用戶進程執行。以上都是在以上都是在CPU執行不可剝奪方式下所引起進程調執行不可剝奪方式下所引起進程調度的原因。在度的原因。在CPU執行方式是可剝奪時，還有：執行方式是可剝奪時，還有：(7) 就緒隊列中的某進程的優先級變得高于當前執行就緒隊列中的某進程的優先級變得高于當前執行進程的優先級，從而也將引發進程調度。進程的優先級，從而也將引發進程調度。所謂可剝奪方式，即就緒隊列中一旦有優先級高于所謂可剝奪方式，即就緒隊列中一旦有優先級高于當前執行進程優先級的進程

37、存在時，便立即發生進當前執行進程優先級的進程存在時，便立即發生進程調度，轉讓處理機。而非剝奪方式或不可剝奪方程調度，轉讓處理機。而非剝奪方式或不可剝奪方式即使在就緒隊列存在有優先級高于當前執行進程式即使在就緒隊列存在有優先級高于當前執行進程時，當前進程仍將繼續占有處理機，直到該進程自時，當前進程仍將繼續占有處理機，直到該進程自己因調用原語操作或等待己因調用原語操作或等待IO而進入阻塞、睡眠而進入阻塞、睡眠狀態，或時間片用完時才重新發生調度讓出處理機。狀態，或時間片用完時才重新發生調度讓出處理機。操作系統將在以上幾種原因之一發生的情況下進行操作系統將在以上幾種原因之一發生的情況下進行進程調度。例

38、如，進程調度。例如，UNIX SystemV 就是在以下就是在以下5種種情況之一發生時進行進程調度的：情況之一發生時進行進程調度的：(1) 當前進程自己調用當前進程自己調用sleep，wait等進入睡眠狀態時。等進入睡眠狀態時。(2) 當前進程從系統調用執行結束后返回用戶態時，當前進程從系統調用執行結束后返回用戶態時，它的優先級已低于其他就緒狀態進程，或調度標志它的優先級已低于其他就緒狀態進程，或調度標志被置位。被置位。(3) 當前進程在完成中斷和陷阱處理后返回用戶態時，當前進程在完成中斷和陷阱處理后返回用戶態時，它的優先級已低于其他就緒狀態進程；或調度標志它的優先級已低于其他就緒狀態進程；或

39、調度標志被置位。被置位。(4) 時間片用完，而且當前進程的優先級低于其他就時間片用完，而且當前進程的優先級低于其他就緒進程。緒進程。(5) 當前進程調用當前進程調用exit，自我終止時。，自我終止時。4.3.3 進程上下文切換進程上下文切換進程上下文由正文段、數據段、硬件寄存器的內容進程上下文由正文段、數據段、硬件寄存器的內容以及有關數據結構等組成。硬件寄存器主要包括存以及有關數據結構等組成。硬件寄存器主要包括存放放CPU將要執行的下條指令虛擬地址的程序計數器將要執行的下條指令虛擬地址的程序計數器PC，指出機器與進程相關聯的硬件狀態的處理機，指出機器與進程相關聯的硬件狀態的處理機狀態寄存器狀態

40、寄存器PS，存放過程調用（或系統調用）時，存放過程調用（或系統調用）時所傳遞參數的通用寄存器所傳遞參數的通用寄存器R以及堆棧指針寄存器以及堆棧指針寄存器S等。數據結構則包括等。數據結構則包括PCB等在內的所有與執行該進等在內的所有與執行該進程有關的管理和控制用表格、數組、鏈等。在發生程有關的管理和控制用表格、數組、鏈等。在發生進程調度時，系統要做進程上下文切換。進程調度時，系統要做進程上下文切換。進程上下文切換包括進程上下文切換包括4個步驟：個步驟：(1) 決定是否做上下文切換以及是否允許做上下文切決定是否做上下文切換以及是否允許做上下文切換。包括對進程調度原因的檢查分析，以及當前執換。包括對

41、進程調度原因的檢查分析，以及當前執行進程的資格和行進程的資格和CPU執行方式的檢查等。執行方式的檢查等。(2) 保存當前執行進程的上下文。這里所說的當前執保存當前執行進程的上下文。這里所說的當前執行進程，實際上是指調用上下文切換程序之前的執行進程，實際上是指調用上下文切換程序之前的執行進程。如果上下文切換程序不是被那個當前執行行進程。如果上下文切換程序不是被那個當前執行進程所調用，且不屬于該進程，則所保存的上下文進程所調用，且不屬于該進程，則所保存的上下文應是先前執行進程的上下文，或稱為應是先前執行進程的上下文，或稱為“老老”進程上進程上下文。顯然，上下文切換程序不能破壞下文。顯然，上下文切換

42、程序不能破壞“老老”進程進程的上下文結構。的上下文結構。(3) 使用使用4.5節中所述進程調度算法，選擇一個處于就節中所述進程調度算法，選擇一個處于就緒狀態進程。緒狀態進程。(4) 恢復或裝配所選進程的上下文，將恢復或裝配所選進程的上下文，將CPU控制權交控制權交給所選進程。給所選進程。4.3.4 進程調度性能評價進程調度性能評價進程調度雖然是系統內部的低級調度，但進程調度進程調度雖然是系統內部的低級調度，但進程調度的優劣直接影響作業調度的性能。反映作業調度優的優劣直接影響作業調度的性能。反映作業調度優劣的周轉時間和平均周轉時間只在某種程度上反映劣的周轉時間和平均周轉時間只在某種程度上反映了進

43、程調度的性能，例如，其執行時間部分中實際了進程調度的性能，例如，其執行時間部分中實際上包含有進程等待（包括就緒狀態時的等待）時間，上包含有進程等待（包括就緒狀態時的等待）時間，而進程等待時間的多少是要依靠進程調度策略和等而進程等待時間的多少是要依靠進程調度策略和等待事件何時發生來決定的。因此，進程調度性能的待事件何時發生來決定的。因此，進程調度性能的衡量是操作系統設計的一個重要指標。衡量是操作系統設計的一個重要指標。進程調度性能的衡量方法可分為定性和定量兩種。進程調度性能的衡量方法可分為定性和定量兩種。在定性衡量方面，首先是調度的可靠性。另外，簡在定性衡量方面，首先是調度的可靠性。另外，簡潔性

44、也是衡量進程調度的一個重要指標。潔性也是衡量進程調度的一個重要指標。進程調度的定量評價包括進程調度的定量評價包括CPU的利用率評價、進程的利用率評價、進程在就緒隊列中的等待時間與執行時間之比等。實際在就緒隊列中的等待時間與執行時間之比等。實際上，由于進程進入就緒隊列的隨機模型很難確定，上，由于進程進入就緒隊列的隨機模型很難確定，而且進程上下文切換等也將影響進程的執行效率，而且進程上下文切換等也將影響進程的執行效率，從而對進程調度進行解析是很困難的。一般情況下，從而對進程調度進行解析是很困難的。一般情況下，大多利用模擬或測試系統響應時間的方法來評價進大多利用模擬或測試系統響應時間的方法來評價進程

45、調度的性能。程調度的性能。4.4 調調 度度 算算 法法本節討論各種常用的進程調度算法和作業調度算法。本節討論各種常用的進程調度算法和作業調度算法。1. 先來先服務（先來先服務（FCFS）調度算法）調度算法將用戶作業和就緒進程按提交順序或變為就緒狀態將用戶作業和就緒進程按提交順序或變為就緒狀態的先后排成隊列，并按照先來先服務的方式進行調的先后排成隊列，并按照先來先服務的方式進行調度處理，是一種最普遍和最簡單的方法。在沒有特度處理，是一種最普遍和最簡單的方法。在沒有特殊理由要優先調度某類作業或進程時，從處理的角殊理由要優先調度某類作業或進程時，從處理的角度來看，度來看，FCFS方式是一種最合適的

46、方法，無論是方式是一種最合適的方法，無論是追加還是取出一個隊列元素在操作上都是最簡單的。追加還是取出一個隊列元素在操作上都是最簡單的。直觀看，該算法在一般意義下是公平的。即每個作直觀看，該算法在一般意義下是公平的。即每個作業或進程都按照它們在隊列中等待時間長短來決定業或進程都按照它們在隊列中等待時間長短來決定它們是否優先享受服務。不過對于那些執行時間較它們是否優先享受服務。不過對于那些執行時間較短的作業或進程來說，如果它們在某些執行時間很短的作業或進程來說，如果它們在某些執行時間很長的作業或進程之后到達，則它們將等待很長時間。長的作業或進程之后到達，則它們將等待很長時間。在實際操作系統中，盡管

47、很少單獨使用在實際操作系統中，盡管很少單獨使用FCFS算法，算法，但和其他一些算法配合起來，但和其他一些算法配合起來，FCFS算法還是使用算法還是使用得相當多的。例如基于優先級的調度算法就是對具得相當多的。例如基于優先級的調度算法就是對具有同樣優先級的作業或進程采用的有同樣優先級的作業或進程采用的FCFS方式。方式。2. 輪轉法（輪轉法（round robin）輪轉法的基本思路是讓每個進程在就緒隊列中的等輪轉法的基本思路是讓每個進程在就緒隊列中的等待時間與享受服務的時間成比例。輪轉法的基本概待時間與享受服務的時間成比例。輪轉法的基本概念是將念是將CPU的處理時間分成固定大小的時間片。如的處理時

48、間分成固定大小的時間片。如果一個進程在被調度選中之后用完了系統規定的時果一個進程在被調度選中之后用完了系統規定的時間片，但未完成要求的任務，則它自行釋放自己所間片，但未完成要求的任務，則它自行釋放自己所占有的占有的CPU而排到就緒隊列的末尾，等待下一次調而排到就緒隊列的末尾，等待下一次調度。同時，進程調度程序又去調度當前就緒隊列中度。同時，進程調度程序又去調度當前就緒隊列中的第一個進程或作業。輪轉法的原理見圖的第一個進程或作業。輪轉法的原理見圖4.4。圖圖4.4 輪轉法調度輪轉法調度顯然，輪轉法只能用來調度分配那些可以搶占的資顯然，輪轉法只能用來調度分配那些可以搶占的資源。將它們隨時剝奪再分配

49、給別的進程。源。將它們隨時剝奪再分配給別的進程。CPU是可是可搶占資源的一種。但如打印機等資源是不可搶占的。搶占資源的一種。但如打印機等資源是不可搶占的。由于作業調度是對除了由于作業調度是對除了CPU之外的所有系統硬件資之外的所有系統硬件資源的分配，其中包含有不可搶占資源，所以作業調源的分配，其中包含有不可搶占資源，所以作業調度不使用輪轉法。度不使用輪轉法。在輪轉法中，時間片長度的選取非常重要。首先，在輪轉法中，時間片長度的選取非常重要。首先，時間片長度的選擇會直接影響系統開銷和響應時間。時間片長度的選擇會直接影響系統開銷和響應時間。如果時間片長度過短，則調度程序剝奪處理機的次如果時間片長度過

50、短，則調度程序剝奪處理機的次數增多。這將使進程上下文切換次數也大大增加，數增多。這將使進程上下文切換次數也大大增加，從而加重系統開銷。反過來，如果時間片長度選擇從而加重系統開銷。反過來，如果時間片長度選擇過長，比方說一個時間片能保證就緒隊列中所需執過長，比方說一個時間片能保證就緒隊列中所需執行時間最長的進程能執行完畢，則輪轉法變成了先行時間最長的進程能執行完畢，則輪轉法變成了先來先服務法。來先服務法。時間片長度的選擇是根據系統對響應時間的要求時間片長度的選擇是根據系統對響應時間的要求R和和就緒隊列中所允許的最大進程數就緒隊列中所允許的最大進程數Nmax確定的。它確定的。它可表示為：可表示為：q

51、=R/Nmax在在q為常數的情況下，如果就緒隊列中的進程數發生為常數的情況下，如果就緒隊列中的進程數發生遠小于遠小于Nmax的變化，則響應時間的變化，則響應時間R看上去會大大看上去會大大減小。但是，就系統開銷來說，由于減小。但是，就系統開銷來說，由于q值固定，從值固定，從而進程上下文切換的時機不變，系統開銷也不變。而進程上下文切換的時機不變，系統開銷也不變。通常，系統開銷也是處理機執行時間的一部分。通常，系統開銷也是處理機執行時間的一部分。CPU的整個執行時間等于各進程執行時間加上系統的整個執行時間等于各進程執行時間加上系統開銷。在進程執行時間大幅度減少的情況下，如果開銷。在進程執行時間大幅度

52、減少的情況下，如果系統開銷也隨之減少的話，系統的響應時間有可能系統開銷也隨之減少的話，系統的響應時間有可能更好一點。例如，在一個用戶進程的情況下，如果更好一點。例如，在一個用戶進程的情況下，如果q 值增大到足夠該進程執行完畢的話，則進程調度值增大到足夠該進程執行完畢的話，則進程調度所引起的系統開銷就沒有了。一種可行的辦法是，所引起的系統開銷就沒有了。一種可行的辦法是，每當一輪調度開始時，系統便根據就緒隊列中已有每當一輪調度開始時，系統便根據就緒隊列中已有進程數目計算一次進程數目計算一次q值，作為新一輪調度的時間片。值，作為新一輪調度的時間片。這種方法得到的時間片隨就緒隊列中的進程數變化。這種方

53、法得到的時間片隨就緒隊列中的進程數變化。3. 多級反饋輪轉法多級反饋輪轉法在輪轉法中，加入到就緒隊列的進程有三種情況，在輪轉法中，加入到就緒隊列的進程有三種情況，一種是分給它的時間片用完，但進程還未完成，回一種是分給它的時間片用完，但進程還未完成，回到就緒隊列的末尾等待下次調度去繼續執行。另一到就緒隊列的末尾等待下次調度去繼續執行。另一種情況是分給該進程的時間片并未用完，只是因為種情況是分給該進程的時間片并未用完，只是因為請求請求IO或由于進程的互斥與同步關系而被阻塞。或由于進程的互斥與同步關系而被阻塞。當阻塞解除之后再回到就緒隊列。再有一種情況就當阻塞解除之后再回到就緒隊列。再有一種情況就是

54、新創建進程進入就緒隊列。如果對這些進程區別是新創建進程進入就緒隊列。如果對這些進程區別對待，給予不同的優先級和時間片，從直觀上看，對待，給予不同的優先級和時間片，從直觀上看，可望進一步改善系統服務質量和效率。例如，可把可望進一步改善系統服務質量和效率。例如，可把就緒隊列按照進程到達就緒隊列的類型和進程被阻就緒隊列按照進程到達就緒隊列的類型和進程被阻塞時的阻塞原因分成不同的就緒隊列，每個隊列按塞時的阻塞原因分成不同的就緒隊列，每個隊列按FCFS原則排列，各隊列之間的進程享有不同的優原則排列，各隊列之間的進程享有不同的優先級，但同一隊列內優先級相同。先級，但同一隊列內優先級相同。這樣，當一個進程在

55、執行完它的時間片之后，或從這樣，當一個進程在執行完它的時間片之后，或從睡眠中被喚醒以及被創建之后，將進入不同的就緒睡眠中被喚醒以及被創建之后，將進入不同的就緒隊列。多級反饋輪轉法與優先級法在原理上的區別隊列。多級反饋輪轉法與優先級法在原理上的區別是，一個進程在它執行結束之前，可能需要反復多是，一個進程在它執行結束之前，可能需要反復多次通過反饋循環執行，而不是優先級法中的一次執次通過反饋循環執行，而不是優先級法中的一次執行。行。4. 優先級法優先級法優先級法可被用作作業或進程的調度策略。首先，優先級法可被用作作業或進程的調度策略。首先，系統或用戶按某種原則為作業或進程指定一個優先系統或用戶按某種

56、原則為作業或進程指定一個優先級來表示該作業或進程所享有的調度優先權。該算級來表示該作業或進程所享有的調度優先權。該算法的核心是確定進程或作業的優先級。法的核心是確定進程或作業的優先級。確定優先級的方法可分為靜態法和動態法。靜態法確定優先級的方法可分為靜態法和動態法。靜態法根據作業或進程的靜態特性，在作業或進程開始執根據作業或進程的靜態特性，在作業或進程開始執行之前就確定它們的優先級，一旦開始執行之后就行之前就確定它們的優先級，一旦開始執行之后就不能改變。動態法則不然，它把作業或進程的靜態不能改變。動態法則不然，它把作業或進程的靜態特性和動態特性結合起來確定作業或進程的優先級，特性和動態特性結合

57、起來確定作業或進程的優先級，隨著作業或進程的執行過程，其優先級不斷變化。隨著作業或進程的執行過程，其優先級不斷變化。靜態優先級靜態優先級作業調度中的靜態優先級大多按以下原則確定：作業調度中的靜態優先級大多按以下原則確定：(1) 由用戶自己根據作業的緊急程度輸入一個適當的由用戶自己根據作業的緊急程度輸入一個適當的優先級。為防止各用戶都將自己的作業冠以高優先優先級。為防止各用戶都將自己的作業冠以高優先級，系統應對高優先級用戶收取較高的費用。級，系統應對高優先級用戶收取較高的費用。(2) 由系統或操作員根據作業類型指定優先級。作業由系統或操作員根據作業類型指定優先級。作業類型一般由用戶約定或由操作員

58、指定。例如：可將類型一般由用戶約定或由操作員指定。例如：可將作業分為：作業分為：IO繁忙的作業，繁忙的作業，CPU繁忙的作業，繁忙的作業，IO與與CPU均衡的作業，均衡的作業，一般作業，等等。一般作業，等等。系統或操作員可以給每類作業指定不同的優先級。系統或操作員可以給每類作業指定不同的優先級。(3) 系統根據作業要求資源情況確定優先級。例如根系統根據作業要求資源情況確定優先級。例如根據估計所需處理機時間、內存量大小、據估計所需處理機時間、內存量大小、IO設備設備類型及數量等，確定作業的優先級。類型及數量等，確定作業的優先級。進程的靜態優先級確定原則可以是：進程的靜態優先級確定原則可以是：(1

59、) 按進程的類型給予不同的優先級。例如，在有些按進程的類型給予不同的優先級。例如，在有些系統中，進程被劃分為系統進程和用戶進程。系統系統中，進程被劃分為系統進程和用戶進程。系統進程享有比用戶進程高的優先級。對于用戶進程來進程享有比用戶進程高的優先級。對于用戶進程來說，則可以分為：說，則可以分為：IO繁忙的進程，繁忙的進程，CPU繁忙的進程，繁忙的進程，IO與與CPU均衡的進程，均衡的進程，其他進程。其他進程。對系統進程，也可以根據其所要完成的功能劃分為對系統進程，也可以根據其所要完成的功能劃分為不同的類型，例如，調度進程、不同的類型，例如，調度進程、IO進程、中斷進程、中斷處理進程、存儲管理進

60、程等。這些進程還可進一步處理進程、存儲管理進程等。這些進程還可進一步劃分為不同類型和賦予不同的優先級。例如，在操劃分為不同類型和賦予不同的優先級。例如，在操作系統中，對于鍵盤中斷的處理優先級和對于電源作系統中，對于鍵盤中斷的處理優先級和對于電源掉電中斷的處理優先級是不相同的。掉電中斷的處理優先級是不相同的。(2) 將作業的靜態優先級作為它所屬進程的優先級。將作業的靜態優先級作為它所屬進程的優先級。動態優先級動態優先級基于靜態優先級的調度算法實現簡單，系統開銷小，基于靜態優先級的調度算法實現簡單，系統開銷小，但由于靜態優先級一旦確定之后，直到執行結束為但由于靜態優先級一旦確定之后，直到執行結束為