本文意在透過閱讀 Linux 核心程式碼理解 CPU Scheduler 機制，並配合 Linux 核心設計: Scheduler 系列 補充以及記錄我個人的疑問和心得。 以下程式碼為 Linux 核心 v6.8-rc7 版本，本篇專注於 EEVDF。 由於 EEVDF 中存在許多基於 CFS 的機制，如 nice level 以及 vruntime，本文在說明這些機制時將以 CFS 角度說明，若不了解 CFS 以及 EEVDF 機制，建議先行閱讀 Demystifying the Linux CPU Scheduler 閱讀筆記 2024。 後續發現，由於 EEVDF 近日才被引進，許多改進仍在進行中，建議讀者在有一定理解後可以參考 Yiwei Lin 以 Patch 追蹤的方式來跟進和驗證 EEVDF 之實作。 為了編撰 Demystifying the Linux CPU Scheduler 用於紀錄我對 EEVDF Patches 的理解 :EEVDF notes

This is a note to record my understanding of EEVDF, for the writing of 《Demystifying The Linux CPU Scheduler》 The difference Between CFS and EEVDF CFS focus on fairness, EEVDF take the latency into consideration. In other words, some tasks require great interactivity, they need to have CPU more frequently compared to other more "latency-sensitive". Pratically, we first found eligible tasks, by examining their vruntime and pick the one with smallest deadline. Because we can control the amount of increasing deadline each time a task run, by "latency-nice" and "nice values"

"Demystifying the Linux CPU Scheduler" 是 Linux 核心設計/實作 之課程教材，由授課老師黃敬群 (Jserv) 以英文編撰，以 CPU 排程器為主題，約 260 頁，仍未公開出版，更多資訊請關注課程行事曆或其粉絲專頁 Jserv與他愉快的小夥伴 。 本文大多數內容撰寫於 v6.8 之前，故以 CFS 以及其相關功能為說明重點；我的另一篇筆記嘗試閱讀 v6.8 之後以 EEVDF 為主的 Linux 核心排程器，歡迎指教參考。 目前受 Jserv 指導新增/修改 2.4 EEVDF Scheduler 一章內容。 已知的其他閱讀筆記： 閱讀 Demystifying The Linux CPU Scheduler (到第 3 章) 紀錄問題 (devarajabc) Demystifying the Linux CPU Scheduler 閱讀筆記 (linhoward0522)

本文旨在記錄 Computer Systems: A Programmer's Perspective (CS:APP) 一書第六章閱讀心得，該書是 CMU 的計算機系統概論的教材 (難度相當於台灣的大學高年級)，該書的簡體中文翻譯名稱為《深入理解計算機系統》。 CS:APP 亦是 Linux Kernel Internals 2024 Spring 課程指定教材，並一同收錄於 Linux Kernel Internals 2024 Spring Collections。 在本章之前，CS:APP 專注討論 CPU 計算架構，如指令的執行、暫存器的存取等，並將記憶體簡化為一簡單線性的矩陣，但顯然與現代系統運作的方式相去甚遠；如同讀者所知，現代記憶體系統是一層級化 (hierarchical) 的結構，如 L1 L2 L3 以及主記憶體等，而每層有其取用的成本以及限制。 作為程式開發人員，了解記憶體對系統性能的衝擊是很必要的，因取用 register 僅需 0 cycle、cache 從 4 到 75 cycles 不等，而存取主記憶體可能需要上百個 cycles。 本章會聚焦 CPU 與主記憶體的互動，因為其是最頻繁存取也最耗費 cycles 的裝置之一，並且討論如何分析、改進 C programs 的 cache locality 等。

本文旨在記錄 Computer Systems: A Programmer's Perspective (CS:APP) 一書第七章閱讀心得，該書是 CMU 的計算機系統概論的教材 (難度相當於台灣的大學高年級)，該書的簡體中文翻譯名稱為《深入理解計算機系統》。 CS:APP 亦是 Linux Kernel Internals 2024 Spring 課程指定教材，並一同收錄於 Linux Kernel Internals 2024 Spring Collections。 9.7 Case Study: The Intel Core i7/Linux Memory Syste 9.7.2 Linux Virtual Memory System 下圖為 Linux 行程當中記憶體配置的示意圖： image

