操作系统第三章讲义 | Richard Liu’s Blog

type

Post

slug

OS_Ch3

status

Published

date

Apr 24, 2026

summary

3.1 处理机调度的层次和调度算法的目标

💡

什么是调度？

调度的本质：分配资源

资源是什么？ 处理机（CPU）的使用时间。

谁来分？ 操作系统。

分配给谁？ 内存里排队等着的各个任务（进程/作业）。

因为 CPU 有限，但任务有很多。所以需要一套运行的规则，这就是调度。

3.1.1 处理机调度层次

因为计算机的架构所限，计算机硬件资源的速度极不匹配，且内存容量有限。所以单靠单一的调度策略很难顾全大局。

这时候就必须对每一层级进行分工调度，协调好“慢速的磁盘”、“金子做的内存”和“极速的CPU”。

高级调度——作业调度

中级调度——内存调度

低级调度——进程调度

如果没有多级调度

没有高级调度会“撑死”： 内存撑爆，系统崩溃。

没有中级调度会“饿死”： 小任务等不到响应，长任务霸占资源。

没有低级调度会“急死”： 电脑变得极其不灵活，开个网页可能要把后台所有程序都关掉才行。

3.1.2 处理机调度算法的目标

💡

核心目标：尽量减少处理机的闲置。

1. 高资源利用率

——别让CPU偷懒。

应使系统中的处理机和其它所有资源都尽可能地保持忙碌状态。

计算处理机利用率：

2. 公平性

——别让老实人等死。

调度算法需要使各进程都要获得合理的CPU时间。

不能厚此薄彼，不能因为进程小就不给其分配资源。

不能发生饥饿现象。

💡

饥饿现象

如果一个算法总是让优先级高的先跑，那么一个优先级低的进程可能等了 3 天还没跑上 1 秒钟，这就叫“饥饿”。

公平是相对的

同类等同： 如果都是普通的文档编辑程序，大家拿到的 CPU 时间应该差不多。
异类区别： 视频播放器（实时性要求高）和后台杀毒软件（不急）相比，系统会优先照顾视频播放器，这虽然“不平等”，但在逻辑上是“公平”的。

3. 平衡性

——别让厨师闲着，也别让洗碗机闲着。

💡

进程的分类

计算型作业 (CPU-bound)： 狂算数字，CPU 很累，但不怎么用硬盘/网络。

I/O 型作业 (I/O-bound)： 频繁读写硬盘、收发网络包，CPU 很闲，但外部设备很忙。

调度算法要把这两种作业混合搭配，平衡CPU和IO设备的使用情况。

理想状态： CPU、硬盘、网卡都在同时工作，系统资源利用率达到最高。

4. 策略强制执行

——规矩大过天。

就像医院急诊室，规定“抢救病人第一优先”。哪怕普通感冒患者已经等了 2 小时，只要来了一个心梗病人，医生必须立刻去抢救心梗病人。

操作系统设定好的规则，调度算法必须无条件准确执行。

即使可能会导致某些普通任务被推迟、延误，但为了系统的安全性、稳定性，必须严格执行预设策略。

3.1.3. 系统的目标

操作系统历史上有三种系统：

批处理系统

分时系统

实时系统

批处理系统的目标

批处理系统通常用于大型计算任务，它不强调人机交互，而是强调“干活的效率”。

1. 平均周转时间短

周转时间——衡量系统快慢最基本的指标

定义：从你把作业提交给系统开始，到系统帮你把活干完输出结果为止，这段总时间。

平均周转时间：

带权周转时间——衡量小任务是否被大任务压住了。

定义为：周转时间 / 实际运行时间。

平均带权周转时间：

衡量一组作业的整体等待体验，值越接近 1 说明用户满意度越高。
如果 W 很大，说明你的小任务在后台被大任务压住了，无法及时运行。

2. 系统吞吐量高

定义：单位时间内系统完成的作业数量。

与批处理作业的平均长度有关

提高

多跑短作业

3. 处理机利用率高

多跑计算量大的作业

分时系统的目标

响应时间快

均衡性

实时系统的目标

截止时间的保证

可预测性

3.2 作业与作业调度

3.2.1 作业（Job）

作业：用户交给计算机的一个完整的任务

不仅包含程序和数据，还包含一份作业说明书，告诉操作系统该怎么运行。

作业步：作业被拆分成若干个相互联系、顺序执行的处理步骤。每一个步骤就是一个作业步

作业控制块（JCB）

操作系统中用于管理和描述“作业”的数据结构。

一个典型的 JCB 通常包含以下四类信息：

作业标识（Identity）：

作业名 / 作业 ID。

用户账号（谁提交的，方便扣费或查权限）。

资源需求（Resource Requirements）： —— 这是调度时的重要依据

