进程调度

我们之前讲解进程状态时讲的进程调度(进程队列、运行队列等)，其实是教材理论上的进程调度，这其实只是调度算法的一种，实际的进程调度还要考虑到进程优先级！讲进程优先级体现到调度中！

Linux真实调度算法

调度和切换共同组成了调度器，调度器是做什么的呢？
1、做进程切换、2、选择进程、3把进程放入CPU

接下里讲解这个调度算法
场景： 一个CPU，一个运行队列runqueue

queue[140] （实时OS和分时OS）

runqueue里面有个queue[140]，我们先看看这个
这个queue的类型为 struct task_struct * queue[140]，实际上就是一个指针数组，数组里有140项！
这里为什么是140项呢？这来源于Linux优先级有140个，但是之前讲解优先级，优先级是[60~99]吗？只有40个，但是Linux中优先级就是有140个，我们现在分成[0~99]共一百个优先级，这个部分优先级我们称为实时优先级（不考虑）

我们现在OS分成两大类别的，一个是分时操作系统（进程优先级部分讲过），分时操作系统是根据时间片为单位来进行公平调度；
还有个OS是实时操作系统，一旦来了一个进程，就必须将这个进程处理完才会处理下一个进程，不会等待时间片结束来切换，而在实时操作系统中的进程大小往往也不会很大，实时操作系统的应用领域是在工业、制造业

例子：汽车会有自己的车载系统和行车电脑，行车电脑会做很多智能控制和辅助操作，当汽车离前车太近了，汽车辅助系统会自动调节速度并主动跟车，如果快要撞上了，汽车会主动刹车！

这里可以刹车的只有人和系统，你敢在汽车系统装分时操作系统吗？在刹车这样的紧急情况，分时操作系统因为时间片让刹车进程滚蛋，并因为音乐进程的优先级高，难不成要让刹车等吗？

一般是在音乐进程调度时，传感器发现汽车要撞车了，此时OS会直接接管，并在内部直接创造一个实时任务，优先级为0，直接把级别干到最高

生产线产品良频率不高，我们现在肯定是需要立即停止生产，我们要求它快速响应

所以，实时操作系统更多是应用于工业和制造业，而分时操作系统更多的应用于互联网上的

而Linux使用领域广泛，所以分时和实时两个操作系统都会被应用的

