2018-05-27发表2018-05-27更新Linux37 分钟读完 (大约5522个字)0次访问

Linux处理器调度

调度程序决定将哪个进程投入运行、何时运行以及运行多长时间。调度程序可以当做在可运行态进程之间分配有限的处理器时间资源的内核子系统。只有通过调度程序的合理调度，系统资源才能最大限度发挥作用，多进程才能够有并发执行效果。

本文源码版本4.16.7

查看源码

参考图书：Linux内核设计与实现

多任务分类

非抢占式多任务

除非任务自己结束，否则会一直执行
抢占式多任务

由调度程序决定什么时候停止一个进程的运行。采用抢占式多任务的基础是使用时间片轮转机制来为每个进程分配可以运行的时间单位。

Linux进程调度的发展

Linux从2.5版本开始使用一种叫做O(1)的调度程序，这种调度程序对于大服务器的工作负载很理想，但是由于缺少交互进程，在桌面系统上表现不佳。因此，从2.6版本开始，Linux开始使用“完全公平调度算法”（CFS）。

策略

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

I/O消耗型进程是指大部分时间都用来提交I/O请求或者等待I/O请求的进程，这样的进程经常处于可运行状态，但运行时间通常较短，因为它在等待更多的I/O请求的过程中总会阻塞。例如大多数的用户图形界面程序都属于I/O密集型的程序，多数时间都在等待来自鼠标或键盘的用户交互操作。

处理器耗费进程则把大多数时间用来执行代码，调度策略往往会尽量降低这种进程的调度频率，延长其运行时间。例如MATLAB等执行大量数学计算的程序。

调度策略往往在两个矛盾的目标中寻找平衡：进程响应迅速和最大系统利用率，Linux为了保证交互式应用和桌面系统的性能，对进程响应做了优化，更倾向于优先调度I/O消耗型进程。
进程优先级

Linux采用了两种不同的优先级范围。
- nice值
  
  nice值范围是-20~+19，默认为0；越大的nice值意味着更低的优先级。
- 实时优先级
  
  实时优先级的值可配置，默认情况下范围是0~99。与nice值意义相反，越高的实时优先级数值意味着进程优先级越高。
时间片

时间片的含义是进程在被抢占前所能持续运行的时间。Linux中并没有直接分配默认时间片，而是将处理器的使用比划分给进程。进程获得的处理器时间与系统负载密切相关，这个比例还会受到nice值的影响。

调度算法

调度器类

Linux调度器以模块方式提供，使得不同类型的进程可以有针对性地选择调度算法。基础的调度器会按照优先级顺序遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，由它来选择下一个要执行的进程。CFS就是一个针对普通进程的调度类。
公平调度

CFS的出发点基于一个简单的理念：进程调度的效果应如同系统具备一个理想中的完美多任务处理器。我们可以给任何进程调度无限小的时间周期，所以在任何可测量范围内，可以给n个进程相同多的运行时间。

举个例子来区分Unix调度和CFS：有两个运行的优先级相同的进程，在Unix中可能是每个各执行5ms，执行期间完全占用处理器，但在“理想情况”下，应该是，能够在10ms内同时运行两个进程，每个占用处理器一半的能力。

CFS的做法：允许每个进程允许一段时间、循环轮转、选择运行最少的进程作为下一个运行进程，而不再采用分配给每个进程时间片的做法。CFS在所有可运行进程总数基础上计算出一个进程应该运行多久，而不是依靠nice值来计算时间片。

接下来我们考虑调度周期，理论上，调度周期越小，就越接近“完美调度”，但实际上这必然会带来严重的上下文切换消耗。在CFS中，为能够实现的最小调度周期设定了一个近似值目标，称为“目标延迟”，于此同时，为了避免不可接受的上下文切换消耗，为每个进程所能获得的时间片大小设置了一个底线——最小粒度（通常为1ms）。

在每个进程的平均运行时间大于最小粒度的情况下，CFS无疑是公平的，nice值用于计算一个进程在当前这个最小调度周期中所应获得的处理器时间占比，这样就算nice值不同，只要差值相同，总是能得到相同的时间片。我们假设一个最小调度周期为20ms，两个进程的nice值差值为5：
- 两进程的nice值分别为0和5，后者获得的时间片是前者的1/3，因此最终分别获得15ms和5ms
- 两进程的nice值分别为10和15，后者获得的时间片是前者的1/3，最终结果也是15ms和5ms