预计运行时间（需要多久）。

内存需求（需要多大空间）。

外设需求（是否需要打印机、磁带机等）。

库函数或文件需求。

调度信息（Scheduling Info）：

优先级： 决定谁先进入内存。

作业状态： 进入系统了（提交）、正在排队（后备）、正在跑（运行）、跑完了（完成）。

进入时间： 记录作业是什么时候来的（用于计算等待时间）。

控制信息：

作业说明书的存放地址。

程序及数据的存放起始地址。

作业运行的生命周期

1. 收容阶段 (Admission Stage) —— “挂号排队”

过程： 当你把程序、数据和作业说明书交给操作系统时，系统会先检查一下：你的格式对不对？系统还有没有地方存你的信息？如果没问题，系统就为你创建一个 JCB（作业控制块），把你放在磁盘的“后备队列”里。

对应状态：后备状态 (Backlog State)。

你到了医院，在大厅挂了号，拿到了一个就诊号。此时你并没见到医生，而是在等候区坐着，你的名字出现在了候诊大屏幕上。这个“号”就是 JCB，候诊大厅就是后备队列。

2. 运行阶段 (Execution Stage) —— “进入诊室”

过程： 当系统资源（主要是内存）有空闲时，作业调度程序会从后备队列里挑一个作业，把它调入内存，为它分配必要的资源，并创建进程去执行它。

对应状态：运行状态 (Running State)。

注意： 这里的“运行状态”是一个宏观概念。从作业进入内存开始，到它运行结束前，都属于这个阶段。在这个阶段里，作业对应的进程可能会在 CPU 上跑，也可能在等 IO。

护士喊你的号了，你进入了诊室。医生给你开检查单、化验、诊断。这时候你正处于“被处理”的过程中。

3. 完成阶段 (Termination Stage) —— “缴费取药走人”

过程： 作业的所有步骤都跑完了，或者中途出错了被强行停止。系统会开始“收尾工作”：把运行结果输出，回收分配给它的内存、设备等资源，最后把它的 JCB 撤销（从系统里注销）。

对应状态：完成状态 (Finished State)。

医生看完了，你拿着处方去缴费、拿药。最后你离开了医院，医院的系统里显示你今天的就诊已经结束，你的号牌被回收了。

3.2.2 作业调度的主要任务

根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求。

按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。

将新创建的进程排在就绪队列上等待调度。

每次执行调度都做决定：

接纳多少个作业？

接纳哪些作业？

3.2.3 调度算法

1. 先来先服务——FCFS (First-Come, First-Served)

核心逻辑：谁先来，谁先办

唯一准则就是时间顺序。

判断标准： 等待时间。谁在队列里等得最久，谁就最优先。
无视因素： 它完全不看这个作业需要运行多久。哪怕排在第一位的作业需要跑 10 小时，而后面排队的作业只需要 1 秒，系统也会先处理那个 10 小时的。

优点

最公平： 谁先来谁先办，谁也没意见。

实现极其简单： 只要一个 FIFO（先进先出）队列就行，算法开销极小。

缺点

对“短作业”非常不友好： 短作业如果跟在长作业后面，周转时间会变得非常长。

平均等待时间较长： 整体效率通常不如其他算法。

2. 短作业优先——SJF（Short Job First）

💡

在实际情况中，短作业(进程)占有很大比例，为了能使它们能比长作业优先执行，而产生了短作业优先调度算法。

核心逻辑：谁快谁先上

唯一准则是作业的预计运行时间（估计时长）

时间越短，优先级越高
实现：当系统准备从后备队列挑选作业进入内存时，它会扫描一遍所有的作业，找出那个“干活最快”的。

缺点

估计时间不准确：

作业还没跑，系统怎么知道它要跑多久？这通常是用户在提交作业时自己填写的。如果用户为了早点运行而故意把时间填短，或者用户自己也预估不准，就会导致调度不准确。

一般会偏长估计。

“饥饿”现象（Starvation）：

如果系统里源源不断地有短作业进来，那么那些长作业（大项目）就永远得不到运行的机会，只能在后备队列里“饿死”。

不考虑紧急程度：

它只看长短。一个很紧急但时间略长的任务，会被一个不紧急但很短的任务插队。

特性	FCFS (先来先服务)	SJF (短作业优先)
判定标准	到达时间	运行时间
公平性	对长短作业都公平	对短作业极其偏心，对长作业不公
效率	平均等待时间较长	平均等待时间最短（在所有非抢占算法中）
风险	无	可能导致长作业“饥饿”

3. 优先级调度算法——PSA（Priority-Scheduling Algorithm）

前两种算法都无法反应作业的“紧迫程度“。

