Multiprog 和 Time-Sharing OS 这两个词几乎每个翻操作系统教材的人都会在第三章撞见但真正能把它们讲清楚的人不多。我见过太多人把多道程序和分时系统当同义词用——反正都是同时跑多个程序嘛——可一旦追问为什么要多道分时的关键指标是什么时间片设多大合适就答不上来了。这两个概念其实分属两个层次。MultiprogMultiple Programming多道程序设计是一种资源利用手段让多道程序同时驻留内存在某道程序等待 I/O 时把 CPU 让给另一道把 CPU 的空闲时间填满。Time-Sharing OS分时操作系统则是一种面向交互的系统形态把 CPU 时间切成小片轮转分配让多个用户或任务觉得自己独占了一台机器。一个是手段一个是目标一个盯吞吐量一个盯响应时间。这篇内容我打算从动机讲起把 CPU 利用率的算法、时间片长度的定量取舍、上下文切换的真实代价讲透再用 Python 手写一个时间片轮转调度器跑给你看最后聊聊这套几十年前的思路今天在通用系统、车载系统、移动端上是怎么变形的。适合正在补操作系统基础、准备技术面试或者被参数调了却没效果这类系统调优问题困住的人。1. CPU 空转的代价Multiprog 到底在补哪个窟窿1.1 单道批处理时代CPU 被 I/O 拖成了配角早期的批处理系统一次只往内存里装一道程序跑完再装下一道。问题出在速度差上CPU 执行一条指令是纳秒级机械磁盘寻道加旋转延迟是毫秒级中间差了六个数量级。程序一发起 I/O 请求CPU 就只能干等等数据从外设搬回来才能继续。拿个具体数字算假设一个作业总共需要 100ms 的 CPU 计算和 900ms 的 I/O 等待那么在单道环境下这道程序占用机器 1000ms其中 CPU 真正干活只有 100ms利用率 10%。剩下 90% 的时间CPU 就在那儿空转。这不是程序写得差而是单道模型的结构性缺陷——内存里只有一道程序它一停整台机器就停。I/O 密集型作业比例越高这个浪费越触目惊心。数据库查询、日志写入、文件传输本质都是算一点、等一下、再算一点。单道批处理跑这类负载CPU 大量时间在发呆。1.2 多道程序用等待换吞吐量多道程序设计的解法很直接内存里同时放好几道程序当正在运行的那道因为 I/O 而阻塞时操作系统不闲着立刻切换到另一道就绪程序继续跑。等 I/O 完成中断通知 CPU原来那道程序重新排队等调度。这样一来I/O 和 CPU 就能重叠工作机器不再因为一次磁盘读写而停摆。这个策略的效果可以用一个经典公式估出来。设每道程序等待 I/O 的时间比例是 p内存里有 n 道独立程序那么 CPU 利用率大致为U 1 - p^n代入 p 0.8典型的 I/O 密集型负载算一组并发程序数 np^nCPU 利用率 U10.8020.0%20.6436.0%30.51248.8%40.41059.0%80.16883.2%100.10789.3%两点值得记住一是加程序确实能显著拉升利用率从 1 道加到 4 道利用率翻了三倍二是收益递减n 从 8 加到 10 只涨了 6 个百分点而且理论上永远逼近 100% 却到不了。这个公式是理想化模型假设各程序等待 I/O 的行为相互独立实际还会受内存容量、I/O 带宽、调度器效率的制约但它足够说明多道程序的价值所在。1.3 多道程序跑不起来往往是缺了这几块硬件拼图很多人以为多道程序只是个软件技巧其实它有一整套硬件前提缺一个都玩不转。中断机制是第一块。如果 CPU 只会忙等轮询外设状态那多道程序的意义就没了。有了中断I/O 完成时外设能主动拍一下CPU操作系统才有机会在正确的时机做切换。DMA 和通道是第二块让外设自己把数据搬进内存减少 CPU 的搬运负担否则光靠 CPU 一个字一个字搬重叠的意义又会打折。内存保护是第三块也是新手最容易忽略的。多道程序意味着多道程序同时躺在内存里如果没有任何保护A 程序一个野指针就能把 B 程序的数据覆盖掉系统立刻崩溃。所以需要基址寄存器、界限寄存器或者页表这种机制给每道程序划定自己的地盘越界访问直接触发异常。早期没有内存保护的分时系统稳定性一直上不去根子就在这里。第四块是可抢占的调度器——得有机制决定下一道该跑谁以及什么时候把控制权收回来。这几块拼图凑齐了多道程序才真正从纸面概念变成能在机器上跑的东西。1.4 并发不等于并行这个区别决定了你的性能预期有个常见的认知偏差既然多道程序能同时跑多个任务那加任务是不是就该变快答案要看是单核还是多核。单核 CPU 上跑多道程序物理层面依然是串行的——某一时刻只有一个任务占用执行单元所谓同时是逻辑上的并发调度器快速地在多个任务之间切来切去快到你感觉不出切换。拿厨房打比方一个厨师同时照看三口锅他一会儿翻炒这口、一会儿搅动那口看上去三口锅都在动但厨师的手只有一双。多核才是真并行那是三个厨师各守一口锅。这个区别直接决定了优化方向。如果你在单核上观察到一个 CPU 密集型程序加了多线程后没变快别怀疑代码那是并发在单核上的必然结果——线程越多切换开销越大甚至可能更慢。反过来I/O 密集型任务加线程通常有效因为线程大部分时间在等 I/O切换出去正好把 CPU 让给别的线程干活这正是多道程序思想的现代形态。2. 分时系统把等待切成人感知不到的节拍2.1 时间片是怎么切出来的多道程序解决了CPU 别闲着但它没规定一道程序能连续跑多久。如果一道 CPU 密集型程序一旦拿到 CPU 就不撒手其他程序只能干等响应时间会难看到没法用。分时系统补的就是这一刀给每道程序分配一个时间片time slice也叫 quantum用完就强制换人。时间片的大小不是拍脑袋定的它得跟人机交互的感知节奏对齐。假设你在一个 10 人的分时系统里时间片设成 10ms那么一轮轮转是 100ms每个用户在轮到自己之前最多等 100ms。而心理学上的经验值是100ms 以内的延迟人基本无感100ms 到 1s 会觉得轻微迟滞但可接受超过 1s 注意力就开始飘。所以 10ms 时间片配上 10 个左右的活跃用户响应体验刚好卡在流畅的区间。用户数上百的话时间片得压到 1ms 甚至更小否则一轮等待时间就长得没法忍了。2.2 时钟中断分时系统的心跳分时能不能成立关键看操作系统有没有能力强行打断一个正在跑的程序。这个能力来自时钟中断。操作系统启动时会设定一个可编程定时器让它每隔固定时间产生一次中断。中断一到CPU 暂停当前程序跳进中断处理程序操作系统在这里检查当前进程的时间片是不是用完了用完了就触发调度、换下一个进程上场。整个过程对用户程序完全透明。没有时钟中断会怎样一道while(1)的死循环就能永久霸占 CPU其他任务一个都别想跑。这就是所谓的非抢占式调度早期 Windows 3.x 和 Mac OS 9 用的就是协作式的思路——程序得主动让路操作系统才能拿回控制权。后果很直接一个程序卡死整个系统跟着假死。现代操作系统全部转向抢占式调度时钟中断就是那个把控制权攥在操作系统手里的硬机制。提示抢占能力和时钟中断频率有关。Linux 的调度时钟节拍CONFIG_HZ常见取值是 250、300 或 1000 Hz意味着每秒最多产生对应次数的时间管理中断。频率越高调度响应越快但中断开销也越大这是一个需要权衡的参数。2.3 目标函数的转变分时优化的是响应不是吞吐批处理和分时盯着的是完全不同的指标认清这一点很多调度策略的取舍就顺理成章了。批处理关心吞吐量单位时间完成多少作业和 CPU 利用率因为它面对的是成堆的离线任务没人在旁边盯着屏幕等结果快慢几个小时无所谓。分时关心响应时间和公平性因为它面对的是活人用户敲一下回车就希望屏幕立刻有反应。实时系统又是另一套它关心截止时间满足率——任务必须在某个时间点前完成晚一毫秒都算失败哪怕平均性能再好也没用。系统类型首要指标次要指标典型场景时间片策略批处理吞吐量、CPU 利用率周转时间离线计算、报表批跑大时间片或不用抢占分时响应时间、公平性吞吐量终端交互、多用户主机小时间片轮转实时截止时间满足率可预测性工业控制、车载电子固定优先级抢占指标一变算法选择就跟着变。批处理场景下用一个粗暴的 FCFS 甚至更划算而分时场景下必须让交互任务优先拿到 CPU——这就是后面几节要展开的调度算法世界。3. 调度算法怎么选从 FCFS 到多级反馈队列3.1 先来先服务与那个坑人的护航效应先来先服务FCFS是最朴素的策略来一个任务排到队尾CPU 空闲就取队头。实现简单、天然公平按到达顺序但有个致命毛病叫护航效应convoy effect。举个例子任务 A 需要 100 个时间单位任务 B、C 各需要 1 个。如果 A 先到执行顺序是 A→B→CB 要等 100C 要等 101平均等待时间约 67。如果把顺序换成 B→C→AB 等 0、C 等 1、A 等 2平均等待才 1。同样的任务顺序一换平均等待差了 60 多倍。一个长任务卡在前面后面所有短任务都被拖着走——这在交互场景里是灾难。所以 FCFS 基本只适合批处理且任务长度比较均匀的情况。3.2 短作业优先理论上最优实际却难落地短作业优先SJF可以数学证明能让平均等待时间最小。它的直觉也简单先干快活短任务迅速清空长任务少挡道。但 SJF 有个没法回避的前提你得预知每个任务要跑多久。实际系统里这件事根本做不到谁也没法在进程刚创建时就知道它要占多少 CPU。工程上的折中是用历史数据做预测常见做法是指数平均预测值(n1) α × 实际值(n) (1-α) × 预测值(n)α 一般取 0.5 左右最近一次的表现和新预测各占一半权重。但预测总有偏差碰上突然变长或变短的任务就不准。更麻烦的是 SJF 可能让长任务永远排在后面——只要系统里一直有短任务进来长任务就饿死了。所以纯 SJF 也很少直接用它的思想更多是融进更复杂的调度器里。3.3 时间片轮转时间片长度该用公式算不是凭感觉时间片轮转Round RobinRR是分时系统的标配所有就绪任务排成队列调度器给队头任务一个时间片用完或提前阻塞就扔到队尾取下一个。时间片的取值很讲究太大和太小都出问题。太大RR 退化成 FCFS交互响应变差太小上下文切换占的比例飙升CPU 大量时间花在换人而不是干活上。这个权衡可以用一个简单公式量化有效 CPU 利用率 q / (q c)其中 q 是时间片长度c 是一次上下文切换的开销。假设切换开销 c 0.1ms代入不同 q时间片 q有效利用率 q/(qc)每秒切换次数上限1ms90.9%约 10005ms98.0%约 20010ms99.0%约 10020ms99.5%约 50可以看到q 从 1ms 提到 5ms利用率就追回了 7 个百分点再往上加收益就很小了。经验规则是让 q 比切换开销大一个数量级左右同时保证一轮轮转时间落在几百毫秒以内。通用分时系统的默认时间片大多落在 10ms 到 100ms 之间背后的账就是这么算的。3.4 多级反馈队列现代操作系统给出的近似答案现实中很少有系统只用单一算法因为负载是混合的——有敲一下键盘就等回显的交互进程也有要跑几分钟的编译任务。要让它们都满意就得用多级反馈队列MLFQ。它的设计思想是分层把就绪队列按优先级分成好几级优先级越高的队列时间片越短优先级越低的队列时间片越长。新任务一律先进最高优先级队列跑完一个短时间片还没结束就降一级时间片也变长。如果某个任务在最底层等太久就把它升回高优先级——这条规则专门用来防止长任务饿死。这套机制的好处是自动区分任务类型交互型任务通常消耗很少 CPU 就阻塞等输入了它会一直待在高优先级响应飞快CPU 密集型任务很快用完短时间片被降级去底层的长时间片里慢慢跑不再频繁打断交互任务。现代通用操作系统调度器的核心思路基本都是 MLFQ 的变体。下面把几种算法摆在一起对比算法抢占式优点缺点适合场景FCFS否实现最简单护航效应严重批处理、均匀负载SJF可选平均等待理论最优需预知运行时间、会饿死长任务已知任务长度的批处理时间片轮转是响应公平、实现简单时间片长度敏感分时交互优先级调度是重要任务优先低优先级饿死实时、有明确优先级的场景多级反馈队列是自动适配混合负载参数多、调优复杂通用操作系统3.5 选算法的三条判断线索落到实际场景可以从三个问题入手。第一用户在不在等结果。有活人盯着屏幕就偏向抢占式小时间片纯后台跑批就用大时间片甚至不抢占减少切换浪费。第二任务长度差多少。如果系统里任务长度差异极大优先级或 MLFQ 能有效隔离长任务对短任务的干扰如果任务长度都差不多RR 就够用。第三有没有硬时限。只要任务存在必须在此刻前完成的约束就得上实时调度那一套固定优先级、优先级继承、速率单调别拿通用的分时策略凑合——这件事后面第 6 节还会再谈。4. 上下文切换分时背后最贵的那一笔开销4.1 一次切换到底发生了什么上下文切换这个词听着抽象拆开就是一套具体的动作。当调度器决定从进程 A 换到进程 B核心里大致走这么几步把 A 的当前执行现场保存下来包括程序计数器、各通用寄存器、栈指针、状态字写进 A 的进程控制块PCB更新 A 的状态从运行改成就绪或阻塞调度器从就绪队列里挑出 B从 B 的 PCB 里恢复执行现场如果 A、B 属于不同进程还要切换地址空间也就是更新页表基址寄存器x86 上就是那个 CR3返回用户态B 从上次中断的地方接着跑。注意第 5 步——切换地址空间才是真正昂贵的地方因为它会让 CPU 里一堆缓存数据瞬间失效。也因此同一进程内线程之间的切换要比进程间切换便宜因为线程共享地址空间省掉了这一步。4.2 真正的代价不在寄存器而在缓存很多人算上下文切换开销只算了保存恢复寄存器和调度器决策那几微秒觉得几微秒还好啊。这是低估了。切换的直接开销确实只有 1 到 10 微秒量级但间接开销要大得多。罪魁祸首是 CPU 缓存和 TLB地址转换后备缓冲。新进程的代码和数据大概率不在 L1、L2 缓存里切换过去之后头几万条指令可能都在缓存缺失cache miss中度过每条都要去内存里捞数据。TLB 更明显它缓存的是虚拟地址到物理地址的映射地址空间一换旧映射基本全废新进程访问内存时要重新做页表遍历page walk每次可能多访问好几次内存。对于工作集大的程序这一串连带损失加起来能达到几十微秒甚至更多远超过切换本身的直接开销。硬件上用 ASID地址空间标识符或 PCID 来缓解 TLB 刷新问题让不同进程的映射可以共存于 TLB 中而不必全清但要彻底消除缓存失效的代价是不可能的。所以调度器设计里有个隐含目标在保证响应时间的前提下尽量减少切换次数别让 CPU 把时间都花在换人上。4.3 怎么观测切换频率几条能直接敲的命令理论讲完怎么知道自己机器上切换是不是过量了Linux 上几个命令就够。# 每秒上下文切换次数看 cs 列 vmstat 1 # 进程级查看自愿切换等 I/O和非自愿切换被抢占 pidstat -w 1 # 统计整机切换事件 perf stat -e context-switches,cpu-migrations -a sleep 5重点关注两组数据。非自愿切换pidstat 里的 nvcswch/s高说明任务是被 CPU 时间到了强行换下来的通常意味着 CPU 争抢严重、线程开太多。自愿切换cswch/s高说明任务在频繁等 I/O 或等锁属于 I/O 密集或锁竞争的信号。那多少算多这得看基线不能一概而论。空载系统每秒几十到几百次很正常中等负载的服务每秒几千到几万次也在合理范围如果观察到每秒几十万次非自愿切换同时系统负载还不高那基本可以断定线程数配置有问题或者某处存在严重的锁竞争。我自己的习惯是先记下低峰期的基线值出问题时对比倍数关系比死记一个绝对阈值靠谱得多。提示如果你想亲手观察切换对性能的影响可以写个小程序开大量线程做纯计算然后逐步增加线程数看吞吐量变化。通常会在某个点之后加线程反而变慢——那个拐点附近就是切换开销开始吃掉收益的地方。5. 动手写一个时间片轮转调度器用数字打破直觉理解了原理最好自己把调度器跑一遍看数据说话。这一节用 Python 实现一个 RR 调度模拟器顺便借os模块看一眼机器核数理解真实系统里并发模型该怎么选。5.1 数据模型把任务抽象成几个字段一个任务在调度器眼里只需要几个关键属性名字、到达时间、需要占用的 CPU 总时间。运行过程中还会派生出现在剩多少、第一次被调度的时间、最终完成时间。from dataclasses import dataclass dataclass class Task: name: str arrive: int # 到达时间 burst: int # 需要的 CPU 总时间 def __post_init__(self): self.remaining self.burst # 剩余需要时间 self.first_run -1 # 首次运行时刻 self.finish -1 # 完成时刻这里用dataclass是为了少写一堆样板代码remaining是 RR 的核心状态——每次被调度它会减少一个时间片的量减到 0 就说明任务完成。5.2 调度循环RR 的核心其实是个队列游戏RR 的逻辑简单到用一段循环就能写清楚但队列的进出时机有几个细节处理不好结果就偏。def schedule_rr(task_list, quantum): # 复制一份避免重复运行污染原始数据 tasks [Task(t.name, t.arrive, t.burst) for t in task_list] tasks.sort(keylambda t: (t.arrive, t.name)) time 0 idx 0 queue [] log [] # 初始时刻已到达的任务先入队 while idx len(tasks) and tasks[idx].arrive time: queue.append(tasks[idx]) idx 1 while queue: cur queue.pop(0) if cur.first_run 0: cur.first_run time run min(cur.remaining, quantum) log.append((time, time run, cur.name)) time run cur.remaining - run # 当前任务运行期间新到达的任务入队 while idx len(tasks) and tasks[idx].arrive time: queue.append(tasks[idx]) idx 1 if cur.remaining 0: queue.append(cur) # 没跑完回到队尾 else: cur.finish time # 跑完了记录完成时刻 return tasks, log有两个约定需要说明。一是新到达任务的入队顺序这里先处理运行期间到达的任务再把没跑完的当前任务放回队尾意味着新来的任务会排在被抢占任务的前面。这个约定更接近公平调度但不同教材处理方式略有差异换一种写法结果会不同。二是一次只处理一个时间片的量run min(cur.remaining, quantum)保证最后一个时间片不会被切得超过实际需要。5.3 跑起来看结果换时间片数字会告诉你答案配上统计和打印就能直观对比不同时间片的效果。def report(tasks, log, quantum): print(f--- 时间片 quantum {quantum} ---) print(执行片段:) for s, e, name in log: print(f [{s:3} - {e:3}] {name}) total_wait total_turn 0 print(任务统计:) for t in sorted(tasks, keylambda x: x.name): turn t.finish - t.arrive wait turn - t.burst total_wait wait total_turn turn print(f {t.name}: 完成{t.finish}, 周转{turn}, 等待{wait}) n len(tasks) print(f 平均等待 {total_wait / n:.2f}, f平均周转 {total_turn / n:.2f}\n) if __name__ __main__: import os print(f本机逻辑核心数: {os.cpu_count()}\n) base [ Task(A, 0, 7), Task(B, 2, 4), Task(C, 4, 1), Task(D, 5, 4), ] for q in (1, 3, 7): tasks, log schedule_rr(base, q) report(tasks, log, q)os.cpu_count()这一行不是装饰。它提醒你一个重要事实模拟器里的CPU永远只有一个虚拟执行单元所以无论开多少任务它们都是并发而非并行。真机上如果cpu_count()返回 4你才能指望 4 个纯计算任务真正同时推进。拿上面四个任务跑一遍结果是这样的时间片 q执行顺序片段平均等待平均周转1A,B,A,B,A,C,B,A,D,B,A,D,B,A,D,A,D5.509.503A,B,A,C,D,B,A,D7.0011.007A,B,C,D4.758.75这个结果可能会让第一次做实验的人有点意外q1 的平均等待并不比 q7 好而 q7 反而是这组任务里最划算的。原因在于这组任务的到达顺序和长度分布恰好对 RR 不友好——长任务 A 先到抢占它反而把短任务不断挤到后面。如果把任务集换成短任务不断到达、长任务一直占 CPU的典型交互负载结论就会反过来