408 知识网络

调度算法演进 FCFS → SJF → HRRN → 优先级 → RR → 多级反馈队列

操作系统

所属模块:OS-1/2 进程、线程与 CPU 调度 · 本模块第 8 / 16 个概念

在「OS-1/2 进程、线程与 CPU 调度」概念体系中的位置

flowchart TD
    A["程序并发失去封闭性<br/>结果不可再现"] --> B["引入进程<br/>= 程序 + 数据 + PCB"]
    B --> C["PCB:进程存在的唯一标志<br/>常驻内存内核区"]
    B --> D["进程状态转换<br/>就绪 / 运行 / 阻塞"]
    B --> E["进程切换开销大<br/>换地址空间 + 更新页表基址"]
    E --> F["引入线程<br/>= CPU 调度的基本单位"]
    D --> G["多个就绪者抢 CPU<br/>→ 调度问题"]
    F --> G
    G --> H["调度算法演进<br/>FCFS → SJF → HRRN → 优先级 → RR → 多级反馈队列"]

核心概念:

概念 要点 易考点
PCB 记录 PID、状态、PC、寄存器、调度信息、页表基址、打开文件表等;进程存在的唯一标志,常驻内存内核区 创建进程:申请空白 PCB + 初始化,但不会直接设为执行态(2021 年 24 题)
进程 vs 程序 程序是静态指令集合;进程是动态执行过程,有生命周期 并发使程序失去封闭性与可再现性,这是引入进程的原因
进程状态 就绪(万事俱备只欠 CPU)、运行、阻塞(等事件,有 CPU 也没用 阻塞→运行不能直达,必须经就绪;就绪→阻塞无此方向(来源:复习资料 P3 §2.1)
线程 进程内的一条执行流;同进程线程共享地址空间、代码、数据、打开文件,不共享栈与寄存器 2011-25(栈指针)、2024-28(Ta/Tb 共享地址空间和 fd,不共享 T 的栈)
用户级 vs 内核级线程 用户级:线程库管理、切换快、内核无感知(无独立 TCB 于内核);内核级:OS 调度、可并行、阻塞一个不影响其他 2019-23:“OS 为每个用户级线程建立线程控制块”是错误
上下文切换 保存/恢复 PC、寄存器、PSW、栈指针;进程级切换还要换页表基址寄存器(PDBR,存物理地址) 进程切换改 PDBR,同进程线程切换不改(2018-44 考点)
调度层次 作业调度(高级)/ 内存调度(中级)/ 进程调度(低级) 408 重点是进程调度
调度指标 周转 = 完成 − 到达;带权周转 = 周转 / 运行;等待 = 周转 − 运行 大题三件套,先画甘特图再列表