英語

CFS 排程器

1. 概述

CFS 代表“完全公平排程器”，是由 Ingo Molnar 實現併合併到 Linux 2.6.23 中的“桌面”程序排程器。 最初合併時，它是對先前 vanilla 排程器的 SCHED_OTHER 互動性程式碼的替代。 如今，CFS 正在為 EEVDF 讓路，有關 EEVDF 的文件可以在 EEVDF 排程器 中找到。

CFS 的 80% 的設計可以用一句話概括：CFS 基本上在真實硬體上模擬了一個“理想的、精確的多工 CPU”。

“理想的多工 CPU”是一個（不存在的 :-））CPU，它具有 100% 的物理能力，並且可以以精確相同的速度並行執行每個任務，每個任務的速度為 1/nr_running。 例如：如果有 2 個任務正在執行，則它以 50% 的物理能力執行每個任務 --- 也就是說，實際上是並行執行。

在真實的硬體上，我們一次只能執行一個任務，因此我們必須引入“虛擬執行時間”的概念。 任務的虛擬執行時間指定了其下一個時間片將在上述理想多工 CPU 上開始執行的時間。 實際上，任務的虛擬執行時間是其實際執行時間，並已標準化為正在執行的任務的總數。

2. 一些實現細節

在 CFS 中，虛擬執行時間透過每個任務的 p->se.vruntime（納秒單位）值來表達和跟蹤。 這樣，就可以準確地對任務應該獲得的“預期 CPU 時間”進行時間戳和測量。

小細節：在“理想”硬體上，在任何時候，所有任務都將具有相同的 p->se.vruntime 值 --- 也就是說，任務將同時執行，並且沒有任務會因“理想”的 CPU 時間份額而“失去平衡”。

CFS 的任務選擇邏輯基於此 p->se.vruntime 值，因此非常簡單：它總是嘗試執行具有最小 p->se.vruntime 值的任務（即，到目前為止執行最少的任務）。 CFS 始終嘗試在可執行任務之間儘可能接近“理想的多工硬體”地分配 CPU 時間。

CFS 的其餘大部分設計都源於這個非常簡單的概念，並添加了一些額外的修飾，例如 nice 級別、多處理和各種演算法變體來識別睡眠者。

3. RBTREE

CFS 的設計非常激進：它不使用舊的資料結構用於執行佇列，而是使用時間排序的 rbtree 來構建未來任務執行的“時間線”，因此沒有“陣列切換”偽像（之前的 vanilla 排程器和 RSDL/SD 都受到影響）。

CFS 還維護 rq->cfs.min_vruntime 值，該值是一個單調遞增的值，用於跟蹤執行佇列中所有任務中最小的 vruntime。 系統完成的總工作量使用 min_vruntime 跟蹤； 該值用於將新啟用的實體儘可能放置在樹的左側。

執行佇列中正在執行的任務總數透過 rq->cfs.load 值來計算，該值是在執行佇列中排隊的任務的權重的總和。

CFS 維護一個時間排序的 rbtree，其中所有可執行的任務都按 p->se.vruntime 鍵排序。 CFS 從這棵樹中選擇“最左邊”的任務並堅持下去。 隨著系統向前推進，執行的任務越來越多地放置在樹的右側 --- 緩慢但肯定地讓每個任務都有機會成為“最左邊的任務”，從而在確定的時間內在 CPU 上執行。

總而言之，CFS 的工作方式如下：它執行一個任務一會兒，當任務排程（或發生排程程式滴答）時，任務的 CPU 使用率被“記錄下來”：它剛剛花費在物理 CPU 上的（少量）時間被新增到 p->se.vruntime。 一旦 p->se.vruntime 足夠高，以至於另一個任務成為它維護的時間排序 rbtree 的“最左邊的任務”（加上相對於最左邊的任務的少量“粒度”距離，以便我們不會過度排程任務並破壞快取），然後選擇新的最左邊的任務並搶佔當前任務。

4. CFS 的一些特性

CFS 使用納秒粒度記帳，並且不依賴於任何節拍或其他 HZ 細節。 因此，CFS 排程器沒有先前排程器那樣的“時間片”概念，也沒有任何啟發式方法。 只有一箇中心可調引數

/sys/kernel/debug/sched/base_slice_ns

可用於將排程器從“桌面”（即低延遲）調整為“伺服器”（即良好的批處理）工作負載。 它預設為適合桌面工作負載的設定。 SCHED_BATCH 也由 CFS 排程器模組處理。

如果 CONFIG_HZ 導致 base_slice_ns < TICK_NSEC，則 base_slice_ns 的值對工作負載幾乎沒有影響。

由於其設計，CFS 排程器不易受到當今針對庫存排程器的啟發式方法的任何“攻擊”：fiftyp.c、thud.c、chew.c、ring-test.c、massive_intr.c 都可以正常工作，並且不會影響互動性，並且產生預期的行為。

