当前位置: 首页 > news >正文

深入解析:CPU调度算法简记

文章目录

      • 批处理系统调度算法:面向 “无交互” 的长任务,追求高吞吐量
        • 先来先服务(First-Come, First-Served, FCFS)
        • 短作业优先(Shortest-Job-First, SJF)
        • 优先级调度(Priority Scheduling)
      • 交互式系统调度算法:面向“用户交互”任务,追求短响应时间
        • 时间片轮转(Round-Robin, RR)
        • 多级反馈队列(Multilevel Feedback Queue, MLFQ)
        • 公平共享调度(Fair-Share Scheduling)
        • 彩票调度(Lottery Scheduling)
      • 实时系统调度算法:面向“实时任务”,追求绝对时间保证
        • 硬实时调度:速率单调调度(Rate-Monotonic Scheduling, RMS)
        • 硬实时调度:截止时间最早优先(Earliest Deadline First, EDF)
        • 软实时调度:加权公平队列(Weighted Fair Queueing, WFQ)
      • Unix/Linux 系统
        • 当前主流CPU调度算法
        • 历史演进关键节点
      • Windows 框架
        • 当前主流CPU调度算法
        • 历史演进关键节点
      • macOS 平台
        • 当前主流CPU调度算法
        • 历史演进关键节点
      • 其他代表性操作系统
        • 移动端操作系统
        • 嵌入式实时系统
        • 轻量桌面/服务器系统

批处理系统调度算法:面向 “无交互” 的长任务,追求高吞吐量

先来先服务(First-Come, First-Served, FCFS)
短作业优先(Shortest-Job-First, SJF)
  • 核心逻辑:优先选择“预计运行时间最短”的就绪进程分配CPU,分为“非抢占式”和“抢占式”两种:
    • 非抢占式SJF:一旦进程开始运行,必须执行到结束或阻塞,不被中途打断;
    • 抢占式SJF(也称“最短剩余时间优先”SRTF):若新进入就绪队列的进程预计运行时间短于当前运行进程的剩余时间,则立即抢占CPU。
  • 特点:理论上能最小化“平均周转时间”(进程从提交到完成的总时间),但存在两个关键问题:
    • “饥饿问题”:若短进程持续进入队列,长进程可能永远无法获得CPU;
    • 前提依赖:需“提前知道进程的预计运行时间”(实际场景中难以完全满足,需通过历史数据估算)。
  • 适用场景:可预估进程运行时间、无实时需求的批处理系统(如编译任务队列)。
优先级调度(Priority Scheduling)

交互式系统调度算法:面向“用户交互”任务,追求短响应时间

时间片轮转(Round-Robin, RR)
多级反馈队列(Multilevel Feedback Queue, MLFQ)
  • 核心逻辑:结合“时间片轮转”和“优先级调度”,是最复杂也最贴近实际的调度算法,核心设计如下:
    1. 设立多个优先级不同的就绪队列(队列1优先级最高,队列n最低),每个队列的时间片长度不同(优先级越高,时间片越短,例:队列1时间片10ms,队列2 20ms,队列3 40ms);
    2. 新进程先进入最高优先级队列,按RR算法调度;若时间片用完未结束,降级到下一级队列;
    3. 低优先级队列中的进程仅在高优先级队列为空时才被调度;
    4. 为缓解饥饿,低优先级队列中的进程若等待时间过长(如1分钟),自动升级到高优先级队列。
  • 特点:兼顾“短进程快速响应”(高优先级短时间片)和“长进程不被饿死”(升级机制),适配不同类型的交互式任务。
    • 多级队列​(Multilevel Queue):之前的一种简化版本。它将就绪队列划分为多个独立的队列(如:​​环境进程队列​​、​​交互式进程队列​​、​​批处理进程队列​​等),每个队列拥有自己的调度算法(如前台队列用RR,后台队列用FCFS),但是进程不能在队列之间移动。
  • 适用场景:通用操作系统(如Linux、Windows的内核调度器均借鉴了MLFQ思想)。
