Linux相关概念和重要知识点（11）（进程调度、Linux内核链表）

1.Linux调度算法

上篇文章我粗略讲过queue[140]的结构，根据哈希表，我们可以将40个不同优先级的进程借助哈希桶链入queue[140]中。调度器会根据queue的下标来进行调度。但这个具体的调度过程是怎样的呢？以及runqueue和queue[140]的关系是什么？我们需要更深入了解

（1）queue

PCB* queue[140]只是一个成员变量，它存在于另一个结构体queue中。

我们可以用数组queue[140]和结构体queue来区分它们。

当有PCB从里面链入或者链出时，nr_active和bitmap都会相应更新

我们可以知道，一个结构体queue就能将进程按优先级处理完，但进程的处理是动态的过程，我们要知道他是怎么流转起来的。这就需要知道runqueue的结构了。

（2）runqueue

runqueue是以结构体queue为基本结构，为满足动态调度而建立起来的。其中active活跃指针指向的array里面的PCB* queue[140]就是CPU正在调度的PCB队列，换句话说，调度器只会从active指向的PCB队列中调度进程。这样实现为什么呢？那另一个array干什么呢？我们需要设想，如果在CPU执行的过程中由新的进程加入进来怎么办？同时，CPU要如何在既保证优先级又保证较为公平的调度呢？

（3）调度算法

①新增：当有新的进程加入runqueue时，它并不会直接加入active指向的队列，而是会链入expired指向的结构体queue里面的PCB* queue[140]，链入规则和前面一样，都遵循哈希算法。

②现有的进程：当active指向的队列里的一个进程被执行完一次之后，它并不会被链入到当前active对应的PCB* queue[140]中，而是会和那些新进程一样，链入expired指向的PCB* queue [140]中。

③完成的进程：当有进程在active被执行一次并完成后，就会进入Z+X状态，就不会被链入expired里面的PCB* queue [140]了，等着被父进程读取回收就行了

我们发现，expired对应的PCB* queue [140]对应的PCB*越来越多（nr_active也增大），而active对应的PCB* queue [140]却越来越少（nr_active减小）。当nr_active == 0时，active和expired的指针交换，这个时候我们就发现expired（原来的active）空了，active（原来的expired）满了。接下来就继续按上述规则执行（active取，放回expired，新增放入expired），如此往复，一个动态的调度过程就形成了。

从上述过程我们就能发现整个调度过程既保证了优先级，也保证了公平性，同时新增入的进程也不会和正在执行的进程发生冲突。调用规则保证了每一次循环active里面的每一个PCB都会被执行（nr_active记录PCB*数量，每调用一次就减1，不会遗漏），而按照顺序调用又保证了优先级，即优先级高的先执行，低的后执行。

（4）bitmap存在的意义

runqueue中active、expired、array[2]存在的意义很明确，没有它们就构不成整个调度的流转，上述的过程就是它们存在的意义。对于queue来说，nr_active用于记录PCB*的数量，即active、expired分别指向的结构体里进程的数量，只有当active里面的进程调度完了（nr_active == 0）才会swap两个指针，它明确了每次swap的时机，也保证了调度进程的公平性。

但还有个细节，那就是遍历PCB* queue [140]效率不高，明明数组可以随机访问，但又要保证所有PCB都被访问，所以就有bitmap的出现。通过160位bit我们可以得到140个位置存放PCB的情况，比如假定bitmap[0]是5，根据101B，我们得到PCB* queue[140]的第0位和第2位有进程，其余30位都没有进程，可以直接跳过。每个int我们就可以扫掉32个位置，效率很高。具体操作涉及到位操作，之前也有讲过一些位操作得到1或0的办法，很多，这里我们明白是怎么一回事即可。

总结：这是一个进程饥饿问题（公平与优先级的矛盾），采用双queue来解决问题，使得active永远处于存量竞争状态，随着时间竞争越来越小，再交换指针重复操作，实现公平与优先级共存。整个调度算法框架的时间复杂度控制在O(1)，效率很高。

2.Linux内核链表

我们常见的链表无外乎分为带头和不带头、单向还是双向、循环还是不循环。这种链表有个共同特点，就是数据和链绑定在了一起。但在Linux内核中，一个PCB，它有可能既是在queue队列，又有可能在waitqueue，那么我们应该怎么做呢？这就是Linux的内核链表，它将链和数据分离，用位操作来访问，极大增强了数据链接和访问的效率。

但这种链表访问数据很麻烦，因为我们只能得到链表连接点的地址，而其它地方的地址并不好拿，我们要想办法拿到struct的起始地址。思路是&(struct  A*)0->(要查找的成员变量链接点)可以得到偏移量offset（宏），再使用(链接点) - offset得到struct A的起始地址，之后就能正常访问了。难点在C语言，学习过偏移量和宏应该能很快理解。

PCB之间就是用这种链表联系起来的，在不同状态切换的效率上很有优势