进程切换

上一章介绍了调度相关的基础知识，那么这章准备介绍一下进程切换相关的原理。包括主调度器和周期性调度器都做了哪些工作。以及进程切换都做了哪些工作。

周期性调度器都做了什么

我们知道周期性调度器就是指scheduler_tick函数，下面我们看看这个函数都干了什么，代码如下：
在看代码之前，很多人都会又一个疑问，这个周期性调度器是如何被调用的。其实scheduler_tick()是由Linux时间子系统的tick_device调用。tick_device是一个周期性定时器，定时时间为1个tick，当触发中断后，会在中断处理函数中，调用scheduler_tick()

其实调用关系如下：

event_handler（具体函数是tick_handle_periodic或者tick_handle_periodic_broadcast）-> tick_periodic(cpu);->update_process_times(user_mode(get_irq_regs())); ->scheduler_tick(); 

event_handler就是中断处理函数的回调，在注册的时候，会根据不同的情况注册不同的函数。如下图所示：

tick_device中断的详细实现原理可以看下面博客的详细介绍，这里不做详细的介绍了。
https://www.cnblogs.com/lingjiajun/p/11944753.html
下面我们看scheduler_tick的代码实现：

/* * This function gets called by the timer code, with HZ frequency. * We call it with interrupts disabled. */ 
void scheduler_tick(void) 
{ int cpu = smp_processor_id(); --------------（1）struct rq *rq = cpu_rq(cpu); ----------------（2）struct task_struct *curr = rq->curr; ----------（3）struct rq_flags rf; sched_clock_tick(); -----------------（4）rq_lock(rq, &rf); --------------------（5）update_rq_clock(rq); -------------------（6）curr->sched_class->task_tick(rq, curr, 0); -----------（7）cpu_load_update_active(rq); ------------------（8）calc_global_load_tick(rq); --------------------（9）rq_unlock(rq, &rf); -------------------------（10）perf_event_task_tick(); -----------------（11）#ifdef CONFIG_SMP rq->idle_balance = idle_cpu(cpu); trigger_load_balance(rq); ----------------（12）
#endif 
} 

（1）

获取当前触发定时器中断的cpu

（2）

获取这个cpu 对应的runqueue 队列指针

（3）

获取runqueue中当前运行task的节点

（4）

更新每cpu上的sched_lock_data,这个sched_lock_data是干啥的，我这里还没有搞清楚，这里先不介绍了。

（5）

给runqueue 上锁，获取runqueue 里面得自旋锁，这里已经disable了当前cpu得时钟中断。代码如下

（6）

更新rq里面的clock和clock_task变量。这两个变量主要是记录当前系统得clock变量。

（7）

执行调度器类中得task_tick函数，这里在dl，rt和cfs调度器中，分别对应着函数task_tick_dl/task_tick_rt
/task_tick_fair函数。

task_tick_dl

函数代码如下：

主要得功能就是：

update_curr_dl(rq);

1.更新当前task的sum_exec_runtime
2.对runtime做扣除
3.触发throttle机制throttle之后，将当前task dequeueu。对于throttle的task, 还没有消除throttle不会重新enqueue。

update_dl_rq_load_avg(rq_clock_task(rq), rq, 1)

计算dl run queue中得负载信息，用于负载均衡，或者cpu调频等功能。

task_tick_rt

函数代码如下所示：

其中主要得函数

update_curr_rt(rq);

更新当前任务运行时间是任务调度一个非常重要的行为：任务运行多久、何时选择下一个任务、选择哪个任务运行以及cpu负载均衡等等都需要是基于任务信息不断更新来进行的。如果使能了带宽限制(即sysctl_sched_rt_runtime >= 0)，还要更新当前任务的运行队列(即叶子节点)到其祖先(root 节点)所在的运行队列的运行时间。其次调用sched_rt_runtime_exceeded函数检查运行队列的运行时间是否超过额定运行时间，如果超过额定运行时间还要通过resched_curr(rq)将就绪队列rq上的当前任务设置为TIF_NEED_RESCHED标志以被调度出去。

update_rt_rq_load_avg(rq_clock_task(rq), rq, 1);

通过这个函数来计算rt rq上的负载信息，这里采用的时pelt算法。时通过调用函数___update_load_sum和函数 ___update_load_avg实现的。
后面就是看调度测率是不是FIFO，如果是，再看时间片是否用完了，如果时间片还没完，就退出，否则就检查当前的FIFO链表，把当前的进程放到链表的末端。

task_tick_fair

这个函数是调度器类cfs的task_tick函数，代码如下：