Linux调度的实现

分别分析四个组成部分：

时间记账

所有的调度器都必须对进程运行时间记录。

调度器实体结构

CFS使用调度器实体结构来追踪进程运行记账，这个结构体定义在<linux/sched.h>的struct_sched_entity中，具体代码如下：

struct sched_entity {
	/* 用于调度均衡的相关变量，主要与红黑树有关 */
	struct load_weight		load;	//权重，与优先级有关
	unsigned long			runnable_weight;	//在所有可运行进程中所占的权重
	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				nr_migrations;

	struct sched_statistics		statistics;

//设置了CONFIG_FAIR_GROUP_SCHED才启用的变量
#ifdef CONFIG_FAIR_GROUP_SCHED
	int				depth;
	struct sched_entity		*parent;
	/* rq on which this entity is (to be) queued: */
	struct cfs_rq			*cfs_rq;
	/* rq "owned" by this entity/group: */
	struct cfs_rq			*my_q;
#endif

#ifdef CONFIG_SMP
	/*
	 * Per entity load average tracking.
	 *
	 * Put into separate cache line so it does not
	 * collide with read-mostly values above.
	 */
	struct sched_avg		avg ____cacheline_aligned_in_smp;
#endif
};

虚拟实时vruntime

我们称vruntime为虚拟运行时间，该运行时间的计算是经过了所有可运行进程总数的标准化（加权）。以ns为单位，与定时器节拍无关。

可以认为这是CFS为了能够实现理想多任务处理而不得不虚拟的一个新的时钟，具体地讲，一个进程的vruntime会随着运行时间的增加而增加，但这个增加的速度由它所占的权重load来决定。

结果就是权重越高，增长越慢：所得到的调度时间也就越小 —— CFS用它来记录一个程序到底运行了多长时间以及还应该运行多久。

记账功能实现源码kernel/sched/fair.c：

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

	if (unlikely(!curr))
		return;

    //获得从最后一次修改负载后当前任务所占用的运行总时间
	delta_exec = now - curr->exec_start;
	if (unlikely((s64)delta_exec <= 0))
		return;

    //更新执行开始时间
	curr->exec_start = now;

	schedstat_set(curr->statistics.exec_max,
		      max(delta_exec, curr->statistics.exec_max));

	curr->sum_exec_runtime += delta_exec;
	schedstat_add(cfs_rq->exec_clock, delta_exec);

    //计算虚拟时间
	curr->vruntime += calc_delta_fair(delta_exec, curr);
	update_min_vruntime(cfs_rq);

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

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

	account_cfs_rq_runtime(cfs_rq, delta_exec);
}

该函数计算了当前进程的执行时间，并且将其存放在变量delta_exec中。然后使用clac_delta_fair函数计算虚拟运行时间，更新vruntime的值。

这个函数是由系统定时器周期性调用的（无论进程的状态是什么），因此vruntime可以准确地测量给定进程的运行时间，并以此为依据推断出下一个要运行的进程是什么。

进程选择

CFS需要选择下一个运行进程时，它会挑选一个具有最小vruntime的进程，这就是CFS算法的核心。

CFS使用红黑树来组织可运行进程队列。

红黑树是一种自平衡二叉树，它是一种以树节点方式储存数据的结构，每个节点对应了一个键值，利用这个键值可以快速索引树上的数据，并且它可以按照一定的规则自动调整每个节点的位置，使得通过键值检索到对应节点的速度和整个树节点的规模呈指数比关系。

挑选下一个任务

先假设一个红黑树储存了系统中所有的可运行进程，节点的键值就是它们的vruntime，CFS现在要找到下一个需要调度的进程，是所有进程中vruntime最小的那个，对应树中最左侧的叶子节点。

具体实现过程如下kernel/sched/fair.c：