只看“等了多久”或“要跑多久”是不够的，我们需要一种能直接定义“这个任务有多急、多重要”的机制。

4. 高响应比优先算法——HRRN（Highest Response Ratio Next）

——对 FCFS（先来先服务）和 SJF（短作业优先）的一种综合折中。

目标：既要照顾短作业，又要保证长作业不会等太久。

方法：

引入响应比（），谁分高谁就先执行

原理：

对短作业：因为分母（要求服务时间）很小，所以即使它刚来（等待时间短），它的响应比也会迅速变得很高。这体现了 SJF（短作业优先） 的优点。
对长作业： 虽然分母很大，一开始很低。但随着它在队里等得越来越久，分子上的“等待时间”不断变大，它的会慢慢涨上来。等到了一定程度，它总会变成全场最高，从而获得处理机。这解决了 “饥饿”问题，体现了公平性。

3.3 进程调度

——从就绪队列中选一个进程，把 CPU 分配给它。

3.3.1 进程调度的任务、机制与方式

任务（上下文切换）

1. 保存处理机的现场信息（现场“存档”）

含义： 当一个正在运行的进程（比如 A）时间到了或者被抢占时，系统必须把 A 运行到哪一步了、寄存器里的数值是多少、程序计数器（PC）指到哪了，通通记下来。

存到哪： 存入该进程的 PCB（进程控制块） 中。

目的： 就像打游戏存档一样，下次轮到 A 运行的时候，能从断点处精准“读档”继续跑，而不是从头开始。

2. 按某种算法选取进程（决定“谁上”）

含义： 调度程序（Scheduler）查看“就绪队列”，里面排了一堆等着干活的进程。

依据： 这就是我们之前讨论的调度算法。

是按响应比（HRRN）选？
还是按时间片轮转（RR）选？
还是按短作业优先（SJF）选？

目的： 按照系统的目标（如：追求公平、追求效率、追求响应速度）选出最合适的那个进程（比如进程 B）。

3. 把处理器分配给进程（正式“换班”）

含义： 这一步由分派程序（Dispatcher）执行。它会做两件事：

从进程 B 的 PCB 中取出上次保存的现场信息，恢复到 CPU 的寄存器里（“读档”）。

把 CPU 的控制权真正交给进程 B，让它开始执行。

目的： 让选中的进程真正跑起来。

机制

主要有三部分构成：

1. 排队器 (Queuer) —— “排号员”

功能： 当一个进程进入就绪状态时（比如刚创建完，或者刚从阻塞状态醒来），排队器负责把它插入到相应的就绪队列中。

逻辑： 为了提高效率，系统通常不只有一个队列。排队器会根据进程的优先级、类型（是计算密集型还是 I/O 密集型）把它们送往不同的“窗口”排队。

2. 分派器 (Dispatcher) —— “叫号员”

功能： 根据调度算法，从就绪队列中选出一个进程。

动作： 它是做决策的那个“大脑”。它决定了谁是下一个作业上 CPU 运行。

3. 上下文切换器 (Context Switcher) —— “换班员”

功能： 这是真正干体力活的，负责处理“换班”时的细节。

流程（图中虚线部分）：

保存现场： 把当前正在 CPU 上跑的进程的各种数据（寄存器数值、程序计数器等）塞回它对应的 PCB（进程控制块） 里。

恢复现场： 把分派器选中的那个新进程的 PCB 里的数据拿出来，填到 CPU 的寄存器里。

移交控制权： 让 CPU 开始跑新进程的代码。

进程调度方式

1. 非抢占方式

——任务结束才能换作业

一旦把处理机分配给某进程后，就一直让它运行下去

不会因为时钟中断或任何其它原因去抢占当前正在运行进程的处理机
直至该进程完成，或发生某事件而被阻塞（如读硬盘，请求IO）时，才把处理机分配给其它进程。

优点： 简单，系统开销小（不需要频繁切换）。

缺点： 极不公平。如果前面排了一个“大长作业”，后面的短作业或紧急任务只能干等。

2. 抢占方式

——随时叫停更换任务

一旦发现更重要（优先级更高）或者更紧急（时间片到了）的进程，会暂停某个正在执行的进程，让其重新排队，把 CPU 让给留那个一个进程。

三个原则：

优先权原则： 来了个更重要的（高优先级）进程。

短作业优先原则： 新来的作业明显比现在的快得多。

时间片原则： 规定每个任务跑 10ms，到点就换（这是分时系统的基础）。

💡

目前的现代OS都采用抢占方式。

原因：

公平性（批处理系统）： 防止一个大任务一直霸占 CPU，让其他任务都能轮流用上。

人机交互（分时系统）： 这是最关键的。你移动鼠标、敲击键盘，系统必须立刻“抢占”当前正在后台跑的程序来响应你。如果不抢占，你点个图标可能要等后台压缩完文件才有反应。

