【Linux】进程调度与切换

1. 基本概念

竞争性: 系统进程数目众多，而CPU资源只有少量，甚至1个，所以进程之间是具有竞争属性的。为了高效完成任务，更合理竞争相关资源，便具有了优先级

从上一张进程优先级我们可以知道，进程之间是存在竞争关系的，并且我们要明白一点就是进程在运行的时候，放在CPU中，不是说必须要把代码跑完后才会从CPU下来。在现代的操作系统，都是基于时间片进行轮转的。

独立性: 多进程运行，需要独享各种资源，多进程运行期间互不干扰

我们电脑上可以打开微信，也可以打开qq，也可以打开CSDN，这一个个都都是进程，但是我们在使用一个进程的时候都是不会影响到其他的进程。

并行: 多个进程在多个CPU下分别，同时进行运行，这称之为并行

一般情况下，我们的电脑都是只有一个CPU的，一个CPU维护一个运行队列，如果有多个CPU的话就会有多个运行队列，所以如有多个CPU那么同一时间段就可以实现每个CPU都运行一个进程。

并发: 多个进程在一个CPU下采用进程切换的方式，在一段时间之内，让多个进程都得以推进，称之为并发

为什么我们的电脑只有一个CPU但是可以同时运行微信，qq，CSCN呢？那是因为CPU是通过时间片进行轮询运行在运行队列的进程的，只要速度够快我们人是反映不过来一个时间段只运行一个进程的。就好比之前的老电影都是一张一张的图片进行快速的播放来达到动态的效果是一样意思。

2. 进程切换

我们在讲解进程状态的时候，讲过了进程在运行的时候其实本质是放在了CPU运行队列中，基于时间片轮转发方式进行占用CPU的资源，从而实现了多个进程同时运行的现象。而基于运行队列进行切换轮询式的享受CPU资源，这个轮询的方式就叫做式进程切换的过程。

而CPU中其实是由大量的寄存器的，其中我们所了解的一个寄存器eip俗称pc指针是我们之前有接触过的，pc指针的作用就是记录当前执行代码的下一个需要执行的代码的位置。所以当一个进程在CPU中运行的时候，会产生大量的临时数据，而这些临时数据是存放在寄存器当中的。

那我们就会有一个疑问了，既然进程是基于运行队列时间片轮询方式进行切换的，那么CPU是怎么知道切换后的进程再次来到的时候上一次运行到那里了呢？CPU又是怎么接着根据这个进程上一次运行的到的位置接着运行呢？所以当一个进程运行的时间片到了的时候，CPU因该将改进程运行后的信息进行记录起来，等到这个进程下一次再来的时候接着运行，而这些信息就是保存在寄存器里面的。但是这些信息最终不是放在寄存器中的，而是将信息重新放到进程的PCB中（这里我们就简单的理解是放到PCB中的，其实是更复杂的），等到下次再到CPU中运行的时候重新将数据个CPU，这个时候CPU就知道那些运行了，那些没有运行，而这个信息叫做进程的硬件上下文

• 上面的保存硬件上下文的操作叫做保护上下文。
• 当一个进程第一次被运行那就正常执行，如果不是那么进程放到CPU中运行就得先将曾经保存的硬件上下文数据进行恢复

这里我们要明白的是：

1. CPU内的寄存器只有一套，但是寄存器内保存的数据可以有多套。
2. 虽然寄存器数据是放在一个共享的CPU设备里面呢，但是所有的数据其实都是被进程私有的。

也就是说，虽然我们的寄存器只有一套，但是只要进程来了，那么此时CPU中的寄存器存放的就是该进程的所数据，只要它走了，另一个进程来了，那么保存的就是该进程的数据。这样就体现出来进程的独立性。

3. 进程调度

Linux下实现进程调度的算法，是需要考虑优先级，饥饿问题，以及效率问题的。

之前我们只是简单的画出了进程调度的方式——运行队列。

现在我们来详细的解剖一下，这是一张运行队列中的详细成员：

上面大部分的属性现阶段都是不要太关系的，我们主要关系的是上面话红色框框的属性字段，和画蓝色框框的属性字段。

3.1运行队列实现优先级设计

在Linux下是通过queue[140]这个数组来控制优先级的，这个数组的下标就对应着优先级。