CFS完全公平调度器类通过task_tick_fair函数完成周期性调度的工作，我们可以看到, CFFS周期性调度的功能实际上是委托给entity_tick函数来完成的。这里在遍历se，从se中找到对应的rq，然后对rq的统计信息进行更新，这里的统计信息包含时间信息和负载信息，时间信息涉及到vruntime的信息，这里不做详细的介绍，后面详细介绍cfs调度算法的时候再详细介绍。

entity_tick

还是调用update_curr(cfs_rq);来更新统计信息，然后调用update_load_avg来更新负载信息。
接下来是hrtimer的更新, 这些由内核通过参数CONFIG_SCHED_HRTICK开启
然后如果cfs就绪队列中进程数目nr_running少于两个(< 2)则实际上无事可做. 因为如果某个进程应该被抢占, 那么至少需要有另一个进程能够抢占它(即cfs_rq->nr_running > 1) 如果进程的数目不少于两个, 则由check_preempt_tick作出决策。check_preempt_tick函数的目的在于, 判断是否需要抢占当前进程. 确保没有哪个进程能够比延迟周期中确定的份额运行得更长。如果检查发现当前进程运行需要被抢占, 那么通过resched_task发出重调度请求. 这会在task_struct中设置TIF_NEED_RESCHED标志, 核心调度器会在下一个适当的时机发起重调度。

（8）

cpu_load_update_active函数是cpu级别的负载计算，负责更新就绪队列的cpu_load数组, 其本质上相当于将数组中先前存储的负荷值向后移动一个位置, 将当前就绪队列的符合记入数组的第一个位置. 另外该函数还引入一些取平均值的技巧, 以确保符合数组的内容不会呈现太多的不联系跳读.这里采用的是PELT算法来计算五个窗口期内cpu的负载情况，详细的计算算法这里不做详细的介绍了。

（9）

calc_global_load_tick函数主要时跟新cpu的活动计数, 主要是更新全局cpu就绪队列的统计。

（10）

解锁自旋锁

(11)

与perf计数事件相关。

（12）

进行周期性负载平衡则触发SCHED_SOFTIRQ，负载均衡其实也是一个很复杂的逻辑，我还没有搞清楚，先不做详细的介绍了。

主调度器都做了什么

主调度器其实就是指函数schedule（）函数，下面是其代码，其实这里核心的实现是函数__schedule

看到上面的代码，其实很想知道current是怎么得到当前进程的task的，下面是current的实现。

#define current get_current()
#define get_current() (current_thread_info()->task)

对于每种平台current_thread_info()这个函数是不一样的，和架构相关。但是具体的原理其实就是从thread info中拿到进程task_struct的指针。
sched_submit_work用于检测当前进程是否有plugged io需要处理，由于当前进程执行schedule后，有可能会进入休眠，所以在休眠之前需要把plugged io处理掉防止死锁。
preempt_disable是禁止抢占，后面执行完调度之后还会调用sched_preempt_enable_no_resched()来使能抢占。
执行__schedule()这个函数是调度的核心处理函数，当前CPU会选择到下一个合适的进程去执行了。need_resched()执行到这里时说明当前进程已经被调度器再次执行了，此时要判断是否需要再次执行调度。
下面我们看看__schedule函数都干了写什么。



我们这里主要介绍几个重要的函数：
（1）rcu_note_context_switch();
更新全局状态，标识当前CPU发生上下文的切换

这里这个判断r检查prev的状态state和内核抢占表示如果prev是不可运行的, 并且在内核态没有被抢占， 此时当前进程不是处于运行态, 并且不是被抢占。此时不能只检查抢占计数 因为可能某个进程(如网卡轮询)直接调用了schedule， 如果不判断prev->stat就可能误认为task进程为RUNNING状态 到达这里，有两种可能，一种是主动schedule, 另外一种是被抢占 被抢占有两种情况, 一种是时间片到点, 一种是时间片没到点 时间片到点后, 主要是置当前进程的need_resched标志 接下来在时钟中断结束后, 会preempt_schedule_irq抢占调度那么我们正常应该做的是应该将进程prev从就绪队列rq中删除, 但是如果当前进程prev有非阻塞等待信号, 并且它的状态是TASK_INTERRUPTIBLE， 我们就不应该从就绪队列总删除它 而是配置其状态为TASK_RUNNING, 并且把他留在rq中。

(2)pick_next_task
选择抢占的进程内核从cpu的就绪队列中选择一个最合适的进程来抢占CPU,全局的pick_next_task函数会从按照优先级遍历所有调度器类的pick_next_task函数, 去查找最优的那个进程, 当然因为大多数情况下, 系统中全是CFS调度的非实时进程, 因而linux内核也有一些优化的策略如果当前cpu上所有的进程都是cfs调度的普通非实时进程, 则直接用cfs调度, 如果无程序可调度则调度idle进程。代码逻辑如下：

