Linux 核心設計: Scheduler(9): Deadline Scheduling

Real-time System Overview

即時作業系統(Real-time operating system) 是作業系統中的一類。其特性是必須在精確的時間限制內對事件做出反應。因此首要目標不是高的吞吐量(throughput)，而是保證任務的延遲，使得以在特定時間內完成。

Ref: Deadline Scheduler - From theory to your server

根據對截止時間的要求，即時系統可再分為 soft real-time 和 hard real-time 兩類:

• Soft real-time: 系統盡可能在時限內完成請求(request)，未在時限內完成的回應(response)可能品質不佳，但不至於被視為是致命的錯誤
• Hard real-time: 對請求的回應不但要求邏輯結果正確，還必須是在截止時間完成，否則該系統被視為是有錯誤的

Linux Realtime Schedulers

Scheduling Policies

在 Linux 中具備對 soft real-time 的支援，可以在分時(Time-sharing) 任務並存的情況下，滿足有 real-time 要求的任務。具體的核心排程策略在 sched 文件中的 "Scheduling policies" 一節對有詳盡的說明。總結而言，每一個任務會被關聯到一種排程策略(Scheduling policy)。根據是否為 real-time 的排程，在 Linux 下可分為以下兩類:

• Normal scheduling policies: 又可以分為 SCHED_OTHER、SCHED_IDLE 和 SCHED_BATCH 三種。這類任務沒有優先級的區別，任務會根據權重以分時方式共享 CPU
• Real-time policies: 又可分為 SCHED_FIFO 與 SCHED_RR、SCHED_DEADLINE 三類。
  • SCHED_FIFO 與 SCHED_RR 屬 fixed-priority scheduler，即每個任務會被定義排程優先級(Scheduling priority)
  • SCHED_DEADLINE 中的任務優先級是根據 deadline 的差異動態調整，詳細在後續內容說明

排程是搶佔式(preemptive)的。如果一個有更高的優先等級的任務是準備運行狀態，則當前的任務將被搶佔並回到 runqueue 中等待。

補充說明: Linux 中的 PREEMPT_RT 分支有對 hard real-time 的支援，該系列改動原本在主分支之外分別維護，但在 6.12 版本的核心正式被上游採納。

本文只先針對 soft real-time 進行說明。

Realtime Scheduler Overview

在如 Linux 這樣的多任務(Multitasking)的作業系統中，有 Realtime scheduler 負責協調對 CPU 資源的使用，以確保系統中的所有 real-time 任務在限期內完成。Linux 中提供了兩種 Realtime scheduler：POSIX Realtime scheduler 和 Deadline scheduler。

POSIX realtime scheduler 包含 FIFO 和 RR 兩種排程策略(scheduling policy)。在這些策略下，每個任務具有一個優先等級值 sched_priority，後者可為 1(最低)到 99(最高)。而等級較高的任務將首先獲得排程。FIFO 和 RR 策略之間的差異只在有兩個任務具有相同優先等級時體現:

• 在 FIFO 中，最先加入 runqueue 的任務將獲得 CPU，一直運行到進入睡眠狀態
• 在 RR 中，有相同優先級的任務將輪流分享 CPU

與此相對，deadline scheduler 是根據任務的完成期限進行排程，動態調整任務之間的先後順序。截止日期最早的任務將首先得到服務。依此策略排程的任務具有三個參數影響排程器的選擇:

• sched_period: 指 realtime 任務的運作模式(pattern)。舉例來說，如果一個影像的處理任務必須每秒處理 60 幀，即每 16 毫秒就會有一個新幀到達，因此 period 應為 16 毫秒。
• sche_runtime: 指任務產生結果所需的 CPU 時間。Runtime 必須是最壞情況執行時間（worst-case execution time , WCET）。例如，在最壞的情況下，影像處理任務可能需要五毫秒，因此對應的此參數是五毫秒。
• sched_deadline: Deadline 是任務必須交待結果的最長時間。例如，如果任務需要在十毫秒內交付處理後的幀，則 Deadline 為十毫秒。

在 Linux 上的 deadline scheduler 是基於 Earliest Deadline First (EDF) 的演算法，並結合 Constant Bandwidth Server(CBS) 來達到任務之間的隔離。詳細會在後續章節中討論。

