linux进程切换

说明：

1. Kernel版本：4.14
2. ARM64处理器，Contex-A53，双核
3. 使用工具：Source Insight 3.5， Visio

1. 概述

进程切换：内核将CPU上正在运行的进程挂起，选择下一个进程来运行。
ARM架构中，一个CPU核上一次只能运行一个任务，内核需要为任务分配运行时间来进行调度，以便同时能处理多个任务请求。如下图所示：

当进行任务调度的时候，设计的基本知识点框架如下：

• 自愿切换： 是指任务由于等待某种资源，将state改为非running状态后，主动调用schedule让出CPU

       1. 任务因为等待 IO 操作完成或者其它资源而阻塞。

       任务显式地调用 schedule 前，把任务运行态设置成 TASK_UNINTERRUPTIBLE。保证任务阻塞后不能因信号到来而引起睡眠过程的中断，从而被唤醒。 Linux 内核各种同步互斥原语，如 Mutex，Semaphore，wait_queue，R/W Semaphore，及其他各种引起阻塞的内核函数。

       2. 等待资源和特定事件的发生而主动睡眠。

        任务显式地调用 schedule 前，把任务运行态被设为 TASK_INTERRUPTIBLE。保证即使等待条件不满足也可以被任务接收到的信号所唤醒，重新进入运行态。 Linux 内核各种同步互斥原语，如 Mutex，Semaphore，wait_queue，及其它各种引起睡眠的内核函数。

       3. 特殊目的，例如 debug 和 trace。

        任务在显式地用 schedule 函数前，利用 set_current_state 将任务设置成非 TASK_RUNNING 状态。 例如，设置成 TASK_STOPPED 状态，然后调用 schedule 函数。强制切换： 任务装仍为running状态，但是失去CPU使用权，此时由于任务时间片用完、有更高优先级的任务、任务中调用了cond_resched()或者yield让出了CPU使用权 

2. 抢占

早期的Linux核心是不可抢占的。它的调度方法是：一个进程可以通过schedule()函数自愿地启动一次调度。非自愿的强制性调度只能发生在每次从系统调用返回的前夕，以及每次从中断或异常处理返回到用户空间的前夕。但是，如果在系统空间发生中断或异常是不会引起调度的。这种方式使内核实现得以简化。但常存在下面两个问题：

1. 如果这样的中断发生在内核中，本次中断返回是不会引起调度的，而要到最初使cpu从用户空间进入内核空间的那次系统调用或中断(异常)返回时才会发生调度。
2. 另外一个问题是优先级反转。在Linux中，在核心态运行的任何操作都要优先于用户态进程，这就有可能导致优先级反转问题的出现。例如，一个低优先级的用户进程由于执行软/硬中断等原因而导致一个高优先级的任务得不到及时响应。

当前的Linux内核加入了内核抢占(preempt)机制。内核抢占指用户程序在执行系统调用期间可以被抢占，该进程暂时挂起，使新唤醒的高优先级进程能够运行。这种抢占并非可以在内核中任意位置都能安全进行，比如在临界区中的代码就不能发生抢占。临界区是指同一时间内不可以有超过一个进程在其中执行的指令序列。在Linux内核中这些部分需要用自旋锁保护。

内核抢占要求内核中所有可能为一个以上进程共享的变量和数据结构就都要通过互斥机制加以保护，或者说都要放在临界区中。在抢占式内核中，认为如果内核不是在一个中断处理程序中，并且不在被 spinlock等互斥机制保护的临界代码中，就认为可以"安全"地进行进程切换。

Linux内核将临界代码都加了互斥机制进行保护，同时，还在运行时间过长的代码路径上插入调度检查点，打断过长的执行路径，这样，任务可快速切换进程状态，也为内核抢占做好了准备，抢占分为用户抢占和内核抢占。

2.1 用户抢占

2.1.1 抢占触发点

• 可以触发抢占的情况很多，比如进程的时间片耗尽、进程等待在某些资源上被唤醒时、进程优先级改变等。Linux内核是通过设置TIF_NEED_RESCHED标志来对进程进行标记的，设置该位则表明需要进行调度切换，而实际的切换将在抢占执行点来完成。

不看代码来讲结论，那都是耍流氓。先看一下两个关键结构体：struct task_struct和struct thread_info。我们在前边的文章中也讲过struct task_struct用于描述任务，该结构体的首个字段放置的正是struct thread_info，struct thread_info结构体中flag字段就可用于设置TIF_NEED_RESCHED，此外该结构体中的preempt_count也与抢占相关。

struct task_struct {
#ifdef CONFIG_THREAD_INFO_IN_TASK
	/*
	 * For reasons of header soup (see current_thread_info()), this
	 * must be the first element of task_struct.
	 */
	struct thread_info		thread_info;
#endif
        ...
}
 
/*
 * low level task data that entry.S needs immediate access to.
 */
struct thread_info {
	unsigned long		flags;		/* low level flags */
	mm_segment_t		addr_limit;	/* address limit */
#ifdef CONFIG_ARM64_SW_TTBR0_PAN
	u64			ttbr0;		/* saved TTBR0_EL1 */
#endif
	int			preempt_count;	/* 0 => preemptable, <0 => bug */
};
 
