SPOOLing假脱机模拟：输入输出井、守护进程与参数调优

简介：围绕操作系统课程中的Spooling假脱机输入输出机制，这套资料以模拟实现为核心，面向正在学习设备管理、进程同步与I/O缓冲的学生及自学者，也可供课程设计参考。压缩包共11个文件，约279KB，包含Java源程序及编译后的class文件、1份设计报告和4张运行截图；源码对应“两个请求输出进程+一个Spooling输出进程”的进程模型，报告与截图可用于对照输入井、输出井及后台输出流程。已有442人学习，说明其在同类课程设计中具有一定参考度。读者可据此梳理虚拟设备与共享打印机的实现思路，观察进程请求、数据入井、后台取数输出的完整链路，并结合报告理解缓冲区管理与并发调度细节，适合作为操作系统实验的对照材料。

1. 假脱机不是「假的脱机」：一个打印队列怎么把独占设备变成共享设备

spooling 假脱机输入输出模拟技术这几个字，第一次看很容易读成「假的脱机」，其实恰恰相反。它解决的是一个特别具体的问题：打印机、读卡机这类独占设备，同一时刻只允许一个作业占用，十个作业同时要用，就有九个在干等。把作业先落到磁盘上的输入井和输出井，再由两个常驻进程按设备自己的节拍慢慢往外送，用户进程看到的就是一台「永远不忙」的设备。这篇讲的是怎么用几百行模拟程序把这件事跑起来、量出收益，并且知道它在什么规模下会失效、参数该往哪边调。

2. 把 SPOOLing 拆成四个可编程部件：输入井、输出井、缓冲区和守护进程

某公司内网里有五十来号人共用两台打印机，最早的做法是谁要打印谁去抢，结果是一半的提交直接失败，重试三次还失败就得手工再点一遍。换上「先落盘、后统一送设备」的结构之后，提交动作变成一次磁盘写入，几十毫秒就返回，真正慢的那一步交给后台。这套结构拆开来只有四个部件：磁盘上的输入井、磁盘上的输出井、内存里的缓冲区、以及两个常驻的守护进程。想写模拟程序，就得先把这四个部件的边界划清楚，否则代码写出来一定是一团乱麻。

2.1 输入井与输出井：磁盘上的队列为什么不能换成内存里的 list

井（well）在教科书里叫「井管理程序管理的一块磁盘区域」，落到实现上就是一段按定长块切分的存储，输入井存「还没被处理过的作业数据」，输出井存「已经算完但还没送进设备的作业结果」。它和内存队列最大的差别不在速度，而在三件事上：容量、持久性、以及读写双方是不是不同的执行体。

容量这件事最直观。一个并发度二十的系统，单作业数据几 MB 到几十 MB，全塞内存里，光是排队就吃掉几百 MB，遇上大作业直接把进程撑爆。持久性更关键，井在磁盘上，掉电重启之后井里的作业还在，扫一遍索引表就能接着送设备；换成内存 list，一次意外退出全部清零，这是真正意义上的后悔药。第三点是解耦，井的写入方和读出方是两个不同优先级的进程，磁盘天然支持这种「一边写一边读」的模式，内存队列就得自己加锁加条件变量，反而更复杂。

容易混淆的是缓冲区和井。两者都叫「中间存储」，但职责完全不同，做模拟的时候如果把这两个概念混在一个结构里，后面调参会一直算不明白账。

井内部怎么组织，直接决定代码复杂度。常见做法是定长块加位图：整块区域切成 N 个等长块，用一个长度 N 的位图记录每块是空闲还是占用，每个作业再持有一张块号表（索引表），相当于这个作业在井里的「文件分配表」。块大小一般取 1KB 到 4KB，太小则索引表膨胀、元数据开销压过数据本身，太大则最后一个块浪费严重，内部碎片明显。模拟程序里我一般直接用「块数」当单位，不折算成字节，原因是参数实验时 64 块、256 块这种数字比 65536 字节直观得多，扫参数也好看。

