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 演算法，會在明天介紹。