实时性（实时系统）： 比如车载系统感应到要撞车了，这个“刹车进程”必须瞬间抢占正在放音乐的进程，否则后果不堪设想。

代价：系统开销大

3.3.2 轮转调度算法（RR）

过程

排队： 所有想要运行的进程按“先来先服务”（FCFS）原则排成一队。

定额： 系统规定一个固定的时间长度，叫做“时间片”（Time Slice，如 30ms）。

分配： CPU 只给排在队首的任务用这 30ms。

轮换： 30ms 时间一到，不管干没干完，打回队尾重新排队，CPU 给下一个任务用。

切换时机

① 提前完成

场景： 给这个进程分配了 10ms，但它执行到第 5ms 就把任务跑完了。

动作： 系统会立即把它从就绪队列里删掉，然后调下一个进程上来，并且给下一个进程重新计时（开始一个新的完整时间片）。

② 时间片用完

场景： 10ms 到了，但这个大工程还没搞定。

动作： 计时器发出中断信号，调度程序强行中止该进程。为了公平，系统把它踢到就绪队列的末尾去重新排队，然后把 CPU 给现在的队首进程。

时间片大小的确定

时间片大小的确定对系统性能影响很大。

对响应时间的影响

这张图揭示了时间片 q 与用户交互时间 s（比如你点一下鼠标，系统处理完所需的时间）之间的博弈。

图 (a) （理想情况）：

时间片 q 足够大，能覆盖掉大部分简单的交互任务。
结果： 进程在第一个时间片内就干完活了，响应时间就是 s。用户感觉非常快，系统也没有多余的切换开销。

图 (b) （糟糕情况）：

时间片太短，任务还没干完就被强行踢下 CPU 去排队。
结果： 进程被迫等待其他进程运行完后，再拿第二个时间片才能完成。
代价： 响应时间变成了原来的好几倍（图中的总长度 s 变长了），用户会明显感到掉帧或卡顿。

对周转时间的影响

进程名称及指标	A	B	C	D	E	平均 (Average)
到达时间	0	1	2	3	4	-
服务时间	4	3	4	2	4	-
RR (q=1) 情况	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ
完成时刻	15	12	16	9	17	-
周转时间	15	11	14	6	13	11.8
带权周转时间	3.75	3.67	3.5	3	3.33	3.46
RR (q=4) 情况	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ
完成时刻	4	7	11	13	17	-
周转时间	4	6	9	10	13	8.4
带权周转时间	1	2	2.25	5	3.33	2.5

在本例中，q=4 的表现明显优于 q=1。

因为 q=4 足够大，使得像 A、B、C 这样的进程在第一个时间片内或较短时间内就能完成，减少了进程在就绪队列中往返排队的次数，从而大幅降低了平均周转时间（从 11.8 降到 8.4）。

3.3.3 优先级调度算法

如果说之前的“轮转调度（RR）”是追求绝对公平，那么“优先级调度”就是追求效率和差异化服务（重要的、急的事先办）。

根据优先级的变动情况，分为以下两类：

1. 静态优先级

定义： 在进程创建时就定死了，整个运行期间优先数保持不变。

定数依据：

进程类型： 系统进程优先级通常高于用户进程。

资源需求： 对 CPU 要求不高的进程（如频繁等待读写磁盘的进程）往往会被给高一点的优先级，这样能提高整体资源利用率。

用户要求： 比如管理员手动给某个关键任务提高优先级。

缺点： 可能会导致“饥饿”现象。如果系统里一直有高优先级的新任务进来，低优先级的任务可能一辈子都轮不到运行。

2. 动态优先级

定义： 进程刚创建时有一个初始值，但在运行过程中，它的值会根据情况“自动调整”。

规则：

等待越久，级别越高： 这叫“老化”（Aging）。为了防止低优先级进程被饿死，如果它在队列里等太久，系统会自动给它“提拔”一级，直到它能被运行。
运行越久，级别越低： 如果一个进程占着 CPU 不撒手，系统会慢慢调低它的优先级，让出位置给别人。

3.3.4 多队列调度算法

——为了解决之前算法的一个通病：“一刀切”。

以前的做法： 系统里只有一个“就绪队列”，不管是系统关键进程、交互式进程（如键盘输入），还是后台大计算进程（如视频渲染），大家都挤在一起。

单一策略的局限性： 如果用轮转法（RR），对后台任务不划算（切换太频繁）；如果用先来先服务（FCFS），对前台交互任务太慢。

多处理机环境： 在多核 CPU 时代，如果只有一个队列，所有的 CPU 核心都要去抢这一个队列，会造成严重的拥堵和管理混乱。

工作原理

