#1024程序员节｜征文#

目录

1.进程优先级

1.1 概念

1.2 为什么有优先级

1.3 Linux进程优先级

2. 概念预备

2.1 并发

2.2 寄存器

主要类型：

2. 进程的调度与切换

3.1 进程调度

3.2 进程切换

4. 调度算法

4.1 runqueue内部结构

4.2 如何调度

4.3 nr_active和bitmap

4.4 task_struct中的数据结构

---

1.进程优先级

1.1 概念

进程优先级属性是操作系统用来确定进程在多任务环境中获得资源（如CPU调度的时间）的相对重要性或紧急程度的指标。在操作系统中，每个进程都会被分配一个优先级，这个优先级会影响进程调度器如何决定哪个进程将获得处理器时间。

现实生活中，比如在食堂打饭需要排队，排队的本质就是确认优先级。

1.2 为什么有优先级

优先级的设定源于进程间对有限资源的竞争。本质上，这是由于目标资源的稀缺性，导致了系统需要对不同进程的需求进行权衡和排序，以确保资源得到合理分配和高效利用。

1.3 Linux进程优先级

进程不仅有程序的代码和数据，操作系统还会创建一个进程控制块。在Linux中，进程控制块就是一个名为task_struct的结构体，里面包含了描述进程属性的变量和管理所有进程的数据结构。

其中进程的优先级是由几个特定的int类型变量共同表示的。优先级的数字越小，表示优先级越高

#include <stdio.h>
#include <unistd.h>int main()
{while(1){printf("我是一个进程，我的pid: %d，ppid: %d\n", getpid(), getppid());sleep(1);}return 0;
}

我们写一个死循环代码，打印进程的pid和ppid。

运行起来后，我们可以看到进程的标识符pid，使用ps指令加上al选项，l选项可以在第一行打印进程属性名，方便对应查看。a选项可以查看与终端相关的进程，包括其他用户的进程。

第一行中的PRI和NI，分别表示priority和nice，就是这两个变量共同表示优先级。其中pri表示最终的优先级数字，进程默认优先级数字是80，nice是调整优先级的数字，可由用户进程修改。

最终优先级 = priority(默认值) + nice

再次启动myproc程序，修改改进程的nice值。我们可以使用top指令进入实时交互式界面，里面可以查看进程信息。然后按下R按键，上面会要求你输入进程的pid值。

输入完进程的pid值，要求你输入整数来修改nice值，我们直接输入100。再使用ps命令查看该进程的pri和nice值，会发现NI下面显示19，说明nice值最大值是19。最终pri值为99。

我们可以测试一下nice的最小值，如果你还有使用top指令修改nice值，需要使用sudo提高权限。因为操作系统禁止普通用户频繁修改nice值。进入top指令界面，直接将nice值修改成-100。再使用ps指令查看进程属性，发现NI值为-20，说明nice最小值是-20。其中pri值为60。

这表明nice值的取值范围在[-20，19]，相当于有40个优先级。但为什么最终的优先级数字不是之前的pri值加上nice值，而是pri的默认值加上修改后的nice值？

因为用户级别的操作系统是分时操作系统，它的原则是调度进程尽量公平。如果用户随意修改nice值，可能会将某个进程优先级调的特别高，每次都优先调度该进程，会破坏分调度时间公平的原则。

2. 概念预备

2.1 并发

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

单个CPU执行进程代码，不是把进程代码执行完毕，才开始执行下一个进程代码。而是给每一个进程分配一个时间片，基于时间片，进行调度轮转。其中一个进程的时间片到了的时候，不一定要执行完整个程序，可以再任何地方被重新调度切换。

我们可以打个比方，假设张三作为一名大学生，响应国家号召，投身军营，当兵两年。在此期间，学校为张三保留了学籍。两年服役期满，张三意欲重返校园继续学业，此时他需办理恢复学籍的手续，才可以正常上学。

张三就相当于一个进程，学校就是操作系统。张三参军入伍相当于时间片到了，保留学籍相当于保存进程的上下文数据。当服役期满，回学校恢复学籍，就是恢复进程的上下文数据。

2.2 寄存器

CPU寄存器是中央处理单元（CPU）中非常快速的数据存储区域，它们是CPU执行指令时用来存储指令、数据和地址等信息的场所。寄存器的速度远高于普通内存，这是因为它们位于CPU内部，并且使用高速的晶体管技术制成。以下是一些关于CPU寄存器的关键点：

主要类型：

1. 通用寄存器：用于存储数据或内存地址。例如，x86架构中的EAX, EBX, ECX, EDX等。

2. 专用寄存器：

   • 程序计数器（PC）：存储下一条要执行指令的地址。
   • 指令寄存器（IR）：存储当前正在执行的指令。
   • 堆栈指针（SP）：指向堆栈的顶部。
   • 基址寄存器（BP）：用于访问函数的参数和局部变量。

3. 状态寄存器：存储程序的状态信息，如标志寄存器（FLAGS），它包含了各种状态标志，如进位标志、零标志等。

2. 进程的调度与切换

3.1 进程调度

