---
tags: LINUX KERNEL, LKI
---

# Linux 核心搶佔
> 資料整理: [jserv](https://wiki.csie.ncku.edu.tw/User/jserv)

## 何謂搶佔 (preemptive)？


在一個以優先權為主的排程策略中，當一個新的行程 (上圖的 Task~2~) 進入到「可執行」(running) 的狀態，核心的排程器會去檢查它的優先權，若該行程的優先權比目前正在執行的行程 (即上圖的 Task~1~) 還高，核心便會觸發搶佔 ([preempt](https://www.dictionary.com/browse/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.
> :notebook: 漢語「[搶佔](https://lib.ctcn.edu.tw/chtdict/content.aspx?TermId=22670)」沒有顯著「優先權」的意涵

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

因此，搶佔的存在是為了讓更高優先權的任務，得以有更低的延遲 (latency)，從而提高系統的即時 (real-time) 能力。
> 延伸閱讀: [Linux 核心設計: PREEMPT_RT 作為邁向硬即時作業系統的機制](https://hackmd.io/@sysprog/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 核心設計: 中斷處理和現代架構考量](https://hackmd.io/@sysprog/linux-interrupt)

### 核心層級執行搶佔

以下針對非 `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](https://www.codeblueprint.co.uk/2019/12/23/linux-preemption-latency-throughput.html)