它的核心思想是：“分类管理，因材施教”。

系统将就绪队列拆分成多个独立的队列，每个队列代表一种特定的任务类型。

队列 1（高优先级）： 放系统任务（如驱动、内核任务）。采用抢占式优先级算法。

队列 2（中优先级）： 放前台交互任务（如文档编辑器、浏览器）。采用轮转法（RR），追求响应快。

队列 3（低优先级）： 放后台批处理任务（如系统更新、杀毒扫描）。采用先来先服务（FCFS），追求吞吐量。

3.3.5多级反馈队列（Multilevel Feedback Queue, MLFQ）调度算法

1. 调度机制 (Mechanism)

该算法通过设置多个队列并动态调整进程所属队列，实现了灵活调度：

设置多个就绪队列：

优先级逐级降低： 队列1优先级最高，队列2次之，以此类推。
时间片逐级增长： 优先级越高的队列，分配到的时间片越小。即：。

进程在队列间的移动规则：

新进程： 首先放入第一队列末尾，按先来先服务（FCFS）等待调度。
降级处理： 如果进程在当前队列的时间片内没跑完，调度程序会把它降级到下一级队列的末尾。
最终阶段： 当进程降到最后一级（第 n 队列）时，该队列通常采用时间片轮转（RR）方式运行。

队列间的调度优先级：

高优先级优先： 只有当第队列全部为空时，才会调度第 i 队列中的进程。
抢占机制： 如果 CPU 正在执行第 i 队列的进程，此时有一个新进程进入了更高优先级的队列（，新进程会抢占 CPU，被抢占的进程放回原队列末尾。

2. 调度算法的性能 (Performance)

该算法之所以被广泛应用，是因为它能同时兼顾各类用户的需求：

终端型用户（交互式）：

这类任务通常很短（如点个鼠标、打个字）。由于它们一进入就在第一队列，且第一队列优先级最高，因此能获得极快的响应时间。

短批处理作业用户：

这类任务通常在第一或第二队列的时间片内就能完成，周转时间非常短。

长批处理作业用户：

这类任务虽然会不断下沉到低优先级队列，但时间片会越来越大。这意味着虽然它们被调度的次数少了，但一旦拿到 CPU，就能连续运行很久，减少了频繁切换的开销。

3.3.6 基于公平原则的调度算法

与之前的“优先级调度”不同，这类算法不分贵贱，核心目标是公平，确保每个进程（或每个用户）都能得到应得的一份 CPU 时间。

1. 保证调度算法 (Guaranteed Scheduling)

这种算法向用户做出一个明确的承诺：“如果你和其他个任务一起跑，我保证你能分到 的 CPU 时间。”

原理：

为了实现这个“合同”，系统需要不断地进行数学计算：

记录实际时间： 记录每个进程从创建到现在，到底在 CPU 上跑了多久（实际时间）。

计算应得时间： 计算从进程创建到现在，它本来“应该”分到多少时间（总时间 / n）。

计算比率： 。

比率 < 1.0： 说明你还没分够，系统欠你的。

比率 > 1.0： 说明你跑超了，占了别人的便宜。

调度策略： 调度程序总是挑选比率最小的进程来运行，直到它的比率追上别人为止。

就像分蛋糕，如果现在有 4 个人。系统会盯着看谁吃得最慢，然后就把叉子递给谁，直到他吃得跟别人一样多为止。

2. 公平分享调度算法 (Fair Share Scheduling)

——对“保证调度算法”的一个重要修正。

公平性的漏洞

如果只看“进程”层面的公平，会导致“用户”层面的不公平：

用户 A： 开了 9 个下载任务（9 个进程）。

用户 B： 只开了 1 个网页（1 个进程）。

如果按“进程”平分，用户 A 会占掉 90% 的 CPU，而用户 B 只有 10%。这显然对用户 B 极度不公平。

它的核心逻辑

公平分享算法把“公平”的维度从进程提升到了用户（或用户组）。

系统先给每个用户分配相等的 CPU 份额。

比如两个用户，每人 50%。

无论用户 A 开了多少个进程，这 9 个进程只能内部去分那 50% 的时间；而用户 B 的那 1 个进程能独享剩下的 50%。

3.4 实时调度

——核心目标：必须满足截止时间要求

重点不在快，而是准时

3.4.1 实现实时调度的基本条件

1. 提供必要的信息

实时调度程序需要根据任务的紧急程度来排班，所以每个任务必须提前告知：

就绪时间： 任务什么时候能开始。

截止时间： 什么时候必须开始或完成（这是核心，没按时完成就算失败）。

处理时间： 任务跑完需要多久。

资源要求： 需要哪些内存、外设资源。

优先级： 是“死命令”（绝对优先级）还是“尽量快”（相对优先级）。

