1、1 在多道程序環境中，主存中有多個進程，在多道程序環境中，主存中有多個進程，其數目往往多于處理機數目，這就要求其數目往往多于處理機數目，這就要求系統能按某種算法，動態地把處理機分系統能按某種算法，動態地把處理機分配給就緒隊列中的一個進程，使之執行，配給就緒隊列中的一個進程，使之執行，分配處理機的任務是由處理機調度程序分配處理機的任務是由處理機調度程序完成的。完成的。 由于處理機是重要的資源，提高處理機由于處理機是重要的資源，提高處理機的利用率及改善系統的性能，在很大程的利用率及改善系統的性能，在很大程度上取決于處理機調度性能的好壞。度上取決于處理機調度性能的好壞。2處理機調度的層次處理機調度的

2、層次進程調度進程調度3高級調度高級調度低級調度低級調度中級調度中級調度41、高級調度、高級調度 高級調度又稱為作業調度，主要功能是根據某高級調度又稱為作業調度，主要功能是根據某種算法，把外存上處于后備隊列中的那些作業種算法，把外存上處于后備隊列中的那些作業調入內存，調度的對象是作業。調入內存，調度的對象是作業。 作業：作業是比程序更為廣泛的概念，它不僅作業：作業是比程序更為廣泛的概念，它不僅包含了通常的程序和數據，還配有一個作業說包含了通常的程序和數據，還配有一個作業說明書，系統根據作業說明書來對程序的運行進明書，系統根據作業說明書來對程序的運行進行控制。行控制。 在批處理系統中，是以作業為基

3、本單位從外存在批處理系統中，是以作業為基本單位從外存調入內存的。調入內存的。51、高級調度、高級調度 在每次執行作業調度時，都須做出以下在每次執行作業調度時，都須做出以下兩個決定。兩個決定。 1) 接納多少個作業：即允許多少個作業接納多少個作業：即允許多少個作業同時在內存中運行。當內存中同時運行同時在內存中運行。當內存中同時運行的作業數目太多時，可能會影響到系統的作業數目太多時，可能會影響到系統的服務質量。的服務質量。 2) 接納哪些作業：應將哪些作業從外存接納哪些作業：應將哪些作業從外存調入內存，這取決于所采用的調度算法。調入內存，這取決于所采用的調度算法。 62、低級調度、低級調度 低級調

4、度也稱為進程調度。低級調度也稱為進程調度。 低級調度用于決定就緒隊列中的哪個進低級調度用于決定就緒隊列中的哪個進程獲得處理機。程獲得處理機。73、中級調度、中級調度 中級調度又稱中程調度。中級調度又稱中程調度。 引入中級調度的主要目的，是為了提高內存利引入中級調度的主要目的，是為了提高內存利用率和系統吞吐量。用率和系統吞吐量。 為此，應使那些暫時不為此，應使那些暫時不能運行的進程不再占用寶貴的內存資源，而將能運行的進程不再占用寶貴的內存資源，而將它們調至外存上去等待，把此時的進程狀態稱它們調至外存上去等待，把此時的進程狀態稱為就緒駐外存狀態或掛起狀態。當這些進程重為就緒駐外存狀態或掛起狀態。當

5、這些進程重又具備運行條件、且內存又稍有空閑時，由中又具備運行條件、且內存又稍有空閑時，由中級調度來決定把外存上的哪些又具備運行條件級調度來決定把外存上的哪些又具備運行條件的就緒進程，重新調入內存，并修改其狀態為的就緒進程，重新調入內存，并修改其狀態為就緒狀態，掛在就緒隊列上等待進程調度。就緒狀態，掛在就緒隊列上等待進程調度。 84、調度隊列模型、調度隊列模型 僅有進程調度的調度隊列模型僅有進程調度的調度隊列模型 具有高級和低級調度的調度隊列模型具有高級和低級調度的調度隊列模型 同時具有三級調度的調度隊列模型同時具有三級調度的調度隊列模型9（1）僅有進程調度的調度隊列模型）僅有進程調度的調度隊列

6、模型10（2）具有高級和低級調度的調度隊列模型）具有高級和低級調度的調度隊列模型就就 緒緒 隊隊 列列 進程調度進程調度CPUCPU進程完成進程完成 等待事件等待事件1 1 作業作業調度調度事件事件1 1出現出現時間片完時間片完 等待事件等待事件2 2事件事件2 2出現出現 等待事件等待事件n n事件事件n n出現出現后后 備備 隊隊 列列 11（3）同時具有三級調度的調度隊列模型）同時具有三級調度的調度隊列模型12v進程調度需要解決三個主要問題：進程調度需要解決三個主要問題：v（1）什么時候分配處理機，即需要確定）什么時候分配處理機，即需要確定處理機調度時機；處理機調度時機； v（2）按什么

