# 2025q1 Homework1 (ideas)
contributed by < [yy214123](https://github.com/yy214123) >

## Linux 核心專題: CPU 排程器
> 執行人 ： var-x
[開發紀錄](https://hackmd.io/@sysprog/BJdyxvxX0)
[講解影片](https://www.youtube.com/watch?v=G6p0Y9DZJsM)

### 筆記
> [並行程式設計](https://hackmd.io/KQ_5E9XZQzm1GUhEAhxqPg)
[Demystifying the Linux CPU Scheduler](https://hackmd.io/@yy214123/rkW9ioGRJe)
[LKMPG 筆記](/FZNwMtx-ToK6Ukd5K9aF5g)

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

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

以時間複雜度來說 CFS 並沒有優於 $O(1)$ 排程

### 教材： [Linux 核心設計: 不只挑選任務的排程器](https://hackmd.io/@sysprog/linux-scheduler)
在教材中題到了兩個命令可用於監看效能：

$ 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 又可以包含單一執行緒或多執行緒