Linux內核使用完全公平調度器（CFS）作為其主要的進程調度算法，旨在以公平的方式分配CPU時間給所有進程。CFS通過以下幾個關鍵機制實現其目標：
-
虛擬運行時間（vruntime）：
- 每個進程都有一個虛擬運行時間，用于記錄該進程已經占用的CPU時間。
- 虛擬運行時間的增長速度根據進程的nice值（優先級）動態調整，nice值越低（優先級越高），vruntime增長越慢，反之則越快。
- 這樣，無論進程的優先級如何，CFS都能確保所有進程在長期內獲得與其權重成比例的CPU時間。
-
紅黑樹結構：
- CFS使用紅黑樹來維護就緒隊列，紅黑樹是一種自平衡的二叉查找樹，按vruntime排序。
- 最小的虛擬運行時間位于樹的根節點，調度器會優先選擇根節點中的進程執行。
-
搶占式調度：
- Linux內核采用搶占式調度，即使某個進程正在運行，內核也可能中斷該進程的執行，將CPU分配給其他更需要執行的進程。
- 這是通過時鐘中斷和優先級來實現的。如果一個高優先級的進程進入就緒隊列，Linux會搶占當前正在執行的進程，立即將CPU分配給優先級更高的進程。
-
時間片和優先級：
- 每個進程都有一個時間片，表示它連續占用CPU的最大時間。時間片用完后，內核會將當前進程放回就緒隊列，并調度下一個進程運行。
- 每個進程還有一個優先級，可以影響進程調度的順序。高優先級的進程通常會優先執行。
- Linux使用動態優先級調度策略，優先級可以根據進程的行為動態調整。
-
進程組支持：
- CFS支持按進程組分配和管理CPU份額的功能，這種技術在Linux內核中稱為控制組（cgroup）。
- 通過cgroup，調度器能夠管理進程組占用的資源，包括CPU資源。
-
實時調度策略：
- CFS還支持實時調度策略，如SCHED_FIFO（先進先出）和SCHED_RR（時間片輪轉），這些策略適用于對時間敏感的應用。
通過這些機制，CFS確保了所有進程都能公平地訪問CPU資源，同時兼顧了系統的響應性和效率。