而剩下的40个优先级不就和我们进程优先级数量对上了吗？x-60+(140-400这样就可以将进程优先级映射到着140个优先级中了

而这样的队列一共有140个，我们关心的进程优先级的40个，而每一个队列都保存的是 task_struct，其中在进程优先级60处的队列，有三个进程优先级是60的进程，这三个进程都可以链入到这个队列，其他优先级进程也同理，链入到对应优先级的task_struct 中

所以未来去挑选一个进程，从上往下遍历这个数组，对应指针为空查下一个，直到查到不为空的指针，把这个指针第一个进程取出来，这个进程就是我们要调度的对象，所以从宏观上，通过遍历来实现根据优先级来调度进程，而在局部上是采用先进先出的规则

根据上面的讲解，优先级和调度的特性已经体现出来了！这个runqueue指针是全局指针，CPU找到runqueue后可以在这个queue里找，那这个queue到底是什么东西？，假设现在来了一个进程，优先级为62，此时这个进程就在queue里，一个一个找，直到找到62优先级的位置，并链入其中，所以这个表本质就是一个hash表！就是一共开散列式的hash，x-60+(140-400)这个是哈希转化算法

bitmap[5]

但是在OS层面，即调度器要调度一个进程，如果这个进程优先级为60，则查找效率肯定为O(1)，那要是这个进程优先级低，并且前面没用进程，那调度器还要去遍历这个数组，所以效率还是O(n)的
所以调度器要如何快速的挑选进程呢？
接下来我们来讲解bitmap[5]

类型为unsigned int bitmap[5]，unsigned int 无符号整数有32个bit，数组有5个元素，所以bitmap一共提供了160个bit，其实这个是一个位图，二进制数位图

bitmap比特位的位置：queue[140]，哪一个slot(一个 bit slot = 1 个二进制位的位置)

0000 0000 ,一个比特位的0代表着queue[0]的位置

比特位的内容：1/0，是否为空

即 0000 0100 代表着 queue[2]的位置有进程，这就是这个位图的含义

这样也是为什么这个位图的数组是5，4个不够位，6个太多了，5个刚刚好只多20个

所以，调度器调度进程有两步骤：1、挑队列、2、挑进程

调度器找进程，挑队列，之前我们讲到要遍历找队列，而现在我们不用了，我们直接查位图就可以了，根据位图，统一查32个比特位，共5次，我们发现bitmap[1]不为零，所以去biemap[1]内查那个比特位不为0，这样就可以在一定程度上缓解调度器遍历查队列的时间复杂度，由遍历转化成查位图，这样挑进程，时间复杂度可以近乎位O(1)了

Linux真实调度算法：O(1)调度算法

在图中还要一个变量是nr_active，是记录整个队列中进程数量的

所以调度是先判断nr_active， nr_active大于零，再去看bitmap，然后确认下标，再索引找到队列，然后从队列头部提取进程，把进程PCB放入current指针里，然后执行切换算法，然后把current指针指向的进程放入CPU

问题：如果有两个进程，一个进程优先级为60，一个进程优先级为90，优先级为60的进程为死循环！现在的问题是，死循环进程经过一个时间片，进程没有运行完，OS继续把死循环进程放入到优先级60的队列末尾，而每次调度进程都是先调度优先级高的队列，而队列中有死循环进程，会导致一直再60优先级的队列中调度，这样就会早成优先级90的进程进程饥饿

所以目前设计的调度算法并不能非常卓越的调度进程

OS面都这个问题是如何处理的呢？
OS在runqueue中再创建了一套队列（nr_active 、bitmap[5]、queue[140]）
我们可以认为这套队列为一个结构体

struct requeue_elem
{
    int nr_active;
    unsigned int bitmap[5];
    struct task_struct * queue[140];
}

在runqueue中相当于有一个struct requeue_elem prio_array[2];

而在runqueue中还要两个指针！

struct requeue_elem * active = &prio_array[0];
struct requeue_elem * expried = &prio_array[1];

这两个指针分别指向两个结构体，OS将一个设为active活跃进程，一个为expried过期进程，OS只会让调度器调度active中的进程，而调度过一次的进程并且并未调度完的，并不会回到active中，而是在expried中链入对应优先级的队列中，以此往复，active queue进程会越来越少，expried queue进程越来越多，当active中的进程全部调度完（active队列中nr_active为0），这时候再通过swap(&active,&expried)将两个队列交换，以此实现了Linux真实调度算法:O(1)调度算法

这样设计后，既可以实现进程切换，为调度完的进程可以重新回到CPU调度，又可以解决死循环进程导致其他进程饥饿的问题！

拓展：

此时来了个新进程，这个时候这个进程是放到active队列还是expried队列里面？

若进程放在expried队列里，那这个进程不就是就绪状态吗？（OS中进程状态中的知识）

但是现在分时操作系统会有内核优先级抢占的现象，进程优先级高的进程有特权，运行新进程插队来优先占领内核，如何插队？在expried队列里算是插队吗？肯定不是，在active队列中，参与调度才算是插队！是直接把PCB链入到active中对应优先级的队列！新进程优先级比旧进程优先级高，就是有特权插队，在进旧进程前面被调度！这也叫进程抢占！

cpu_load

我们知道一个CPU就有一个运行队列runqueue，两个CPU就有两个
现在有个问题，就是CPU进程数量失衡问题，这样肯定不合理，一个CPU忙碌，一个CPU悠闲，是资源分配不均的体现，而cpu_load即CPU负载就是记录这个CPU上进程的数量，新进程需要链入优先队列，此时需要查看每个运行队列的cpu_load，并找到CPU负载最低的运行队列，将新进程链入其中，这就是多CPU并行运行时保证了CPU的负载均衡，nr_switches也是同理，nr_switches是记录CPU进程切换次数，切换次数高的CPU肯定忙碌