#include <asm/current.h>
#define current_thread_info() ((struct thread_info *)current)   //通过该宏可以直接获取thread_info的信息
#endif

看看具体哪些函数过程中，设置了TIF_NEED_RESCHED标志吧：

• 内核提供了set_tsk_need_resched函数来将thread_info中flag字段设置成TIF_NEED_RESCHED；
• 设置了TIF_NEED_RESCHED标志，表明需要发生抢占调度；

2.1.2 抢占执行点

用户抢占：抢占执行发生在进程处于用户态。
抢占的执行，最明显的标志就是调用了schedule()函数，来完成任务的切换。
具体来说，在用户态执行抢占在以下几种情况：

• 异常处理后返回到用户态；
• 中断处理后返回到用户态；
• 系统调用后返回到用户态；

如下图：

• ARMv8有4个Exception Level，其中用户程序运行在EL0，OS运行在EL1，Hypervisor运行在EL2，Secure monitor运行在EL3；
• 用户程序在执行过程中，遇到异常或中断后，将会跳到ENTRY(vectors)向量表处开始执行；
• 返回用户空间时进行标志位判断，设置了TIF_NEED_RESCHED则需要进行调度切换，没有设置该标志，则检查是否有收到信号，有信号未处理的话，还需要进行信号的处理操作；

2.2 内核抢占

Linux内核有三种内核抢占模型，先上图：

• CONFIG_PREEMPT_NONE：不支持抢占，中断退出后，需要等到低优先级任务主动让出CPU才发生抢占切换；
• CONFIG_PREEMPT_VOLUNTARY：自愿抢占，代码中增加抢占点，在中断退出后遇到抢占点时进行抢占切换；
• CONFIG_PREEMPT：抢占，当中断退出后，如果遇到了更高优先级的任务，立即进行任务抢占；

2.2.1 抢占触发点

• 在内核中抢占触发点，也是设置struct thread_info的flag字段，设置TIF_NEED_RESCHED表明需要请求重新调度。
• 抢占触发点的几种情况，在用户抢占中已经分析过，不管是用户抢占还是内核抢占，触发点都是一致的；

2.2.2 抢占执行点

内核抢占：抢占执行发生在进程处于内核态。

总体而言，内核抢占执行点可以归属于两大类：

• 中断执行完毕后返回内核空间，且这个时候内核具有可抢占性；
• 主动调用preemp_enable或schedule等接口的地方进行抢占调度；
• 当内核代码再一次具有可抢占性的时候（如:spin_unlock时）；
• 如果内核中的任务阻塞。

2.3 preempt_count

• Linux内核中使用struct thread_info中的preempt_count字段来控制抢占。
• preempt_count的低8位用于控制抢占，当大于0时表示不可抢占，等于0表示可抢占。
• preempt_enable()会将preempt_count值减1，并判断是否需要进行调度，在条件满足时进行切换；
• preempt_disable()会将preempt_count值加1；

此外，preemt_count字段还用于判断进程处于各类上下文以及开关控制等，如图：

3. 上下文切换流程

• 进程上下文：包含CPU的所有寄存器值、进程的运行状态、堆栈中的内容等，相当于进程某一时刻的快照，包含了所有的软硬件信息；
• 进程切换时，完成的就是上下文的切换，进程上下文的信息会保存在每个struct task_struct结构体中，以便在切换时能完成恢复工作；

进程上下文切换的入口就是__schedule()，分析也围绕这函数展开。

3.1 __schedule()

__schedule()函数调用分析如下：

主要的逻辑：

• 根据CPU获取运行队列，进而得到运行队列当前的task，也就是切换前的prev;
• 根据prev的状态进行处理，比如pending信号的处理等，如果该任务是一个worker线程还需要将其睡眠，并唤醒同CPU上的另一个worker线程;
• 根据调度类来选择需要切换过去的下一个task，也就是next；
• context_switch完成进程的切换；

3.2 context_switch()

context_switch()的调用分析如下：

核心的逻辑有两部分：

• 进程的地址空间切换：切换的时候要判断切入的进程是否为内核线程，1）所有的用户进程都共用一个内核地址空间，而拥有不同的用户地址空间；2）内核线程本身没有用户地址空间。在进程在切换的过程中就需要对这些因素来考虑，涉及到页表的切换，以及cache/tlb的刷新等操作。
• 寄存器的切换：包括CPU的通用寄存器切换、浮点寄存器切换，以及ARM处理器相关的其他一些寄存器的切换；

进程的切换，带来的开销不仅是页表切换和硬件上下文的切换，还包含了Cache/TLB刷新后带来的miss的开销。在实际的开发中，也需要去评估新增进程带来的调度开销。

 上一章学习了调度的方式，分为主调度器和周期性调度器，明白了进程切换分为自愿(voluntary)和强制(involuntary)两种。

本章的主要学习的内容如下：

• 内核自愿切换的主要场景有哪些，具体的流程如何
• 内核强制切换的主要场景有哪些，具体的流程如何

1 主动调度时机

通常情况下，我们的进程运行在用户空间，无法实现主动调度，仅能通过陷入内核态后的某个时机点进行调度，例如内核在等待资源的时候，将当前进程移到等待队列，并主动调用schedule()放弃CPU。

