0. 前言

前边整理了一下Linux环境编程的接口，本阶段来对调度、内存、网络通信3部分进行深一层的学习。本文主要来学习进程的调度。
本文主要参考《Linux环境编程：从应用到内核》

主要目的：

1. 掌握调度的基本概念
2. 掌握完全公平调度(CFS)以及实时进程调度2种算法
3. 整理调度算法的过程，方便看源码

1. 概述

进程描述符

进程描述符存放了很多信息，不仅包含进程属性的字段，还包含一些指向其他数据结构的指针，示意性的描述如下：

进程的状态

最主要是在3态之间转换：运行、就绪、等待。

调度算法的要求

有n个任务，有m个CPU，调度算法就是把这n个任务分给m个CPU进行运算，它要求：

• 公平：每个进程都能得到调度的机会，不会出现饿死的现象
• 良好的调度延迟：尽量保证在一定时间内，总能得到调度的机会
• 差异化：重要的进程获得等多的执行时间
• 均衡：多个CPU要负载均衡，不能出现一些CPU很忙，另一些很闲。

由此看，调度算法就是带有点优先级的平均算法。

这里将进程做个简单的分类，根据等待的长短，可以分成：

• 交互型进程，进程会不断进入休眠，但对响应要求很高。
• 批量处理型进程，不需要与用户交互，通常在后台运行大量计算。
• 实时类进行，比交互型有更高的响应要求，优先级也就更高。

2. 调度入口

进程的调度的入口函数是schedule()，下边来看看调度做了哪些事情.

这一块代码有点像模板模式，将算法的流程写到__schedule中，而将具体的实现在pick_next_task中来实现，同时有2个hook函数：pre_schedule与post_schedule 。整个流程图如下：

这里的deactivate、put_prev_task、pick_next_task都有些多态的意味，根据不同的调度类实现不同。下边来看看pick_next_task函数如下:

static inline struct task_struct *
pick_next_task(struct rq *rq)
{
	const struct sched_class *class;
	struct task_struct *p;

    // 优化，若所有任务都属于公平类，直接调用公平类算法选择下一个task
	if (likely(rq->nr_running == rq->cfs.h_nr_running)) {
		p = fair_sched_class.pick_next_task(rq);
		if (likely(p))
			return p;
	}
	// 按照调度类的优先级，从高到低选择下一个进程，直到选中位置。
	for_each_class(class) {
		p = class->pick_next_task(rq);
		if (p)
			return p;
	}
	BUG(); /* the idle class will always have a runnable task */
}

Linux有4种调度类：

• stop_sched_class:停止类
• rt_sched_class:实时类
• fair_sched_class:完全公平调度类
• idle_sched_class:空闲类

它们的优先级次序为：

停止类与空闲类都只有一个任务，和应用层关系不大，下边分别来看看完全公平调度类与实时类。

在这里简单看一下调度类的接口：

struct sched_class {
	const struct sched_class *next;
	// 加入队列
	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
    // 移除调度队列
	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
	void (*yield_task) (struct rq *rq);
	bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);
	// 唤醒抢占
	void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
	// 选择下一个要执行的任务
	struct task_struct * (*pick_next_task) (struct rq *rq);
	void (*put_prev_task) (struct rq *rq, struct task_struct *p);

    ...

	void (*set_curr_task) (struct rq *rq);
    // tick处理
	void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
    // fork处理
	void (*task_fork) (struct task_struct *p);

	void (*switched_from) (struct rq *this_rq, struct task_struct *task);
	void (*switched_to) (struct rq *this_rq, struct task_struct *task);
	void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
			     int oldprio);

	unsigned int (*get_rr_interval) (struct rq *rq,
					 struct task_struct *task);

#ifdef CONFIG_FAIR_GROUP_SCHED
	void (*task_move_group) (struct task_struct *p, int on_rq);
#endif
};

这就是策略模式的抽象接口，c语言的写面向对象也没问题。

3. 完全公平调度类

简介

完全公平调度类像是一个福利社会，一个都不能落下。除非将Linux用在特定的领域，否则大部分时间里所有进程都属于完全公平调度类。

原理

完全公平调度类简单讲就是加权平均求时间片。一步一步来看看其原理。

