Linux2.6内核进程调度队列

运行队列runqueue

活跃队列&过期队列

queue[140]&优先级&队列数组下标

bitmap[5]&O(1)调度算法

nr_active

active指针和expired指针

O(1)调度算法之调度过程

本篇是Linux进程概念篇的最后一篇，Linux2.6内核是一个具体的/可行的/实际的存在的一个调度方案。下篇我们将进入进程控制篇。

运行队列runqueue

下图是Linux2.6内核中进程队列的数据结构，之间关系已经给大家画出来，方便大家理解。

一个CPU拥有一个runqueue （struct runqueue）
runqueue是CPU的PCB（task_strutc)
如果有多个CPU就要考虑进程个数的负载均衡问题
我们现在谈论的OS都是分时操作系统，调度时强调的是公平！
关于实时操作系统，暂且不谈，调度时强调的时实时性！智能自动驾驶骑车等。

活跃队列&过期队列

CPU调度时，需要把进程拿走的同时，把正在执行的进程剥离下来（被放入运行队列）
运行队列中存在两套相同的结构体类型。
拿走的队列：活跃队列。放入队列：过期队列。
活跃队列表示当前CPU正在执行的运行队列，而正在执行的运行队列（也就是活跃队列）是不可以增加新的进程的 。
与此同时，操作系统设置了一个 和活跃队列相同属性的过期队列，当活跃队列正在执行时如果有进程需要添加进运行队列，那么就会添加至过期队列当中，也就是说活跃队列的进程一直在减少，而过期队列中的进程一直在增多！
活跃队列是只出不进
过期队列是只进不出
两个队列是被存放在结构体数组中的，结构体数组存放在运行队列中
且运行队列中存在active指针和expired指针分别指向活跃队列和过期队列。

活跃队列

时间片还没有结束的所有进程都按照优先级放在该队列
nr_active: 总共有多少个运行状态的进程
queue[140]: 一个元素就是一个进程队列，相同优先级的进程按照FIFO规则进行排队调度,所以，数组下标就是优先级！
从该结构中，选择一个最合适的进程，过程是怎么的呢？

从0下表开始遍历queue[140]
找到第一个非空队列，该队列必定为优先级最高的队列
拿到选中队列的第一个进程，开始运行，调度完成！
遍历queue[140]时间复杂度是常数！但还是太低效了！

bitmap[5]:一共140个优先级，一共140个进程队列，为了提高查找非空队列的效率，就可以用5*32个比特位表示队列是否为空，这样，便可以大大提高查找效率！

过期队列

过期队列和活动队列结构一模一样
过期队列上放置的进程，都是时间片耗尽的进程
当活动队列上的进程都被处理完毕之后，对过期队列的进程进行时间片重新计算

queue[140]&优先级&队列数组下标

task_struct *queue[140]
维护的是一个140个队列的进程PCB的数组（指针数组）
数组有140个元素，每个元素指向一个队列的第一个进程PCB，存放的PCB地址。
140个下标可以包含140个队列。但是❗只用100~139的下标&队列。（40个）

之前我们笼统的理解为进程的调度是进程的PCB在runqueue里面排队，其实是在上面的queue里面排队。

怎么体现优先级呢❓前面提到进程的优先级只有40个。
若进程的优先级相同又该怎么办呢❓
进程的优先级也是[60,99]（40个）
普通优先级：100～139（我们都是普通的优先级，想想nice值的取值范围，可与之对应！）
实时优先级：0～99（不关心）

优先级和队列数组下标转化：

优先级+40=下标值
下标值-40=优先级的值
存在一一对应的关系

例：优先级为60的进程直接把进程的PCB链接到下标值：60+40=100的地方。

所以表面看起来，LinuxOS维护了一个运行队列，但实际上OS维护了40个运行队列。

CPU调度一个进程找到运行队列数组，找到活跃队列，以优先级顺序找到队列，取队列中第一个进程的PCB来调度。

bitmap[5]&O(1)调度算法

