进程调度

调度器

核心调度器

调度器的实现基于两个函数：周期性调度器函数和主调度器函数。这些函数根据现有进程的优先级分配CPU时间。这也是为什么整个方法称之为优先调度的原因。

周期性调度器函数

周期性调度器在scheduler_tick中实现，如果系统正在活动中，内核会按照频率HZ自动调用该函数。该函数主

要有两个任务如下：

• 更新相关统计量：管理内核中与整个系统和各个进程的调度相关的统计量。其间执行的主要操作是对各种计数器+1
• 激活负责当前进程的调度类的周期性调度方法

更新统计量函数：update_rq_clock()/calc_global_load_tick()

主调度器函数

在内核中的许多地方，如果要将CPU分配给与当前活动进程不同的另一个进程，都会直接调用主调度器函数(schedule)

主调度器负责将CPU的使用权从一个进程切换到另一个进程。周期性调度器只是定时更新调度相关的统计信息。

cfs队列实际上是用红黑树组织的，rt队列是用链表组织的。

调度类及运行队列

调度类

为方便添加新的调度策略，Linux内核抽象了一个调度类sched_class，目前为止实现5种调度类：

调度类	调度策略	调度算法	调度对象	task_tick函数
stop_sched_class（停机调度类）	无	无	停机进程	task_tick_stop
dl_sched_class（限期调度类）	SCHED_DEADLINE	最早期限有限	限期进程	task_tick_dl
rt_sched_class（实时调度类）	SCHED_FIFO	先进先出	实时进程	task_tick_rt
	SCHED_RR	轮流调度	实时进程	task_tick_rt
fair_sched_class（公平调度类）	SCHED_NORMAL	完全公平调度	普通进程	task_tick_fair
	SCHED_IDLE	完全公平调度	普通进程	task_tick_fair
idle_sched_class（空闲调度类）	无	无	空闲进程	task_tick_idle

运行队列

每个处理器有一个运行队列，结构体是rq，定义的全局变量如下：

rq是描述就绪队列，其设计是为每一个CPU就绪队列，本地进程在本地队列上排序：

调度进程

主动调度进程的而函数是schedule()，它会把工作委托给__schedule去处理

函数__shcedule的主要处理过程如下：

• 调用pick_next_task()以选择下一个进程。
• 调用context_switch()以切换进程。

context_swtich函数如下

/*
 * context_switch - switch to the new MM and the new thread's register state.
 */
static __always_inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,
	       struct task_struct *next, struct rq_flags *rf)
{
	struct mm_struct *mm, *oldmm;

	// 执行进程切换的准备工作
	prepare_task_switch(rq, prev, next);

	mm = next->mm;
	oldmm = prev->active_mm;
	/*
	 * For paravirt, this is coupled with an exit in switch_to to
	 * combine the page table reload and the switch backend into
	 * one hypercall.
	 */
	// 开始上下文切换，是每种处理器架构必须定义的函数
	arch_start_context_switch(prev);

	// 如果下一个进程是内核进程（成员mm是空指针），内核线程 没有用户虚拟地址空间
	if (!mm) {
		next->active_mm = oldmm;
		mmgrab(oldmm);
		// 通知处理器架构不需要切换用户虚拟地址空间。这种加速进程切换技术TLB
		enter_lazy_tlb(oldmm, next);
	} else
		// 如果下一个调度进程是用户进程，那么就调用此函数，切换进程用户虚拟地址空间
		switch_mm_irqs_off(oldmm, mm, next);

	// 如果上一个进程是内核线程，把成员active_mm为空，断开它与用户虚拟地址空间的联系。把它借用的
	// 的用户虚拟地址空间，保存在运行队列成员prev_mm中
	if (!prev->mm) {
		prev->active_mm = NULL;
		rq->prev_mm = oldmm;
	}

	rq->clock_update_flags &= ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);

	/*
	 * Since the runqueue lock will be released by the next
	 * task (which is an invalid locking op but in the case
	 * of the scheduler it's an obvious special-case), so we
	 * do an early lockdep release here:
	 */
	rq_unpin_lock(rq, rf);
	spin_release(&rq->lock.dep_map, 1, _THIS_IP_);

	/* Here we just switch the register state and the stack. */
	switch_to(prev, next, prev);
	barrier();

	return finish_task_switch(prev);
}

context_switch里做的主要有亮点

• 切换用户虚拟地址空间，ARM64架构使用默认的switch_mm_irqs_off，其实就是调用了一个switch_mm的函数

• 切换寄存器，宏switch_to把该工作委托给__switch_to去做

调度时机

继承调度的时间如下：

• 进程主动调用schedule()函数
• 周期性调度，抢占当前进程，强迫当前进程退出处理器
• 唤醒进程的时候，被唤醒的进程可能抢占当前进程
• 创建新进程的时候，新进程可能抢占当前进程

主动调度

进程在用户模式下运行的时候，无法直接调用schedule()函数，只能通过系统调用进入内核模式，如果系统调

用需要等待某个资源，如互斥锁或信号量，就会把进程的状态设置为睡眠状态，然后调用schedule()函数来调

度进程。

周期调度

有些进程不主动让出处理器，内核只能依靠周期性的时钟中断夺回处理器的控制权，时钟中断是调度器的脉博。时钟中断处理程序检查当前进程的执行时间有没有超过限额，如果超过限额，设置需要重新调度的标志。当时钟中断处理程序准备返点处理器还给被打断的进程时，如果被打断的进程在用户模式下运行，就检查有没有设置需要重新调度的标志，如果设置了，调用schedule函数以调度进程。

SMP调度

在SMP系统中，进程调度器必须支持如下：

• 需要使用每个处理器的负载尽可能均衡
  • 期限调度类的处理器负载均衡：限期调度类的处理器负载均衡简单，调度选择下一个限期进程的时候，如果当前正在执行的进程是限期进程，将会试图从限期进程超载的处理器把限期进程搞过来。（超载定义：限期运行队列至少有两个限期进程；至少有一个限期进程绑定到多个处理器。）
  • 实时调度类的处理器负载均衡：实时调度类的处理器负载均衡和限期调度类相似。调度器选择下一个实时进程时，如果当前处理器的实时运行队列中的进程的最高调度优先级比当前正在执行的进程的调度优先级低，将会试图从实时进程超载的处理器把可推送实时进程拉过来。（超载定义：实时运行队列至少有两个实时进程；至少有一个可推送实时进程。）
  • 公平调度类的处理器负载均衡：目前多处理器系统有两种体系结构：NUMA和SMP。
    • 核(core)：一个处理器包含多个核，每个核独立的一级缓存，所有核共享二级缓存。
    • 硬件线程：也称为逻辑处理器或者虚拟处理器，一个处理器或者核包含多个硬件线程，硬件线程共享一级缓存和二级缓存。MIPS处理器的叫法是同步多线程(Simultaneous Multi-Threading,SMT)，英特尔对它的叫法是超线程。
• 可以设置进程的处理器亲和性，即允许进程在哪些处理器上执行
  • 设置进程的处理器亲和性，通俗就是把进程绑定到某些处理器，只允许进程在某些处理器上执行，默认情况是进程可以在所有处理器上执行。
• 可以把进程从一个处理器迁移到另一个处理器