Linux 核心專題: Linux 的 Preempt-RT 機制

一、RTOS 介紹

即時系統是一個有時間限制的系統，具有明確定義的固定時間限制。處理必須在定義的約束內完成，否則系統將失敗。

可以將 RTOS 分為以下兩種:

1. Hard RTOS: 將任何錯過最後期限的行為視為系統故障。廣泛用於任務關鍵型系統。
2. Soft RTOS: 允許經常錯過最後期限，只要任務及時執行，其結果就繼續有價值。已完成的任務在截止日期之前的價值可能會增加，而在截止日期之後價值可能會減少。

注意到 Real time != Real fast

• Real-time: 系統是指能夠在指定的時間限制內對事件作出反應的系統。這個時間限制稱為 "deadline" 。
• Real-fast: 強調任務的執行速度，即系統能夠以最快的速度完成任務。

1.1. Latencies

在 RTOS 中，一個事件的發生到系統回應此事件所花的時間就稱作 Latencies (延遲)。對於某些非常重要的任務，例如核能場的設備，特定的操作控制必須在非常嚴格的時序限制內進行。開發者必須保證特定任務最壞情況執行時間 (WCET) 低於特定時間限制，以便它們可以在底層實際分配給它們的計劃時間內執行。

就如圖上所示，問號的部份就是在不重要任務中切換到重要任務的時間，而我們希望盡可能減少這段時間。

1.2. Multi tasking

現代的作業系統和 CPU 都支持這種多工系統，它允許多個使用者同時執行多個任務。多工處理是作業系統在 CPU 機器上同時執行多個任務的能力。而要實現多工系統，必須有以下特性:

• Time sharing: process 共享著 CPU 的使用時間。
• Context switching: 保存上一個執行的 process 的詳細資訊(暫存器、PC、記憶體資訊等)，接著切換到下一個 process。
• Multi-threading: 多執行緒是程式或作業系統一次支援多個使用者而不需要在電腦上執行程式的多個副本的能力。
• Hardware Interrupt: 它通知處理器出現了需要中斷正在運行的程序的高優先級任務。

下圖是三個不同概念，分別是 Single thread、Multi-thread、Multi-processing。可以看到 thread 在 process 內共享程式碼、資料以及文件，但暫存器和堆疊是獨立的。

1.3. Preemption

搶佔是暫時中斷正在執行的任務的行為，以便稍後恢復它，並執行優先級更高的任務。對處理器目前正在執行的任務的這種改變稱為上下文切換(Context switching)。

對於一般的作業系統，搶佔是有效的去分享處理器使用時間，而對 RTOS 而言則是非常關鍵的，因為可以搶佔低優先級的任務而去執行關鍵的任務(critical tasks)。而不管是 kernel space 還是 user space 中的任務都應該要是可以被搶佔的。

當任務運作在 user space 執行並被中斷時，如果中斷處理程序喚醒另一個任務，我們可以立即調度(透過 scheduler)該任務從中斷處理程序返回。

有一個特殊的情況，當任務呼叫 System call 到 kernel space 中執行時，此刻下有中斷發生，結束完中斷事件後，會先執行完在 kernel space 的系統呼叫後，才會使用 Scheduler 對任務進行排程，這就會導致在中斷結束到系統呼叫結束的這段時間是 Unbounded 。

參照 Linux 核心搶佔

1.4. Interrupts and events

硬體中斷是延遲的常見來源，硬體中斷有以下兩種:

• 內部中斷: 處理器內建的外部設備所發出的中斷信號，例如定時器中斷。
• 外部中斷: 外接設備透過裝置驅動向處理器發出的中斷信號，例如 USB 中斷。

硬體中斷是可以搶佔關鍵任務的，這部分可以參考 2.3.2. 節所示的原始 Linux 核心示意圖。也就是說對系統而言關鍵任務仍然是一個執行緒，而中斷的優先級還是高於這些一般任務。因此就會導致不管任務有多重要，仍無法 "及時" 執行。解決辦法會在後面探討。

1.5. Scheduling and proritizing

排程器(Scheduler)是保證即時系統的關鍵，它會根據不同特性去做排程，而大多數則是根據優先級做排程，優先級高的優先執行。而相同優先級的任務則是可以以 FIFO 或是 Round-Robin 的方式處理。

1.6. Lock

在 Multi tasking 的情況下意味著會對資源並行(Concurrency)的訪問。關鍵的資源通常會透過鎖(lock)的機制來保護。而常見的所有以下兩種:

• Semaphore(信號量): 基於計數器的機制，這裡的信號量是指可用資源的數量。
  • 如果信號量的值大於 0，則任務可以存取臨界區或共享資源。但是，如果該值為 0，則表示沒有任何可用資源，或者臨界區已被多個任務存取並且無法被更多任務存取。
  • 當有任務取得資源時，信號量增加，而當有任務釋放資源時信號量減少。
  • 多個任務可以存在在 critical section，因此沒有單一擁有者。
