处理机调度层次与评价指标

复习定位

操作系统在三个不同时间尺度上决定到底是"让哪个程序占用CPU"。高级调度控制多少程序进入内存参与竞争、中级调度置换内存中的程序以缓解内存压力、低级调度决定下一个占据CPU的就绪进程。相应的关键指标——周转时间(作业从提交到完成的总时间)和响应时间(用户从发出命令到获得响应的时间)是用户最关心的。

三种调度层次

高级调度(作业调度)——决定从后备队列中选择哪些作业/进程进入内存——创建进程——加入就绪队列。频繁度较低(几秒至几分钟一次)。控制多道程序度(同时允许在内存的进程数)。在分时系统中——用户命令直接创建进程无需高级调度——高级调度主要用于批处理系统。

中级调度(对换)——从挂起队列中选择一些进程将其换回内存——或把内存中的一些非活跃进程换入磁盘(挂起)。用于调节内存压力——当内存紧张时——挂起一些进程并释放其所占内存给更活跃的进程。对换通常发生在秒级的时间尺度。

低级调度(进程调度)——从就绪队列中选择一个进程——分配CPU。每10ms~100ms发生一次——频率最高。低级调度的核心算法分为抢占和非抢占——现代操作系统全部使用抢占式(时间片用尽后强行剥夺CPU控制权)。

调度算法评价指标

CPU利用率——CPU忙的时间占总时间的比例。批处理系统追求高CPU利用率(尽可能让CPU满载)但交互系统更注重响应时间而CPU不一定跑满。

吞吐量——在单位时间内完成的进程数量——相同时间内完成的进程数越多——吞吐量越高。批处理系统的重要指标。

周转时间——从作业提交到作业完成所经过的总时间——包括等待进内存、等待CPU、I/O操作的总和。周转时间 = 完成时间 - 提交时间。平均周转时间越短——系统的总体效率越高。

等待时间——进程在就绪队列中排队等待CPU的总时间(不包含I/O等待时间)。对用户感知来说——等待时间比周转时间更直接。

响应时间——从用户提交作业(如按下一个按键)到系统首次产生输出(字符显示在屏幕上)的时间——交互式系统中最关键——必须短于100ms人才能感受到顺滑。

资源使用的权衡

没有一种调度算法能同时优化所有指标：

• FCFS使长作业周转时间长(护航效应)。
• SJF(短作业优先)最小化平均等待时间——但长作业可能饥饿。
• 时间片轮转(RR)使响应时间短——但增加了上下文切换开销——降低了总吞吐。

因此现代调度器(如Linux CFS)使用复杂的动态优先级和抢占时间片模型在多种指标间做权衡。

复习检查

1. 高级调度和低级调度各自——高级调度从作业队列中选择作业进入内存——低级调度从就绪队列中选择进程上CPU。

2. 什么是"多道程序度"——内存中同时容纳的进程数量——高级调度控制这个数量的上限——防止进程太多导致内存不足而频繁换页。

3. 为什么响应时间在交互系统中比周转时间更重要——用户从键盘输入到字符显示在屏幕上之间的延迟——用户希望毫秒级(<100ms)反馈——而周转时间往往受限于程序的计算或I/O总体时间。

4. 中级调度何时触发——物理内存不足时——操作系统选择一个或多个进程将其挂起换到磁盘交换区——释放内存给需要的进程。

5. 低级调度中的"抢占"和"非抢占"的区别——抢占式调度中——时钟中断强制当前运行的进程暂停放回就绪队列——调度器在队列中另选一个进程运行。非抢占式调度中——进程一旦获得CPU就一直运行到主动放弃(I/O或结束)。

三种调度层次的详细比较

特性	高级调度(作业调度)	中级调度(对换)	低级调度(进程调度)
触发频率	低(秒~分钟级)	中等(秒级)	极高(10~100ms一次)
切换代价	大(创建地址空间/加载程序)	大(进程内存换入换出)	小(寄存器上下文切换)
主要目标	控制多道程序度	缓解内存压力	公平分配CPU时间
调度对象	作业(外存→内存)	进程(内存↔磁盘)	进程/线程(CPU分配)
典型算法	FCFS、SJF	页面置换/换出策略	时间片轮转/CFS

三种层次互相配合——高级调度决定多少作业进入系统——中级调度在内存紧张时临时减少活跃进程数——低级调度在就绪进程中分配CPU。如果没有高级调度——大量作业涌入内存可能导致系统过载——如果没有中级调度——内存不足时只能依赖低级调度频繁换页——系统性能将会严重下降。

调度评价指标的定量关系