static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
	struct sched_entity *left = __pick_first_entity(cfs_rq);
	struct sched_entity *se;

	/*
	 * If curr is set we have to see if its left of the leftmost entity
	 * still in the tree, provided there was anything in the tree at all.
	 */
	if (!left || (curr && entity_before(curr, left)))
		left = curr;

	se = left; /* ideally we run the leftmost entity */

	/*
	 * 下面过程针对一些特殊情况
	 * Avoid running the skip buddy, if running something else can
	 * be done without getting too unfair.
	 */
	if (cfs_rq->skip == se) {
		struct sched_entity *second;

		if (se == curr) {
			second = __pick_first_entity(cfs_rq);
		} else {
			second = __pick_next_entity(se);
			if (!second || (curr && entity_before(curr, second)))
				second = curr;
		}

		if (second && wakeup_preempt_entity(second, left) < 1)
			se = second;
	}

	/*
	 * Prefer last buddy, try to return the CPU to a preempted task.
	 */
	if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
		se = cfs_rq->last;

	/*
	 * Someone really wants this to run. If it's not unfair, run it.
	 */
	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
		se = cfs_rq->next;

	clear_buddies(cfs_rq, se);

	return se;
}

向树中加入进程

进程由阻塞态被唤醒或者fork产生新的进程时，需要执行插入新节点工作。enqueue_entity()函数实现了将进程加入红黑树以及缓存最左叶子节点的过程：

static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
	bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
	bool curr = cfs_rq->curr == se;

	/*
	 * 如果加入的进程是当前正在运行的进程，我们需要重新规范化vruntime
	 * 更新当前任务的统计数据
	 */
	if (renorm && curr)
		se->vruntime += cfs_rq->min_vruntime;

	update_curr(cfs_rq);

	/*
	 * Otherwise, renormalise after, such that we're placed at the current
	 * moment in time, instead of some random moment in the past. Being
	 * placed in the past could significantly boost this task to the
	 * fairness detriment of existing tasks.
	 */
	if (renorm && !curr)
		se->vruntime += cfs_rq->min_vruntime;

	/*
	 * 更新对应调度器实体的记录值
	 * When enqueuing a sched_entity, we must:
	 *   - Update loads to have both entity and cfs_rq synced with now.
	 *   - Add its load to cfs_rq->runnable_avg
	 *   - For group_entity, update its weight to reflect the new share of
	 *     its group cfs_rq
	 *   - Add its new weight to cfs_rq->load.weight
	 */
	update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
	update_cfs_group(se);
	enqueue_runnable_load_avg(cfs_rq, se);
	account_entity_enqueue(cfs_rq, se);

	if (flags & ENQUEUE_WAKEUP)
		place_entity(cfs_rq, se, 0);

	check_schedstat_required();
	update_stats_enqueue(cfs_rq, se, flags);
	check_spread(cfs_rq, se);
	if (!curr)
		__enqueue_entity(cfs_rq, se);	//插入过程
	se->on_rq = 1;

	if (cfs_rq->nr_running == 1) {
		list_add_leaf_cfs_rq(cfs_rq);
		check_enqueue_throttle(cfs_rq);
	}
}

上述函数用来更新运行时间和对应调度器实体的各种统计数据，然后调用__enqueue_entity()函数来执行插入红黑树的操作：

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
	struct rb_node *parent = NULL;
	struct sched_entity *entry;
	bool leftmost = true;

	/*
	 * 在红黑树中搜索合适位置
	 */
	while (*link) {
		parent = *link;
		entry = rb_entry(parent, struct sched_entity, run_node);
		/*
		 * 具有相同键值得结点放在一起
		 */
		if (entity_before(se, entry)) {
			link = &parent->rb_left;
		} else {
			link = &parent->rb_right;
			leftmost = false;
		}
	}

	rb_link_node(&se->run_node, parent, link);
	rb_insert_color_cached(&se->run_node,
			       &cfs_rq->tasks_timeline, leftmost);
}

while()循环遍历树寻找匹配键值，找到后对插入位置父节点执行rb_link_node()，最后更新红黑树的自平衡属性。

从树中删除进程

进程执行完毕或受到阻塞时需要删除：