程序计数器本质是一个指针，英文为program counter，也叫pc指针。在x86架构下，pc指针就是eip，用于存储当前正在执行指令的下一条指令的地址。

IR是一个指令寄存器，存储当前正在执行的指令。

如上图所示，当启动磁盘中的名为proc的程序，操作系统会创建一个进程结构体对象，再加载proc程序的代码和数据到内存中。该结构名为task_struct，里面不仅包含各种属性，还有管理进程的数据结构。task_struct对象中会有指向该进程的代码和数据。

其中代码经过汇编，会变成一行行的代码，以code1、code2、code3等来表示一行行的代码。假设代码的左侧是它们的地址。

而CPU中有两个寄存器，ir用来存放当前执行的指令，pc指针存放下一条指令的地址。所以从该程序的第一行代码开始执行，ir存放code1，pc指针存放code2的地址。

当CPU执行完code1时，会根据pc指针的地址，寻找到下一行要执行的代码，并将其更新到ir寄存器中。pc指针会自动更新到下一行代码的地址。

如果下一行代码是要执行某个函数，转成汇编语言，会有call函数后面加上代码跳转地址，pc指针会记录这个地址。CPU就可以顺利执行进程的代码。

总结下来，进程调度就是CPU取指令，更新pc指针，执行获取的指令三个操作的循环。

3.2 进程切换

如上图，启动proc程序时，操作系统为该进程创建一个task_struct结构体对象，并从磁盘中加载代码数据到内存中。其中C/C++代码会转换成汇编代码，上面的汇编代码相当于简单的加法远算。

CPU中的eax和ebx寄存器用来存储数据，mov指令相当于C语言中的赋值。mov eax 10转换成C语言代码就是eax = 10。

    int a, b, c;a = 10, b = 20;c = a + b;

CPU调度该进程时，会存在一个调度队列，假设是一个task_struct类指针，指向proc进程的task_struct结构体对象。CPU通过这个指针可以获得指令，并将其存储到ir寄存器上，pc指针获取当前指令的下一条指令的地址。

值得注意的是，由于数据以二进制形式连续存储，指令并非如文本般分行排列，而是紧密相连。因此，pc指针的地址实际上是当前指令的地址加上该指令的长度，以此确保能够连续访问指令序列。当CPU执行到第二条mov指令，eax和ebx寄存器存放了数据。

如果此时该进程的时间片到了，CPU调度下一个进程，这是如何发生的呢？

当上一个进程运行到mov ebx 20指令，需要切换新进程时，操作系统会把执行的产生的数据和执行到哪一步代码和指令保存下来，这些就是task_struct对象属性中的上下文数据。

做了这个操作后，CPU通过current指针找到新进程的代码，覆盖掉原来的ir寄存器的指令，重新计算pc指针的地址，写入新地址。控制器通过ir寄存器的代码，对eax寄存器进行新的写入，用100覆盖10。

如果切换出去的进程再次切换回来，只需要将上下文数据重新写入到CPU中各个寄存器，就可以被CPU继续执行代码。

4. 调度算法

4.1 runqueue内部结构

在进程状态那一章节，我们讲到进程处于不同状态，本质上处在不同硬件调度队列中。CPU调度进程时通过runqueue队列进行管理。

上图是runqueue结构体内部的变量，其中又包含一个queue结构体对象，queue结构体中有task_struct结构体指针数组，里面的元素用于指向进程的task_struct对象。

因为数组中前100个元素主要是用于存放实时进程，所以不用考虑前一百个位置。这个数组其实是开散列的哈希表，每个元素可以挂一张链表。这个链表是具有相同优先级的进程task_struct对象。如果哈希表优先级为61的进程有很多，CPU会选择优先级为61链表的第一个进程结构提对象。

nice的取值范围为[-20, 19]，刚好有四十个数字。根据优先级计算公式，真实进程优先级的取值范围在[60, 99]。这就可以解释为什么nice取值范围有四十个数，因为管理优先级的队列开放了四十个优先级状态。

进程如何通过自身的优先级映射到queue数组的下标？可以将最终优先级减去最小优先级60，再加上100，就可以获得某个进程在该表的位置。

4.2 如何调度

上图是runqueue内部属性示意图，还有许多属性没有列举出来。其中struct queue array[2]是queue结构数组，queue中task_struct* queue[140]是一个存放task_struct指针的开散列哈希表。在runqueue中，active和expired变量类型是queue结构体指针，一般直接指向array中的两个元素。

首先，CPU调度进程时，只会从active指向的queue结构体对象中的哈希表里查看要调度的进程，也就是图中struct queue array[0]中的哈希表。CPU调度一般会出现三种情况：

• 某个进程运行后退出。进程退出后，可能会变成僵尸状态等待父进程回收，或者直接变成死亡状态，所以这种情况不用考虑。

• CPU在调度时，有新的进程产生。

此时，操作系统会给新进程创建一个task_struct对象，将该结构体对象连入到runqueue队列中。新进程的task_struct对象能否直接连接到active指向的结构体中的哈希表呢？