與之前的 vanilla 排程器相比，CFS 排程器對 nice 級別和 SCHED_BATCH 的處理要強得多：兩種型別的工作負載都被更積極地隔離。

SMP 負載平衡已被重新設計/清理：執行佇列遍歷假設已從負載平衡程式碼中刪除，並且使用了排程模組的迭代器。 結果，平衡程式碼變得簡單得多。

5. 排程策略

CFS 實現了三種排程策略

  • SCHED_NORMAL（傳統上稱為 SCHED_OTHER）：用於常規任務的排程策略。

  • SCHED_BATCH：不會像常規任務那樣頻繁地搶佔，從而允許任務執行更長時間並更好地利用快取，但以互動性為代價。 這非常適合批處理作業。

  • SCHED_IDLE：這甚至比 nice 19 還要弱，但它不是真正的空閒計時器排程器，以避免陷入優先順序反轉問題，這會使機器死鎖。

SCHED_FIFO/_RR 在 sched/rt.c 中實現，並且符合 POSIX 規範。

來自 util-linux-ng 2.13.1.1 的命令 chrt 可以設定所有這些，除了 SCHED_IDLE。

6. 排程類

新的 CFS 排程器被設計成引入“排程類”的方式，它是排程器模組的可擴充套件層次結構。 這些模組封裝了排程策略細節，並由排程器核心處理，而核心程式碼對此假設不多。

sched/fair.c 實現了上述 CFS 排程器。

sched/rt.c 以比之前的 vanilla 排程器更簡單的方式實現了 SCHED_FIFO 和 SCHED_RR 語義。 它使用 100 個執行佇列（對於所有 100 個 RT 優先順序級別，而不是先前排程器中的 140 個），並且不需要過期的陣列。

排程類透過 sched_class 結構實現，該結構包含每當發生有趣事件時必須呼叫的函式的鉤子。

這是（部分的）鉤子列表

  • enqueue_task(...)

    當任務進入可執行狀態時呼叫。 它將排程實體（任務）放入紅黑樹中，並增加 nr_running 變數。

  • dequeue_task(...)

    當任務不再可執行時，呼叫此函式以使相應的排程實體脫離紅黑樹。 它減少 nr_running 變數。

  • yield_task(...)

    除非啟用了 compat_yield sysctl，否則此函式基本上只是一個出隊後跟一個入隊； 在這種情況下，它將排程實體放置在紅黑樹的最右端。

  • wakeup_preempt(...)

    此函式檢查進入可執行狀態的任務是否應搶佔當前正在執行的任務。

  • pick_next_task(...)

    此函式選擇最適合接下來執行的任務。

  • set_next_task(...)

    當任務更改其排程類、更改其任務組或被排程時，將呼叫此函式。

  • task_tick(...)

    此函式主要從時間滴答函式呼叫； 它可能會導致程序切換。 這驅動正在執行的搶佔。

7. CFS 的組排程器擴充套件

通常，排程器對單個任務進行操作，並努力為每個任務提供公平的 CPU 時間。 有時，可能需要對任務進行分組併為每個這樣的任務組提供公平的 CPU 時間。 例如，可能需要首先為系統上的每個使用者提供公平的 CPU 時間，然後為屬於使用者的每個任務提供公平的 CPU 時間。

CONFIG_CGROUP_SCHED 努力實現這一目標。 它允許對任務進行分組，並在這些組之間公平地分配 CPU 時間。

CONFIG_RT_GROUP_SCHED 允許對即時（即 SCHED_FIFO 和 SCHED_RR）任務進行分組。

CONFIG_FAIR_GROUP_SCHED 允許對 CFS（即 SCHED_NORMAL 和 SCHED_BATCH）任務進行分組。

這些選項需要定義 CONFIG_CGROUPS，並允許管理員使用“cgroup”偽檔案系統建立任意的任務組。 有關此檔案系統的更多資訊，請參閱 控制組。

定義 CONFIG_FAIR_GROUP_SCHED 後，將為使用偽檔案系統建立的每個組建立一個“cpu.shares”檔案。 請參閱下面的示例步驟，以建立任務組並使用“cgroups”偽檔案系統修改其 CPU 份額

# mount -t tmpfs cgroup_root /sys/fs/cgroup
# mkdir /sys/fs/cgroup/cpu
# mount -t cgroup -ocpu none /sys/fs/cgroup/cpu
# cd /sys/fs/cgroup/cpu

# mkdir multimedia      # create "multimedia" group of tasks
# mkdir browser         # create "browser" group of tasks

# #Configure the multimedia group to receive twice the CPU bandwidth
# #that of browser group

# echo 2048 > multimedia/cpu.shares
# echo 1024 > browser/cpu.shares

# firefox &     # Launch firefox and move it to "browser" group
# echo <firefox_pid> > browser/tasks

# #Launch gmplayer (or your favourite movie player)
# echo <movie_player_pid> > multimedia/tasks