• 时间片

  每个进程分配一段时间使用CPU，过了该时间段就等待下一次被调度。

• 调度延迟

  保证每一个可运行的进程都至少运行一次的时间间隔。它像是一个周期，在这个周期内每个进程都会被调用到。

  cat /proc/sys/kernel/sched_latency_ns可看该值。

• 调度最小粒度

  进程所拥有的最小的时间片长度。时间片过小会造成上下文频繁的切换，降低效率。

  cat /proc/sys/kernel/sched_min_granularity_ns可看该值。

• 调度周期

  有了调度延迟与最小的粒度对进程个数就了约束，调度延迟 / 最小粒度 就是能保证这2个条件的最大进程数。当进程数超过时，就只能满足其中一个了，也就是最小粒度。

  调度周期就是在这种情况下调度一次全部进程的周期。

  当进程数 <= 调度延迟 / 最小粒度，调度周期 = 调度延迟；

  当进程数 > 调度延迟 / 最小粒度，调度周期 = 进程数 * 最小粒度。

• 优先级与进程权重(weight)

  有些优先级比较高，理应获得更多的运行时间。这个优先级就是Nice，Nice值越大，优先级越低，取值在[-20, 19]之间。

  进程运行时间 = 调度周期 * 进程权重 / 所有进程权重之和

  而这个进程权重就是进程的优先级（Nice值）决定的了：weight = 1024 / (1.25 ^ nice)。

  这个weight是设计出来的，每降低一个nice值，多获得10%的时间。

  ps: 依次，最小粒度是不能保证的，最小粒度 = 平均运行时间

• 真实运行时间

  有了权重，就可以根据权重可以计算出该进程的在本次调度周期内所运行的时间片大小了。

  内核会周期性的检测进程是否已经消耗完自己的的时间片，如果本次运行时间已经超过了分配的时间片，则发生一次抢占。

• 虚拟运行时间

  有了权重，还可以将运行的真实时间加权成一个虚拟的运行时间。这样每个进程的运行时间的长短就可以进行统一的比较了。

  vruntime = 真实运行时间 * NICE_0_WEIGHT / 进程权重。也就NICE是真实值，以他为参考折算各自的vruntime。

  比如nice为0的进程运行了15毫秒，其权重为1024，其虚拟运行时间就 +15毫秒。nice为5的进程运行了5毫秒，其权重为335，其虚拟运行时间就 为5*(1024/335) 也约定于15毫秒。

• 选择下一个进程

  有了虚拟运行时间，内核会累加每次的虚拟时间，完全公平算法只需要挑选具有最小虚拟运行时间的进程投入运行即可。

核心实现

• sched_entity调度实体

  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			nr_migrations;
  	...
  };
  

