目录一、 进程切换与 CPU 寄存器原理1.1 死循环进程如何运行——深入理解时间片1.1.1 现代操作系统的公平调度1.2 聊聊 CPU 寄存器与临时数据1.2.1 寄存器的诞生背景与核心作用1.2.2 常见的核心寄存器分类1.3 核心结论区分“空间”与“内容”1.3.1 寄存器盒子 / 空间1.3.2 寄存器里面的数据内容 / 答案二、 进程上下文与切换机制2.1 什么是进程上下文Process Context2.1.1 进程上下文的核心组成2.2 进程切换的“当兵留籍”故事2.2.1 角色映射表2.2.2 一次完整的切换流程2.3 硬件上下文的具体保存与恢复实现2.3.1 进程 A 与进程 B 的交替运行机制2.4 内核源码审视上下文存在哪里2.4.1 任务状态段TSS, Task State Segment与 task_struct2.4.2 内核中的current指针2.5 衍生思考全新进程 vs 已调度过的进程2.5.1 如何区分2.6 补充分时操作系统与实时操作系统三、O1调度算法与调度队列3.1 进程调度的核心诉求与优先级数组3.1.1优先级映射方法3.2 查找下一个进程从 O(N) 遍历到位图优化3.2.1 传统的顺序遍历困境3.2.2 性能破局引出位图技术3.3 活跃队列与过期队列3.3.1 活跃队列Active Array3.3.2 过期队列Expired Array3.3.3指针交换3.3.4完整梳理3.4周边问题3.4.1新进程来了怎么办3.4.2调度队列其他元素了解3.4.3优先级与调度算法的关系一、 进程切换与 CPU 寄存器原理1.1 死循环进程如何运行——深入理解时间片在多任务操作系统中我们经常会遇到或写出“死循环”程序。一个不加限制的死循环进程是否会死死卡住 CPU导致整个系统瘫痪让其他进程动弹不得呢答案是绝对不会1.1.1 现代操作系统的公平调度当我们的进程被加载到 CPU 并开始运行时它并不能无限期地独占 CPU 资源。现代操作系统如 Linux普遍采用**时间片Time Slice**轮转的调度机制单次运行受限一个进程在跑的时候跑完一个指定的时间片就必须得停下来。重回队列排队被剥夺 CPU 使用权的进程会被操作系统重新放入运行队列的末尾进行排队等待下一次轮到它。保护系统响应依靠这种高频的轮转切换即使某个进程内部是死循环操作系统也能保证其他进程获得 CPU 资源绝不会让其他进程卡死。1.2 聊聊 CPU 寄存器与临时数据当进程在 CPU 上运行时它需要执行大量的算术、逻辑运算以及内存访问。这就引出了操作系统中极其核心的概念——寄存器。1.2.1 寄存器的诞生背景与核心作用我们的 PCB被加载进 CPU 后CPU 的控制器需要根据进程的执行状态去取得该进程所指向的代码和数据。临时存储的刚需CPU 从内存中取出来的、或者在运算过程中产生的各种高频变化的数据必须有一个极度高速的临时存储场所于是寄存器诞生了。寄存器的定义寄存器就是CPU 内部的临时存储空间专门用来存储正在运行的进程的临时数据包括变量值、指令地址、状态标志等。1.2.2 常见的核心寄存器分类不同的硬件架构如 x86、ARM以及不同的系统其寄存器的个数和具体类型会有所不同但通常都包含以下几类核心寄存器程序计数器PC / EIP存放 CPU 即将执行的下一条指令的内存地址。栈指针寄存器EBP / ESP维护管理函数调用栈的边界与空间。通用寄存器如 EAX, EBX, ECX, EDX / RAX…用于暂存各类运算过程中的操作数和临时结果。段寄存器CS, DS, ES, SS, FG, GS在寻址时用于指示不同的内存段。标志寄存器EFLAGS记录当前运算的状态信息如是否溢出、是否为负数、进位等。控制寄存器CR0 ~ CR4决定 CPU 的工作模式以及控制虚拟内存分页等控制核心。1.3 核心结论区分“空间”与“内容”为了彻底理解后续的“进程上下文切换”我们需要厘清一个极其关键的认知误区核心结论寄存器 ≠ 寄存器里面的数据1.3.1 寄存器盒子 / 空间寄存器本身是固化在 CPU 内部的硬件电路。物理空间的唯一性对于一个单核 CPU 而言其内部的寄存器硬件只有1 份。概念类比它就像是办公桌上的一个“固定的公用文件盒”。1.3.2 寄存器里面的数据内容 / 答案寄存器内部填充的数值是随着当前运行的进程不断发生剧烈变化的。数据的多份与流动虽然盒子寄存器只有一份但每一个进程在运行到某一行代码时它往盒子里塞进去的“账单数据”是变化的、多份的。示例代码说明int a 10; // 此时寄存器中临时存入 10 a 20; // 寄存器中的数据被刷新覆盖为 20 b a; // 从寄存器中读取 20 赋给 b当进程 A 的时间片到了被切走进程 B 进来运行时B 就会覆盖这个“文件盒”里的内容。因此在进程切换时如何安全地保护和恢复这唯一的“文件盒”里的多份临时数据就是我们下一部分要深入探讨的上下文切换Context Switch机制。二、 进程上下文与切换机制2.1 什么是进程上下文Process Context当一个进程在分时操作系统中运行、暂退、再恢复时操作系统必须确保它能无缝衔接。这就需要引入进程上下文的概念。从逻辑层面来看它描述的是一个进程执行时所需的整个环境。2.1.1 进程上下文的核心组成一个完整的进程上下文主要由以下三个层次构成用户级上下文包含进程的虚拟地址空间环境如代码段、数据段、用户栈以及共享内存等。寄存器级上下文硬件上下文即 CPU 内部各个寄存器PC, EFLAGS, ESP, 通用寄存器等在某一瞬间的特定数值。这部分直接决定了 CPU 当前的运行状态。系统级上下文操作系统为了管理该进程而维护的各种内核数据包括进程控制块PCB/task_struct、页表、打开的文件描述符表、内核栈以及信号处理状态等。作用进程上下文的存在保证了进程在被重新调度时不仅 CPU 状态寄存器能完全恢复连同内存映射、文件访问权限和内核资源等都能退回到中断发生前的那一瞬间。2.2 进程切换的“当兵留籍”故事为了生动地理解进程是如何切换的我们可以听一个通俗易懂的故事。2.2.1 角色映射表学校→CPU提供学习和运行的场所导员辅导员→调度器决定谁来、谁走、什么时候走你→进程在学校里接受培养的主体学籍 / 成绩单→硬件上下文数据你在学校某一时刻的所有表现和状态记录即寄存器里的内容2.2.2 一次完整的切换流程假设你在大学读到大二突然想响应国家号召去当兵去当兵进程被剥夺 CPU你必须暂时离开学校。保留学籍保存上下文离开前导员把你大一和大二的所有期末成绩、学分等信息打包塞进档案袋存入学校的教务系统。这就是把 CPU 寄存器里面的临时数据保存起来的过程。退役复学重新获得 CPU两年后你当兵回来了想要继续读大三。恢复学籍恢复上下文导员从档案袋里调出你当年的成绩单重新同步到当前的教学系统中你才能无缝衔接大三的课程而不是从大一重头读起。这就是把保存的数据重新恢复到 CPU 寄存器里的过程。核心结论一次硬件上下文的保存与恢复就对应着一次进程的切换。2.3 硬件上下文的具体保存与恢复实现在具体的工程实现中多进程如进程 A 和进程 B的轮转正是通过高频的“清音留存”来实现的。2.3.1 进程 A 与进程 B 的交替运行机制进程 A 运行满一个时间片此时 CPU 寄存器如EIP 100行,EAX 10存满了 A 的临时数据。操作系统介入将这些硬件上下文数据保存一份清单到 A 专属的存储区域随后 A 带着它的数据回到运行队列中排队。进程 B 开始执行B 进驻 CPU覆盖硬件寄存器并在其时间片内运行。B 运行满一个时间片后同样把自己的硬件上下文保存一份清单回队列排队。进程 A 再次被调度操作系统把 A 刚才记录在清单中的数据重新写入/恢复到 CPU 对应的寄存器当中。此时CPU 的EIP重新变回100行EAX重新变回10。A 就能完美地从历史位置和状态继续向下运行由此周而复始。2.4 内核源码审视上下文存在哪里那么当前运行进程的硬件上下文在被切走时究竟脱水保存到了哪里呢2.4.1 任务状态段TSS, Task State Segment与 task_struct在早期的Linux 内核例如初代 Linux 内核源码设计中硬件上下文是依赖特定的硬件数据结构TSS任务状态段来管理的// 早期 Linux 内核中关于任务状态段的结构定义 struct tss_struct { long back_link; long esp0, ss0; long esp1, ss1; long esp2, ss2; long cr3; long eip; // 报错 A 进程断点指令位置的寄存器数据 long eflags; // 保存标志位 long eax, ecx, edx, ebx; // 保存通用寄存器数据 long esp, ebp; long esi, edi; long es, cs, ss, ds; // ... };钥匙与保险箱在初代内核中每个进程的struct task_structPCB内部包含了一个struct tss_struct或者包含了一个可以获取该硬件上下文的“钥匙”指针/段选择子通过它去 TSS 中获取或写入对应的硬件上下文内容。现代内核的演进在新版本的 Linux 内核中为了追求更高的切换效率和架构平台的可移植性这种强依赖硬件 TSS 的机制已经被剥离和优化转而直接在内核栈Kernel Stack或task_struct的特定字段如thread_struct中通过轻量级汇编指令进行手动保存。2.4.2 内核中的current指针在 Linux 内核源码如sched.h中有一个非常高频使用的全局/宏变量extern struct task_struct *current; // 当前进程结构指针变量这个指针永远指向当前正占有 CPU 运行的那个进程的 PCB。当调度器决定切换进程时就是以current指针指向的进程作为源头把当前寄存器里的值打包抽离出来的。2.5 衍生思考全新进程 vs 已调度过的进程在整个切换生命周期中调度器需要面对两种形态的进程已经调度过的进程之前运行过其中途断点和寄存器数据已经保存在 PCB 或内核栈中再次调度时直接走“恢复上下文”流程。全新进程刚被fork出来从来没有在 CPU 上运行过。2.5.1 如何区分为了让调度器不至于接手一个全新进程时手忙脚乱操作系统在设计 PCB 时通常会引入一个状态标记struct task_struct { /* ... 各种硬编码的进程信息 ... */ long state; // -1 unrunnable, 0 runnable, 0 stopped int is_running; // 状态标记位是否属于已经运行过的进程 // ... };首次调度的伪装对于全新进程操作系统在fork创建它时会在内核栈里为它手动伪造一个初始的上下文环境例如把它的EIP指向进程的入口函数main把相关寄存器清零或赋初值。统一调度逻辑这样一来全新进程在第一次被调度时就能假装自己是一个“被切走过的老进程”同样通过统一的“恢复上下文”代码顺利跑起来2.6 补充分时操作系统与实时操作系统我们上述讨论的时间片轮转切换主要适用于我们日常接触的分时操作系统Time-sharing OS如 Linux、Windows、macOS。它的核心目标是公平与高并发吞吐让每个用户、每个进程感觉自己都在独占计算机。但在某些特定领域如智能驾驶汽车的刹车控制、航天飞机引导、工业自动化生产流水线等则必须使用实时操作系统RTOS, Real-Time OS。实时性的本质实时操作系统不强调绝对的“时间片公平轮转”它强调的是任务响应的确定性与极限死线。如果一个高优先级紧急任务如自动驾驶发现障碍物需要紧急制动到达即使当前进程的时间片没到系统也必须在微秒级内完成强行上下文切换绝对不能允许排队等待。大部分操作系统都支持实时操作系统但是这一部分在非应用领域基本用不到所以一般在编译的时候会被注释掉。三、O1调度算法与调度队列如上是整一个调度队列的简化示意图我们接下来慢慢来了解它。3.1 进程调度的核心诉求与优先级数组当系统中存在大量处于就绪状态的进程时调度器面临的核心问题是下一次该把 CPU 分配给谁为了满足不同进程对响应速度的差异化需求Linux 引入了优先级的概念。在底层的实现中内核并没有采用单一的无序链表而是设计了优先级数组。例如内核会维护一个指针数组如task_struct *queue[140]数组的下标直接对应着进程的优先级0-139。每一个数组元素都是一个链表的头指针挂载着所有该优先级下的就绪进程。3.1.1优先级映射方法实时进程优先级范围0 ~ 99数值越小优先级越高。映射规则这部分进程的优先级直接原样映射到多级就绪队列的 0 ~ 99 下标位置。普通进程优先级范围100 ~ 139由经典的 nice 值动态计算而来。nice 值与优先级转换普通进程的 nice 值范围是-20 到 19。内核通过以下公式将其转换为 100 ~ 139 的纯数字优先级PriorityNice120映射规则计算出来的优先级别数值同样直接对应多级就绪队列中 100 ~ 139 的数组下标。3.2 查找下一个进程从 O(N) 遍历到位图优化有了优先级队列当我们想要挑选下一个最高优先级的进程来运行时就需要去查找这个队列数组中哪一个是第一个非空的队列。这就是经典 Linux 调度算法如 O(1) 调度器必须攻克的核心性能关。3.2.1 传统的顺序遍历困境假设我们有一个简化的优先级队列数组int queue[100];以及一个用于指向当前查找位置的变量int index;。如果按照最朴素的思维我们怎么找最直接的办法就是写一个 for 循环按顺序去遍历这个数组。致命的性能瓶颈如果我们的队列长度不是 100而是100010000这种时间复杂度为 O(N) 的线性查找在操作系统底层是绝对无法容忍的。因为进程调度极其频繁如果每次挑选进程都要经历漫长的遍历系统性能将受到严重拖累。3.2.2 性能破局引出位图技术为了打破 O(N) 的魔咒实现 O(1) 的超高效率Linux 内核**引出了位图Bitmap**结构来辅助查找。位图的映射原理系统使用一段连续的比特位bit来映射对应的队列是否为空。例如使用一个长整型数组long bitmap[5];在 32 位系统中5 * 32 160 个 bit足以覆盖 140 个优先级队列。0 与 1 的状态如果第 0 个队列有进程排队那么位图的第 0 个 bit 就被置为1如果队列为空对应 bit 就是0。硬件级指令查找如果想找 1 对应的队列呢现代 CPU 都提供了专门的硬件指令如 x86 的bsf / bsr指令可以在一个 CPU 时钟周期内直接计算出一个整数中最低位或最高位的1在哪里。借助这种硬件指令操作系统瞬间就能知道哪个优先级队列里有进程实现了真正的 O(1) 查找时间复杂度3.3 活跃队列与过期队列活跃队列和过期队列都放在一个数组里面。即使解决了查找效率问题传统的单队列模型还会遇到一个问题高优先级的进程如果不断产生低优先级的进程就会遭遇饥饿永远分不到时间片。为了解决这个问题经典 O(1) 调度算法在运行队列runqueue中引入了两个核心的队列集合3.3.1 活跃队列Active Array这里面存放的是当前时间片还没有用完的进程。调度器每次都从活跃队列的最高优先级链表中取出一个进程投入运行。当这个进程在 CPU 上跑完它的时间片后它就失去了继续待在活跃队列的资格。3.3.2 过期队列Expired Array当活跃队列中的某个进程耗尽了时间片调度器会为它重新计算下一次的优先级和时间片然后将其直接放入过期队列中。3.3.3指针交换随着时间推移活跃队列里的进程越来越少最终会被清空。使用一个nr_active来记录进程数量为0时交换指针此时过期队列里则装满了重新洗牌后等待运行的进程。当活跃队列为空的瞬间调度器不需要做任何复杂的数据搬移操作只需要互换一下活跃队列和过期队列的两个指针曾经的过期队列瞬间变成了新的活跃队列。曾经空掉的活跃队列变成了新的过期队列。3.3.4完整梳理上一个进程的时间片结束系统会先通过nr_active查看当前进程数量数量0.则调用bitmap查找下一个进程的所在位置。调取queue找到进程位置然后将头部的结点取出。将它的PCB链接到current指针指向。 current指针将其指向的进程加载到CPU中使用调度算法。CPU开始运行3.4周边问题3.4.1新进程来了怎么办古人的做法将新进程链接到过期队列里面这个时候就是操作系统宏观的就绪状态。但是Linux没有分的这么明确活跃队列和过期队列都是运行队列。但是现代的一些做法进程支持抢占就是说把新的进程按照优先级插入到活跃队列中抢占了活跃队列中后面进程的时间。除此之外对于新进程还有很多的设计方案可以了解。3.4.2调度队列其他元素了解cpu_load CPU负载因子:主要服务于多CPU并发的情况一个新进程来的时候首先要通过cpu_load查看多个CPU的负载状态找到负载低的那CPU插入。nr_switches 切换次数衡量一个CPU有多忙的一个指标3.4.3优先级与调度算法的关系回来看我们之前留下的问题为什么修改优先级不直接在PRI上修改而要加上一个NI值我们下面的A队列默认是指活跃队列D队列默认是过期队列如果直接修改PRI会遇到两个问题把这个进程的优先级修改了如果在A队列中就要在这个队列中重新链入到指定位置。那么到底是A队列的指定位置还是D队列的指定位置我们不知道但是不论是A还是D都不好。那么不链入呢又又点奇怪我的优先级是60但是我在80的位置。于是加入了NI值我们修改优先级就是修改NI的值这个进程的NI值被修改了于是这一轮我把这个进程运行完之后在链入D队列中的时候把这个进程按照这个NI值重新定位到新的位置接下运行进程的时候就以新的优先级运行。