[Linux] Linux 的进程如何调度——Linux的 O(1)进程调度算法
标题：[Linux] Linux 的进程如何调度——优先级与进程调度
个人主页@水墨不写bug
目录
一、前言
二、将要出现的概念
1.进程调度队列
2.位图
3.进程的优先级
三、Linux进程的调度过程
1.活动队列（*active指向的队列）
2.过期队列（*expired指向的队列）
3.active指针和expired指针
4.总结
正文开始：
一、前言
当你看过书上的讲解，它通常会将操作系统对进程的调度一笔带过：
一个一个的进程会被存储在队列中（称为运行队列），CPU通过运行队列来调度进程。
这样的讲解通常让人捉摸不透，Linux操作系统具体是怎么调用进程的？又是怎么一个调用法？能不能用直观的图来表示这样的调度过程？这就是本文着重讲解的内容。
二、将要出现的概念
1.进程调度队列
Linux中，每个CPU都对应有一个运行队列；CPU与运行队列是一对一的关系。CPU想要调度进程，就需要到runqueue这个数据结构中去得到进程的PCB：task_struct。
在这里，我们形象的表示出runqueue：
在runqueue中，由于不考虑其他的信息，只考虑进程调度相关的变量，我们仅仅在上面的图形中表示出了进程调度的关键信息。首先我们会发现，红色和蓝色分别是两组相同的结构，这与调度的逻辑密切相关。
这两组相同的结构，一组表示正在被调度的进程队列，另一组是未被调度的进程队列。这里的队列（queue）要与运行队列（runqueue）区分，这里的队列的实际类型是：
struct task_struct *queue[140];运行队列是一个CPU调度对应的一个数据结构，但是这里的队列只是运行队列中的一个组织进程的数据结构。
2.位图
在C++中，位图（bitmap）通常指的是一种用于表示和操作位（bit）的数据结构。位图可以被看作是一个由连续的位（0或1）组成的序列，其中每一个位都可以表示某个状态或属性的值。
在C++中，可以使用位操作（bit manipulation）来对位图进行操作，例如设置某个位的值、获取某个位的值、将多个位进行逻辑运算等。常见的位操作操作符包括位与（&）、位或（|）、位异或（^）、位取反（~）等。
使用位图可以实现一些高效的算法和数据结构，例如位图可以被用来表示一个大范围的二进制数，节省内存空间。位图也可用于表示布尔值数组、位向量（bit vector）、位集合（bit set）等数据结构。
在我们上述的两个相同的结构中，都有一个位图bitmap[5]：
int bitmap[5];int具有32位，可以表示32个状态值，5个int则可以表示160个状态值，正好可以覆盖140个大小的PCB数组。用位图表示PCB数组的这个位置上是否有进程。实际上PCB数组内存储的是一个task_struct*的链表，在具体调用时，如果这个位置上有链表，则取出头节点，加载到CPU中调度。
我们首先需要知道，Linux操作系统想要正常为用户服务，就需要不断的调度用户的进程，所以调度进程是一个每时每刻都在发生的事。想要调度进程，Linux就需要在进程队列中查找进程。运行队列是一个指针数组，每一个位置只可能有两种状态：
1）存储有有效的进程地址；
2）空指针；
这就需要一个非常高效的确认进程队列中每一个位置是否有进程的查找方法——这也就是在这里位图的用武之地：
我们可以通过访问表示位图数组的每一个元素，每一个元素是整形，表示32个位置是否有指针存在：这样我们就可以通过一次判断，就可以知道32个位置是否有进程了！！！
3.进程的优先级
在Linux操作系统中，优先级是相对于拥有时间片的进程而言的。进程分为实时进程和分时进程，分时进程才有时间片的概念，并会被根据优先级依次被操作系统调度。
上述的140个数组位置而言：
普通优先级： 100～ 139（我们创建的进程一般普通的优先级，想想nice值的取值范围，可与之对应！）
实时优先级： 0～ 99（在这里我们不关心）
除此之外，如果你优先级不太了解， 可参考 （《进程的优先级》）。
我们在之前的讲解中，我们明白了这样的一个事实：CPU是稀缺资源，相对于CPU的数目来说，进程的数目是更多的，进程的调度需要CPU，于是进程需要竞争CPU资源，这也就需要指定进程优先级。
进程的优先级与操作系统的尽量让每个进程调度的总时间是相同的原则是不冲突的，在本文的第三部分会有详尽的演示。
三、Linux进程的调度过程
1.活动队列（*active指向的队列）
时间片还没有结束的所有进程都按照优先级放在该队列；
nr_active: 表示总共有多少个运行状态的进程；
queue[140]: 一个元素就是一个进程队列，相同优先级的进程按照FIFO规则进行排队调度,所以，数组下标就是优先级！
从该结构中，选择一个最合适的进程，过程是怎么的呢？
1. 从0下表开始遍历queue[140]
2. 找到第一个非空队列，该队列必定为优先级最高的队列
3. 拿到选中队列的第一个进程，开始运行，调度完成！
4. 遍历queue[140]时间复杂度是常数！但还是太低效了！
bitmap[5]:一共140个优先级，一共140个进程队列，为了提高查找非空队列的效率，就可以用5*32个比特位表示队列是否为空，这样，便可以大大提高查找效率
2.过期队列（*expired指向的队列）
过期队列和活动队列结构一模一样；
过期队列上放置的进程，都是时间片耗尽的进程；
当活动队列上的进程都被处理完毕之后，对过期队列的进程进行时间片重新计算；
3.active指针和expired指针
active指针永远指向活动队列
expired指针永远指向过期队列
可是活动队列上的进程会越来越少，过期队列上的进程会越来越多，因为进程时间片到期时一直都存在的。
为了解决这个问题，操作系统会在合适的时候交换两个指针的内容，这样就完成了操作系统对进程的调度的可持续进行。
由于查找进程的顺序是从小下标到大下标查找的，这也就导致了优先级数值比较小的进程会优先被调用，但是终究是要在这个进程队列调度完成之后才能进行下一轮进程进程调度，这就很好的体现了优先级的意义：优先级高，体现在每个调度周期中先调度这个优先级高的进程。
4.总结
在系统当中查找一个最合适调度的进程的时间复杂度是一个常数，不随着进程增多而导致时间成本增加，我们称之为进程调度O(1)算法。
完~
未经作者同意禁止转载