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

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

news 2025/10/19 17:30:25

深入解析：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）

核心逻辑：按进程进入就绪队列的“先后顺序”分配CPU，先到的进程先占用CPU，直到运行结束或因I/O阻塞才释放。
特点：构建最方便（仅需队列结构），但公平性差，易出现“长进程阻塞短进程”的convoy effect（护航效应）（例：一个需1小时的进程先进入队列，后续多个1分钟的短进程需等待1小时才能执行）。
适用场景：进程运行时间差异小、无实时需求的批处理任务（如后台数据备份）。

短作业优先（Shortest-Job-First, SJF）

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

优先级调度（Priority Scheduling）

核心逻辑：为每个进程分配一个“优先级”（数值越小优先级越高，或反之），优先选择优先级最高的就绪进程分配CPU，同样分为“非抢占式”和“抢占式”：
- 非抢占式：仅当前进程结束/阻塞时，才调度新的高优先级进程；
- 抢占式（也称“抢占式优先级调度”）：新进程优先级高于当前进程时，立即抢占CPU。
特点：可灵活适配业务需求（如给关键任务设高优先级），但存在饥饿问题（低优先级进程可能长期被高优先级进程抢占）；为缓解饥饿，引入“优先级老化”机制（进程等待时间越长，优先级自动提升）。
适用场景：需区分任务重要性的批处理或通用系统（如服务器中，数据库进程优先级高于普通日志进程）。

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

时间片轮转（Round-Robin, RR）

核心逻辑：将CPU时间划分为固定长度的“时间片”（如10ms），就绪进程按FCFS顺序排队，每个进程每次仅占用1个时间片；若时间片用完进程未结束，则放回队尾等待下一轮。
特点：公平性好（每个进程均能获得CPU时间），响应时间可控，是交互式系统的基础算法。
- 关键参数：时间片长度（过短会导致频繁“进程切换”，增加体系开销；过长会退化为FCFS，响应时间变长）。
适用场景：桌面操作系统（Windows、macOS）、多用户服务器（Linux）。

多级反馈队列（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）

核心逻辑：将系统资源（CPU时间）视为“共享资源”，按“用户或任务组”而非单个进程分配资源份额。例如，若系统中有2个用户，可设定每个用户获得50%的CPU时间；若用户A有10个进程，用户B有2个进程，则用户A的每个进程平均获得5%的时间，用户B的每个进程平均获得25%的时间。
特点：确保“用户/组”之间的资源分配公平，避免单个用户通过创建大量进程抢占资源。
适用场景：多用户共享框架（如服务器、云计算平台）。

彩票调度（Lottery Scheduling）

核心逻辑：经过“彩票”比喻达成公平性——系统为每个进程（或用户）分配一定数量的“彩票”，每次调度时随机抽取一张彩票，持有该彩票的进程获得CPU时间。进程拥有的彩票数量越多，被选中的概率越高。
特点一种概率性的公平调度策略，按比例分配资源。实现轻松，可通过调整彩票数量灵活改变进程优先级，且能在统计意义上保证长期公平性（彩票比例决定资源获取比例）。就是：
适用场景：多用户共享环境（如服务器、云平台）。

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

硬实时调度：速率单调调度（Rate-Monotonic Scheduling, RMS）

核心逻辑：针对“周期性硬实时任务”（如每10ms采集一次传感器材料），任务的“优先级与周期成反比”——周期越短（执行越频繁），优先级越高。
特点：静态优先级调度（编译期确定优先级，运行时不改变），可利用数学公式验证“任务集是否可调度”（确保所有任务在截止时间前完成）。前提条件为：
- 任务为周期性，且周期、执行时间、截止时间已知（截止时间=周期）；
- 任务无抢占开销，且不互相依赖。
适用场景：周期性硬实时系统（如嵌入式设备的传感器数据采集、工业机床控制）。

硬实时调度：截止时间最早优先（Earliest Deadline First, EDF）

核心逻辑：针对“周期性/非周期性硬实时任务”，优先选择“截止时间最早”的就绪进程分配CPU，属于“动态优先级调度”（优先级随截止时间动态变化）。
特点：调度灵活性高于RMS，可协助非周期性任务；同样可通过公式验证调度可行性，且在“任务负载不超过100%”时，能保证所有任务的截止时间。
适用场景：复杂硬实时系统（如自动驾驶的路径规划任务，截止时间随路况动态变化）。

软实时调度：加权公平队列（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系统）。

历史演进关键节点

