Linux CFS调度器分析

进程被调度的条件是什么，以及真正发生调度的时刻又是在哪里？

以下结论和代码分析都是基于最新Linux master分支(Linux5.0)

1. 调度的时刻

1.1 当前进程主动放弃CPU或者调用msleep/down/wait等阻塞函数时,会直接调用schedule()函数。

1.2. 当前进程满足被调度条件时(设置了TIF_NEED_RESCHED标志位)，在下面几种情况会发生调度。

1. 内核态中断返回时(el1_irq->preempt_schedule_irq)

如果内核没用定义CONFIG_PREEMPT宏，那么就不能在内核中断返回时进行抢占

2. 调用preempt_enable允许抢占时(preempt_enable->__preempt_schedule->preempt_schedule->__schedule)

3. 用户态的异常处理(缺页/预取指)返回用户空间时

el0_sync->el0_da/el0_ia->ret_to_user->work_pending->do_notify_resume->schedule

4. 用户态中断处理，返回用户空间时

el0_sync->el0_irq->ret_to_user->work_pending->do_notify_resume->schedule

5. 用户态系统调用处理，返回用户空间时

el0_sync->el0_svc->ret_to_user->work_pending->do_notify_resume->schedule

2. 调度的条件

调度可以分为主动调度和被动调度

主动调度:就是进程调用了休眠/阻塞函数，如msleep/down/yield/wait_event等函数.

被动调用: 进程时间片用完，或者有优先级更高的进程. 此时进程会被设置TIF_NEED_RESCHED标志位

判断进程是否需要被调度，有以下几个地方

2.1 周期性的schedule_tick()

schdule_tick()->task_tick,这里看CFS的tick fair

tatic void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
	struct cfs_rq *cfs_rq;
	struct sched_entity *se = &curr->se;
	/*循环遍历se层级，判断当前se是否需要被调度出去 */
	for_each_sched_entity(se) {
		cfs_rq = cfs_rq_of(se);
		entity_tick(cfs_rq, se, queued);
	}

}

sstatic void
entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
	/*更新虚拟运行时间,curr/cfs负载，用户组负载 */
	update_curr(cfs_rq);
	update_load_avg(cfs_rq, curr, UPDATE_TG);
	update_cfs_group(curr);
	/*最终调用check_preempt_tick来计算是否需要被调度 */
	if (cfs_rq->nr_running > 1)
		check_preempt_tick(cfs_rq, curr);
}

发生抢占的条件:

1.实际运行时间大于理想运行时间

2.当前进程的虚拟时间与CFS最左侧进程的虚拟时间差值大于当前理想运行时间

不发生抢占的条件:

1. 当前进程运行时间小于最小粒度(sysctl_sched_min_granularity(0.75ms))

2. 当前进程虚拟时间更小

3. 当前进程虚拟时间虽然大于CFS最左侧进程虚拟时间，但是差值小于进程的理想运行时间.

static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    
    ideal_runtime = sched_slice(cfs_rq, curr);/*根据进程权重分到的理想运行时间 */
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
    if (delta_exec > ideal_runtime) {/*运行时间大于理想时间 */
        resched_curr(rq_of(cfs_rq));
        return;
    }
    /*如果运行时间小于最小粒度(0.75ms),则不抢占 */
    if (delta_exec < sysctl_sched_min_granularity)
        return;
    /*获取CFS中最小虚拟时间进程 */
    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));
}

2.2 唤醒调度

唤醒调度主要发生在进程调用wake_up_new_task/wake_up等函数接口，最终会调用到

try_to_wake_up->ttwu_do_wakeup->check_preempt_curr->wakeup_preempt_entity函数，发生唤醒抢占的条件:

唤醒进程的虚拟时间需要比当前进程小,且差值要大于根据唤醒进程权重来计算的1ms对应的虚拟时间

其中最小抢占粒度由sysctl_sched_wakeup_granularity定义，默认是1ms

tatic 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);/*1ms对应的虚拟时间 */
    if (vdiff > gran)
        return 1;/*如果大于1ms对应的虚拟时间 */

    return 0;
}

如果wakeup_preempt_entity返回1，则ttwu_do_wakeup会标记当前进程需要被调度，在返回try_to_wake_up后会打开系统抢占

preempt_enable，此时就有可能发生进程的切换.

2.3 高精度hrtick

sched core为每个cpu的run queue启动一个hrtimer定时器，超时时间为当前进程的时间片，超时后，调用entity_tick判断当前进程是否需要调度.

如果需要支持HRTICK sched,需要打开宏CONFIG_SCHED_HRTICK和是能HRTICK

SCHED_FEAT(HRTICK, true)

3. 调度schedule()分析

schedule主要做了三件事

1. 把当前进程移出运行队列（有条件移出）

2. 选择下一个可运行进程

3. 新旧进程的切换

