前言：

了解了进程的状态和进程的优先级，我们现在来看进程是如何被CPU调度执行的。

在单CPU的系统在，程序是并发执行的；也就是说在一段时间呢，进程是轮番执行的；

这也是说一个进程在运行时不会一直占用CPU直到运行结束，而是运行一段时间(时间片)然后切换下一个进程运行；

所以，对于一个死循环的进程执行的时候，我们是可以进行其他操作的，它并没有一直占有CPU。

那这就要涉及到一个问题，那就是进程切换

对于一个进程，如果它在一个时间片内运行结束，那没有什么问题；但是如果一个时间片内没有运行结束呢？

那该进程被切换，然后等待再次被调度；

这里就有一个疑问：那再次调度进程时，如何知道上次运行到哪里呢？

寄存器

在叙述上面问题之前，先来了解一下寄存器

• 寄存器是CPU内部的临时空间
• 寄存器 != 寄存器中的数据

什么意思呢？

我们应该进程在运行的时候，它是会产生临时数据的，但是这些临时输出存放到哪里呢，就存放在CPU中的寄存器当中；

而寄存器又分为很多种，这里就不详细描述了；

这里简单理解：寄存器就是CPU内部的临时空间。

进程切换

思考一个问题：进程的时间片到了，被切换出CPU，在下次运行时，CPU是如何知道进程上次运行到哪里了，以及运行时产生的临时数据？

这里举个例子：(比较牵强，简单理解)

博主最近喜欢看一本小说，但是这本小说特别特别长，我今天看了200页，要休息了；但是博主又担心明天看时，忘记看到了哪一页，所以博主在博主搞了一个书签，记录下当前页数（第几页、第几行）。

但是第二天睡醒，博主大脑空空的，再打开这本书时，书签只记录了第几行第几页了，博主不知道这本小说里面都有什么人物了，没办法博主只能再从又开始看，了解小说人物；博主第二天看到了300页，要休息了，博主学精了，这次我不仅记录了当前第几页第几行，还记录了小说情节中出现的任务，还用其他细节的内容。

这样第三天博主再打开这本小说，虽然不记得第几页第几行，人物和小说细节，但是博主打开书签，上面记录了上次看完时小说的信息；这时就可以接着上次继续阅读了。

我们CPU也是如此，当一个进程被切换出CPU，下次被调度时，CPU是完全不记得上次进程运行到了哪里，有哪些临时变量等这些信息的；

那怎么办呢？

很简单，在我们一个进程被切换出CPU时，只需要记录一下上下文内容，和临时变量等这一系列信息即可；

这里又存在问题了：这些信息存放在哪里呢？

很显然，不会存放在CPU中；那就只能存在于进程的task_struct中。

在Linux中，这些信息存放到了task_struct中的成员Tss中。

这样，当我们进程再次被调度时，直接将Tss中记录的上下文信息加载到CPU中的寄存器上，CPU就可以继续上次运行的位置继续去运行。

此外，为了区分首次被调度和已经被调度过的进程，task_struct中还存在一个整型变量来区分。

进程调度

简单了解了进程是如何切换的，我们现在再来看进程是如何被调度的？

在了解进程状态时，提及到一个CPU一个运行队列，那进程不是按照队列顺序被调度的吗？

很显然不是，如果真的是如此，那进程优先级就没有存在的意义了。

我们现在来看，linux中运行队列的整体结构：

一眼望去，眼花缭乱的，为何如此复杂？

我们这里先注意看上图中的红色区域和蓝色区域内的内容；

运行队列的实现思路

我们先来看，红色区域和蓝色区域内都存在三个成员：

• nr_active
• bitmap[5]
• queue[140]

queue

我们首先来看queue，它是一个数组一个140个元素；这里面存储的类型是struct task_struct*，可以理解为一个task_struct链表

它可以分为两部分：

• [0 , 99]：这一部分表示的是实时优先级（暂时不探讨）；
• [100 , 139]：这一部分，每一个位置都对应一个优先级。

