【Linux】进程管理:状态与优先级调度的深度分析

时间:2024-10-03 20:33:29

✨                                                  山海自有归期,风雨自有相逢      ???? 

????个人主页island1314

????个人专栏:Linux—登神长阶

⛺️ 欢迎关注:????点赞 ????????留言 ????收藏  ???? ???? ????


1. 前言 ????

????之前在这篇文章揭秘计算机内部奥秘:从CPU到操作系统,深入探索进程与线程的工作原理中就已经简述了 进程的部分相关内容,下面我们来进一步深入了解进程的内容。

????进程的基本概念

???? 我们在编写完代码并运行起来时,在我们的磁盘中会形成一个可执行文件,当我们双击这个可执行文件时(程序时),这个程序会加载到内存中,而这个时候我们不能把它叫做程序了,应该叫做进程。

???? 所以说,只要把程序(运行起来)加载到内存中,就称之为进程。
???? 进程的概念:程序的一个执行实例,正在执行的程序等。
???? 如果站在内核的角度来看:进程是分配系统资源的单位。

2. 描述进程-进程控制块(PCB)

2.1 基本概念

????前面说了一个抽象的概念需要一个具体的结构体来进行描述的。进程中的信息就被放在了一个叫做进程控制块(PCB)的结构体中。

在不同的操作系统下进程控制块的名称不同(比如:不同地方的人称呼某一个东西有不同的叫法)

  • 在Linux操作系统中PCB的具体名称是:task_struct

????当一个程序被加载到内存中要开始执行的时候,操作系统同时会给该进程分配一个PCB,在Linux中就是task_struct这里面包含了所有关于进程的数据信息。所以CPU对task_struct进行管理就相当于对进程进行管理

???? task_struct Linux内核的一种数据结构,它会被装载到 RAM(内存) 里并且包含着进程的信息,在进程执行时,任意时间内,进程对应的 PCB 都要包含以下内容:

  1. 标识符:与进程相关的唯一标识符,用来区别其他进程
  2. 状态:进程会有不同的状态,如运行,停止等等
  3. 优先级:相对于其他进程的优先顺序
  4. 程序计数器:程序中即将执行的下一条指令的地址
  5. 内存指针:包括程序代码和进程相关数据的指针,还有和其他进程共享的内存块的指针
  6. 上下文数据:进程执行时CPU的寄存器中的数据
  7. IO状态信息: 包括显示的I/O请求,分配给进程的I/O设备和正在被进程使用的文件列表。
  8. 记账信息:可能包括处理器时间总和,使用的时钟总数,时间限制,记账号等
  9. 其他信息:... 暂且了解上面八个即可,其他就不做过多了解

 2.2 分类详解

???? 进程标识符:描述本进程的唯一标示符,用来区别其他进程

也就是进程的PID,【PID】是操作系统中唯一标识的进程号

有两个获得进程PID】的方式:

  1. 可以使用ps aux查看进程的信息。

  2. 可以使用系统接口得到进程PID和父进程的PPID 

    #include <stdio.h>    
    #include <unistd.h>    
    
    int main() {    
        printf("pid=%d, ppid=%d\n", getpid(), getppid()); // 进程号和父进程号
        return 0;    
    }
    

    ????PPID 的解释:

???? 进程状态:

进程有很多的不同的状态,在kernel源代码中是这样定义的

static const char * const task_state_array[] = {
    "R (running)", /* 0 */
    "S (sleeping)", /* 1 */
    "D (disk sleep)", /* 2 */
    "T (stopped)", /* 4 */
    "t (tracing stop)", /* 8 */
    "X (dead)", /* 16 */
    "Z (zombie)", /* 32 */
};

(1)R- -可执行状态(运行状态)

  • 只有在运行状态的进程才有可能在CPU上运行,注意是可能,并不意味着进程一定在运行中。同一时刻可能有多个进程处在可执行状态,这些进程的PCB(进程控制块)被放入对应CPU的可执行队列中。然后进程调度器从各个可执行队列中分别选择一个进程在CPU上运行。
  • 另外如果计算机只有一个处理器,那么一次最对只有一个进程处于这种状态。