7、原則分配處理機，即需要確）按什么原則分配處理機，即需要確定處理機調度算法；定處理機調度算法；v（3）如何分配處理機，即需要給出處理）如何分配處理機，即需要給出處理機調度過程。機調度過程。13進程調度進程調度v進程調度的任務是控制協調進程對進程調度的任務是控制協調進程對CPU的競爭，即按一定的調度算法從就緒隊的競爭，即按一定的調度算法從就緒隊列中選中一個進程，把列中選中一個進程，把CPU的使用權交的使用權交給被選中的進程。給被選中的進程。14 在單處理機多道程序設計系統中，進程在單處理機多道程序設計系統中，進程被作為占用處理機運行的執行單位。由被作為占用處理機運行的執行單位。由于處理機是最重要的

8、計算機資源，所以于處理機是最重要的計算機資源，所以合理、有效地選擇進程占有處理機是進合理、有效地選擇進程占有處理機是進程調度的重要任務。提高處理機的利用程調度的重要任務。提高處理機的利用率及改善系統響應時間、吞吐率，在很率及改善系統響應時間、吞吐率，在很大程度上取決于進程調度性能的好壞。大程度上取決于進程調度性能的好壞。15調度目標：調度目標： 公平保證每個進程得到合理的公平保證每個進程得到合理的CPU 時間時間 高效使高效使CPU 保持忙碌狀態即總是有進程在保持忙碌狀態即總是有進程在CPU 上運行上運行 響應時間使交互用戶的響應時間盡可能短響應時間使交互用戶的響應時間盡可能短 周轉時間使批處

9、理用戶等待輸出的時間盡可能周轉時間使批處理用戶等待輸出的時間盡可能短短 吞吐量使單位時間內處理的進程盡可能多吞吐量使單位時間內處理的進程盡可能多 由于這些目標的相互沖突，任一調度算法要想由于這些目標的相互沖突，任一調度算法要想同時滿足上述目標是不可能的。同時滿足上述目標是不可能的。16不同系統調度目標也不同：不同系統調度目標也不同： 在多道批處理系統中，為了提高處理機的效率在多道批處理系統中，為了提高處理機的效率和吞吐量，當調度一批作業運行時，盡可能使和吞吐量，當調度一批作業運行時，盡可能使作業搭配合理，充分利用資源。作業搭配合理，充分利用資源。 在分時系統中，由于用戶使用交互式會話的工在分時

10、系統中，由于用戶使用交互式會話的工作方式，系統必須要有較快的響應時間，使得作方式，系統必須要有較快的響應時間，使得每個用戶都感到如同只有他自己一人在使用計每個用戶都感到如同只有他自己一人在使用計算機，因此考慮的是公平性。算機，因此考慮的是公平性。 在實時系統中，首先要保證截止時間，即某任在實時系統中，首先要保證截止時間，即某任務必須開始執行的最遲時間，或必須完成的最務必須開始執行的最遲時間，或必須完成的最遲時間。遲時間。17調度性能評價調度性能評價 定性衡量：調度的可靠性、簡潔性定性衡量：調度的可靠性、簡潔性 可靠性：一次進程調度是否可能引起數據結構的破可靠性：一次進程調度是否可能引起數據結構

11、的破壞，這要求對調度時機的選擇和保存壞，這要求對調度時機的選擇和保存CPU現場十分現場十分謹慎。謹慎。 簡潔性：調度會涉及到多個進程和上下文切換，如簡潔性：調度會涉及到多個進程和上下文切換，如果調度程序過于繁瑣和復雜，會耗去較大的系統開果調度程序過于繁瑣和復雜，會耗去較大的系統開銷。銷。 定量評價：定量評價：CPU的利用率評價、進程在就緒隊的利用率評價、進程在就緒隊列中的等待時間與執行時間之比等。列中的等待時間與執行時間之比等。18 衡量調度策略的最常用的幾個指標是：衡量調度策略的最常用的幾個指標是： 周轉時間周轉時間：指將一個作業提交給計算機系統開：指將一個作業提交給計算機系統開始，到作業完

12、成為止的這段時間間隔。始，到作業完成為止的這段時間間隔。 吞吐量吞吐量：指在單位時間內，一個計算機系統所：指在單位時間內，一個計算機系統所完成的作業數。完成的作業數。 響應時間響應時間：指從用戶向計算機提交一個請求開：指從用戶向計算機提交一個請求開始，直至系統首次產生響應為止的時間。始，直至系統首次產生響應為止的時間。191. 周轉時間：周轉時間：作業作業i的周轉時間的周轉時間Ti為為Ti=Tei-Tsi其中其中Tei為作業為作業i的完成時間，的完成時間，Tsi為作業的提交時間。為作業的提交時間。對于被測定作業流所含有的對于被測定作業流所含有的n（n=1）個作業來說，）個作業來說，其平均周轉時