2. 系统处理能力强

核心公式：

：第 i 个任务的处理时间。

：第 i 个任务的周期时间。

：这个任务占用了 CPU 多少百分比的“带宽”。

含义： 如果所有周期性任务占用的 CPU 百分比之和大于 1（即 100%），说明 CPU 忙不过来，一定会有任务错过截止时间。

解决办法： 增加 CPU 核心数，或者提高主频。

3. 采用抢占式调度机制

在非实时系统中，一个任务可能一直占着 CPU。

在实时系统中，必须是抢占式的。一旦有一个更高优先级的实时任务（HRT）就绪，系统必须能够立刻打断当前任务，把 CPU 让给最紧急的任务，以确保截止时间不被错过。

4. 具有快速切换机制

如果抢占发生了，但系统“切换任务”的过程太慢，也会影响效率。这需要两个能力：

快速中断响应： 硬件能迅速察觉到紧急信号，并让 CPU 停下当前工作。

快速分派能力： 操作系统内核要非常精简，把进程切换（Context Switch）的时间压缩到极致。就像F1赛车换轮胎，每一秒都关系到生死。

3.4.2 实时调度算法的分类

按实时：

硬实时
软实时

按调度方式：

非抢占调度
抢占调度

1. 非抢占式调度算法（比较“温和”，实时性较差）

在这种模式下，就算紧急任务来了，也不能立刻把正在干活的任务踢走，必须等人家干完。

(a) 非抢占式轮转调度 (Non-preemptive Round Robin)：

逻辑： 任务排成一圈，轮流用 CPU。
图解： 实时进程请求调度后，得排在进程 1、进程 2... 进程 n 的后面。只有等前面的兄弟们都跑完了，才轮到实时进程。
缺点： 响应时间非常长，不适合高实时要求的场景。

(b) 非抢占式优先权调度 (Non-preemptive Priority)：

逻辑： 实时进程优先级高，可以“插队”到队列最前面。
图解： 实时进程来了，发现 CPU 正在跑“当前进程”。它不能中断人家，只能在旁边等着。等“当前进程”运行完成的一瞬间，它立刻顶上去。
缺点： 如果“当前进程”是一个需要跑很久的大任务，实时进程还是会等很久。

2. 抢占式调度算法（比较“霸道”，实时性强）

这种模式下，紧急任务可以直接打断当前正在运行的任务。

(c) 基于时钟中断抢占的优先权调度：

逻辑： 不是立刻抢，而是等“闹钟”响。
图解： 实时进程请求调度，系统收到了，但没动作。直到下一个时钟中断（Clock Interrupt）到来时，调度程序才醒过来，发现有贵客，于是把当前进程换下来，让实时进程上。
评价： 延迟取决于时钟频率（通常是几个毫秒），比非抢占式好很多。

(d) 立即抢占 (Immediate Preemption) 的优先权调度：

逻辑： 真正的“秒回”，一刻都不等。
图解： 只要实时进程发出请求，系统立即产生中断，强行停止当前进程，并在极短的调度开销后立刻运行实时进程。
评价： 这是硬实时系统（如导弹控制、自动驾驶）必须采用的机制。它的响应时间（调度时间）被压缩到了微秒级。

调度方式	什么时候切换？	响应延迟	适用场景
(a) 轮转	轮到你了才换	极高	简单、非实时
(b) 非抢占优先	当前进程主动结束	较高	任务都很短的实时系统
(c) 时钟中断抢占	等下一个时钟滴答	较低	软实时系统（如视频播放）
(d) 立即抢占	立刻、马上	极低	硬实时系统（工业控制、航天）

3.4.3 最早截止时间有限算法——EDF(Earliest Deadline First)

核心思想：谁的任务最赶时间（截止时间最早），就让谁先做。

1. 非抢占式调度用于非周期任务

在非抢占式的情况下，即使新来的任务更紧急，也得等当前任务做完。

执行逻辑：

任务 1 先到达并开始执行。

在任务 1 执行期间，任务 2 和 任务 3 陆续到达。

调度程序查看它们的截止时间：发现 任务 3 的截止时间 比 任务 2 早。

等任务 1 执行完，系统不按到达顺序，而是优先安排任务 3，最后才运行任务 2。

适用场景： 任务执行时间短，或者对实时性要求不是极其严苛的场景。

2. 抢占式调度用于周期性任务

案例背景：

任务 A：每 20ms 来一次，每次做 10ms（）。

任务 B：每 50ms 来一次，每次做 25ms（）。

EDF 运行轨迹：

t = 0ms：A1 和 B1 同时到达。A1 的截止时间是 20，B1 是 50。A1 截止时间早，先跑 A1。

t = 10ms：A1 跑完了，开始跑 B1。