• Mutex: 相互排斥的鎖
  • 有兩種狀態: Taken、Free，分別表示資源使用中、資源釋放。
  • 取得互斥鎖的任務是擁有者，其他任務需要等待互斥鎖釋放後再取得它。

1.7. Priority inversion

優先級反轉(Priority inversion)說明了一種特殊的情況，會使高優先級的任務被低優先級的任務搶佔，以下說明例子:

上圖流程如下:

• Task C 被 Task A 搶佔去執行關鍵任務
• Task A 執行到一半發現有個資源需要 Task C 去釋放，所以執行權還給 Task C
• Task B 加入排程後因其優先級高於 Task C 所以搶佔 Task C
• 最高優先級的 Task A 因為 Task C 一直被搶佔無法釋放資源而無法執行，進而導致優先級反轉(Task B 比 Task A 還優先執行)。

1.8. Priority Inheritance

解決優先級反轉的問題就是使用優先級繼承(Priority Inheritance)，它透過將低優先級的任務(但持有資源)暫時地設置為最高優先級，保證了資源可以被釋放。同樣是剛剛的例子:

• 在關鍵任務需要特定資源釋放時，會將 Task C 的優先級提高使其可以正常釋放資源給 Task A。
• 釋放資源後，Task A 就可以執行，而不會被 Task B 給搶先執行。

Real-time 的迷思

real-time 系統往往存在一些迷思，以下列出兩項說明:

1. (x) 使用 real-time 可以增加吞吐量以及整體的性能:
   實際上會因為需要在期限內做完重要的任務而導致整體的效能是下降的。
2. (x) 使用 real-time 可以降低整體平均延遲:
   real-time 的中心思想是要降低最大的延遲。舉例說明，老師出作業給學生寫並設置期限內繳交。那對老師而言，你在第一天就交和你在最後一天才交是一樣的，但是老師最怕你沒有在期限內繳交。因此普通的系統就可能是有同學很快就交了，有同學超過期限還沒交。而 real-time 系統則是雖然每個學生沒辦法第一天就交了，但是一定可以在期限內繳交。也就是拉低整體平均但確保了時限性。

二、Linux 中的 Preempt_RT

2.1. 背景知識

其實原本的 Linux 核心就是一種 Soft RTOS，只是隨著工業上、業界上越來越多對 Hard RTOS 的需求，這也使 Linux 開始發展 Hard real-time 的機制。

但由上面介紹我們知道 Hard 和 Soft 的機制完全不一樣，若是要重新為了 Real-time 重新開發 Linux 好像不是一個理想的作法，因此 Preempt_RT 的補丁(patch)機制就出現了。它實際上是 Linux 的配置參數(config)，我們可以透過設定這些參數來讓 Linux 核心有不同客製化的表現。而 Preempt_RT 的設定就是使核心變成 Hard real-time 。

2.2. 原理

Preempt_RT 的關鍵就在盡可能減少非搶佔式的程式，且最大幅度的減少因為要增加可搶佔性而增加的程式碼。PREEMPT_RT 補丁(patch) 利用 Linux 核心的 SMP 功能來添加這種額外的搶佔性，而無需完全重寫核心。從某種意義上說，我們可以粗略地將搶佔視為向系統添加新的 CPU，然後使用正常的鎖去同步任何搶佔任務。

2.3. 特色

以下是幾個 Preempt_RT 的特色：

1. Preemptible critical sections
2. Preemptible interrupt handlers
3. Preemptible "interrupt disable" code sequences
4. Priority inheritance for in-kernel spinlocks and semaphores
5. Deferred operations

2.3.1. Preemptible critical sections

我們知道通常要保護資源會使用自旋鎖(spinlock)，若是已經有一個任務獲得自旋鎖，當另一個任務想獲取資源時，只能原地等待。但在 Preempt_RT 中，將 spinlock 變成了 sleeping spinlock ，也就是說它不再原地等待了，而是會進入睡眠模式，並排程其他任務。這也就讓原本的 spinlock (spinlock_t 和 rwlock_t) 變成可搶佔的。

這樣的機制使在 critical sections 仍然還是可以搶佔。但若是真的想要一個非搶佔的 critical sections 那可以使用 raw_spinlock_t 。這是在 Preempt_RT 中保留傳統的 spinlock 。

考慮到多核的系統，若是 critical sections 能被搶佔，那在某個 CPU 上執行的關鍵部份就有可能因為搶佔而被移到不同的 CPU 上。原本 spinlock 的工作就是保護這些 CPU 參數。如今就需要額外來處理這些搶佔。

以下有兩種方法來處理：

1. 透過使用 get_cpu_var()、preempt_disable() 或停用硬體中斷來明確禁止搶佔發生。
2. 使用 per-CPU lock 來保護每 CPU 變數。