13、間為：其平均周轉時間為：一個作業的周轉時間說明了該作業在系統內停留的一個作業的周轉時間說明了該作業在系統內停留的時間，包含兩部分：等待時間；執行時間，即：時間，包含兩部分：等待時間；執行時間，即：Ti=TwiTri這里，這里，Twi主要指作業主要指作業i等待處理機的時間。等待處理機的時間。nii = 11T =Tn202. 帶權周轉時間帶權周轉時間作業的周轉時間包含了兩個部分，即等待時間和執作業的周轉時間包含了兩個部分，即等待時間和執行時間。為了更進一步反映調度性能，使用帶權周行時間。為了更進一步反映調度性能，使用帶權周轉時間的概念。帶權周轉時間是作業周轉時間與作轉時間的概念。帶權周轉時間是作

14、業周轉時間與作業執行時間的比：業執行時間的比：Wi=Ti/Tri對于被測定作業流所含有的幾個作業來說，其平均對于被測定作業流所含有的幾個作業來說，其平均帶權周轉時間為：帶權周轉時間為：對于分時系統，除了要保證系統吞吐量大、資源利對于分時系統，除了要保證系統吞吐量大、資源利用率高之外，還應保證有用戶能夠容忍的響應時間。用率高之外，還應保證有用戶能夠容忍的響應時間。因此，在分時系統中，僅僅用周轉時間或帶權周轉因此，在分時系統中，僅僅用周轉時間或帶權周轉時間來衡量調度性能是不夠的。時間來衡量調度性能是不夠的。nii=11W =Wn21對于分時系統和實時系統來說，對于分時系統和實時系統來說， 僅用周轉

15、時間或帶權周轉時間衡量調度僅用周轉時間或帶權周轉時間衡量調度性能是不夠的，需要加平均響應時間作性能是不夠的，需要加平均響應時間作為衡量調度策略優劣的標準。為衡量調度策略優劣的標準。 響應時間：指從用戶向計算機提交一個響應時間：指從用戶向計算機提交一個請求開始，直至系統首次產生響應為止請求開始，直至系統首次產生響應為止的時間。的時間。22評價指標：評價指標： 批處理系統來說，主要的性能指標是批處理系統來說，主要的性能指標是 周轉時間，平均周轉時間（等待時間、平均周轉時間，平均周轉時間（等待時間、平均等待時間）等待時間） 帶權周轉時間，平均帶權周轉時間帶權周轉時間，平均帶權周轉時間 分時系統來說，

16、主要的性能指標是分時系統來說，主要的性能指標是 響應時間，平均響應時間響應時間，平均響應時間 實時系統來說，主要的性能指標是實時系統來說，主要的性能指標是 截止時間截止時間23進程調度進程調度 何時調度？何時調度？ 選擇誰運行選擇誰運行調度算法？調度算法？ 調度時需要做什么？調度時需要做什么？24一、何時調度一、何時調度進程調度的原因進程調度的原因 (1) 正在執行的進程執行完畢。正在執行的進程執行完畢。 (2) 執行中進程自己調用阻塞原語將自執行中進程自己調用阻塞原語將自己阻塞起來進入睡眠等待狀態。己阻塞起來進入睡眠等待狀態。 (3) 執行中進程調用了執行中進程調用了P原語操作，從而原語操作

17、，從而因資源不足而被阻塞；或調用了因資源不足而被阻塞；或調用了V原語操原語操作激活了等待資源的進程隊列進入就緒作激活了等待資源的進程隊列進入就緒隊列，并請求重新調度。隊列，并請求重新調度。 (4) 執行中進程提出執行中進程提出IO請求后被阻塞。請求后被阻塞。25以上都是在以上都是在CPU執行不可剝奪方式下所引執行不可剝奪方式下所引起進程調度的原因。在起進程調度的原因。在CPU執行方式是執行方式是可剝奪時，還有：可剝奪時，還有：(5) 在分時系統中時間片已經用完。在分時系統中時間片已經用完。(6) 就緒隊列中的某進程的優先級變得高就緒隊列中的某進程的優先級變得高于當前執行進程的優先級，從而也將引

18、于當前執行進程的優先級，從而也將引發進程調度。發進程調度。26二、調度時需要做什么二、調度時需要做什么進程調度的功能進程調度的功能 1保存保存“下降下降”進程現場進程現場 2選擇將要運行的進程選擇將要運行的進程“上升上升”進進程程 3恢復恢復“上升上升”進程的現場進程的現場27三、調度算法三、調度算法 v引入多道程序系統的直接目的就是想讓處理機引入多道程序系統的直接目的就是想讓處理機“忙忙”，一，一直以來處理機都是計算機系統中的瓶頸資源之一，特別是直以來處理機都是計算機系統中的瓶頸資源之一，特別是在單處理機系統中，處于就緒狀態的多個進程競爭使用一在單處理機系統中，處于就緒狀態的多個進程競爭使用

