進程調度算法（Short-Term）

1.先來先服務（FCFS）

該方法按照進程到達的先后順序排隊，每次調度隊首的進程（就像超市中購物付款一樣）。
FCFS算法屬于非剝奪調度方式，實現簡單，看似公平。但是對于那些后進入隊列而運行時間較短的進程，或I/O型的進程而言，可能需要長時間等待（對短進程以及I/O型進程不公平）。

1.1 幼兒園小孩喂食問題

如果采用FCFS方法，讓全部小孩排成一個先進先出的隊列，老師從隊首開始逐個給小孩喂食，只有當前一個小孩吃飽了，才喂食下一個小孩。那么，排在隊列后面的的小孩將長時間不能被喂食而饑餓。
特別地，如果排在隊列前面的某些小孩需要喂食的時間較長，而排在隊列后面的某些小孩只需進食很少的飯量，卻需要等待很長的時間。因此，該方法對這樣的小孩不公平。

1.2 FCFS調度算法實例

假設：就緒隊列中從隊首開始依次排列有四個進程P1，P2，P3和P4（假設它們同時到達就緒隊列），它們的預計執行時間分別為16，12，4和3個單位時間。若采用FCFS方法調度，試計算P1，P2，P3和P4的周轉時間分別為多少？平均周轉時間是多少？

1.3 FCFS調度算法綜合評價

A: 對短進程不公平。
B: 由于長進程可能排在隊列前面，必將增加隊列后部進程的等待時間，從而將增加平均周轉時間。
C: 不利于I/O型進程，未有效利用系統資源。
D: 一般地，FCFS與其他調度算法混合使用。例如，系統可以按照不同的優先級維護多個就緒隊列，每個隊列內部按照FCFS算法調度。
E: FCFS算法同時適合于長程、中程和短程調度三種調度類型。

2.短進程優先調度算法

當需要調度進程（或作業）時，通過計算判斷就緒進程隊列中哪一個進程的預期執行時間最短，或后備作業隊列中哪一個或幾個作業的預期執行時間最短，就調度誰。

2.1?如何預判斷時間最短？？？

進程還沒有執行，如何才能預測進程（或作業）的執行時間呢？？？操作系統內核的統計功能，進程終止沒有退出系統還要停留一段時間，此時，就是操作系統的統計模塊在執行功能。這樣操作系統利用統計模塊根據同類進程執行歷史，來估計本進程的執行時間。該方法并不是十分精準的。

2.2 內容與實例

屬于非剝奪調度算法。當某進程獲得處理機，直到其執行完成，或需要等待某事件而阻塞時，才自動釋放處理機。系統又調度新的進程（或作業）。
若采用短進程優先算法調度上例的4個進程，按照進程預期執行時間排序（升序）為P4，P3，P2，P1，試分別計算4個進程的周轉時間和他們的平均周轉時間。

2.3 綜合評價

與FCFS算法比較，短進程優先調度算法改善了系統的性能，降低了系統的平均等待時間，提高了系統的吞吐量。但是，該算法也存在一些問題：
⑴ 很難準確預測進程的執行時間；
⑵ 可能導致長進程饑餓，這對長進程不公平；
⑶ 采用非剝奪調度方式，未考慮進程的緊迫程度，不適合于分時系統和事務處理系統。?

3.時間片輪轉調度法

在一個分時聯機系統中，同時有n個人通過各自的終端共享一臺主機（服務器）。終端完成輸入/輸出操作，主機負責處理從終端發來的請求，為之建立進程、協調各進程的運行、調度各個進程等，并盡量滿足每個終端用戶對響應時間的要求。


在分時聯機系統中，n個進程循環地獲得時間片而執行。從系統中來看它們是交替執行的，但就每個終端用戶而言，都感覺到自己獨占了一臺主機，不受其他用戶的影響。這是通過進程并發執行實現的。
如果用戶數太多，主機處理的進程將會急劇增加，進程排隊等待的時間也會很長，進程的響應時間也可能增長，用戶將明顯感覺到主機的速度變慢而不滿意。
時間片的大小也會影響進程的響應時間。（重點討論時間片大小對CPU性能的影響）

