調度算法

調度算法

作業系統管理了系統的有限資源,當有多個進程(或多個進程發出的請求)要使用這些資源時,因為資源的有限性,必須按照一定的原則選擇進程(請求)來占用資源。這就是調度。目的是控制資源使用者的數量,選取資源使用者許可占用資源或占用資源。

基本介紹

  • 中文名:調度算法
  • 所屬領域:作業系統
調度算法,評價因素,吞吐量,CPU利用率,周轉時間,確定進程調度原則,調度算法分類,先來先服務(FCFS),輪轉法(Round Robin),多級反饋佇列算法,linux進程調度算法,

調度算法

作業系統中調度是指一種資源分配,因而調度算法是指:根據系統的資源分配策略所規定的資源分配算法。對於不同的的系統和系統目標,通常採用不同的調度算法,例如,在批處理系統中,為了照顧為數眾多的段作業,應採用短作業優先的調度算法;又如在分時系統中,為了保證系統具有合理的回響時間,應當採用輪轉法進行調度。目前存在的多種調度算法中,有的算法適用於作業調度,有的算法適用於進程調度;但也有些調度算法既可以用於作業調度,也可以用於進程調度。
通常將作業或進程歸入各種就緒或阻塞佇列
調度算法要求:高資源利用率、高吞吐量、用戶滿意等原則。
進程調度所採用的算法是與整個系統的設計目標相一致的:
1.批處理系統:增加系統吞吐量和提高系統資源的利用率;
2.分時系統:保證每個分時用戶能容忍的回響時間。
3.實時系統:保證對隨機發生的外部事件做出實時回響。

評價因素

吞吐量

單位時間內CPU完成作業的數量。

CPU利用率

從0%~100%。

周轉時間

評價批處理系統的性能指標。
Ti = 作業完成時刻 - 作業提交時刻

確定進程調度原則

在系統角度來說,公平性:每個進程(不論優先權)都有機會被運行;較大的吞吐量。
用戶角度:及時性:回響速度要快;較短的周轉時間:不應當讓用戶等待時間過長。

調度算法分類

先來先服務(FCFS)

先來先服務(FCFS, First Come First Serve)是最簡單的調度算法,按先後順序進行調度。
1. FCFS算法
按照作業提交或進程變為就緒狀態的先後次序,分派CPU; 當前作業或進程占用CPU,直到執行完或阻塞,才出讓CPU(非搶占方式)。 在作業或進程喚醒後(如I/O完成),並不立即恢復執行,通常等到當前作業或進程出讓CPU。最簡單的算法。
2. FCFS的特點
比較有利於長作業,而不利於短作業。 有利於CPU繁忙的作業,而不利於I/O繁忙的作業。

輪轉法(Round Robin)

輪轉法(Round Robin)是讓每個進程在就緒佇列中的等待時間與享受服務的時間成正比例。
1. 輪轉法
將系統中所有的就緒進程按照FCFS原則,排成一個佇列
每次調度時將CPU分派給隊首進程,讓其執行一個時間片。時間片的長度從幾個ms到幾百ms。
在一個時間片結束時,發生時鐘中斷
調度程式據此暫停當前進程的執行,將其送到就緒佇列的末尾,並通過上下文切換執行當前的隊首進程。? 進程可以未使用完一個時間片,就出讓CPU(如阻塞)。
2. 時間片長度的確定
時間片長度變化的影響2 過長->退化為FCFS算法,進程在一個時間片內都執行完,回響時間長。2 過短->用戶的一次請求需要多個時間片才能處理完,上下文切換次數增加,回響時間長。
對回響時間的要求:T(回響時間)=N(進程數目)*q(時間片)
就緒進程的數目:數目越多,時間片越小
系統的處理能力:應當使用戶輸入通常在一個時間片內能處理完,否則使回響時間,平均周轉時間和平均帶權周轉時間延長。

多級反饋佇列算法

多級反饋佇列算法時間片輪轉算法和優先權算法的綜合和發展。優點:2 為提高系統吞吐量和縮短平均周轉時間而照顧短進程。2 為獲得較好的I/O設備利用率和縮短回響時間而照顧I/O型進程。2 不必估計進程的執行時間,動態調節。
1. 多級反饋佇列算法2 設定多個就緒佇列,分別賦予不同的優先權,如逐級降低,佇列1的優先權最高。每個佇列執行時間片的長度也不同,規定優先權越低則時間片越長,如逐級加倍。2 新進程進入記憶體後,先投入佇列1的末尾,按FCFS算法調度;若按佇列1一個時間片未能執行完,則降低投入到佇列2的末尾,同樣按FCFS算法調度;如此下去,降低到最後的佇列,則按“時間片輪轉”算法調度直到完成。2 僅當較高優先權的佇列為空,才調度較低優先權的佇列中的進程執行。如果進程執行時有新進程進入較高優先權的佇列,則搶先執行新進程,並把被搶先的進程投入原佇列的末尾。
2. 幾點說明
I/O型進程:讓其進入最高優先權佇列,以及時回響I/O互動。通常執行一個小時間片,要求可處理完一次I/O請求的數據,然後轉入到阻塞佇列。
計算型進程:每次都執行完時間片,進入更低級佇列。最終採用最大時間片來執行,減少調度次數。 I/O次數不多,而主要是CPU處理的進程。在I/O完成後,放回優先I/O請求時離開的佇列,以免每次都回到最高優先權佇列後再逐次下降。2為適應一個進程在不同時間段的運行特點,I/O完成時,提高優先權;時間片用完時,降低優先權。
3.shortest job next
系統計算程式調用的時間,時間最短的先執行。

