【Linux学习笔记】进程调度与切换之O(1)调度算法

【Linux学习笔记】进程调度与切换之O(1)调度算法

🔥个人主页：大白的编程日记

🔥专栏：Linux学习笔记

前言

哈喽，各位小伙伴大家好!上期我们讲了进程状态 今天我们讲的是进程调度与切换之O(1)调度算法。话不多说，我们进入正题！向大厂冲锋！

一. 孤儿进程

• 父进程如果提前退出，那么子进程后退出，进入Z之后，那该如何处理呢？
• 父进程先退出，子进程就称为“孤儿进程”
• 孤儿进程被1号init进程领养，当然要看看init进程回收咯。

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

int main()
{
    pid_t id = fork();
    if(id < 0){
        perror("fork");
        return 1;
    }
    else if(id == 0){//child
        printf("I am child, pid : %d\n", getpid());
        sleep(10);
    }else{//parent
        printf("I am parent, pid : %d\n", getpid());
        sleep(3);
        exit(0);
    }
    return 0;
}

二. 进程优先级

2.1 基本概念

• CPU资源分配的先后顺序，就是进程的优先权（priority）。
• 优先权高的进程有优先执行权利。配置进程优先级对多任务环境的Linux很有用，可以改善系统性能。
• 还可以把进程运行到指定的CPU上，这样一来，把不重要的进程安排到某个CPU，可以大大提高系统整体性能。

2.2 查看系统进程

在Linux或者Unix系统中，用ps -l命令则会类似输出以下几个内容：

[qcj@white-alicloud processbar]$ ps -l
F S   UID   PID  PPID  C PRI  NI ADDR SZ WCHAN  TTY          TIME CMD
4 S     1000  1257 24278  0  80   0 - 38328 - pts/0    00:00:00 ps
4 S     1000  24278 24271  0  80   0 - 28919 do_wai pts/0    00:00:00 bash

我们很容易注意到其中的几个重要信息，有下：

• UID：代表执行者的身份
• PID：代表这个进程的代号
• PPID：代表这个进程是由哪个进程发展衍生而来的，亦即父进程的代号
• PRI：代表这个进程可被执行的优先级，其值越小越早被执行
• NI：代表这个进程的nice值

2.3 PRI and NI

• PRI也是比较好理解的，即进程的优先级，或者通俗点说就是程序被CPU执行的先后顺序，此值越小进程的优先级别越高

• 那NI呢?就是我们所要说的nice值了，其表示进程可被执行的优先级的修正数值

• PRI值越小越快被执行，那么加入nice值后，将会使得PRI变为：PRI(new)=PRI(old)+nice

• 这样，当nice值为负值的时候，那么该进程将会优先级值将变小，即其优先级会变高，则其越快被执行

• 所以，调整进程优先级，在Linux下，就是调整进程nice值

• nice其取值范围是-20至19，一共40个级别。

2.4 PRI vs NI

• 需要强调一点的是，进程的nice值不是进程的优先级，他们不是一个概念，但是进程nice值会影响到进程的优先级变化。

• 可以理解nice值是进程优先级的修正数据

2.5 查看进程优先级的命令

用top命令更改已存在进程的nice：

• top
• 进入top后按“r”->输入进程PID->输入nice值

注意：

• 其他调整优先级的命令：nice，renice
• 系统函数：

2.6 补充概念-竞争、独立、并行、并发

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

三. 进程切换

CPU上下文切换：其实际含义是任务切换，或者CPU寄存器切换。当多任务内核决定运行另外的任务时，它保存正在运行任务的当前状态，也就是CPU寄存器中的全部内容。这些内容被保存在任务自己的堆栈中，入栈工作完成后就把下一个将要运行的任务的当前状况从该任务的栈中重新装入CPU寄存器，并开始下一个任务的运行,这一过程就是context switch。

📌 注意：

时间片：当代计算机都是分时操作系统，没有进程都有它合适的时间片(其实就是一个计数器)。时间片到达，进程就被操作系统从CPU中剥离下来。

3-4Linux2.6内核进程0(1)调度队列

• 上图是Linux2.6内核中进程队列的数据结构，之间关系也已经给大家画出来，方便大家理解

3.1 优先级

• 普通优先级：100～139（我们都是普通的优先级，想想nice值的取值范围，可与之对应！）
• 实时优先级：0～99（不关心）

3.2 活动队列

• 时间片还没有结束的所有进程都按照优先级放在该队列
• nr_active: 总共有多少个运行状态的进程
• queue[140]: 一个元素就是一个进程队列，相同优先级的进程按照FIFO规则进行排队调度，所以，数组下标就是优先级！
• 从该结构中，选择一个最合适的进程，过程是怎么的呢？
  1. 从0下表开始遍历queue[140]
  2. 找到第一个非空队列，该队列必定为优先级最高的队列
  3. 拿到选中队列的第一个进程，开始运行，调度完成！
  4. 遍历queue[140]时间复杂度是常数！但还是太低效了！
• bitmap[5]: 一共140个优先级，一共140个进程队列，为了提高查找非空队列的效率，就可以用5*32个比特位表示队列是否为空，这样，便可以大大提高查找效率！
  

3.3 过期队列

• 过期队列和活动队列结构一模一样

• 过期队列上放置的进程，都是时间片耗尽的进程

• 当活动队列上的进程都被处理完毕之后，对过期队列的进程进行时间片重新计算

3.4 active指针和expired指针

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

3.5 总结

• 在系统当中查找一个最合适调度的进程的时间复杂度是一个常数，不随着进程增多而导致时间成本增加，我们称之为进程调度O(1)算法！

后言

这就是进程调度与切换之O(1)调度算法。大家自己好好消化！今天就分享到这！ 感谢各位的耐心垂阅！咱们下期见！拜拜~