[校招面试]CPU调度系列一

进程调度：在可运行态进程之间分配有限处理器时间资源的内核子系统。通俗来说就是，各个进程之间如何有规律的使用CPU。当然实现起来也很复杂，也是操作系统的核心。

Linux的进程调度是基于分时技术(time-sharing)。允许多个进程“并发”运行就意味着CPU 的时间被粗略地分成“片”,给每个可运行进程分配一片。

当然,单处理器在任何给定的时刻只能运行一个进程。当一个并发执行的进程其时间片或时限(quantum)到期时还没有终止,进程切换就可以发生。分时依赖于定时中断,因此,对进程是透明的。为保证CPU 分时,不需要在程序中插入额外的代码。

在Linux 中,进程的优先级是动态的。调度程序跟踪进程做了些什么,并周期性地调整它们的优先级。在这种方式下,在较长的时间间隔内没有使用CPU的进程,通过动态地增加它们的优先级来提升它们。相应地,对于已经在CPU上运行了较长时间的进程,通过减少它们的优先级来处罚它们。每个进程在创建之初有一个基本的优先级,执行期间调度系统会动态调整它的优先级,交互性高的任务会获得一个高的动态优先级,而交互性低的任务获得一个低的动态优先级。

进程分类

传统上把进程分类为“I/O 受限(I/O-bound)”或“CPU受限(CPU-bound)”。前者频繁地使用I/O 设备,并花费很多时间等待I/O操作的完成;而后者是需要大量CPU 时间的数值计算应用程序。

另一种分类法把进程区分为三类: 交互式进程、 批处理进程、 实时进程。

交互式进程经常与用户交互,需要花很多时间等待键盘和鼠标操作。典型的交互式程序是命令shel、文本编辑程序、图形应用程序等。批处理程序不必与用户交互,经常在后台运行。因为这些进程不必被很快地相应,因此常受到调度程序的慢待。典型的批处理程序是编译程序、数据库搜索引擎、科学计算等。实时进程有很强的调度需要,他们不会被低优先级的进程阻塞,响应的时间很短。典型的实时程序有视频和音频应用程序、机器人控制程序、从物理传感器上收集数据的程序等。

这2种分类法在一定程度上互相独立。例如一个批处理程序可能是I/O受限型的(如数据库服务器),也可能是CPU受限型的(图像绘制程序)。Linux的调度算法可以明确的区分实时程序,但是没有办法区分交互式程序和批处理程序。Linux根据进程的过去行为,通过特定的算法区分交互式程序和批处理程序。因为交互式程序需要给用户一个良好的体验,所以Linux调度程序对交互式程序比较偏爱。

进程优先级

交互式程序和批处理程序都叫做 非实时进程(普通进程),每个非实时进程都有自己的静态优先级(nice值), 值越大优先级越低。nice值是所有Unix系统的标准化概念,在OS X系统中nice值代表分配给进程的时间片的绝对值, 而Linux中代表时间片的比例。通过 ps -el命令查看系统中的进程列表,结果中标记 NI的一列就是进程对应的nice值。

对于实时进程,实时优先级的范围是从1(最低优先级)~ 99(最高优先级)，含义与nice值相反。任何实时进程的优先级总高于非实时进程(普通进程)。

你可以通过 ps -eo stata,uid,pid,ppid,rtprio,time,com查看系统中的进程列表，在 RTPRIO列的就是实时优先级，如果显示 -，则该进程不是实时进程。

时间片

时间片是一个数值,它表明进程在被抢占前所能持续运行的时间。一般来说,调度策略必须规定一个默认的时间片,但是Linux的CFS调度器并没有直接分配时间片到进程,而是将处理器的使用比划分给了进程。这样一来,进程所获得的处理器时间其实是和系统负载密切相关的。nice值作为权重将调整使用比,值越大,使用比越小。Linux中CFS调度器的抢占时机取决于新进程所消耗的使用比。通过这种方式,CFS确保了进程调度中能有恒定的公平性,而将切换频率置于不断变动中。

不过,当可运行进程的数量区域无限时,每个进程获得使用比则趋于0,岂不是时间都花在切换进程上了?CFS为此引入了每个进程获得的时间片最小粒度,默认是1ms,也就是每个进程最少能获得1ms的运行时间。