如果前面大面积没有进程PCB存放，只有在后面才有进程PCB存放。那么CPU在调度进程时，需要遍历数组，才能找到存放进程PCB的位置。效率低且麻烦。

由我们bitmap数组去解决这个问题！其实就是位图法，在我们C++也会学习到！
long bitmap[5]
long是4个字节，8*4=32个bite位，有32*5=160个bite位
把数组中的每一个位置的队列看成bitmap中的一个bit位（0/1序列）
只用140个位置
设定：bit位为0的表示队列数组中的这个位置的队列无进程PCB
bit位为1的表示队列数组中的这个位置的队列有进程PCB
所以，CPU不需要遍历140的队列数组，只需要遍历bitmap的5个位置，遍历一次就查找了32个bite位，大大提高了效率！
时间复杂度位O(1)，所以O（1）调度算法！

nr_active

在Linux内核中，nr_active通常与进程调度、任务管理或资源计数有关。它通常用于表示当前活跃的任务或资源的数量。
在Linux内核2.6版本中，nr_active可能出现在多个上下文中，例如任务队列、进程描述符或资源管理器中。这个变量通常用于跟踪系统当前正在处理或可用的任务数量，以便内核可以进行适当的调度和资源分配
请注意，nr_active的具体含义和用途可能取决于它在内核代码中的具体实现和上下文。因此，要准确理解nr_active在Linux内核2.6中的含义，您需要查阅该版本的源代码，并查找nr_active的使用位置。

active指针和expired指针

运行队列中存在active指针和expired指针分别指向活跃队列和过期队列。CPU调度时只找active指向的队列。

在Linux内核中，特别是在进程调度和任务管理的上下文中，active指针和expired指针通常与运行队列（runqueue）相关。运行队列是内核用于管理和调度进程的数据结构。

active指针：
active指针通常指向当前活跃的任务或进程。活跃任务是指那些已经准备好运行但尚未被调度器选中的进程。这些进程通常位于CPU的运行队列中，等待调度器的调度。active指针帮助内核快速定位并调度这些活跃进程。
expired指针：
expired指针则用于管理那些已经超过其运行时间限制或因为其他原因而被标记为“过期”的进程。这些进程不再处于活跃状态，但仍然需要被适当地处理，例如可能需要被唤醒或重新调度。expired指针帮助内核跟踪这些过期的进程，以便在需要时进行处理。

active指针永远指向活动队列
expired指针永远指向过期队列
可是活动队列上的进程会越来越少，过期队列上的进程会越来越多，因为进程时间片到期时一直都存在的。
没关系，在合适的时候，只要能够交换active指针和expired指针的内容，就相当于有具有了一批新的活动进程！

这两个指针是内核调度器用于有效管理进程运行队列的重要工具。通过它们，内核能够高效地调度和执行进程，确保系统的正常运行和性能优化。

CPU正在执行访问的队列是active指向的A活跃队列（只出不进）
另外一个被expired指向的结构相同的过期队列B（只进不出）
新创建的进程的PCB只链接到过期队列B
CPU调度的活跃队列A中的进程PCB被CPU调度时间片到了之后，也链接到过期队列B
最后A队列中的进程被CPU全部调度完/处理完，B队列也满满的
接着将两个active指针和expired指针交换swap(active，expired)，交换的是指针内容
重复上诉过程

O(1)调度算法之调度过程

CPU正在执行访问的队列是active指向的A活跃队列（只出不进）
另外一个被expired指向的结构相同的过期队列B（只进不出）
新创建的进程的PCB只链接到过期队列B
CPU调度的活跃队列A中的进程PCB被CPU调度时间片到了之后，也链接到过期队列B
最后A队列中的进程被CPU全部调度完/处理完，B队列也满满的
接着将两个active指针和expired指针交换swap(active，expired)，交换的是指针内容
重复上诉过程
在系统当中查找一个最合适调度的进程的时间复杂度是一个常数，不随着进程增多而导致时间成本增加，我们称之为进程调度O(1)算法！
Linux的进程优先级 NI 和 PR - 简书 (jianshu.com)