3.1 時間片的設置

進程切換將會增加系統的額外開銷（保護現場、恢復現場等）。?
時間片設定得太短，進程切換會非常頻繁，從而降低處理機的效率；時間片設定得太長，將無法滿足交互式用戶對響應時間的要求。
因此，時間片大小的確定應綜合考慮系統的最大用戶數、響應時間、系統效率等多種因素。?

3.2例題分析

采用基于時間片輪轉調度算法調度上例的4個進程，并分別按照兩種時間片大小輪轉調度（1個單位時間和4個單位時間），分析該算法的性能。
首先按照進程到達的先后順序組織就緒隊列，即P1,P2,P3,P4。從隊首開始調度，首先調度P1，執行一個時間片，強行中斷P1，P1回到就緒隊列隊尾排隊；切換到P2，執行一個時間片，強行中斷P2，P2回到就緒隊列隊尾排隊（排在P1之后）…?


計算等待時間以及周轉時間：
注意： ? ? 1.為了簡單，圖中忽略了進程切換時的系統開銷，而實際操作系統中，這類系統額外開銷是客觀存在的。 2.采用基于時間片輪轉調度法，進程的周轉時間和平均周轉時間并不比采用FCFS和短進程優先調度算法小。 3. 加上進程切換所需的系統開銷時間，該算法的平均周轉時間還會增長。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

3.3 綜合評價

1. 常用于分時系統及事務處理系統，合理的時間片大小將帶來滿意的響應時間。
2. 通常，合理的時間片指，能讓80%左右的進程在一個時間片內完成。
3. 對于短的、計算型的進程較有利。
4. 不適合于批處理系統的進程調度（任務量太大、中斷太多、系統開銷太大）
5. 不利于I/O型的進程。
改進的方法之一，可以將I/O阻塞事件完成的進程單獨組織一個就緒隊列，該隊列進程的時間片可以設置的小一些，且優先調度。

4.基于優先級的調度算法

基于時間片輪轉調度法循環式地為每個被調度的進程分配一個時間片，對每個進程都是公平的。
然而，實際應用中，進程的性質可能是不同的。例如，一個與用戶進行交互的前臺進程急迫地需要對用戶的輸入作出響應，而一個后臺打印進程的迫切性也許就不那么重要。
因此，可以為每個進程定義一個優先級，優先級越高的進程將優先獲得處理機的調度。?

4.1 如何設定進程的優先級？

1. 進程完成功能的重要性 ?（用戶與系統）
2. 進程完成功能的急迫性 ?（前臺比后臺急迫）
3. 為均衡系統資源的使用，指定進程（作業）優先級
4. 進程對資源的占用程度 ?例如，可以為短進程（或作業）賦予較高的優先級。

4.2 靜態優先級與動態優先級

靜態優先級： 一旦確定，則進程運行期間優先級一直不改變（管理簡單，但是太死板）。
動態優先級： 系統首先賦予進程一個初始優先級，該優先級將隨著進程的運行而改變。
典型的動態優先級變化方式為：
? A - 優先級隨著進程運行的剩余時間的減少而上升，使將要執行結束的進程盡快完成；
? B - 隨著進程排隊等待時間的增長而上升，使等待時間越長的進程優先得到調度，不至于長時間饑餓。
具體實現方法，可以在每個時鐘中斷時，或需要進程切換時，重新計算就緒隊列中各進程的優先級，并優先調度高優先級的進程。
采用動態優先級的兩種調度算法：剩余時間最短者優先和響應比高者優先。

4.3優先級調動（剩余時間最短者優先調度算法）