前面我们学习进程优先级的时候，我们说过了进程的优先级范围是[60,99]的一共有40个有限等级。那为什么这里控制优先级的数组是140呢？

首先这里的话我们只关系100 ~ 139,这部分叫做是普通优先级，100-139刚好对应着我们之前学习的进程的40个优先级。所以100对应着就是我们进程优先级的60，139就对应着99，剩下的0~99的部分称之为实时优先级

• 分时操作系统必须以时间片为周期调度不同的进程，是为了确保公平，避免进程饥饿，比如现在的互联网，在互联网的视角中，所有用户都是公平的，不能因为谁的优先级高就仅服务谁，所有用户的优先级都差不太多，不会出现谁的优先级非常高的情况。
• 还有另外一种为实时操作系统则相反，在运行某个进程时，必须跑完，严格按照队列先后顺序进行，如果有更高优先级的进程，允许插队，即实时操作系统必须对用户有高响应这一特性，比如车载系统，绝对不能使用基于时间片轮转的分时操作系统，而必须采用实时操作系统，刹车的指令优先级非常高，在用户需要刹车时他不会考虑音乐播放器进程会不会饥饿。
• 所以我们必须保证一些进程实时尽快的被处理，所以也就有了实时优先级的概念，而0~99这些优先级就是为了这一部分而准备的。

而这个的原型其实是task_struct *queue[140]是一个指针数组，里面存放是处于同一优先级的进程的队列。所以就可以根据优先级插入对应的优先级队列中了。

通过上述我们可以得到40个优先级队列，那么拿到CPU运行的时候都是按照着40个优先级队列依次的遍历进行调度吗？拿到要遍历40次吗，因为着40个队列中大部分情况是不会每个都会有的，所以这必然会有不必要的操作，也会影响一点效率。

3.2 处理效率问题

所以为了防止把把40个队列中都进行遍历一次，在运行队列中的属性中有一个属性int bitmap[5]，这是一个位图。所以在linux下其实时使用位图的方式来确定那些优先级里面是由进程在排队的。

int bitmap[5]有5个int类型的空间，也就是32 * 5 = 160个bit位，也就可以表示160个优先级了。所以bit位的位置就表示哪一个队列，哪一个优先级，bit位的内容就表示队列的内容。即1就表示有队列，0就表示没有队列。

所以我们检测队列中是否有进程，就是检测位图中的bit位是否位1。

而具体检测的过程就是先对int bitmap[5]中这5个元素通过int整形的方式来进行位位操作，一旦与一个整形进行位操作（比如用bitmap[0] & 0xFFFFFFF == 0，如果等于0就说明此时第一个整形位中是没有队列的，那么就去和第二个整形进行对比，一次类推）。而这种算法接近O(1)的算法了。

3.3 活动队列与过期队列

像上述的队列中，如果优先级更高的的队列中一直有进程进行插入的话，那么那些处于优先级比较低的进程就可能长时间的得不到CPU的调度，甚至是可能优先级特别低的进程将一直得不到调度，那么就会出现我们打开程序会出现一直打不开的情况，甚至是打都打不开。

所以Linux的设计者非常的聪明，他在原理的基础上（对应红色的框框）在次创建了一份同样的结构（对应着蓝色框框）所以说活动队列和过期队列是完全相同的一个结构，我们其实可以用一个结构体进行维护。

struct q
{
	int nr_active;
	bitmap[5];
	task_struct queue[140];
}

然后过期队列和活动队列就是使用一下这种结构来表示
struct q array[2]

3.4 如何解决饥饿问题

有了活动队列和过期队列后，就有效的解决了上述的问题。

当CPU在执行活动队列中的进程的时候，后来的进程无论让的优先级有多高，他都不会在添加到后动队列中取了，而是添加到过期队列中去，并且一旦在活动队列中的进程在本才的时间片结束后也不会再次添加到当前的活动队列中去了，而是同样的添加到过期队列中去了。一旦活动队列中的进程都完成了后，这个时候我们的过期队列就变成了活动队列，活动队列就变成了过期队列。

3.5 active指针和expired指针

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

一开始struct q* active = &array[0], struct q* expried= &array[1]。

一旦检测到活动队列中中没有进程了，操作系统就会执行一个操作swap(&active, &expried)，进而完成了活动队列和过期队列的交换。