19、一臺處理機，所以當處理機空閑時，系統需要從多個就緒進臺處理機，所以當處理機空閑時，系統需要從多個就緒進程中挑選一個使其投入運行。選擇哪一個呢？這需要按某程中挑選一個使其投入運行。選擇哪一個呢？這需要按某一種算法。一種算法。調度算法的實質就是一種資源分配調度算法的實質就是一種資源分配。 v從資源的角度來看，該算法確定了處理機的分配策略，故從資源的角度來看，該算法確定了處理機的分配策略，故稱其為處理機調度算法；稱其為處理機調度算法；v而從資源使用者的角度看，該算法確定了進程運行的次序，而從資源使用者的角度看，該算法確定了進程運行的次序，故也稱進程調度算法。故也稱進程調度算法。 28不可搶占方式：在

20、這種方式下，一旦把處理機分不可搶占方式：在這種方式下，一旦把處理機分配給某進程后，便讓他一直運行下去，直到進程配給某進程后，便讓他一直運行下去，直到進程完成或發生某事件而阻塞時，才把處理機分配給完成或發生某事件而阻塞時，才把處理機分配給另一進程。但存在明顯的缺點：如當一個緊急任另一進程。但存在明顯的缺點：如當一個緊急任務到達時，不能立即投入運行，實時性差。務到達時，不能立即投入運行，實時性差。進程調度有兩種基本方式：進程調度有兩種基本方式： 不可搶占方式不可搶占方式與可搶占方式可搶占方式 29 可搶占方式：在這種方式下，某個進程正在運可搶占方式：在這種方式下，某個進程正在運行時可以被系統以某種

21、原則搶占已分配給它的行時可以被系統以某種原則搶占已分配給它的處理機，將處理機分配給其他進程。搶占原則處理機，將處理機分配給其他進程。搶占原則可以是優先權原則，即高優先級進程可以剝奪可以是優先權原則，即高優先級進程可以剝奪低優先級的進程運行，也可以是時間片原則，低優先級的進程運行，也可以是時間片原則，在運行進程的時間片用完后被剝奪處理機，重在運行進程的時間片用完后被剝奪處理機，重新參與調度。新參與調度。30 基本的處理機調度算法有先來先服務基本的處理機調度算法有先來先服務法、優先級法和時間片輪轉法等，現在也有法、優先級法和時間片輪轉法等，現在也有些操作系統使用綜合性的調度算法，比如多些操作系統使

22、用綜合性的調度算法，比如多級反饋隊列調度算法等。級反饋隊列調度算法等。 311先來先服務調度算法（先來先服務調度算法（First Come First Served，FCFS） 該算法按照進程進入就緒隊列的先后順序選擇最先進該算法按照進程進入就緒隊列的先后順序選擇最先進入該隊列的進程，把處理機分配給它，使之投入運行。入該隊列的進程，把處理機分配給它，使之投入運行。一旦一個進程占有了處理機就一直運行下去，直到該一旦一個進程占有了處理機就一直運行下去，直到該進程完成或因等待某事件而不能繼續運行才釋放處理進程完成或因等待某事件而不能繼續運行才釋放處理機。機。DCBACPU完成32在單道環境下，某批處

23、理有四道作業，已知他們的進入在單道環境下，某批處理有四道作業，已知他們的進入系統的時刻、估計運算時間如下：系統的時刻、估計運算時間如下：進程進程到達時刻到達時刻執行時間執行時間開始時刻開始時刻完成時刻完成時刻 周轉時間周轉時間 帶權周轉帶權周轉ABCD0123110011000110110211011022021100100199111001.99短作業短作業C的帶權周轉時間高達的帶權周轉時間高達100。長作業長作業D的帶權周轉時間僅為的帶權周轉時間僅為1.99 33 這是一種不可搶占方式的調度算法，優點這是一種不可搶占方式的調度算法，優點是實現簡單，缺點是后來的進程等待是實現簡單，缺點是后來

24、的進程等待CPUCPU的時間的時間較長。即有利于長進程，不利于短進程。較長。即有利于長進程，不利于短進程。 在當今系統中，先進先出很少作為調度模在當今系統中，先進先出很少作為調度模式，而是常常嵌套在其它的調度模式中。式，而是常常嵌套在其它的調度模式中。 例如，許多調度模式根據優先級將處理機例如，許多調度模式根據優先級將處理機分配給進程，但具有相同優先級的進程卻按先分配給進程，但具有相同優先級的進程卻按先進先出進行分配。進先出進行分配。342.2.最短進程優先法（最短進程優先法（Shortest Process/Job Shortest Process/Job FirstFirst，SPF/SJ