目標上，SCHED_DEADLINE 任務應該每 sched_period ms 獲得 sched_runtime ms 的執行時間，且這些sched_runtime ms 要在週期開始後的 sched_deadline ms 中取得。為了達到此目的，每次任務喚醒時，排程器都會使用 CBS 計算任務的截止時間。然後在截止時間上使用 EDF 來進行任務的排程（選擇並執行具有最早截止時間的任務）。

與靜態優先級的排程方式相比，雖然 deadline scheduler 看起來很複雜，但這種方式使得使用者只需提供任務自身的參數設定，即可確保在截止日期之前得到結果，而無需了解系統中其他任務的情況。相對的，在依賴靜態優先級的 realtime scheduler 下，使用者必須考慮系統的所有任務，才便選擇任務的優先等級值以指派正確的先後順序。

甚者，由於 deadline scheduler 知道每個任務需要多少 CPU，因此可以計算系統何時及可否接受新任務，避免使用者讓系統過載，從而保證當前所有 SCHED_DEADLINE 任務有足夠 CPU 時間完成目標。

Early Deadline First (EDF)

Linux 的 deadline schduler 採用的是 Early Deadline First (EDF) 演算法，後者是在單處理器系統上的最佳演算法(在多處理器上，deadline scheduling 是 NP 問題)。接下來，讓我們更深入相關細節，來釐清 realtime 排程的方法。

將工作啟動的連續時間段定義為 job，則每個 realtime 的任務(task)即是由 N 個循環的 job 組成。如果一個任務的每個 job 都在距離其前次 job 的固定時間後發生，該任務稱為週期性(periodic)任務。舉例來說，每 2ms 啟動一次的任務，即是週期(preriod)為 2ms 的週期性任務

任務也可以是零星的(sporadic)組成。零星任務會在距離上次啟動後的某個最小時間間隔後再次啟動。例如，週期為 2ms 的零星任務將在距離上次啟動至少 2ms 後啟動。最後，任務也可以是非週期性的(aperiodic)，這類任務沒有固定的啟動模式。

任務的另一項特性是截止時間。任務可以具有隱式的截止時間(implicit deadline)，此時截止時間等於啟動週期時；當截止日期小於或等於啟動週期時，任務具有約束的截止時間(constrained deadline)。最後，任務可以有任意的截止日期(arbitrary deadlin)，這表示截止時間與週期無關。

假設系統有三個周期性任務，相關參數如下:

Task	Runtime(WCET)	Period/Deadline
T1	1	4
T2	2	6
T3	3	8

• 此時 CPU 使用率(utilimization) 為 1/4 + 2/6 + 3/8 = 23/24，不超過 100%。

則 EDF 的排程模式會呈現如下圖:

如果在 fixed-priority scheduler 上，受限於任務的先後是固定的，我們將不可能能夠滿足每個截止時間。如下圖，T3 在完成運行時已錯過 deadline(紅色點)。

正如之前提到，deadline scheduler 的主要優點是只需定義好自己的任務之相關參數，而不需要分析其他任務，即可確保該任務會在截止日期前完成。這種方式通常也會導致更少的 context switch。在單處理器系統上，比起 fixed-priority scheduler，deadline scheduler 可以在滿足每個任務截止日期的前提下，同時排程更多的任務。

然而，deadline scheduker 也有一些缺點。它雖然提供了完成任務的截止時間保證，但無法確保任何給定任務的最小回應時間。與之相對，在 fixed-priority scheduler 下，最高優先等級的任務總是具有最短的回應時間。 EDF 演算法也比 fixed-priority 方式更為複雜，前者的實作複雜度為

$O(log(n))$，後者則為

$O(1)$。不過 fixed-priority 需要使用者事先對當前的所有任務分析以選擇合適的的優先級，這點的複雜度可能高達

$O(N!)$。

除此之外，如果系統由於某種原因而過載，則可能會面臨糟糕的骨牌效應: 一旦一個任務因運行時間超過其聲明的運行時間而錯過了期限，所有其他任務可能會錯過最後期限，如下圖紅色區域所示：

相反，固定優先級方式只有優先順序低於錯過截止時間的任務的任務才會受到影響。

Deadline Scheduling on Multi-core System

