Try   HackMD

Linux 核心專題: 排程器研究

執行人: YangYeh-PD
專題解說影片 (2024.06.29)

任務簡介

  1. 檢閱學員對於 Linux 核心 CPU 排程器的分析，確認其內容的正確，適度提出疑惑和參與討論。
  2. 重現《Demystifying the Linux CPU Scheduler》第 7 章的實驗。

TODO: 閱讀《Demystifying the Linux CPU Scheduler》

問題紀錄

  1. 我們知道在 Linux 核心要求 Source Program 在把任務交給 Scheduler 之前，一定要標示好任務的類型(比如緊急與否)。那麼把一個任務歸類在 Scheduling Class 的時候，到底是由 Source Program 本身定義出來的還是由 Scheduler 識別出來的？
  2. 為何 SCHED_IDLE 屬於 idle_sched_class, 兩者差別在哪裡?

在 yenslife 的排程器研究當中有提到，scheduling class 和 scheduling policies 的差異在於，前者用來區分優先權，後者則是排程的方法。

  1. sleep 在早期 Linux 核心排程器有什麼用途? 為何這項行程與 interactivity 有關聯?

第 2 章: Linux 核心的 CPU 排程器

一個 CPU Scheduler 需要考慮的特性

CPU 排程器在搶占式多工和非搶占式多工系統中都扮演著重要角色。

  • 在搶占式多工系統中，排程器允許作業系統強行中斷正在運行的行程，並將 CPU 分配給其他行程。這確保所有行程都能獲得公平的 CPU 時間，並提高系統的響應性。
  • 在非搶占式多工系統中，當一個行程被創建時，它會被放置在 runqueue 中。然後排程器會從中選擇一個行程。






shuffle



scheduler1

scheduler



node1

task1



scheduler1->node1





head1

head



head1->node1





tail1

tail



node5

task5



tail1->node5





node2

task2



node1->node2





node3

task3



node2->node3





node4

task4



node3->node4





node4->node5
Interactive v.s. Throughput

為何排程器往往需要在 interactiveness 與 throughput 之間做取捨？如果想要提升作業系統的互動性 (interactive)，那就要進行搶佔式多工。而這種搶佔式多工當中的 context switch 會造成 CPU 短時間閒置，因此就會降低 throught。

Fairness and Liveness

Fairness 意指具有相同優先級的任務應該獲得相等的 CPU 時間。然而，僅有 fairness 是不夠的。如果一個高優先級的任務持續佔用 CPU，其他任務將無法執行。因此，Liveness 的設計變得至關重要。Liveness 能確保每個任務在一定時間內獲得 CPU 資源。通過 Liveness，即使是需要完成的低優先級任務也能得到執行。

Realtime (RT)

Realtime 分為兩種類型：Soft real-time 以及 Hard real-time。

  • 在 Soft real-time 中，如果一個進程在超過截止時間後仍未被處理，後果並不嚴重。最常見的例子是音頻和視頻不同步。
  • 在 Hard real-time 中，如果一個進程在超過截止時間後仍未被處理，可能會導致嚴重後果，甚至可能導致系統崩潰。
Power Efficiency

Linux CPU 會根據不同的平台採用不同的節能方法。在桌機和筆記本電腦上，主要有兩種節能策略

  • 優先處理低功耗任務，如閒置任務或低優先級任務。
  • 根據工作負載調整 CPU 頻率。當工作負載較輕時，降低頻率以節省能源。

在伺服器中，由於系統需要連續運行，因此在 Throughput 和功耗之間尋求平衡是至關重要的。

  • 優先處理 CPU 密集型任務，以提高 cache（包括時間和空間方面）和處理器之間的效率。
Working Pattern

所以排程器如何知道哪些任務需要優先執行呢？Linux 核心直接要求 Source Program 在將任務交給排程器進行調度之前指定優先級。Linux 核心使用 Scheduling Classes 的概念來實現任務調度。現在的核心版本中，有五種不同的調度類別。







shuffle



node1

Stop



node2

Deadline



node1->node2





node3

Real-Time



node2->node3





node4

Fair



node3->node4





node5

Idle