井容量怎么估，有个粗算公式：并发作业数 × 平均作业数据块数 × 1.5 的安全系数。比如模拟项目X 里设定 20 个并发、平均每个作业 8 块输出数据，那输出井至少要 240 块，实际取 256 块。这个数不是拍脑袋来的，它决定了后面「井满回退」发生的频率，太小会频繁回退拉长周转时间，大过一个临界点之后收益就趋近于零。

2.2 预输入进程与缓输出进程：两个守护进程的状态机怎么画

四个部件里真正让系统「动起来」的是两个常驻进程。预输入进程（spool-in）负责把数据从慢速输入设备搬进输入井；缓输出进程（spool-out）负责把输出井里的数据搬进设备。它们和用户进程的关系是：用户进程只跟井打交道，永远不直接碰设备。

为什么必须是常驻进程，而不是「用户进程自己写设备」？因为「同一时刻只有一个执行体能操作设备」这条约束，必须由系统里某个统一的角色来执行。让每个用户进程各自去抢，那就退回到最初的争抢模式了。用户进程也不可能一直挂在那里等设备空闲，它的时间是宝贵的，等设备这件事应该由一个专门的、优先级可控的进程来干。

状态机大致是这样一条链：作业提交后处于 CREATED，被预输入进程取走、数据全部落进输入井后变成 READY；处理线程调度到它，进入 RUNNING；算完之后把结果写进输出井，变成 OUT_SPOOLED；缓输出进程把它送进设备、打印完成，变成 PRINTED；最后回收它占用的所有块，变成 DONE。每一条边上都有一个明确的触发条件，也都有一个潜在的阻塞点。

两个阻塞点是整套设计的命门。预输入进程在「输入井满」时阻塞，因为再往里写就没地方放了；缓输出进程在「输出井空」时阻塞，因为没东西可送。这两个阻塞点构成了整条流水线的反压机制：下游慢了，上游自然被顶住，不会无限堆积。但也正因为它们，环形等待的死锁随时可能出现——输入井满导致处理进程停产，处理进程停产导致输出井空，输出井空导致缓输出进程空转，而预输入进程还在等一个永远不会到来的空位。这个问题在第 5 章会单独拆开讲。

优先级上有个经验：缓输出进程的优先级一般要高于预输入进程。原因是输出井满会把所有处理线程全部堵死，整条流水线停摆；而输入井空只是让处理线程暂时闲着，属于「产能闲置」而不是「系统卡死」，两者的严重程度差一个量级。

顺带说清楚「假脱机」这个名字的来历。早期确实是拿一台小型卫星机专门替主机做 I/O，主机只管算，卫星机管读写，那叫真脱机。后来用主机自己的进程模拟这个角色，功能一样但不再需要额外的硬件，于是叫「假」脱机。名字里的「假」说的是实现方式，不是效果。

2.3 模拟选型：多线程、离散事件还是真设备回放

写模拟程序有三条路，选错了后面全是返工。

多线程版最直观，time.sleep一写，设备的串行性、井的阻塞、线程间的唤醒全都真实发生，跑一遍就能看见哪里卡住。代价是时间压不下去，一个作业真要等几十毫秒，跑一千个作业就是几十秒，而且线程调度本身有抖动，两次跑出来数字不一样，做参数扫描会很痛苦。

离散事件版用一个虚拟时钟加一个事件堆，所有 sleep 变成「把事件插入 t + Δ 的时刻」，一次模拟几毫秒跑完，完全可复现，扫一百组参数毫无压力。代价是阻塞和唤醒要自己实现，一不小心就写出一个「看起来对、其实永远不会死锁」的假模型，那这模拟就白做了。

我的做法是两个版本都写，但共用同一套 Well 和 Job 结构。先用多线程版把状态机和阻塞点跑通，这一步的产出不是性能数据，而是「我知道哪一段会卡、卡的时候现场长什么样」；再把同一套状态机搬到虚拟时钟上做参数扫描，这一步的产出才是「参数怎么选」。两版共用数据结构，改动量很小，但能避免拿一个自己都没验证过的模型去指导生产。

3. 用 Python 写一个能跑的 SPOOLing 模拟器：从井结构到调度循环

