Skip to content

3、进程调度

Harlon edited this page Jul 28, 2018 · 1 revision

进程调度程序可看做在可运行态进程之间分配有限的处理器时间资源的内核子系统。

目录


3.1 多任务

多任务操作系统就是能同时并发地交互执行多个进程的操作系统。多任务系统可以分为两类:

  • 非抢占式多任务:让步
  • 抢占式多任务:抢占、时间片

3.2 Linux的进程调度

2.5之前:O(1)调度器 2.6之后:完全公平调度算法CFS


3.3策略

3.3.1 I/O消耗型和处理器消耗型的进程

进程可以被分为I/O消耗型和处理器消耗型,前者是指处理器大多数时间都是再提交IO请求或者等待IO请求,而后者大多数都再运行代码,除非被抢占,这类任务通常会不停的运行,占用大量的CPU时间,调度器应该减少他们的执行频率。
调度策略通常要在两个矛盾的目标中寻找平衡:响应时间和吞吐量,Unix系统的调度程序更倾向于I/O消耗程序,以提供更好的程序响应时间,Linux为了保证交互式应用和桌面系统的性能,所以对进程的响应做了优化(缩短响应时间),更倾向于I/O消耗进程。


3.3.2 进程优先级

Linux提供了两种优先级策略:

  • nice值:范围是-2019,默认是0,值越大表示优先级越低,优先级越高会获得更多的处理器时间,Linux系统中,nice值代表时间片的比例,而Mac OS X中,进程的nice值代表分配给进程的时间片的绝对值。
  • 实时优先级:其值是可配置的,默认情况下从0~99,越高优先级越大,任何实时进程的优先级都高于普通进程。

3.3.3 时间片

时间片是一个数值,它表明进程在抢占前能够持续运行的时间。时间片的设置有很大的问题,如果时间片太长,导致有些任务无法及时调度, 如果太短,会明显增大进程切换的开销,前面提到的I/O消耗型进程希望时间片越小越好,这样能够及时的处理响应,而处理器消耗型希望时间片越长越好,尽可能多的占用处理器时间,能够明显的提高高速缓存的命中率。
Linux的CFS并没有直接分配时间片到进程,而是将处理器的使用比例划分到进程,这样的话,进程获得的处理器时间和系统负载有密切的关系,这个比例还会受到nice值的影响。
Linux中的CFS调度器,其抢占时机取决于新的可运行程序消耗了多少处理器使用比,如果消耗的使用比比当前进程小,则新进程立刻投入运行中,抢占当前进程,否则,推迟其执行。


3.4 Linux调度算法

3.4.1 调度器类

Linux调度器是以模块的方式提供的,称作为调度器类,它允许多种不同的可动态添加的调度算法并存,调度属于自己的进程,每个调度器都有一个优先级,基础的调度器的代码位于kernel/sched.c文件中,它会按照优先级顺序遍历调度类,拥有一个可执行进程的最高优先级的调度器类生出,去选择下面要执行的一个程序。
完全公平调度(CFS)是一个针对普通进程的调度类,在Linux中被称为SCHED_NORMALCFS算法实现定义在文件kernel/sched_fair.c中。


3.4.2 公平调度

CFS称为公平调度器是因为它确保给每个进程公平的处理器使用比,任何进程所获得的处理器时间是由他自己和其他可运行进程nice值的相对差值决定的。nice值对时间片的作用不再是算数加权,而是几何加权。


3.5 Linux调度的实现

Linux中CFS调度算法的代码位于文件kernel/sched_fair.c中,我们关注其四个组成部分:

  • 时间记账
  • 进程选择
  • 调度器入口
  • 睡眠和唤醒

3.5.1 时间记账

CFS算法中记录进程运行时间的结构体如下:

struct sched_entity {
	struct load_weight	load;		/* for load-balancing */
	struct rb_node		run_node;
	struct list_head	group_node;
	unsigned int		on_rq;
	u64			exec_start;
	u64			sum_exec_runtime;
	u64			vruntime;
	u64			prev_sum_exec_runtime;
	u64			last_wakeup;
	u64			avg_overlap;
	u64			nr_migrations;
	u64			start_runtime;
	u64			avg_wakeup;
	u64			avg_running;
...

这个记账信息保存在task_struct中的ee字段中,update_curr()函数完成了该记账功能。

static void update_curr(struct cfs_rq *cfs_rq)
{
	struct sched_entity *curr = cfs_rq->curr;
	u64 now = rq_of(cfs_rq)->clock_task;
	unsigned long delta_exec;

	if (unlikely(!curr))
		return;

	/*
	 * Get the amount of time the current task was running
	 * since the last time we changed load (this cannot
	 * overflow on 32 bits):
	 */
	delta_exec = (unsigned long)(now - curr->exec_start);
	if (!delta_exec)
		return;

	__update_curr(cfs_rq, curr, delta_exec);
	curr->exec_start = now;

	if (entity_is_task(curr)) {
		struct task_struct *curtask = task_of(curr);

		trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
		cpuacct_charge(curtask, delta_exec);
		account_group_exec_runtime(curtask, delta_exec);
	}
}

记账中最重要的变量是vruntime,虚拟运行时间,每隔一段时间内核会执行update_curr()函数,计算当前进程的执行时间,然后根据权值计算虚拟的运行时间,再加到vruntime变量上,Linux中进程的权值是由prio_to_weight这个数组定义的。

static const int prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

权值的计算公式如下:

虚拟运行时间 = 实际运行时间 * (NICE_0_LOAD / 权重)

其中NICE_0_LOADnice为0的权重,可以看到权重越大,虚拟运行时间越小,而Linux会选择虚拟时间最小的进行调度。

3.5.2 进程选择

CFS使用红黑树来组织可运行队列,并利用其迅速找到最小vruntime值的进程。它通过__pick_next_entity()函数来选择最小的vruntime

static struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
{
	struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);

	if (!last)
		return NULL;

	return rb_entry(last, struct sched_entity, run_node);
}

当进程变为可运行状态(被唤醒)或者是通过fork()调用第一次创建时,CFS将其加入红黑树种;当进程被阻塞或者终止时,CFS将其从红黑树中删除。


3.5.3 调度器入口

进程调度的主要入口点是函数schedule()schedule()会调用pick_next_task()从当前调度器中选择一个优先级最大的任务来调度,pick_next_task()会遍历调度器,从每一个调度器中执行pick_next_task()来选择要调度的进程,如果当前系统没有被调度的进程,则返回idle进程。

asmlinkage void __sched schedule(void)
{
	struct task_struct *prev, *next;
	unsigned long *switch_count;
	struct rq *rq;
	int cpu;

need_resched:
	preempt_disable();
	cpu = smp_processor_id();
	rq = cpu_rq(cpu);
	rcu_sched_qs(cpu);
	prev = rq->curr;
	switch_count = &prev->nivcsw;

	release_kernel_lock(prev);
need_resched_nonpreemptible:

	schedule_debug(prev);

	if (sched_feat(HRTICK))
		hrtick_clear(rq);

	spin_lock_irq(&rq->lock);
	update_rq_clock(rq);
	clear_tsk_need_resched(prev);

	if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
		if (unlikely(signal_pending_state(prev->state, prev)))
			prev->state = TASK_RUNNING;
		else
			deactivate_task(rq, prev, 1);
		switch_count = &prev->nvcsw;
	}

	pre_schedule(rq, prev);

	if (unlikely(!rq->nr_running))
		idle_balance(cpu, rq);

	put_prev_task(rq, prev);
	next = pick_next_task(rq);

	if (likely(prev != next)) {
		sched_info_switch(prev, next);
		perf_event_task_sched_out(prev, next, cpu);

		rq->nr_switches++;
		rq->curr = next;
		++*switch_count;

		context_switch(rq, prev, next); /* unlocks the rq */
		/*
		 * the context switch might have flipped the stack from under
		 * us, hence refresh the local variables.
		 */
		cpu = smp_processor_id();
		rq = cpu_rq(cpu);
	} else
		spin_unlock_irq(&rq->lock);

	post_schedule(rq);

	if (unlikely(reacquire_kernel_lock(current) < 0))
		goto need_resched_nonpreemptible;

	preempt_enable_no_resched();
	if (need_resched())
		goto need_resched;
}