其中for_each_class遍历所有的调度器类, 依次执行pick_next_task操作选择最优的进程
它会从优先级最高的sched_class_highest(目前是stop_sched_class)查起, 依次按照调度器类的优先级从高到低的顺序调用调度器类对应的pick_next_task_fair函数直到查找到一个能够被调度的进程。
其实执行各个调度器类的pick_next_task函数才是选择任务的核心算法，是从dl_rq 还是rt_rq 还是cfs_rq里面选择进程，所有的算法是不同的。根据不同的算法，选择不同的进程。这里不做详细的介绍了。其详细的实现，在对应的调度器类中pick_next_task。
(3)context_switch进程上下文切换context_switch
主要事在函数context_switch内完成的，其代码如下：

上下文切换(有时也称做进程切换或任务切换)是指CPU从一个线程切换到另一个线程的过程，主要包含软件层面的上下文切换和硬件层面的上下文切换。而硬件层面的切换其实这个过程是和架构相关的。
整个过程其实主要包含如下过程：

（1）挂起一个进程，将这个进程在 CPU 中的状态（上下文）存储于内存中的某处，
（2）在内存中检索下一个进程的上下文并将其在 CPU 的寄存器中恢复
（3）跳转到程序计数器所指向的位置（即跳转到进程被中断时的代码行），以恢复该进程
因此上下文是指某一时间点CPU寄存器和程序计数器的内容, 广义上还包括内存中进程的虚拟地址映射信息.
上下文切换只能发生在内核态中, 上下文切换通常是计算密集型的。也就是说，它需要相当可观的处理器时间，在每秒几十上百次的切换中，每次切换都需要纳秒量级的时间。所以，上下文切换对系统来说意味着消耗大量的 CPU 时间，事实上，可能是操作系统中时间消耗最大的操作。Linux相比与其他操作系统（包括其他类 Unix 系统）有很多的优点，其中有一项就是，其上下文切换和模式切换的时间消耗非常少。

进程切换的前提条件设置TIF_NEED_RESCHED的时机

其实在任务做切换的时候，首先要判读task_struct 中的thread_info中的flag 变量是否设置了TIF_NEED_RESCHED这个标记，如果设置了，才有可能被切换，否则这个线程还会一直运行。下面是thread_info中的变量：

那么在什么时候去设置这个标记呢？其实主要在以下时机进行：

（1）scheduler_tick 时钟中断函数内设置

这里以cfs调度为例，代码流程如下图所示，这里就不做详细的流程介绍了

也就是在时钟中断触发周期性调度器的时候，也就是触发scheduler_tick函数的时候，调用关系如下：
scheduler_tick–>task_tick_fair->entity_tick(cfs_rq, se, queued)->check_preempt_tick(cfs_rq, curr); ->resched_curr(rq_of(cfs_rq))->set_tsk_need_resched(curr);
对于rt类的调度器调用关系如下：
scheduler_tick–>task_tick_rt->resched_curr(rq);->set_tsk_need_resched(curr);

（2）wake_up_proces唤醒进程的时候

如下图所示：

调用关系如下：
cfs调度器来说调度流程如下：
wake_up_process->try_to_wake_up(p, TASK_NORMAL, 0)->ttwu_queue(p, cpu, wake_flags);->ttwu_do_activate(rq, p, wake_flags, &rf);->ttwu_do_wakeup(rq, p, wake_flags, rf);->check_preempt_wakeup;->resched_curr(rq);->set_tsk_need_resched(curr);

对于rt调度器类来说调用流程如下：
wake_up_process->try_to_wake_up(p, TASK_NORMAL, 0)->ttwu_queue(p, cpu, wake_flags);->ttwu_do_activate(rq, p, wake_flags, &rf);->ttwu_do_wakeup(rq, p, wake_flags, rf);->check_preempt_curr_rt;->resched_curr(rq);->set_tsk_need_resched(curr);

对于dl调度器类来说调用流程如下：
wake_up_process->try_to_wake_up(p, TASK_NORMAL, 0)->ttwu_queue(p, cpu, wake_flags);->ttwu_do_activate(rq, p, wake_flags, &rf);->ttwu_do_wakeup(rq, p, wake_flags, rf);->check_preempt_curr_dl;->resched_curr(rq);->set_tsk_need_resched(curr);

（3）do_fork 创建新进程的时候

代码流程如下图所示：

（4）set_user_nice 修改进程nice值的时候

代码流程如下图所示：

（5）smp_send_reschedule 负载均衡的时候

执行调度即调用schedule()的时机

内核在判断当前进程标记是否为 TIF_NEED_RESCHED，是的话调用 schedule 函数，执行调度，切换上下文，这也是上面抢占(preempt)机制的本质。那么在哪些情况下会执行 schedule 呢？