公平共享调度(Fair-Share Scheduling)
彩票调度(Lottery Scheduling)
  • 核心逻辑:经过“彩票”比喻达成公平性——系统为每个进程(或用户)分配一定数量的“彩票”,每次调度时随机抽取一张彩票,持有该彩票的进程获得CPU时间。进程拥有的彩票数量越多,被选中的概率越高。
  • 特点一种概率性的公平调度策略,按比例分配资源。实现轻松,可通过调整彩票数量灵活改变进程优先级,且能在统计意义上保证长期公平性(彩票比例决定资源获取比例)。就是:
  • 适用场景:多用户共享环境(如服务器、云平台)。

实时系统调度算法:面向“实时任务”,追求绝对时间保证

硬实时调度:速率单调调度(Rate-Monotonic Scheduling, RMS)
  • 核心逻辑:针对“周期性硬实时任务”(如每10ms采集一次传感器材料),任务的“优先级与周期成反比”——周期越短(执行越频繁),优先级越高。
  • 特点:静态优先级调度(编译期确定优先级,运行时不改变),可利用数学公式验证“任务集是否可调度”(确保所有任务在截止时间前完成)。前提条件为:
    • 任务为周期性,且周期、执行时间、截止时间已知(截止时间=周期);
    • 任务无抢占开销,且不互相依赖。
  • 适用场景:周期性硬实时系统(如嵌入式设备的传感器数据采集、工业机床控制)。
硬实时调度:截止时间最早优先(Earliest Deadline First, EDF)
软实时调度:加权公平队列(Weighted Fair Queueing, WFQ)
  • 核心逻辑:针对“软实时任务”(允许偶尔错过截止时间,但需尽量减少),为每个任务分配一个“权重”,CPU时间按权重比例分配(权重越高,获得的CPU时间越多)。
  • 特点:兼顾公平性和实时性,不严格保证截止时间,但能让高权重的实时任务获得更多CPU资源。
  • 适用场景:软实时系统(如视频流媒体播放、VoIP通话,偶尔卡顿可接受)。

Unix/Linux 环境

当前主流CPU调度算法
  • 核心调度器:完全公平调度器(CFS),为Linux 5.x及以上内核默认调度器。
  • 核心思想:基于“公平共享调度”思想,确保每个进程获得公平的CPU时间份额,通过“红黑树”维护进程的“虚拟运行时间(vruntime)”。
  • 调度逻辑:每次选择vruntime最小的进程执行,进程运行时vruntime按比例增长(优先级越高,增长越慢,获得更多CPU资源),无固定时间片,动态调整进程运行时长。
  • 调度类机制:承受多调度类灵活切换,适配不同任务场景:
    • SCHED_FAIR:普通进程调度类,默认使用CFS,保证多进程公平性;
    • SCHED_RR:实时轮转调度类,适用于低延迟需求任务(如数据库进程),按时间片轮转分配CPU;
    • SCHED_FIFO:实时先进先出调度类,高优先级实时任务独占CPU,直到完成或主动释放,适用于硬实时场景(需配合RT_PREEMPT补丁)。
  • 实时性支持:默认CFS不支持硬实时,利用“RT_PREEMPT实时补丁”将内核大部分代码改为可抢占(仅保留临界区不可抢占),实时进程最高优先级为100,协助工业控制、自动驾驶等硬实时场景(如Ubuntu RT、Debian RT系统)。
历史演进关键节点
  1. 1970s-1990s(早期Unix)
    • 核心算法:优先级调度(非抢占式)+短作业优先(SJF);
    • 设计特点:内核级进程(如IO守护进程)优先级高于用户进程,短进程优先调度减少批处理任务平均周转时间;
    • 局限性:单进程可长期占用CPU,无抢占机制,交互响应差。
  2. 2001年(Linux 2.4内核)
    • 核心算法:O(1)调度器(固定优先级抢占式);
    • 改进目标:解决“调度延迟随进程数增长”挑战,调度决策时间复杂度降至O(1);
    • 设计特点:用两个固定数组(活跃/过期队列)存储进程,支持140个优先级(0-99为实时优先级,100-139为普通优先级),实时进程可抢占普通进程;
    • 局限性:普通进程按“优先级+时间片”调度,多进程场景下公平性差(高优先级普通进程易抢占低优先级进程)。
  3. 2007年(Linux 2.6.23内核)
    • 核心算法:完全公平调度器(CFS);
    • 改进目标:处理多进程公平性问题,适配通用场景;
    • 设计特点:摒弃固定时间片,引入vruntime和红黑树,动态分配CPU时间,成为后续Linux内核默认调度器。
  4. 2010年(Linux 2.6.33及以上内核)
    • 核心改进:CFS+RT_PREEMPT实时补丁;
    • 改进目标:增强Linux实时性,支持硬实时任务;
    • 设计特点:内核大部分代码拥护抢占,实时进程采用“优先级抢占调度”,普通进程仍用CFS,填补硬实时场景空白。