Instructor: Jim Huang (黃敬群) jserv.tw@gmail.comSyllabus/Schedule: https://wiki.csie.ncku.edu.tw/linux/schedule This is a collection of the course materials and assignments for the course Linux Kernel Internals 2024 Spring at National Cheng Kung University. :::info [name=Kuanch] This course has been concluded on July 7, however, the content on this page will be updated regularly. You might be also interested on my degree essay about Point Cloud Segmentation 2DDATA and Image and Point Cloud Misamatch (SNPD 2023).

本文旨在記錄 Computer Systems: A Programmer's Perspective (CS:APP) 一書第七章閱讀心得，該書是 CMU 的計算機系統概論的教材 (難度相當於台灣的大學高年級)，該書的簡體中文翻譯名稱為《深入理解計算機系統》。 CS:APP 亦是 Linux Kernel Internals 2024 Spring 課程指定教材，並一同收錄於 Linux Kernel Internals 2024 Spring Collections。 本章一開始就介紹了三種常見的並行方法，並在以下三節介紹 12.1 Concurrent Programming with Processes /* * echoserverp.c - A concurrent echo server based on processes

在前篇 Review with code: Linux Scheduler 閱讀筆記 (1) 我們提及了 sched_fork()，又再往上追溯到了 kernel_clone()，那又是被誰呼叫的呢？ 第一個行程 (PID = 1) 是怎麼產生的？CPU Scheduler 又是怎麼被初始化的？我們嘗試回答以上問題，以便對 Linux CPU Sceheduler 有更深的了解。 以下程式碼為 Linux 核心 v6.8-rc7 版本。 Call Hierachy 我們大概都知道 bootstrap 的流程大概是 BIOS -> MBR -> boot loader -> kernel，前三者多是硬體主導，而載入 Kernel 後才是我們現在關心的；我們知道 boot loader 會載入 kernel，kernel 會將自己放到記憶體後開始一連串的初始化以及測試，也就是作業系統了，要回答開頭的問題，我們能夠由此下手。 以下我們此 call hierachy 開始理解，從 start_kernel() 到我們熟知的 kernel/sched/fair.c 中的 _fair() 函式：

contributed by < Kuanch > :::spoiler lscpu $ lscpu lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian Address sizes: 39 bits physical, 48 bits virtual

volatile volatile 用於告訴編譯器每一次存取該變數都需要從記憶體讀取，而非暫存器，也就是說在使用前一定會有 load memory (mov in x86, lw in RISC-V) 的指令發生，考慮以下程式碼： #include <stdio.h> int main(void) { const int local = 10; int *ptr = (int *)&local;

Linux Kernel Internals 2024 Spring Overview Assigment 1 Assigment 2 Assigment 3 Assigment 4 Assigment 5 Assigment 6 Term Project Prerequisite Linux 核心專題: CPU 排程器研究

contributed by < Kuanch > Linux 核心模組原理 What is a Kernel Module? 參閱 "The Linux Kernel Module Programming Guide"，一個核心模組 (kernel module) 最重要的特色是能夠被動態載入、在不重新開機的狀況下擴展核心功能： A Linux kernel module is precisely defined as a code segment capable of dynamic loading and unloading within the kernel as needed. These modules enhance kernel capabilities without necessitating a system reboot. 更完備的理解是，在不影響當前核心運作的狀況下掛載新的模組、動態擴充核心；另外，如果每一次功能的新增都需要被加入到 kernel image，不可避免的會導致擁腫的核心、增加重新編譯核心以及重新佈署系統的成本。