调度类型

每个Linux进程都按照以下调度类型被调度:

SCHED_FIFO，先进先出的实时进程。如果没有优先级更高的可运行的实时进程,则当前运行的实时进程想运行多久便运行多久,即使还有其他优先级相同的可运行实时进程

SCHED_RR，时间片轮转的实时进程。保证对所有相同优先级的实时进程公平地分配CPU时间。

SCHED_NORMAL，普通的分时进程。

什么是调度器？

通常来说，操作系统是应用程序和可用资源之间的媒介。典型的资源有内存和物理设备。但是 CPU 也可以认为是一个资源，调度器可以临时分配一个任务在上面执行（单位是时间片）。调度器使得我们同时执行多个程序成为可能，因此可以与具有各种需求的用户共享 CPU。

调度器的一个重要目标是有效地分配 CPU 时间片，同时提供很好的用户体验。调度器还需要面对一些互相冲突的目标，例如既要为关键实时任务最小化响应时间，又要最大限度地提高 CPU 的总体利用率。下面我们来看一下 Linux 2.6 调度程序是如何实现这些目标的，并与以前的调度器进行比较。

Linux 调度器是一个颇有压力但很有趣的话题。一方面它涉及应用 Linux 的使用模型。尽管 Linux 最初开发为桌面操作系统环境，但现在在服务器、微型嵌入式设备、主机和超级计算机中都能发现它。 无疑，这些领域的调度负载有很大差异。另一方面，它要考虑平台方面的技术进步，包括架构（多处理、对称多线程、非一致内存访问 [NUMA] 和虚拟化）。 另外，这里还要考虑交互性（用户响应能力）和整体公平性之间的平衡。从这些方面很容易看出解决 Linux 中的调度问题有多难。

早期 Linux 调度器的问题

早期的 Linux 调度器使用了最低的设计，它显然不关注具有很多处理器的大型架构，更不用说是超线程了。1.2 Linux 调度器使用了环形队列用于可运行的任务管理，使用循环调度策略。 此调度器添加和删除进程效率很高（具有保护结构的锁）。简而言之，该调度器并不复杂但是简单快捷。

Linux 版本 2.2 引入了调度类的概念，允许针对实时任务、非抢占式任务、非实时任务的调度策略。 2.2 调度器还包括对称多处理 (SMP) 支持。

2.4 内核包含了相对简单的调度器，按 O(N) 的时间间隔运行（在调度事件期间它会迭代每个任务）。2.4 调度器将时间分割成 epoch，每个 epoch 中，每个任务允许执行到其时间切片用完。如果某个任务没有使用其所有的时间切片，那么 剩余时间切片的一半将被添加到新时间切片使其在下个 epoch 中可以执行更长时间。 调度器只是迭代任务，应用 goodness 函数（指标）决定下面执行哪个任务。尽管这种方法比较简单，但是却比较低效、缺乏可扩展性而且不适合用在实时系统中。它还缺少利用新硬件架构（比如多核处理器）的能力。

---

当下调度器概述

在 2.6 版本的内核之前，当很多任务都处于活动状态时，调度器有很明显的限制。这是由于调度器是使用一个复杂度为 O(n) 的算法实现的。在这种调度器中，调度任务所花费的时间是一个系统中任务个数的函数。换而言之，活动的任务越多，调度任务所花费的时间越长。在任务负载非常重时，处理器会因调度消耗掉大量的时间，用于任务本身的时间就非常少了。因此，这个算法缺乏可伸缩性。

O-notation 的重要性：

O-notation 可以告诉我们一个算法会占用多少时间。一个 O(n) 算法所需要的时间依赖于输入的多少（与 n 是线性关系），而 O(n^2) 则是输入数量的平方。O(1) 与输入无关，可以在固定的时间内完成操作。

在对称多处理系统（SMP）中，2.6 版本之前的调度器对所有的处理器都使用一个运行队列。这意味着一个任务可以在任何处理器上进行调度 —— 这对于负载均衡来说是好事，但是对于内存缓存来说却是个灾难。例如，假设一个任务正在 CPU-1 上执行，其数据在这个处理器的缓存中。如果这个任务被调度到 CPU-2 上执行，那么数据就需要先在 CPU-1 使其无效，并将其放到 CPU-2 的缓存中。