主动调度时机是指显式调用schedule()函数释放CPU，引起新一轮调度．一般发生在当前进程状态改变，如：进程终止、进程睡眠、进程对某些信号处理过程中等．

1.1 用户空间调用调度接口

通常情况下，我们的进程运行在用户空间，通过系统调用进入到内核空间，从而做一些更**高级**的事情。yield 系统调用主要是调用yield_task的接口，然后调度schedule让当前进程放弃 cpu，其接口 (kernel/sched/core.c)如下

SYSCALL_DEFINE0(sched_yield)
{
    struct rq *rq = this_rq_lock();
 
    schedstat_inc(rq->yld_count);
    current->sched_class->yield_task(rq);
 
    /*
     * Since we are going to call schedule() anyway, there's
     * no need to preempt or enable interrupts:
     */
    __release(rq->lock);
    spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
    do_raw_spin_unlock(&rq->lock);
    sched_preempt_enable_no_resched();
    schedule();
    return 0;
}

pause 系统调用首先将当前进程设置为 TASK_INTERRUPTIBLE 状态，其实就是给 task_struct 结构中的 state 字段赋值，附上 TASK_INTERRUPTIBLE 之后，在后续进程调度中就可以过滤掉这个进程，选择其他的进程进行调度。接着，同样是一个简单的 schedule 函数，进入到调度，其接口(kernel/signal.c)如下：

SYSCALL_DEFINE0(pause)
{
    while (!signal_pending(current)) {
        __set_current_state(TASK_INTERRUPTIBLE);
        schedule();
    }
    return -ERESTARTNOHAND;
}

futex (fast userspace mutex)，用来给上层应用构建更高级别的同步机制，是实现信号量和锁的基础。我们简化一下场景：一个进程在等待某个信号的时候，最终会通过系统调用进入到 futex。其kernel/futex.c接口如下

SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val,
        struct timespec __user *, utime, u32 __user *, uaddr2,
        u32, val3)
{
    ...
    return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);
}

这个系统调用有 6 个参数，参数类型和名称并列展开，上层应用在等待一个信号量的时候，给 op 这个参数的传递的是 FUTEX_WAIT_BITSET，我们通过调用链往下追

long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
        u32 __user *uaddr2, u32 val2, u32 val3)
{
    ...
    switch (cmd) {
        case FUTEX_WAIT:
            val3 = FUTEX_BITSET_MATCH_ANY;
        case FUTEX_WAIT_BITSET:
            return futex_wait(uaddr, flags, val, timeout, val3);
        ...
    }
    ...
}

改接口最终会调用futex_wait_queue_me可能会将自己设置为睡眠状态并且进行一次进程调度。

1.2 exit 进程退出

在一个进程退出的时候会触发进程调度，我们通过内核源码来证明这一点。应用层的进程在退出时，最终会通过 exit 系统调用进入到内核，调用如下(kernel/exit.c)：

SYSCALL_DEFINE1(exit, int, error_code)
{
    do_exit((error_code&0xff)<<8);
}

其最终会调用do_task_dead，最终将进程的state置位TASK_DEAD，然后调用__schedule，其实现如下

void __noreturn do_task_dead(void)
{
    /*
     * The setting of TASK_RUNNING by try_to_wake_up() may be delayed
     * when the following two conditions become true.
     *   - There is race condition of mmap_sem (It is acquired by
     *     exit_mm()), and
     *   - SMI occurs before setting TASK_RUNINNG.
     *     (or hypervisor of virtual machine switches to other guest)
     *  As a result, we may become TASK_RUNNING after becoming TASK_DEAD
     *
     * To avoid it, we have to wait for releasing tsk->pi_lock which
     * is held by try_to_wake_up()
     */
    smp_mb();
    raw_spin_unlock_wait(&current->pi_lock);
 
    /* causes final put_task_struct in finish_task_switch(). */
    __set_current_state(TASK_DEAD);
    current->flags |= PF_NOFREEZE;  /* tell freezer to ignore us */
    __schedule(false);
    BUG();
    /* Avoid "noreturn function does return".  */
    for (;;)
        cpu_relax();    /* For when BUG is null */
}

1.3 内核主动阻塞

进程陷入内核后的自愿放弃行为是不可见的，它隐藏在其他可能受阻的系统调用，比如open、read、write等。进程因这些系统调用而陷入内核，如果这些调用被阻塞，总不能让CPU阻塞在这里啥都不干吧，于是内核就替进程做主，自愿放弃CPU启动一次调度。

2 抢占调度时机