(2)S- -可中断睡眠状态(sleeping)

  • 处在这个状态意味着进程在等待事件完成。这些进程的PCB(task_struct结构)被放入对应时间的等待队列中。然后等待的事件发生时,对应的进程将被唤醒。

(3)D- -不可中断睡眠(disk sleep)

  • 在这个状态的进程通常会等待IO的结束。
  • 这个状态与sleeping状态相似,处于睡眠状态,但是此刻进程是不可中断的,意思是不响应异步信号。
  • 另外你会发现处在D状态的进程kill -9竟然也杀不死。这就相当于我们怎么也叫不醒一个装睡的人。

(4)T- -暂停状态

  • 给进程发送一个SIGSTOP信号,进程就会响应信号进入T状态,除非该进程正处在D状态。
  • 再通过发送SIGCONT信号让进程继续运行。
  • kill -SIGSTOP
  • kill -SIGCONT

(5)Z- -僵尸状态

  • 僵死状态是一个比较特殊的状态。进程在退出的过程中,处于TASK_DEAD状态。
  • 在这个退出过程中,进程占有的所有资源将被回收,除了task_struct结构(以及少数资源)以外。于是进程就只剩下task_struct这么个空壳,故称为僵尸。

(6)X- -死亡状态或退出状态(dead)

  • 死亡状态是内核运行 kernel/exit.c ⾥的 do_exit() 函数返回的状态。这个状态只是⼀个返回状态,你不会在任务列表里看到这个状态

???? 进程优先级:

  • ????因为CPU资源有限,而进程却有很多个,所以需要优先级这个属性去决定了进程拿到资源的顺序。

???? 程序计数器:程序中即将被执行的下一条指令的地址

????CPU有三个工作:取指令,分析指令和执行指令。CPU中的指令寄存器每一次都会保存下一条指令的地址,以此来进行指令判断。

???? 内存指针:包括程序代码和进程相关数据的指针,还有和其他进程共享的内存块的指针

????上下文数据

通常操作系统内核使用一种叫做**上下文切换**的方式来实现控制流。

实行这种机制是因为CPU只有一套寄存器,所有只能有将一个进程的存储数据放入寄存器中计算,从而形成了上下文数据。但是同时有多个进程的时候,操作系统为了使得CPU的利用率最高,所以会让进程之间来回的切换,一般进程切换有两种情况:

  1. 我们称两个执行流在执行的时间上与另一个执行流有重叠的部分,就称这个两个执行流在 并发的运行。一个进程在和其他的进程轮流轮流运行成为 多任务。一个进程执行它的控制流的那一段时间叫做时间片。简单来说,每一个进程都会有最多执行的时间限制,如果执行时间超过了时间片,就会自动的退出执行

  2. 当操作系统内核,发现一个优先级更高的进程的时候,该优先级更高的进程就会抢占当前进程的位置,然后执行优先级更高的进程。等到该进程执行完后,在执行被 抢占 的进程。这种决策方式叫做 调度

以上两种情况,都会使得进程意外的退出CPU的执行,但是下次CPU还想接着上一次执行的地方继续执行那个意外退出的进程,所以就需要在进程退出之前,在task_struct中保留下上一次执行的数据,方便下一次再被执行。

????IO状态信息: 包括显示的I/O请求,分配给进程的I/ O设备和被进程使用的文件列表

3. 查看进程 ????

查看进程有三种方式:

3.1 通过系统目录

???? 在 /proc 这个目录下保存着所有进程的信息。
注意:/proc不是磁盘级别的文件

3.2 通过ps命令

ps aux # 查看系统中所有的进程信息
ps axj # 可以查看进程的父进程号

# 一般的合并操作如下
ps ajx | head -1 && ps ajx | grep 可执行程序/pid

3.3 通过top命令

top命令是一个可以动态查看进程信息的命令(很像windows中的任务管理器)

top # 动态的查看进程的信息,其中的信息默认3秒回更新,按 q 退出

4. 创建进程 --fork() ????

????进程的创建一般有两种方式:

  1. 使用./运行某一个可执行程序,这种是最常见的方式
  2. 使用系统调用接口创建进程,即使用fork()

当时用 fork() 函数之后,就在原来的进程中创建了一个子进程,在 fork() 之前的代码只被父进程执行,在 fork() 之后的代码有父子进程一起执行。