除了優先級問題之外，在多核心系統上，排程還包含決定任務可以在哪個 CPU 運行。在此特性上，我們可以把排程器分為以下幾種：

• Global: 單一排程器管理所有 CPU，意味著任務可以遷移(migration)到所有 CPU
• Clustered： 單一排程器管理一個子集的 CPU，這代表任務只能遷移到可用 CPU 的子集
• Partitioned：排程器管理單一 CPU，因此不允許遷移
• Arbitrary：每個任務可以在任何一組 CPU 上運行。

在多核系統，我們很難定義完美的排程演算法來滿足 deadline。舉個例子: 假設具有四個處理器的系統可以調度四個「大」任務，任務運行時間和週期都等於 1000 毫秒。在這種情況下，系統將達到最大利用率： 4 * 1000/1000 = 4

直覺上，我們可能會認為負載較低的系統也是可排程的(滿足所有 deadline)，但事實可能並非如此。例如，在上述的系統中，此時任務由四個小任務組成，每個小任務的運行時間為 1 毫秒，且週期為 999 毫秒，此外還有一個大任務，運行時間和週期為 1 秒。此系統的負載為: 4 * (1/999) + 1000/1000 = 1.004

雖然 1.004 小於 4，但對 global deadline scheduler 來說，如果所有任務同時加入，則 4 個小任務將被排程到 4 個可用處理器中。然後，大任務只有在小任務運行後才能啟動，從而錯過截止時間。如下圖。這稱為 Dhall's effect。

Constant Bandwidth Server(CBS)

EDF 演算法以任務截止期限作為優先順序的依據。然而，如果一個任務的截止時間設定不當，而截止時間較早的任務獲得排程並運行過長，這可能導致下個任務錯過期限。為使每個任務最差情況的結束時間不受其他任務影響，能夠隔離每個任務間的行為，以確保在週期內都能獲得完整的運行時間，deadline scheduler 需搭配資源預留(resource reservation)的演算法。

在 Linux 的 SCHED_DEADLINE 中實作了 Constant Bandwidth Server(CBS)演算法來滿足資源預留(resource reservation)。每次啟動任務時，CBS 演算法會為任務分配排程截止時間，補充(replenish)任務的運行時間。任務運行時會消耗該運行時間。當時間用完，他就會被取消排程。藉此，CBS 可以防止某個任務不當的運行過長時間，而給其他任務帶來負面影響。

dl_entity_overflow()

下面讓我們深入 CBS 是如何分配截止時間。回顧一下，之前提到每個任務有 sched_period、sched_deadline、sched_runtime 三個靜態的屬性。而在運行時，任務的狀態可以由 「排程截止時間」 和 「剩餘運行時間」來描述。這兩個參數初始設定為 0。則當一個 SCHED_DEADLINE 被喚醒時，排程器進行以下檢查:

$$\frac{\mathrm{剩}\mathrm{餘}\mathrm{運}\mathrm{行}\mathrm{時}\mathrm{間}}{\mathrm{排}\mathrm{程}\mathrm{截}\mathrm{止}\mathrm{時}\mathrm{間}-\mathrm{當}\mathrm{前}\mathrm{時}\mathrm{間}}>\frac{\text{sched\_runtime}}{\text{sched\_period}}$$

如果排程截止時間小於當前時間(已經超時)，或者條件成立(所需要的 bandwidth 超出當前配給的)，則應該重新填充剩餘運行時間並將排程截止時間設定為未來的某個時刻。否則，將導致破壞向其他任務的 realtime 保證。更新的方式是:

• 排程截止時間 = 當前時間 + sched_deadline
• 剩餘運行時間 = sched_runtime

當 SCHED_DEADLINE 任務執行經過時間 t 時，其剩餘運行時間將減少為:

• 剩餘運行時間 = 剩餘運行時間 - t

當剩餘運行時間小於或等於 0 時，該任務就稱為被 "throttled"(有些論文會用 "depleted" 這個單詞)，在其下個 deadline 來臨之前將無法被排程。這時，此任務的「runtime 補充時間」被設定為等於排程截止時間的當前值。則當目前的時間來到「runtime 補充時間」時，任務的狀態更新如下:

• 排程截止時間 = 排程截止時間 + sched_period
• 剩餘運行時間 = 剩餘運行時間 + sched_runtime

Overloading Protection