Windows 系统

当前主流CPU调度算法
历史演进关键节点
  1. 1995-2000年(Windows 95/98)
    • 核心算法:协作式多任务(无抢占);
    • 设计特点:依赖进程主动释放CPU(如调用Sleep()函数),无抢占机制;
    • 局限性:单进程死循环会导致系统卡死,仅帮助单CPU,无多核调度能力,交互体验差(如打开大型软件时系统卡顿)。
  2. 2000-2001年(Windows NT/2000/XP)
    • 核心算法:抢占式优先级调度 + 时间片轮转;
    • 改进目标:提升交互响应速度,帮助多任务并发;
    • 设计特点:引入线程级调度,普通线程用“时间片轮转”(默认10-15ms),实时线程用“优先级抢占”(高优先级实时线程可抢占所有普通线程);新增动态优先级调整(线程等待用户输入时,优先级临时提升)。
  3. 2006-2009年(Windows Vista/7)
    • 核心算法:多核负载均衡 + 动态时间片;
    • 改进目标:适配多核CPU,优化调度效率;
    • 设计特点:针对多核CPU设计“处理器关联”和“负载均衡”机制;时间片动态调整(高负载时缩短时间片提升响应,低负载时延长减少切换开销)。
  4. 2015-2021年(Windows 10/11)
    • 核心算法:核心Parking + 能效优先调度;
    • 改进目标:平衡性能与能效,适配移动设备(如笔记本、二合一设备);
    • 设计特点:引入核心休眠技术,细分能效优先级,优化异构CPU调度,成为当前主流策略基础。

macOS 系统

当前主流CPU调度算法
  • 内核基础:基于“XNU混合内核”,融合BSD进程管理与Mach线程调度,macOS 14(Sonoma)为最新主流版本。
  • 核心策略:异构核调度(大核+小核)+ 能效优先,适配Apple Silicon芯片(如M1/M2/M3系列)。
  • 异构核分配逻辑
    • 性能核(P-core,大核):分配高负载任务,如视频剪辑(Final Cut Pro)、编程编译(Xcode)、3D渲染等,保证高算力输出;
    • 能效核(E-core,小核):分配轻负载任务,如桌面通知、邮件同步、文档编辑(Pages)等,降低功耗,延长续航。
  • 动态任务迁移:实时监控线程负载,动态调整任务核心归属(如打开大型文件时,先由小核启动加载,负载升高后自动迁移到大核,兼顾启动速度与运行性能)。
  • 辅助优化技能
    • 进程冻结:长时间后台进程(如未活跃的浏览器标签页)暂停CPU占用,仅保留内存素材,恢复时迅速唤醒;
    • 多媒体优先级:视频播放、音频处理(如Logic Pro编曲)线程默认提升优先级,保证4K播放、直播等场景无卡顿。
历史演进关键节点
  1. 1984-2001年(经典Mac OS 9及之前)
    • 核心算法:协作式多任务;
    • 设计特点:与Windows 9x类似,依赖进程主动释放CPU,无抢占机制;
    • 局限性:仅支持单线程调度,无法利用多核CPU,多媒体任务(如视频播放)易卡顿。
  2. 2001年(Mac OS X 10.0)
    • 核心算法:Mach线程调度 + BSD抢占式;
    • 改进目标:引入抢占机制,支持多线程与多核;
    • 设计特点:以“Mach线程”为调度单位,支持抢占式调度(优先级0-127为普通优先级,128-255为实时优先级);普通线程采用“基于优先级的时间片轮转”,借鉴MLFQ思想(高优先级线程时间片短,如UI线程5ms;低优先级线程时间片长,如后台任务20ms);帮助“线程迁移”,优化缓存命中率。
  3. 2016年(macOS 10.12 Sierra)
    • 核心算法:能效调度 + 实时多媒体优先级;
    • 改进目标:平衡笔记本续航与多媒体性能;
    • 设计特点:引入“能效模式”,低负载时降低CPU频率,限制后台线程CPU占用(如邮件同步设为低优先级);多媒体任务(视频渲染、音频处理)默认提升优先级,优化4K播放体验。
  4. 2020年(macOS 11 Big Sur)
    • 核心算法:异构核调度(大核+小核);
    • 改进目标:适配Apple Silicon芯片(M1系列),最大化异构硬件性能;
    • 设计特点:针对4大核+4小核架构,设计智能核心分配策略,动态迁移任务,成为当前macOS调度算法的核心框架。