创建的子进程和父进程几乎一模一样,子进程和父进程的共享地址空间,子进程可以或者父进程中所有的文件,只有PID是父子进程最大的不同(注:PID是进程标识符,在上面描述进程里有说)

先来个最简单的案例1:

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

int main()
{
    printf("main 函数的 pid: %d, ppid: %d\n",getpid(), getppid());
    pid_t id = fork();
    if(id < 0){
        printf("Error\n");
    }
    else if(id == 0){
        printf("我是子进程, pid: %d, ppid: %d\n",getpid(), getppid();
    }
    else{
        printf("我是父进程, pid: %d, ppid: %d\n",getpid(), getppid());
    }
}

结果及分析

对于 fork 函数的进一步理解:

案例2 如下:

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

int gval = 0;

int main()
{
    printf("I am a process, pid: %d, ppid: %d\n", getpid(), getppid());
    pid_t id = fork();

    if(id > 0){
        while(1){ // 父进程只读 gval,不做修改
            printf("我是父进程, pid: %d, ppid: %d, gval:%d\n", getpid(), getppid(), gval);
            sleep(2);
        }
    }
    else if(id == 0){
        while(1){ //子进程对 gval 读 + 修改
            printf("我是子进程, pid: %d, ppid: %d, gval: %d\n", getpid(), getppid(), gval);
            gval++;
            sleep(2);
        }
    }
    return 0;
}

案例3:

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

int main()    
{    
    fork();    
    fork();    
    printf("hello\n");    
    return 0;    
}

上面应该是输出了4个 hello,下面这张图就可以解释

????结论:一个父进程可以创建多个子进程,因此我们可以知道 Linux 进程 整体就是一种 树形结构

这里面有很多有意思的点:

fork函数调用一次,返回两次

  • ???? 上面的代码是如何实现执行两个不同的分支语句的呢?其实是因为fork函数会返回两个返回值,一个是子进程会返回0,一个是父进程会返回子进程的PID。所以会同时进程两个分支语句中。

并发执行

  • ???? 父子进程是两个并发运行的独立程序。并发(同一个cpu执行),就是两个执行流在执行的时间上有重叠的部分。也就是说父子进程谁先被调度是不能确定的。

相同但是独立的地址空间

  • ???? 两个进程其实地址空间是一样的,但是它们都有自己私有的地址空间,所以父子进程的运行都是独立的,一个进程中的内存不会影响另一个进程中的内存。

共享文件

  • ???? 子进程继承了父进程所有打开的文件,
    #include <stdio.h>
    int main()
    {
        while (1) 
        {
         	printf("hello world\n");
            sleep(100); // 睡眠100秒
        }
        return 0;
    }
    
    所以父进程调用fork的时候,stdout文件呢是打开的,所以子进程中执行的内容也可以输出到屏幕上

5. 进程状态 ????

5.1 基本知识

小知识:

1. kill 指令

2. shell 脚本监控

# 每隔一秒就查看进程的信息
while :; do ps ajx | head -1 && ps ajx | grep a.out | grep -v grep; sleep 1; done

我们在上面描述进程中已经看过了部分知识,下面是对之前的一个补充

5.2 状态演示

 (1)R运行状态,,S运行状态

  1. 处于R状态的进程有的在cpu中执行,但是很多都是在运行队列中等待运行,也就是该进程允许被调度。
  2. S这种状态是一种浅度睡眠,此时的进程是在被阻塞的状态中,等待着条件的满足过后进程才可以运行。在这种状态下可以被信号激活,也可以被信号杀死。
  3. 可以使用sleep() 系统调用接口使得一个进程睡眠

案例:

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

int main()
{
  int cnt = 0; 
  while(1)
  {
    scanf("%d", &cnt);
    printf("hello world, cnt: %d \n", cnt++);
  }
  return 11;
}

为啥带了printf之后,查出的状态就是S状态?

  • 因为一个时间片的进程是非常短的,根据冯诺依曼体系,printf 打印的时候不是向显示器直接打印,而是往内存去写的,相当于显示器也有自己的缓存,但是如果疯狂写入,缓存很容易写满,导致显示器并不能时时刻刻就绪的,虽然每一次都能看到打印的信息
  • 但其实 printf有 I/0,因此这一份代码看似死循环,其实在死循环的过程中99%情况大部分时间都在做 I/0 的。
  • 因为 I/0 速度比较慢因此当它在while中检测该条件,执行printf代码,才能真正叫作运行状态(R状态)
  • 也就是 放到运行队列里,被CPU 所调动时,其状态才叫作R状态,很多时候进程都处于等待状态(S状态),因为外设不一定就绪.

(2)D磁盘休眠状态
这种状态是一种深度休眠的状态,在这种状态下即使是操作系统发送信号也不可以杀死进程,只能等待进程自动唤醒才可以。

模拟实现:

这种情况没法模拟,一般都是一个进程正在对IO这样的外设写入或者读取的时候,为了防止操作系统不小心杀掉这个进程,所以特地创建出一个状态保护这种进程。

案例:

(3)T停止状态

可以通过发送 SIGSTOP 信号给进程来停止(T)进程。这个被暂停的进程可以通过发送 SIGCONT 信号让进程继续运行。

模拟实现:

可以使用信号

kill -SIGSTOP PID 		// 停止进程, 可以用 kill -19 来替代
kill -SIGSONT PID 		// 继续进程, 可以用 kill -18 来替代

 案例:

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

int main()
{
  while(1)
  {
    printf("I am a process, pid: %d, ppid: %d\n", getpid(), getppid());
    sleep(1);
  }
  return 0;
}

分析及理解:

补充一个知识:

  • 前后台任务:

 我们可以发现在前台任务执行时,输入其他指令也不会产生别的影响,而在后台任务中,我们输入的每个指令都会有相对应的输出,因此我们可以知道:

  • 前台任务用户直接与之交互的任务或程序。用户可以通过输入、点击等方式与这些任务进行实时的交互。通常会占用用户的注意力
  • 后台任务:不需要用户直接交互,且可以在用户进行其他操作时继续运行的任务。用户不需要关注它们的进程

(4)X死亡状态

  • X进程停止执行,进程不能投入运行。通常这种状态发生在接受到SIGSTOP、SIGTSTP、SIGTTIN、SIGOUT等信号的时候。

可以使用kill -9 PID即可杀死一个进程,上面我们也用到了 kill -9 .

(5)Z僵尸状态

  • 僵死状态(Zombies)是一个比较特殊的状态。当进程退出并且父进程(使用wait()系统调用,后面讲)
  • 没有读取到子进程退出的返回代码时就会产生僵死(尸)进程
  • 僵死进程会以终止状态保持在进程表中,并且会一直在等待父进程读取退出状态代码。

所以,只要子进程退出,父进程还在运行,但父进程没有读取子进程状态,子进程进入Z状态

案例:

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

int main()
{
  printf("父进程运行:pid: %d ,ppid: %d\n", getpid(), getppid());

  pid_t id = fork();
  if(id == 0)
  {
    // 子进程
    int cnt = 10;
    while(1)
    {
      printf("我是子进程,pid: %d ,ppid: %d, cnt: %d\n", getpid(), getppid(), cnt);
      sleep(1);
      cnt--;
    }
  }
  else
  {
    // 父进程
    while(1)
    {
      printf("我是父进程,pid: %d ,ppid: %d\n", getpid(), getppid());
      sleep(1);
    }
  }
  return 0;
}

5.3 孤儿进程

????如果父进程比子进程先退出,那么此时子进程就叫做孤儿进程。而操作系统不会让这个子进程孤苦伶仃的运行在操作系统中,所以此时孤儿进程会被init进程(也就是1号进程,即所有进程的祖先)领养,从此以后孤儿进程的状态和最后的PCB空间释放都是由init进程负责了。

5.4 僵尸进程

a. 为什么会出现僵尸进程?

  • 前面说过进程的作用是为了给操作系统提供信息的,所以在进程调用结束之后,应该将该进程完成的任务情况汇报(exit code)给操作系统,但是进程在执行完之后已经结束了,所以此时进程的状态就是僵尸状态。

b. 僵尸进程的概念

  • 僵尸进程:即进程已经结束了,但是父进程没有使用wait()系统调用,此时父进程不能读取到子进程退出返回的信息,此时就该进程就进入僵死状态。

c. 僵尸进程的危害

  • 进程已经结束了,但是进程控制块PCB却还是没有被释放,这时就会浪费这一块资源空间。所以会导致操作系统的内存泄漏。

d. 如何消灭僵尸进程?

  • 僵死状态需要父进程发出wait()系统调用终止进程,如果父进程不终止进程,那么此时要消灭僵尸进程只能通过找到僵尸进程的父进程,然后kill掉这个父进程,然后僵尸进程就会成为孤儿进程,此时由init进程领养这个进程然后杀死这个僵尸进程。

具体演示在上面已经写过,大家可以在上面自行查看。

5.5 进程状态转换

6. 进程优先级 ????

6.1 基本概念

  • cpu资源分配的先后顺序,就是指进程的优先级(priority)

  • 优先权高的进程有优先执行权利。配置进程优先权对多任务环境的linux很有用,可以改善系统性能

  • 可以把进程运行到指定的CPU上,这样一来,把不重要的进程安排到某个CPU,可以大大改善系统整体性能

6.2 进程优先级的意义

之所以会存在进程优先级,是因为cpu本身的资源分配是有限的,一个cpu一次只能run一个进程,但是一个操作系统中可能会有成千上百的进程,所以需要存在进程优先级来确定每一个进程获得cpu资源分配的顺序。

6.3 查看进程优先级

在linux或者unix系统中,用ps –al或者ps -l命令则会类似输出以下几个内容:

注:ps -l 查看 进程优先级 信息,ps -al 查看整个系统的 优先级信息

其中我们来了解几组关于进程优先级的相关信息:

  1. UID : 代表执行者的身份
  2. PID : 代表这个进程的代号
  3. PPID :代表这个进程是由哪个进程发展衍生而来的,亦即父进程的代号
  4. PRI :代表这个进程可被执行的优先级,其值越小越早被执行
  5. NI :代表这个进程的nice值
  6. Linux的默认优先级是80

6.4 PRI 和 NI 的异同

PRINI是一组对应的概念。NI的取值会影响到PRI的最终值。

PRI代表进程被CPU执行的先后顺序,并且 PRI越小进程的优先级越高NI代表nice值,表示进程的优先级的修改数值。所以两者之间有一个计算的公式:(new)PRI = (old)PRI + NI

注意:

  1. 1. PRI 在系统中默认为 80

2. NI 的取值范围为 [-20,19],一共40个级别 

相异之处:

  • 需要强调一点的是,进程的nice值不是进程的优先级,他们不是一个概念,但是进程nice值会影响到进程的优先级变化。
  • 可以理解nice值是进程优先级的修正数据。

6.5 修改进程优先级

(1)通过top命令更改nice

top命令 上面有说明,这里我们就直接使用了。

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

(2)通过renice命令更改nice

语法格式:renice nice值 进程PID

6.6 NI 为什么会在可控范围内

该问题即 为啥Linux的优先级调整会被限制?

????由于我们现在用的系统都是分时操作系统进程调度需要保证尽量公平,而只有在可控范围内才不会影响到我们的公平调度。如果不受限制,自己可以将自己的进程的优先级设置非常高,而系统的,或者别人的非常低,优先级较高的进程获得资源,后续还有很多今后曾源源不断产生,会导致常规进程享受不到资源。造成进程饥饿问题。

6.7 其它概念

前面一直在介绍单个进程的概念,下面我们稍微了解一下多个进程之间的关系概念。

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

补充:

等待的本质

阻塞:每一个 CPU 都会给 操作系统 提供一个叫作 运行队列的东西。只要进程在运行队列中,该进程就叫作 运行状态,表示我已经准备好了,可以被 CPU 随时调度。

了解完阻塞之后,我们就可以知道卡顿的本质:是CPU 不调动 它了,有以下两种原因:

  1. ① 就是该进程在等待外设,比如键盘数据输入
  2. ② 系统内的进程过多

7. 进程切换及调度 ????

在讲解具体知识前,我们先来了解相关知识:

时间片

Linux / windows 民用级别的操作系统,分时操作系统 --> 调度任务追求公平

???? 进程在运行的时候,放在CPU上,并不是需要将该进程的代码全部执行完才会被拿下CPU,现代操作系统,都是基于时间片进行轮转执行,一个进程在CPU上有一个执行最大时间,即时间片,在CPU上执行了该时间,就会被拿下

7.1 基本理解 

 进程切换(process switch)是操作系统的核心任务之一,用于在不同进程之间进行 CPU 时间的共享和分配。当一个进程在运行时,它占用了 CPU,并占用了其他诸如内存等资源。当操作系统需要执行另一个进程时,就需要进行进程切换。进程切换涉及到保存当前进程的上下文信息,包括 CPU 寄存器、程序计数器、栈指针等,以及恢复调度执行下一个进程所需的上下文信息。

在 Linux 操作系统中,进程切换的实现源码可以分为两个部分:进程调度 和 上下文切换

  • 进程调度负责决定当前应该将哪个进程分配给 CPU 执行;
  • 上下文切换则是在进程切换时,保存当前进程的上下文信息,并恢复调度执行下一个进程所需的上下文信息。

进程调度的代码主要位于kernel/sched/ 目录下,包括了进程调度算法以及实现。而进程切换则需要涉及到进程的 PCB(进程控制块)和线程的 TCB(线程控制块),以及 CPU 的寄存器状态和内核栈等上下文数据。在 x86 架构的处理器上,进程切换的具体实现涉及到  task_switch 函数、 switch_to 宏以及 switch_to_asm 汇编函数等。在 AArch64 等不同架构的处理器上,对应的汇编代码可能有所不同,但目的是一致的。

7.2 进程切换

 CPU里面有大量的寄存器,比如:eax,ebx,ecx,edc,eds/ecs,eip… 等等,当一个进程在CPU 上被运行的时候,这些寄存器会围绕这个进程进行展开运算,保存相关的在执行该进程代码中的信息,临时数据,比如变量,函数等等。

  1. 其中 epi 也就是我们所说的 pc指针,记录进程执行到哪里了(比如PC记录的是一个进程代码的50行,则说明当前执行的是第49行)。这能保证进程在切换回来后还是继续往后执行。
  2. 当一个进程在CPU上的时间到了,要被拿下CPU时,需要将CPU上关于该进程的所有数据(大多是寄存器上的数据)(被称为进程的硬件上下文)全部保存带走,这些数据有些保存到进程的PCB中,有些保存在其他地方,较为复杂。这个过程叫 保护上下文。
  3. 这个进程被拿下后,CPU里面的寄存器的数据还是上一个进程的旧数据,当这些寄存器需要存储新的进程的相关数据时,直接覆盖式的写入即可。
  4. 如果是首次调度该进程,就直接从代码开头运行即可,如果不是首次调度,进程被放到CPU上运行时,则需要先把上次的硬件上下文数据进行恢复(恢复上下文),然后根据 eip寄存器 中保存的上次代码执行的位置继续执行。
  5. CPU内的寄存器只有一套,虽然寄存器数据放在了共享的CPU是设备里面,但是所有的数据,其实都是被进程私有的

总结:进程在被执行的过程中,一定会存在大量的临时数据,会暂存在 CPU 内的寄存器中。

我们把进程在运行中产生的各种寄存器数据,我们叫进程的硬件上下文数据。

  • 当进程被剥离:需要保存上下文数据
  • 当进程恢复时:需要将曾经保存的上下文数据恢复到寄存器中。

调度器根据保存的进程上下文,就可以实现进程切换

7.3 进程调度 

进程调度的核心代码实现参考kernel/sched 目录文件,主要包含以下几个部分:

  1. 调度算法:Linux 中实现了多种不同的进程调度算法,如 CFS(Completely Fair Scheduler)、O(1) 调度算法、实时调度算法等,并且各个算法之间可以配置和切换,由用户指定默认调度器。(注:Linux实现进程调度的算法,需要考虑优先级,考虑饥饿,考虑效率)
  2. 调度队列:调度算法的实现需要用到调度队列,它通过双向链表的数据结构来管理所有进程。Linux 中有就绪队列、休眠队列、实时队列等不同类型的队列,它们存储着不同状态的进程。
  3. 进程状态:Linux 中的进程状态有很多种,如 TASK_RUNNING(运行中)、TASK_INTERRUPTIBLE(可中断的)、TASK_UNINTERRUPTIBLE(不可中断的)、TASK_STOPPED(已停止的)等。进程在不同状态下会被放置到不同类型的调度队列中,以便进行合适的调度。

  • ???? 活跃队列

    ????时间片还没有结束的所有进程都按照优先级放在该队列

  • nr_active:总共有多少个运行状态的进程
  • queue[140]:  一个元素就是一个进程队列,相同优先级的进程按照FIFO规则进行排队调度,所以,数组下标就是优先级!
  • 先看蓝色框内的内容,有个叫 queue[140] 的数组,这里的 queue 数组表示活动状态进程的进程队列
  • 其中在queue数组中,索引【0~99】号下标我们是不用的,这是因为0-99号下标对应的是 实时进程的优先级,实时进程是内核里更加重要的进程,放在前100位由操作系统控制,避免系统抢占的情况。
  • 所以我们只剩下 [100-139] 这个范围可操控,其实这也就和我们优先级的可控范围大小相同,正好对应队列的四十个空位,而OS通过某种映射关系,将可控优先级映射到数组 【100-139】的下标
  • 从该结构中,选择一个最合适的进程,过程是怎样的呢?

1. 从0下表开始遍历queue[140]
2. 找到第一个非空队列,该队列必定为优先级最高的队列
3. 拿到选中队列的第一个进程,开始运行,调度完成!
4. 遍历queue[140]时间复杂度是常数!但还是太低效了,因此我们就用到了下面的位图判断。

  • bitmap[5]:一共140个优先级,一共140个进程队列,为了提高查找非空队列的效率,就可以用5*32个比特位表示队列是否为空,这样,便可以大大提高查找效率!

???? 位图判断

????  bitmap数组,类型为int,这个数组用来干嘛呢?只能存储5个整形变量。数组的名字叫做bitmap已经很明显了,就是位图,5个整形元素有 32 * 5 = 160 个比特位,比特位的位置,表示哪一个队列。比特位的内容,表示该队列为不为空。

比如:0000 … 0000 ,如果最左侧0对应queue[100]的位置,那么如果该比特位为0表示在该下标映射的优先级下该队列为空,否则不为空。

那么为什么要用位图?

  • 遍历整个队列的时间开销要远大于查找位图。
  • 所以,bitmap是用来检测队列中是否有进程,检测对应的比特位是否为1!

在蓝色框内还有一个元素:nr_active ,在 Linux 中,nr_active 是运行队列中用于表示活跃进程数量的计数器。nr_active  的值可以告诉内核有多少进程正在等待执行,从而帮助内核进行进程调度和资源分配。

???? 过期队列

????在红色框中的三项属性与蓝色框中的三项属性完全相同,也就是另外一个队列,被称为——过期队列。

活跃队列表示当前CPU正在执行的运行队列,而 正在执行的运行队列(也就是活跃队列)是不可以增加新的进程的。

所以操作系统设置了一个 和活跃队列相同属性的过期队列,当活跃队列正在执行时如果有进程需要添加进运行队列,那么就会添加至过期队列当中,也就是说 活跃队列的进程一直在减少,而过期队列中的进程一直在增多!

当活跃队列的进程执行完毕后,就会和过期队列进行交换,它们交换的方式是通过两个结构体指针:

  • 就是  activeexpired 结构体指针,它们分别指向 活跃队列和过期队列,而活跃队列与过期队列由于属性完全相同,于是被放在了一个叫做prio_arry_t[2] 的数组里,prio_arry_t[0] 指向活跃队列prio_arry_t[1]指向过期队列
  • 当活跃队列被CPU执行完毕后,我们 只需要交换两个指针的内容即可,这样仅仅只有指向的内容变了,然后活跃队列变为过期队列,过期队列变活跃队列,并且时间复杂度为 O(1):
  • 新增进程在过期队列里插入,此时正在执行的是活跃队列,所以这个时候在过期队列里就有时间处理竞争饥饿的问题了。

总结:

  • 进程切换最重要的部分就是进程上下文的保护和恢复。
  • 进程调度的优先级问题活跃进程数组的下标与进程优先级形成一种映射关系 解决。
  • 进程调度的时间复杂度问题由 位图和两个结构体指针 解决,时间复杂度控制在了O(1)。
  • 进程调度的进程饥饿问题由 活跃队列 和 过期队列 解决。

补充:

 active 指针和 expired 指针

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