25、FSPF/SJF）SPF/SJF:SPF/SJF:從就緒隊列中選擇估計運行時間最短的進程，從就緒隊列中選擇估計運行時間最短的進程，先將處理機分配給它，使它立即執行。先將處理機分配給它，使它立即執行。非搶占式。非搶占式。優點：減少了在就緒隊列中等待的進程數，同時也降低優點：減少了在就緒隊列中等待的進程數，同時也降低了進程的平均等待時間，提高了系統的吞吐量。了進程的平均等待時間，提高了系統的吞吐量。缺點：沒有考慮到某些進程的緊迫程度。缺點：沒有考慮到某些進程的緊迫程度。 用戶作出的估計時間并不準確，帶有很大的主觀性。用戶作出的估計時間并不準確，帶有很大的主觀性。 35例：例： 假設有假設有5道作業

26、，它們的提交時間及運行時間由下道作業，它們的提交時間及運行時間由下表給出：表給出：作業作業 提交時間（時）提交時間（時） 運行時間（小時）運行時間（小時）1 9 2 2 925 13 1005 0754 1225 055 125 025若采用若采用FCFS和和SJF兩種調度算法，指出作業被調度兩種調度算法，指出作業被調度順序及平均周轉時間。順序及平均周轉時間。 363.3.最高響應比優先算法（最高響應比優先算法（ Highest Highest Response Ratio NextResponse Ratio Next， HRNHRN） 是對是對FCFSFCFS方式和方式和SJFSJF方式的

27、一種綜合平衡方式的一種綜合平衡響應比。響應比。 FCFSFCFS只考慮了每個作業的等待時間而未只考慮了每個作業的等待時間而未考慮執行時間的長短，而考慮執行時間的長短，而SJFSJF只考慮執行只考慮執行時間而未考慮等待時間的長短。時間而未考慮等待時間的長短。 HRNHRN算法同時考慮每個作業的等待時間長算法同時考慮每個作業的等待時間長短和估計需要的執行時間長短，從中選短和估計需要的執行時間長短，從中選出響應比最高的作業投入執行。出響應比最高的作業投入執行。373.3.最高響應比優先算法最高響應比優先算法 響應比：響應比： R R( (作業等待時間需運行時間作業等待時間需運行時間)/ )/ 需運行

28、時間需運行時間 1 1已等待時間已等待時間 / / 需運行時間需運行時間 1 1W/TW/T由于由于R R與要求運行時間成反比，故對短作業是與要求運行時間成反比，故對短作業是有利的，另一方面，因有利的，另一方面，因R R與等待時間成正比，與等待時間成正比，故長作業隨著其等待時間的增長，也可獲的較故長作業隨著其等待時間的增長，也可獲的較高的響應比。這就克服了短作業優先數法的缺高的響應比。這就克服了短作業優先數法的缺點，既照顧了先來者，又優待了短作業，是上點，既照顧了先來者，又優待了短作業，是上述兩種算法的一種較好的折中。述兩種算法的一種較好的折中。384優先級調度算法（優先級調度算法（Prior

29、ity DrivenPriority Driven，PDPD） 總是選擇具有總是選擇具有最高優先級最高優先級的進程首先使用處理機的進程首先使用處理機。在這種算在這種算法中，首先考慮的問題是如何確定進程的優先數。法中，首先考慮的問題是如何確定進程的優先數。 分為分為： 靜態優先級靜態優先級：在創建進程的時候便確定的，且在進在創建進程的時候便確定的，且在進程的運行期間保持不變。（程的運行期間保持不變。（簡單易行，系統開銷小，簡單易行，系統開銷小，但不夠精確，很可能出現優先權低的進程長期不被但不夠精確，很可能出現優先權低的進程長期不被調度的情況。所以只在要求不太高的系統中，才使調度的情況。所以只在要

30、求不太高的系統中，才使用靜態優先級用靜態優先級） 動態優先級動態優先級：在創建進程時所賦予的優先級，可以在創建進程時所賦予的優先級，可以隨進程的推進而改變，以便獲得更好的調度性能隨進程的推進而改變，以便獲得更好的調度性能 39這是一種這是一種可搶占方式可搶占方式的調度算法，可防止一個長進程長的調度算法，可防止一個長進程長期的壟斷處理機。期的壟斷處理機。 若所有的進程具有相同的優先級初值，若所有的進程具有相同的優先級初值，則按照則按照FCFS算法，最先進入就緒隊列的算法，最先進入就緒隊列的進程最先獲得處理機。進程最先獲得處理機。40進程的靜態優先級確定原則可以是：進程的靜態優先級確定原則可以是：