其他代表性操作系统

移动端操作系统
嵌入式实时环境
  • VxWorks(Wind River):硬实时操作系统的代表,默认采用“优先级抢占式调度”,支持RMS(速率单调)和EDF(截止时间最早优先)算法:

    • 核心设计:优先级0-255(0最高),实时任务采用“立即抢占”(高优先级任务就绪时,10us内抢占当前CPU);
    • 适用场景:工业机床、航天器控制(如火星探测器的姿态调整任务,需毫秒级响应)。
  • QNX(BlackBerry):分布式实时系统,采用“微内核+优先级抢占调度”:

    • 调度逻辑:以“进程”为单位,优先级1-63(1最高),支持“优先级继承”(避免优先级反转,例:低优先级进程持有锁时,临时提升至请求锁的高优先级进程优先级);
    • 适用场景:车载系统(如自动驾驶的激光雷达数据处理,需硬实时保证)、医疗设备(如呼吸机控制)。
轻量桌面/服务器系统
http://www.hskmm.com/?act=detail&tid=34401

相关文章:

  • 2025年TYPE-C母座厂家推荐排行榜,防水/板上/沉板/立插/立贴/侧插/立式/插座/接口/插头/5A大电流/高速/TID认证公司精选
  • 在AI技术唾手可得的时代,挖掘用户真实需求成为制胜关键——某知名系统工具需求探索
  • 2025年通风气楼/通风天窗厂家推荐排行榜,圆拱型/电动/一字型/钢结构/流线型/屋顶自然/三角型/排烟/采光/启闭式/薄型/成品/消防联动/工厂/屋面/开敞式/启闭式排烟/通风设备公司推荐!
  • 科技领域导师制度与因果分析方法解析
  • 比赛与好题记录(2025 9-10)
  • 全面详解 C++std::vector用法指南
  • Visual Studio Code 初步配置指南(Windows端)
  • 2025年UV光源厂家推荐排行榜,UV面光源,UV LED点光源,UV LED面光源,UV LED固化机公司精选
  • 课上积极回答加分
  • 022304105叶骋恺数据采集第一次作业
  • 智能预加载:基于用户行为和路由预测
  • 函数简单传入参数的汇编分析 - 指南
  • 数据类型转换以及内存溢出
  • 美股数据接口对接指南:快速获取指数实时行情
  • 25-deepin-linux-wsl-nginx-installation
  • 2025国际冷链运输推荐腾翼搏时,专业温控保障生物药品安全!
  • 鸿蒙设备开发-gpio控制
  • AI Agent和Agentic AI
  • http基础
  • Java基础语法与面向对象
  • Java中java.util.Random的用法
  • 2025年磨粉机厂家推荐排行榜,雷蒙磨粉机,环辊磨粉机,摆式磨粉机,矿石磨粉机,超微磨粉机,高压磨粉机公司推荐!
  • 我的学习开始及历程
  • 2025信息流代运营推荐:线尚网络精准投放,效果显著!
  • 零售行业绩效流程推行难点及 Tita 目标绩效一体化管理方案
  • Godot-C#处理节点关系
  • 软件工程-结队项目
  • 2025 年防撞钢护栏厂家推荐聊城市泰锌金属材料有限公司,桥梁,不锈钢,复合管,景观,灯光,热镀锌,河道,铝合金,绳索防撞钢护栏公司推荐
  • 2025年聚氨酯制品厂家推荐排行榜,浇注型聚氨酯,聚氨酯预聚体,聚氨酯胶黏剂,聚氨酯组合料,液体聚氨酯,专业品质与创新技术之选
  • Vue中keep-alive实现原理解析