图解Linux进程调度（一）_进程调度动图

一、进程调度解决什么问题？

我们在使用电脑的时候，比如打开一个视频剪辑器，一个文本编辑器，可以认为它们都是一个进程。假如CPU是单核的，那么在同一时间只能运行一个进程，但是给我们的感觉是视频剪辑器和文本编辑器好像是同时运行的，也就是视频剪辑器在剪辑视频的时候，我们同时可以使用文本编辑器，这是怎么实现的呢？

其实这只是我们从宏观上感觉它们是并行运行的，而微观上它们是串行运行的。也就是说，可以认为这两个进程在做频繁的切换，比如视频剪辑器运行10ms，然后文本编辑器运行10ms，如此交替，这样子它们其实串行运行的，但由于我们的反应没那么快，所以觉得它们是并行运行的，如下图所示

一般操作系统的进程的进程数会非常的多，而一个CPU同一时间只能运行一个进程，这些进程可能是视频剪辑器，可能是文本编辑器等等。例如文本编辑器大多数时间在等待我们按下按键，并不需要占用太多CPU运行时间，而每当我们按下键盘上的按键的时候，它需要快速响应我们的操作并且将字符显示在屏幕。而视频剪辑器在剪辑视频的时候非常耗费CPU，但是它并不需要像文本编辑器那么频繁地与用户交互。也就是文本编辑器它可以占用更少地CPU运行时间，但是它需要快速响应用户操作，而视频编辑器它需要占用更多地CPU运行时间，但是它不需要快速响应用户操作，如下图所示

为了提高用户体验和系统性能，要解决的问题就是决定什么时候应该运行哪一个进程，该进程应该运行多久。也就是我们上面举的例子，每当我们操作文本编辑器的时候，要快速让文本编辑器处于运行状态，在我们没有操作文本编辑器的时候，应该尽量让视频剪辑器运行

这就是进程调度解决的问题，这也是衡量一个操作系统的优秀与否的一个重要指标

本篇文章讲解Linux如何管理进程，进程调度是怎么转起来的，为了实现进程调度维护了哪些数据结构，实现了哪些算法

至于一个进程如何实现抢占，进程调度的时机等细节将放到后面的文章讲解

二、进程调度整体框架：

在设计到内核具体的代码之前，我先来给你讲解一下进程调度的大体框架，让你明白进程调度是怎么转起来的，在你明白每一个部分的含义之后，再深入讲解内核的实现

操作系统管理非常多的进程，这些进程当前可能处于可运行状态或者睡眠状态。进程调度解决的是当前应该运行哪一个进程，它关心的对象是当前可运行状态的进程，内核为了管理这些可运行的进程，准备了一个运行队列，如下图所示

对于多CPU处理器，每一个CPU都有属于它的运行队列

我们将CPU当前正在运行的进程称为 current 进程，current 进程是不在运行队列中的，如下图所示：

接下来要解决的是，current进程什么时候应该被其它进程抢占，以及如何抢占？

进程切换一般分为两步：

• 第一步对current进程设置需要重新调度标志

• 第二步在系统调用返回或中断返回时等时机检查current进程是否设置了需要重新调度标志，如果需要，则调用schedule发生进程切换（具体的时机将在后面的文章详细讨论，这里暂且这么认为就行）

• 什么是系统调用返回和中断返回？如果你对这两个概念不了解也无大碍，我这里简单地讲解。你可以理解成，当CPU在运行某一个进程的时候，发生系统调用或者中断，会暂停进程的运行，然后去执行特定的处理程序，在执行完处理程序想要恢复进程运行的这个时候，就是系统调用返回或中断返回的时机；中断是由硬件触发的，系统调用是进程运行时触发的，可能有很多硬件频繁地产生中断，许多进程频繁地触发系统调用，所以对于操作系统来说，系统调用返回和中断返回这样的时机是随机又频繁地产生地，所以我们有很多个时机可以去检查current进程是否需要被切换

• 另外，你可以这样理解真正发生进程切换都是通过调用schedule函数完成的

首先我们来解决第一步，设置current进程需要重新调度的标志

我们通过什么机制来设置current进程需要重新调度的标志呢？

硬件电路中有一个硬件定时器，它负责周期性的产生时钟中断（一般为10ms），我们称它为滴答定时器，可以认为，它就是操作系统的心脏。每当产生定时器中断的时候，CPU就会执行中断处理程序：

在滴答定时器的中断处理中，我们会判断current进程是否需要被抢占，怎么判断？

很明显，这一部分需要具体的调度算法来实现，Linux将调度算法的实现抽象成调度类

在滴答定时器的中断处理中，通过调度类去实现相应的计算，然后判断current进程是否需要被抢占，如果需要被抢占，那么就在current进程设置需要重新调度的标志，如下图所示：

实时上，Linux内核的调度类不仅仅只有一个，因为内核同时实现了多种调度算法，但是我们这里强调总体框架，暂不讨论这里细节问题

到此，进程切换的第一步设置current进程需要重新调度标志部分已经讲解完

接下看第二步，进程真正的切换

实现进程真正的切换总是调用schedule函数，而schedule函数被调用的一般时机是系统调用返回或者是中断返回时。在系统调用返回或者是中断返回中，会检查current进程是否设置了需要重新调度标志，如果设置了，那么就调用schedule函数

系统调用返回或者是中断返回这样的时机对于操作系统整体来说，总是随机且频繁地产生，如下图所示：

如果current进程设置了需要重新调度标志，那么就会调用schedule函数。schedule函数会通过调度类，从运行队列中选取下一个要运行的进程，然后抢占current进程，成为新的current进程，如下图所示：

到这里，你应该明白了整个进程调度机制是怎么运行起来的，以及为了实现进程调度，实现了哪些数据结构，下面适当地总结一下

• 首先进程调度处理的对象是可运行的进程，所以准备了一个运行队列来管理当前可运行的进程，如果是多CPU处理器，那么每一个CPU都有它对应的一个运行队列

• CPU当前正在运行的进程成为current进程，进程调度解决的问题就是合理地切换current进程

• 进程发生切换需要两步，第一步在current进程设置需要重新调度的标志。第二步是在中断返回或系统调用返回时，检查是否current进程是否设置两类需要重新调度标志，如果设置了，那么就调用schedule函数来发生进程抢占（换言之，进程真正发生切换总是通过调用schedule函数发生的）

• 在硬件电路有一个滴答定时器，每隔10ms产生一次中断，CPU就处理一次中断。在滴答定时器中断处理中，通过调度类来检查current进程是否需要被切换，如果需要就设置需要重新调度的标志

• 对于整个操作系统来说，中断和系统调用总是随机且频繁地产生，在中断返回或者系统调用返回地时候，会检查current进程是设置了需要重新调度地标志。如果设置了，就会调用schedule函数发生进程抢占，切换current进程

• schedule函数通过调度类，从运行队列中获取下一个运行的进程，然后用它来抢占current进程，从而切换进程运行