31、(1) 系統根據進程要求資源情況確定優先系統根據進程要求資源情況確定優先級。例如根據估計所需處理機時間、內級。例如根據估計所需處理機時間、內存量大小、存量大小、IO設備類型及數量等，確設備類型及數量等，確定進程的優先級。定進程的優先級。(2) 按進程的類型給予不同的優先級。例按進程的類型給予不同的優先級。例如，在有些系統中，進程被劃分為系統如，在有些系統中，進程被劃分為系統進程和用戶進程。系統進程享有比用戶進程和用戶進程。系統進程享有比用戶進程高的優先級。進程高的優先級。41進程的動態優先級一般根據以下原則確定：進程的動態優先級一般根據以下原則確定：(1) 根據進程占有根據進程占有CPU時間的

32、長短來決定。一個時間的長短來決定。一個進程占有處理機的時間愈長，則在被阻塞之后進程占有處理機的時間愈長，則在被阻塞之后再次獲得調度的優先級就越低，反之，其獲得再次獲得調度的優先級就越低，反之，其獲得調度的可能性就會越大。調度的可能性就會越大。(2) 根據就緒進程等待根據就緒進程等待CPU的時間長短來決定。的時間長短來決定。一個就緒進程在就緒隊列中等待的時間越長，一個就緒進程在就緒隊列中等待的時間越長，則它獲得調度選中的優先級就越高。則它獲得調度選中的優先級就越高。由于動態優先級隨時間的推移而變化，系統要經由于動態優先級隨時間的推移而變化，系統要經常計算各進程的優先級，因此，系統要為此付常計算各

33、進程的優先級，因此，系統要為此付出一定的開銷。出一定的開銷。42例：例： 有有5個進程個進程P1、P2、P3、P4、P5，它們同時依次，它們同時依次進入就緒隊列，它們的優先數和需要的處理機時間如下進入就緒隊列，它們的優先數和需要的處理機時間如下（優先數越大代表優先級越高）（優先數越大代表優先級越高） ： 進程進程 處理機時間處理機時間 優先數優先數 P1 10 3P1 10 3 P2 1 1P2 1 1 P3 2 3P3 2 3 P4 1 4P4 1 4 P5 5 2P5 5 2 43忽略進程調度所花的時間，要求：忽略進程調度所花的時間，要求： （1 1）分別寫出采用先來先服務調度算法和靜態優

34、）分別寫出采用先來先服務調度算法和靜態優先級調度算法中進程的執行次序；先級調度算法中進程的執行次序； （2 2）分別計算各進程在就緒隊列中的等待時間和）分別計算各進程在就緒隊列中的等待時間和平均等待時間。平均等待時間。 解：（解：（1 1）采用先來先服務調度算法時各進程的執）采用先來先服務調度算法時各進程的執行次序為：行次序為：P1P1P2P2P3P3P4P4P5P5。 采用靜態優先級調度算法時各進程的執行次序為：采用靜態優先級調度算法時各進程的執行次序為： P4P1P3P5P2。 44（2 2）FCFSFCFS中，平均等待時間（中，平均等待時間（0+10+11+13+140+10+11+13

35、+14）/5/59.69.6；靜態優先級法中，平均等待時間（靜態優先級法中，平均等待時間（1+18+11+0+131+18+11+0+13）/5/58.68.6進程進程 處理機時間處理機時間 FCFSFCFS等待時間等待時間 靜態優先級法等待時間靜態優先級法等待時間 P1 10 0 1P1 10 0 1 P2 1 10 18P2 1 10 18 P3 2 11 11P3 2 11 11 P4 1 13 0P4 1 13 0 P5 5 14 13 P5 5 14 13 455時間片輪轉調度算法時間片輪轉調度算法Round-Robin (RR) 基本思想基本思想：系統把所有的就緒進程按系統把所有的

36、就緒進程按FCFS原則排成一個原則排成一個隊列，且規定一個時間片作為進程每次使用處理機的最隊列，且規定一個時間片作為進程每次使用處理機的最長時間單位，按時間片把處理機輪流分配給當前位于就長時間單位，按時間片把處理機輪流分配給當前位于就緒隊列隊首的進程使用，緒隊列隊首的進程使用，當該進程的時間片用完以后，當該進程的時間片用完以后，系統產生時鐘中斷，剝奪該進程的執行，將它送到就緒系統產生時鐘中斷，剝奪該進程的執行，將它送到就緒隊列隊尾，等待下一輪次的調度。隊列隊尾，等待下一輪次的調度。同時處理機調度程序同時處理機調度程序又去調度當前就緒隊列的又去調度當前就緒隊列的隊首進程隊首進程，也讓它運行給定的

37、也讓它運行給定的時間片，如此循環往復。時間片，如此循環往復。46FCB A .CPU完成 A B C時間片輪轉算法圖示 w該算法適合分時系統使用。該算法適合分時系統使用。47時間片選擇時間片選擇 在輪轉法中，時間片長度的選取非常重要。首在輪轉法中，時間片長度的選取非常重要。首先，時間片長度的選擇會直接影響系統開銷和先，時間片長度的選擇會直接影響系統開銷和響應時間。如果時間片長度過短，則調度程序響應時間。如果時間片長度過短，則調度程序剝奪處理機的次數增多。這將使進程上下文切剝奪處理機的次數增多。這將使進程上下文切換次數也大大增加，從而加重系統開銷。反過換次數也大大增加，從而加重系統開銷。反過來，