被动调度时间指不显示调用schedule()函数，只是PCB中的 need_resched 进程调度标志，该域置位为1将引起新的进程调度，而每当中断处理和系统调用返回时，核心调度程序都会主动查need_resched的状态(若置位，则主动调用 schedule ()函数。一般发生在新的进程产生时、某个进程优先级改变时、某个进程等待的资源可用被唤醒时、当前进程时间片用完等。

2.1 中断异常返回时调度

介绍中断之前，先描述一下什么是异常：进程的指令按照程序正常流程一直在 CPU 上跑，系统突然发生了一个带有异常号的异常，强迫 CPU 停止执行当前的指令，CPU 随后会在执行完当前指令之后，保存现场，根据异常号跳转到异常处理程序，处理完之后，回到被异常终止的下一条机器指令继续执行。

系统调用是常见一种类型的异常，也是应用代码从用户空间主动进入内核空间的唯一方式。另外一种常见的异常就是硬件中断，比如我们点下鼠标、按下键盘、网卡接收到数据、磁盘数据读写完毕等，都会触发一次硬件中断，运行在用户空间的进程会被动陷入到内核空间，进行中断处理程序的处理。armv8中断、系统调用的入口在arch/arm64/kernel/entry.S，实现的函数有el1_sync，el1_irq，el0_sync，el0_irq。其余都是invalid。

el1_sync：当前处于内核态时，发生了指令执行异常、缺页中断（跳转地址或者取地址）。
el1_irq：当前处于内核态时，发生硬件中断。
el0_sync：当前处于用户态时，发生了指令执行异常、缺页中断（跳转地址或者取地址）、系统调用。
el0_iqr：当前处于用户态时，发生了硬件中断。
2.1.1 中断异常内核空间抢占调度
当中断发生在内核态，中断el1_irq退出前，即irq handler之后，kernel_exit恢复现场之间。会去检查current进程的preempt_count和need_resched以判断是否需要进行一次抢占。

el1_irq:
    kernel_entry 1
    enable_dbg
#ifdef CONFIG_TRACE_IRQFLAGS
    bl  trace_hardirqs_off
#endif
 
    irq_handler
 
#ifdef CONFIG_PREEMPT
    ldr w24, [tsk, #TI_PREEMPT]     // get preempt count
    cbnz    w24, 1f             // preempt count != 0
    ldr x0, [tsk, #TI_FLAGS]        // get flags
    tbz x0, #TIF_NEED_RESCHED, 1f   // needs rescheduling?
    bl  el1_preempt
1:
#endif
#ifdef CONFIG_TRACE_IRQFLAGS
    bl  trace_hardirqs_on
#endif
    kernel_exit 1
ENDPROC(el1_irq)

如果内核开启了CONFIG_PREEMPT，抢占前的检查：preempt_count和need_resched，设置need_resched的地方，同时也会设置TIF_NEED_RESCHED，所以这里检查need_resched即可，如果设置了，就跳转到el1_preempt尝试抢占

#ifdef CONFIG_PREEMPT
el1_preempt:
    mov x24, lr
1:  bl  preempt_schedule_irq        // irq en/disable is done inside
    ldr x0, [tsk, #TI_FLAGS]        // get new tasks TI_FLAGS
    tbnz    x0, #TIF_NEED_RESCHED, 1b   // needs rescheduling?
    ret x24
#endif

preempt_schedule_irq中断抢占的核心函数。注意：执行到此中断仍是关闭的，所以跳转回来时中断也要是关闭的

//封装了__schedule函数，且它会保证返回时local中断仍关闭
asmlinkage __visible void __sched preempt_schedule_irq(void)
{
    enum ctx_state prev_state;
 
    /* Catch callers which need to be fixed */
    //检测异常：若抢占计数不为零，或者中断没有关闭 则dump_stack并产生oops
    BUG_ON(preempt_count() || !irqs_disabled());
    //保存当前cpu的异常状态下的上下文到prev_state
    prev_state = exception_enter();
 
    do {
        preempt_disable();    //关抢占，__schedule的过程不允许被抢占
        local_irq_enable();    //使能中断
        __schedule(true);    //调度器核心函数。true表示此次切换为抢占
        local_irq_disable();    //关闭中断
        sched_preempt_enable_no_resched();    //开抢占
    } while (need_resched());//如果调度出去后的进程操作了被中断进程的thread_info.flags，使它仍为TIF_NEED_SCHED，那就继续进行调度
    //恢复抢占前的保存在prev_state中的异常上下文。
    exception_exit(prev_state);
}

当中断发生在进程的用户态，中断程序处理完之后，势必也要返回到用户空间，在返回用户空间之前，也会做一件事情，判断是否要进行调度，如果需要，则顺便做一次进程调度。我们以arm64处理器为例，中断处理程序的入口是el0_irq，流程如下：

el0_irq:
    kernel_entry 0                                #将进程的寄存器值保存到内核栈中
el0_irq_naked:
    enable_dbg
#ifdef CONFIG_TRACE_IRQFLAGS
    bl    trace_hardirqs_off
#endif
 
    ct_user_exit
#ifdef CONFIG_HARDEN_BRANCH_PREDICTOR
    tbz    x22, #55, 1f
    bl    do_el0_irq_bp_hardening
1:
#endif
    irq_handler                            #中断处理
 
#ifdef CONFIG_TRACE_IRQFLAGS
    bl    trace_hardirqs_on
#endif
    b    ret_to_user                     #使用内核栈保存的寄存器值恢复进程的寄存器并返回用户模式
ENDPROC(el0_irq)

该接口在中断处理irq_handler后，通过ret_to_user返回用户空间的时候会发生一次调度

ret_to_user:
    disable_irq                // disable interrupts
    ldr    x1, [tsk, #TI_FLAGS]
    and    x2, x1, #_TIF_WORK_MASK
    cbnz    x2, work_pending
finish_ret_to_user:
    enable_step_tsk x1, x2
    kernel_exit 0
ENDPROC(ret_to_user)

关中断
获取thread_info中的flags变量的值,就是 task_struct 结构中的 thread_info 结构中的 flags 字段的偏移量
取出 task_struct->thread_info->flags 字段，然后通过与 _TIF_WORK_MASK 进行 and 操作，如果二进制位的值不为 0，就跳转（cbnz）到 work_pending 方法。

#define_TIF_WORK_MASK        (_TIF_NEED_RESCHED |_TIF_SIGPENDING | \
_TIF_NOTIFY_RESUME |_TIF_FOREIGN_FPSTATE)

进入最重要的接口do_notify_resume

/*
 * Ok, we need to do extra processing, enter the slow path.
 */
work_pending:
    mov    x0, sp                // 'regs'
    bl    do_notify_resume
#ifdef CONFIG_TRACE_IRQFLAGS
    bl    trace_hardirqs_on        // enabled while in userspace
#endif
    ldr    x1, [tsk, #TI_FLAGS]        // re-check for single-step
    b    finish_ret_to_user

参数中 thread_flags 的值就是上面保存在 x1 寄存器中的值，也就是 `task_struct->thread_info->flags，如果该flags置位_TIF_NEED_RESCHED，就进行调度

asmlinkage void do_notify_resume(struct pt_regs *regs,
                 unsigned int thread_flags)
{
    /*
     * The assembly code enters us with IRQs off, but it hasn't
     * informed the tracing code of that for efficiency reasons.
     * Update the trace code with the current status.
     */
    trace_hardirqs_off();
    do {
        if (thread_flags & _TIF_NEED_RESCHED) {
            schedule();
        } else {
            local_irq_enable();
 
            if (thread_flags & _TIF_SIGPENDING)
                do_signal(regs);
 
            if (thread_flags & _TIF_NOTIFY_RESUME) {
                clear_thread_flag(TIF_NOTIFY_RESUME);
                tracehook_notify_resume(regs);
            }
 
            if (thread_flags & _TIF_FOREIGN_FPSTATE)
                fpsimd_restore_current_state();
        }
 
        local_irq_disable();
        thread_flags = READ_ONCE(current_thread_info()->flags);
    } while (thread_flags & _TIF_WORK_MASK);
}

到此，中断返回到用户空间的调度就比较清楚了，当中断处理程序返回用户空间的时候，如果被中断的进程被设置了需要进程调度标志，那么就进行一次进程调度。

那么，什么时候当前进程会被设置这个标志位呢？

只有进入到内核空间才能设置当前进程需要调度标志，而系统调用是我们主动从用户空间进入到内核空间的唯一方式，那些系统调用会设置当前进程需要调度标志。

创建新进程
futex 唤醒进程
周期调度
Linux 内核里，中断和异常因其打断的上下文不同，在返回时可能会触发以下类型的任务调度，

User Preemption

中断和异常打断了用户态运行的任务，在返回时检查 TIF_NEED_RESCHED 标志，决定是否调用 schedule。

Kernel Preemption

中断和异常打断了内核态运行的任务，在返回时调用 preempt_schedule_irq。其代码会检查 TIF_NEED_RESCHED 标志，决定是否调用 schedule。

2.2 系统调用调度

当发生系统调用时，进程用户态转变成核心态，此时可能由于调度的资源需要等待资源，就会主动的调用进程切换，此时当系统调用完后，只能返回到用户态。我们来进一步查看SVC mode的处理。当系统调用时CPU会切换到SVC mode，并跳转到对应的地址去运行。kernel中会配置两个SVC Handler，分别对应这SVC_32/SVC_64两种mode，32bit程序和64bit程序执行系统调用会跳转到两个不同的handler去执行，arch/arm64/kernel/entry.S汇编代码中设置了SVC异常entry

el0_svc:
    adrp    stbl, sys_call_table        // load syscall table pointer
    uxtw    scno, w8            // syscall number in w8
    mov    sc_nr, #__NR_syscalls
el0_svc_naked:                    // compat entry point
    stp    x0, scno, [sp, #S_ORIG_X0]    // save the original x0 and syscall number
    enable_dbg_and_irq
    ct_user_exit 1
 
    ldr    x16, [tsk, #TI_FLAGS]        // check for syscall hooks
    tst    x16, #_TIF_SYSCALL_WORK
    b.ne    __sys_trace
    cmp     scno, sc_nr                     // check upper syscall limit
    b.hs    ni_sys
    mask_nospec64 scno, sc_nr, x19    // enforce bounds for syscall number
    ldr    x16, [stbl, scno, lsl #3]    // address in the syscall table
    blr    x16                // call sys_* routine
    b    ret_fast_syscall
ni_sys:
    mov    x0, sp
    bl    do_ni_syscall
    b    ret_fast_syscall
ENDPROC(el0_svc)

这个数组在创建时首先会把所有的数组成员设置为sys_ni_syscall，而后根据**arch/arm64/include/asm/unistd32.h**中定义了所有的系统调用接口

void * const sys_call_table[__NR_syscalls] __aligned(4096) = {
    [0 ... __NR_syscalls - 1] = sys_ni_syscall,
#include <asm/unistd.h>
};

我们重点关注ret_fast_syscall，其处理流程跟中断基本类似，判断条件，然后跳转到**[work_pending](https://elixir.bootlin.com/linux/v4.9.295/C/ident/work_pending)处理**

ret_fast_syscall:
    disable_irq                // disable interrupts
    str    x0, [sp, #S_X0]            // returned x0
    ldr    x1, [tsk, #TI_FLAGS]        // re-check for syscall tracing
    and    x2, x1, #_TIF_SYSCALL_WORK
    cbnz    x2, ret_fast_syscall_trace
    and    x2, x1, #_TIF_WORK_MASK
    cbnz    x2, work_pending
    enable_step_tsk x1, x2
    kernel_exit 0

与中断处理类似，具体系统调用函数退出后，公共系统调用代码返回用户空间时，可能会触发 User Preemption，即检查 TIF_NEED_RESCHED 标志，决定是否调用 schedule。 系统调用不会触发 Kernel Preemption，因为系统调用返回时，总是返回到用户空间，这一点与中断和异常有很大的不同。

2.3 禁止内核抢占结束时

当linux2.6的内核，作为支持内核抢占，Linux 只允许在当前内核上下文需要禁止抢占的时候才使用 preempt_disable 禁止抢占，内核代码在禁止抢占后，应该尽早调用 preempt_enable 使能抢占，避免引入高调度延迟。 为尽快处理在禁止抢占期间 pending 的重新调度申请，内核在 preempt_enable 里会调用 preempt_schedule 检查 TIF_NEED_RESCHED 标志，触发任务切换

2.4 内核中调用cond_resch

内核代码中显式调用cond_resched()触发抢占，它的核心函数是preempt_schedule_common，该接口重要是在不支持内核抢占的情况下，会主动调用**[__schedule](https://elixir.bootlin.com/linux/v4.9.295/C/ident/__schedule)**

#define cond_resched() ({            \
    ___might_sleep(__FILE__, __LINE__, 0);    \
    _cond_resched();            \
})
 
#ifndef CONFIG_PREEMPT
int __sched _cond_resched(void)
{
    if (should_resched(0)) {
        preempt_schedule_common();
        return 1;
    }
    return 0;
}
EXPORT_SYMBOL(_cond_resched);
#endif

3 触发抢占时机

抢占如果发生在进程处于用户态的时候，称为User Preemption（用户态抢占）；如果发生在进程处于内核态的时候，则称为Kernel Preemption（内核态抢占）。在2.6内核的之前，只支持用户抢占，Linux在2.6版本之后就支持内核抢占了，但是请注意，具体取决于内核编译时的选项：

- CONFIG_PREEMPT_NONE=y
不允许内核抢占。这是SLES的默认选项。
- CONFIG_PREEMPT_VOLUNTARY=y
在一些耗时较长的内核代码中主动调用cond_resched()让出CPU。这是RHEL的默认选项。
- CONFIG_PREEMPT=y
允许完全内核抢占。

如果在内核态发生中断，在中断处理完后，内核会检查TIF_NEED_RESCHED标志并调用schedule()执行抢占。所以每个进程都包含一个TIF_NEED_RESCHED标志，内核根据这个标志判断该进程是否应该被抢占，设置TIF_NEED_RESCHED标志就意味着触发抢占。本小节主要关注TIF_NEED_RESCHED标志什么时候被设置呢？

3.1 周期性中断

时钟中断处理函数会调用scheduler_tick()，这是调度器核心层(scheduler core)的函数，它通过调度类(scheduling class)的task_tick方法 检查进程的时间片是否耗尽，如果耗尽则触发抢占，详细进程管理(二十)----进程调度器

void scheduler_tick(void)
{
        ...
        curr->sched_class->task_tick(rq, curr, 0);
        ...
}

在周期性的时钟中断里，内核调度器检查当前正在运行任务的持续运行时间是否超出具体调度算法支持的时间上限，从而决定是否剥夺当前任务的运行。 一旦决定剥夺在 CPU 上任务的运行，则会给正在 CPU 上运行的当前任务设置一个请求重新调度的标志：TIF_NEED_RESCHED。TIF_NEED_RESCHED 标志置位后，并没有立即调用 schedule 函数发生上下文切换。真正的上下文切换动作是 User Preemption 或 Kernel Preemption 的代码完成的。

User Preemption 或 Kernel Preemption 在很多代码路径上放置了检查当前任务的 TIF_NEED_RESCHED 标志，并显式调用 schedule 的逻辑。 接下来很快就会有机会调用 schedule 来触发任务切换，这时抢占就真正的完成了。上下文切换发生时，下一个被调度的任务将由具体调度器算法来决定从运行队列里挑选。

例如，如果时钟中断刚好打断正在用户空间运行的进程，那么当周期性中断会将TIF_NEED_RESCHED标志位置位，随后时钟中断处理完成，并返回用户空间。此时中断返回会检查TIF_NEED_RESCHED标志位，如果置位就会调用schedule来完成上下文的切换

void scheduler_tick(void)
    |--arch_scale_freq_tick();
    |--sched_clock_tick()
    |--update_rq_clock(rq);
    |--thermal_pressure = arch_scale_thermal_pressure(cpu_of(rq));
    |--update_thermal_load_avg(rq_clock_thermal(rq), rq, thermal_pressure);
    |--curr->sched_class->task_tick(rq, curr, 0);//调用调度类对应的task_tick方法
    |      |--task_tick_fair(rq, curr, 0) //针对CFS调度类该函数是task_tick_fair
    |             |--for_each_sched_entity(se)
    |                    entity_tick(cfs_rq, se, queued)
    |--calc_global_load_tick(rq);
    |--psi_task_tick(rq);
    \--trigger_load_balance(rq);//触发SMP负载均衡

周期性调度是指Linux定时周期性地检查当前进程是否耗尽当前进程的时间片，也就是检查当前进程的实际运行时间是否超过理论计算的允许运行时间，并检查是否应该抢占当前进程。一般会在定时器的中断函数中，通过一层层函数调用最终到scheduler_tick()函数。

for_each_sched_entity： 此是一个宏定义for (; se; se = se->parent)，顺着se的parent链表往上走 ，如果有一个se运行时间超过分配限额时间就需要重新调度。如果组调度未打开的情况下，这里就是一层循环

task_tick_fair：主要通过调用entity_tick来决定当前进程是否已经耗尽时间片，如果耗尽则需要设置TIF_NEED_RESCHED 标记

entity_tick(cfs_rq, se, queued)
    |--update_curr(cfs_rq);//更新当前运行的调度实体的vruntime和就绪队列的min_vruntime
    |--update_load_avg(cfs_rq, curr, UPDATE_TG);//Update task and its cfs_rq load average
    |--update_cfs_group(curr);
    |--if (cfs_rq->nr_running > 1)
    |      check_preempt_tick(cfs_rq, curr);
    |          |--ideal_runtime = sched_slice(cfs_rq, curr);//计算curr进程在本次调度周期中应该分配的(理论)时间片
    |          |--delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;//当前进程已经运行的实际时间
    |          |--if (delta_exec > ideal_runtime)//如果实际运行时间已经超过分配给进程的时间片
    |          |      resched_curr(rq_of(cfs_rq));//需要抢占当前进程。设置TIF_NEED_RESCHED flag
    |          |      clear_buddies(cfs_rq, curr);
    |          |      return;
    |          |--if (delta_exec < sysctl_sched_min_granularity)//如果运行时间小于最小粒度时间，不应该抢占
    |          |      return;
    |          |--se = __pick_first_entity(cfs_rq);//从红黑树中找到虚拟时间最小的调度实体
    |          |--delta = curr->vruntime - se->vruntime;
    |          |--if (delta < 0) return;//当前进程的虚拟时间仍然比红黑树中最左边调度实体虚拟时间小,不应该被抢占
    |          |--if (delta > ideal_runtime) //希望权重小的任务更容易被抢占?
    |                  resched_curr(rq_of(cfs_rq));

check_preempt_tick()：如果就绪队列就绪态的调度实体个数大于1需要检查是否满足抢占条件，如果可以抢占就设置TIF_NEED_RESCHED flag,表示当前进程可以被调度出去(触发抢占场景之一)。

delta_exec是当前进程已经运行的实际时间。如果实际运行时间已经超过分配给进程的时间片，自然就需要抢占当前进程。设置TIF_NEED_RESCHED flag。为了防止频繁过度抢占，我们应该保证每个进程运行时间不应该小于最小粒度时间sysctl_sched_min_granularity（0.75ms）。因此如果运行时间小于最小粒度时间，不应该抢占。从红黑树中找到虚拟时间最小的调度实体。如果当前进程的虚拟时间仍然比红黑树中最左边调度实体虚拟时间小，也不应该发生调度。这里把虚拟时间和实际时间比较，看起来很奇怪。感觉就像是bug一样，然后经过查看提交记录，作者的意图是：希望权重小的任务更容易被抢占。

3.2 唤醒进程时候

当进程被唤醒的时候，如果优先级高于CPU上的当前进程，就会触发抢占。相应的内核代码中，当进程被唤醒的时候，如果优先级高于CPU上的当前进程，就会触发抢占。相应的内核代码中，当在try_to_wake_up/wake_up_process和wake_up_new_task中唤醒进程时, 内核使用全局check_preempt_curr看看是否进程可以抢占当前进程可以抢占当前运行的进程

//被唤醒进程的描述符指针(p), 
//可以被唤醒的进程状态掩码(state),
// 一个标志wake_flags，用来禁止被唤醒的进程抢占本地CPU上正在运行的进程.
static int
try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
{
...
    ttwu_queue(p, cpu, wake_flags);
stat:
    ttwu_stat(p, cpu, wake_flags);
out:
    raw_spin_unlock_irqrestore(&p->pi_lock, flags);
 
    return success;
}

ttwu_queue进程状态设置为TASK_RUNNING，并把该进程插入本地CPU运行队列rq来达到唤醒睡眠和停止的进程的目的

static inline void ttwu_activate(struct rq *rq, struct task_struct *p, int en_flags)
{
    activate_task(rq, p, en_flags);
    p->on_rq = TASK_ON_RQ_QUEUED;
 
    /* if a worker is waking up, notify workqueue */
    if (p->flags & PF_WQ_WORKER)
        wq_worker_waking_up(p, cpu_of(rq));
}

[ttwu_do_wakeup](https://elixir.bootlin.com/linux/v4.9.295/C/ident/ttwu_do_wakeup) 然后调用 check_preempt_curr，检查当前进程是否需要被抢占，如果需要，就会设置 TIF_NEED_RESCHED 标志check_preempt_curr 的定义如下

void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
{
    const struct sched_class *class;
 
    if (p->sched_class == rq->curr->sched_class) {
        rq->curr->sched_class->check_preempt_curr(rq, p, flags);
    } else {
        for_each_class(class) {
            if (class == rq->curr->sched_class)
                break;
            if (class == p->sched_class) {
                resched_curr(rq);
                break;
            }
        }
    }
 
    /*
     * A queue event has occurred, and we're going to schedule.  In
     * this case, we can save a useless back to back clock update.
     */
    if (task_on_rq_queued(rq->curr) && test_tsk_need_resched(rq->curr))
        rq_clock_skip_update(rq, true);
}

唤醒的进程和当前的进程同属于一个调度类，直接调用调度类的check_preempt_curr方法检查抢占条件。毕竟调度器自己管理的进程，自己最清楚是否适合抢占当前进程。
如果唤醒的进程和当前进程不属于一个调度类，就需要比较调度类的优先级。例如，当期进程是CFS调度类，唤醒的进程是RT调度类，自然实时进程是需要抢占当前进程的，因为优先级更高。就会调用 resched_curr 函数，它最终会设置 TIF_NEED_RESCHED 标志

3.3 新进程创建的时候

接下来，我们来分析 fork 系统调用是如何来设置进程需要调度的标识的，fork详细的过程见进程管理(八)–创建进程fork,创建完新进程之后，调用 wake_up_new_task 唤醒新进程，我们来看内核是如何唤醒新进程的，check_preempt_curr同样也会设置标志位，起流程如下：

void wake_up_new_task(struct task_struct *p)
{
    struct rq_flags rf;
    struct rq *rq;
    //将当前进程设置为 RUNNING 状态，后续即可调度
    raw_spin_lock_irqsave(&p->pi_lock, rf.flags);
    p->state = TASK_RUNNING;
...
    activate_task(rq, p, 0);
    p->on_rq = TASK_ON_RQ_QUEUED;
    trace_sched_wakeup_new(p);
//判断是否要抢占当前进程
    check_preempt_curr(rq, p, WF_FORK);
...
    task_rq_unlock(rq, p, &rf);
}

3.4 进程修改nice值的时候

如果进程修改nice值导致优先级高于CPU上的当前进程，也会触发抢占resched_curr。内核代码参见 set_user_nice()

void set_user_nice(struct task_struct *p, long nice)
{
   ....
    if (queued) {
        enqueue_task(rq, p, ENQUEUE_RESTORE);
        /*
         * If the task increased its priority or is running and
         * lowered its priority, then reschedule its CPU:
         */
        if (delta < 0 || (delta > 0 && task_running(rq, p)))
            resched_curr(rq);
    }
    if (running)
        set_curr_task(rq, p);
out_unlock:
    task_rq_unlock(rq, p, &rf);
}

3.5 futex 唤醒进程

除了 fork 系统调用，在 futex 系统调用的时候，也会设置需要调度的标志。，futex 的 wake 操作，最后同样会落到和 fork 一样的方法 check_preempt_curr，这个方法我们上面刚分析过，做的事情就是给当前线程设置一个需要调度的标志，在下一次中断返回时进行一次调度。

3.6 进行负载均衡的时候

在多CPU的系统上，进程调度器尽量使各个CPU之间的负载保持均衡，而负载均衡操作可能会需要触发抢占。

不同的调度类有不同的负载均衡算法，涉及的核心代码也不一样，比如CFS类在load_balance()中触发抢占:

4 总结

在不支持内核抢占的系统中，进程/线程一旦运行于内核空间，就可以一直运行，直到他主动放弃或者耗尽时间片为止，这样就会导致非常紧急的进程或线程长时间得不到运行。

为了提高Linux的实时性。在linux2.6中引入了“Kernel preemption”（内核抢占调度模式）。并很好的解决了这个问题。一句话就是抢占式内核可以在进程处于内核态时，进行抢占。

而根据进程抢占发生的时机, 抢占可以分为内核抢占和用户抢占, 内核抢占就是指一个在内核态运行的进程, 可能在执行内核函数期间被另一个进程取

用户抢占发生在以下几种情况

• 从系统调用返回用户空间；
• 从中断(异常)处理程序返回用户空间

内核抢占发生的时机，一般发生在：

• 当从中断处理程序正在执行，且返回内核空间之前。当一个中断处理例程退出，在返回到内核态时(kernel-space)。这是隐式的调用schedule()函数，当前任务没有主动放弃CPU使用权，而是被剥夺了CPU使用权。
• 当内核代码再一次具有可抢占性的时候，如解锁（spin_unlock_bh）及使能软中断(local_bh_enable)等, 此时当kernel code从不可抢占状态变为可抢占状态时(preemptible again)。也就是preempt_count从正整数变为0时。这也是隐式的调用schedule()函数
• 如果内核中的任务显式的调用schedule(), 任务主动放弃CPU使用权
• 如果内核中的任务阻塞(这同样也会导致调用schedule()), 导致需要调用schedule()函数。任务主动放弃CPU使用权