以前的调度器还使用了一个运行队列锁；因此在 SMP 系统中，选择一个任务执行就会阻碍其他处理器操作这个运行队列。结果是空闲处理器只能等待这个处理器释放出运行队列锁，这样会造成效率的降低。

最后，在早期的内核中，抢占是不可能的；这意味着如果有一个低优先级的任务在执行，高优先级的任务只能等待它完成。

Linux 2.6 调度器简介

2.6 版本的调度器是由 Ingo Molnar 设计并实现的。Ingo 从 1995 年开始就一直参与 Linux 内核的开发。他编写这个新调度器的动机是为唤醒、上下文切换和定时器中断开销建立一个完全 O(1) 的调度器。

为了解决 O(1) 调度器面临的问题以及应对其他外部压力， 需要改变某些东西。这种改变来自 Con Kolivas 的内核补丁，其中包括他的 Rotating Staircase Deadline Scheduler (RSDL)， 这包含了他在 staircase 调度器方面的早期工作。这些工作的成果就是一个设计简单的调度器，包含了公平性和界限内延迟。 Kolivas 的调度器吸引了很多人（并且很多人呼吁将其包含在目前的 2.6.21 主流内核中），很显然调度器的变革即将发生。 Ingo Molnar，O(1) 调度器的创造者，然后围绕 Kolivas 的一些思想开发了基于 CFS 的调度器。我们来剖析一下 CFS，从较高的层次上看看它是如何运行的。

题外话：触发对新调度器的需求的一个问题是 Java™ 虚拟机（JVM）的使用。Java 编程模型使用了很多执行线程，在 O(n) 调度器中这会产生很多调度负载。O(1) 调度器在这种高负载的情况下并不会受到太多影响，因此 JVM 可以有效地执行。

2.6 版本的调度器解决了以前调度器中发现的 3 个主要问题（O(n) 和 SMP 可伸缩性的问题），还解决了其他一些问题。现在我们将开始探索一下 2.6 版本的调度器的基本设计。

主要的调度结构

首先我们来回顾一下 2.6 版本的调度器结构。每个 CPU 都有一个运行队列，其中包含了 140 个优先级列表，它们是按照先进先出的顺序进行服务的。被调度执行的任务都会被添加到各自运行队列优先级列表的末尾。每个任务都有一个时间片，这取决于系统允许执行这个任务多长时间。运行队列的前 100 个优先级列表保留给实时任务使用，后 40 个用于用户任务，如下图

Linux 2.6 调度器的运行队列结构

给定处理器上可执行进程的链表，每个处理器一个。每个可执行进程都唯一归属于一个可执行队列。除了 CPU 的运行队列（称为活动运行队列（active runqueue））之外，还有一个过期运行队列。当活动运行队列中的一个任务用光自己的时间片之后，它就被移动到过期运行队列（expired runqueue） 中。在移动过程中，会对其时间片重新进行计算（因此会体现其优先级的作用；稍后会更详细地介绍）。如果活动运行队列中已经没有某个给定优先级的任务了，那么指向活动运行队列和过期运行队列的指针就会交换，这样就可以让过期优先级列表变成活动优先级的列表。

调度器的工作非常简单：它在优先级最高的队列中选择一个任务来执行。为了使这个过程的效率更高，内核使用了一个位图来定义给定优先级列表上何时存在任务。因此，在大部分体系架构上，会使用一条 find-first-bit-set 指令在 5 个 32 位的字（140 个优先级）中哪一位的优先级最高。查找一个任务来执行所需要的时间并不依赖于活动任务的个数，而是依赖于优先级的数量。这使得 2.6 版本的调度器成为一个复杂度为 O(1) 的过程，因为调度时间既是固定的，而且也不会受到活动任务个数的影响。

scan一下runqueue结构体的定义：