2.3.2. Preemptible interrupt handlers

這邊導入了 Threaded interrupt 機制，將大部分的中斷都變成和一般的執行緒一樣，使其可以和一般任務一樣可以被中斷。但有一些中斷是不希望被搶佔的，例如:

• irq0: 每個 CPU 的定時器中斷
• fpu_irq: 浮點數輔助處理器 FPU 發出的中斷
• lpptest: 中斷延遲基準測試

這些不可被搶佔的中斷就歸類到 SA_NODELAY，在這邊的中斷皆是不可搶佔的。若是我們歸類太多中斷到此區的話就會大幅降低中斷和排程的延遲，也就失去了 Real-time 的效益了。

下面兩張圖顯示了原始 Linux 核心和 Preempt_RT 的差別：

• 原始 Linux 核心
  

• Preempt_RT 機制
  

我們會在 2.5. 節更詳細的探討中斷相關議題。

透過這樣的機制，就可以達成 real-time 的精隨，也就是幾乎任何情況接可以被搶佔。下圖說明搶佔情況，紅色為不可搶佔、綠色為可搶佔。

• Non-Preemptive
  

• Preemption Points in Linux Kernel
  

• Fully Preemptive
  

  

include/linux/interrupt.h

2.3.3. Preemptible "interrupt disable" code sequences

搶佔一段 "禁止中斷" 的區域聽上去似乎是很奇怪的，但 Preempt_RT 就是要讓多數事件是能被搶佔的。值得注意的是那要如何保護關鍵區域所擁有的資源呢？

如同 2.3.1. 節所述，spinlock 已經變成 sleeping spinlock ，也就是說若是有任務搶佔了持有 spinlock 的程式，那也會在嘗試要存取 spinlock 時進入 block 狀態並再次排程其他任務。因此我們可以理解成在 Preempt_RT 的機制下會把 spinlock 變成 mutex 。

TODO: 引用程式

2.3.4. Priority inheritance for in-kernel

如同 1.7. 和 1.8. 節提到的優先級反轉以及解決它的優先級繼承，Preempt_RT 當然也有這樣的機制。

但當信號量(Semaphore)不是作為鎖，而是做為事件機制時，不需要使用優先級繼承。例如:

• 任務完成通知：一個任務完成其工作後，使用信號量通知其他等待的任務。
• 多生產者-多消費者問題：信號量用來協調多個生產者和消費者之間的關係，確保資源在生產和消費之間有效傳遞。

這樣無法知道誰會觸發事件，優先級繼承就不適用。在這種情況下，可以使用 compat_semaphore 和 compat_rw_semaphore，這些變體不會實現優先級繼承。

2.3.5 Deferred operations

spinlock 睡眠問題

現在因為 spinlock 會可能進入睡眠狀態，這代表我們不能在禁止搶佔或中斷的情況下使用 spinlock 。但若是還是很想使用 spinlock 怎麼辦？

使用延遲(Deferred)操作，將那些想要使用 spinlock 的操作往後延遲到搶佔重新啟動。

1. 延遲操作
   • put_task_struct_delayed()：將put_task_struct 操作排隊，等到可以安全獲取鎖時再執行。
   • mmdrop_delayed()：類似於 put_task_struct_delayed()，將 mmdrop 操作排隊延遲執行。
2. 延遲排程
   • 避免不必要的搶佔：當高優先級任務被喚醒時，如果它不能立即取得鎖，則會被快速 block。因此，延遲排程避免了這種情況，等待當前任務釋放鎖後再進行排程。
   • wake_up_process_sync()：如果喚醒進程會導致當前進程被搶占，則使用此方法來延遲喚醒，並設置 TIF_NEED_RESCHED_DELAYED 標誌，確保喚醒在更合適的時機進行。

Deferrable work

為了降低中斷處理帶來的延遲(latency)，Linux 核心中將中斷切成:

• top half: 緊急且重要的中斷處理
• bottom half: 相對不重要的中斷處理

當發生中斷時，馬上處理 top half 的事情，並將 bottom half 的事情推遲(Defer)到後面再做，如下圖所示:

注意到在很關鍵的中斷時，會在 top-half 階段先暫時將中斷關閉。確保執行中不被搶佔。執行結束後再將中斷開啟。

這樣的設計有助於中斷搶佔關鍵區域時所浪費的時間，對照 1.4. 節中斷搶佔關鍵任務後執行了一大段時間才結束，下圖則是使用了 Deferrable work ，使中斷可以即時處理，而又不佔用關鍵任務的時間。而這也是我們將中斷變成 threaded interrupt 的原因之一。

參照 Linux 核心設計: 中斷處理和現代架構考量

2.3.6. High resolution timers