t = 20ms：关键点！ A2 到达了。

此时 B1 还没跑完（还剩 15ms），B1 的截止时间是 50。

A2 的截止时间是 40。

因为 40 < 50，所以 A2 抢占了 B1。B1 被踢下去，A2 开始跑。

t = 30ms：A2 跑完了，B1 继续跑剩下的 15ms。

t = 40ms：A3 到达。

A3 的截止时间是 60。

此时 B1 还没跑完（还剩 5ms），B1 的截止时间是 50。

因为 50 < 60（B1 更急），所以 B1 继续跑，A3 必须等着。

t = 45ms：B1 总算跑完了，A3 开始跑。

3. 为什么 EDF 更好？（对比结论）

看图片最下方的对比：

固定优先级调度：如果给 A 高优先级，B 可能会错过截止时间（错过 50ms 的节点）；如果给 B 高优先级，A 可能会错过截止时间。

EDF（动态优先级）：优先级不是写死的，而是随着截止时间的逼近而改变。这种灵活性使得它能比固定优先级算法更充分地利用 CPU 资源，保证更多的任务不“违约”。

EDF 的精髓：

不看出身（到达时间）。

不看地位（固定优先级）。

只看截止日期（Deadline）。

在单处理机环境下，只要总的利用率，EDF 算法就能保证所有任务都在截止时间前完成。

3.4.4 最低松弛度优先算法——LLF（Least Laxity First）

松弛度 = 必须完成的时间 - 任务本身还需要运行的时间 - 当前时间

松弛度 = 0：意味着必须现在立刻开始跑，否则绝对跑不完。

松弛度很大：意味着可以先睡会，晚点再写也没事。

系统会不断计算所有就绪任务的松弛度，并优先执行松弛度最低的任务。这通常是一种抢占式调度。

案例详解：

还是回到上一个算法的场景。

t = 0ms：

A1 的松弛度 = 20 - 10 - 0 = 10
B1 的松弛度 = 50 - 25 - 0 = 25
结果：A1 松弛度更低，A1 开始运行。

t = 10ms：

A1 运行结束。此时只有 B1 在排队。
结果：B1 开始运行。

t = 20ms（关键点）：

任务 A2 到达。
A2 的松弛度 = 40 - 10 - 20 = 10
B1 已经跑了 10ms，还剩 15ms。B1 的松弛度 = 50 - 15 - 20 = 15
虽然 A2 更急，但在某些 LLF 实现中（为了减少切换开销），如果松弛度没到 0，可以先不抢占。但严格来说，此时 A2 (10) < B1 (15)，A2 应该抢占。
注：书中的图 3-9 采用了“等到松弛度为 0 再抢占”的策略。

t = 30ms：

A2 的松弛度 = 40 - 10 - 30 = 0（火烧眉毛了！）
B1 此时还剩 5ms。B1 的松弛度 = 50 - 5 - 30 = 15
结果：A2 的松弛度降到了 0，必须立刻抢占 B1。A2 开始跑，B1 停下。

t = 40ms：

A2 运行结束。B1 还有最后 5ms 没写完。
此时 A3 也到达了，A3 的松弛度 = 60 - 10 - 40 = 10。
B1 此时的松弛度 = 50 - 5 - 40 = 5。
结果：B1 更急（5 < 10），B1 优先补完剩下的 5ms。

3.4.5 优先级倒置

在优先级调度算法中，我们期望高优先级的任务能优先执行，但在某些情况下，高优先级任务反而会被低优先级任务阻塞，且被中优先级任务“插队”抢占执行时间。

1. 问题的起因（低优先级占用了资源）

初始阶段：低优先级的进程最先运行，它执行了 P(mutex) 操作，进入了临界区，并拿到了互斥锁（资源）。

时刻 a：中优先级的进程到达。因为优先级高于，它抢占了 CPU， 被挂起（但手里还拿着锁）。

2. 冲突的发生（高优先级被阻塞）

时刻 b：高优先级的进程到达。它是级别最高的，立刻抢占了开始运行。

时刻 c：运行到一半，也需要使用那个互斥资源（执行 P(mutex)）。但由于锁在手里， 被阻塞，进入等待状态。

3. 核心问题点（中优先级的“插队”）

c 到 d 之间：按理说，在等放锁，此时应该让赶紧跑完把锁还给。

但是，系统中还有一个就绪的。因为的优先级比高，调度器会选择 优先运行。

结果：一直运行到结束（时刻 d），这段时间内，最高级别的只能眼睁睁看着在跑，自己却在等。

4. 最终解决

时刻 d：运行完了，CPU 终于回到了手中。继续执行临界区代码。

时刻 e：执行 V(mutex) 释放了锁。此时，阻塞的立即被唤醒，抢占 CPU 进入临界区执行。