[100 , 139]，一共40个位置，而我们优先级正好也是40个，所以这四十个位置和我们40个优先级一一对应。

这样每一个位置存放的都是优先级相同的进程的task_struct队列；

这样对于一个进程，我们只需要根据它的优先级就可以直接找到它对应的队列。（当然这里需要一个映射关系：对应位置 = (x - 60) + (140 - 100);)

那这样，我们的queue本质上不就是一个hash表吗（这个表中每一个位置存储的是对应优先级的task_struct队列）

bitmap[5]

在上述中，queue本质上上一个hash表，我们可以通过进程的优先级快速的找到其对应的队列；

但是，我们CPU要挑选一个进程运行，那还是要遍历一遍整个queue表啊；效率也不是很高啊

为了提高效率，这里存在一个bitmap[5]位图；

• 它的类型是：unsigned int bitmap[5]

• 我们知道一个字节等于8个bit位，一个整形4个字节；那一个整形用二进制表示就存在32位(32个0/1)。

• 这里有5给个整形，也就是160个二进制数；而queue中一共存在140个位置，我们是不是可以用一个bit对应queue中的一个task_struct队列；

• 所以这里bitmap[5]中每一个bit位如果为1就表示其对应位置的队列中存在task_struct；为0表示其对应位置不存在task_struct。

所以，有了bitmap[5]，CPU在选择进程运行时，就不需要再遍历queue表，而是在bitmap中找到bit位为1的位置，然后直接去其queue对应位置去寻找进程的task_struct即可。

这里检测的过程，简单来说急速对bitmap[5]中的5个元素通过int的方式进行位操作，(例如，bitmap[0] & xFFFFFFF == 0就表示bitmap[0]的二进制的每一位都等于0，就表示第一个整型位对应位置队列中是不存在task_struct的；一次类推）；这样相比于去遍历queue表，效率快了非常对，已经接近O(1)了。

nr_avtive

这个就简单多了，它指的就是当前CPU队列中所有可运行队列的数量。

进程饥饿

进程饥饿（Process Starvation） 是指某个进程因长期无法获得所需的系统资源（如CPU时间、I/O资源等）而无法执行的现象。

简单来说就是应该进程它一直在等待被调度，但是一直没有被调度；

我们知道一个进程它运行时间片结束后，被切换出CPU，它是要重新回到等待队列，等待下一次被调度的；

在我们上述的理解中，应该优先级为60的进程，它是一个死循环，时间片到了，被切换出CPU之后，它又回到了优先级是60的队列中；那CPU在下一次调度时，还是有限调度优先级高的进程；此时还存在一个优先级为90的队列，那此时CPU就会一直调用优先级为60的进程，直到该进程执行结束，才会去调度优先级为90队列中的进程；

那如果这样去设计的话，非常容易就造成了进程饥饿的问题；

Linux中是如何去解决的呢？

Linux中，它不仅存在一个queue，在内核中，将queue、bitmap、nr_avtive包装成rqueue_elem；然后定义struct rqueue_elem[2]；

这样一个struct rqueue_elem表示活动队列，另外一个struct rqueue_elem表示过期队列；

在Linux内核中还存在两个指针，一个是active指向当前的活动队列，另一个expired指向当前的过期队列。（初始情况下：struct rqueue_elem[0]是活动队列，struct rqueue_elem[1]是过期队列；active指向rqueue_elem[0]，expired指向rqueue_elem[1]）

这样CPU只在active指向的活动队列中选取进程调度，进程被调度结束后，放入到expired指向的过期队列中。

这样，active执行的活动队列中进程被调度完时，CPU就要去调度expired指向的队列。

交换一下active和expired的值，active就指向了新的活动队列；expired就指向了新的过期队列。

到这里，本篇文章大致内容就结束了，感谢各位支持

简单总结：

• 进程切换：进程是如何切换的，切换时上下文信息存储到哪里
• 进程调度：linux中的调度算符：O(1)调度算法实现的思路。