系統中有許多事情是需要用到定時器的，而通常 CPU 內會內建一個 Timer ，會週期性的觸發中斷，讓系統知道一個時間段到了。而這個週期性的時脈就稱作 tick 。

而通常要在 user space 設置定時器往往都和 system tick 綁在一起。若我想要設置一個頻率更大的定時器要怎麼做，簡單想就是直接把 system tick 的頻率拉高就好啦，但每次 tick 時 CPU 都要去處理中斷的事情，若是頻率太高，不但會佔用到正常程式的執行，更會使系統變慢和增加功耗。這並不是一個好的辦法。

因此結合 tickless 和 "on-demand" 技術的定時器中斷就出現了。而此時底層的硬體計時器也支援 "one-shot" 的技術。當有計時器中斷時，除了處理這個計時的中斷之外，系統還會掃描所有的 Timer ，並找到即將要超時的，將其時間值設置到硬體的 Timer 就好了。

而這樣的 tickless 的設置會使其計時中斷的間隔不是均勻的，這也提供了一個較高頻的計時器實作方式。假設有一些計時器，若是使用 tick 的話就沒辦法很精準的響應真實計時時間，而 tickless 則可以較好的實現。

Linux時間子系統之（十三）：Tick Device layer綜述

2.4. config 類型

Linux 核心有以下幾種搶佔模型可以做選擇:

• CONFIG_PREEMPT_NONE: 核心程式碼（中斷、異常、系統呼叫）永遠不會被搶佔。
  • 適合密集運算的系統，其中整體吞吐量是關鍵。例如: 伺服器
  • 最好減少任務切換，以最大限度地提高 CPU 和快取的使用率
• CONFIG_PREEMPT_VOLUNTARY: 核心可以自願的選擇搶佔點
  • 通常用於桌面系統，以便應用程式對使用者輸入做出更快的反應。
  • 對吞吐量影響較小。
• CONFIG_PREEMPT: 大多數核心程式碼隨時都可能被非自願地搶佔。當一個行程變成可運行時，不再需要等待核心程式碼（通常是系統呼叫）在排程之前返回。
  • 例外: kernel critical sections (持有 spinlocks):

• CONFIG_PREEMPT_RT: 幾乎所有的核心程式碼都可以隨時被非自願地搶佔。
  • spinlock 變成 sleeping lock，raw_spinlock_t 保留原始 spinlock 功能
  • 大多數 interrupt handler 變成 threaded
  • 用於需要 Hard Real-time 的系統

回到根目錄輸入以下命令，就可以看到我的電腦所設置 config 類型。

$ cat /boot/config-6.5.0-44-generic | less
CONFIG_PREEMPT_BUILD=y
# CONFIG_PREEMPT_NONE is not set
CONFIG_PREEMPT_VOLUNTARY=y
# CONFIG_PREEMPT is not set
CONFIG_PREEMPT_COUNT=y
CONFIG_PREEMPTION=y
CONFIG_PREEMPT_DYNAMIC=y
CONFIG_SCHED_CORE=y

2.5. Threaded Interrupt

本節將探討 Linux 核心的中斷以及 Threaded 後的中斷帶來的影響，會結合理論和程式碼解說。

2.5.1. Linux 中斷原理

在開始討論 Threaded Interrupt 之前，先來看看 Linux 核心如何完整的處理中斷。

• 以下是 Linux 核心處理中斷的流程

完整流程:

• 硬體設備發出中斷信號
• 中斷控制器 (PIC or APIC) 負責仲裁多個中斷信號，並發送給 CPU
• 根據中斷線，可以得到中斷的 IRQ 號碼
• 進入通用中斷處理函式，在堆疊中保存當前執行的資訊
• 進入 do_IRQ 函式，負責執行中斷相關服務程式

unsigned int __irq_entry do_IRQ(struct pt_regs *regs)
{                                                                                                                                       
    struct pt_regs *old_regs = set_irq_regs(regs);
 
    /* high bit used in ret_from_ code  */
    unsigned vector = ~regs->orig_ax;
    unsigned irq;
 
    exit_idle();
    irq_enter();
 
    irq = __get_cpu_var(vector_irq)[vector];
 
    if (!handle_irq(irq, regs)) {
        ack_APIC_irq();
 
        if (printk_ratelimit())
            pr_emerg("%s: %d.%d No irq handler for vector (irq %d)\n",
                __func__, smp_processor_id(), vector, irq);
    }   
 
    irq_exit();
 
    set_irq_regs(old_regs);
    return 1;
}

• 進入 handle_irq 函式，在 irq_desc 數列中找到此 IRQ 對應到的 irq_desc 。執行對應的 headle_irq 函式，也就是會執行中斷處理程式 ISR 。