為了避免 SCHED_DEADLINE 任務使系統過載，當一個任務成為 deadline policy，或者 deadline scheduler 中任務的屬性被調整時(__sched_setscheduler())，排程器會對其實施驗收測試(acceptance test)，以保證任務不會使用超過系統 CPU 時間的最大量，後者與 /proc/sys/kernel/sched_rt_runtime_us 和 /proc/sys/kernel/sched_rt_period_us 相關並可由此 knobs 調整。預設值分別為 950000 和 1000000，代表 deadline 任務被限制為每 1 秒上限可使用 950,000 µs 的 CPU 時間。

__checkparam_dl()

對於單核心系統來說，這個測試是必要而充分的。意味著被接受的任務可以被保證在截止時間之前得到分配給它的所有運行時間。

不過對於多處理器系統上的 global scheding 來說，這種驗收測試雖是必要的，但仍有所不足。正如前文中提到的 Dhall's effect，即使 CPU 負載很低，global deadline scheduler 也無法滿足所有任務的期限。換句話說，即便通過目前的驗收測試，在多處理器系統上並不能保證任務將能夠在截止日期之前使用所有分配的運行時間。

如果使用者想要確保所有任務都能滿足截止日期，則使用者可以使用必要且充分的驗收測試，定義為：

$$\sum \frac{WCE{T}_i}{P_i}<=M-(M-1)\ast U_{max}$$

• M 為處理器數量
• $U_{max}$ 為任務集中的最大 utilization

在這種測試下，可以看到如果 Umax 越大，系統能夠處理的負載就越小。則當存在 utilization 較高的任務時，一個好的策略是對系統進行分區(partition)並隔離一些高負載任務。目前，deadline scheduler 不允許使用者設定執行緒的 affinity，但可以使用 cgroup cpuset 來做到分區。

舉例來說，假設是一個具有八個 CPU 的系統。一個大任務的 CPU utilization 接近 90%，而其他任務的 utilization 較低。則我們要隔離 CPU0 來執行高 utilization 任務，其他任務則在剩餘 CPU 中執行。可以依循下列步驟：

1. 在 cpuset 下建立建立兩個 cpuset

# cd /sys/fs/cgroup/cpuset/
# mkdir cluster
# mkdir partition

2. 將 root cpuset 中的 load balancing 停用，以設置兩個新的 root domain

# echo 0 > cpuset.sched_load_balance

3. 進入 cluster cpuset，將可用的 CPU 設定為 1-7，運行的記憶體節點設定為 0(假設非 NUMA 系統，因此它始終是節點零)，並將 cpuset 設為 exclusive 模式(這些 CPU 將只分配此 cpuset)

# cd cluster/
# echo 1-7 > cpuset.cpus
# echo 0 > cpuset.mems
# echo 1 > cpuset.cpu_exclusive 

4. 將所有任務移動到 cluster

ps -eLo lwp | while read thread; do echo $thread > tasks ; done

5. 設置 partition cpuset

# cd ../partition/
# echo 1 > cpuset.cpu_exclusive 
# echo 0 > cpuset.mems 
# echo 0 > cpuset.cpus

6. 可以將 shell 移動到 partition 以運行 workload

# echo $$ > tasks 

TODO: 調整至 v2

小記

• Deadline scheduler 任務(SCHED_DEADLINE)的優先順序高於 realtime scheduler(SCHED_FIFO/SCHED_RR) 任務。意味著即使是最高 fixed-priority 的任務也會被 deadline 任務延遲
• Deadline Scheduler 和 PREEMPT_RT 在 Linux 的 realtime 特性的支援是不同面向的。Deadline Scheduler 允許以更可預測的方式排程，而 PREEMPT_RT 需要進階的減少 preemption 和 disable IRQ 情況下運行的時間以更嚴謹的保證延遲

Real-time Scheduling 的難題

甚麼是 DL Server?

Reference

• Deadline scheduling part 1 — overview and theory
• Deadline scheduler part 2 — details and usage
• Deadline Task Scheduling
• Welcome message and DL Server - Daniel Bristot de Oliveira
• [RFC PATCH V3 0/6] SCHED_DEADLINE server infrastructure
• Deadline Scheduler
• SCHED DEADLINE: a real-time CPU scheduler for Linux
• Using SCHED_DEADLINE