static void __sched notrace __schedule(bool preempt)
{
	struct task_struct *prev, *next;
	unsigned long *switch_count;
	struct rq_flags rf;
	struct rq *rq;
	int cpu;

	cpu = smp_processor_id();
	rq = cpu_rq(cpu);
	prev = rq->curr;
	/*调度只能发生在开抢占状态下的进程上下文，其他情况都是非法调度*/
	schedule_debug(prev);
	
	/*nivcsw记录进程被切换的次数，hung task 检测就是根据这个计数来判断进程是否被异常阻塞 */
	switch_count = &prev->nivcsw;
	/* 如果进程为非运行状态且不是抢占调度，则把pre进程移除runnable队列*/
	if (!preempt && prev->state) {
		if (signal_pending_state(prev->state, prev)) {
			prev->state = TASK_RUNNING;
		} else {/*把进程从runnable队列移出  */
			deactivate_task(rq, prev, DEQUEUE_SLEEP | DEQUEUE_NOCLOCK);
		}
		switch_count = &prev->nvcsw;
	}
	/*选择下一个进程运行 */
	next = pick_next_task(rq, prev, &rf);
	/*清楚进程的抢占标记位 */
	clear_tsk_need_resched(prev);
	clear_preempt_need_resched();

	if (likely(prev != next)) {
		rq->nr_switches++;
		rq->curr = next;
		
		++*switch_count;

		/* 进行进程的切换 */
		rq = context_switch(rq, prev, next, &rf);
	} else {
		rq->clock_update_flags &= ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);
		rq_unlock_irq(rq, &rf);
	}

}

3.1 task出队列

函数调用关系: deactivate_task->dequeue_task->dequeue_task_fair

static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
	struct cfs_rq *cfs_rq;
	struct sched_entity *se = &p->se;
	
	for_each_sched_entity(se) {
		cfs_rq = cfs_rq_of(se);
		/* 把调度实体se移除cfs,并计算vruntime/min_vruntime/平均负载*/
		dequeue_entity(cfs_rq, se, flags);
		
		cfs_rq->h_nr_running--;

		/*如果用户组权重不为0，证明还有其他进程在用户组，不能把组se移除CFS  */
		if (cfs_rq->load.weight) {
			/* Avoid re-evaluating load for this entity: */
			se = parent_entity(se);
			/*
			 * Bias pick_next to pick a task from this cfs_rq, as
			 * p is sleeping when it is within its sched_slice.
			 */
			break;
		}
		flags |= DEQUEUE_SLEEP;
	}
	/*重新计算组负载 */
	for_each_sched_entity(se) {
		cfs_rq = cfs_rq_of(se);
		cfs_rq->h_nr_running--;
		update_load_avg(cfs_rq, se, UPDATE_TG);
		update_cfs_group(se);
	}

	if (!se)
		sub_nr_running(rq, 1);
	hrtick_update(rq);
}

static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
	/*
	 更新vruntime和min_vruntime,以及se的运行时间
	 */
	update_curr(cfs_rq);

	/*
	 更新se和cfs_rq的load_sum和load_avg负载参数
	 */
	update_load_avg(cfs_rq, se, UPDATE_TG);
	/*从cfs_rq中减去se的负载和runnable权重值 */
	dequeue_runnable_load_avg(cfs_rq, se);

	/*这里为什么是不等于cfs_rq->curr，才从红黑树中移出se??,
	因为se等于cfs_rq->curr,证明se正在CPU上运行，running状态的进程，
	不来就不在runnaable队列

       */
	if (se != cfs_rq->curr)
		__dequeue_entity(cfs_rq, se);
	/*标记se不在runnable队列 */
	se->on_rq = 0;
	/*从cfs_rq中减去se的权重值load */
	account_entity_dequeue(cfs_rq, se);

	/*更新用户组负载和权重 */
	update_cfs_group(se);

	/*
	 再一次更新cfs的min_vruntime
	 */
	if ((flags & (DEQUEUE_SAVE | DEQUEUE_MOVE)) != DEQUEUE_SAVE)
		update_min_vruntime(cfs_rq);
}

3.2 选择下一个task

选择红黑数中最左侧的se(虚拟运行时间最小)来运行

pick_next_task->pick_next_task_fair

static struct task_struct *
pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
	struct cfs_rq *cfs_rq = &rq->cfs;
	struct sched_entity *se;
	struct task_struct *p;
	int new_tasks;

	do {/* 从se层级中选择一个虚拟运行时间最小的se运行*/
		se = pick_next_entity(cfs_rq, curr);
		cfs_rq = group_cfs_rq(se);
	} while (cfs_rq);

	p = task_of(se);
	
	if (prev != p) {
		struct sched_entity *pse = &prev->se;
		/*把se设置到cfs_rq->curr */
		put_prev_entity(cfs_rq, pse);
		set_next_entity(cfs_rq, se);
	}

	p = task_of(se);

	return p;

}

3.3 进程切换

1.切换MMU的TLB

2.把prev进程寄存器保存到堆栈，并从next进程的堆栈恢复寄存器到CPU

context_switch->switch_to->__switch_to->cpu_switch_to

