2025q1 Homework1 (ideas)

contributed by < yy214123 >

Linux 核心專題: CPU 排程器

執行人 ： var-x
開發紀錄
講解影片

在論文 Machine Learning for Load Balancing in the Linux
Kernel 的提到了 Linux 核心排程的演進史：

時期	排程演算法
舊代	$O(n)$
中期	$O(1)$
現代	CFS

以時間複雜度來說 CFS 並沒有優於

$O(1)$ 排程

教材： Linux 核心設計: 不只挑選任務的排程器

在教材中題到了兩個命令可用於監看效能：

$ perf bench sched pipe                                      ok  07:00:49 AM 
# Running 'sched/pipe' benchmark:
# Executed 1000000 pipe operations between two processes

     Total time: 12.657 [sec]

      12.657793 usecs/op
          79002 ops/sec

$ taskset -c 0 perf bench sched pipe               TSTP  10s  %  07:03:37 AM 
# Running 'sched/pipe' benchmark:
# Executed 1000000 pipe operations between two processes

     Total time: 2.529 [sec]

       2.529580 usecs/op
         395322 ops/sec

可以看到 taskset 來的快上許多，使用 htop 觀察各核心負載時可以發現，前者會將負載打散到多個核心中，後者會幾乎都在同個核心上執行，對應到以前學習作業系統時，這就是所謂 cpu affinity 的體現。

排程的基本單位：scheduling entity(包括行程、執行緒)
階層：
Session 可以包含多個 Process Group
Process Group 又可以包含多個 Process
Process 又可以包含單一執行緒或多執行緒