以一组进程的执行时间为例——计算不同调度算法下的指标：

进程: P1(CPU=8ms), P2(CPU=4ms), P3(CPU=9ms), 全部在时刻0到达

FCFS(P1→P2→P3):
等待时间: P1=0, P2=8, P3=12 → 平均等待=6.67ms
周转时间: P1=8, P2=12, P3=21 → 平均周转=13.67ms
响应时间: P1=0, P2=8, P3=12

SJF(非抢占, P2→P1→P3):
等待时间: P2=0, P1=4, P3=12 → 平均等待=5.33ms
周转时间: P2=4, P1=12, P3=21 → 平均周转=12.33ms
响应时间: P2=0, P1=4, P3=12

RR(q=4ms):
执行顺序: P1(0-4)→P2(4-8)→P3(8-12)→P1(12-16)→P3(16-21)
等待时间: P1=(4+8)=12, P2=4, P3=(4+4)=8 → 平均等待=8ms
周转时间: P1=16, P2=8, P3=21 → 平均周转=15ms
响应时间: P1=0, P2=4, P3=8

从以上数据可以看出：SJF的最小化了平均等待时间(5.33ms)——RR的响应时间最短(最大8ms)——FCFS综合表现居中。不同的目标选择不同的算法——没有"绝对最好"的调度算法。

响应时间在交互系统中的实际意义

响应时间是交互式系统中用户能直观感知的关键指标：

响应时间 < 100ms: 用户感觉"即时响应"
响应时间 100-300ms: 用户能感知到轻微延迟但不影响体验
响应时间 300-1000ms: 用户明显感到系统"卡了一下"
响应时间 > 1000ms: 用户会分心或认为系统运转停滞

分时系统的核心设计目标就是将响应时间控制在100ms以内——通过更短的时间片(10-50ms)、更高的进程切换频率——使多个用户都能感觉到"系统专为自己服务"。响应时间由低级调度的时间片长度和就绪队列的进程数共同决定——在总就绪进程数一定时——更短的时间片带来了更快的平均响应——但也带来了更多的上下文切换开销。

调度指标之间的冲突关系

没有任何一种调度算法可以同时优化所有指标：

• 周转时间与响应时间冲突——SJF最小化平均周转时间——但长作业(需要长时间计算的作业)响应时间很差(轮到它时已过很久)。
• 吞吐量与响应时间冲突——RR通过频繁切换改善响应时间——但上下文切换消耗CPU时间——降低了总吞吐量。
• 公平性与其他指标冲突——完全公平分配CPU时间可能让短作业得不到优先响应——降低交互用户体验。

Linux CFS的设计目标是"在公平分配CPU时间的前提下、最小化响应时间"——而不是单纯追求最小周转时间。

复习检查（续）

6. 用FCFS、SJF、RR(q=4ms)三个算法计算一组进程(P1:8ms,P2:4ms,P3:9ms——同时到达)的平均等待时间、平均周转时间和响应时间表的差异——SJF的平均等待时间最短(5.33ms)——RR的响应时间最均匀——FCFS的周转时间最大(13.67ms平均)。

7. 为什么没有一种调度算法能同时优化周转时间、响应时间和吞吐量——因为优化目标互相冲突——SJF优化周转时间但长作业早起入等待期延长——RR优化响应但增加了切换开销降低了吞吐——没有免费的午餐。

8. 中级调度在什么具体条件下触发——OS检测到物理内存不足(频繁缺页)——选择一个或多个非活跃进程——将其地址空间换出(suspend)到磁盘交换区——释放物理页框给活跃进程。

9. 分时系统和批处理系统在响应时间要求上的差异——分时系统要求响应时间<100ms——批处理系统不在乎响应时间(数小时都可以接受)——只在乎周转时间。

10. 高级调度如何控制多道程序度——设定系统允许的最大进程数——当内存中的进程数达到上限时——新作业在后备队列等待——直到有进程退出。

三级调度在现代操作系统中的实际体现

现代Linux操作系统中——三个调度层次都有对应的实现：

高级调度——在批处理系统中——通过作业队列限制同时运行的作业数。在分时系统中——每个终端登录直接创建进程——没有作业队列——所以高级调度功能简化为fork的资源的限制(通过ulimit -u限制用户的最大进程数——通过/etc/security/limits.conf配置)。

中级调度——在内存压力下——Linux的kswapd内核线程和直接页面回收机制(页面换出)将不活跃的匿名页面换出到交换分区——当进程重新访问被换出的页面时——触发缺页中断——从交换分区读回内存。这一换入换出过程实质上就实现了中级调度的功能——而不需要挂起整个进程。