本文旨在記錄 Computer Systems: A Programmer's Perspective (CS:APP) 一書第七章閱讀心得，該書是 CMU 的計算機系統概論的教材 (難度相當於台灣的大學高年級)，該書的簡體中文翻譯名稱為《深入理解計算機系統》。 CS:APP 亦是 Linux Kernel Internals 2024 Spring 課程指定教材，並一同收錄於 Linux Kernel Internals 2024 Spring Collections。 7.1 Compiler Drivers 我們知道常說的 compiling 事實上是指 Compiler Driver 的一系列工作，即將 C 轉換成可執行檔的多個過程，包含 C compiler 將 C 翻譯為 asm code assembler 將 asm code 翻譯為 binary code

contributed by < Kuanch > Reviewed by Lccgth 佇列實作部分應只貼出關鍵程式碼，例如 q_merge 中可省略變數宣告的程式碼，以文字敘述。 for (struct list_head *p = head->next->next; p != head; p = p->next) { queue_contex_t *node = list_entry(p, queue_contex_t, chain); list_splice_init(node->q, merged_list->q); } q_sort(merged_list->q, descend);

cfs_rq /* CFS-related fields in a runqueue */ struct cfs_rq { struct load_weight load; unsigned int nr_running; unsigned int h_nr_running; /* SCHED_{NORMAL,BATCH,IDLE} */ unsigned int idle_nr_running; /* SCHED_IDLE */ unsigned int idle_h_nr_running; /* SCHED_IDLE */ s64 avg_vruntime;

contributed by < Kuanch > Week 3 Quiz Week3 Quiz Quiz 1 - Bitwise Square 首先應為 $a_i = b_i2^i$，故任何整數 $N$ 可寫作 $$ N = b_02^{32}+b_12^{31}+...+b_{30}2+b_{31} = (a_{32}+a_{31}+a_{30}+...+{a_0}) $$

contributed by < Kuanch > Week 1 Quiz - Linked List Week1 Quiz Quiz 1 - Head Linked List hlist_node 解釋程式碼 快速排序法為以指定值 pivot 為界，將小於和大於 pivot 的數值分開至左右側，再對左右側進行排序；因其明顯的分治特性 (divide and conquer)，通常以遞迴方式實作；若改以迭代方式實作，其外圈迭代應取代每一次遞迴，亦即分割出左右側後，再分別分割左側、右側，故如何儲存左右側會是其重點。 此處我們使用 begin 及 end 不僅儲存左右側，同時也儲存 pivot，且依照 left pivot right 的小中大順序儲存，每一次分割後先對 right 再分割，再對 left 再分割，每一次分割為一次迴圈。

contributed by < Kuanch > 期末專題提案 希望能夠進行 排程器研究，尤其是 Energy Aware Scheduling (EAS) 或 EEVDF針對 EAS，發現有同學留下相關資料 Linux 核心設計: Scheduler(8): Energy Aware Scheduling，此系列源自於 Linux 核心設計: 不只挑選任務的排程器，並延伸探討 Completely Fair Scheduling (CFS) 至 EEVDF 及 EAS。 一個可能的專案進行方式是繼續更新、補完該系列文章，因不可避免的要閱讀、理解其所有參考資料；缺點是目前不清楚該系列文章分析的深度與廣度，具體要如何更深入探討仍待研究。 實作高效記憶體配置器

CPU scheduling 對系統的影響 本節說明如何評估一個 scheduling 的效能： 原理是兩個行程相互 pipe，排程器夾在其間來回奔波。 想像兩個行程互相丟球(資源的轉移)，一旦排程器跟上球便拋給另一行程，而排程器追著球跑，如此我們就可以測量出排程器的速度(效能)。 :::info [name=Kuanch]

本文是綜合閱讀 Linux 核心設計: 不只挑選任務的排程器 Demystifying the Linux CPU Scheduler (課程內部教材) Linux 核心設計: Scheduler 之筆記，記載閱讀過程中的疑問與心得。 這系列文章寫在 2024/4，在開展 Linux 核心設計/實作 2024 期末專題之前，其中觀點和心得可能有誤，請小心服用。