这一章把上面四个部件落成一个能python3 spool_sim.py直接跑起来的文件。分四步走：先定井和作业控制表的数据结构，再写预输入进程，然后写缓输出进程和处理线程，最后接上主循环和指标埋点。代码不追求工业级健壮，追求的是每一行都能对上上一章的概念，方便你改参数、加埋点、故意制造故障。

3.1 井的空闲块管理与作业控制表的数据结构

先写井。核心是一个位图、一个已用块计数、一把条件变量。条件变量是关键，它让「井满」这件事从「轮询等待」变成「睡到有人释放为止」。

# spool_core.py —— 井与作业控制表 import threading from dataclasses import dataclass, field class Well: """输入井 / 输出井的统一实现：定长块 + 位图分配，带阻塞与反压""" def __init__(self, name: str, blocks: int): self.name = name self.total = blocks # 井的块数，容量上限 self.used = 0 # 已分配块数，和 bitmap 必须始终一致 self.bitmap = [0] * blocks # 0 空闲 / 1 占用 self.cv = threading.Condition() self.peak = 0 # 峰值占用，调参时最该看的一列 self.timeout_cnt = 0 # 井满超时次数 def acquire(self, n: int, timeout=None): with self.cv: # 睡到空闲块够 n 个，或者超时 if not self.cv.wait_for(lambda: self.total - self.used >= n, timeout=timeout): self.timeout_cnt += 1 return None # 井满超时，由调用方决定回退还是报错 got = [] for i in range(self.total): if len(got) == n: break if self.bitmap[i] == 0: self.bitmap[i] = 1 got.append(i) self.used += n self.peak = max(self.peak, self.used) return got # 块号列表，等价于作业的索引表 def release(self, blocks): with self.cv: for b in blocks: self.bitmap[b] = 0 self.used -= len(blocks) self.cv.notify_all() # 必须唤醒，否则等待方永远睡着

total就是井容量，单位是块；timeout决定井满时是硬等还是回退，后面处理死锁全靠这个参数；peak记录整个运行期间的峰值占用，它比平均值有用得多，因为它对应的是「最坏那一刻井差点爆掉」；timeout_cnt是井满回退的累计次数，直接反映井是不是配小了。

分配这里用的是线性扫描位图，复杂度 O(total)，在几百块的规模下完全够用。真要上大规模，换成空闲块链或者分级位图（类似多级页表的思想），把扫描摊到多级上。但在做参数实验的阶段，线性扫描反而更好，因为它慢得均匀，不会让某个时间点的行为突然变快，干扰你对瓶颈的判断。

作业控制表这边，字段不多但每个都有用：

@dataclass class Job: jid: int blocks_in: int # 输入数据占几块 blocks_out: int # 输出数据占几块 prio: int # 越小越优先 seq: int # 提交序号，保证同优先级内 FCFS t_submit: float = 0.0 t_spooled_in: float = 0.0 t_finished: float = 0.0 in_blocks: list = field(default_factory=list) # 输入井占用的块号 out_blocks: list = field(default_factory=list) # 输出井占用的块号

prio和seq这两个字段必须成对出现。只按prio排序，同优先级的作业顺序就取决于底层数据结构的实现细节，表现出来就是打印顺序莫名其妙地乱，这种问题查起来极其费劲。in_blocks和out_blocks分开存，是为了让释放逻辑能精确定位到具体哪块，避免「释放了不属于自己的块」这种低级但要命的错误。

3.2 预输入进程的最小实现

预输入进程要模拟的是「慢速输入设备把数据一块一块搬进井」这个过程，所以每搬一块都要 sleep 一小段时间，这个 sleep 就是设备速率。