低级调度——Linux的CFS调度器在每次时钟中断(或主动调度)时——选择vruntime最小的就绪进程——分配CPU。低级调度进程的触发频率极高(通常在1ms到几毫秒间隔的tick上进行以及抢占点)——这是操作系统最核心的时间共享和资源分配功能。

进程调度的决策时机

低级(进程)调度发生在以下时机：

1. 当前进程主动放弃CPU(调用sleep/wait/block等系统调用)
2. 时钟中断——当前进程CPU时间片用完
3. 系统调用或中断返回时——检查need_resched标志——如果设置则触发调度
4. 更高优先级的进程醒来——可能抢占当前进程
5. 进程退出时——自动调度下一个就绪进程

其中第2点(时钟中断)是现代操作系统实现抢占式调度的基础硬件支持。

调度评价指标在工程中的权衡使用

在设计一个多用户操作系统或在评估系统反应能力时——应该根据业务类型选择主评价指标：对于网站服务器(Web Server)或系统控制台——响应时间最关键；对于后台大规模数据处理(如数据分析、媒体转码处理)——吞吐量和周转时间最重要；对于实时控制(如工业机器人控制器)——需要确保每个任务的调度和终止时间绝对可控——按完成时限(Deadline)调度——不是一般分时的调度指标体系的范围。

复习检查（续二）

11. 抢占式调度依赖的硬件机制——时钟中断(通常由可编程间隔定时器PIT或高精度事件定时器HPET产生)——定时向CPU发送中断信号——操作系统在中断处理程序中检查当前进程是否已用完时间片——触发调度。

12. 非抢占式调度下如何保证响应公平——进程自愿放弃CPU(调用yield、I/O阻塞)——但如果进程不主动放弃——就可能长时间霸占CPU——交互响应极差——因此所有现代多任务OS都使用抢占式调度。

13. 低级调度的主要触发时机——时钟中断时间片用尽——进程主动阻塞——更高优先级进程唤醒抢占——系统调用/中断返回时need_resched检查。

14. 为什么交互式系统对响应时间敏感而对周转时间相对容忍——用户操作(按键、点击)后的反馈延迟直接影响用户体验——而任务后台耗时长短用户往往可以理解(数据下载、文件导出等)。

15. 高级调度(作业调度)在分时系统中通过其他方式实现的资源限制——通过ulimit -u限制每个用户的最大进程数——通过cgroup限制用户组的总CPU/内存使用量——从而间接控制系统的多道程度。

16. 虚拟化环境下调度层级的变化——从"OS调度进程"变为"OS→Hypervisor调度vCPU→物理CPU"——额外调度层增加了CPU时间分配的不确定性。

17. 容器的调度层级相比虚拟机更简单的原因——容器进程直接由宿主机CFS调度——没有vCPU层——调度开销更小、性能损耗更低。

18. load average与CPU使用率的关系——load average高而CPU使用率低通常意味着大量进程在等待I/O(表现为D状态或S状态)——而不是CPU满载。

19. 时钟中断在抢占式调度中的作用——每10ms触发一次中断——检查当前进程是否用完时间片——用完则调度另一个就绪进程——确保按时间片公平分享CPU。

20. IC交互系统对响应时间的容忍限度——人机交互延迟100ms内认为是即时——100-300ms可感知延迟——>1000ms会打断用户的工作流——因此CFS和RR将时间片选择在10-100ms范围内。

调度指标在系统调优中的应用

实际系统中——性能监控工具(top、htop)显示的"load average"值可以反映CPU的调度负载——如果load average ≈ CPU核心数——说明CPU资源使用接近饱和但还没过载——如果load average >> CPU核心数——说明系统有大量进程在等待CPU——可能是调度器超负荷——也可能是大量I/O请求导致进程阻塞等待的中级调度行为。需要进一步检查是CPU瓶颈还是I/O等待——使用iostat、vmstat细化分析。

处理机调度在虚拟化和容器环境中的特殊性

虚拟化环境中——hypervisor增加了额外的调度层：客户机(VM/container)对vCPU进行调度——hypervisor在物理CPU上调度这些vCPU。这导致调度层级从"OS进程调度"增加为"OS进程调度→vCPU调度→物理CPU调度"三层——产生了额外的复杂性——如嵌套抢占和CPU时间分配的多层不确定性。Docker容器虽然轻量——但容器内的所有进程仍然被宿主机的CFS调度器调度——不涉及虚拟机那层vCPU调度——所以调度层次更简单、性能损耗更小。

复习检查（续三）