(文章目錄) 一、調度演算法的原理和分類 1.進程調度簡介 進程調度的研究是整個操作系統理論的核心，在多進程的操作系統中，進程調度是一個全局性的、關鍵性的問題，它對系統的總體設計、系統的實現、功能設置以及各方面的性能都有著決定性的影響。進程運行需要各種各樣的系統資源，如記憶體、文件、印表機和最寶貴的CP ...
目錄
一、調度演算法的原理和分類
1.進程調度簡介
進程調度的研究是整個操作系統理論的核心，在多進程的操作系統中，進程調度是一個全局性的、關鍵性的問題，它對系統的總體設計、系統的實現、功能設置以及各方面的性能都有著決定性的影響。進程運行需要各種各樣的系統資源，如記憶體、文件、印表機和最寶貴的CPU等，所以說，調度的實質就是資源的分配。系統通過不同的調度演算法(Scheduling Algorithm)來實現這種資源的分配。通常來說，選擇什麼樣的調度演算法取決於資源分配的策略(Scheduling Policy)。
Linux是一個支持多任務的操作系統，而多個任務之間的切換是通過調度器來完成，調度器使用不同的調度演算法會有不同的效果。
Linux2.4版本使用的調度演算法的時間複雜度為O(n),其主要原理是通過輪詢所有可運行任務列表，然後挑選一個最合適的任務運行，所以其時間複雜度與可運行任務隊列的長度成正比。
而Linux2.6開始替換成名為0(1)調度演算法 ，顧名思義，其時間複雜度為0(1)。
此後，後面的版本開始使用CFS（Completely Fair Scheduler）調度演算法。
Linux的CFS調度器搶占處理器的要求是：新進程消耗的使用比比當前進程小，則新進程立刻投入運行。否則，將推遲進行。
一個好的調度演算法應當考慮以下幾個方面：
（1）公平:保證每個進程得到合理的CPU時間。
（2）高效:使CPU保持忙碌狀態，即總是有進程在CPU上運行。
（3）響應時間:使交互用戶的響應時間儘可能短。
（4）周轉時間:使批處理用戶等待輸出的時間儘可能短。
（5）吞吐量:使單位時間內處理的進程數量儘可能多。
很顯然，這5個目標不可能同時達到，所以，不同的操作系統會在這幾個方面中作出相應的取捨，從而確定自己的調度演算法，例如UNIX採用動態優先數調度、5.3BSD採用多級反饋隊列調度、Windows採用搶先多任務調度等。
2.按不同需求對調度的進程分類
第一種分類：
I/O-bound
1.頻繁的進行I/O
2.通常會花費很多時間等待I/O操作的完成
CPU-bound
1.計算密集型
2.需要大量的CPU時間進行運算
前者需要更多的IO資源，比如多數的圖形交互程式；後者則把時間花在了執行代碼上。linux系統為了保證互動式應用和桌面的性能，更傾向於有限調度IO消耗型的進程。
第二種分類
互動式進程（interactive process）
1.需要經常與用戶交互，因此要花很多時間等待用戶輸入操作
2.響應時間要快，平均延遲要低於50~150ms
3.典型的互動式程式：shell、文本編輯程式、圖形應用程式等
批處理進程（batch process）
1.不必與用戶交互，通常在後臺運行
2.不必很快響應
3.典型的批處理程式：編譯程式、科學計算
實時進程（real-time process）
1.有實時需求，不應被低優先順序的進程阻塞
2.響應時間要短
3.典型的實時進程：視頻/音頻、機械控制等
對於實時進程，採用FIFO, Round Robin或者Earliest Deadline First (EDF)最早截止期限優先調度演算法的調度策略.
Linux既支持普通的分時進程，也支持實時進程，Linux中的調度是多種調度策略和調度演算法的混合。Linux的調度基於分時和優先順序，隨著版本的變化，分時技術在不斷變化，優先順序越來越複雜。Linux的進程根據優先順序排隊，根據特定的演算法計算出進程的優先順序，用一個值表示，這個值表示把進程如何適當的分配給CPU。，Linux中進程的優先順序是動態的，調度程式會根據進程的行為周期性的調整進程的優先順序，較長時間未分配到CPU的進程，通常優先順序被提升，已經在CPU上運行了較長時間的進程，通常優先順序被減低。
3.調度演算法分類
（1）時間片輪轉調度演算法
時間片(Time Slice) 就是分配給進程運行的一段時間。在分時系統中，為了保證人機交互的及時性，系統使每個進程依次地按時間片輪流的方式執行，此時即應採用時間片輪轉法進行調度。在通常的輪轉法中，系統將所有的可運行(即就緒)進程按先來先服務的原則，排成一個隊列， 每次調度時把CPU分配給隊首進程，並令其執行一個時間片。時間片的大小從幾ms到幾百ms不等。當執行的時間片用完時，系統發出信號，通知調度程式，調度程式便據此信號來停止該進程的執行，並將它送到運行隊列的末尾，等待下一次執行。然後，把處理機分配給就緒隊列中新的隊首進程，同時也讓它執行一個時間片。這樣就可以保證運行隊列中的所有進程，在一個給定的時間( 人所能接受的等待時間)內，均能獲得一時間片的處理機執行時間。
（2）優先權調度演算法
為了照顧到緊迫型進程在進入系統後便能獲得優先處理，引入了最高優先權調度演算法。當將該演算法用於進程調度時，系統將把處理機分配給運行隊列中優先權最高的進程，這時，又可進一步把該演算法分成兩種方式。
(a)非搶占式優先權演算法(又稱不可剝奪調度，Nonpreemptive Scheduling) 在這種方式下，系統一旦將處理機(CPU) 分配給運行隊列中優先權最高的進程後，該機分配給另一個優先權高的進程。這種調度演算法主要用於批處理系統中，也可用於某些對實時性要求不嚴的實時系統中。
(b)搶占式優先權調度演算法(又稱可剝奪調度，Preemptive Scheduling) 該演算法的本質就是系統中當前運行的進程永遠是可運行進程中優先權最高的那個。在這種方式下，系統同樣是把處理機分配給優先權最高的進程，使之執行。但是只要一齣現了另一個優先權更高的進程時，調度程式就暫停原最高優先權進程的執行，而將處理機分配給新出現的優先權最高的進程，即剝奪當前進程的運行。因此，在採用這種調度演算法時，每當出現一新的可運行進程，就將它和當前運行進程進行優先權比較，如果高於當前進程，將觸發進程調度。 這種方式的優先權調度演算法，能更好的滿足緊迫進程的要求，故而常用於要求比較嚴格的實時系統中，以及對性能要求較高的批處理和分時系統中。Linux 也採用這種調度演算法。
(3)多級反饋隊列調度
其本質是:綜合了時間片輪轉調度和搶占式優先權調度的優點，即:優先權高的進程先運行給定的時間片，相同優先權的進程輪流運行給定的時間片。
(4)實時調度
最後我們來看一下實時系統中的調度。什麼叫實時系統，就是系統對外部事件有求必應、儘快響應。在實時系統中存在有若幹個實時進程或任務，它們用來反應或控制某個(些)外部事件，往往帶有某種程度的緊迫性，因而對實時系統中的進程調度有某些特殊要求。在實時系統中，廣泛採用搶占調度方式，特別是對於那些要求嚴格的實時系統。因為這種調度方式既具有較大的靈活性，又能獲得很小的調度延遲;但是這種調度方式也比較複雜。
二、調度的時機
進程調度的Linux 的調度程式是一個叫Schedule()的函數，這個函數被調用的頻率很高，由它來決定是否要進行進程的切換，如果要切換的話，切換到哪個進程等。我們先來看在什麼情況下要執行調度程式，我們把這種情況叫做調度時機。Linux調度時機主要分兩種情況：主動調度和被動調度。
Linux 調度時機主要有：
(1）進程狀態轉換的時刻:進程終止、進程睡眠;
(2）當前進程的時間片用完時(current->counter=0） ;
(3）設備驅動程式;
(4）進程從中斷、異常及系統調用返回到用戶態時。
時機1，進程要調用sleep()或exit()等函數進行狀態轉換，這些函數會主動調用調度程式進行進程調度。
時機2，由於進程的時間片是由時鐘中斷來更新的，如同時機4。
時機3，當設備驅動程式執行長而重覆的任務時，直接調用調度程式。在每次反覆迴圈中，驅動程式都檢查need_resched的值，如果必要，則調用調度程式schedule()主動放棄CPU。
時機4，如前所述，不管是從中斷、異常還是系統調用返回，最終都調用ret_from_sys_call()，由這個函數進行調度標誌的檢測，如果必要，則調用調度程式。那麼，為什麼從系統調用返回時要調用調度程式呢﹖這當然是從效率考慮。從系統調用返回意味著要離開內核態而返回到用戶態，而狀態的轉換要花費一定的時間，因此，在返回到用戶態前，系統把在內核態該處理的事全部做完。
三、調度的依據
在linux2.4.16中，調度程式運行時，要在所有處於可運行狀態的進程之中選擇最值得運行的進程投入運行。選擇進程的依據是什麼呢?在每個進程的task_struct結構中有如下5項:need_resched、 nice、counter、 policy 及rt_priority
（1）need_resched:在調度時機到來時,檢測這個域的值,如果為1,則調用schedule()。
（2） counter:進程處於運行狀態時所剩餘的時鐘滴答數，每次時鐘中斷到來時，這個值就減1。當這個域的值變得越來越小，直至為0時，就把need_resched域置1，因此，也把這個域叫做進程的“動態優先順序”。
（3）nice:進程的“靜態優先順序”，這個域決定 counter的初值。只有通過 nice()、POSIX.1b sched_setparam()或5.4BSD/SVR4 setpriority()系統調用才能改變進程的靜態優先順序。
（4） rt_priority:實時進程的優先順序
（5）policy:從整體上區分實時進程和普通進程，因為實時進程和普通進程的調度是不同的，它們兩者之間，實時進程應該先於普通進程而運行，可以通過系統調用sched_setscheduler ( )來改變調度的策略。對於同一類型的不同進程，採用不同的標準來選擇進程。對於普通進程，選擇進程的主要依據為counter和nice。對於實時進程，Linux採用了兩種調度策略，即FIFO（先來先服務調度）和RR(時間片輪轉調度)。因為實時進程具有一定程度的緊迫性，所以衡量一個實時進程是否應該運行，Linux採用了一個比較固定的標準。實時進程的counter只是用來表示該進程的剩餘滴答數，並不作為衡量它是否值得運行的標準，這和普通進程是有區別的。
與其他操作系統一樣，Linux的時間單位也是“時鐘滴答”，只是不同的操作系統對一個時鐘滴答的定義不同而已(Linux設計者將一個“時鐘滴答”定義為10ms)。在這裡，我們把counter叫做進程的時間片，但實際上它僅僅是時鐘滴答的個數，例如，若counter為5，則分配給該進程的時間片就為5個時鐘滴答，也就是5*10ms=50ms，實際上，Linux 2.4中給進程初始時間片的大小就是50ms。
函數goodness()就是用來衡量一個處於可運行狀態的進程值得運行的程度。該函數綜合使用了上面我們提到的5項，給每個處於可運行狀態的進程賦予一個權值(weight)，調度程式以這個權值作為選擇進程的唯一依據。函數主體如下:
將函數goodness（）簡化如下：
在sched.h中對調度策略定義如下：
這個goodness（）函數比較很簡單。首先，根據 policy區分實時進程和普通進程。實時進程的權值取決於其實時優先順序，其至少是1000，與conter和nice無關。
普通進程的權值需特別說明如下兩點。
(1）為什麼進行細微的調整﹖如果p->mm為空，則意味著該進程無用戶空間（例如內核線程），則無需切換到用戶空間。如果 p->mm=this_mm，則說明該進程的用戶空間就是當前進程的用戶空間，該進程完全有可能再次得到運行。對於以上兩種情況，都給其權值加 1，算是對它們小小的“獎勵”。
(2）進程的優先順序nice是從早期UNIX沿用下來的負向優先順序，其數值標誌“謙讓”的程度，其值越大，就表示其越“謙讓”，也就是優先順序越低，其取值範圍為一20~~19，因此，（20-p->nice）的取值範圍就是0~40。可以看出，普通進程的權值不僅考慮了其剩餘的時間片，還考慮了其優先順序，優先順序越高，其權值越大。
有了衡量進程是否應該運行的標準，選擇進程就是輕而易舉的事情了，“弱肉強食”，誰的權值大誰就先運行。根據進程調度的依據，調度程式就可以控制系統中的所有處於可運行狀態的進程併在它們之間進行選擇。
四、調度的實現
1.Linux2.4.16版本
在linux2.4.16中調度的實現具體過程如下：
為了討論方便﹐我們同樣對其進行了簡化,略去對SMP的實現部分。
如果當前進程既沒有自己的地址空間,也沒有向別的進程借用地址空間,那肯定出錯。另外，如果schedule()在中斷服務程式內部執行,那也出錯。
對當前進程做相關處理，為選擇下一個進程做好準備。當前進程就是正在運行著的進程，可是，當進入schedule()時，其狀態卻不一定是TASK_RUNNIG，例如，在exit()系統調用中，當前進程的狀態可能已被改為TASK_ZOMBE;又例如，在wait4()系統調用中，當前進程的狀態可能被置為TASK_INTERRUPTIBLE。因此，如果當前進程處於這些狀態中的一種，就要把它從運行隊列中刪除。從運行隊列中選擇最值得運行的進程，也就是權值最大的進程。
如果已經選擇的進程其權值為0，說明運行隊列中所有進程的時間片都用完了(隊列中肯定沒有實時進程，因為其最小權值為1000)，因此，重新計算所有進程的時間片，其中巨集操作NICE_TO_TICKS 就是把優先順序nice轉換為時鐘滴答。
進程地址空間的切換。如果新進程有自己的用戶空間，也就是說，如果next->mm 與next->active_mm相同，那麼，switch_mm ( ）函數就把該進程從內核空間切換到用戶空間，也就是載入next的頁目錄。如果新進程無用戶空間(next->mm為空），也就是說，如果它是一個內核線程，那它就要在內核空間運行，因此，需要借用前一個進程（prev)的地址空間，因為所有進程的內核空間都是共用的，因此，這種借用是有效的。用巨集switch_to()進行真正的進程切換。
2.Linux2.6.23版本
O(1)調度演算法：
O(1)調度演算法通過優先順序來對任務進行分組，可分為140個優先順序(0～139，數值越小優先順序越高），每個優先順序的任務由一個隊列來維護。prio_array 結構就是用來維護這些任務隊列，如下代碼:
下麵介紹prio_array結構各個欄位的作用:
- nr_active:所有優先順序隊列中的總任務數。
- bitmap:點陣圖，每個位對應一個優先順序的任務隊列，用於記錄哪個任務隊列不為空，能通過bitmap夠快速找到不為空的任務隊列。
- queue:優先順序隊列數組，每個元素維護一個優先順序隊列，比如索引為0的元素維護著優先順序為0的任務隊列。
下圖更直觀地展示了prio_array結構各個欄位的關係:
如圖所述， bitmap的第2位和第6位為1(紅色代表為1，白色代表為0)，表示優先順序為2和6的任務隊列不為空，也就是說queue數組的第2個元素和第6個元素的隊列不為空。
runqueue結構:
另外，為了減少多核CPU之間的競爭，所以每個CPU都需要維護―份本地的優先隊列。因為如果使用全局的優先隊列，那麼多核CPU就需要對全局優先隊列進行上鎖，從而導致性能下降。每個CPU都需要維護一個runqueue結構，runqueue結構主要維護任務調度相關的信息，比如優先隊列、調度次數、CPU負載信息等。其定義如下:
runqueue結構有兩個重要的欄位: active和expired ，這兩個欄位在o(1)調度演算法中起著至關重要的作用。我們先來瞭解一下o(1)調度演算法的大概原理。我們註意到active和expired欄位的類型為prio_array，指向任務優先隊列。active代表可以調度的任務隊列，而expired欄位代表時間片已經用完的任務隊列。active和expired會進行以下兩個過程:1.當active中的任務時間片用完，那麼就會被移動到expired中。2.當active中已經沒有任務可以運行，就把expired 與active交換，從而expired中的任務可以重新被調度。如下圖所示：
0(1)調度演算法把140個優先順序的前100個(0 -99)作為實時進程優先順序，而後40個(100 -139）作為普通進程優先順序。實時進程被放置到實時進程優先順序的隊列中，而普通進程放置到普通進程優先順序的隊列中。
實時進程調度：實時進程分為FIFo（先進先出)和RR（時間輪詢)兩種。
普通進程調度：每個進程都要一個動態優先順序和靜態優先順序，靜態優先順序不會變化(進程創建時被設置)，而動態優先順序會隨著進程的睡眠時間而發生變化。動態優先順序可以通過以下公式進行計算:
上面公式的bonus（獎勵或懲罰)是通過進程的睡眠時間計算出來，進程的睡眠時間越大，bonus的值就 越大，那麼動態優先順序就越高（前面說過優先順序的值越小，優先順序越高)。
當一個普通進程被添加到運行隊列時，會先計算其動態優先順序，然後按照動態優先順序的值來添加到對應優先順序的隊列中。而調度器調度進程時，會先選擇優先順序最高的任務隊列中的進程進行調度運行。
運行時間片計算：當進程的時間用完後，就需要重新進行計算。進程的運行時間片與靜態優先順序有關，可以通過以下公式進行計算:
0(1)調度演算法的具體實現：
時鐘中斷是由硬體觸發的，可以通過編程來設置其頻率，Linux內核一般設置為每秒產生100 ～1000次。時鐘中斷會觸發調用scheduler_tick()內核函數，其主要工作是:減少進程的可運行時間片，如果時間片用完，那麼把進程從active隊列移動到expired隊列中。代碼如下:
代碼主要完成以下幾個工作:
1.減少進程的時間片，並且判斷時間片是否已經使用完。
2.如果時間片使用完，那麼把進程從active隊列中刪除。
3.調用set_tsk_need_resched()函數設TIF_NEED_RESCHED標誌，表示當前進程需要重新調度。
4.調用effective_prio()函數重新計算進程的動態優先順序。
5.調用task_timeslice()函數重新計算進程的可運行時間片。
6.如果當前進程是交互進程或者出來饑餓狀態，那麼重新加入到active隊列。
7.否則移動到expired 隊列。
如果進程設置了TIF_NEED_RESCHED標誌，那麼當從時鐘中斷返回到用戶空間時，會調用schedule()函數進行任務調度。schedule()函數代碼如下:
代碼主要完成以下幾個工作:
1.如果當前runqueue的active隊列為空，那麼把active隊列與expired 隊列進行交換。
2.調用sched_find_first_bit()函數在bitmap中找到優先順序最高並且不為空的任務隊列索引。
3.減少當前進程的睡眠時間。
4.調用context_switch()函數切換到next進程進行運行。
小結
在Linux 2.4中用戶進程數越多，系統開銷越大；而Linux 2.6系統開銷並不隨用戶進程數增加而增加。Linux 2.6調度程式比Linux 2.4有了很大的改進，做到了調度程式演算法複雜度與系統負載無關，但對於實時進程的調度性能的改變還是不大，僅僅實現了內核搶占調度，離真正的實時性還有一定的距離。