import time def spool_in_one(sim, job) -> bool: """把单个作业的全部输入数据搬进输入井，成功返回 True""" held = [] for _ in range(job.blocks_in): blk = sim.well_in.acquire(1, timeout=sim.well_timeout) if blk is None: # 井满超时：已经占的块必须还回去，否则越积越少 sim.well_in.release(held) sim.stats["spool_in_retry"] += 1 return False held.extend(blk) time.sleep(sim.t_block_in) # 输入设备每块耗时，串行不可并发 job.in_blocks = held job.t_spooled_in = sim.now() return True def spool_in_daemon(sim): """预输入进程：到达队列 -> 输入井。井满就退回队首，形成反压""" while not sim.stop: job = sim.pop_arrival(timeout=0.05) if job is None: continue if not spool_in_one(sim, job): sim.push_arrival_front(job) # 退回队首，等井里有空位再试 time.sleep(sim.t_backoff) continue sim.push_ready(job) # 进就绪队列，唤醒处理线程

t_block_in是输入设备搬一块的耗时，改这个值等于换一台快慢不同的设备。well_timeout是井满时最多等多久，设成 None 就是硬等，硬等在法律上讲得通（等井空出来就好），但实践中更容易掩盖死锁：一旦环形等待成立，硬等就是永久的。给一个有限超时加回退，程序不会卡死，但会表现为「作业反复重试、周转时间暴涨」，这个现象反而是一个有用的诊断信号。

「退回队首」这个动作有讲究。如果退回队尾，一个反复失败的作业会不断被别人插到后面，永远轮不到它，形成饥饿；退回队首保证它能优先重试，代价是可能挡住后面的作业一小会儿。两种策略在模拟里都能跑，表现出的差异正好可以用来讨论调度公平性。

spool_in_daemon里没有做优先级排序，因为输入设备本身是串行的，先来先服务是最自然的策略。如果你的模拟场景里输入数据有明显冷热之分，可以在pop_arrival里换成按(prio, seq)取最小。

3.3 缓输出进程与单设备串行化

输出侧比输入侧多一个角色：处理线程。它从输入井取作业、算、把结果写进输出井，然后由缓输出进程负责把输出井里的数据送进打印机。

def worker_loop(sim, wid): """处理线程：输入井 -> 计算 -> 输出井""" while not sim.stop: job = sim.pop_ready(timeout=0.05) # 按 (prio, seq) 取 if job is None: continue job.t_start = sim.now() time.sleep(job.blocks_in * sim.t_cpu) # 模拟计算耗时 held = sim.well_out.acquire(job.blocks_out, timeout=sim.well_timeout) if held is None: sim.well_out.timeout_cnt += 1 sim.push_ready_front(job) # 输出井满，作业退回去 time.sleep(sim.t_backoff) continue job.out_blocks = held sim.push_outq(job) # 进待打印队列 def spool_out_daemon(sim): """缓输出进程：输出井 -> 打印机。设备独占，边打边还块""" while not sim.stop: job = sim.pop_outq(timeout=0.05) # 同样按 (prio, seq) 取 if job is None: continue t0 = sim.now() for b in job.out_blocks: time.sleep(sim.t_block_out) # 打印机每块耗时，串行 sim.well_out.release([b]) # 打完一块立刻还，占用呈锯齿状 job.t_finished = sim.now() sim.printer_busy += sim.now() - t0 sim.done.append(job)

这里有三个点值得单独说。

第一，spool_out_daemon只有一个，这是「设备独占」在代码里的体现。想模拟两台打印机，不用改这个函数，起两个线程、让它们各自对应一台设备、用一个信号量把同名设备串起来就行。但要注意，两台打印机共用同一口输出井的时候，井的释放顺序和打印顺序就没有必然关系了。

第二，「边打边还」是个容易被简化掉、但影响很大的细节。如果等整个作业打完才一次性释放块，输出井的实际占用是阶梯状的，峰值明显偏高；边打边还则是锯齿状，峰值低一截。真实系统里也是这么干的，因为输出井存在的意义就是让数据流动起来，不是当成一个完整作业的暂存区。

第三，sim.push_outq(job)之后，作业就归缓输出进程管了。处理线程绝不能再去碰它的out_blocks，否则就是双重释放。这种「所有权转移」在代码里没有类型系统帮你保证，只能靠约定，所以释放动作必须集中在唯一一处。

3.4 跑起来：主循环、指标埋点和一次完整回放

把上面几块拼起来，加一个 argparse 命令行和一份指标报告，就是一个能直接跑的模拟器。