node4->node5
Scheduling classes Scheduling Policies
stop_sched_class
dl_sched_class SCHED_DEADLINE
rt_sched_class SCHED_FIFO&SCHED_RR
fair_sched_class SCHED_NORMAL&SCHED_BATCH&SCHED_IDLE
idle_sched_class
  • Stop 是用來停止 CPU 任務的，僅適用於對稱多處理器（SMP）系統。它包括一種機制，可以停止在特定 CPU 上運行的行程並將其遷移到另一個 CPU。
  • Deadline 類型的任務必須在規定的截止時間內完成。使用此策略的任務會定義一個截止時間，在該時間之前任務必須完成執行。
  • 在 rt_sched_class 當中，有兩種 scheduling policy，分別是 SCHED_FIFO 和 SCHED_RR，這兩者非常相似。
    • 在 SCHED_FIFO 中，FIFO 代表 First in First Out。因此任務按照到達的順序執行。然而，如果有更高優先級的任務需要執行，它將被優先執行。
    • SCHED_RR（round robin）與 FIFO 相似，但區別在於 RR 有 timeslice。它使用輪轉的方法循環調度所有具有相同優先級的任務。每個任務只能運行一個最大固定時間片。這會讓排程更具有 Liveness 的特性。
  • SCHED_NORMAL 和 SCHED_OTHER 是用於普通任務的 scheduling policy，會使用 CFS（Completely Fair Scheduler）排程。SCHED_BATCH 與 SCHED_NORMAL 相似，但它會更少地搶占 CPU 的資源。
  • SCHED_IDLE 用於非常低優先級的任務，幾乎任何任務都可以搶占使用此策略的任務。

早期的 Linux 核心排程器

在 Linux 核心的 v0.01 版本中，所有任務都通過一個 array 表示。這個 array 不僅是所有任務的列表，也是 runqueue。這個 array 的長度為 NR_TASKS，即 64。空條目表示為 NULL。







G



1


  runnable 10 


  runnable 15 


  NULL 


  runnable 5 


  sleep 12

其演算法很簡單

  1. 逆向走訪整個 array，調度第一個可運行且具有最大 timeslice 的行程。
  2. 如果沒有這樣的進程，那就會重置所有任務的 timeslice，並將當前 timeslice 的一半添加到休眠任務的 timeslice 中。






G



1


  runnable 10 


  
runnable 15
    


  NULL 


  runnable 5 


  sleep 12 










G



1


  
runnable 10
    


  runnable 0 


  NULL 


  runnable 5 


  sleep 12 










G



1


  runnable 0 


  runnable 0 


  NULL 


  
runnable 5
    


  sleep 12 










G



1


  runnable 0 


  runnable 0 


  NULL 


  runnable 0 


  sleep 12 










G



1


  runnable 15 


  runnable 15 


  NULL 


  runnable 15 


  sleep 20

這個過程會不斷進行，直到任務完成時，它就會離開 array，並將該元素設置為 NULL。

O(n) 排程器

在這個階段，所有任務都存在一個連結串列當中。當 Linux 需要選擇一個任務進行執行時，它會走訪每個任務，並為每個任務給予一個 goodness score。得分最高的任務將會獲得 CPU 資源。當任務的執行時間耗盡時，它就會被搶占，然後 CPU 會運行另一個任務。







shuffle



node0




node2

task2



node0->node2





node1

task1



node1->node2





node3

task3



node2->node3





node4

task4



node3->node4





node5

task5



node4->node5

TODO: 檢閱學員對於 Linux 核心 CPU 排程器的分析

探討以下:

在上方開發紀錄提出你的疑惑並參與討論。

Linux 核心專題: CPU 排程器研究 (Kuanch, devarajabc)

  • 針對《Demystifying the Linux CPU Scheduler》第 2 章排程器的 Response Time (Interactive) 與 Throughput 做補充。

為何 Response Time 與 Throughput 需要做取捨?
如果想要提升作業系統的互動性 (interactive)，那麼每當使用者輸入指令的時候，CPU 都需要立刻暫行當下執行的任務，並且切換到其他任務回饋給使用者。這是搶占式多工 (preemptive multitasking) 的例子。在 《Demystifying the Linux CPU Scheduler》34 頁有提到

Every time the scheduler determines to context switch, the CPU becomes idle and are unoccupied by any task.

因此，會降低 throughput 的原因是 context switch 當中造成 CPU 短時間閒置，任務被打斷是表面原因。

  • 提出建議，比較 FIFO 與 RR 兩者 Scheduling Policy 的差異，並探討其 Fairness 與 Liveness。

Fairness 意思是相同優先權的任務會享有相同的 CPU 時間。
Liveness 意思是每個任務，無論優先權高低，最終都會得到 CPU 的資源。

由於兩者 Scheduling Policy 都是優先權高先執行，享有 CPU 的資源比較多，因此在 Fairness 上，兩者表現一樣。