static __always_inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,
	       struct task_struct *next, struct rq_flags *rf)
{
	/*进程TLB的切换，有时间再来分析 */
	if (!mm) {
		next->active_mm = oldmm;
		mmgrab(oldmm);
		enter_lazy_tlb(oldmm, next);
	} else
		switch_mm_irqs_off(oldmm, mm, next);

	if (!prev->mm) {
		prev->active_mm = NULL;
		rq->prev_mm = oldmm;
	}

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

	prepare_lock_switch(rq, next, rf);

	/*进程切换，这里是prev的终点，next进程的起点 */
	switch_to(prev, next, prev);
	barrier();
	/*运行到这里时，已经属于next进程的上下文了，因为next进程也是从switch_to切还出去的，
         被调度回来，当然还是接着switch_to运行.
	而当prev进程再次被调度时，prev的值可能改变成另外的进程X了
	因为再调度回A时，可能不是从B->A
       有可能是 A->B->X->A
    */
	return finish_task_switch(prev);
}

ENTRY(cpu_switch_to)
	mov	x10, #THREAD_CPU_CONTEXT
	/*保存prev寄存器 */
	add	x8, x0, x10 /*x8 = &(prev->thread.cpu_context) */
	mov	x9, sp /*save prev stack pointer */
	/*save prev thread regitster to cpu_context */
	stp	x19, x20, [x8], #16		// store callee-saved registers
	stp	x21, x22, [x8], #16
	stp	x23, x24, [x8], #16
	stp	x25, x26, [x8], #16
	stp	x27, x28, [x8], #16
	stp	x29, x9, [x8], #16
	str	lr, [x8]
	/*恢复next进程寄存器 */
	/*x8 = &(next->thread.cpu_context) */
	add	x8, x1, x10
	ldp	x19, x20, [x8], #16		// restore callee-saved registers
	ldp	x21, x22, [x8], #16
	ldp	x23, x24, [x8], #16
	ldp	x25, x26, [x8], #16
	ldp	x27, x28, [x8], #16
	/*x9=sp x29 = fp */
	ldp	x29, x9, [x8], #16
	ldr	lr, [x8]
	mov	sp, x9
	/*这里把当前进程task_struct把保存到sp_el0中，所以current宏直接读取sp_el0即可 */
	msr	sp_el0, x1
	/*bl to next lr */
	ret
ENDPROC(cpu_switch_to)

4. 抢占调度

当打开CONFIG_PREEMT时，就会支持抢占内核进程，preempt_schedule_irq->__schedule(true)

asmlinkage __visible void __sched preempt_schedule_irq(void)
{
	
	do {
		preempt_disable();
		local_irq_enable();
		/*标记当前为抢占内核进程 */
		__schedule(true);
		local_irq_disable();
		sched_preempt_enable_no_resched();
	} while (need_resched());

}

在__schedule中，如果当前进程不是RUNNING状态，会把进程移除runable queue队列，考虑以下常见的代码:

for (; ;) {
 prepare_to_wait(&wq, &__wait, TASK_UNINTERRUPTIBLE);
 if (condition)
      break; #这里发生抢占
 schedule();
}
finish_wait();

在判断condition为false后，发生抢占调度，由于进程处于非运行状态，__schedule会把进程移除运行队列，导致这个存在再也无法调度的可能。所以加入了preemt标记, 如果preemt为true,不会把进程从runnable 队列移除。

Linux CFS调度器分析

1. 调度的时刻

2. 调度的条件

2.1 周期性的schedule_tick()

2.2 唤醒调度

2.3 高精度hrtick

3. 调度schedule()分析

3.1 task出队列

3.2 选择下一个task

3.3 进程切换

4. 抢占调度

继续阅读

Linux的进程管理

进程管理(七)--进程的加载1 程序的编译2 ELF文件格式3 程序启动4 处理参数结构5 加载ELF6 从ELF入口到main函数7 总结

进程管理(十一)---进程fork+vfork+clone1 进程的四要素2 fork3 vfork4 clone5. 总结

linux进程管理1 进程描述符和task结构体2、进程创建3、 Linux线程的实现机制

第十四章：Linux实操篇进程管理1、进程的基本介绍2、显示系统执行的进程3、终止进程kill和killall4、查看进程树pstree5、服务(service)管理6、动态监控进程7、查看系统网络情况netstat

linux进程监控及管理进程状态Linux 系统状态的查看及管理工具进程相关内存相关系统监控工具linux作业控制screen;COMMAND多脚本并行运行实例

LInux操作详解十一：linux进程管理十一：进程管理；

Linux系统管理——进程个计划任务管理第十二章进程个计划任务管理

《linux内核设计与实现-笔记2》

计算机操作系统还能这样玩？这一篇计算机操作系统的总结为你保驾护航（零风险、高质量、万字长文、建议收藏）

操作系统学习笔记——进程管理（进程与线程）

关于fork函数的使用问题

进程管理(八)--创建进程fork1 _do_fork函数分析2 copy_process函数分析3. wake_up_new_task唤醒新进程流程4. 总结

Linux内核之进程1:进程的概念

用户标识和进程调度

进程管理逻辑图