一、竞争、独立、并行、并发1.1 概念竞争性系统进程数目众多而 CPU 资源只有少量甚至 1 个所以进程之间是具有竞争属性的。为了高效完成任务更合理地竞争相关资源便有了优先级独立性多进程运行需要独享各种资源多进程运行期间互不干扰并行多个进程在多个 CPU 下分别同时进行运行这称之为并行并发多个进程在一个 CPU 下采用进程切换的方式在一段时间之内让多个进程都得以推进称之为并发。下面举例子来理解。1.2 喝咖啡并发Concurrent咖啡店只有一台咖啡机单核 CPU前排着两条顾客长龙。咖啡师只能给 A 队做一杯再转头给 B 队做一杯通过高频无缝切换让两条队伍同时缓慢推进。虽然微观上某一时刻只能服务一个人但宏观上两个队列都在向前推进。并行Parallel同一家咖啡店直接升级安装了两台一模一样的咖啡机多核 CPU。两位咖啡师各占一台机器同时在同一时刻为两位顾客制作咖啡。两个队伍在各自的物理设备上独立、同时推进互不干扰。怎么查看你的机器是单核还是多核指令cat/proc/cpuinfo二、基于时间片的分时操作系统早期的计算机采用的是单任务批处理系统一个程序不跑完后面的程序只能干等着。而现代 Linux 则是典型的分时操作系统。2.1 什么是时间片内核为了让多个进程看起来是在同时运行的会给运行队列中的每一个进程分配一段微小的 CPU 轮转执行时间这个极其短暂的时间区域就叫做时间片通常只有几毫秒到几十毫秒。2.2 时间片轮转机制的好处基于时间片轮转机制Linux 的多任务运行呈现出一种独特的运行景观微观串行在极短的几毫秒一个时间片内CPU 核心依然是严格单线程、串行地只执行某一个进程的指令宏观并行当一个进程的时间片耗尽操作系统会立刻剥夺其 CPU 使用权强行将其推回队列排队并把 CPU 切换给下一个进程这就是进程切换。因为时间片极短且切换频率极高在人类肉眼的宏观视觉下就造成了所有程序都在同时流畅运行的并行错觉。三、进程优先级的基本概念在多任务操作系统中CPU 的资源是有限的而需要运行的进程往往有很多。为了保证系统高效、有序地运行操作系统必须有一套机制来决定谁先运行谁后运行这就是进程优先级。3.1 为什么要有进程优先级进程优先级的存在本质是因为 CPU 资源是稀缺的。一个 CPU 核心在同一时刻只能处理一个进程的指令。当系统中有大量进程同时维持在运行R状态时它们就必须在运行队列中排队。优先级的高低实际上就是决定在排队等待时谁能够排在前面、谁能优先获得 CPU 的分配资源。3.2 区分优先级与权限很多初学者容易将优先级和权限搞混它们在操作系统中是完全不同的概念权限决定的是你能不能做某件事。例如普通用户能否读取 root 权限的文件优先级决定的是你先做还是后做某件事。它假设你已经具备了执行的权限只是在时间节点上进行排队。1. UIDUser ID在 Linux 内核中系统用来识别用户身份、划分进程归属的硬核判据并不是用户名这样的字符串而是一串数字 —— UIDUser ID用户标识符。内核对身份的数字化绑定每当一个用户在终端启动一个程序时内核在为其创建进程控制块task_struct时会将该用户的 UID 直接写入其中。这意味着系统中的每一个进程底层都有那个 UID 数字。UID 的划分规则0超级用户 root 的 UID 永远是 0最高权力1000现代 Linux 发行版中普通用户的 UID 通常从 1000 开始往后顺序累加如 1000、1001、1002……。如何查看 UID在终端输入ls -l命令输出结果中包含的 UID 列对应的数字代表的就是该文件的拥有者是谁。-n选项以数字形式返回。原本ll显示的是我们的用户名这个用户名是被包装的。那么回到我们的进程我们为什么要突然插入 UID 的概念访问一个文件是什么去访问进程去访问。进程访问文件时怎么知道自己有没有能力去访问 —— 看权限权限来自哪里来自 UID也就是用户。3.3 进程优先级的正面作用合理配置和动态调整进程优先级可以带来以下好处改善系统性能让关键的系统核心服务如中断处理、音视频流实时解码优先运行避免卡顿提升用户体验交互式进程如用户正在使用的窗口、鼠标键盘响应会被赋予更高的优先级使得系统反馈更加流畅、跟手。在 Linux 的 O(1) 调度算法等底层设计中优先级越高的进程往往会被系统分配到更长、更充裕的时间片而优先级较低的进程分配到的时间片则相对较短。四、查看修改优先级4.1 Linux 下查看进程优先级在 Linux 终端中我们可以通过输入ps -l或ps -al实际上得加上a选项命令来查看当前终端下进程的详细列表和硬核指标。输入命令后输出的头部字段通常包含以下信息[ljmiZ0jlgycwuno4vikja7kneZ day5]$ps-lF SUIDPIDPPIDC PRI NI ADDR SZ WCHAN TTY TIME CMD0S100013727137260800-28920do_wai pts/0 00:00:00bash0R100014101137270800-38338- pts/0 00:00:00ps4.2 PRI 与 NI在输出的众多列中我们需要重点关注两个与进程优先级直接相关的核心指标PRI 和 NI。PRIPriority进程优先级这是进程真正被 CPU 执行时的最终优先级指标。数字越小对应的优先级越高意味着越先被 CPU 执行NINice谦让值 / nice 值这是我们要手动或动态调整的修正数据。它表示进程的修改程度。Nice 值越小负数说明该进程竞争性越强想要抢占更多 CPU 资源从而拉低 PRINice 值越大正数说明它竞争性越弱愿意把资源让给别人。这样设计的好处修改优先级的时候不需要知道优先级历史上是多少。4.3 进程优先级的计算公式在 Linux 系统中进程最终的优先级 PRI 并不是一成不变的而是由系统基准值与 Nice 值共同叠加计算出来的。其核心计算公式如下PRI(最终)PRI(基准)NIPRI_{(最终)} PRI_{(基准)} NIPRI(最终)​PRI(基准)​NI基准值是多少在标准 Linux 内核中普通进程的默认基准优先级PRI(基准)PRI_{(基准)}PRI(基准)​通常固定为80。通过公式我们可以非常直观地看出 Nice 值是如何干预进程优先级的当NI0NI 0NI0时默认状态PRI(最终)80080PRI_{(最终)} 80 0 80PRI(最终)​80080当NI−10NI -10NI−10时竞争性越强PRI(最终)80(−10)70PRI_{(最终)} 80 (-10) 70PRI(最终)​80(−10)70此时数字变小优先级反而提升了当NI15NI 15NI15时竞争性越弱PRI(最终)801595PRI_{(最终)} 80 15 95PRI(最终)​801595此时数字变大优先级下降了。4.4 Nice 值的取值范围与限制原因1. Nice 值的取值范围为了防止某个进程无休止地调整 Nice 值从而彻底垄断或者搞崩溃系统Linux 内核对 Nice 值的取值作了极其严格的界定Nice 值的取值范围 [-20, 19]总共只有 40 个级别。这意味着无论你如何疯狂地尝试调小 Nice 值系统允许的最低 Nice 值就是 -20。最高优先级为 80 (-20) 60最低优先级为 80 19 99。2. 为什么要把 Nice 值的范围限制得这么小Linux 这样设计的根本目的是为了防止进程饥饿Process Starvation。操作系统必须要做到公平调度。如果允许用户无限度地拉高或降低进程优先级那么某些高优先级的恶意进程将会死死霸占住 CPU 资源导致其他普通的后台进程、系统维持进程永远分配不到 CPU 时间片这个概念在后面讲。长时间得不到 CPU 响应的进程就会在队列里饿死因此Nice 值必须被锁死在固定的区间内。4.5 优先级修改方法优先级可以调整不论是启动进程时还是进程运行中。1. nice 命令在启动进程时指定其初始 Nice 值nice 示例以较低优先级Nice 值为 10启动一个耗时的编译任务。nice-n10gcc myprocess.c-omyprocess注如果不指定-n参数nice 默认会把进程的 Nice 值设置为 102. renice 命令在进程运行时动态调整其 Nice 值renice 示例将一个正在运行的、PID 为 1234 的进程的 Nice 值调整为 5。renice-n5-p1234提高优先级需要 root 权限将 PID 为 1234 的进程 Nice 值降到 -5优先级更高。sudorenice-n-5-p12343. 通过 top 命令交互式修改了解即可进入控制台在终端输入top运行性能监视器触发修改机制在 top 界面中按下键盘上的r键进入 renice 调整模式选择进程 PID此时界面会弹出提示PID to renice [default pid 24300]缺省参数即为当前 top 列表中默认选中的 PID如提示中的 24300如果想修改特定进程手动输入目标进程 PID例如输入 25110并回车修改 Nice 值随后系统会提示Renice PID 25110 to value在此处输入你期望修改的全新 Nice 值范围通常为 -20 至 19并回车确认。五、进程切换与 CPU 寄存器原理5.1 死循环进程如何运行 —— 深入理解时间片在多任务操作系统中我们经常会遇到或写出死循环程序。一个不加限制的死循环进程是否会死死卡住 CPU导致整个系统瘫痪让其他进程动弹不得呢答案是绝对不会当我们的进程被加载到 CPU 并开始运行时它并不能无限期地独占 CPU 资源。现代操作系统如 Linux普遍采用时间片Time Slice轮转的调度机制单次运行受限一个进程在跑的时候跑完一个指定的时间片就必须得停下来重回队列排队被剥夺 CPU 使用权的进程会被操作系统重新放入运行队列的末尾进行排队等待下一次轮到它保护系统响应依靠这种高频的轮转切换即使某个进程内部是死循环操作系统也能保证其他进程获得 CPU 资源绝不会让其他进程卡死。5.2 CPU 寄存器当进程在 CPU 上运行时它需要执行大量的算术、逻辑运算以及内存访问。这就引出了操作系统中极其核心的概念 —— 寄存器。1. 寄存器的核心作用我们的 PCB 被加载进 CPU 后CPU 的控制器需要根据进程的执行状态去取得该进程所指向的代码和数据。临时存储的刚需CPU 从内存中取出来的、或者在运算过程中产生的各种高频变化的数据必须有一个极度高速的临时存储场所比内存还快于是寄存器诞生了寄存器的定义寄存器就是 CPU 内部的临时存储空间专门用来存储正在运行的进程的临时数据包括变量值、指令地址、状态标志等。2. 常见的核心寄存器分类不同的硬件架构如 x86、ARM以及不同的系统其寄存器的个数和具体类型会有所不同但通常都包含以下几类核心寄存器程序计数器PC / EIP存放 CPU 即将执行的下一条指令的内存地址栈指针寄存器EBP / ESP维护管理函数调用栈的边界与空间通用寄存器如 EAX、EBX、ECX、EDX / RAX……用于暂存各类运算过程中的操作数和临时结果段寄存器CS、DS、ES、SS、FG、GS在寻址时用于指示不同的内存段标志寄存器EFLAGS记录当前运算的状态信息如是否溢出、是否为负数、进位等控制寄存器CR0 ~ CR4决定 CPU 的工作模式以及控制虚拟内存分页等控制核心。六、进程上下文与切换机制进程的上下文就是进程在运行中产生的临时数据以及进程切换的时候我怎么知道我执行到哪个地方的代码了、变量的值是多少。6.1 例子假设你在大学读到大二突然想响应国家号召去当兵去当兵进程被剥夺 CPU你必须暂时离开学校保留学籍保存上下文离开前导员把你大一和大二的所有期末成绩、学分等信息打包塞进档案袋存入学校的教务系统。这就是把 CPU 寄存器里面的临时数据保存起来的过程退役复学重新获得 CPU两年后你当兵回来了想要继续读大三恢复学籍恢复上下文导员从档案袋里调出你当年的成绩单重新同步到当前的教学系统中你才能无缝衔接大三的课程而不是从大一重头读起。这就是把保存的数据重新恢复到 CPU 寄存器里的过程。一次上下文的保存与恢复就对应着一次进程的切换。6.2 进程 A 与进程 B 的交替运行机制进程 A 运行满一个时间片此时 CPU 寄存器如 EIP 100 行EAX 10存满了 A 的临时数据。操作系统介入将这些硬件上下文数据保存一份清单到 A 专属的存储区域随后 A 带着它的数据回到运行队列中排队。进程 B 开始执行B 进驻 CPU覆盖硬件寄存器并在其时间片内运行。B 运行满一个时间片后同样把自己的硬件上下文保存一份清单回队列排队。进程 A 再次被调度操作系统把 A 刚才记录在清单中的数据重新写入/恢复到 CPU 对应的寄存器当中。此时CPU 的 EIP 重新变回 100 行EAX 重新变回 10。A 就能完美地从历史位置和状态继续向下运行由此周而复始。6.3 上下文存在哪里在早期的 Linux 内核例如初代 Linux 内核源码设计中硬件上下文是依赖特定的硬件数据结构 TSS任务状态段来管理的// 早期 Linux 内核中关于任务状态段的结构定义structtss_struct{longback_link;longesp0,ss0;longesp1,ss1;longesp2,ss2;longcr3;longeip;// 进程下一条指令位置的寄存器数据longeflags;// 保存标志位longeax,ecx,edx,ebx;// 保存通用寄存器数据longesp,ebp;longesi,edi;longes,cs,ss,ds;// ...};在初代内核中每个进程的struct task_structPCB内部包含了一个struct tss_struct或者包含了一个可以获取该硬件上下文的钥匙指针/段选择子通过它去 TSS 中获取或写入对应的硬件上下文内容现代内核的演进在新版本的 Linux 内核中为了追求更高的切换效率和架构平台的可移植性这种强依赖硬件 TSS 的机制已经被剥离和优化转而直接在内核栈Kernel Stack或task_struct的特定字段如thread_struct中通过轻量级汇编指令进行手动保存。6.4 全新进程 vs 已调度过的进程在整个切换生命周期中调度器需要面对两种形态的进程已经调度过的进程之前运行过其中途断点和寄存器数据已经保存在 PCB 或内核栈中再次调度时直接走恢复上下文流程全新进程刚被 fork 出来从来没有在 CPU 上运行过。为了让调度器不至于接手一个全新进程时手忙脚乱操作系统在设计 PCB 时通常会引入一个状态标记structtask_struct{/* ... 各种进程相关信息 ... */longstate;// -1 unrunnable, 0 runnable, 0 stoppedintis_running;// 状态标记位是否属于已经运行过的进程// ...};首次调度对于全新进程操作系统在 fork 创建它时会在内核栈里为它手动伪造一个初始的上下文环境例如把它的 EIP 指向进程的入口函数 main把相关寄存器清零或赋初值统一调度逻辑这样一来全新进程在第一次被调度时就能假装自己是一个被切走过的老进程同样通过统一的恢复上下文代码顺利跑起来。6.5 分时操作系统与实时操作系统我们上述讨论的时间片轮转切换主要适用于我们日常接触的分时操作系统Time-sharing OS如 Linux、Windows、macOS。它的核心目标是公平与高并发吞吐让每个用户、每个进程感觉自己都在独占计算机。但在某些特定领域如智能驾驶汽车的刹车控制、航天飞机引导、工业自动化生产流水线等则必须使用实时操作系统RTOSReal-Time OS。实时性的本质实时操作系统不强调绝对的时间片公平轮转它强调的是任务响应的确定性。如果一个高优先级紧急任务如自动驾驶发现障碍物需要紧急制动到达即使前面的进程的时间片没到系统也必须在微秒级内完成强行上下文切换绝对不能允许排队等待。七、O(1) 调度算法与调度队列如上是整个调度队列的简化示意图我们接下来慢慢来了解它。7.1 进程调度的核心诉求与优先级数组当系统中存在大量处于就绪状态的进程时调度器面临的核心问题是下一次该把 CPU 分配给谁为了满足不同进程对响应速度的差异化需求Linux 引入了优先级的概念。在底层的实现中内核并没有采用单一的无序链表而是设计了优先级数组。例如内核会维护一个指针数组如task_struct *queue[140]数组的下标直接对应着进程的优先级0-139。每一个数组元素都是一个链表的头指针挂载着所有该优先级下的就绪进程。这也就是为什么优先级可调节范围是 -20 到 19刚刚好 40 个7.2 优先级映射方法实时进程优先级范围0 ~ 99数值越小优先级越高映射规则这部分进程的优先级直接原样映射到多级就绪队列的 0 ~ 99 下标位置。普通进程优先级范围100 ~ 139由 nice 值动态计算而来nice 值与优先级转换普通进程的 nice 值范围是 -20 到 19内核通过120 nice将其转换为 100 ~ 139 的纯数字优先级。7.3 查找下一个进程从 O(N) 遍历到位图优化有了优先级队列当我们想要挑选下一个最高优先级的进程来运行时就需要去查找这个队列数组中哪一个是第一个非空的队列。这就是经典 Linux 调度算法如 O(1) 调度器必须攻克的核心性能关。假设我们有一个简化的优先级队列数组int queue[140];以及一个用于指向当前查找位置的变量int index;。如果按照最朴素的思维我们怎么找最直接的办法就是写一个 for 循环按顺序去遍历这个数组。致命的性能瓶颈如果我们的队列长度不是 100而是 100010000这种时间复杂度为 O(N) 的线性查找在操作系统底层是绝对无法容忍的。因为进程调度极其频繁如果每次挑选进程都要经历漫长的遍历系统性能将受到严重拖累。为了打破 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) 查找时间复杂度。7.4 活跃队列与过期队列活跃队列和过期队列都放在一个数组里面。即使解决了查找效率问题传统的单队列模型还会遇到一个问题高优先级的进程如果不断产生低优先级的进程就会遭遇饥饿永远分不到时间片。为了解决这个问题经典 O(1) 调度算法在运行队列runqueue中引入了两个核心的队列集合。1. 活跃队列Active Array这里面存放的是当前时间片还没有用完的进程。调度器每次都从活跃队列的最高优先级链表中取出一个进程投入运行。当这个进程在 CPU 上跑完它的时间片后它就失去了继续待在活跃队列的资格。2. 过期队列Expired Array当活跃队列中的某个进程耗尽了时间片调度器会为它重新计算下一次的优先级和时间片然后将其直接放入过期队列中。3. 指针交换随着时间推移活跃队列里的进程越来越少最终会被清空使用一个nr_active来记录进程数量为 0 时交换指针。此时过期队列里则装满了重新洗牌后等待运行的进程。当活跃队列为空的瞬间调度器不需要做任何复杂的数据搬移操作只需要互换一下活跃队列和过期队列的两个指针曾经的过期队列瞬间变成了新的活跃队列曾经空掉的活跃队列变成了新的过期队列。7.5 总结上一个进程的时间片结束系统会先通过nr_active查看当前进程数量数量 0 则调用 bitmap 查找下一个进程的所在位置调取 queue 找到进程位置然后将头部的结点取出将它的 PCB 链接到 current 指针指向current 指针将其指向的进程加载到 CPU 中使用调度算法CPU 开始运行。设计这一套算法的人真是天才。7.6 调度队列其他元素了解cpu_load CPU负载因子:主要服务于多CPU并发的情况一个新进程来的时候首先要通过cpu_load查看多个CPU的负载状态找到负载低的那CPU插入。nr_switches 切换次数:衡量一个CPU有多忙的一个指标