iT邦幫忙

2021 iThome 鐵人賽

DAY 6
0
自我挑戰組

當你凝視linux, linux也在凝視你系列 第 6

Day6 讓 scheduler 規劃未來

Day6 讓 scheduler 規劃未來

tags: 鐵人賽

前言

昨天講到了行程的生老死別,那麼行程是如何被挑中,成為那百中選一能夠執行的行程呢?那就不得不提到排程器(scheduler) 這個重要的挑選者了。

排程器 (scheduler )

凡事皆有輕重緩急,行程也是一樣,每一個行程依據類型以及時限可以分成不同的優先權,優先權高的必然有必須早點完成的必要性,優先權低的可以先擱置,先把重要的行程先完成。
排程器(scheduler)就是負責完成將行程依照輕重緩急排序的演算法,能讓資源在有限的情況下,完成最合理的順序,這就是排程器背負的任務。
在排程演算法之前要先知道,排程本身的運作是需要耗費系統資源的,排程本身就是需要CPU的運算資源,會與其他行程爭搶運行時間,所以並不是讓很多時間讓排程器做出最好的排序就是一個好的結果,而是要在盡可能短的時間內完成最好的解。

如上圖,如果紅色的區域是排程的時間,那麼當然希望能在最短的時間完成排程,才不會佔用到實際的行程的執行時間。
以下提及一個經典的排程演算法 MLFQ 與兩個 Linux 舊版使用的 O(n), O(1) 演算法。

經典排程演算法 (Multi-Level Feedback Queue, MLFQ)


上圖是 MLFQ的精神,同時有多個隊列,每一條隊列裡的行程都是同樣優先級的,更重要的事情是這些行程的優先權是可以被排程器修改的,關於 MLFQ還有更多的規則,詳細都在以下這篇文章

Linux 2.4 O(n)排程器

Linux 這麼偉大的作業系統,一開始的排程器也是相當的簡陋,排程器要維護兩個連結串列(link list),每次一個當成目前要執行的串列,另一個必須等到目前執行的串列為空時,才切換到另一個串列。每一次排程器從當下的串列頭拿出一個行程執行,執行結束後,將該行程移動到另一個等待串列,並且依照優先權插入,直到目前執行的串列為空時,才換成另一個串列開始執行,也因為每次行程結束後需要依照正確的優先權插入另一個串列,所以最糟糕需要O(n)的時間複雜度。

Linux 2.6 O(1)排程器

在O(1)的排程器裡,一樣用到兩個array,兩個array的每一格都含有一個位元,與一個串列,該位元是為了確定串列是否為空,如果串列為空,則位元值設為0,反之則設1。這麼做可以將尋找下個行程的過程變成在一個bitarray內找到最高位是1的bit ,這個行為可以用 CPU 指令 : Find first set/one 達成。
詳細步驟為以下

大致的排程步驟如下:

  1. 在 active bitarray 裡,尋找 left-most bit 的位置 x;
  2. 在 active priority array(APA)中,找到對應 queue APA[x];
  3. 從 APA[x] 中 dequeue 一個 process,dequeue 後,如果 APA[x] 的 queue 為空,那麼將 active bitarray 裡第 x bit 設定為 0;
  4. 對於目前執行完的行程,重新計算其 priority,然後 enqueue 到 expired priority array(EPA)相應的 queue EPA[priority];
  5. 若 priority 在 expired bitarray 裡對應的 bit 為 0,將其設定 1;
  6. 如果 active bitarray 全為 0,將 active bitarray 和 expired bitarray 交換;

參考資料 : Linux核心設計:不只挑選任務的排程

目前Linux 使用的是CFS 演算法,會在明天介紹。


上一篇
Day5 process 的生命週期
下一篇
Day7 初探CFS scheduler (上)
系列文
當你凝視linux, linux也在凝視你30

尚未有邦友留言

立即登入留言