static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
	/*
	 * 更新当前进程的统计数据
	 */
	update_curr(cfs_rq);

	/*
	 * When dequeuing a sched_entity, we must:
	 *   - Update loads to have both entity and cfs_rq synced with now.
	 *   - Substract its load from the cfs_rq->runnable_avg.
	 *   - Substract its previous weight from cfs_rq->load.weight.
	 *   - For group entity, update its weight to reflect the new share
	 *     of its group cfs_rq.
	 */
	update_load_avg(cfs_rq, se, UPDATE_TG);
	dequeue_runnable_load_avg(cfs_rq, se);

	update_stats_dequeue(cfs_rq, se, flags);

	clear_buddies(cfs_rq, se);

	if (se != cfs_rq->curr)
		__dequeue_entity(cfs_rq, se);
	se->on_rq = 0;
	account_entity_dequeue(cfs_rq, se);

	/*
	 * 重新规范化vruntime 
	 * Normalize after update_curr(); which will also have moved
	 * min_vruntime if @se is the one holding it back. But before doing
	 * update_min_vruntime() again, which will discount @se's position and
	 * can move min_vruntime forward still more.
	 */
	if (!(flags & DEQUEUE_SLEEP))
		se->vruntime -= cfs_rq->min_vruntime;

	/* return excess runtime on last dequeue */
	return_cfs_rq_runtime(cfs_rq);

	update_cfs_group(se);

	/*
	 * Now advance min_vruntime if @se was the entity holding it back,
	 * except when: DEQUEUE_SAVE && !DEQUEUE_MOVE, in this case we'll be
	 * put back on, and if we advance min_vruntime, we'll be placed back
	 * further than we started -- ie. we'll be penalized.
	 */
	if ((flags & (DEQUEUE_SAVE | DEQUEUE_MOVE)) == DEQUEUE_SAVE)
		update_min_vruntime(cfs_rq);
}

实际删除操作由__dequeue_entity()实现：

static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
}

调度器入口

进程调度的主要入口函数是schedule()，该函数会找到一个最高优先级的调度类，然后向其询问下一个要运行的进程是谁。

该函数中唯一重要的事情就是调用pick_next_task()函数，该函数以优先级为序，从高到低依次检查每一个调度类，从最高优先级的调度类中选择最高优先级的进程：

static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
	const struct sched_class *class;
	struct task_struct *p;

	/*
	 * 如果当前所有要调度的进程都是普通进程，那么就直接采用CFS
	 * Optimization: we know that if all tasks are in the fair class we can
	 * call that function directly, but only if the @prev task wasn't of a
	 * higher scheduling class, because otherwise those loose the
	 * opportunity to pull in more work from other CPUs.
	 */
	if (likely((prev->sched_class == &idle_sched_class ||
		    prev->sched_class == &fair_sched_class) &&
		   rq->nr_running == rq->cfs.h_nr_running)) {

		p = fair_sched_class.pick_next_task(rq, prev, rf);
		if (unlikely(p == RETRY_TASK))
			goto again;

		/* Assumes fair_sched_class->next == idle_sched_class */
		if (unlikely(!p))
			p = idle_sched_class.pick_next_task(rq, prev, rf);

		return p;
	}

//遍历调度类
again:
	for_each_class(class) {
		p = class->pick_next_task(rq, prev, rf);
		if (p) {
			if (unlikely(p == RETRY_TASK))
				goto again;
			return p;
		}
	}

	/* The idle class should always have a runnable task: */
	BUG();
}

睡眠和唤醒

睡眠：进程将自己标记为休眠状态，从可执行红黑树中移出，放入等待队列，然后调用schedule()选择和执行一个其他进程。

唤醒：进程被设置为可执行状态，然后从等待队列中移到可执行红黑树中。

等待队列

等待队列是由等待某些事件发生的进程组成的简单链表。可以通过DECLARE_WAITQUEUE()静态创建，也可以由init_waitqueue_head()动态创建。

内核使用wait_queue_head_t结构来表示一个等待队列，它其实就是一个链表的头节点，但是加入了一个自旋锁来保持一致性（等待队列在中断时可以被随时修改）

include/linux/wait.h：

struct wait_queue_head {
	spinlock_t		lock;
	struct list_head	head;
};
typedef struct wait_queue_head wait_queue_head_t;

通过执行下面几个步骤将自己加入一个等待队列：