pick_next_task实现:

/*
 * 挑选醉倒优先级的任务
 */
static inline struct task_struct *
pick_next_task(struct rq *rq)
{
	const struct sched_class *class;
	struct task_struct *p;

	/*
	 * 优化:我们知道所有任务都在公平类中,就可以直接调用公平类中的函数选择下一个进程
	 */
	if (likely(rq->nr_running == rq->cfs.nr_running)) {
		p = fair_sched_class.pick_next_task(rq);
		if (likely(p))
			return p;
	}

	class = sched_class_highest;
	for ( ; ; ) {
		p = class->pick_next_task(rq);
		if (p)
			return p;
		/*
		 * Will never be NULL as the idle class always
		 * returns a non-NULL p:
		 */
		class = class->next;
	}

3.5.4 睡眠和唤醒

睡眠的过程:进程把自己置为休眠状态,从可执行红黑树种移出,放入等待队列,然后调用schedule()选择和执行下一个进程。唤醒的过程刚好相反。休眠的两种相关的进程状态:TASK_INTERRUPTIBLETASK_UNINTERRUPTIBLE,他们的唯一区别是处于TASK_UNINTERRUPTIBLE的进程会忽略信号,而处于TASK_INTERRUPTIBLE状态的进程如果接受到一个信息,会被提前唤醒并响应该信号。


3.6 抢占和上下文切换

上下文切换就是从一个进程切换到下一个要执行的进程,由定义在kernel/sched.c中的context_switch()函数负责处理,当一个新的进程被选出来准备投入运行的时候,schedule()就会调用该函数。它完成两项基本的工作:

  • 调用<asm/mmu_context.h>中的switch_mm(),该函数负责把虚拟内存从上一个进程切换到下一个进程。
  • 调用<asm/system.h>中的switch_to()该函数负责从上一个进程的处理器状态切换到新的进程的处理器状态,这包括保存、恢复栈信息和寄存器信息,还有其他任何与体系结构相关的状态信息,都必须以每个进程为对象进行管理和保存。

schedule()函数的执行时机是通过need_resched这个标志来判断的。

3.6.1 用户抢占

内核即将返回用户空间的时候,如果need_reched标志被设置,会导致schedule()被调用。用户抢占在以下情况下产生:

  • 从系统调用返回用户空间时
  • 从中断处理程序返回用户空间时

3.6.2 内核抢占

内核抢占需要查看thread_info中的preempt_count计数器,这个计数器记录当前进程使用锁的个数,只有当前进程没有锁的时候,进程才能被抢占。


3.7 实时调度策略

Linux中有两种实时调度策略:SCHED_FIFOSCHED_RR,具体的实现在kernel/sched_rt.c
SCHED_FIFO:先入先出的调度策略,只有等当前进程自己受阻塞或者显式地释放处理器为止,才能调度后面的进程执行。
SCHED_RR:轮询式调度策略,带有时间片,时间片用完,在同一优先级的其他实时进程被轮流调度。
实时进程的优先级比普通进程要高。


3.8 与调度相关的系统调用

系统调用 描述
nice() 设置进程的nice值
sched_setscheduler() 设置进程的调度策略
sched_getscheduler() 获取进程的调度策略
sched_setparam() 设置进程的实时优先级
sched_getparam() 获取进程的实时优先级
sched_get_priority_max() 获取实时优先级的最大值
sched_get_priority_min() 获取实时优先级的最小值
sehed_rr_get_interval() 获取进程的时间片值
sched_setaffinity() 设置进程的处理器的亲和力
sched_getaffinity() 获取进程的处理器的亲和力
sched_yield() 暂时让出处理器
You can’t perform that action at this time.