struct runqueue {

spinlock_t lock; /* 保护运行队列的自旋锁*/

unsigned long nr_running; /* 可运行任务数目*/

unsigned long nr_switches; /* 上下文切换数目*/

unsigned long expired_timestamp; /* 队列最后被换出时间*/

unsigned long nr_uninterruptible; /* 处于不可中断睡眠状态的任务数目*/

unsigned long long timestamp_last_tick; /* 最后一个调度程序的节拍*/

struct task_struct *curr; /* 当前运行任务*/

struct task_struct *idle; /* 该处理器的空任务*/

struct mm_struct *prev_mm; /* 最后运行任务的mm_struct结构体*/

struct prio_array *active; /* 活动优先级队列*/

atomic_t nr_iowait; /* 等待I/O操作的任务数目*/

…… };

通过下面三个宏操作运行队列里的数据

#define cpu_rq(cpu) //返回给定处理器可执行队列的指针

#define this_rq() //返回当前处理器的可执行队列

#define task_rq(p) //返回给定任务所在的队列指针

进程调度

 系统要选定下一个执行的进程通过调用schedule函数完成。

调度时机：

　　l  进程状态转换的时刻：进程终止、进程睡眠；

　　l  当前进程的时间片用完时（current->counter=0）；

　　l  设备驱动程序调用；

　　l  进程从中断、异常及系统调用返回到用户态时；

睡眠和唤醒：

       休眠（被阻塞）的进程处于一个特殊的不可执行状态。休眠有两种进程状态：

　　　　TASK_INTERRUPTIBLE：接收到信号就被唤醒

　　　　TASK_UNINTERRUPTIBLE：忽略信号

　　两种状态进程位于同一个等待队列上，等待某些事件，不能够运行。

进程休眠策略

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

1) 调用DECLARE_WAITQUEUE()创建一个等待队列的项。 

2) 调用add_wait_queue()把自己加入到队列中。该队列会在进程等待的条件满足时唤醒它。当然我们必须在其他地方撰写相关代码，在事件发生时，对等待队列执行wake_up()操作。 

3) 将进程的状态变更为 TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE。 

4) 如果状态被置为TASK_INTERRUPTIBLE,则信号唤醒进程。这就是所谓的伪唤醒（唤醒不是因为事件的发生），因此检查并处理信号。 

5) 检查条件是否为真；如果是的话，就没必要休眠了。如果条件不为真，调用schedule()。 

6) 当进程被唤醒的时候，它会再次检查条件是否为真。如果是，它就退出循环，如果不是，它再次调用schedule()并一直重复这步操作。 

7) 当条件满足后，进程将自己设置为TASK_RUNNING并调用remove_wait_queue()把自己移出等待队列。 

任务抢占和上下文切换

Linux 2.6 版本调度器的另外一个优点是它允许抢占。这意味着当高优先级的任务准备运行时低优先级的任务就不能执行了。调度器会抢占低优先级的进程，并将这个进程放回其优先级列表中，然后重新进行调度。

进程切换schedule函数调用context_switch()函数完成以下工作：

　　　　l  调用定义在中的switch_mm()，该函数负责把虚拟内存从上一个进程映射切换到新进程中。

　　　　l  调用定义在中的switch_to()，该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。

　　　　　　这包括保存、恢复栈信息和寄存器信息。在前面看到schedule函数调用有很多种情况，完全依靠用户来调用不能达到

　　　　　　很好的效果。内核需要判断什么时候调用schedule，内核提供了一个need_resched标志来表明是否需要重新执行一次调度：

　　　　l  当某个进程耗尽它的时间片时，scheduler_tick()就会设置这个标志；

　　　　l  当一个优先级高的进程进入可执行状态的时候，try_to_wake_up()也会设置这个标志。

　　每个进程都包含一个need_resched标志，这是因为访问进程描述符内的数值要比访问一个全局变量快

　　（因为current宏速度很快并且描述符通常都在高速缓存中）。

用户抢占

       内核即将返回用户空间时候，如果need_resched标志被设置，会导致schedule函数被调用，此时发生用户抢占。

 用户抢占在以下情况时产生：

　　　　l  从系统调返回用户空间。

　　　　l  从中断处理程序返回用户空间。

内核抢占

