# Linux 核心搶佔
###### tags: `linux-kernel`
資料來源：[linux 内核抢占那些事](https://zhuanlan.zhihu.com/p/166032722?fbclid=IwAR3VW9P2pORN2eph9wyOtM2iM83seFp4UphNYymioVICj-_SinjUixsNQKo)
## 何謂搶佔 (preemptive)？
當一個新的行程進入到 `running state` 的時候，核心的排程器會去檢查它的優先權，如果該行程的優先權比目前正在執行的行程還高的話，核心便會觸發搶佔，使得正在執行的行程被打斷，而擁有更高優先權的行程則會開始執行。
其實早期的 Linux 核心是不支援搶佔的，但是這樣會引發兩個問題:
* 在 v2.6 版的核心之前，當一個行程從使用者模式進入核心模式後，其他的行程只有等到他退出核心模式才有機會得到執行權，這樣就會有延遲的問題。
* 若一個低優先權的行程在執行 `critical section` 時執行被打斷，這會使得同樣需要進到該 `critical section` 的高優先權行程被迫暫停，這可能會造成優先權反轉。
因此，簡單來說，搶佔的機制是為了讓更高優先權的任務可以即時的執行。
## 搶佔何時發生？
在 linux 核心中，使用者層級的搶佔實際上是由搶佔者行程A及被搶佔行程B共同完成的，並不如字面上，由行程A單方面的奪走 CPU 的使用權，實際上，行程A再確認具有搶佔資格後，僅透過行程B的 `TIF_NEED_RESHCED` 旗標，告知行程B其需讓出 CPU 的使用權，待行程B執行到搶佔點時，會檢查該旗標，來選擇自己是否有權繼續執行，若發現旗標被設置了，則觸發重新排程，讓排程器選擇具有更高優先權的行程執行。整體流程如下:
1. 行程A進入 `running state`
2. 核心檢查行程A的優先權
3. 若其優先權高於正在執行的行程B，則設置行程B的 `TIF_NEED_RESCHED` 旗標
4. 當行程B執行到搶佔點時，檢查其 `TIF_NEED_RESCHED` 旗標，若該旗標被設置了，則觸發重新排程，而若是核心層級的行程，除了檢查旗標，還要再檢查 `preempt_count`
### 何時設置 `TIF_NEED_RESCHED` ？
#### 1. 當前行程執行完被分配的時間後
在當前行程執行完被分配的時間後，若遲遲沒有讓出 CPU ，則由計時器中斷觸發搶佔，其處理函式如下：
```c
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()` 函式，之後呼叫到的函式如下：
```c
task_tick() -> entity_tick() -> 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()` 函式，之後呼叫到的函式如下：
```c
try_to_wake_up() -> ttwu_queue() -> ttwu_do_activate() -> ttwu_do_wake_up()
```
並且在 `wake_up_new_task()` 及 `ttwu_do_wake_up()` 函式中，皆呼叫了 `check_preempt_curr()` 函式，其內容如下：
```c
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 類別為例：
```c
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，只有在0的時候才能觸發搶佔。為此，核心提供了一系列的巨集來設置及檢查 `preempt_count`。
```c
#define preempt_count_add(val) // preempt_count 增加 val
#define preempt_count_sub(val) // preempt_count 減少 val
#define preempt_count_inc() // preempt_count 增加 1
#define preempt_count_dec() // preempt_count 減少 1
#define preempt_disable() // 禁止搶佔且 preempt_count 增加 1
#define preempt_enable() // 開放搶佔且 preempt_count 減少 1
#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()` 的比較少，相對的使用鎖的地方比較多，而我們知道， spinlock 是不能被打斷的，其實就是在 lock 時使用 `preempt_disable()` ，並在 unlock 時使用 `preempt_enable()` ，所以可以認為每次使用 spinlock 結束時會默認觸發一次搶佔。
## 何時執行搶佔
### 使用者層級執行搶佔
一般的使用者行程可以被搶佔的地方必較固定，主要為：
#### 1. 系統呼叫結束
在系統呼叫結束後，準備返回使用者模式時會進行檢查，以 x86 架構為例，其系統呼叫的流程如下：
```c
do_syscall_64() -> syscall_exit_to_user_mode() -> exit_to_user_mode_prepare() -> exit_to_user_mode_loop()
```
其中 `exit_to_user_mode_loop()` 的函式內容擷取如下：
```c
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. 中斷結束
當中斷結束，準備返回到使用者模式時，會通過下列的一系列函式：
```c
irqentry_exit() -> irqentry_exit_cond_resched()
```
`irqentry_exit_cond_resched()` 之函式內容如下：
```c
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()` 函式。
### 核心層級執行搶佔
#### 1. 執行中斷時不允許搶佔
如前節所述，在中斷結束後會先判斷 `preempt_count` 及 `TIF_NEED_RESCHED` 來決定是否需要進行搶佔。
#### 2. 執行軟中斷時不允許搶佔
在執行軟中斷前，核心會先調整 `preempt_count` 使其不為0，待軟中斷執行完畢後，再
```c
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()` 來觸發搶佔。
Sign in with Wallet
Connect another wallet