linux進程調度算法

linux核心的三種調度方法:
1. SCHED_OTHER 分時調度策略,
2. SCHED_FIFO實時調度策略,先到先服務
3. SCHED_RR實時調度策略,時間片輪轉
實時進程將得到優先調用,實時進程根據實時優先權決定調度權值,分時進程則通過nice和counter值決
定權值,nice越小,counter越大,被調度的機率越大,也就是曾經使用了cpu最少的進程將會得到優先調
度。
SHCED_RR和SCHED_FIFO的不同:
當採用SHCED_RR策略的進程的時間片用完,系統將重新分配時間片,並置於就緒佇列尾。放在佇列
尾保證了所有具有相同優先權的RR任務的調度公平。
SCHED_FIFO一旦占用cpu則一直運行。一直運行直到有更高優先權任務到達或自己放棄。
如果有相同優先權的實時進程(根據優先權計算的調度權值是一樣的)已經準備好,FIFO時必須等待該
進程主動放棄後才可以運行這個優先權相同的任務。而RR可以讓每個任務都執行一段時間。
SHCED_RR和SCHED_FIFO的相同點:
SHCED_RR和SHCED_FIFO都只用於實時任務。
創建時優先權大於0(1-99)。
按照可搶占優先權調度算法進行。
就緒態的實時任務立即搶占非實時任務。
所有任務都採用linux分時調度策略時。
1. 創建任務指定採用分時調度策略,並指定優先權nice值(-20~19)。
2. 將根據每個任務的nice值確定在cpu上的執行時間(counter)。
3. 如果沒有等待資源,則將該任務加入到就緒佇列中。
4. 調度程式遍歷就緒佇列中的任務,通過對每個任務動態優先權的計算(counter+20-nice)結果,選擇
計算結果最大的一個去運行,當這 個時間片用完後(counter減至0)或者主動放棄cpu時,該任務將被放在
就緒佇列末尾(時間片用完)或等待佇列(因等待資源而放棄cpu)中。
5. 此時調度程式重複上面計算過程,轉到第4步。
6. 當調度程式發現所有就緒任務計算所得的權值都為不大於0時,重複第2步。
所有任務都採用FIFO時:
1. 創建進程時指定採用FIFO,並設定實時優先權rt_priority(1-99)。
2. 如果沒有等待資源,則將該任務加入到就緒佇列中。
3. 調度程式遍歷就緒佇列,根據實時優先權計算調度權值(1000+rt_priority),選擇權值最高的任務使用
cpu,該FIFO任務將一直占有cpu直到有優先權更高的任務就緒(即使優先權相同也不行)或者主動放棄(等
待資源)。
4. 調度程式發現有優先權更高的任務到達(高優先權任務可能被中斷或定時器任務喚醒,再或被當前運行
的任務喚醒,等等),則調度程式立即在當前任務 堆疊中保存當前cpu暫存器的所有數據,重新從高優先權
任務的堆疊中載入暫存器數據到cpu,此時高優先權的任務開始運行。重複第3步。
5. 如果當前任務因等待資源而主動放棄cpu使用權,則該任務將從就緒佇列中刪除,加入等待佇列,此時
重複第3步。
所有任務都採用RR調度策略時
1. 創建任務時指定調度參數為RR,並設定任務的實時優先權和nice值(nice值將會轉換為該任務的時間片
的長度)。
2. 如果沒有等待資源,則將該任務加入到就緒佇列中。
3. 調度程式遍歷就緒佇列,根據實時優先權計算調度權值(1000+rt_priority),選擇權值最高的任務使用
cpu。
4. 如果就緒佇列中的RR任務時間片為0,則會根據nice值設定該任務的時間片,同時將該任務放入就緒隊
列的末尾。重複步驟3。
5. 當前任務由於等待資源而主動退出cpu,則其加入等待佇列中。重複步驟3。
系統中既有分時調度,又有時間片輪轉調度和先進先出調度
1. RR調度和FIFO調度的進程屬於實時進程,以分時調度的進程是非實時進程。
2. 當實時進程準備就緒後,如果當前cpu正在運行非實時進程,則實時進程立即搶占非實時進程。
3. RR進程和FIFO進程都採用實時優先權做為調度的權值標準,RR是FIFO的一個延伸。FIFO時,如果兩
個進程的優先權一樣,則這兩個優先 級一樣的進程具體執行哪一個是由其在佇列中的未知決定的,這樣導
致一些不公正性(優先權是一樣的,為什麼要讓你一直運行?),如果將兩個優先權一樣的任務 的調度策略都
設為RR,則保證了這兩個任務可以循環執行,保證了公平。

相關詞條

熱門詞條

聯絡我們