# spool_sim.py 的主循环部分（省略队列包装和统计口径的细节） if __name__ == "__main__": import argparse, random p = argparse.ArgumentParser() p.add_argument("--jobs", type=int, default=40) p.add_argument("--in-blocks", type=int, default=64) p.add_argument("--out-blocks", type=int, default=64) p.add_argument("--workers", type=int, default=2) p.add_argument("--t-block-in", type=float, default=0.002) # 输入设备每块 p.add_argument("--t-block-out", type=float, default=0.004) # 打印机每块 p.add_argument("--t-cpu", type=float, default=0.001) # 每块计算耗时 p.add_argument("--sched", choices=["fcfs", "prio"], default="prio") p.add_argument("--seed", type=int, default=7) args = p.parse_args() random.seed(args.seed) sim = SpoolSim( in_blocks=args.in_blocks, out_blocks=args.out_blocks, workers=args.workers, t_block_in=args.t_block_in, t_block_out=args.t_block_out, t_cpu=args.t_cpu, sched=args.sched, well_timeout=0.5, ) sim.start() for i in range(args.jobs): sim.submit(Job(jid=i, blocks_in=random.randint(2, 8), blocks_out=random.randint(4, 20), prio=random.randint(0, 3), seq=i)) time.sleep(random.uniform(0.0, 0.02)) # 到达间隔，制造并发 sim.drain_and_stop() # 等流水线彻底排空再停线程 sim.report() # 打印指标

python3 spool_sim.py --jobs 40 --in-blocks 64 --out-blocks 64 \ --workers 2 --sched prio --seed 7

drain_and_stop这个函数不能省。常见错误是主循环提交完作业就立刻置stop=True，此时流水线里还残留着没打完的作业，指标算出来全是半成品，周转时间被系统性低估。正确做法是等「到达队列空、就绪队列空、待打印队列空、且没有线程正持锁」四个条件同时成立再停。

report()输出四组数：平均周转时间（提交到打完）、打印机利用率（忙碌时间 / 总时间）、两个井的峰值占用与超时次数、以及系统吞吐（作业数 / 总时间）。这四组数就是后面调参的全部依据。

跑一次看结果的时候，先别急着看平均周转时间，先看井的超时次数。超时次数是零，说明井容量绰绰有余，加井不会有任何收益；超时次数上百，说明井是瓶颈之一，加井能立刻看到效果。这个判断顺序能省掉大量无效实验。

提示：time.sleep的精度在毫秒级，t_block_out设到 0.0001 这个量级时测出来的时间基本是噪声。做参数实验时把最小耗时控制在 1ms 以上，或者干脆换虚拟时钟版本。

4. 参数怎么调：井大小、块大小、并发度和调度策略的量化对比

模拟器跑通之后，绝大多数人的下一个问题是「这些参数该设多少」。这一章给一套可以照抄的实验方法：先明确每个参数的物理含义，再用固定种子的网格扫描找出拐点，最后学会怎么读结果。

4.1 四个必调参数与它们的物理含义

out_blocks是最常被高估的参数。它只影响「井满回退」发生的频率，不影响设备本身的服务率。把输出井从 64 块加到 1024 块，如果瓶颈本来就在打印机，吞吐一点都不会变，唯一的变化是内存占用涨了十六倍。

workers的边际收益衰减得非常快。第一个处理线程基本吃满单核，第二个能掩盖 I/O 等待，第三个开始就在抢井的锁了。经验上，处理线程数配到「井锁临界区耗时」和「单作业计算耗时」的比值附近就够，再往上加只会让well_out.acquire的等待队列变长。

t_block_out不是你能调的参数，它是设备属性。但它决定了整个系统的理论上限：总输出块数 ×t_block_out就是任何调度策略都突破不了的下限。算这个数只用十秒钟，却能让你一眼看出实测值离天花板还有多少空间，值不值得继续优化。

sched的差别在平均周转时间上看不出来，要看的是长尾。FCFS 下所有作业的等待时间分布比较均匀；优先级调度下高优先级作业飞快，低优先级作业可能等到天荒地老，这个差异在第 6 章会用一条分布曲线量出来。

