Linux 核心搶佔

資料整理: jserv

何謂搶佔 (preemptive)？

在一個以優先權為主的排程策略中，當一個新的行程 (上圖的 Task₂) 進入到「可執行」(running) 的狀態，核心的排程器會去檢查它的優先權，若該行程的優先權比目前正在執行的行程 (即上圖的 Task₁) 還高，核心便會觸發搶佔 (preempt)，使得正在執行的行程被打斷，而擁有更高優先權的行程則會開始執行。

1. to occupy (land) in order to establish a prior right to buy.
2. to acquire or appropriate before someone else; take for oneself; arrogate:
   a political issue preempted by the opposition party.
3. to take the place of because of priorities, reconsideration, rescheduling, etc.; supplant:
   The special newscast preempted the usual television program.
   漢語「搶佔」沒有顯著「優先權」的意涵

早期 Linux 核心不支援核心搶佔，這會引發以下問題：

• 在 Linux v2.6 之前，當一個行程從使用者模式進入核心模式後，其他的行程只有等到已處於核心模式的行程在退出核心模式後，才有機會執行，這樣就會致使非預期的延遲。
• 若一個低優先權的行程在執行 critical section (CS) 時，中途被打斷，這會使得同樣需要進到該 CS 的高優先權行程被迫暫停，這可能會造成優先權反轉。

因此，搶佔的存在是為了讓更高優先權的任務，得以有更低的延遲 (latency)，從而提高系統的即時 (real-time) 能力。

延伸閱讀: Linux 核心設計: PREEMPT_RT 作為邁向硬即時作業系統的機制

搶佔何時發生？

在 Linux 核心中，使用者層級的搶佔是由被搶佔者行程 A 及搶佔行程 B 共同完成。示意如下:

行程 B 有較行程 A 更高的優先權，因此我們說 Process B preempts A

這不是字面上，由行程 B 單方面奪走 CPU 的使用權，而是行程 B 在確認具有搶佔資格後，藉由行程 A 的 TIF_NEED_RESCHED 旗標，告知行程 A 其需讓出 CPU 的使用權，待行程 A 執行到搶佔點時，會檢查該旗標，來選擇自己是否有權繼續執行，若發現旗標已被設定，則觸發重新排程 (reschedule，簡稱 resched)，讓排程器選擇具有更高優先權的行程執行。整體流程如下:

1. 行程 B 進入可執行的狀態
2. 核心檢查行程 B 的優先權
3. 若其優先權高於正在執行的行程 A，則設定行程 A 的 TIF_NEED_RESCHED 旗標
4. 當行程 A 執行到搶佔點時，檢查其 TIF_NEED_RESCHED 旗標，若該旗標已設定，則觸發重新排程，而若是核心層級的行程，除了檢查旗標，還要再檢查 preempt_count

何時設定 TIF_NEED_RESCHED ？

1. 目前行程執行完被分配的時間後

在目前行程執行完被分配的時間後，若遲遲沒讓出 CPU，則由計時器中斷觸發搶佔，其處理函式如下：

void scheduler_tick(void)
{
    int cpu = smp_processor_id();
    struct rq *rq = cpu_rq(cpu);
    struct task_struct *curr = rq->curr;
    ...
    curr->sched_class->task_tick(rq, curr, 0);
    ...
}

計時器中斷處理函式會取出目前 CPU 正在執行的行程的 task_struct，並呼叫其排程器類別的 task_tick() 函式，之後呼叫的流程如下：

task_tick()

$\to$ entity_tick()

$\to$ update_curr()

其中 update_curr() 會更新正在執行的行程的 vruntime，之後會由 entity_tick() 函式呼叫 check_preempt_tick() 來觸發搶佔。

2. 新喚醒的行程優先權高於正在執行的行程時

Linux 核心共提供三個函式來喚醒行程，分別是:

• wake_up_new_task(): 用來喚醒新的行程，例如 fork 出來的行程
• wake_up_process(): 用來喚醒處於 TASK_NORMAL 狀態的行程
• wake_up_state(): 用來喚醒指定狀態的行程

而最後二者都會呼叫到 try_to_wake_up() 函式，之後呼叫的流程如下如下：

try_to_wake_up()

$\to$ ttwu_queue()

$\to$ ttwu_do_activate()

$\to$ ttwu_do_wake_up()

在 wake_up_new_task() 及 ttwu_do_wake_up() 函式中，皆呼叫 check_preempt_curr() 函式，其內容如下：

void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
{
    if (p->sched_class == rq->curr->sched_class)
        rq->curr->sched_class->check_preempt_curr(rq, p, flags);
    else if (p->sched_class > rq->curr->sched_class)
        resched_curr(rq);
    ...
}

可見，若搶佔者行程及被搶佔行程的 sched_class 相同，則會呼叫相對應排程器類別的 check_preempt_curr()，根據不同的排程器類別來決定是否搶佔，而若搶佔者行程的排程器類別的優先權高於被搶佔行程，則會無條件呼叫 resched_curr() 函式來設定 TIF_NEED_RESCHED。

而在個別排程類別中，以下以 fair 類別為例：

static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
{
    ...
    if (unlikely(task_has_idle_policy(curr)) &&
        likely(!task_has_idle_policy(p)))
        goto preempt;
    ...
    if (wakeup_preempt_entity(se, pse) == 1) {
        if (!next_buddy_marked)
            set_next_buddy(pse);
        goto preempt;
    }
	return;

preempt:
    resched_curr(rq);
    ...
}

static int
wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
{
    s64 gran, vdiff = curr->vruntime - se->vruntime;

    if (vdiff <= 0)
        return -1;

    gran = wakeup_gran(se);
    if (vdiff > gran)
        return 1;

    return 0;
}