38、如果時間片長度選擇過長，比方說一個時來，如果時間片長度選擇過長，比方說一個時間片能保證就緒隊列中所需執行時間最長的進間片能保證就緒隊列中所需執行時間最長的進程能執行完畢，則輪轉法變成了先來先服務法。程能執行完畢，則輪轉法變成了先來先服務法。48 最佳時間片的確定最佳時間片的確定 這個最佳的時間片值是多少呢？顯然，它將隨這個最佳的時間片值是多少呢？顯然，它將隨系統而異。隨負載而異，同時也隨進程而異。系統而異。隨負載而異，同時也隨進程而異。 時間片的選取是實現各種調度算法的關鍵之處，時間片的選取是實現各種調度算法的關鍵之處，而時間片的選定通常應考慮終端數目，處理機能力、而時間片的選定通常應考慮終端

39、數目，處理機能力、各終端任務的急迫程度、外存傳輸速度等方面的因各終端任務的急迫程度、外存傳輸速度等方面的因素。素。49例：例： 有有5個進程個進程P1、P2、P3、P4、P5，它們同時依次，它們同時依次進入就緒隊列，請寫出使用輪轉法調度時的調度次序，進入就緒隊列，請寫出使用輪轉法調度時的調度次序，各進程的周轉時間和等待時間，其中時間片為各進程的周轉時間和等待時間，其中時間片為2 2： 進程進程 處理機時間處理機時間 P1 10P1 10 P2 1P2 1 P3 2 P3 2 P4 1P4 1 P5 5P5 550RR算法算法 每個進程被分配一個時間段，稱作它的每個進程被分配一個時間段，稱作它的

40、時間片，即該進程允許運行的時間。如時間片，即該進程允許運行的時間。如果在時間片結束時進程還在運行，則果在時間片結束時進程還在運行，則CPU將被剝奪并分配給另一個進程。如將被剝奪并分配給另一個進程。如果進程在時間片結束前阻塞或結束，則果進程在時間片結束前阻塞或結束，則CPU當即進行切換。當即進行切換。 516多級反饋隊列調度算法多級反饋隊列調度算法 以上介紹的算法，都存在一定的局限性。以上介紹的算法，都存在一定的局限性。 現在主流的操作系統，如現在主流的操作系統，如UNIX、Windows NT、Linux等，都使用一種綜合性的調度算等，都使用一種綜合性的調度算法法多級反饋隊列調度算法。該算法綜

41、合了多級反饋隊列調度算法。該算法綜合了上述算法以及多隊列調度算法的思想和優點，上述算法以及多隊列調度算法的思想和優點，總體調度性能優越，但其實現也比較復雜。總體調度性能優越，但其實現也比較復雜。 52算法的基本思想（實施過程）是算法的基本思想（實施過程）是： 首先首先：系統按進程優先級設置了多級（比如系統按進程優先級設置了多級（比如n級，級，n2）就）就緒進程隊列，從第一級隊列到最后一級隊列，優先級越來越緒進程隊列，從第一級隊列到最后一級隊列，優先級越來越低。低。其次其次：每一級就緒隊列對應一個不同的時間片。優先級越高：每一級就緒隊列對應一個不同的時間片。優先級越高的隊列，進程的時間片越小。的

42、隊列，進程的時間片越小。再次再次：當一個新進程進入內存后，首先被放到第一級隊列的當一個新進程進入內存后，首先被放到第一級隊列的隊尾。按照隊尾。按照FCFS原則排隊等待調度。當輪到該進程執行時，原則排隊等待調度。當輪到該進程執行時，如能在時間片內完成，便可準備撤離系統；如果在時間片內如能在時間片內完成，便可準備撤離系統；如果在時間片內未完成，調度程序便將該進程轉入第二隊列的末尾，再依次未完成，調度程序便將該進程轉入第二隊列的末尾，再依次按照按照FCFS原則等待調度。原則等待調度。53最后最后：僅當第一級隊列為空時，才調度第二級隊列中僅當第一級隊列為空時，才調度第二級隊列中的進程；如此下去，僅當前

43、面的的進程；如此下去，僅當前面的n-1級隊列全部為空級隊列全部為空時，才去調度最后第時，才去調度最后第n級隊列中的進程。級隊列中的進程。 如果處理機正在第如果處理機正在第I隊列中為某進程服務時，又有新的隊列中為某進程服務時，又有新的進程進入優先級高的隊列（第進程進入優先級高的隊列（第1I-1中任何一隊列），中任何一隊列），則系統搶占正在運行的進程的處理機，由調度程序把則系統搶占正在運行的進程的處理機，由調度程序把正在運行的進程放回到剛才所在第正在運行的進程放回到剛才所在第I隊列的隊尾，重新隊列的隊尾，重新進行處理機調度。進行處理機調度。 54實時系統調度方法實時系統調度方法一、實時系統的特點：