只要重新调度是安全的，那么内核就可以在任何时间抢占正在执行的任务。

什么时候重新调度才是安全的呢？只要没有持有锁，内核就可以进行抢占。锁是非抢占区域的标志。由于内核是支持SMP的，所以，如果没有持有锁，那么正在执行的代码就是可重新导入的，也就是可以抢占的。为了支持内核抢占所作的第一处变动就是为每个进程的thread_info引入了preempt_count计数器。该计数器初始值为0，每当使用锁的时候数值加1，释放锁的时候数值减1。当数值为0的时候，内核就可执行抢占。从中断返回内核空间的时候，内核会检查need_resched和preempt_count的值。如果need_resched被设置，并且preempt_count为0的话，这说明有一个更为重要的任务需要执行并且可以安全地抢占，此时，调度程序就会被调用。

内核抢占会发生在：

　　l  当从中断处理程序正在执行，且返回内核空间之前。

　　l  当内核代码再一次具有可抢占性的时候。

　　l  如果内核中的任务显式的调用schedule()。

　　l  如果内核中的任务阻塞（这同样也会导致调用schedule()）。

CFS调度和任务抢占的支持，是一个Linux内核划时代的一个发展，这个后续有机会再展开说说。

动态任务优先级

为了防止任务独占 CPU 从而会饿死其他需要访问 CPU 的任务，Linux 2.6 版本的调度器可以动态修改任务的优先级。这是通过惩罚 CPU 绑定的任务而奖励 I/O 绑定的任务实现的。I/O 绑定的任务通常使用 CPU 来设置 I/O，然后就睡眠等待 I/O 操作完成。这种行为为其他任务提供了 CPU 的访问能力。

用户响应能力更好：

与用户进行通信的任务都是交互型的，因此其响应能力应该比非交互式任务更好。由于与用户的通信（不管是向标准输出上发送数据，还是通过标准输入等待输入数据）都是 I/O 绑定型的，因此提高这些任务的优先级可以获得更好的交互式响应能力。

由于 I/O 绑定型的任务对于 CPU 访问来说是无私的，因此其优先级减少（奖励）最多 5 个优先级。CPU 绑定的任务会通过将其优先级增加最多 5 个优先级进行惩罚。

任务到底是 I/O 绑定的还是 CPU 绑定的，这是根据交互性 原则确定的。任务的交互性指标是根据任务执行所花费的时间与睡眠所花费的时间的对比程度进行计算的。注意，由于 I/O 任务先对 I/O 进行调度，然后再进行睡眠，因此 I/O 绑定的任务会在睡眠和等待 I/O 操作完成上面花费更多的时间。这会提高其交互性指标。

有一点值得注意，优先级的调整只会对用户任务进行，对于实时任务来说并不会对其优先级进行调整。

SMP 负载均衡

在 SMP 系统中创建任务时，这些任务都被放到一个给定的 CPU 运行队列中。通常来说，我们无法知道一个任务何时是短期存在的，何时需要长期运行。因此，最初任务到 CPU 的分配可能并不理想。

为了在 CPU 之间维护任务负载的均衡，任务可以重新进行分发：将任务从负载重的 CPU 上移动到负载轻的 CPU 上。Linux 2.6 版本的调度器使用负载均衡（load balancing） 提供了这种功能。每隔 200ms，处理器都会检查 CPU 的负载是否不均衡；如果不均衡，处理器就会在 CPU 之间进行一次任务均衡操作。

这个过程的一点负面影响是新 CPU 的缓存对于迁移过来的任务来说是冷的（需要将数据读入缓存中）。

记住 CPU 缓存是一个本地（片上）内存，提供了比系统内存更快的访问能力。如果一个任务是在某个 CPU 上执行的，与这个任务有关的数据都会被放到这个 CPU 的本地缓存中，这就称为热的。如果对于某个任务来说，CPU 的本地缓存中没有任何数据，那么这个缓存就称为冷的。

不幸的是，保持 CPU 繁忙会出现 CPU 缓存对于迁移过来的任务为冷的情况。

先留一张图，后面再续。不是我懒，最近有点忙

嗯，前言的废话就先到这里，下一篇继续看看CFS调度机制。