--- tags: LINUX KERNEL, LKI --- # [Linux 核心設計](https://beta.hackfoldr.org/linux/): 不只挑選任務的排程器 Copyright (**慣C**) 2019 [宅色夫](http://wiki.csie.ncku.edu.tw/User/jserv) ==[直播錄影 (一)](https://youtu.be/Oa_PWUb2GGo)== ==[直播錄影 (二)](https://youtu.be/nNOjasRU9Hw)== ## 目標設定 排程器 (scheduler) 是任何一個多工作業系統核心都具備的機制,但彼此落差極大,考量點不僅是演算法,還有當應用規模提昇時 (所謂的 scalability) 和涉及即時處理之際,會招致不可預知的狀況 (non-determinism),不僅即時系統在意,任何建構在 Linux 核心之上的大型服務都會深受衝擊。是此,Linux 核心的排程器經歷多次變革,需要留意的是,排程的難度不在於挑選下一個可執行的行程 (process),而是讓執行完的行程得以安插到合適的位置,使得 runqueue 依然依據符合預期的順序。 在本講座中,我們會探討 $O(1)$ 排程器前後的設計變化,一併提及 Completely Fair Scheduler (CFS), SCHED_DEADLINE 等等實作。預計涵蓋: - scheduling goal - context switch 實作機制 - O(1) scheduler + rebalancing - CPU topologies 和 scheduling domain - 排程相關系統呼叫 - Completely Fair Scheduler (CFS) - Real-tIme scheduling - Kernel preemption ## 重新認識 scheduling [Wikipedia](https://en.wikipedia.org/wiki/Scheduling_(computing)) 說: > In computing, scheduling is the method by which work specified by some means is assigned to resources that complete the work. 用數學觀念來思考: scheduling 是個函數,把一組任務的集合映射到一組資源。具體來說,Linux (CPU) 排程器就是把一系列 process (中譯「行程」,即一種 workload) 映射到一個個 CPU core: * 主要的任務計有常駐系統的服務、各式 agent, [initscripts](https://www.calculate-linux.org/main/en/initscripts)、週期性任務 * scheduling 作為一個特殊函數,承受著考驗,需要考慮到公平、優先權、搶佔 (preemption)、效率、可擴展能力 (scalability,從單核遷徙到多核,還要涵蓋 NUMA) 等等。 先不講 Linux 排程器,資訊系統其實也存在多種排程器,例如: 1. [erlang scheduler](http://erlang.org/doc/man/scheduler.html): erlang processes 到 threads 間的映射; 2. [nginx](https://nginx.org/en/): HTTP/HTTPS 請求到 processes / application 間的映射; 3. [Memory manager](https://www.kernel.org/doc/html/latest/admin-guide/mm/index.html): virtual memory 到 physical memory 間的映射; 4. [hypervisor](https://en.wikipedia.org/wiki/Hypervisor): VM 到實體硬體間的映射; 5. [Amazon Elastic Compute Cloud (EC2)](https://aws.amazon.com/ec2/): VM 到 hypervisor 間的映射; 6. [Apache Spark](https://spark.apache.org/): map/reduce job 到計算節點間的映射; 經由上述映射,我們可得到額外的好處: * 資源得到更高效的利用; * 由於增加一層 indirection,任務和任務所需要的資源間的耦合度大幅下降; * 更好的服務品質([quality of service](https://en.wikipedia.org/wiki/Quality_of_service), QoS); :::info "All problems in computer science can be solved by another level of [indirection](https://en.wikipedia.org/wiki/Indirection)" (the "[fundamental theorem of software engineering](https://en.wikipedia.org/wiki/Fundamental_theorem_of_software_engineering)") -- David Wheeler ::: 仔細觀察上述案例,不難發現,待處理任務的數量往往遠大於資源的數量,甚至,二者落差可達數個數量級。這種用少量的資源以「打腫臉充胖子」的姿態,嘗試完成大量的任務的行為,在電腦科學領域有個經典的描述,叫做 [oversubscribed](https://encyclopedia2.thefreedictionary.com/Oversubscribed)。其實很多商業領域尤其是網際網路,其營運的秘密就在於 oversubscription 這個概念中。例如,電信業者承諾給你每月 50MB 流量的網路、早期 GMail 提供不斷增長的 1GB 信件容量、AWS 總是拍胸脯說「只要你有錢,EC2 機器想開幾台就開幾台」。 反過來,我們若想支援 oversubscription,就可引入特製的排程器,降低資源的兩端耦合度,即可解決。 當然,你很快就會納悶:享受到排程器的好處,對應的代價是什麼? ## scheduling 對系統的影響 排程器本身的運作會消耗系統資源,是其最主要的代價。自然,我們希望這代價越小越好。於是,下一個問題是:當 Linux 做一次 reschedule 的動作時,究竟耗費多少資源 (CPU 時間)? ![](https://i.imgur.com/vb0jvXC.png) 回答這個問題之前,我們要回答另一個問題:「如何測量?」 要測量上圖中橘色的部分,有兩個直觀的方法。一種方法是在進入點和出口記錄時間,然後計算數值差距,最後求平均值 —— 然而 scheduling 的動作並不受你我掌控,使用者層級 (userspace) 下很難找到其進入點和出口。 另一種方法是我們讓青色的區域無限接近零,讓整個時間片都被橘色的區域佔滿,這樣,任務運行的時長便是 scheudling 花費的總時長。按照這個思路,使用者層級的程式碼需要被簡化到只做一件事情:一旦被執行就立刻阻塞 (block) 自己,讓排程器毫不猶疑地把 CPU 讓給其他工作。 GNU/Linux 下面的 [perf 工具](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) 已提供對應的基礎建設,操作如下: ```shell $ perf bench sched pipe # Running 'sched/pipe' benchmark: # Executed 1000000 pipe operations between two processes Total time: 5.296 [sec] 5.296456 usecs/op 188805 ops/sec ``` (測試環境: [AMD Ryzen Threadripper 2990WX 32-Core Processor](https://www.amd.com/zh-hant/products/cpu/amd-ryzen-threadripper-2990wx)) 原理是兩個行程相互 pipe,排程器夾在其間來回奔波。這裡有個問題,由於行程可能分佈在不同的 CPU 核裡頭,測出的數字會失真,所以我們應該用 [taskset](https://linux.die.net/man/1/taskset) 工具將其 affinity 到某一個 CPU core 下: > affinity KK:[əˋfɪnətɪ] DJ:[əˋfiniti] 有「吸引力」的意思,特別是異性相吸 > 參照 [CPU Topology](http://kodango.com/cpu-topology) 和 [理解 CPU topology](http://fishcried.com/2015-01-09/cpu_topology/) ```shell $ taskset -c 0 perf bench sched pipe # Running 'sched/pipe' benchmark: # Executed 1000000 pipe operations between two processes Total time: 2.849 [sec] 2.849532 usecs/op 350934 ops/sec ``` 每個操作的時間成本從 5.3 us 降到 2.8 us, 為什麼呢? 經由上述效能評比,我們學到些什麼? 首先,這些測試都不算嚴謹。我們並未消除系統裡其它行程的影響,因而測量的結果並不精確。但是,我們大概可以瞭解其處理速度的量級。知道這個量級,非常重要,因為,排程器把 CPU 時間切出來的 time slice 應該要高於這個量級,否則,便沒有意義。 其次,與其說它是 scheduling 的效能,不如說是 context switch 的表現,不過這兩者在非專門對排程器演算法和內部實作分析的我們來說,可初略地是做相等,因為此刻我們關心的是,scheduling 前前後後所處理的各種瑣事 (從上一個 task 結束執行,到下一個 task 開始執行),擠佔多少 CPU 時間。 我們接著可推斷:Linux 排程器做了大量的工作,這其中耗費的絕大多數時間是在 context switch 上,其中也有切換 page table 的成本。 golang 的排程器效能可以比 linux 排程器好上 20 倍,因為在使用者層級下的排程器沒有諸多紛繁複雜,效能自然是很好。golang 排程器設計單純,沒有優先權,也沒有搶佔,而且 Go 語言程式已經預先編譯為原生的機械碼,效能勝出無可厚非。 ## Patterns / Trade-offs 考慮一個排程器時,我們探討下述問題: * 任務如何組織?是所有的資源共享一個任務的 runqueue,排程器排程時經由 locking 來保證互斥,還是針對每個資源,我們都為其設置一個 runqueue,以減少 lock 帶來的損耗?那麼問題又來了,如果某個資源上的任務列表空了,資源是就此閒置,還是可以去別的資源的 runqueue 上「偷」任務給自己執行? * 資源如何利用?是 run to completion,還是 time slicing?run to completion 對於計算密集,且在意 latency 的場景非常有價值,因而在網絡設備中,除 traffic shaping 的需求外,訊息的處理大多採用 run to completion。time slicing 則適用於 I/O 密集,或者在意系統總體的使用率的場景。 * 用什麼資料結構組織 runqueue?是 FIFO queue (linked list),還是 rb tree,還是 bitmap + FIFO queue,各種結構的優劣如何? * 使用什麼演算法?是用一個 while loop 去 O(N) 地遍歷來尋找最合適的任務,還是對於任意任務 round robin(weighted round robin)?Linux 2.6 O(1) 排程器使用什麼演算法?CFS (Completely Fair Scheduler) 為何又將其取而代之?對於目前大叢集下的 cluster scheduling,排程器如何處理,borg / mesos /omega 這些先後名噪江湖的算法是怎麼回事,該怎麼選用? ![](https://i.imgur.com/wg2RfUz.png) > 改寫自 [scheduling](https://zhuanlan.zhihu.com/p/33389178) 排程器主要功能是將系統中的 task 分派給個別 CPU 之上執行,並要滿足以下效能要求: 1. 對於 time-sharing 的行程,排程器必須公平; 2. 快速的行程反應時間 ([Response time](https://en.wikipedia.org/wiki/Response_time_(technology))) 3. 高 throughput; 4. 低功耗; 不同的應用場景就有不同的需求,因此我們需要對任務進行分類: * 普通行程 * 即時行程 對於即時行程,毫無疑問地,快且精準的反應時間的需求最為關鍵,而對於普通行程來說,該兼顧前 3 點。不難發現,上述這些需求互相衝突,對於這些 time-sharing 的普通行程如何平衡設計呢?於是又需要將普通行程細分為: * 交互式行程 (interactive processs) * 批處理行程 (batch process) 交互式行程需要和使用者互動,因而對排程器的延遲較為敏感,相較之下,批處理行程屬於在背景默默做事的執行單元,因而更注重 throughput。在 Linux 廣泛在移動裝置上採用後,排程器也往能源效率進行調整,於是有了 [Energy Aware Scheduling (EAS)](https://developer.arm.com/open-source/energy-aware-scheduling) ## 令人詬病的 Linux 2.4 排程器 回顧 Linux 2.4 排程器的設計,瞭解其傳承,同時以史為鏡。 ![](https://i.imgur.com/LvLrxIQ.png) Linux 2.4 排程器支持 SMP(Symmetric Multi-Processing),然而,由於只用一個 global runqueue,各個 core 需要競爭同一個 runqueue 裡面的任務,所以可延展性能力 (scalability) 不好。稍早提及的考量點: > 任務如何組織?是所有的資源共享一個任務的 runqueue,調度器調度時通過 locking 來保證互斥,還是針對每個資源,我們都為其設置一個 runqueue,以減少 lock 帶來的損耗?那麼問題又來了,如果某個資源上的任務列表空了,資源是就此閒置,還是可以去別的資源的 runqueue 上「偷」任務給自己執行? global runqueue 帶來的效能問題其實可忍受,畢竟只是在 dequeue 的過程需要 lock,但這個問題就很致命:Linux 2.4 排程器的時間複雜度是 $O(N)$。現代作業系統可運作成千上萬個行程,$O(N)$ 的時間複雜度意味著,每到排程之際,對於目前執行完的行程,需要將所有在 expired queue 中的行程存取過一遍,找到合適的位置插入。這不僅僅會帶來效能上的巨大損失,還使得系統的排程時間非常不確定 —— 根據系統的負載,可能有數倍甚至數百倍的差異。如此的不確定性 (non-determinism) 是資訊系統的障礙,尤其在即時處理的領域。 在 Linux 2.4 中,排程器維護兩個 queue: * runqueue * expired queue 這二者永遠保持有序,當一個行程耗盡時間片段 (time slice) 之際,就會被插入 expired queue;當 runqueue 為空時,只需要把 runqueue 和 expired queue 對調即可。 值得注意的是,排程系統的難點不在於尋找下一個可執行的行程,這個操作往往可達到 $O(1)$ 時間複雜度,因為我們只要妥善對 runqueue 排序,使其第一個行程永遠是下次需要調度的行程即可。難點在於執行完的行程該如何安插,才能確保 runqueue 的順序符合預期。 ## 符合 $O(1)$ 操作的資料結構 很多資料結構的操作,O(log N) 就是很好的表現,那 Linux 2.6 的 O(1) 排程器到底如何實現呢? 回答這個問題前,我們回顧以下資料結構的基本操作及其時間複雜度: * access (隨機存取) * array 是唯一能夠達到,且平均情況和最壞情況均能達到 $O(1)$ 隨機存取的資料結構; * 其它的資料結構,像是 linked list 是 $O(N)$,tree 一般是 $O(log N)$; * search (搜尋): * 也許你會先想到 hash table 作為 $O(1)$ 時間複雜度的實現。然而,它在最壞情況下是 $O(N)$; * 沒有任何演算法可確保在最壞情況下,search 依然是 $O(1)$; * 大部分 tree(B-tree, red-black tree)平均和最壞情況都是 $O(log N)$; * insert/deletion (插入和刪除) * 插入和刪除兩者是對等的操作,這裡一起探討。linked list, stack, queue 在平均和最壞情況下都是 $O(1)$,而上述 hash table 雖然平均是 $O(1)$,但最壞情況是 $O(N)$; * 大部分 tree(b-tree, red-black tree)平均和最壞情況都是 $O(log N)$ 不難發現,若要達成 $O(1)$ 排程器所需,操作只能包含純粹的 access, insert 和 deletion,但不得有 search。Linux 2.4 排程器在將執行完的行程 insert 回 expired queue 之際使用 search 操作,就大幅增長時間複雜度。此外,對於排程器的設計來說,儘量要選擇平均情況和最壞情況表現一致的演算法。若平均情況是 $O(1)$,最壞情況是 $O(n)$,那麼這個排程器會給系統帶來很大的不確定性。 綜合考量下,我們可選擇的範圍就很有限: * access 只能用 array; * insert/deletion 只能用 linked list, queue, stack; ## Linux 2.6 `O(1)` 排程器 我們思考以下排程場景: * 假設系統中有 6 個行程; * 具備 3 種優先權等級: high, medium, low * 沒有 preemption,嚴格按照優先權的順序執行行程 那麼,我們怎麼組合上述的資料結構,讓排程的操作達到 $O(1)$ 呢? ![](https://i.imgur.com/3KzQs8S.png) Linux 2.6 核心中,共有 140 種優先級,所以我們就用長度為 140 的陣列去記錄優先權級別。每個優先權下面用一個 FIFO queue 管理這個優先權下的行程。新來的插到隊尾,先進先出。在這種情況下,insert / deletion 都是 $O(1)$。 ![](https://i.imgur.com/nM1OlJA.png) > Priority Array 根據目前 140 個優先權等級 (`MAX_PRIO` = 140),為每個 Task Priority 配置對應的 queue head,並且用`unsigned long` 涵蓋這 140 個優先權等級,透過個別 bit 為 0 或 1,表示該 Task Priority 是否有需要被執行的任務在排程等待執行中 再來,怎麼找到目前最高優先級下面的可執行的行程呢?若從 0 開始一直遍歷下去,時間複雜度雖然不是 $O(N)$,但跟優先級多寡相關的 $O(M)$,也不能算作 $O(1)$。在 Linux 2.6 排程器中,開發者採用 bitarray,為每種優先權分配一個 bit,若這個優先權佇列 ([priority queue](https://en.wikipedia.org/wiki/Priority_queue)) 下面有行程,那麼就對相應的 bit 染色,置為 1,否則置為 0。這樣,問題就簡化成尋找一個 bitarray 裡面最高位是 1 的 bit(left-most bit),這在現代的處理器中,就是一道 CPU 指令: [Find first set/one](https://en.wikipedia.org/wiki/Find_first_set)。 > Linux 核心 API: [fls](https://www.kernel.org/doc/htmldocs/kernel-api/API-fls.html) ![](https://i.imgur.com/EeB2VmP.png) 大致的排程步驟如下: 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 交換; 當然,這裡面還有一些細節,比如如果是行程被搶佔,其時間片沒用完,那麼第 4 步,enqueue 回 active priority queue 中。 儘管 O(1) 排程器確實可消弭排程機制的不確定性,但單一處理器在同一時間只能執行一個任務,換言之,不考慮觸發中斷與重新觸發排程機制的情況下,目前任務的時間片段在尚未執行完畢前,其他的任務沒有機會執行,這導致我們無法細緻地排程。因此,在 Linux 2.6.23 後,引入新的 CFS (Completely Fair Scheduler) 排程機制,盡可能讓每個不同等級的任務得以更公平分配到處理器的時間,基於 RB Tree,讓越少被執行到的任務,得以有更高的機率被處理器挑選出來,從而避免優先級較低的任務,被延遲較久的時間,才有被處理器執行的機會。 在 Linux 核心的文件 [CFS Scheduler](https://www.kernel.org/doc/Documentation/scheduler/sched-design-CFS.txt),嘗試以一句話說明原理: > 80% of CFS's design can be summed up in a single sentence: CFS basically models an "ideal, precise multi-tasking CPU" on real hardware. 所謂理想的多工處理器,是當處理器有 100% 的能力,且系統中有兩個任務在運作,這兩個任務可各自取得處理器 50% 的執行能力,並被處理器平行執行。換言之,任意時間間隔來看 (例: 隨機取 10 ms 間隔),這兩個任務都具備分配到處理器 50% 的執行能力。 Linux 2.6 $O(1)$ 排程器已被更加強調公平性的 CFS取代,但其以獨特的設計,簡單的演算法,將 bitarray + priority queue 的組合展現核心演算法之美。 > 改寫自 [Linux O(1)](https://zhuanlan.zhihu.com/p/33461281) ## 排程器設計 複習 [不僅是個執行單元的 Process](https://hackmd.io/s/r1ojuBGgE) 取自 Donald E. Porter 教授的 [CSE 506: Operating Systems](http://www.cs.unc.edu/~porter/courses/cse506/) 教材 - [ ] [Scheduling](http://www.cs.unc.edu/~porter/courses/cse506/s16/slides/scheduling.pdf) ![](https://i.imgur.com/qlf9c7y.png) * cooperative multitasking: 協同式多工 * preemptive multitasking: 搶佔式多工 * 搶佔的機會 - System calls * Before, During, After - Interrupts * Timer interrupt: ensures maximum time slice - [ ] [Scheduling, Part 2](http://www.cs.unc.edu/~porter/courses/cse506/s16/slides/scheduling2.pdf) ## 涉及即時處理能力 - [ ] [Effectively Measure and Reduce Kernel Latencies for Real-time Constraints](https://elinux.org/images/a/a9/ELC2017-_Effectively_Measure_and_Reduce_Kernel_Latencies_for_Real-time_Constraints_%281%29.pdf) - [ ] [Using SCHED_DEADLINE](https://elinux.org/images/f/fe/Using_SCHED_DEADLINE.pdf) - [ ] [SCHED_DEADLINE: a status update](https://events.static.linuxfound.org/sites/events/files/slides/SCHED_DEADLINE-20160404.pdf) ## 待整理 * [Predictive CPU isolation of containers at Netflix](https://medium.com/netflix-techblog/predictive-cpu-isolation-of-containers-at-netflix-91f014d856c7)