基本概念

为什么会存在进程优先级？
  进程优先级用于确定在资源竞争的情况下，哪个进程将被操作系统调度为下一个运行的进程。进程优先级允许操作系统根据进程的相对重要性和需求来分配有限的系统资源。
  在操作系统中，进程优先级是指操作系统调度器为每个进程分配的优先级级别

查看系统进程

在Linux中可以使用ps -l指令查看有关进程优先级的信息

同时，我们需要知道几个比较关键的i信息

• UID 表示执行者的身份
• PID 当前进程的id
• PPID 当前进程父进程的id
• PRI 当前进程的优先级
• NI 当前进程的nice值

修改进程的优先级

  当我们需要修改进程的优先级时

1. 输入top指令
2. 输入r,然后再输入进程PID，最后输入nice值

在 Linux 中，执行 top 命令后按下 r 键，表示向 top 命令发送一个重新调度进程的信号。这个操作通常会让 Linux 内核尝试重新分配 CPU 时间片给进程，以优化系统的性能。

• PRI还是比较好理解的，就是进程的优先级(这个值越小，就表示优先级越高)

• NI就是nice值，表示的就是进程可被执行的优先级的修正数值

• PRI计算规则如下：
  $$PRI(new)=PRI(old)+nice$$
    所以当nice值为负数的时候，就会使得PRI变小，从而使优先级变高。所以，调整进程优先级，实质上就是调整进程的nice值

• nice的取值范围是[-20,19]，一共40个级别

为什么调整进程优先级要受限制？
  如果不加以限制，将某个进程调整的很高，而其他的进程调整得很低，优先级高得进程，会优先获得资源，但是后续产生的常规进程就很难享受到CPU等资源，就会产生进程饥饿问题

注意

• 进程的nice值不是进程的优先级，它们不是一个概念，但是进程NI会影响到进程优先级的变化

Linux2.6内核进程调度队列的简要介绍

  以上就是Linux2.6内核中进程调度队列的数据结构
  一个CPU只有一个runqueue
  首先看到活跃进程，进程中queue[140]是一个指针数组，这个数组中，下标从0到99是不使用的，只会使用下标100到139，这也正好对应了进程优先级一共有40个优先级。
  queue中每个元素都是指针，指针指向的是一个链表的头节点，而链表的每个结点都是一个task_struct的结构体，也就是pcb对象，相同优先级的进程的pcb对象就会被放到同个队列中。因此，我们可以将这个queue看作是这样的结构

  这样，判断活跃进程中是否还有进程，就只需要判断数组下标从100到139位置上是否还存在有效的队列地址就可以了
  但是，如果每次都是遍历整个数组的话，效率上又不太高，于是又添加了一个数组bitmap,这个数组有5个元素，且每个元素的类型都是int。由于int类型有32个bit位，所以整个数组就相当于是拥有了160个bit位，这个数组的意义就是通过bit位的位置来记录数组中所对应下标所指向的队列是否为空。（若队列不为空，则对应的bit位为1否则为0）
  举个例子，将整个数组所对应的bit为看作是一个整体，若第120个bit位为1，则说明queue数组中下标为120的元素所指向的队列中还存在进程（因为数组中一共有140个元素,所以需要至少140个bit位才能表示）,变量nr_active表示当前是否有进程需要运行
  所以，CPU维护进程队列中的进程大致过程如下：首先看nr_active,看是否有进程，如果有的话，就会去数组bitmap中查看数组queue中哪个下标存在需要运行的进程，最后直接去对应的下标所指向的队列中拿到对应进程的pcb，并开始运行工作。
  当CPU正在执行活跃进程内的进程时，若后面又有了新的进程或者是当前进程的时间片已经被耗尽，为了不妨碍CPU的执行，就会将该进程放到过期队列中。通过上图的进程调度队列我们可以看到，所谓的活跃进程和过期进程实际上是被放到一个数组array上面的，且该数组的元素都是结构体类型。调度队列runqueue中还有两个变量分别是active和expirea,这两个变量都是结构体指针类型，它们分别指向活跃队列和过期队列。
  随着时间的推进，活跃进程中的进程会不断减少，过期进程的进程会不断增多。操作系统并不会通过数组下标判断哪个是活跃队列哪个是过期队列，而是直接通过active和expirea两个指针来判断，所以当活跃进程中的进程全部被执行完之后，要轮到过期队列了是，只用交换active和expirea两个指针的内容即可
总结一下：
优先级：

• 普通优先级：100～139
• 实时优先级：0～99（不关心）

活动队列

• 时间片还没有结束的所有进程都按照优先级放在该队列
• nr_active: 总共有多少个运行状态的进程
• queue[140]：一个元素就是一个进程队列，相同优先级的进程按照FIFO规则进行排队调度,所以，数组下标就是优先级！

从该结构中，选择一个最合适的进程，过程是怎么的呢？

1. 从0下表开始遍历queue[140]
2. 找到第一个非空队列，该队列必定为优先级最高的队列
3. 拿到选中队列的第一个进程，开始运行，调度完成！
4. 遍历queue[140]时间复杂度是常数！但还是太低效了！
   bitmap[5]:一共140个优先级，共140个进程队列，为了提高查找非空队列的效率，就可以用5*32个bit位表示队列是否为空，这样，便可以大大提高查找效率

过期队列

• 过期队列中的放置的进程都是新增的进程或者是时间片被耗尽的进程
• 当活动队列中的进程被处理完之后，会对过期队列中的进程重新计算

active指针和expired指针

• active永远指向活动队列而expired永远指向过期队列
• 随着时间的推进，活动队列中的进程逐渐变少而过期进程中的进程逐渐变多，当活动队列上的进程被执行完，就会发生两个指针内容的交换，这样过期队列就变成了新的活动队列

O(1)调度
  在系统中查找一个最合适调度的进程的算法的时间复杂度是常数级别的，所以被称之为是进程调度的O(1)算法

和进程优先级有关的概念

竞争性：竞争性: 系统进程数目众多，而CPU资源只有少量，甚至1个，所以进程之间是具有竞争属性的。为了高效完成任务，更合理竞争相关资源，便具有了优先级
独立性：多进程运行，需要独享各种资源，多进程运行期间互不干扰
并行：多个进程在多个CPU下分别同时运行
并发：多个进程在一个CPU下采用进程切换的方式，在一段时间内，让多个进程得以推进，称之为并发

进程切换

  当一个进程在CPU上运行时，CPU上所有的寄存器就要为该进程服务，由此，在运行期间，CPU中的寄存器会存储大量的临时数据(比如执行到哪一行、返回值是多少…)。在pcb对象中，存在一个字段称之为时间片，这个字段中存的是当前进程还剩多长运行时间，当时间片上的时间被耗尽时,也就是说CPU不会为该进程继续运算，这个时候就需要进行进程切换。
  进程切换之前首先要做的就是保存CPU寄存器中的临时变量（因为下一个进程运算时产生的临时数据会覆盖上一个进程的临时数据），这些临时变量最终都会被暂时保存到pcb中，将CPU内部寄存器与该进程相关的所有数据都称之为该进程的硬件上下文数据，这些数据保存在pcb中，就叫做保护上下文。
  一般进程的调度有两种情况

1. 如果时首次调度：将代码放到寄存器eip中，逐步去执行，并将中间产生的临时变量填充到寄存器中
2. 如果时二次被调度：先将pcb中保存的硬件上下文数据恢复，然后代码从上次最后一次执行的位置后面开始执行