而由於 RR 每隔一個 timeslice 就會切換一次任務，就能夠讓比較低優先權的任務更有機會執行， Liveness 的特性比較好。而因為 FIFO 在執行完一個任務後才會接續執行下一個任務，因此 Liveness 的特性與 RR 相比，就沒那麼好。

  • 在探討 Task Migration 的時候有提到因為在 UMA 的設計裡每個 CPU Core 存取每個記憶體的時間是一樣的，因此遷移成本可能遠小於 NUMA。 但我持不同的觀點。

NUMA 雖然會提高 migration 的成本，但因為在 NUMA 可以涵蓋到大量的處理器，每個處理器會比其他處理器更接近某些記憶體，讓記憶體存取速度比其他部分更快速，因此在高效能運算系統也很常見。因此UMA + NUMA 的混和版本是否會犧牲掉這點，也應該考慮。

Linux 核心專題: CPU 排程器研究 (yenslife)

  • 回答同學在 Stop-task 上 task migration 的疑問。

如果今天系統負載較低，它會關閉任意 secondary CPU，以降低能源消耗。在關閉該 CPU 之前，一定會執行 Stop-Task 類別的任務。如果你關閉的那顆 CPU 上面剛好在執行其他任務，那 stop-task 就需要把上面的任務 migrate 到其他 CPU 完成，因此需要任務遷移。

TODO: CPU 排程器實驗重現

重現《Demystifying the Linux CPU Scheduler》第 7 章的實驗。

  • Same Nice v.s. Different Nice
  • FIFO v.s. RR Scheduling Policy

開發環境

$ gcc --version
gcc (Ubuntu 13.2.0-4ubuntu3) 13.2.0

$ uname -mrs
Linux 6.5.0-41-generic x86_64

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
    CPU family:          6
    Model:               142
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            10
    CPU(s) scaling MHz:  36%
    CPU max MHz:         3400.0000
    CPU min MHz:         400.0000
    BogoMIPS:            3600.00
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   128 KiB (4 instances)
  L1i:                   128 KiB (4 instances)
  L2:                    1 MiB (4 instances)
  L3:                    6 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-7

事前準備工作

  1. 更新 Linux 至版本 6.1 或更高版本。
    在 Linhoward0522 的排程器研究中，有相關的操作說明。
  2. 下載 Scheduler Analyzer
    需要前往 sched-analyzer 下載。在生成 trace file 以後，我們可以將其放到 Perfetto 從而視覺化排程器的行為。

FIFO v.s. RR Scheduling Policy

本實驗旨在展示 FIFO 和 RR 調度策略之間的差異。這兩種策略都屬於 real-time 的 scheduling class。為了詳細介紹這兩種 scheduling policy，我會進行三個實驗。

  1. 展示 FIFO 和 RR 在相同優先權任務下的排程狀況
    我們預期在 FIFO 策略下，每個任務只有在前一個任務終止後才會被選擇執行；而在 RR 策略下，每個任務在前一個任務超過給定的 timeslice 以後都有機會執行。我將會使用以下 configuration file。
{
    "proc": [
        {
            "comm": "cpu_bound",
            "cpus": "3",
            "name": "fifo",
            "policy": "fifo",
            "policy_detail": "99",
            "spawn_cnt": 3
        },
        {
            "comm": "cpu_bound",
            "cpus": "2",
            "name": "rr",
            "policy": "rr",
            "policy_detail": "99",
            "spawn_cnt": 3
        }
    ]
}
  1. 展示 FIFO 和 RR 在不同優先權任務下的排程狀況
    因為所使用的任務優先權必須不同，因此須給每個不同優先權的任務寫 configuration file。
{
    "proc": [
        {
            "comm": "cpu_bound",
            "cpus": "3",
            "name": "low priority (fifo)",
            "policy": "fifo",
            "policy_detail": "97"
        },
        {
            "comm": "cpu_bound",
            "cpus": "3",
            "name": "medium priority (fifo)",
            "policy": "fifo",
            "policy_detail": "98",
            "spawn_cnt": 2
        },
        {
            "comm": "cpu_bound",
            "cpus": "3",
            "name": "high priority (fifo)",
            "policy": "fifo",
            "policy_detail": "99"
        },
        {
            "comm": "cpu_bound",
            "cpus": "2",
            "name": "low priority (rr)",
            "policy": "rr",
            "policy_detail": "97"
        },
        {
            "comm": "cpu_bound",
            "cpus": "2",
            "name": "medium priority (rr)",
            "policy": "rr",
            "policy_detail": "98",
            "spawn_cnt": 2
        },
        {
            "comm": "cpu_bound",
            "cpus": "2",
            "name": "high priority (rr)",
            "policy": "rr",
            "policy_detail": "99"
        }
    ]
}
Last changed by 
 
sysprog
System Software Programming
0
416
Published on HackMD