bool handle_irq(unsigned irq, struct pt_regs *regs)
{
    struct irq_desc *desc;
    int overflow;
 
    overflow = check_stack_overflow();
 
    desc = irq_to_desc(irq);                                                                   
    if (unlikely(!desc))
        return false;
 
    if (!execute_on_irq_stack(overflow, desc, irq)) {
        if (unlikely(overflow))
            print_stack_overflow();
        desc->handle_irq(irq, desc);
    }   
 
    return true;
}

• 如下圖所示

• 處理完 ISR，將剩下不重要的部份留到 SoftIRQ 執行
• 存取被保存的資訊，回到原本執行的任務

2.5.2. Threaded Interrupt 的影響

為了要向核心申請 interrupt handler ，需要呼叫 request_irq 函式，而在 PREEMPT_RT 的機制下，此函式以被實作成 request_threaded_irq ，也就是中斷執行緒化。下面我們來分析此函式的執行流程。

可以在 kernel/irq/manage.c 中找到函式。

int request_threaded_irq(unsigned int irq, irq_handler_t handler,
			 irq_handler_t thread_fn, unsigned long irqflags,
			 const char *devname, void *dev_id)

參數名稱	功能
irq	要註冊 handler 的 IRQ number
handler	上半部的函式
thread_fn	下半部執行緒化函式
irqflags	保存關閉中斷之前的狀態

【Linux】—中斷處理流程

三、Linux 即時排程

對於一個即時系統而言，任務可能存在期限性，若是未完成的話，則有可能導致系統崩潰。因此排程器 (scheduler) 就非常關鍵。它負責選擇適合的任務給 CPU 執行，而在不同的情況下會有不同的選擇。

在 Linux 中，行程 (Process) 和執行緒 (Thread) 是沒有差別的，在排程器眼中，就是一個任務 (Task) 。

3.1. 目標

排程器的目標可以分為以下幾點:

1. Throughput: 定義為CPU在給定時間內執行的任務數量。
2. Response time: CPU 回應任務發出的請求所花費的時間，它是進程到達和第一次運行之間的持續時間。
3. 公平性: 對於 Time-sharing 系統，需要盡量公平分配任務，避免 Starvation 。

3.2. Process 分類

根據任務的性質不同，Linux 將每個行程分為:

• 普通行程
• 即時行程

我們又可以將普通行程分為:

• 交互式行程 (interactive processs) <-> I/O Bound
• 批處理行程 (batch process) <-> CPU Bound

交互式行程注重的是用戶使用體驗，通常是 I/O Bound 任務，因此 Response time 比較重要，例如文字編輯器等。另一方面批處理行程則是會使 CPU 做大量的工作，因此更注重 Throughput 。

3.3. Task

前面說到，Linux 會根據不同任務的性質去分配它的類型。在 linux/include/linux/sched.h 找到任務的結構。

struct task_struct {
...
	int				on_rq;

	int				prio;
	int				static_prio;
	int				normal_prio;
	unsigned int			rt_priority;

	struct sched_entity		se;
	struct sched_rt_entity		rt;
	struct sched_dl_entity		dl;
	struct sched_dl_entity		*dl_server;
	const struct sched_class	*sched_class;
...
    unsigned int			policy;
...
}

3.3.1. Task priority

為了確保任務可以優先得到 CPU 時間，Linux 核心給任務定義了從 0 ~ 139 的優先級。

• 0 ~ 99: 即時任務
• 100 ~ 139: 普通任務

3.3.2. Nice Value

Nice value 本身是一個 User space 的概念，它使使用者可以修改優先級來讓排程器優先選擇。而 Nice 值得取值範圍則是 -20 ~ 19 。注意到在這個區間，越低的值，其優先級越高。反之亦然。

• -20: 最高優先級
• 0: 預設優先級
• 19: 最低優先級

3.3.3. Static priority

它映射了普通任務的優先級範圍。在一個任務被創建時，這個值就會被決定。在 kernel/sched/core.c 裡可以看到 sched_fork 函式裡 static_prio 被設置為 NICE_TO_PRIO 。

