概要在前面的学习中我们已经知道操作系统通过 PCB进程控制块管理进程也了解了进程的不同状态以及优先级。但是还有两个问题值得继续研究一个进程正在 CPU 上运行突然需要切换到另一个进程那么原来进程执行到哪里了CPU 又是如何记住它的运行位置的如果系统中有很多进程都处于就绪状态操作系统应该让谁先运行又如何快速找到这个进程这就涉及今天的两个核心知识点进程上下文切换和进程调度算法。首先我们要理解 CPU 寄存器、进程上下文以及保存和恢复现场的过程然后再从进程调度的问题出发了解 Linux 曾经使用的经典 O(1) 调度算法看看它是如何利用优先级数组、位图以及活跃队列和过期队列提高调度效率的。一、进程切换与 CPU 寄存器原理1.1 一个死循环进程会一直占用 CPU 吗先来看一个简单的问题。假设我们写了一个程序#includestdio.hintmain(){while(1){printf(hello Linux\n);}return0;}这个程序进入死循环之后就会一直执行下去。那么问题来了如果一个进程一直不结束是不是就会一直占用 CPU导致其他进程没有机会运行当然不是。我们前面学习过操作系统需要管理多个进程并且要合理分配 CPU 资源。CPU 是有限的一个 CPU 核心在同一时刻只能执行一条指令流因此多个进程需要轮流获得 CPU 的使用权。为了实现这种效果操作系统会给进程分配一定的 CPU 运行时间这个时间通常称为时间片Time Slice。我们可以把它理解成一张限时使用的通行证假设系统中有 A、B、C 三个进程操作系统给它们分配一定的运行时间。A 先运行获得自己的时间片。A 的时间片用完操作系统暂停 A。接下来让 B 运行。B 运行一段时间后再轮到 C。等到后面再次轮到 AA 就可以继续运行。这样多个进程就能够轮流使用 CPU。这里要注意时间片不是说进程必须把这段时间全部用完才能退出 CPU。例如进程 A 在运行过程中需要读取磁盘数据而磁盘数据还没有准备好那么 A 就需要等待。此时 A 会进入阻塞状态主动让出 CPU操作系统就可以调度其他进程运行。所以进程离开 CPU 主要有两类情况被动让出 CPU时间片用完或者被更高优先级的进程抢占。主动让出 CPU进程需要等待某种资源例如等待 I/O 操作完成。无论是哪一种情况都会引出一个问题原来的进程暂停以后下一次再获得 CPU 时怎么知道自己执行到哪里了总不能每次重新从 main 函数开始执行吧这就需要认识 CPU 内部的一个重要组成部分——寄存器。1.2 CPU 寄存器程序运行时的临时存储空间我们之前学习过冯·诺依曼体系结构计算机主要由输入设备、输出设备、存储器、运算器和控制器组成。其中CPU 负责执行指令而内存负责存放程序运行所需要的数据和指令。但是CPU 执行指令时并不是每次都直接从内存中读取数据再把计算结果写回内存。因为内存的访问速度远远低于 CPU 内部的运算速度如果每一步都访问内存就会影响 CPU 的执行效率。所以CPU 内部设计了速度非常快的存储单元这就是寄存器Register。寄存器可以理解成 CPU 内部的小型高速存储空间用来暂时保存正在执行指令时需要的数据和状态。例如inta10;intb20;intcab;当 CPU 执行这段代码时需要读取 a 和 b 的值完成加法运算再得到 c 的结果。在实际执行过程中编译器会根据具体情况生成机器指令CPU 也可能利用寄存器保存中间数据和运算结果。寄存器虽然数量不多但它们对程序的执行非常重要。其中有几个寄存器尤其值得我们了解。1通用寄存器通用寄存器主要用于保存程序运行过程中的临时数据例如运算操作数、中间结果以及函数调用过程中需要使用的数据。不同 CPU 架构的寄存器名称和数量不完全相同。例如在 x86-64 架构中可以看到 RAX、RBX、RCX、RDX 等通用寄存器。2程序计数器 PCPCProgram Counter也叫程序计数器。它主要用于记录 CPU 接下来应该执行哪条指令的地址。假设程序中有下面三条指令指令1a 10 指令2b 20 指令3c a bCPU 执行完第一条指令之后需要知道下一条指令在哪里。这时候就需要程序计数器记录下一条待执行指令的位置。因此PC 对程序的正常执行非常重要。在 x86-64 架构中对应的指令指针寄存器通常称为 RIP在 32 位 x86 架构中则称为 EIP。3栈指针寄存器 SPSPStack Pointer也就是栈指针。我们之前学习函数调用时接触过栈帧的概念。函数调用过程中会涉及局部变量、函数参数、返回地址等信息其中一部分会存放在栈上。那么 CPU 如何知道当前栈的位置呢就需要栈指针寄存器来记录当前栈顶的位置。在 x86-64 架构中对应的寄存器是 RSP。4标志寄存器标志寄存器用于保存 CPU 执行指令后产生的一些状态信息。例如两个数进行比较之后结果可能相等也可能一个大于另一个。CPU 会根据运算结果更新相应的标志位后续的条件跳转指令就可以根据这些标志位决定是否跳转。在 x86-64 中这部分状态主要体现在 RFLAGS 寄存器中。5控制寄存器控制寄存器主要用于控制 CPU 的运行模式和内存管理等功能。例如x86 架构中的 CR3 寄存器就与页表管理有关它保存当前地址空间顶层页表的物理地址。后面讲到进程切换时我们还会遇到它。1.3 一个重要区别寄存器不等于寄存器中的数据了解了寄存器之后我们再回到最开始的问题。假设 CPU 正在执行进程 A。此时CPU 内部的寄存器保存着 A 当前运行所需要的数据例如通用寄存器中保存的临时计算结果。程序计数器记录的下一条指令地址。栈指针记录的当前栈位置。标志寄存器保存的运算状态。这些数据共同描述了 A 当前的执行现场。现在A 的时间片用完了操作系统决定让 B 运行。问题来了CPU 的寄存器是由当前 CPU 核心使用的A 离开 CPU 后B 也要使用这些寄存器。如果直接让 B 使用A 原来保存在寄存器中的数据就会被覆盖。那么等到下一次 A 再次获得 CPU 时原来的计算结果、栈位置和执行位置都可能丢失。这显然不行。所以操作系统必须在切换进程之前先把 A 当前运行所需要的现场信息保存起来。等到以后 A 再次获得 CPU 时再把之前保存的信息恢复到寄存器中。这样A 就能够从之前暂停的位置继续执行。这里可以先记住一句话寄存器是 CPU 内部的硬件存储单元而寄存器中的数据是程序运行过程中不断变化的执行现场。进程切换时需要保存和恢复的是这些数据而不是把寄存器本身搬走。这就引出了进程上下文的概念。二、进程上下文与切换机制2.1 什么是进程上下文Process Context我们刚才知道进程运行过程中CPU 寄存器里保存着它当前的执行信息。但一个进程要想继续运行难道只需要保存寄存器就够了吗当然不够。我们知道一个进程并不只是 CPU 正在执行的一段代码它还有自己的虚拟地址空间、内存管理信息、打开的文件、信号处理信息以及其他资源。这些信息共同构成了进程运行所需要的环境。因此进程上下文Process Context可以理解为为了让一个进程能够暂停后再继续运行操作系统需要维护的那一整套运行环境信息。为了方便理解可以把它分成几个层次。1用户级上下文主要是进程在用户空间中的运行环境。例如程序代码段。全局变量和静态变量。堆空间。用户栈。共享库等映射区域。这些信息构成了进程的用户空间运行环境。2寄存器级上下文硬件上下文主要是 CPU 寄存器中的运行状态。例如通用寄存器。程序计数器。栈指针。标志寄存器。其他与当前执行状态有关的寄存器。它们能够帮助 CPU 恢复进程原来的执行现场。3系统级上下文主要是操作系统为了管理进程而维护的信息。例如进程控制块 PCB。进程状态。文件描述符表。信号相关信息。内存管理信息。调度优先级等。这里需要注意进程上下文是一个比较广义的概念。不同教材和内核资料对上下文的划分方式可能有所不同。而在实际的进程切换中我们最关注的是硬件上下文的保存和恢复以及内核如何切换当前运行任务所需要的内核栈和地址空间等环境。2.2 进程切换的本质保存与恢复现在我们已经知道进程 A 要离开 CPU必须先保存自己的执行现场。那么这些信息保存在哪里呢还记得我们之前学习的 PCB 吗PCB 是操作系统用来管理进程的数据结构。在 Linux 中它主要对应task_struct结构体。每个进程都有自己的task_struct里面保存着操作系统管理这个进程所需要的各种信息。因此PCB 是保存和关联进程运行信息的重要载体。不过这里不能简单理解为所有寄存器数据都直接放在task_struct结构体内部。在 Linux 中不同架构、不同类型的寄存器状态可能保存在内核栈、thread_struct或其他专门的数据结构中。它们通过 PCB 关联起来共同完成进程上下文的管理。我们先从整体上理解这个过程。假设现在 CPU 正在运行进程 A接下来需要切换到进程 B。整个过程可以分为三个阶段第一步保存进程 A 的现场。A 离开 CPU 之前操作系统需要保存它当前的执行状态包括必要的寄存器信息和栈信息。第二步切换到进程 B 的运行环境。操作系统需要找到 B 之前保存的运行状态并准备好 B 所需要的内核栈和地址空间。第三步恢复进程 B 的现场。把 B 之前保存的寄存器状态恢复到 CPU 中让 CPU 从 B 上次暂停的位置继续执行。所以进程上下文切换的核心就是保存当前进程的运行现场再恢复下一个进程的运行现场。我们可以把它理解成玩游戏时的存档和读档。A 玩到一半需要暂停就先保存当前进度等以后再次轮到 A 时再读取之前的存档继续游戏。当然这只是帮助我们理解原理的比喻真正的进程切换还涉及内核栈、地址空间和处理器架构相关的底层操作。2.3 一次完整的进程上下文切换下面我们把整个过程串起来。假设系统中有两个进程进程 A正在 CPU 上运行 进程 B处于就绪状态此时A 的时间片用完了。第一阶段时间片用完进入内核。CPU 运行过程中时钟硬件会定期产生时钟中断。当时间片耗尽时内核能够通过时钟中断处理流程发现当前进程已经需要重新调度。注意时钟中断本身并不等于进程切换它只是让操作系统获得处理时机。第二阶段保存进程 A 的运行现场。操作系统需要保存 A 当前的执行状态。例如进程 A | | 当前执行状态 | -- 通用寄存器 -- 程序计数器 -- 栈指针 -- 标志寄存器这些信息会根据具体的处理器架构和进入内核的方式保存在相应的上下文区域中。第三阶段选择进程 B。操作系统通过调度器从当前 CPU 的可运行任务中选择下一个应该运行的进程。假设这次选中了 B。第四阶段切换运行环境。操作系统切换到 B 对应的内核栈并根据需要切换地址空间。例如在两个不同进程的地址空间之间切换时可能需要更新 CR3 寄存器让 MMU 使用新的页表。第五阶段恢复进程 B 的执行现场。操作系统恢复 B 之前保存的寄存器状态。CPU 就可以继续执行 B 的指令。整个过程可以概括为进程 A 正在运行 | | 时间片用完 | v 进入内核处理 | v 保存进程 A 的上下文 | v 调度器选择进程 B | v 切换 B 的运行环境 | v 恢复进程 B 的上下文 | v 进程 B 开始运行那么等到下一次轮到 A 时操作系统再恢复 A 之前保存的状态。A 就可以继续执行而不是从头开始。这就是进程上下文切换的基本过程。2.4 上下文究竟保存在哪里前面我们一直在说保存上下文那么 Linux 到底把这些信息放在哪里这就需要把 PCB、内核栈、thread_struct和 TSS 联系起来理解。1PCB进程的管理中心Linux 中每个进程都有一个task_struct。它记录着进程的各种管理信息例如task_struct | -- 进程状态 | -- PID | -- 优先级 | -- 内存管理信息 | -- 文件相关信息 | -- thread_struct | -- 内核栈相关信息可以把task_struct理解为进程的管理档案。操作系统通过它找到和管理进程的各种资源。2内核栈保存内核执行过程中的现场我们知道每个进程都有自己的用户栈用于用户程序中的函数调用。除此之外Linux 还为每个任务维护内核栈。当进程通过系统调用或者中断进入内核态时内核需要在内核栈上执行函数调用、保存相关现场以及处理内核代码。例如用户程序调用read()读取文件执行过程中进入内核态内核就会在相应的内核执行环境中处理这次请求。如果之后发生进程切换内核需要保存足够的信息让这个任务以后能够继续执行。这里要特别注意进入内核时形成的寄存器现场通常保存在内核栈上的相应结构中而真正的任务切换还需要保存和恢复底层切换所需的寄存器及栈指针。3thread_struct保存与线程执行有关的架构信息task_struct中包含与线程执行状态有关的信息。Linux 中有一个重要的数据结构structthread_struct;它用于保存与具体处理器架构相关的线程状态。例如在 x86 架构下会涉及内核栈指针、部分寄存器状态以及其他架构相关信息。因此我们可以这样理解task_struct负责管理整个任务。内核栈保存内核执行过程中的调用现场和相关寄存器现场。thread_struct保存架构相关的线程执行状态。其他内核数据结构管理地址空间、文件、信号等资源。它们共同配合才能让一个进程在离开 CPU 后再次恢复运行。4TSS任务状态段在学习 x86 架构时还经常会遇到一个概念TSSTask State Segment也就是任务状态段。在传统 x86 硬件任务切换机制中TSS 可以保存任务的处理器状态例如寄存器、栈指针等信息。但是现代 Linux 并不依靠 x86 的硬件任务切换机制完成普通进程切换而是主要通过软件方式保存和恢复任务上下文。在现代 x86 Linux 中TSS 仍然存在但它主要承担一些特定的处理器状态管理工作例如为不同特权级切换提供内核栈信息以及管理 I/O 权限位图等。所以不要把 TSS 和 Linux 的 PCB 混为一谈。简单来说TSS 是 x86 架构提供的一种硬件数据结构而 task_struct 是 Linux 内核自己设计的任务管理结构。2.5 新进程与老进程第一次运行有什么不同现在我们已经知道进程切换时需要先保存当前进程的现场再恢复下一个进程的现场。但是这里又出现一个问题如果一个进程刚刚被创建出来它还没有真正运行过那么操作系统应该恢复什么例如我们通过fork()创建一个子进程。子进程刚创建出来时虽然已经拥有自己的进程管理信息也已经具备运行所需要的基本环境但是它还没有真正获得过 CPU。因此它并不存在一个完整的、由自己之前运行所产生的现场。那么第一次调度时怎么办答案是操作系统需要为新进程准备一个初始运行上下文。也就是说新进程第一次运行时不是恢复之前保存的现场而是使用内核提前准备好的初始上下文进入相应的执行流程。以 Linux 的实现为例内核会根据创建方式准备新任务的内核栈、线程状态以及首次运行所需的执行路径。当调度器第一次选择这个进程时就能够通过相应的底层切换机制让它进入内核中预先准备好的启动流程。之后它才逐渐进入正常的运行过程。所以老进程再次运行恢复之前保存的上下文。新进程第一次运行使用内核准备好的初始上下文。两者的目的都是让 CPU 能够正确开始执行这个进程只不过起点不同。2.6 补充分时操作系统与实时操作系统前面我们提到操作系统会给进程分配时间片让多个进程轮流使用 CPU。这种思想与分时操作系统有关。分时操作系统主要强调多个任务共享 CPU让用户能够获得及时的交互体验。例如我们一边听音乐一边打开浏览器再一边运行编辑器。虽然 CPU 的资源有限但是操作系统可以通过快速调度让这些程序看起来像是在同时运行。而实时操作系统更加关注任务能否在规定时间内完成。例如在工业控制、汽车控制等场景中有些任务不仅要求执行结果正确还要求在规定的时间范围内完成。两者的关注重点不同对比分时操作系统实时操作系统主要目标提高交互体验和资源利用率满足任务的时间约束关注重点响应速度、公平性时间确定性调度特点多任务共享 CPU根据实时任务需求调度需要注意实时系统不一定完全不使用时间片分时系统也可能有优先级调度。这里主要是从设计目标上进行区分。到这里我们已经弄清楚了进程为什么需要切换以及切换时如何保存和恢复运行现场。但是还有一个问题没有解决假设现在有十几个进程都处于就绪状态操作系统应该选择哪一个这就进入下一部分——进程调度。三、O(1) 调度算法与调度队列3.1 从进程切换到进程调度前面我们讲了进程切换。进程切换解决的是当前进程离开 CPU 后如何保存它的运行现场再让另一个进程继续执行。而进程调度解决的是另一个问题当多个进程都想使用 CPU 时操作系统应该选择谁这两个概念虽然经常一起出现但它们不是一回事。我们可以这样理解进程调度决定下一个运行的进程是谁。进程切换真正完成从当前进程到下一个进程的运行环境切换。例如进程 A就绪 进程 B就绪 进程 C就绪现在 CPU 正在运行进程 A。A 的时间片用完后操作系统需要从 B 和 C 中选择一个。假设选择了 B。那么调度器负责做出选择底层上下文切换机制负责让 CPU 从 A 转换到 B。因此进程调度和进程切换是相互配合的两个过程。那么操作系统选择进程时依据什么最重要的依据之一就是优先级。我们之前学习过进程优先级决定了进程获得 CPU 资源的竞争顺序。一般来说优先级越高进程越容易优先获得 CPU。但是系统中的进程数量可能非常多如果每次调度都从头开始遍历所有进程再寻找优先级最高的那个效率会不会很低这就需要设计一种更加高效的数据结构。经典的 Linux O(1) 调度器就是为了解决这类调度效率问题而设计的。3.2 优先级数组把进程按照优先级分类先假设系统中有很多进程进程 A优先级 5 进程 B优先级 2 进程 C优先级 8 进程 D优先级 2 进程 E优先级 5如果每次调度都遍历所有进程逐个比较优先级最后找出最高优先级的进程那么进程数量越多需要检查的对象就越多。有没有更简单的方法我们可以提前按照优先级把进程分组。例如优先级 2A、B 优先级 5C、D 优先级 8E这样当操作系统需要寻找最高优先级的进程时就不必再逐个比较每个进程。只需要找到优先级最高的非空队列再从这个队列中取出一个进程即可。这就是优先级数组的基本思想。在经典 Linux O(1) 调度器中系统使用一个优先级数组来组织可运行进程。每个优先级对应一个队列同一优先级的进程放在同一个队列中。可以简化成下面的结构优先级数组 | -- queue[0] - 进程链表 | -- queue[1] - 进程链表 | -- queue[2] - 进程链表 | -- queue[3] - 进程链表 | -- ...注意这里的每个 queue 本质上是一个链表队列。同一优先级的多个进程可以通过链表连接起来操作系统从对应队列中选择进程。为什么要使用链表因为进程会不断地加入队列、离开队列以及调整位置。链表比较适合这种频繁插入和删除的场景。我们之前学习过 Linux 内核中的list_head它就是一种侵入式双向链表结构。在经典 O(1) 调度器中优先级队列就利用链表组织进程。那么优先级数组到底有多少个位置经典 O(1) 调度器使用 140 个优先级。其中099实时进程优先级。100139普通进程优先级。这里要注意Linux 的优先级数值与我们日常理解的数字大小相反数值越小优先级越高。例如优先级 2 优先级 5 优先级 8优先级 2 的进程会比优先级 8 的进程更优先获得 CPU。这 140 个优先级对应 140 个队列。但是新的问题又出现了如果有 140 个队列操作系统每次调度都要从 queue[0] 开始一个一个检查到 queue[139]才能找到第一个非空队列吗如果还是这样就没有真正解决遍历问题。于是经典 O(1) 调度器又引入了一个重要的数据结构——Bitmap。3.3 如何快速找到最高优先级的进程我们先想一个简单的问题如果一个数组中有很多队列我只想知道哪些队列不为空应该怎么做其实不需要把每个队列中的进程都检查一遍。我们只需要额外维护一张表记录每个队列是否为空就可以了。这张表就是位图Bitmap。Bitmap 的核心思想非常简单用一个二进制位表示一个队列的状态。例如优先级 0 1 2 3 4 5 6 7 Bitmap 0 0 1 0 1 1 0 0我们规定0对应优先级的队列为空。1对应优先级的队列不为空。那么上面的 Bitmap 就表示优先级为 2、4、5 的队列中存在可运行进程。这样操作系统就不需要挨个检查队列了。只要查看 Bitmap就能够知道哪些优先级有进程等待运行。1Bitmap 如何帮助调度器找到进程假设现在有三个非空队列优先级 2有进程 优先级 4有进程 优先级 5有进程由于数值越小优先级越高。所以操作系统应该选择优先级 2 对应的队列。而 Bitmap 可以通过寻找第一个置位的位置快速找到优先级最高的非空队列。2如何快速找到第一个置位的位置这就涉及 CPU 提供的一些位扫描指令。例如在 x86 架构中可以使用BSFBit Scan Forward等指令查找一个数中最低位的 1 所在的位置。Linux 内核也提供了相应的位图操作接口例如find_first_bit()具体实现会根据架构和内核版本有所不同。我们不需要在这里深入汇编指令只需要理解CPU 可以利用专门的位操作指令快速定位 Bitmap 中第一个置位的位置。这样调度器就能够快速找到最高优先级的非空队列。3为什么叫 O(1)我们之前学习算法时接触过时间复杂度。例如O(1)操作次数不随数据规模增长。O(N)数据量增加操作次数也会相应增加。O(N²)数据量增加时操作次数增长得更快。如果每次调度都要遍历 N 个进程那么时间复杂度可能达到 O(N)。而经典 O(1) 调度器通过固定数量的优先级队列和 Bitmap避免了随着可运行进程数量增加而进行线性遍历。因为优先级数量是固定的查找最高优先级非空队列的操作不需要遍历所有进程。所以经典调度器的选择操作可以做到 O(1)。这里的 O(1) 主要指调度器选择可运行任务的核心操作而不是说进程调度和上下文切换中的所有操作都永远只需要一步。3.4 活跃队列与过期队列解决进程饥饿问题到目前为止我们已经知道经典 O(1) 调度器通过优先级数组和 Bitmap可以快速找到优先级最高的非空队列。但是这样还有一个问题。假设系统中有两个进程进程 A优先级较高 进程 B优先级较低如果 A 一直处于就绪状态并且不断获得 CPU那么 B 会不会一直等下去有可能。如果一个低优先级进程长期得不到 CPU就会产生**进程饥饿Starvation**问题。那么操作系统应该怎么处理经典 O(1) 调度器使用了一个非常巧妙的设计活跃队列Active Array和过期队列Expired Array。先不要急着看代码我们先理解它们为什么存在。1什么是活跃队列活跃队列中存放的是当前调度周期内还可以继续使用时间片的可运行进程。可以理解成这些进程已经获得了当前调度周期的运行资格只要时间片还有剩余就可以继续参与调度。2什么是过期队列当一个普通进程的时间片用完后它就不能继续使用当前调度周期分配给自己的时间了。此时调度器会根据它的优先级等信息重新计算相关调度参数并将它放入过期队列等待下一个调度周期。所以Active Array当前调度周期内还有运行机会的进程。Expired Array当前调度周期内已经用完时间片、等待下一轮的进程。注意这里的过期并不是进程已经结束更不是进程退出了。它只是表示当前调度周期的时间片已经用完。3为什么需要两个队列假设现在有 A、B、C 三个进程。它们最初都在活跃队列中Active Array A还有时间片 B还有时间片 C还有时间片随着 CPU 不断调度A 的时间片用完进入过期队列。B 的时间片用完进入过期队列。C 的时间片用完进入过期队列。最终Active Array空 Expired Array A B C此时当前活跃队列已经没有可运行进程了。那么怎么办经典 O(1) 调度器不会重新创建一套队列也不需要把 A、B、C 一个一个搬回去。它只需要交换两个队列的指针。4指针交换两个队列互换身份我们先看交换之前active ----- 原来的活跃队列 expired ----- 原来的过期队列当活跃队列为空时调度器交换两个指针交换之前 active ----- 空队列 expired ----- A、B、C 交换之后 active ----- A、B、C expired ----- 空队列注意这里交换的是两个队列的指针并不是把链表中的所有进程重新复制一遍。原来的过期队列变成新的活跃队列原来的活跃队列则变成新的过期队列。这样A、B、C 就能够进入下一轮调度。整个操作非常高效。5双队列如何帮助缓解进程饥饿假设低优先级进程 B 的时间片用完了。它会进入过期队列。即使高优先级进程 A 在当前周期内多次获得 CPUB 也不会因为每次都要和 A 重新竞争当前活跃队列而被无限期地留在原地。当活跃队列中的进程都用完时间片之后两个队列就会交换。B 就有机会进入新的活跃队列重新参与调度。因此双队列设计可以帮助管理不同调度周期中的运行机会缓解进程饥饿问题。不过要注意O(1) 调度器并不是简单地保证所有进程完全公平。它还会结合动态优先级、交互性等因素调整调度行为。3.5 串联整个 O(1) 调度过程前面我们分别讲了优先级数组、Bitmap、Active Array 和 Expired Array。现在把它们放在一起看看一次完整的调度过程。假设当前 CPU 正在运行进程 A。系统中还有 B、C、D 等进程处于就绪状态。第一步进程 A 的时间片用完。时钟中断让内核获得处理时机内核发现 A 需要重新参与调度。第二步处理进程 A 的时间片。如果 A 的时间片已经用完就需要根据调度规则重新计算相关参数并放入对应的过期队列。第三步检查活跃队列。调度器查看当前 Active Array。如果里面还有可运行进程就继续从活跃队列中选择。如果活跃队列已经为空就交换 Active Array 和 Expired Array 的指针。第四步利用 Bitmap 查找最高优先级队列。调度器通过 Bitmap 找到第一个非空优先级队列。由于数值越小优先级越高因此找到的就是当前应该优先考虑的队列。第五步从链表中取出进程。找到对应优先级队列后调度器从链表中选择一个进程。假设选中了 B。第六步切换进程。调度器确定下一个运行的进程是 B接下来由底层上下文切换机制完成运行环境的切换。保存 A 的必要上下文恢复 B 的上下文。最终CPU 就开始执行 B。整个过程可以用下面的图来理解进程 A 正在运行 | v 时间片用完 | v A 进入 Expired Array | v 检查 Active Array | ---------------- | | 不为空 为空 | | | v | 交换两个队列指针 | | ---------------- | v 检查 Bitmap | v 找到最高优先级非空队列 | v 从链表取出进程 B | v 上下文切换 | v 进程 B 运行这样我们就把 O(1) 调度器的几个核心组成部分串起来了。可以发现它的设计思路其实很清晰优先级数组负责按照优先级组织进程。Bitmap负责快速找到非空队列。Active Array管理当前调度周期内的可运行进程。Expired Array管理时间片已经用完、等待下一轮的进程。指针交换快速完成两个调度周期之间的切换。这些数据结构共同配合完成进程的选择和调度。3.6 调度队列的其他成员除了前面介绍的优先级数组和 Bitmap经典 O(1) 调度器还需要维护一些其他信息。这些信息主要用于记录运行队列的状态以及统计调度情况。1每个 CPU 的运行队列 Runqueue在多核 CPU 系统中不同 CPU 核心可以同时运行不同的进程。因此经典 O(1) 调度器会为每个 CPU 维护自己的运行队列。每个 CPU 都有对应的调度数据结构管理分配给这个 CPU 的可运行任务。这样做可以减少不同 CPU 之间对同一个运行队列的竞争也方便进行负载均衡。2nr_active用于记录当前运行队列中可运行任务的数量。调度器可以通过它了解当前有多少任务处于可运行状态。3nr_switches用于记录上下文切换次数。操作系统可以通过相关统计信息了解系统发生了多少次进程或线程切换。4cpu_load用于记录和计算 CPU 负载相关的信息。内核可以利用这些信息辅助判断 CPU 的工作负载并进行相应的调度和负载均衡。需要注意这些字段的具体定义和使用方式会随着内核版本变化不能把某个历史版本中的字段直接当成当前 Linux 的统一实现。3.7 PRI 与 NI为什么修改优先级要通过 NI前面我们说过优先级决定了进程参与 CPU 竞争时的顺序。那么如果我们想让某个进程更容易获得 CPU应该怎么调整它的优先级在 Linux 中我们经常会遇到两个概念PRI优先级。NInice 值。它们之间有什么关系1什么是 NINI 就是 nice 值也叫友好值。它的取值范围通常是-20 19其中NI 越小进程越容易获得 CPU。NI 越大进程越不容易获得 CPU。例如进程 ANI -5 进程 BNI 0 进程 CNI 10在其他条件相同的情况下A 的调度优先级会高于 BB 又会高于 C。2什么是 PRIPRI 是系统显示和描述进程优先级时常见的字段。在 Linux 的普通进程中优先级数值越小通常表示优先级越高。因此PRI 数值越小 | v 优先级越高 | v 越容易获得 CPU不过ps、top等工具显示的 PRI/PR 是面向用户的优先级表示和内核内部调度器使用的优先级字段不能完全简单地画等号。3NI 和 PRI 有什么关系在经典 O(1) 调度器中普通进程的静态优先级会受到 nice 值影响。可以先简单理解为NI 改变 | v 静态优先级受到影响 | v 动态优先级也会受到影响 | v 影响进程参与调度的顺序经典 O(1) 调度器还会根据进程的交互性等因素计算动态优先级因此并不是只看 NI 一个值。4为什么不直接修改 PRI因为 PRI 是调度器内部根据调度规则维护和计算的结果之一。如果直接随意修改它就可能破坏调度器原有的优先级管理逻辑。而 NI 是专门提供给用户调整普通进程调度倾向的参数。因此我们通常通过调整 nice 值来影响普通进程的优先级。Linux 中可以使用nice-n10./a.out让程序以指定的 nice 值启动。也可以使用renice10-p1234调整 PID 为 1234 的进程的 nice 值。其中普通用户通常只能提高 nice 值也就是降低进程的调度优先级想要提高进程优先级通常需要相应的权限。5修改 NI 后进程会发生什么变化当 nice 值发生变化后调度器会根据新的参数调整普通进程的调度优先级。在经典 O(1) 调度器中进程的动态优先级还会结合其他因素进行计算。当进程时间片用完、需要重新进入调度队列时调度器会根据更新后的优先级将它放入对应的优先级队列。这样进程之后参与 CPU 竞争时就会按照新的优先级参与调度。这里需要记住NI 是用户可以调整的 nice 值PRI 是常见的优先级显示字段而内核内部还有更具体的静态优先级和动态优先级管理机制。四、总结从寄存器到调度队列理解 Linux 进程运行的完整过程这篇文章我们主要解决了两个问题第一个问题进程离开 CPU 后下一次如何继续运行因为 CPU 寄存器中的数据会随着程序执行不断变化所以进程切换时需要保存当前进程的执行现场并在下一次运行时恢复。这就是进程上下文切换的本质。第二个问题多个进程都想使用 CPU 时操作系统如何选择下一个进程经典 Linux O(1) 调度器通过优先级数组组织进程通过 Bitmap 快速查找最高优先级的非空队列再利用 Active Array 和 Expired Array 管理不同调度周期中的进程。当活跃队列为空时只需要交换两个队列的指针就能够快速开始下一轮调度。最后我们把整个过程串起来多个进程处于就绪状态 | v 进程调度 | v O(1) 调度器选择进程 | v 确定下一个进程 | v 上下文切换 | v 保存当前进程的现场 | v 恢复下一个进程的现场 | v CPU 运行 | v 时间片用完或阻塞 | v 再次调度最后还要补充一点O(1) 调度器是 Linux 历史上的经典调度器主要用于早期 Linux 2.6 内核。后来 Linux 引入了 CFS完全公平调度器而较新的 Linux 内核又逐步引入了 EEVDF 调度机制。因此我们今天学习 O(1) 调度算法主要是为了理解 Linux 调度器曾经如何利用数据结构优化进程选择过程以及优先级调度的底层思想。本篇结束下一篇继续学习 Linux 进程篇的相关知识