Linux内核学习——进程调度

发表于

进程调度

调度程序负责对哪个进程投入运行，运行多久做出决策。通过有效地调度程序，最大化地利用系统资源，即利用处理器的时间。

多任务

多任务操作系统可以同时地并行交互执行多个进程。多任务系统分为两种：抢占式和非抢占式，linux提供了抢占式的多任务模式。

Linux的调度策略

在2.6内核之后，Linux引入了著名RSDL和CFS作为新的进程调度算法。

策略

IO消耗型和处理器消耗型的进程

进程可以分为IO消耗型和处理器消耗型。前者需要更多的IO资源，比如多数的图形交互程序；后者则把时间花在了执行代码上。linux系统为了保证交互式应用和桌面的性能，更倾向于有限调度IO消耗型的进程。

进程优先级

优先级高的进程先获得处理器时间，低的后运行，相同的优先级按照轮转的方式进行调度。

linux采用了两种不同的优先级范围：

  • nice值，[-20-19]，默认值为0，高nice值则优先级低，低nice值则属于高优先级，可以通过命令ps -el查看进程列表；
  • 实时优先级，[0-99]，与nice值意义相反，99代表最高优先级。另外任何的实时进程的优先级都高于普通进程；

时间片

IO消耗型不需要长的时间片，避免影响交互。处理器型的则希望时间片越长越好。Linux系统的CFS调度器将对处理器的使用比例划分给进程，使得进程获得的时间片长度与系统负载相关。

另外，Linux的CFS调度器抢占处理器的要求是：新进程消耗的使用比比当前进程小，则新进程立刻投入运行。否则，将推迟进行。

Linux调度算法

调度器类

Linux的调度器是以模块化的方式提供，这样不同类型的进程就可以采用不同的调度算法。

例如CFS就是一个针对普通进程的调度类。

公平调度

CFS在调度时，针对每一个进程分配它们1/n的处理器时间——n就是可运行进程的数量。在这种情况下，当可执行任务数量趋于无限时，各自获得的处理器使用时间就会趋近于0，这种情况下会带来高昂的切换消耗。因此CFS为每个进程获得时间片设置一个最小粒度，默认为1ms。

另外，按照CFS的调度策略，任何nice值对应的绝对时间不再是一个绝对值，而是处理器的使用比。

Linux调度的实现

CFS的具体实现代码位于文件kernel/sched_fair.c中。

时间记账

CFS虽然没有时间片的概念，但不变的是它也必须维护每个进程运行的时间记账，确保进程只在公平分配给它的处理器时间内运行。CFS使用了一个结构体struct sched_entity进行追踪。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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;


#ifdef CONFIG_SCHEDSTATS
	struct sched_statistics statistics;
#endif


#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
};

而task_struct 包含关于 sched_entity 和 sched_class 这两种结构的信息：

1
2
3
4
5
6
7
8
struct task_struct { /* Defined in 2.6.23:/usr/include/linux/sched.h */
	....
	struct prio_array *array;
	struct sched_entity se;
	struct sched_class *sched_class;
	....
	....
};
  • 虚拟实时

观测上面的结构体，可以看到一个成员vruntime，该变量用来存放进程的虚拟运行时间。

简单来说，CFS通过每个进程的虚拟时间来衡量哪个进程最值得被调用，而这个时间是通过进程的实际运行时间和进程的权重计算出来的。该变量记录了一个程序到底运行了多久以及它还要运行多久。

一个进程的权重越大，表示这进程越需要被运行，因此它的虚拟运行时间越小。

所有的虚拟时间的计算都在update_curr进行：

  • 首先计算进程当前时间与上次启动时间的差值；
  • 通过符合权重与当前时间模拟出进程的虚拟允许时钟；
  • 重新设置cfs的min_vruntime；

进程选择

刚刚已经提到，CFS的核心是在选择下一个运行进程时，选择vruntime值最小的进程。而在linux中，是通过红黑树来组织这些进程队列的。

  • 挑选下一个进程

红黑树存储了所有可运行的进行，而节点的键值就是可运行进程vruntime。那么对应的所有进程中vruntime最小的就是树中最左侧的树叶子节点。

事实上，挑选结点的时候并不是遍历整棵树，而是利用缓存在rb_leftmost字段的值。

  • 向树中加入进程

发生在进程变为可运行状态或者通过fork()第一次创建的时候

  • 从树中删除进程

发生在进程堵塞或者终止时

调度器入口

调度器的入口是在文件kernel/sched.c中的schedule()，该函数先找到一个最高优先级的调度类，然后询问该调度类下一个该运行的进程是什么。

睡眠和唤醒

在等待诸如文件IO或者键盘输入的事件时，进程可能进入休眠状态，变得不可执行——TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE。前者如果接收到一个信号，会被唤醒并响应信号。

等待队列

等待某些事件发生的进程会组成一个简单的链表，这就是等待队列。

  • 调用宏DEFING_WAIT()创建一个等待队列的项；
  • 通过add_wait_queue()将该项加入等待队列；
  • 调用prepare_to_wait()变更进程状态；
  • 如果状态被设置为TASK_INTERRUPTIBLE时，进程可以被信号唤醒；
  • 当进程被唤醒的时候，它会检查条件是否为真，真则退出循环；否则，不断调用schedule()重复该步骤；
  • 进程被唤醒后，进程修改状态，并将自己移除等待队列；

唤醒

唤醒操作通过wait_up()实现，它会唤醒指定队列上的所有进程。为了避免虚假唤醒，所以有时需要一个循环处理保证它等待的条件真正达成。

抢占和上下文切换

上下文切换，把一个可执行进程切换到另一个可执行进程，具体实现在kernel/sched.c的context_switch()。所以新的进程被投入使用时，schedule()就会调用该函数；

  • 负责切换虚拟内存到新的进程中；
  • 负责切换上一个进程的处理器状态到新进程中，包括栈信息和寄存器信息；

在这种情况下，内核需要知道什么时候可以调用schedule()，这是为了避免客户程序调用该函数，导致永远执行。所以我们需要一个need_resched的标识来识别是否需要重新执行一次调度。

每个程序都包含一个need_resched，这样可以更快地访问这个标识（在thread_info）中。

用户抢占

用户抢占发生在：

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

内核抢占

内核抢占需要保证重新调度是安全的。linux的解决方法是，如果没有锁，就可以进行抢占，至于锁的使用，就是为每个进程的thread_info假如preempt_count计数器。当计数器为0时，内核就可以抢占。

内核的抢占发生在：

  • 中断处理程序返回内核空间之前；
  • 内核代码再一次具有可抢占性的时候；
  • 显示调用schedule()或者任务阻塞；

实时调度策略

linux提供了两种实时调度策略：SCHED_FIFO和SCHED_RR。这两种策略在学操作系统的时候应该讲过，就不赘述了。

一个是先进先出，一个是round robin