1970s-1990s（早期Unix）：
- 核心算法：优先级调度（非抢占式）+短作业优先（SJF）；
- 设计特点：内核级进程（如IO守护进程）优先级高于用户进程，短进程优先调度减少批处理任务平均周转时间；
- 局限性：单进程可长期占用CPU，无抢占机制，交互响应差。
2001年（Linux 2.4内核）：
- 核心算法：O(1)调度器（固定优先级抢占式）；
- 改进目标：解决“调度延迟随进程数增长”挑战，调度决策时间复杂度降至O(1)；
- 设计特点：用两个固定数组（活跃/过期队列）存储进程，支持140个优先级（0-99为实时优先级，100-139为普通优先级），实时进程可抢占普通进程；
- 局限性：普通进程按“优先级+时间片”调度，多进程场景下公平性差（高优先级普通进程易抢占低优先级进程）。
2007年（Linux 2.6.23内核）：
- 核心算法：完全公平调度器（CFS）；
- 改进目标：处理多进程公平性问题，适配通用场景；
- 设计特点：摒弃固定时间片，引入vruntime和红黑树，动态分配CPU时间，成为后续Linux内核默认调度器。
2010年（Linux 2.6.33及以上内核）：
- 核心改进：CFS+RT_PREEMPT实时补丁；
- 改进目标：增强Linux实时性，支持硬实时任务；
- 设计特点：内核大部分代码拥护抢占，实时进程采用“优先级抢占调度”，普通进程仍用CFS，填补硬实时场景空白。

Windows 系统

当前主流CPU调度算法

核心策略：优先级抢占 + 多核负载均衡 + 能效调度混合策略（Windows 11默认）。
调度单位：以“线程”为调度单位，而非进程，更贴合桌面交互场景。
优先级机制：支持32个优先级（0-15为普通优先级，16-31为实时优先级），普通场景下优先保证UI线程（如桌面窗口、应用交互）响应速度。
多核优化：
- 处理器关联：将线程绑定到特定CPU核心，减少缓存失效，提升性能；
- 负载均衡：实时监控核心负载，将空闲核心分配给高负载线程，避免单核心过载。
能效优化：
- Core Parking（核心休眠）：低负载时关闭部分CPU核心（如笔记本仅启用2个核心），平衡性能与功耗；
- 能效优先级：新增“能效优先级”维度，后台更新等低重要性线程设为“低能效优先级”，优先使用空闲核心，不影响前台任务。
异构CPU适配：针对Intel大小核、AMD 3D V-Cache等异构CPU，将高负载任务（如视频剪辑、游戏）分配给大核/缓存密集核，轻任务（如文档编辑、通知）分配给小核，最大化硬件利用率。

历史演进关键节点

1995-2000年（Windows 95/98）：
- 核心算法：协作式多任务（无抢占）；
- 设计特点：依赖进程主动释放CPU（如调用Sleep()函数），无抢占机制；
- 局限性：单进程死循环会导致系统卡死，仅帮助单CPU，无多核调度能力，交互体验差（如打开大型软件时系统卡顿）。
2000-2001年（Windows NT/2000/XP）：
- 核心算法：抢占式优先级调度 + 时间片轮转；
- 改进目标：提升交互响应速度，帮助多任务并发；
- 设计特点：引入线程级调度，普通线程用“时间片轮转”（默认10-15ms），实时线程用“优先级抢占”（高优先级实时线程可抢占所有普通线程）；新增动态优先级调整（线程等待用户输入时，优先级临时提升）。
2006-2009年（Windows Vista/7）：
- 核心算法：多核负载均衡 + 动态时间片；
- 改进目标：适配多核CPU，优化调度效率；
- 设计特点：针对多核CPU设计“处理器关联”和“负载均衡”机制；时间片动态调整（高负载时缩短时间片提升响应，低负载时延长减少切换开销）。
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播放、直播等场景无卡顿。

历史演进关键节点

1984-2001年（经典Mac OS 9及之前）：
- 核心算法：协作式多任务；
- 设计特点：与Windows 9x类似，依赖进程主动释放CPU，无抢占机制；
- 局限性：仅支持单线程调度，无法利用多核CPU，多媒体任务（如视频播放）易卡顿。
2001年（Mac OS X 10.0）：
- 核心算法：Mach线程调度 + BSD抢占式；
- 改进目标：引入抢占机制，支持多线程与多核；
- 设计特点：以“Mach线程”为调度单位，支持抢占式调度（优先级0-127为普通优先级，128-255为实时优先级）；普通线程采用“基于优先级的时间片轮转”，借鉴MLFQ思想（高优先级线程时间片短，如UI线程5ms；低优先级线程时间片长，如后台任务20ms）；帮助“线程迁移”，优化缓存命中率。
2016年（macOS 10.12 Sierra）：
- 核心算法：能效调度 + 实时多媒体优先级；
- 改进目标：平衡笔记本续航与多媒体性能；
- 设计特点：引入“能效模式”，低负载时降低CPU频率，限制后台线程CPU占用（如邮件同步设为低优先级）；多媒体任务（视频渲染、音频处理）默认提升优先级，优化4K播放体验。
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最高），支持“优先级继承”（避免优先级反转，例：低优先级进程持有锁时，临时提升至请求锁的高优先级进程优先级）；
- 适用场景：车载系统（如自动驾驶的激光雷达数据处理，需硬实时保证）、医疗设备（如呼吸机控制）。