Linux下进程的调度与切换

前言：

  在Linux操作系统中，进程的调度与切换是操作系统核心功能之一，它直接影响着系统的性能和响应速度。那么话不多说，开启我们今天的话题！

🚀进程切换

  CPU中存在众多寄存器，不同的寄存器有不同的功能，这些寄存器都在CPU中保存着，每一个都能装一定的数据。

  运行队列控制着PCB排队执行，每执行到一个进程的时候，内存里的eip指针会逐条追踪下一条指令。

  我们要知道，所有的保存都是为了恢复，保存在CPU寄存器里的数据，是当前进程时间片用完之前所执行的进度，而 所有的恢复，都是为了从上次的运行位置继续运行。

  并且，CPU内的所有临时数据，我们称之为进程的 硬件上下文！ 硬件上下文，由我们的 进程进行保存，得以保护上下文。

  当进程在进行第二次及第N次调度进程的时候，进程被放到CPU上开始运行，将曾经保存的硬件上下文进行恢复。

  所以进程切换最重要的就是 进程上下文的保存和恢复。

  我们可以看一下内核中的一些寄存器：

注意： CPU中的寄存器只有一套，而寄存器保存的数据可以有多套。虽然寄存器数据放在了共享的CPU设备内，但是 所有的数据都是被进程私有的！

🚀进程调度

✈️活动状态进程队列

  我们上次说过，Linux实现进程调度的算法，需要考虑 优先级，考虑进程饥饿，以及效率。那么CPU是如何实现进程调度的呢？

  我们来看一下Linux下CPU的运行队列的各项属性：

  我们首先看蓝色框内的内容，有一个叫做 queue[140] 的数组，这里的 queue数组表示活动状态进程的进程队列。

  其中在queue数组中，索引0~99号下标我们是不用的，这是因为0-99号下标对应的是 实时进程的优先级，实时进程是内核里更加重要的进程，放 在前100位由操作系统控制，避免系统抢占的情况。

  所以我们只剩下 100-139 这个范围可操控，其实这也就和我们优先级的可控范围大小相同，正好对应队列的四十个空位，而OS通过 某种映射关系，将可控优先级映射到数组 100-139的下标。

  我们看蓝色框内还有一项 bitmap数组，类型为int，这个数组用来干嘛呢？只能存储5个整形变量。

  数组的名字叫做bitmap已经很明显了，就是位图，5个整形元素有 32 * 5 = 160 个比特位，比特位的位置，表示哪一个队列。比特位的内容，表示该队列为不为空。

比如：0000 … 0000 ，如果最左侧0对应queue[100]的位置，那么如果该比特位为0表示在该下标映射的优先级下该队列为空，否则不为空。

  有人会问：为什么要用位图？不得不说，这是个愚蠢的问题，遍历整个队列的时间开销要远大于查找位图。

  所以，bitmap是用来检测队列中是否有进程，检测对应的比特位是否为1！

  而蓝色框内还有一个元素：nr_active，在Linux中，nr_active 是运行队列中用于表示活跃进程数量的计数器。nr_active 的值可以告诉内核有多少进程正在等待执行，从而帮助内核进行进程调度和资源分配。

✈️过期队列

  在红色框中的三项属性与蓝色框中的三项属性完全相同，也就是另外一个队列，被称为——过期队列。

  活跃队列表示当前CPU正在执行的运行队列，而 正在执行的运行队列（也就是活跃队列）是不可以增加新的进程的。

  所以操作系统设置了一个 和活跃队列相同属性的过期队列，当活跃队列正在执行时如果有进程需要添加进运行队列，那么就会添加至过期队列当中，也就是说 活跃队列的进程一直在减少，而过期队列中的进程一直在增多！

  当活跃队列的进程执行完毕后，就会和过期队列进行交换，它们交换的方式是通过两个结构体指针：

  就是 active 和 expired 结构体指针，它们分别指向活跃队列和过期队列，而活跃队列与过期队列由于属性完全相同，于是被放在了一个叫做 prio_arry_t[2] 的数组里，prio_arry_t[0]指向活跃队列，prio_arry_t[1]指向过期队列：

struct q{//q是我随意取的名字
	int nr_active;
	int bitmap[5];
	task_struct queue[140];
}

struct q *active;//活跃队列
struct q *expired;//过期队列

struct q *active = &prio_array_t[0];
struct q *expired = &prio_array_t[1];

  当活跃队列被CPU执行完毕后，我们 只需要交换两个指针的内容即可，这样仅仅是指向的内容变了，活跃队列变为过期队列，过期队列变活跃队列，并且时间复杂度为 O(1)：

swap(active, expried);//直接交换两个指针的内容

  新增进程在过期队列里插入，此时正在执行的是活跃队列，所以这个时候在过期队列里就有时间处理竞争饥饿的问题了。

  这样，我们竞争饥饿，优先级，以及进程效率都解决了。

📒✏️总结

•  进程切换最重要的部分就是 进程上下文的保护和恢复。
•  进程调度的优先级问题由 活跃进程数组的下标与进程优先级形成一种映射关系 解决。
•  进程调度的时间复杂度问题由 位图和两个结构体指针 解决，时间复杂度控制在了O(1)。
•  进程调度的进程饥饿问题由 活跃队列和过期队列 解决。