為了使將要結束的進程盡早結束，釋放系統資源，讓別的進程執行。可以在每個時鐘中斷時，根據就緒隊列中各進的剩余執行時間動態調整其優先級，剩余時間最短的進程優先級最高。
顯然，該算法是剝奪型的短進程優先調度算法，調度程序總是選擇剩余執行時間最短的進程調度執行。
算法評價： 1. 與短進程優先調度算法一樣，該調度算法很難準確估計進程的剩余執行時間。
2. 長進程在未執行時，或剛開始執行的一段時間內，其剩余執行時間都不會最短，該算法對長進程不公平。
3. 但是，它不象FCFS算法偏袒長進程，也不象輪轉調度算法會產生很多中斷而增加系統負擔。
4. 短進程提前完成，故采用剩余時間最短者優先的調度算法獲得的平均周轉時間比采用短進程優先算法短。?

4.4優先級調動（響應比高者優先調度算法）

進程的等待時間w和進程的預期執行時間s納入優先級的計算，進程（預期執行時間）越長優先級越低，而隨著進程的等待時間增長優先級上升，即進程的優先級與等待時間成正比，與進程執行時間成反比。則響應比：
R = (W+S)/S = W/S + 1； R的最小值為1 調度方法： 若當前執行進程執行完畢，或需要阻塞等待某事件而釋放處理機，調度程序選擇就緒隊列中響應比最大的進程執行。若等待時間相同，短進程因為s較小，R較大而優先調度。若進程的預期執行時間相同，則等待時間長的進程優先調度，相當于FCFS。隨著等待時間的增加，長進程的響應比不斷增大，在某個時刻，也必然被調度。?
缺點： 同短進程優先和剩余時間最短者優先調度算法一樣，很難準確估計進程的預期執行時間S。
每次調度之前都需要計算響應比，增加了系統開銷。

5.反饋調度法

前面介紹的幾種調度算法都存在各自不同的問題，尤其是短進程優先、剩余時間最短者優先以及響應比高者優先調度算法都需要估計進程的預期執行時間，如果估計不準確，將影響調度結果和系統性能。如果根據進程執行歷史，而非未來，進行調度，將解決這個問題。反饋調度法就是一種根據進程執行歷史調整調度方式的調度方法，它結合了優先級和時間片輪轉調度思想。

5.1原理示意圖

5.2 反饋調度法綜合評價

1. 有利于交互型短進程或短批處理作業，因為它們一般只需要一個或很少的幾個時間片即可完成，
2. 可能使長進程的周轉時間急劇增加。
3. 如果不斷地有新進程到來，還可能出現長進程長期饑餓現象。
4. 可以為各隊列設置不同的時間片，優先級愈低時間片愈長。

6.進程調度算法總結

6.1?如何選擇進程調度算法？

如何選擇進程調度算法與系統設計的目標有關。交互式多任務系統，主要考慮聯機用戶對響應時間的要求，一般采用基于時間片輪轉調度算法，同時，根據進程的性質設置不同的優先級；批處理系統，往往以作業的平均周轉時間來衡量調度性能，常選用基于優先級的短進程（或作業）優先調度算法。

6.2 實時系統

能及時響應外部事件的請求，在規定的時間內完成對該事件的處理，并控制所有實時任務協調一致地運行的計算機系統.分為實時控制系統和實時信息處理系統。
實時控制系統： 主要用于生產過程的控制，實時采集現場數據，并對所采集的數據進行及時處理，進而自動地控制相應的執行機構，使某些(個)參數(如溫度、壓力、方位等)能按預定的規律變化，以保證產品的質量和提高產量。也可用于武器的控制，如火炮的自動控制系統，飛機的自動駕駛系統，以及導彈的制導系統等。
實時信息處理系統： 該系統由一臺或多臺主機通過通信線路連接成百上千個遠程終端，計算機接收從遠程終端發來的服務請求，根據用戶提出的問題，對信息進行檢索和處理，并在很短的時間內為用戶做出正確的回答。典型的實時信息處理系統有：飛機訂票系統、情報檢索系統等。

總結

以上是生活随笔為你收集整理的[OS复习]进程管理4的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。