Linux的调度算法

一：内部结构

今天我们解决这么几个问题在我们一个Linux系统中，要调度那么多进程，那先调度谁，如果有新进程加进来该怎么办，内部到底是怎么处理的

1.runqueue（此图片来自网络）

这个是我们Linux系统的runqueue，听名字就知道，这个就是调度运行中的程序的，也就是管理进程的一个队列，我们看到红圈里，有个queue[140],这个queue一共有140 个元素，前一百个是其他种类进程应用的，这些进程优先级大于我们要运行的程序，他们会保护电脑的安危，前一百个我们现在不用管，以后学习到了再说，后四十个，四十这个正好和nice的那[-20,19]的取值范围正好对应，就是保存了四十个PCB--task_struct ,都是对进程的描述，也就是每个进程的结构体。

这个runqueue用的哈希桶的数据结构，相同优先级的进程会被挂在一起，也就是在哈希桶中的同一个链表里（每个桶都是一个链表）。

2.在Linux的系统中存在两个队列，一个叫活跃队列（active），一个是过期队列（expired），这两个队列是对所有要调度的进程一个管理。

2.1首先回答为什么的问题？为什么要有两个队列，负责全部管理进程

当我们只有一个队列的时候，如果我们的进程被人恶意调度，保持大量程序运行，大量进程需要调度，且这些进程的优先级都很高，而那些已经调度过的进程，也会排队，造成大量拥挤，而那些一直没有调度的，一直需要等待，那么电脑是不是出现了问题。

而当我们有了两个队列的时候，将调度过的进程全部依次放到过期队列，新的进程也要放到过期队列，然后，这就会让active队列一直保持越调度越少的状态，即使有新的进程不断累加，也都会在过期队列乖乖等待下一次的调度。

为什么active队列会越来越少：1.时间片会到，2.进程会退出

2.2接着回答怎么做的问题？两个队列，当活跃队列的全部进程全部都被调度了，活跃队列为空了该怎么做了？两个队列的指针直接交换就可以了。

交换之前：按照优先级调度

交换之后：给了其他优先级进程调度的机会

如何决定什么时候交换：，这里有一个活跃队列进程的数量，当队列里为空，就会进行交换。

3.位图：进行确认位置。

首先声明Linux的内核算法 是O（1）的算法

位图是如何查找位置的：优先级有许多，只能一个一个查有没有进程，会非常浪费，然后就有了位图，位图一共是40个比特位，一共五个字节，一个字节八个比特位。而我们调度的进程是40个，所以每个比特位代表的就是此队列（哈希桶的桶）为不为空。可以通过比特位确定是哪个位置，确定有几个哈希桶里面存了进程。

二：其他概念

三：补充知识

1.进程都要进链表

链表的结构是双向链表结构，但并不是这样的结构，因为上面的结构拓展性非常差，Linux链表是这样的结构，没有数据。。

而且PCB里面的属性，把它们连接在了一起，用的是内部的数据结构，属性是在数据结构外部的。

，在PCB中，每每成了链表。

这样做的意义是什么？一个进程，既可以在全局的链表中，又可以在任何一个其他数据结构中，只要加节点字段就可以。所以就到了下面的第二点，它也在调度队列，也可以在阻塞队列，既不脱离全局队列，也可以保持在其他数据结构。

2.进程在调度队列，阻塞队列中