解决：优先级继承

在之前的问题图中，高优先级的被中优先级的无端阻塞。而在这一张图中，通过“临时提升优先级”的策略，成功缩短了的等待时间。

时刻 c：P1 请求互斥资源（P(mutex)），但资源被 P3 占用，P1 进入阻塞状态。

关键变化：此时系统发现高优先级的 P1 在等 P3。为了防止 P2 插队，系统将 P3 的优先级临时提升到与 P1 相同的水平。这就是图中标注的“继承”。

c 到 d 之间：因为 P3 现在拥有了“伪高优先级”，它比 P2 级别更高。所以 P3 能够抢回 CPU 继续执行，而 P2 只能继续等待。

时刻 d：P3 执行完临界区代码，调用 V(mutex) 释放资源。

优先级复原：一旦释放资源，P3 的优先级立刻跌回原本的低水平。
P1 夺回控制权：资源空闲后，P1 立即被唤醒并抢占 CPU，进入 CS−1 执行。

时刻 e：P1 全部运行结束。此时系统中优先级最高的是 P2，于是 P2 开始恢复运行。

习题

1、下列进程调度算法中，综合考虑进程等待时间和执行时间的是（）。

A. 时间片轮转 B. 短进程优先 C. 先来先服务 D. 高响应比优先

答案

考点： HRRN 的核心公式 响应比=(等待时间+服务时间)/服务时间

2、【2017 408】下列有关基于时间片的进程调度的叙述中，错误的是（）。

A. 时间片越短，进程切换次数越多，系统开销越大

B. 当前进程的时间片用完后，该进程状态由执行态变为阻塞态

C. 时钟中断发生后，系统会修改当前进程在时间片内的剩余时间

D. 影响时间片大小的主要因素包括响应时间、系统开销和进程数量等

答案

解析：进程切换带来系统开销，切换次数越多，系统开销越大，即A选项正确；当前进程的时间片用完后，该进程状态由执行态变为就绪态，即B选项错误；时钟中断是系统特定的周期性时钟节拍。操作系统通过它来确定时间间隔，实现时间的延时和任务的超时，即C选项正确；现代操作系统为了保证性能最优，通常根据响应时间、系统开销、进程数量、进程运行时间、进程切换开销等因素确定时间片大小，即D选项正确。

3、假设4个作业到达系统的时刻和运行时间如下表所示。

系统在t=2时开始作业调度。若分别采用先来先服务和短作业优先调度算法，则选中的作业分别是 A．J2、J3 B．J1、J4 C．J2、J4 D．J1、J3

答案

解析：系统在 t=2时开始作业调度，若采用先来先服务调度算法，此时已有J1、J2和J3作业到达，作业来得越早优先级越高，则选中的作业是J1；若采用短作业优先调度算法，此时已有J1、J2和J3作业到达，但作业运行时间大小排序为J3<J2=J1，作业运行时间越短优先级越高，则选中的作业是J3。

4、高响应比优先 HRRN 分析题

有 4 个作业：

J1：到达 0，服务时间 3

J2：到达 2，服务时间 6

J3：到达 4，服务时间 4

J4：到达 6，服务时间 2

系统采用高响应比优先 HRRN。要求：

（1）在每次调度时，计算所有已到达作业的响应比；

（2）给出作业选择顺序；

（3）求平均周转时间；

（4）说明 HRRN 为什么能兼顾短作业和长作业。

答案

已知：

J1：到达 0，服务 3

J2：到达 2，服务 6

J3：到达 4，服务 4

J4：到达 6，服务 2

HRRN 为非抢占式调度，响应比公式为：

每次从已到达且未完成的作业中选择响应比最大的作业执行。

1. 调度过程

t = 0

只有 J1 到达：

执行：J1：0 →3

t = 3

此时只有 J2 已到达：

执行：J2：3 → 9

t = 9

此时 J3、J4 已到达：

因为 (R_4 > R_3)，所以执行：J4：9 →11

t = 11

只剩 J3：

执行：J3：11 → 15

2. 调度顺序

3. 周转时间

周转时间 = 完成时刻 - 到达时刻

J1：(3-0=3)

J2：(9-2=7)

J3：(15-4=11)

J4：(11-6=5)

平均周转时间：

4. 结论

各次调度响应比：

(t=0)：J1 = 1
(t=3)：J2 = 7/6
(t=9)：J3 = 9/4，J4 = 5/2
(t=11)：J3 = 11/4

调度顺序：

平均周转时间：

HRRN 既考虑服务时间，又考虑等待时间：短作业因服务时间短，响应比容易更高；长作业等待越久，响应比也会逐步增大，因此能在一定程度上避免 SJF 中长作业“饥饿”的问题。