调用宏DEFINE_WAIT()创建一个等待队列的项（链表的节点）
调用add_wait_queue()把自己加到队列中去。该队列会在进程等待的条件满足时唤醒它，当然唤醒的具体操作需要进程自己定义好（你可以理解为一个回调）
调用prepare_to_wait()方法把自己的状态变更为上面说到的两种休眠状态中的其中一种。

kernel/sched/wait.c:

void add_wait_queue(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
{
	unsigned long flags;

	wq_entry->flags &= ~WQ_FLAG_EXCLUSIVE;
	spin_lock_irqsave(&wq_head->lock, flags);
	__add_wait_queue(wq_head, wq_entry);
	spin_unlock_irqrestore(&wq_head->lock, flags);
}

//wait.h
static inline void __add_wait_queue(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
{
	list_add(&wq_entry->entry, &wq_head->head);
}

void
prepare_to_wait(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry, int state)
{
	unsigned long flags;

	wq_entry->flags &= ~WQ_FLAG_EXCLUSIVE;
	spin_lock_irqsave(&wq_head->lock, flags);
	if (list_empty(&wq_entry->entry))
		__add_wait_queue(wq_head, wq_entry);
	set_current_state(state);
	spin_unlock_irqrestore(&wq_head->lock, flags);
}

唤醒

唤醒操作主要通过wake_up()实现，它会唤醒指定等待队列上的所有进程。内部由try_to_wake_up()函数将对应的进程标记为TASK_RUNNING状态，接着调用enqueue_task()将进程加入红黑树中。

抢占和上下文切换

上下文切换

上下文切换是指从一个可执行进程切换到领一个可执行进程，由context_switch()实现。

上下文切换由schedule()函数在切换进程时调用。但是内核必须知道什么时候调用schedule()，如果只靠用户代码显式地调用，代码可能会永远地执行下去。

为此，内核为每个进程设置了一个need_resched标志来表明是否需要重新执行一次调度，当某个进程应该被抢占时，scheduler_tick()会设置这个标志，当一个优先级高的进程进入可执行状态的时候，try_to_wake_up()也会设置这个标志位，内核检查到此标志位就会调用schedule()重新进行调度。
用户抢占

简单来说有以下两种情况会发生用户抢占：
- 从系统调用返回用户空间
- 从中断处理程序返回用户空间
内核抢占

在Linux中，只要重新调度是安全的，内核就可以在任何时间抢占正在执行的任务，这个安全是指，只要没有持有锁，就可以进行抢占。

为了支持内核抢占，Linux做出了如下的变动：
- 为每个进程的thread_info引入了preempt_count计数器，用于记录持有锁的数量，当它为0的时候就意味着这个进程是可以被抢占的。
- 从中断返回内核空间的时候，会检查need_resched和preempt_count的值，如果need_resched被标记，并且preempt_count为0，就意味着有一个更需要调度的进程需要被调度，而且当前情况是安全的，可以进行抢占，那么此时调度程序就会被调用。
除了响应中断后返回，还有一种情况会发生内核抢占，那就是内核中的进程由于阻塞等原因显式地调用schedule()来进行显式地内核抢占：当然，这个进程显式地调用调度进程，就意味着它明白自己是可以安全地被抢占的，因此我们不用任何额外的逻辑去检查安全性问题。

下面罗列可能的内核抢占情况：
- 中断处理正在执行，且返回内核空间之前
- 内核代码再一次具有可抢占性时
- 内核中的任务显式地调用schedule()
- 内核中的任务被阻塞

实时调度策略

Linux提供了两种实时调度策略：SCHED_FIFO和SCHED_RR.

SCHED_FIFO

这是一种简单的先入先出的调度算法，一旦一个SCHED_FIFO级进程处于可执行状态，就会一直执行。直到它自己受阻塞或显式的释放处理器为止。
SCHED_RR

SCHED_RR与SCHED_FIFO大体相同，但SCHED_RR级进程在耗尽事先分配给他的时间后就不再继续执行，SCHED_RR是带有时间片的SCHED_FIFO。

总结

进程调度是内核的重要组成部分，Linux操作系统为了寻求调度周期和吞吐量的平衡以及满足各种负载的需求，使用的CFS调度能够尽量满足这些需求。

#Linux 操作系统