Linux系統篇-進程的管理與調度

當需要選擇當前最高優先順序的進程時，2.6調度器不用遍歷整個runqueue，而是直接從active數組中選擇當前最高優先順序隊列中的第一個進程。假設當前所有進程中最高優先順序為50（換句話說，系統中沒有任何進程的優先順序小於50）。則調度器直接讀取active[49]，得到優先順序為50的進程隊列指針。該隊列頭上的第一個進程就是被選中的進程。

在SD演算法中，處於樓梯底部的低優先順序進程必須等待所有的高優先順序進程執行完才能獲得CPU。因此低優先順序進程的等待時間無法確定。RSDL中，當高優先順序進程組用完了它們的Tg(即組時間配額)時，無論該組中是否還有進程Tp尚未用完，所有屬於該組的進程都被強制降低到下一優先順序進程組中。這樣低優先順序任務就可以在一個可以預計的未來得到調度。從而改善了調度的公平性。這就是RSDL中Deadline代表的含義。

當active數組為空，或者所有的進程都降低到最低優先順序時就會觸發主輪詢majorrotation。Majorrotation交換active數組和expire數組，所有進程都恢復到初始狀態，再一次從新開始minorrotation的過程。RSDL對互動式進程的支持：和SD同樣的道理，互動式進程在睡眠時間時，它所有的競爭者都因為minorrotation而降到了低優先順序進程隊列中。

所有可運行的任務通過不斷地插入操作最終都存儲在以時間為順序的紅黑樹中（由sched_entity對象表示），對處理器需求最多的任務（最低虛擬運行時）存儲在樹的左側，處理器需求最少的任務（最高虛擬運行時）存儲在樹的右側。為了公平，CFS調度器會選擇紅黑樹最左邊的葉子節點作為下一個將獲得cpu的任務。這樣，樹左側的進程就被給予時間運行了。

後來發現該圖片是BFS調度器的引子,太具有諷刺意義了。

內核在pick-next的時候，按照O(1)調度器的方式首先查找點陣圖中不為0的那個queue，然後在該queue中執行O(n)查找，查找到virtualdeadline(如下所述)最小的那個進程投入執行。過程很簡單，就像流水一樣。之所以規劃103個隊列而不是一個完全是為了進程按照其性質而分類，這個和每CPU沒有任何關係，將進程按照其性質(RT?優先順序?)分類而不是按照CPU分類是明智之舉。

在結構單一，功能確定且硬體簡單的系統中，不正確的調度器架構如下圖所示：

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！