在 fair 排程類別中，共有兩種情況會發生搶佔：

1. 目前正在執行的行程為 IDLE 行程，且搶佔者行程並非 IDLE 行程時
2. 當兩個行程的 vruntime 差值大於 gran 時

最終呼叫 reshced_curr() 函式來設定 TIF_NEED_RESCHED 旗標。

何時設定 preempt_count ？

對於核心層級的行程而言，搶佔不僅要檢查 TIF_NEED_RESCHED 外，還需要檢查 preempt_count 是否為 0：只有在 preempt_count 為 0 時，才能觸發搶佔。為此，核心提供一系列的巨集來設定及檢查 preempt_count。

#define preempt_count_add(val)	// preempt_count 增加 val
#define preempt_count_sub(val)	// preempt_count 減少 val

#define preempt_count_inc() // preempt_count 遞增
#define preempt_count_dec() // preempt_count 遞減

#define preempt_disable() // 禁止搶佔且 preempt_count 遞增
#define preempt_enable() // 開放搶佔且 preempt_count 遞減

#ifdef CONFIG_PREEMPTION
#define preempt_enable() \
do { \
    barrier(); \
    if (unlikely(preempt_count_dec_and_test())) \
        __preempt_schedule(); \
} while (0)

在 preempt_enable() 中，會用 preempt_count_dec_and_test() 巨集來檢查 preempt_count 是否為 0，如果是則會呼叫 __preempt_schedule() 來觸發排程。

核心程式碼較少直接使用 preempt_enable() 或 preempt_disable()，相對更常使用 lock，而我們知道，只要不是 PREEMPT_RT (以下簡稱 RT) 的核心組態，spinlock 不能被打斷，其實就是在 lock 時使用 preempt_disable() ，並於 unlock 時使用 preempt_enable()，換言之，每次使用 spinlock 結束時，會預設觸發一次搶佔。

何時執行搶佔？

使用者層級執行搶佔

一般的使用者行程可被搶佔的地方較為固定，主要是：

1. 系統呼叫結束

在系統呼叫結束後，準備返回使用者模式時會進行檢查，以 x86 架構為例，其系統呼叫的流程如下：

do_syscall_64()

$\to$ syscall_exit_to_user_mode()

$\to$ exit_to_user_mode_prepare()

$\to$ exit_to_user_mode_loop()

其中 exit_to_user_mode_loop() 的函式內容如下：

static unsigned long exit_to_user_mode_loop(struct pt_regs *regs,
					    unsigned long ti_work)
{
    while (ti_work & EXIT_TO_USER_MODE_WORK) {
        local_irq_enable_exit_to_user(ti_work);

        if (ti_work & _TIF_NEED_RESCHED)
            schedule();
        ...
}

可見，若 TIF_NEED_RESCHED 旗標被設定，便會觸發排程。

2. 中斷結束

當中斷結束，準備返回到使用者模式時，會執行下方一系列函式：

irqentry_exit()

$\to$ irqentry_exit_cond_resched()

irqentry_exit_cond_resched() 之函式內容如下：

void irqentry_exit_cond_resched(void)
{
    if (!preempt_count()) {
        /* Sanity check RCU and thread stack */
        rcu_irq_exit_check_preempt();
        if (IS_ENABLED(CONFIG_DEBUG_ENTRY))
            WARN_ON_ONCE(!on_thread_stack());
        if (need_resched())
            preempt_schedule_irq();
    }
}

可見若 preempt_count 為 0 且需要重新排程時，便會呼叫 preempt_scheule_irq() 函式。

在 Linux 中，許多中斷處理會拆分成以下二部分:

• top-half: 由硬體決定何時觸發，應該儘可能及早結束執行
• bottom-half (簡稱 bh): 由 top-half 來排程，實際執行時機要等所有等待中的 top-half 都處理後，才會開始

以時間順序來看是這樣:

以處理層級來看則是:

其中 bottom-half 在 Linux 核心對應的機制有三種:

• softirq: 即 software interrupt，在 interrupt context 內執行
• tasklet: 建構在 softirq 之上，動態註冊的軟體中斷，確保單一處理器核在特定時間內只能執行一個 tasklet
• workqueue: 在 process context 內執行排入的工作，容許較長的延遲或執行可能引發休眠的操作，相較 tasklet 更有彈性，後者的操作必須為 atomic (一氣呵成)

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

核心層級執行搶佔

以下針對非 RT 的核心組態。

1. 執行中斷時不允許搶佔

如前節所述，在中斷結束後會先判斷 preempt_count 及 TIF_NEED_RESCHED 來決定是否需要進行搶佔。

2. 執行 softirq 時不允許搶佔

在執行軟體中斷 (softirq) 前，核心會先調整 preempt_count 使其不為 0，待 softirq 執行完畢後，再執行以下:

void __local_bh_enable_ip(unsigned long ip, unsigned int cnt)
{
    ...
    /*
     * Keep preemption disabled until we are done with
     * softirq processing:
     */
    __preempt_count_sub(cnt - 1);

    if (unlikely(!in_interrupt() && local_softirq_pending())) {
        /*
         * Run softirq if any pending. And do it in its own stack
         * as we may be calling this deep in a task call stack already.
         */
        do_softirq();
    }

    preempt_count_dec();
    ...
    preempt_check_resched();
}

3. Critical Section 中不允許搶佔

核心在執行 critical section 如 spinlock 時不允許搶佔，待 critical section 執行完畢後透過 preempt_schedule() 來觸發搶佔。

待整理

• Linux kernel preemption and the latency-throughput tradeoff