假设新进程的优先级特别高，如果直接放到active指向的哈希表队列中，会影响CPU的选择。如果不断有高优先级的进程产生，那么CPU就频繁调度新进程，导致优先级低的进程不被调度。

但是CPU要保证每个进程的调度要均衡，所以新进程的task_struct对象会插入到expired指向的哈希表队列中。

• 当某个进程不退出，它的执行时间到达时间片。

当某进程的执行时间到达时间片时，如果不将该进程放到expired指向的队列中，CPU会再次调度该进程，所以这种情况也是将进程放到expired指向的队列中。

在active队列中，执行时间到达时间片的进程会放到expired指向的队列，而新进程也会放到expired指向的队列，那么说明active指向队列中的进程结构体对象，只会越来越少。直到active指向的队列中没有进程结构体对象时，我们该怎么办呢？

因为CPU只调度active指向的队列中的进程。所以我们可以直接将active和expired指针指向的内容互换即可，这样CPU就可以继续调度进程。

4.3 nr_active和bitmap

queue结构体内部，有nr_active整型变量，用来记录task_struct* queue中连接了多少个进程结构体。每次CPU准备选择进程时，会判断nr_active是否为0。如果为0，说明哈希队列中已经没有进程结构体，就会将交换active和expired指针指向的queue对象。

queue结构体内部还有一个bitmap数组，bitmap是一个位图。什么是位图呢？

一个整型变量通常占用4个字节的空间，每个字节包含8个比特位，因此一个整型变量总共占用32个比特位。在这32个比特位中，每个比特位都可以独立地表示0或1，其中0可以用来表示某个变量不存在，而1则表示该变量存在。因此，一个整型变量可以有效地标记32个不同变量的存在状态。

for(int i = 0; i < 5; i++)
{//如果整型元素为0，说明32个比特位上的数也是0//可以一次性判断32个位置上是否有进程结构体对象if (bitmap[i] == 0)continue;//...
}

其中bitmap包含五个整型元素，可以表示160个变量的存在状态，刚好用来标记哈希表中140个优先级是否存在。当判断队列是否存在进程结构体对象，可以遍历bitmap数组上的变量，判断一个元素是否0。如果为0，说明该元素32个比特位上全是0。一次性可以判断队列32个位置上是否存在进程结构体对象。

通过按位与、按位或、按位异或等位运算，可以确定一个元素上有几个为1的比特位，也可以确定比特位上为1的最低位置。

4.4 task_struct中的数据结构

如上图所示，task_struct结构体对象通过一个名为node的结构体来实现链接，而不是直接使用task_struct类型的指针指向下一个task_struct对象。这里的node结构体包含了两个个node类型的指针，只有连接字段，不包含进程属性字段，从而构成了一个双向链表的结构。一般也是使用双向链表的结构。

那这有什么意义呢？如上图，task_struct结构体对象不仅可以在全局链表中，也有可以在任何一个数据结构中，如等待队列，调度队列等。代价就是只要在结构体对象中多加几个node类型的变量即可。

但是我们获取node结构体内的变量，怎么获取task_struct的其他属性？

#include <stdio.h>struct X
{int a;char b;float c;double d;
};int main()
{struct X obj;printf("%p\n", &obj);printf("%p\n", &obj.a);printf("%p\n", &obj.b);printf("%p\n", &obj.c);printf("%p\n", &obj.d);return 0;
}

 代码中有一个X结构体自定义类型，里面包含四种内置类型的属性。我们创建一个X结构体对象obj，分别对本身和它的内部变量取地址。

根据代码运行后的结果，我们可以知道结构体内部属性地址会不断升高。

 假设我们只能获取obj.c的地址，下面来解决如何获取obj的地址，进而访问其他变量。

根据上面的代码实验，我们可以知道obj的地址小于obj.c的地址。那么obj的地址等于c的地址减去偏移量，再强转成X结构体指针类型，这样就可以访问其他成员变量。那如何获取偏移量呢？

因为偏移量等于c地址减去obj地址的差。假设将obj对象初始地址除于0地址，通过对0强转成X结构体指针类型，然后访问c变量，再对这个部分取地址，就获得了c地址。之后，c地址要减去obj的地址，但是obj地址为0，相当于上面的操作直接获得了偏移量。

#define who(type, x) ((type*)((char*)(&x)-(size_t)(&((type*)0->x)))

最后c地址强转成char指针类型，减去偏移量，再整体强转成X结构体指针类型，就获得了obj的地址。这样就解决了通过进程结构体对象在不同队列的地址，获取该进程结构体对象的其他属性的问题。写成who宏，其中type传结构体对象类型，x传已知地址的type结构成员变量。

4.5 调度算法分析

调度进程中使用到了哈希表，哈希表的插入和删除时间复杂度是O(1)级别的。 bitmap是位图，位图操作的时间复杂度也是O(1)级别。

总的来说，Linux调度算法是O(1)级别的。

---

创作充满挑战，但若我的文章能为你带来一丝启发或帮助，那便是我最大的荣幸。如果你喜欢这篇文章，请不吝点赞、评论和分享，你的支持是我继续创作的最大动力！