int sched_fork(unsigned long clone_flags, struct task_struct *p)
{
	if (unlikely(p->sched_reset_on_fork)) {
		if (task_has_dl_policy(p) || task_has_rt_policy(p)) {
			p->policy = SCHED_NORMAL;
			p->static_prio = NICE_TO_PRIO(0);
			p->rt_priority = 0;
		} else if (PRIO_TO_NICE(p->static_prio) < 0)
			p->static_prio = NICE_TO_PRIO(0);

		p->prio = p->normal_prio = p->static_prio;
		set_load_weight(p, false);
...

接著在 linux/sched/prio.h 定義了 NICE_TO_PRIO 宏。

#define MAX_NICE	19
#define MIN_NICE	-20
#define NICE_WIDTH	(MAX_NICE - MIN_NICE + 1)

#define MAX_RT_PRIO		100

#define MAX_PRIO		(MAX_RT_PRIO + NICE_WIDTH)
#define DEFAULT_PRIO		(MAX_RT_PRIO + NICE_WIDTH / 2)


#define NICE_TO_PRIO(nice)	((nice) + DEFAULT_PRIO)
#define PRIO_TO_NICE(prio)	((prio) - DEFAULT_PRIO)

因此我們知道 static_prio 會被設置為 nice + 120 。特別注意到其值越低，優先級越高。

3.3.4. Normal Priority

Normal Priority 會根據 Static priority 和排程策略來決定。若是 DEADLINE 策略會設置為 -1 ，若是 Real-time 策略則會設置為 100 - 1 - rt_prio，若是普通任務就等於 static_prio 。

特別注意到，父行程的 Normal Priority 會繼承給子行程。

static inline int __normal_prio(int policy, int rt_prio, int nice)
{
	int prio;

	if (dl_policy(policy))
		prio = MAX_DL_PRIO - 1;
	else if (rt_policy(policy))
		prio = MAX_RT_PRIO - 1 - rt_prio;
	else
		prio = NICE_TO_PRIO(nice);

	return prio;
}

3.3.5. Prio

prio 的值是排程器真正參考的數值，在 sched_fork 函式預設是 static_prio ，但在 set_user_nice 函式中會呼叫 effective_prio 來判斷是否為即時任務。若是普通任務則會回傳 static_prio ，反之就回傳 Real-time 的 Normal Priority 。

static int effective_prio(struct task_struct *p)
{
    p->normal_prio = normal_prio(p);

    if (!rt_prio(p->prio))
        return p->normal_prio;
    return p->prio;
}

void set_user_nice(struct task_struct *p, long nice)
{
    ...
    p->prio = effective_prio(p);
    ...
}

3.4. 排程演算法

在 Linux 核心中會有一個排程策略，根據任務動態調整排程演算法。主要分為非即時和及時策略。

3.4.1. Completely Fair Scheduler (CFS)

旨在注重公平分配。CFS 為每個任務分配一個虛擬運行時間，根據這個時間來決定優先級，確保所有任務都能平等獲得 CPU 資源。CFS 使用紅黑樹結構來管理和快速查找最需要運行的任務，並且隨著系統負載自動調整，達到平衡系統性能與任務公平性的目標。

• SCHED_NORMAL（原本是 SCHED_OTHER）：用於一般任務的排程策略。
• SCHED_BATCH：不像一般任務那樣經常搶佔，從而允許任務運行更長時間並更好地利用緩存，但以互動性為代價。這非常適合批次作業。
• SCHED_IDLE：比 Nice 值為 19 還要低優先級，但它不是真正的空閒計時器排程程序，以避免陷入優先反轉問題，從而導致死結。

本章的重點不是 CFS ，詳細可以參考

CFS Scheduler
Linux 核心設計: Scheduler(2): 概述 CFS Scheduler

3.4.2. Real-time scheduler

sched_rt 是 Linux 核心中軟即時排程的演算法分類，主要有 FIFO 與 RR 兩個演算法。

1. FIFO (First In First Out): 先進入的任務優先處理，這是最簡單的一種排程演算法。在 Linux 核心的 FIFO 演算法，每個任務的優先級從 0(低)到 99(高)， 任務會被放入一個佇列，優先執行優先級較高的任務，若優先級相同則選擇最先進來的任務。一個任務一旦佔用 CPU ，則會一直執行直到有更高優先級任務到達或是執行完成。
2. RR (Round Robin): 是 FIFO 的簡單增強，一樣屬於先進先出。但和 FIFO 不同的是，RR 會給定一個時間片(time slices)，每個任務最多執行一個時間片的時間，接著就會切換到另一個相同優先級的任務。相較於 FIFO ，在相同優先級的任務下，RR 演算法擁有更高的公平性。

3.4.3. FIFO、RR 實驗

我們希望透過一系列實驗來觀察兩個演算法的特性。以下實驗皆是在 Ubuntu Linux 環境下實作。使用 Linux 核心的 SCHED_FIFO 和 SCHED_RR (時間片預設為 100ms) 實驗。編譯器使用 GCC 並且關閉所有的優化。使用 trace-cmd 追蹤 CPU 的行為，最後使用 Kernelshark 工具視覺化 CPU 內的任務排程情況。任務的執行皆為 CPU-Bound。並將任務分為4 個不同量級，分別為Little、 Medium、 High、 Extreme。

void test_little(void) {
    volatile int i, j;
    for (i = 0; i < 30000000; i++) j = i;
}
...

實驗一: FIFO 和 RR 的策略

我們先觀察 FIFO 和 RR 最基本的差異，使用 C 語言的 fork 函式產生子行程，設計相同優先級的 4 個任務。

因為是相同優先級，因此 FIFO 的策略就是一直執行直到結束，而 RR 則是每 100ms 就切換任務一次。若是先進來的任務執行時間很長，在 FIFO 的策略下就會相對不公平。而 RR 策略可能會因為多次的切換而導致有比較大的開銷。

• FIFO
  
  
• RR
  
  

實驗二: RR Time slice 選擇策略

Round Robin 策略的 Time slice 的選擇是非常關鍵的。過大的 Time slice 會導致其行為變成 FIFO 策略; 而過小的 Time slice 則會導致 CPU 太頻繁的切換任務，進而降低 CPU 使用率。本實驗要來測試 Time slice 的選擇是否會造成效能上的影響，換句話說，實驗目的就是要測試多少比例的任務可以在一個 Time slice 下執行結束可以獲得最好的取捨。

我們設計了 10 個從小到大負載的任務，先計算每個任務使用 CPU 的時間，再透過調整 Linux 核心的 sched_rr_timeslice_ms 參數修改 Time slice 。預設是 100 ms。

sudo sysctl kernel.sched_rr_timeslice_ms=1

因為每個任務的數量平均分配的，分別使 0% ~ 100% 的任務是可以在一個 Time slice 之內完成。測試程式會執行 300 個任務，也就是一個區間大小的任務有 30 個。

實驗方法就是先用迴圈 fork 出 n 個子行程，進入 start_task 函式後使用 pause 函式使子行程進入睡眠。等到所有子行程都生成後，再使用 kill 函式向子行程發送信號並喚醒。我透過實驗觀察到子行程會等這個使用 kill 的父行程對每個子行程發送完信號後才會開始執行，因此所有的子行程就是幾乎一起進入 runqueue 的。

使用 perf 效能測量工具來觀測，取五次實驗數據做平均。觀察 Context-Switch 和 Throughput 。

sudo perf stat --repeat 5 ./RR_test

策略	Time slice (ms)	Context-Switches (次數)	Throughput (task/sec)
RR _0%	1	17694	2.863
RR _10%	10	3610	4.855
RR _20%	30	1425	4.981
RR _30%	70	728	4.893
RR _40%	100	557	5.118
RR _50%	130	456	5.037
RR _60%	160	412	5.117
RR _70%	200	356	5.146
RR _80%	300	320	5.108
RR _90%	400	111	4.926
RR _100%	1500	81	4.957
FIFO	無	83	4.612

透過數據可以看出，RR_0% 的 Context-Switch 次數非常多，就直接導致其 吞吐量非常低。而 RR_100% 與 FIFO 策略的數據非常相近，也就證實了當 Time slice 過高時，就失去了 Round Robin 的優勢了。有研究顯示在 80% 通常吞吐量最高，本實驗則是在 70%。

此外，我們也同時追蹤每個行程的回應時間，分別考慮平均、最大和最小。下圖顯示了回應時間的折線圖。最小回應時間是不會因為策略而改變。而平均與最大回應時間就會隨著比例的上升而增大，在 RR_100 ，也就是 FIFO 策略下平均和最大回應時間都是最長的，對應上表所呈現的效能，即使 FIFO 策略的數據不差，但回應時間的增加可能導致行程無法在給定的時間內完成。而 RR_70 在效能和回應時間的取捨下表現最好的。

• 平均、最大與最小的回應時間
  
  

Deadline (EDF)

最後，我們將提到 SCHED_DEADLINE 策略，它是 Linux 中最貼進及時系統的排程器。而其實際上就是實作了 EDF (Earliest Deadline First) 演算法。

在 deadline 排程器中需要定義三個參數分別是:

• period: 週期
• runtime: 執行時間
• deadline: 截止期限

我們以一個處理影像的任務來舉例說明，假設一秒鐘需要處理 60 幀，那就代表每 16.6 (ms) 就會有一幀畫面到達，因此這個任務的 period 就是 16.6 (ms) 。再者，運行時間是任務產生輸出所需的 CPU 時間。處理一幀的時間我們需要考慮的是最壞情況執行時間 (WCET)，若是 WCET 為 5 (ms) 的話，則 runtime 就是 5 (ms)。截止期限是任務必須給出結果的最長時間，如果任務需要在 10 (ms) 之內將一幀的畫面處理好，那它的 deadline 就是 10 (ms)。

由於截止期限排程器知道每個截止期限任務需要多少 CPU 時間，因此它知道系統何時可以（或不行）再接納新的任務。因此，截止期限排程器不允許使用者使系統超載，而是拒絕添加更多截止期限任務，從而保證所有截止期限任務將有 CPU 時間來完成其任務，至少有一定的延遲。

在即時調度理論中，調度程序的評估重點在於它是否能滿足所有即時任務的時間要求。即時任務必須有確定的時間行為，這意味著我們可以預測它們何時會執行。

即時任務可以分為幾種類型：

1. 週期性任務(periodic)：這類任務在固定的時間間隔後重複執行。例如，一個週期為2毫秒的任務，每2毫秒就會啟動一次。
2. 零星任務(sporadic)：這類任務不像週期性任務有固定的啟動時間，但它們至少在兩次啟動之間有一個最短的間隔時間。例如，一個零星任務的最短間隔時間是2毫秒，那麼每次啟動之間至少會有2毫秒的間隔。
3. 非週期性任務(aperiodic)：這類任務的啟動沒有固定的模式或時間。

任務還有不同的截止日期設定：

• 隱式截止日期：截止日期等於任務的週期。
• 約束截止日期：截止日期可以比週期短或等於週期。
• 任意截止日期：截止日期和週期沒有關聯。

根據這些任務特性，即時排程研究者開發了不同的調度方法來比較哪個算法能更有效地排程任務集。針對單處理器系統，EDF 排程算法被認為是最佳的，因為它能夠有效排程所有不超過 100% CPU 使用率的週期性或零星任務。

下面舉個例子說明:

Task	Runtime(WCET)	period	deadline
T1	1	4	4
T2	2	6	6
T3	3	8	8

$$\text{CPU time utilization}=\frac{1}{4}+\frac{2}{6}+\frac{3}{8}=\frac{23}{24}$$

• 如果使用 EDF 策略就會如下圖所示，這也證實了若是 CPU time utilization 如果小於 100% ，則任務必定可以在期限內完成。
  
  
• 但如果使用優先級策略的話，就如下圖所示，並不能保證任務會在期限內完成。
  
  
• 剛才提到 Deadline 策略會判斷系統是否過載 (CPU 使用率是否大於 100%) 來決定是否可以加入任務，假設因為系統異常或出現錯誤計算 WCET 而導致一個任務
  $T_4$ 加入，使其 CPU 使用率大於 100% ，則可能會面臨多米諾骨牌效應：一旦一個任務因運行時間超過其聲明的執行時間而錯過了最後期限時間，所有其他任務可能會錯過最後期限，如下圖紅色區域所示：

Task	Runtime(WCET)	period	deadline
T4	2	8	8

EDF in multi-core

對於多核心系統(multi-core system)來說，排程器需要考慮要將任務放到哪個處理器上面，我們可以將其分為:

• Global: 單一的排程器管理所有的 CPU，也就是說任務都可任意 CPU 上。
• Clustered: 單一的排程器管理特定的 CPU 子集，也就是說任務只能在特定的 CPU 子集上。
• Partitioned: 每個排程器管理單一 CPU 時，代表不能將任務遷移到其他 CPU 上。
• Arbitrary: 每個任務可以在任何一組 CPU 上運行。

對於多核心系統，Global、Clustered、Arbitrary 都不是 optimal。考慮到多核心系統會比單核系統複雜許多，以下考慮兩個案例。假設我有一個 4 核心的系統，我想排程 4 個大任務，其執行時間和週期都是 1 秒，在這種情況下，系統會剛剛好滿載

$$\text{CPU time utilization}=4\ast \frac{1000}{1000}=4$$
執行狀態如下圖所示:

既然這樣滿載的情況下都可以執行了，那負載較低的話是不是必定能執行呢? 答案是不一定的。假設和上面一樣有一個 4 核心的系統，今天我有 4 個小任務，其執行時間和期限為 1 ms，然後有一個大任務，其執行時間和週期都是 1 秒。它的 CPU 使用率是小於 4 個。

$$\text{CPU time utilization}=4\ast \frac{1}{999}+\frac{1000}{1000}=1.004$$

但是它如果這 5 個任務是同時進入 ready queue 的，那因為期限，4 個小任務會先佔走 4 個處理器，執行完後才會給到大任務執行，但此時大任務就必定會超過截止期限 1 ms ，就如下圖所示，而這種 CPU 使用率比較小的情況，但在多核系統上會超出期限的效應就稱為 Dhall's effect 。

總結

這篇文章深入探討了 Linux 核心的 Preempt-RT 機制，涵蓋範圍廣泛，從 RTOS 的基本概念，到 Preempt-RT 中的 spinlock 調整、threaded interrupt、優先級繼承、延遲中斷、High Resolution Timer 以及即時排程器等主題。由此可以看出，解決即時任務期限問題涉及許多作業系統的相關挑戰。本文也將作為記錄，總結與反思這些議題。

References

wiki/RTLinux
Linux 核心設計: PREEMPT_RT 作為邁向硬即時作業系統的機制
Understanding Linux real-time with PREEMPT_RT training
A realtime preemption overview
Technical details of the real-time preemption
Real Time Linux Scheduling Comparison
实时Linux内核（PREEMPT_RT）的编译安装以及测试
Linux 核心設計: 中斷處理和現代架構考量
linux-insides
四種任務優先度 (prio、static_prio、rt_priority 與 normal_prio) 之間的差異
Deadline scheduling part 1 — overview and theory