44、一、實時系統的特點：實時系統與其他系統的最大區別在于，其處理和控實時系統與其他系統的最大區別在于，其處理和控制的正確性不僅僅取決于計算的邏輯結果，而且取制的正確性不僅僅取決于計算的邏輯結果，而且取決于計算和處理結果產生的時間。決于計算和處理結果產生的時間。實時系統中處理的外部事件可分為硬實時任務和軟實時系統中處理的外部事件可分為硬實時任務和軟實時任務。硬實時任務要求系統必須完全滿足任務實時任務。硬實時任務要求系統必須完全滿足任務的時限要求。軟實時任務則允許系統對任務的時限的時限要求。軟實時任務則允許系統對任務的時限要求有一定的延遲，其時限要求只是一個相對條件。要求有一定的延遲，其時限要求只是一

45、個相對條件。55一般來說，實時操作系統具有以下特點：一般來說，實時操作系統具有以下特點：(1) 有限等待時間有限等待時間(2) 有限響應時間有限響應時間(3) 可靠性高可靠性高(4) 系統出錯處理能力強系統出錯處理能力強56上述特性要求實時操作系統具有下述能力：上述特性要求實時操作系統具有下述能力：(1) 很快的進程切換速度很快的進程切換速度(2) 快速的外部中斷響應能力快速的外部中斷響應能力(3) 基于優先級的搶先式調度策略基于優先級的搶先式調度策略57二、實時調度算法的分類二、實時調度算法的分類(1) 靜態表格驅動靜態表格驅動Time Driven(TD算法算法)(2) 頻率單調調度算法頻

46、率單調調度算法Rate Monotonic（RM算法）算法）(3) 最早時間限優先調度算法最早時間限優先調度算法Early Deadline First （EDF算法）算法）58三、最早時間限優先調度算法與頻率單調調度算法三、最早時間限優先調度算法與頻率單調調度算法最早時間限優先調度算法是一種以滿足用戶要求的最早時間限優先調度算法是一種以滿足用戶要求的時限為調度原則的算法。時限為調度原則的算法。最早時間限優先調度算法最早時間限優先調度算法的基本思想是：按用戶的的基本思想是：按用戶的時限要求順序設置優先級，優先級高者占據處理機，時限要求順序設置優先級，優先級高者占據處理機，也就是說，時限要求最近

47、的任務優先占有處理機。也就是說，時限要求最近的任務優先占有處理機。59例子：設實時系統從兩個不同的數據源例子：設實時系統從兩個不同的數據源DA和和DB周期周期性地收集數據并進行處理，其中性地收集數據并進行處理，其中DA的時限要求以的時限要求以30 ms為周期，為周期，DB的時限要求以的時限要求以75 ms為周期。設為周期。設DA所所需處理時限為需處理時限為15 ms，DB所需處理時限為所需處理時限為38 ms。60圖4.11 周期性任務的預計發生、執行與結束時限61在開始時，進程在開始時，進程DA（1）和）和DB（1）的結束時限比）的結束時限比較結果，較結果，DA（1）的結束時限最近，從而調度

48、進程）的結束時限最近，從而調度進程DA（1）執行。）執行。DA（1）的實際結束時間為）的實際結束時間為15，小，小于于30的時限要求。緊接著，進程的時限要求。緊接著，進程DB（1）被調度執）被調度執行。在執行到時間為行。在執行到時間為30 ms時，進程時，進程DA（2）進入）進入就緒狀態。由于就緒狀態。由于DA（2）的結束時限為）的結束時限為60，近于，近于DB（1）的結束時限）的結束時限75，從而，從而DB（1）被）被DA（2）搶）搶先。先。DA（2）的實際結束時間為）的實際結束時間為45，小于要求時限，小于要求時限60在在DA（2）結束之后，）結束之后，DB（1）再次占有處理機）再次占有處理機繼續執行，當繼續執行，當DB（1）執行到時間為）執行到時間為60 ms時，進時，進程程DA（3）進入就緒狀態。但是，由于）進入就緒狀態。但是，由于DA（3）的）的結束時限為結束時限為90，遠于，遠于DB（1）的結束時限）的結束時限75，從而，從而DB（1）繼續執行。）繼續執行。62頻率單調調度算法是一種被廣泛用于多周期性實時頻率單調調度算法是一種被廣泛用于多周期性實時處理的調度算法。處理的調度算法。頻率單調調度算法的基本原理是頻率越低（周期越頻率單調調度算法的基本原理是頻率越