• 虚拟运行时间的更新以及判断是否该抢占

  

  scheduler_tick()是被定时器周期调用，通过_update_curr()更新了vruntime，它又通过calc_delta_fair计算了加权的运行时间，其代码如下：

  static inline void
  __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
  	      unsigned long delta_exec)
  {
  	unsigned long delta_exec_weighted;
  
  	schedstat_set(curr->statistics.exec_max,
  		      max((u64)delta_exec, curr->statistics.exec_max));
  
  	// delta_exec是真实的间隔
  	curr->sum_exec_runtime += delta_exec;
  	schedstat_add(cfs_rq, exec_clock, delta_exec);
      // 根据真实的间隔加权计算
  	delta_exec_weighted = calc_delta_fair(delta_exec, curr);
  	// 累加到vruntime上
  	curr->vruntime += delta_exec_weighted;
  	update_min_vruntime(cfs_rq);
  
  #if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
  	cfs_rq->load_unacc_exec_time += delta_exec;
  #endif
  }
  

  通过check_preempt_tick判断本次运行是否到期，其代码如下:

  static void
  check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
  {
  	unsigned long ideal_runtime, delta_exec;
  	struct sched_entity *se;
  	s64 delta;
  
  	ideal_runtime = sched_slice(cfs_rq, curr);
  	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
  	if (delta_exec > ideal_runtime) {
  		resched_task(rq_of(cfs_rq)->curr);
  
  		clear_buddies(cfs_rq, curr);
  		return;
  	}
  

  这里通过sched_slice计算出本进程的时间片，然后判断运行的是否已经到期，如果是，则调用resched_task设置需要重新调度的标志。

• 选择下一个运行的task

  在上节中，看到schedule中调用了pick_next_task，其整个调用栈如下：

  

  最后调用的是_pick_first_entity()，是从红黑树上取task。内核为了加速挑选具有最小虚拟运行时间的进程，使用了红黑树，运行队列上所有的调度实体，都是红黑树的节点，调度实体的vruntime就是红黑树的键值。红黑树最左侧的节点，就是最小vruntime的节点。

其他调度

除了正常的调度，这里简单整理一下几种其他的调度形式：周期性调度任务、新进程的加入、睡眠进程醒来等

• 周期性调度任务

  

  周期性调度任务，在时钟到期后，也调度到scheduler_tick上，完成任务的调度。

• 新进程的加入

  

  新加入的进程一般是调用fork或者vfork系统调用，最后进入了do_fork，在do_fork中，进入了task_fork_fair。

  这个过程如下：

  static void task_fork_fair(struct task_struct *p)
  {
  	struct cfs_rq *cfs_rq = task_cfs_rq(current);
  	struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
  	int this_cpu = smp_processor_id();
  	struct rq *rq = this_rq();
  	unsigned long flags;
  
  	raw_spin_lock_irqsave(&rq->lock, flags);
  
  	update_rq_clock(rq);
  
  	if (unlikely(task_cpu(p) != this_cpu)) {
  		rcu_read_lock();
  		__set_task_cpu(p, this_cpu);
  		rcu_read_unlock();
  	}
  	// 更新CFS调度类的队列，包括执行_update_curr更新当前进程统计
  	update_curr(cfs_rq);
  
      // 新建进程vruntime设置成父进程的vruntime
  	if (curr)
  		se->vruntime = curr->vruntime;
      // 调整集创建进程的vruntime
  	place_entity(cfs_rq, se, 1);
  	// 如果设置了子进程先调度，则交换彼此的vruntime
  	if (sysctl_sched_child_runs_first && curr && entity_before(curr, se)) {
  		swap(curr->vruntime, se->vruntime);
  		resched_task(rq->curr);
  	}
  	// 此处减去当前队列最小虚拟运行时间，真正进入运行队列，即enqueue_entity时，进程vruntime会加上该值。
  	se->vruntime -= cfs_rq->min_vruntime;
  
  	raw_spin_unlock_irqrestore(&rq->lock, flags);
  }
  

• 睡眠进程醒来

  当内核调用wake_up系列宏时，会执行运行队列中指定的回调函数，通常是default_wake_function然后进入到try_to_wake_up()中，其的调用栈如下：

  

普通进程调度组

完全公平调度算法会尽力在进程之间保证公平，考虑一个极端情况，系统上有50个进程，其中49个属于用户A，而用户B只有1个进程，那么对于用户B而言，它只能使用2%的CPU资源，这显然是不同平的。

比较合理的做法，首先确保组间的公平，然后才是组内进程之间的公平。

Linux内核实现了cgroups(control groups)功能，该功能用来限制、记录喝隔离一个进程组群所使用的物理资源，包括：cpu、内存、磁盘IO、网络等。为了管理不同的资源，cgroups提供了一系列子系统，这里的cpu子系统只用于限制进程的cpu使用率。

ps：cgroups是docker的基石。

4. 实时调度类

简介

实时调度类是弱肉强食，强者生存的社会，高优先级有着绝对的权利。实时进程有硬实时与软实时，硬实时对响应时间要求非常严格，必须保证在一定的时间内完成，超过时间限制就会失败，且后果非常严重，如军用武器系统、航空航天系统等；软实时弱化一些，需要快速响应和在规定的时间内完成，但超过了时间的范围也不会有灾难的后果，如视频直播。

原理

Linux提供了2种实时调度策略：先进先出(SCHED_FIFO)策略和时间片轮转(SCHED_RR)策略。Linux为实时进程提供了99个实时优先级，从(0, 99]属于实时调度范围，从[100, 139]属于前边的完全公平调度范围。

每个CPU都有实时运行队列，根据99种离散的优先级可知，共有99个队列。具有相同优先级的实时进程都保存在一个队列之中。实时调度进程选择下一个运行的进程只需按照优先级从高到低的顺序，选择存在可运行进程的最高优先级队列中第一个进程即可。内核维护有位图来表征哪个优先级的运行队列有可运行的进程。

相关的结构体如下：

struct rt_prio_array {
	DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); 
	struct list_head queue[MAX_RT_PRIO];
};

