歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux基礎 >> Linux技術

常見的及Linux中的進程調度算法

首先,我們來看看什麼是進程調度。

高級調度:(High-Level Scheduling)又稱為作業調度,它決定把後備作業調入內存運行;

低級調度:(Low-Level Scheduling)又稱為進程調度,它決定把就緒隊列的某進程獲得CPU;

中級調度:(Intermediate-Level Scheduling)又稱為在虛擬存儲器中引入,在內、外存對換區進行進程對換。

接下來,我們看一看常見的進程調度算法。

先來先服務(First Come First Service,FCFS)調度算法按照進程進入就緒隊列的先後順序選擇可以占用處理器的進程。這是一種不可搶占方式的調度算法,優點是實現簡單,缺點是後來的進程等待CPU的時間較長。它現今主要用作輔助調度法;例如結合在優先級調度算法中使用,當有兩個最高優先級的進程時,則誰先來,誰就先被調度。

短執行進程優先算法(Shortest Process First,SPF)就是從就緒隊列中選擇一個CPU執行時間預期最短的進程,將處理器分配給它。雖然較公平,但實現難度較大,因為要准確預定下一個進程的CPU執行周期是很困難的。

•最高優先級優先(Highest Priority First,HPF)調度算法的核心是確定進程的優先級。首先,系統或用戶按某種原則為進程指定一個優先級來表示該進程所享有的調度優先權。確定優先級的方法較多,一般可分為兩類,即靜態法和動態法。靜態法根據進程的靜態特性,在進程開始執行之前就確定它們的優先級,一旦開始執行之後就不能改變。動態法則不然,它把進程的靜態特性和動態特性結合起來確定進程的優先級,隨著進程的執行過程,其優先級不斷變化。

•進程的靜態優先級確定最基本的方法是按照進程的類型給予不同的優先級。例如,在有些系統中,進程被劃分為系統進程和用戶進程。系統進程享有比用戶進程高的優先級;對於用戶進程來說,則可以分為:I/O繁忙的進程、CPU繁忙的進程、I/O與CPU均衡的進程和其他進程等。

•對系統進程,也可以根據其所要完成的功能劃分為不同的類型。例如,調度進程、I/O進程、中斷處理進程、存儲管理進程等。這些進程還可進一步劃分為不同類型並賦予不同的優先級。例如,在操作系統中,對於鍵盤中斷的處理優先級和對於電源掉電中斷的處理優先級是不相同的。

•基於靜態優先級的調度算法實現簡單,系統開銷小,但由於靜態優先級一旦確定之後,直到執行結束為止始終保持不變,從而系統效率較低,調度性能不高。現在的操作系統中,如果使用優先級調度的話,則大多采用動態優先級的調度策略。

•進程的動態優先級一般可以根據以下兩個方面來確定:

• (1)根據進程占有CPU時間的長短來決定。一個進程占有處理機的時間愈長,則在被阻塞之後再次獲得調度的優先級就越低。反之,其獲得調度的可能性就會越大。

• (2)根據就緒進程等待CPU的時間長短來決定。一個就緒進程在就緒隊列中等待的時間越長,則它獲得調度選中的優先級就越高。

•由於動態優先級隨時間的推移而變化,系統要經常計算各個進程的優先級,因此,系統要為此付出一定的開銷。

•最高優先級優先調度算法用於多道批處理系統中較好,但它使得優先級較低的進程等待時間較長,這對於分時系統中要想獲得較好的響應時間是不允許的,所以在分時系統中多采用時間片輪轉法來進行進程調度。

接下來,我們在說一說Linux中的進程調度。

調度程序運行時,要在所有可運行狀態的進程中選擇最值得運行的進程投入運行。選擇進程的依據是什麼呢?在每個進程的task_struct結構中有以下四項:policy、priority、counter、rt_priority。這四項是選擇進程的依據。其中,policy是進程的調度策略,用來區分實時進程和普通進程,實時進程優先於普通進程運行;priority是進程(包括實時和普通)的靜態優先級;counter是進程剩余的時間片,它的起始值就是priority的值;由於counter在後面計算一個處於可運行狀態的進程值得運行的程度goodness時起重要作用,因此,counter也可以看作是進程的動態優先級。rt_priority是實時進程特有的,用於實時進程間的選擇。

調度方法

1,SCHED_OTHER 分時調度策略,

2,SCHED_FIFO實時調度策略,先到先服務

3,SCHED_RR實時調度策略,時間片輪轉

相同點:

RR和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,則保證了這兩個任務可以循環執行,保證了公平。

本文僅對進程調度進行了簡單的介紹和理解,如有錯誤,望留言批評。

Copyright © Linux教程網 All Rights Reserved