文档教程知识库【免费下载链接】CS-Base图解计算机网络、操作系统、计算机组成、数据库共 1000 张图 50 万字破除晦涩难懂的计算机基础知识让天下没有难懂的八股文 在线阅读https://xiaolincoding.com项目地址https://gitcode.com/GitHub_Trending/cs/CS-Base点击查看免费下载导读操作系统是计算机系统的大管家而调度算法就是这位管家分配 CPU、内存和磁盘资源的核心策略。本文基于 CS-Base小林图解计算机基础仓库中 《进程调度/页面置换/磁盘调度算法》 一文系统梳理操作系统的三大调度机制——进程调度、页面置换与磁盘调度并结合仓库内进程与线程基础、虚拟内存、内存回收、磁盘存储等配套章节深入剖析其底层原理。读完本文你将掌握六大进程调度算法、五种页面置换算法和五种磁盘调度算法的核心思想、适用场景与相互优劣足以应对校招/社招中关于操作系统调度的高频面试题。一、总览操作系统的三大调度机制操作系统的调度贯穿于 CPU、内存、磁盘三大资源的管理之中对应三大类算法调度类别调度对象核心目标典型场景进程调度CPU 调度就绪队列中的进程公平高效地分配 CPU 时间多任务操作系统页面置换内存调度物理内存中的页面尽可能减少换入换出次数虚拟内存管理磁盘调度磁盘 I/O 请求队列减少寻道时间机械磁盘读写这三者有一个共同点都是在资源有限、请求众多的情况下决定下一个该服务谁。理解了这一点再看具体算法时就会事半功倍。二、进程调度算法把 CPU 时间公平地分出去2.1 什么是进程调度何时触发调度进程调度算法也称CPU 调度算法。当 CPU 空闲时操作系统会从内存中选择某个「就绪状态」的进程为其分配 CPU。在进程、线程基础知识中我们知道进程在运行态、就绪态、阻塞态之间不断变迁每一次状态变迁都可能触发一次调度。通常CPU 调度发生在以下四种情况进程从运行状态转到等待状态进程从运行状态转到就绪状态进程从等待状态转到就绪状态进程从运行状态转到终止状态。其中情况 1 和 4 属于非抢占式调度进程运行直到完成或被阻塞才让出 CPU情况 2 和 3 属于抢占式调度进程运行过程中可以被打断把 CPU 让给其他进程。抢占的原则一般有三种时间片原则、优先权原则、短作业优先原则。为什么等待状态转到就绪状态也会触发调度假设一个高优先级进程等待的事件发生了它转入就绪状态如果调度算法按优先级调度它就会立即抢占正在运行的进程。而运行态转到就绪态典型就是时间片到——时间片耗尽触发中断抢占当前进程。这就是 CPU 调度的本质在进程状态变迁的瞬间决定 CPU 的归属。调度算法影响的是等待时间进程在就绪队列中等待调度的时间总和而不能影响进程真正使用 CPU 的时间和 I/O 时间——这是理解各类调度算法效果的前提。2.2 调度原则好调度算法的评判标准在进程与线程基础的调度原则一节中给出了五种核心评判维度CPU 利用率调度程序应确保 CPU 始终忙碌提高利用率系统吞吐量单位时间内 CPU 完成的进程数量短作业能提升吞吐量长作业会拉低它周转时间进程运行时间 阻塞时间 等待时间的总和越小越好等待时间进程处于就绪队列的时间注意不是阻塞时间等待越久用户体验越差响应时间用户提交请求到系统第一次产生响应所花费的时间交互式系统中尤为重要。一句话总结这么多原则目的就是让进程执行得更快。不同的调度算法正是对这些原则的权衡取舍。2.3 六大经典进程调度算法① 先来先服务调度算法FCFS先来先服务First Come First Served, FCFS是最简单的非抢占式调度算法每次从就绪队列选择最先进入队列的进程一直运行直到进程退出或被阻塞才继续选择队列中下一个进程。优点实现简单、公平缺点当一个长作业先运行时后面所有短作业都要长时间等待适用性对长作业有利适用于CPU 繁忙型作业的系统不适用于I/O 繁忙型作业的系统。② 最短作业优先调度算法SJF最短作业优先Shortest Job First, SJF优先选择运行时间最短的进程运行有助于提高系统吞吐量。优点吞吐量高缺点对长作业极不友好——如果一个长作业在就绪队列中等待而队列里不断涌入短作业长作业会被不断往后推周转时间越来越长甚至长期得不到运行造成饥饿。③ 高响应比优先调度算法HRRNFCFS 和 SJF 都没有很好权衡长短作业高响应比优先Highest Response Ratio Next, HRRN对此做了折中。每次调度时先计算每个进程的「响应比优先级」把响应比最高的进程投入运行响应比 (等待时间 要求的服务时间) / 要求的服务时间从公式可以推导出两个性质两个进程等待时间相同时要求的服务时间越短响应比越高 → 短作业容易被选中吸收 SJF 优点两个进程要求的服务时间相同时等待时间越长响应比越高 → 长作业随着等待时间增加响应比不断升高最终获得运行机会避免饥饿。注意该算法需要预知进程要求的服务时间而现实中这一信息不可预估因此 HRRN 属于理想型算法现实中难以实现。④ 时间片轮转调度算法RR时间片轮转Round Robin, RR是最古老、最简单、最公平且使用最广的算法。每个进程被分配一个时间段时间片 Quantum在该时间段内运行时间片用完进程还在运行 → 从 CPU 释放分配给下一个进程进程在时间片结束前阻塞或结束 → CPU 立即切换。时间片长度是关键参数太短进程上下文切换过于频繁降低 CPU 效率太长短作业的响应时间变长退化为 FCFS折中值通常设为20ms ~ 50ms。⑤ 最高优先级调度算法HPF时间片轮转假设所有进程同等重要但多用户系统希望调度有优先级。最高优先级Highest Priority First, HPF从就绪队列中选择最高优先级的进程运行。进程优先级分为两类静态优先级创建进程时就确定运行期间不变动态优先级随进程状态动态调整如运行时间增加则降低优先级等待时间就绪队列等待增加则升高优先级——随着时间的推移提高等待进程的优先级。HPF 有两种实现方式非抢占式当前进程运行完后再选择高优先级进程抢占式高优先级进程一出现立即挂起当前进程去运行它。致命缺点可能导致低优先级进程永远得不到运行饥饿。动态优先级可以部分缓解该问题。⑥ 多级反馈队列调度算法MFQ多级反馈队列Multilevel Feedback Queue是时间片轮转与最高优先级算法的综合与发展多级设置多个队列队列优先级从高到低同时优先级越高时间片越短反馈新进程进入高优先级队列时立刻停止当前运行进程转去运行高优先级队列中的进程。具体工作流程新进程放入第一级队列末尾按 FCFS 原则排队等待调度若在第一级队列规定的时间片内未运行完成转入第二级队列末尾以此类推直至完成只有较高优先级队列为空时才调度较低优先级队列中的进程若进程运行时有新进程进入高优先级队列则停止当前进程并将其移入原队列末尾让出 CPU。效果短作业在第一级队列即可快速完成长作业逐级下沉虽然等待时间变长但每级运行的时间片也变长了。因此 MFQ兼顾长短作业且有较好的响应时间是综合最均衡的进程调度算法。三、内存页面置换算法缺页时的换人决策3.1 前置知识缺页异常缺页中断当 CPU 访问的页面不在物理内存时会产生缺页中断请求操作系统把所缺页面调入物理内存。它与一般中断有两个关键区别缺页中断在指令执行期间产生和处理中断信号一般中断在指令执行完成后才检查和处理缺页中断返回后重新执行该指令一般中断返回后执行下一条指令。缺页中断的处理流程6 步CPU 执行 Load M 指令查找 M 对应的页表项若页表项状态位有效直接访问物理内存若无效CPU 发送缺页中断请求操作系统执行缺页中断处理函数先在磁盘上查找该页面的位置在物理内存中找空闲页找到则把页面换入物理内存换入完成后把页表项状态位修改为有效CPU 重新执行导致缺页异常的指令。如果第 4 步找不到空闲页内存已满就需要页面置换算法来选择一个物理页换出若该页被修改过脏页先换出到磁盘并把被置换页的页表项状态位改为无效再把正在访问的页面装入该物理页。3.2 页表项的关键字段理解页面置换算法前先弄清页表项通常包含的字段详见虚拟内存中对页表与多级页表的讲解字段作用状态位表示该页是否有效是否在物理内存中供程序访问时参考访问字段记录该页在一段时间内被访问的次数供页面置换算法选择置换页面时参考修改位表示该页调入内存后是否被修改过。内存中每页在磁盘上都有副本未修改则置换时无需写回磁盘减少开销已修改则必须重写磁盘以保持最新副本硬盘地址指出该页在硬盘上的地址通常为物理块号供调入页面时使用页面置换算法的功能是当出现缺页异常、需调入新页面而内存已满时选择被置换的物理页面。其算法目标是尽可能减少页面的换入换出次数。3.3 五种经典页面置换算法以下算法讲解沿用原文档的经典示例3 个空闲物理页请求页面序列为7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1该序列常用于教材对比各类算法表现。① 最佳页面置换算法OPT基本思路置换在未来最长时间不访问的页面。实现需要计算内存中每个逻辑页面的下一次访问时间选择未来最长时间不被访问的页面。在示例序列中缺页共发生7次空闲页换入 3 次 最优页面置换 4 次页面置换发生4次——这是所有算法中的理论下限。局限实际系统中程序访问页面是动态的无法预知每个页面下一次访问前的等待时间因此 OPT无法实现。它的价值在于作为衡量其他算法效率的基准——你的算法缺页次数越接近 OPT说明越高效。② 先进先出置换算法FIFO既然无法预知未来就选择在内存中驻留时间最长的页面进行置换——这就是先进先出First In First Out思想。示例序列下FIFO 缺页发生10次页面置换7次明显劣于 OPT。补充知识点FIFO 还存在著名的Belady 异常——在某些访问序列下增大物理页框数反而导致缺页次数增加这在 LRU 等栈式算法中不会出现。③ 最近最久未使用置换算法LRU基本思路发生缺页时选择最长时间没有被访问的页面置换即假设很久没用的页面未来很长一段时间内仍不会被使用。LRU 与 OPT 的对比很有意思OPT 用未来推测LRU 用历史推测因此 LRU 是 OPT 的近似。示例序列下LRU 缺页发生9次页面置换6次优于 FIFO。代价完全实现 LRU 需要在内存中维护所有页面的链表最近最多使用的在表头最少使用的在表尾每次访问内存都要更新整个链表——查找、删除、移动到表头都是非常费时的操作。因此 LRU 虽然理论上可行、效果不错但实际应用中较少直接使用。值得一提在 Linux 内核的内存回收中见内存满了会发生什么LRU 思想被工程化为active / inactive 两个双向链表的近似实现越靠近链表尾部表示越不常访问回收时优先回收不活跃页面——这正是 LRU 在真实系统中的落地形态。④ 时钟页面置换算法Clock能否找到一种既能优化置换次数又方便实现的算法时钟页面置换算法Clock就是这样的两全之选它近似 LRU又是对 FIFO 的改进。算法思路把所有页面保存在一个类似钟面的环形链表中表针指向最老的页面。发生缺页中断时检查表针指向的页面若其访问位为 0淘汰该页面把新页面插入这个位置表针前移一个位置若其访问位为 1清除访问位表针前移重复此过程直到找到访问位为 0 的页面。因为表针像时钟指针一样在环形链表上转动该算法因此得名时钟算法。它通过访问位来记住页面最近是否被访问过既避免了 FIFO 的机械又不像 LRU 那样维护全量链表实现成本低、效果好是实际操作系统中最常使用的页面置换算法。⑤ 最不常用置换算法LFU最不常用Least Frequently Used, LFU发生缺页中断时选择访问次数最少的页面淘汰。实现方式是为每个页面设置一个访问计数器每访问一次累加 1缺页时淘汰计数器值最小的页面。LFU 看似简单但落地面临两个问题硬件成本高每个页面都要增加计数器查找访问次数最小的页面需要遍历链表链表很长时非常耗时只考虑频率、不考虑时间某些页面过去访问频率很高但现在已不活跃而当前正在频繁访问但累计次数还不高的页面反而可能被误伤淘汰。解决方案定期衰减访问次数——例如在时间中断发生时把过去时间访问页面的计数除以 2。这样随着时间流逝以前的高频页面计数慢慢降低被置换的概率相应增大让 LFU 能记住最近而非只记住曾经。四、磁盘调度算法让磁头少跑冤枉路4.1 磁盘结构与寻道成本在磁盘比内存慢几万倍一文中我们了解到机械硬盘的随机访问延迟高达 10 毫秒比 CPU L1 Cache 慢千万倍是存储层次中最慢的一层。这种慢主要源于寻道——磁头移动到目标磁道的时间。机械磁盘结构要点中间为盘片一般有多个每个盘面有独立磁头盘片每层分为多个磁道每个磁道分为多个扇区每个扇区512字节多个相同编号的磁道形成一个柱面。磁盘调度算法的目的通过优化磁盘访问请求的顺序减少不必要的寻道时间提高磁盘访问性能。下文所有算法基于同一个示例请求序列98, 183, 37, 122, 14, 124, 65, 67数字代表磁道位置磁头初始位置在第53磁道。4.2 五种经典磁盘调度算法① 先来先服务FCFS先到来的请求先被服务按98 → 183 → 37 → 122 → 14 → 124 → 65 → 67顺序移动。磁头总共移动640个磁道。算法简单粗暴但当大量进程竞争使用磁盘、请求磁道分布很分散时寻道时间过长性能很差。② 最短寻道时间优先SSF优先选择从当前磁头位置所需寻道时间最短的请求。从 53 磁道出发服务顺序为65 → 67 → 37 → 14 → 98 → 122 → 124 → 183。磁头移动总距离236磁道相比 FCFS 性能大幅提升。致命缺陷——饥饿若后续动态请求都集中在磁头当前所在的小区域如都在 183 以下则 183 磁道的请求可能永远不被响应。饥饿的根源是磁头在一小块区域来回移动而眼下的最优未必是全局的最优。③ 扫描算法Scan电梯算法为解决 SSF 的饥饿问题规定磁头沿一个方向移动访问该方向上所有未完成请求直到到达该方向最后的磁道才调换方向——这就是扫描算法也叫电梯算法电梯保持一个方向移动直到该方向没有请求才改变方向。假设先朝磁道号减小的方向移动服务顺序为37 → 14 → 0 → 65 → 67 → 98 → 122 → 124 → 183先响应左侧请求直到最左端 0 磁道再反向响应右侧请求。优点性能较好不会产生饥饿缺点中间部分磁道比较占便宜——磁头每次往返都经过中间区域导致每个磁道的响应频率存在差异。④ 循环扫描算法C-SCAN为消除 Scan 的中间占便宜问题规定总是按相同方向扫描使每个磁道响应频率基本一致只有磁头朝某个特定方向移动时才处理请求返回时直接快速移动至最靠边缘的磁道复位磁头返回途中不处理任何请求。假设先朝磁道增加的方向移动服务顺序为65 → 67 → 98 → 122 → 124 → 183 → 199 → 0 → 14 → 37磁头碰到最右端 199 磁道后立即回到磁道 0返回途中不响应任何请求。相比扫描算法C-SCAN 对各个位置磁道的响应频率相对平均。⑤ LOOK 与 C-LOOK 算法Scan 和 C-SCAN 的共同点是磁头都要移动到磁盘的最始端或最末端才调换方向。这其实可以优化——磁头只移动到最远的请求位置就立即反向。LOOK 算法对 Scan 的优化每个方向上只移动到最远请求位置就反向反向途中会响应请求C-LOOK 算法对 C-SCAN 的优化每个方向上只移动到最远请求位置就反向反向途中不会响应请求。两者省去了往返磁盘边界的无效行程在请求未覆盖全盘的情况下能显著减少磁头移动距离。五、三大调度机制横向对比与面试要点5.1 算法速查表类别算法核心思想关键弱点实际应用进程调度FCFS先来先服务短作业等待过长CPU 繁忙型系统进程调度SJF优先最短作业长作业饥饿理论/批处理进程调度HRRN响应比最高优先需预知服务时间理想型理论进程调度RR时间片轮转时间片设置两难通用、使用最广进程调度HPF最高优先级优先低优先级饥饿多用户系统进程调度MFQ多队列时间片反馈参数调优复杂现代通用 OS 广泛采用页面置换OPT置换未来最久不访问的页无法实现仅作基准理论基准页面置换FIFO置换驻留最久的页可能触发 Belady 异常简单场景页面置换LRU置换最久未访问的页维护链表开销大近似实现Linux active/inactive 链表页面置换Clock环形链表访问位近似 LRU 仍有误差实际 OS 最常用页面置换LFU置换访问次数最少的页硬件成本高、忽视时间维度需配合计数衰减磁盘调度FCFS按请求到达顺序寻道距离大请求较少时磁盘调度SSF优先最近磁道边缘磁道饥饿请求较集中时磁盘调度Scan单向扫描到边界中间磁道响应频率高传统 OS磁盘调度C-SCAN单向循环扫描仍需扫到边界现代 OS 改进磁盘调度LOOK / C-LOOK到最远请求即反向——现代 OS 常用5.2 面试高频追问抢占式与非抢占式调度怎么区分关键看进程运行中能否被打断FCFS 是非抢占RR 靠时钟中断实现抢占HPF 可按抢占/非抢占实现。LRU 与 OPT 的区别OPT 看未来理论最优、不可实现LRU 看历史近似实现。Clock 算法为何叫 Clock页面组织成环形链表表针像时钟指针一样转动靠访问位的 0/1 决定淘汰与放行。SSF 为什么会饥饿磁头总在小区域来回移动远离该区域如大磁道号的请求永远轮不到。Scan 与 C-SCAN 的差异Scan 往返都响应请求中间磁道受益多C-SCAN 只单方向响应、返回时快速复位各磁道响应频率更均匀。MFQ 为什么综合最优短作业在高优先级队列快速完成长作业逐级下沉获得更大时间片兼顾吞吐量与响应时间。六、结语调度算法的学习路径调度算法是操作系统资源分配思想的集中体现三类算法表面不同内核相通——都是在约束条件下做取舍进程调度在公平与效率间取舍页面置换在命中率与实现开销间取舍磁盘调度在寻道距离与公平性间取舍。想进一步巩固这部分知识建议在 CS-Base 仓库中按以下顺序阅读配套章节进程状态、PCB、上下文切换与调度时机进程、线程基础知识虚拟内存、分页与页表结构为什么要有虚拟内存LRU 在真实内核中的落地active/inactive 链表与内存回收流程内存满了会发生什么机械磁盘的物理结构与性能差距磁盘比内存慢几万倍。操作系统是计算机系统的大管家而调度算法就是这位管家分配 CPU、内存和磁盘资源的三大核心策略。把这三大调度机制吃透你对操作系统资源管理的理解将上升一个台阶。赞分享文档教程知识库【免费下载链接】CS-Base图解计算机网络、操作系统、计算机组成、数据库共 1000 张图 50 万字破除晦涩难懂的计算机基础知识让天下没有难懂的八股文 在线阅读https://xiaolincoding.com项目地址https://gitcode.com/GitHub_Trending/cs/CS-Base点击查看免费下载相关推荐CS-Notes 计算机操作系统笔记磁盘结构与磁盘调度算法FCFS / SSTF / SCAN详解CS Notes 计算机操作系统笔记磁盘结构与磁盘调度算法FCFS / SSTF / SCAN详解 本文是 CS Notes 仓库「计算机操作系统」系列中知识库文档教程CS-Notes 操作系统进程管理详解进程、线程、调度算法、同步机制与 IPC 全解析CS Notes 操作系统进程管理详解进程、线程、调度算法、同步机制与 IPC 全解析 进程管理是操作系统五大部分进程管理、内存管理、文件管理、设备管理、处知识库文档教程操作系统调度算法实现CS-Xmind-Note笔记代码解析操作系统调度算法实现CS Xmind Note笔记代码解析 你是否还在为理解操作系统调度算法而烦恼是否在面对优先级调度、轮转调度等多种算法时感到无从下手本文档教程知识库上一篇knowledge-catalog 的 Stack Overflow posts_answers 表完全指南BigQuery 公共数据集中的回答结构、Schema 与查询分析下一篇5分钟快速上手ElasticJobSpringBoot整合分布式定时任务完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考