分别来看看这2种策略。

• SCHED_FIFO策略

  FIFO先进先出，没有时间片的概念，只要没有更高优先级的进程就绪，使用该调度策略的进程就会一直执行，直到发生：

  1. 自动放弃CPU资源，如执行了一个阻塞的系统调用，或调用了sched_yield系统调用，进程不再处于可执行状态
  2. 进程终止
  3. 被更高优先级进程抢占

  如果主动染出CPU，则内核会将该进程放到对应队列的尾部；如果是高优先级抢占，该进程在队列中的位置不变。

• SCHED_RR策略

  时间片轮转策略中，高优先级也会直接抢占低优先级进程，但对于同优先级的进程，会轮流执行，进程每次使用CPU的时间为一个固定长度的的时间片。使用SCHE_RR策略的实时进程一旦被调度器选中，就会一致占有CPU资源，直到：

  1. 时间片耗尽
  2. 自动方案CPU资源
  3. 进程终止
  4. 被更高优先级进程抢占

  前2种情况，SCHED_RR策略的进程会被放到对应队列的尾部；如果是高优先级抢占，该进程在队列中的位置不变。

除此之外还有SCHED_BATCH策略SCHED_IDLE策略，但这些策略不属于实时调度类，这里不介绍了。

实现

对照完全公平调度类，来看看时钟周期的task_tick_rt以及选择下个task的pick_next_task_rt。

• 时钟周期更新

  

  这里的更新就没有vruntime虚拟运行时间的概念了，只是更新真实的运行时间sum_exec_runtime即可。sched_rt_runtime_exceeded()是与一个固定的时间进行对比，比较像SCHED_RR策略。

• 选择下一个task

  

  这段从bit图以及队列中获取下一个task的代码如下:

  static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
  						   struct rt_rq *rt_rq)
  {
  	struct rt_prio_array *array = &rt_rq->active;
  	struct sched_rt_entity *next = NULL;
  	struct list_head *queue;
  	int idx;
  
  	idx = sched_find_first_bit(array->bitmap);
  	BUG_ON(idx >= MAX_RT_PRIO);
  
  	queue = array->queue + idx;
  	next = list_entry(queue->next, struct sched_rt_entity, run_list);
  
  	return next;
  }
  

  这个位图其实就是long类型的数组，sched_find_first_bit如下:

  static inline int sched_find_first_bit(const unsigned long *b)
  {
  #if BITS_PER_LONG == 64
  	if (b[0])
  		return __ffs(b[0]);
  	return __ffs(b[1]) + 64;
  #elif BITS_PER_LONG == 32
  	if (b[0])
  		return __ffs(b[0]);
  	if (b[1])
  		return __ffs(b[1]) + 32;
  	if (b[2])
  		return __ffs(b[2]) + 64;
  	return __ffs(b[3]) + 96;
  #else
  #error BITS_PER_LONG not defined
  #endif
  }
  

  这里其实是调用了__ffs来获取的long类型中第一个bit出现的index

  static inline unsigned long __ffs(unsigned long word)
  {
  	asm("bsf %1,%0"
  		: "=r" (word)
  		: "rm" (word));
  	return word;
  }
  

  这块的实现是一个汇编代码，bsf是正向位扫描指令bsf dest, src,从源操作数的的最低位向高位搜索，将遇到的第一个“1”所在的位序号存入目标寄存器中，影响标志为ZF。若所有位都是0，则ZF=1，否则ZF=0。与其相对的是bsr，从高位往地位扫描，示例：

  AX=0098H=0000000010011000B
  BSF BX,AX;
  ZF=0,BX=3h
  BSR DX,AX;
  ZF=0,DX=7H
  

5. 总结

本文主要是整理了一下Linux的进程调度，重点是完全公平调度算法，其本质上是加权平均，包括真实时间片的计算，以及vruntime的概念。