Linux：进程：进程调度

进程在CPU上运行具有以下特性：

竞争、独⽴、并⾏、并发

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

独⽴性:

为了避免一个进程出问题而导致其他进程出现连锁反应，进程之间在一定程度上相互独立，即使是父进程和子进程也是如此

并⾏:有同时多个进程被多个CPU调度运行，这种关系就叫做并行

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

基于以上特性，我们要对进程进行调度

进程调度依赖于进程优先级，要了解进程是如何调度的，我们需要先了解进程优先级的规则：

时间片

即CPU分配给该进程允许运行的时间，使各个进程从表面上看是同时进行的。

如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。

如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。而不会造成CPU资源浪费。

在宏观上：我们可以同时运行多个进程，每个进程并行不悖，同时运行。

但在微观上：由于只有一个CPU，一段时间内只能运行一个进程，如何处理公平，一种方法就是引入时间片，让每个进程轮流运行。

进程切换

首先，CPU的构成中有许多的寄存器，这些寄存器保存着当前运行的进程的数据。
 
寄存器被所有进程共享，寄存器内的数据，是属于当前运行进程的，这个数据也被称为 — 上下文数据
 
当操作系统想要运行一个进程，会将对应进程PCB地址传给CPU的某一个寄存器。让CPU能找到这个进程PCB，从而找到对应代码和数据。
 
当进程运行将指令传给CPU，CPU靠指令集分析指令运行对应代码，当进程的时间片结束后，操作系统将保存此时CPU中寄存器内的数据，当再次轮到这个进程后操作系统将原本数据加载到寄存器中，eip就可以通过下一条指令地址让代码继续运行。
 
进程退出CPU，操作系统保留寄存器里的数据，进程回到CPU，操作系统将原本数据恢复到寄存器中。这就完成了进程切换。

进程优先级

Linux进程的优先级是用来确定在多个进程同时运行时，哪个进程会获得更多的CPU时间片。

Linux进程的优先级分为实时优先级和普通优先级。

我们不需要关心实时优先级，只需关注普通优先级即可

查看系统进程

在linux系统中，⽤ps ‒l命令则会输出以下内容：

  

• UID:代表执⾏者的⾝份

• PID:代表这个进程的代号

• PPID：代表⽗进程的代号

• PRI：代表这个进程可被执⾏的优先级，其值越⼩越早被执⾏，普通进程的PRI的范围为[60,99]

• NI：代表这个进程的nice值

nice值

nice值用于调整PRI，其方法为：PRI(old)=PRI(new)+nice（PRI默认为80）

所以，在Linux系统中，调整进程优先级，就是调整进程nice值

nice其取值范围是-20⾄19，⼀共40个级别，对应了普通进程的PRI范围

实例：修改进程11835的nice值，进而改变PRI

 

普通进程向用户显示的PRI的范围为[60,99]，经内核处理为[100,139]：

​ 

下面介绍如何通过优先级来调度进程

Linux2.6内核:进程O(1)调度队列

在内核中有一个名为runqueue的数据结构负责进程的调度，

其中有一个类型为task_struct的指针数组queue[140]

而queue[i]为PRI为i的task_struct链表的头节点

CPU空闲时，就可以遍历这个指针数组，找到第一个不为空的节点并沿着这条链表执行

当然，遍历数组效率较低，所以实际是通过位图（bitmap）来实现的：

即bitmap[5]是一个整形数组，大小为160bit，我们只需要前120个bit，每一个bit对应一个queue[i]，1表示queue[i]不为空,0表示为空，这样我们可以通过高效的位运算来找到PRI最低的task_struct链表

饥饿问题

刚才的调度队列存在一个问题：

如果一个进程的PRI很高，而此时又不断地有PRI较低的进程被创建，那么新创建的进程总是会

先于该进程被CPU运行，导致该进程一直无法被执行，这就是进程的饥饿问题

为了解决这个问题，Linux在一个runqueue里维护了两个队列：活动队列和过期队列，具体实现是将表示队列内进程数量的nr_active和queue[140]和bitmap[5]组成一个新的数据结构struct q，并在runqueue内定义一个struct q数组array[2]， 

其中array[0]为活跃队列，由指针active维护，而array[1]为过期队列，由指针expired维护

CPU通过active指针和expired指针来访问活动队列和过期队列

CPU空闲时，总是从活动队列中寻找优先级最高的进程来执行

当活动队列为空时，会直接将active指针和expired指针交换

新进程或是在CPU上执行时时间片用完，被CPU剥离的进程会进入过期队列

这就在很大程度上避免了饥饿问题