4.2 用固定种子的网格扫描找出拐点

单次跑出来的数字没有意义，因为有随机抖动。正确做法是固定几个种子、每个配置跑三遍取均值，然后横向比。

# sweep.py —— 参数扫描，输出按平均周转时间排序的前若干组 import itertools, statistics from spool_sim import run GRID = { "in_blocks": [16, 64, 256], "out_blocks": [16, 64, 256], "workers": [1, 2, 4], } SEEDS = (1, 2, 3) # 固定种子，保证不同配置面对同一批作业 rows = [] for combo in itertools.product(*GRID.values()): cfg = dict(zip(GRID.keys(), combo)) samples = [run(seed=s, n_jobs=40, **cfg) for s in SEEDS] rows.append({ **cfg, "tat": statistics.mean(s["avg_turnaround"] for s in samples), "util": statistics.mean(s["printer_util"] for s in samples), "retry": statistics.mean(s["spool_in_retry"] + s["well_out_timeout"] for s in samples), }) rows.sort(key=lambda r: r["tat"]) for r in rows[:8]: print(r)

这段脚本有三个刻意的设计。第一，SEEDS固定，同一批种子意味着不同配置面对的是同一组作业大小和到达间隔，比较才有意义；换种子等于换了考卷，成绩不可比。第二，每个配置跑三遍取均值，压制线程调度的抖动，三遍是最小值，两遍分不清是趋势还是噪声。第三，除了周转时间还输出了retry，因为很多配置的周转时间差异其实来自回退次数，不看这个数就不知道为什么变慢。

n_jobs=40也别乱改。作业数太少，队列还没堆起来就跑完了，测不出井满；作业数太多，单次跑的时间变长，扫一遍网格要等很久。四十个作业、二十毫秒的平均到达间隔，差不多能让队列稳态维持在整个运行周期的一半以上，是个比较平衡的取值。

4.3 结果怎么读：三张曲线和两个反直觉结论

扫完之后把结果画成曲线（哪怕只是在终端里按列打印），看三件事。

第一张是「输出井大小 vs 平均周转时间」。典型的形状是先陡降后走平，拐点出现在「井大到能吸收到达波动」的位置。拐点之后继续加井，曲线几乎完全水平。你在拐点右侧再投入磁盘配额，等于白花钱。

第二张是「处理线程数 vs 吞吐」。第一段上升，第二段走平，有些配置下第三段会轻微下降。下降的那一段就是锁竞争开始压过并行收益的位置，这也是判断「该不该继续加线程」的直接证据。

第三张是「设备耗时 vs 系统吞吐」。这条线是双曲线形状，斜率的倒数就是设备的理论服务率。它更像一把尺子，用来衡量前两张图里你的实测值离天花板还有多远。

两个反直觉的结论值得提前打预防针。

一是「井越大不一定越快」。当井大到一定程度，单个作业在井里的驻留时间变长，作业完成的通知链路变长，反而会让周转时间的方差变大。更常见的情况是井大了之后，回退消失了，但设备前面积压的队列变长了，平均等待时间没降多少，尾部延迟反而更差。

二是「处理线程越多不一定吞吐越高」。处理线程多了，同一时刻抢输出井的线程就多，锁的争用上升，acquire里的notify_all唤醒的线程数也变多，这些都是纯开销。在输出设备是瓶颈的场景下，加处理线程只是在更快地把作业堆到输出井里，然后大家一起等。

5. 排查清单：SPOOLing 模拟里最容易翻车的五个地方

这套结构跑起来不难，难的是跑对。下面五条是我在不同项目里反复见到的现场，每条按「现象 → 原因 → 解决」写。

5.1 跑着跑着所有线程都不动了，CPU 归零

现象：程序启动十几秒后完全静止，top显示进程还在但 CPU 占用为零，日志停在某一行不再输出。

原因：环形等待。输入井满导致预输入进程阻塞，处理线程因为输入井空而阻塞，输出井因为有作业堆积而满导致处理线程无法写入，缓输出进程却在等一个还没进输出井的作业。四个角色各等一个别人

本文还有配套的精品资源，点击获取