操作系统：期中典型题与综合分析

第一步，说明进程需要的状态。 操作系统要准备进程身份与内核记录，建立虚拟地址空间和程序映射，准备用户栈、参数与环境，关联打开文件，设置程序计数器和寄存器等初始上下文，再将进程放入就绪队列。具体内核可以按需装载，不要求创建时把所有程序页都读入物理内存。

第二步，按转换条件作答。

就绪 --调度选中--> 运行
运行 --时间片结束/被抢占--> 就绪
运行 --需要等待I/O或事件--> 阻塞
阻塞 --I/O或事件完成--> 就绪

第三步，串起一次阻塞读。 程序发起读请求，经系统调用进入内核；如果数据尚不可用，内核记录等待条件并把该进程设为阻塞，调度其他进程。设备完成后产生通知，内核使原进程变成就绪。等它再次被调度，才继续执行后续路径。

I/O完成只消除了“现在不能继续”的条件，并没有自动给它CPU。把“唤醒”写成“立即运行”，忽略了就绪队列和其他任务。

评分建议： 创建所需状态4分；四种基本转换4分；解释唤醒不等于立即获得CPU2分。

fork创建子进程，父子从同一个调用返回位置继续，但返回值不同。普通私有内存的逻辑内容得到复制，现代实现可用COW推迟实际数据复制。父子之后更改自己的普通变量，不会自动更改另一方。

exec成功后替换调用进程的程序映像，装入新程序的代码和初始执行环境；PID不因这次替换自动改变，调用之后的旧程序语句不再执行。若调用失败，它才返回错误，需要由旧程序处理。

wait或waitpid针对自己的子进程等待、获取结束状态并回收相关资源。它返回被回收子进程的PID；状态字不是直接的退出码，须先判断 WIFEXITED(status)，再取 WEXITSTATUS(status)。

模式切换是同一执行流在用户态与内核态之间改变权限级别；进程切换要保存一个进程的执行上下文并恢复另一个。系统调用可能进入内核后很快返回同一进程，因此模式切换不必伴随进程切换。

计时器中断使内核即使面对一个不主动让出CPU的用户进程，也能定期重新获得控制权，检查是否调度其他任务；并不是每个计时器中断都必须换进程。

评分建议： 三种API各2分，共6分；模式/进程切换区别2分；计时器的控制权作用2分。

所有任务的到达时刻都是0，所以响应时间等于第一次开始运行的时刻，周转时间等于完成时刻。一般情况仍应写成 $S_i-A_i$、$C_i-A_i$，不能把“到达0”的简化记成定义。

FIFO的时间线为

0          100                    300                              600
|---- A ----|--------- B ----------|--------------- C ---------------|

当前顺序已经从短到长，SJF不会改变它。因此二者都有：

平均响应为 $400/3\approx133.33$，平均周转为 $1000/3\approx333.33$。

RR开始时按A、B、C各运行1，所以首次开始为0、1、2。完成时刻不能直接写成100、200、300：任务在等待轮转时，真实时间仍在推进。

1. 三个任务各运行99次，到297。A还剩1，在297—298完成。
2. B、C随后各运行一次，到300时分别剩100、200。
3. 两者各再运行99次，到498。B剩1，在498—499完成。
4. C最后剩101，独自运行到600完成。

平均响应为1；平均周转为 $(298+499+600)/3\approx465.67$。因此响应更快不代表平均周转更短。

在本题“同时到达、无I/O”的模型中，FIFO队列若已按任务长度非递减排列，SJF可采用相同次序，周转结果相同；所有任务等长是特殊情况。有不同到达时刻或抢占规则时，应重新比较，不能套这个充分条件当作全模型结论。

评分建议： 定义与假设2分；FIFO/SJF结果3分；RR完成时刻与均值4分；相同结果的条件1分。

20+30虽然大于40，但两个块不相邻，不能直接组成一个连续40 B对象。这是外部碎片的表现。若它们在地址上相邻，而且实现允许合并，可在合并后满足请求；“空闲总量”本身不能给出是否可分配的答案。

最佳匹配选择能满足请求的最小可用块。30 B块满足24 B时：

• 若实现成功把6 B分割为可管理的空闲块，它是空闲余块，不是这次已分配块的内部碎片。
• 若6 B不足以容纳最小空闲块或元数据，分配器把整个30 B给出，实际申请未使用的部分才位于已分配块内部。实际大小还可能受对齐和块头影响，不能只看24和30就忽略这些条件。

free(p)通常通过分配器维护的元数据找回该分配块的大小和状态，例如块头、大小类别或其他索引结构。调用者必须传入合法的、尚未释放的分配指针；传入块中间地址不因“分配器有元数据”就合法。

释放块回到用户态分配器，不一定立即使RSS下降；分配器可能保留它以供后续对象复用，只有满足整页或大映射回收等条件时才向内核归还。

评分建议： 不相邻与外部碎片3分；6 B的条件辨析3分；分配器元数据2分；free与向内核归还的区别2分。

页大小为 $2^{12}$ B，所以偏移12位，VPN有 $32-12=20$ 位。单级表的项数为 $2^{20}$，总空间

每页能放 $4096/4=1024=2^{10}$ 个表项，因此二级索引为10位，一级索引也为10位：

| 一级索引10位 | 二级索引10位 | 页内偏移12位 |

VPN0和1都落在第一个下级页表；VPN1024落在第二个下级页表。故需要1张顶级表＋2张下级表，共3页，即12 KiB。三个数据页另外占12 KiB，不能混入“页表空间”的答案。

TLB未命中且查找成功时，先读PDE，再读PTE，最后读数据，共3次主存访问。持有根表基地址的寄存器不是把整张顶级表缓存起来，不能凭它把PDE读取次数删掉。若查找中途发现无效项，或题目加入缓存，计数会改变。

命中耗时 $10+100=110$ ns；未命中但无缺页时为 $10+3\times100=310$ ns。所以

这里的TLB未命中不包含磁盘I/O。若题目另给缺页率 $p$ 与完整缺页服务时间 $T_f$，应按给定口径组合，例如 $EAT=(1-p)T_{\mathrm{normal}}+pT_f$；不能把毫秒和纳秒直接相加。

评分建议： 位数与单级大小3分；两级表数2分；三次访存2分；命中/未命中分支及EAT3分。

FIFO只在新页装入时改变装入队列；命中不改变“谁最早装入”。LRU每次访问都更新最近性。下面FIFO队列按最早装入→最近装入，LRU队列按最久未用→最近使用排列，不代表物理页框编号。

FIFO缺页7次，LRU缺页6次。关键分歧发生在第5次：A刚被访问过，但仍然是FIFO里最早装入的页。

若该不驻留页是合法映射，内核要保存故障上下文，检查地址和权限，取得空闲页框；必要时选择牺牲页并处理脏页写回；从文件或交换区调入所需内容，更新页表与相关TLB状态，恢复进程执行。需要I/O等待时，故障进程可阻塞，完成后先变为就绪。

引起异常的取指、读或写还没有完成，因此应重试原指令。直接执行下一条会跳过程序应有的操作。真实架构的精确异常机制负责让软件可以恢复，不能把所有异常都当成可修复缺页。

评分建议： FIFO/LRU追踪与计数6分；区分命中对队列的影响1分；缺页机制2分；重试原因1分。

把三处调用按源码位置记为F1、F2、F3。&&和||都有短路规则，且左操作数先求值。父进程从 fork得到正数，逻辑上为真；子进程得到0，为假。

1. F1的父分支为真，才执行F2。F1的子分支为假，跳过F2。
2. F1父、F2父：真 && 真为真，所以跳过 ||右边的F3，产生1条最终执行路径。
3. F1父、F2子：真 && 假为假，执行F3，F3产生父、子两条路径。
4. F1子：左边整体为假，执行F3，又产生父、子两条路径。

原进程
├─ F1父
│  ├─ F2父：跳过F3 → 1个
│  └─ F2子：执行F3 → 2个
└─ F1子：跳过F2，执行F3 → 2个

总共 $1+2+2=\boxed5$ 个进程，包括原进程在内。每条最终路径恰好到达一次 write，所以输出5个 X。谁先输出由调度决定，但这5个相同字节组成的内容都是 XXXXX。源码有三处 fork，运行过程中实际执行F1一次、F2一次、F3两次，共成功创建4个新进程。

while(wait(NULL)>0)让每个进程回收自己的子进程；没有子进程时最终返回-1，并不使它少执行前面的输出。不能用这行去等待任意兄弟或父进程。

评分建议： 短路条件3分；进程树及5个总数4分；输出次数与调度边界2分；等待对象1分。

子进程先写字节C，然后成功 exec。此时它仍是同一个子PID，但执行的程序已经变为 echo，所以接下来输出 E\n。原程序里的F和 _exit(7)不再执行。

父进程的 waitpid(p,...)直到该子进程结束才成功返回，因此P行位于子进程完成之后。输出为

CE
P:1:0

其中第一个1来自 w==p：等待返回了预期子PID。它不是实际PID总等于1。第二个0来自 echo的正常退出码；退出码需要通过状态宏取得，不能把 status原值或 waitpid返回值直接当成退出码。

若另行改变题设，使 execl失败，才会执行F和 _exit(7)，父进程可观察到退出码7。这个失败分支不能与成功分支的 E\n同时出现。

评分建议： exec成功替换与F不可达3分；输出和等待顺序3分；返回PID与退出状态的区别3分；成功/失败路径分离1分。

open在fork之前发生一次，初始偏移为0。fork复制父进程的描述符表引用，父子各自的 fd指向同一个内核打开文件描述，因此共享当前偏移。

1. 子进程先读取 ab，共享偏移从0变成2；写出 ab。
2. 子进程关闭自己的引用并退出，父进程的引用仍有效。
3. 父进程的等待结束后从偏移2读取 cd，共享偏移变成4；写出 cd。

最终字节为 abcd，无换行。子进程中的用户数组 b与父进程的 b是私有内存，父进程得到 cd不是“子进程把b数组改好了”，而是因为自己的读请求使用了已经前进的文件偏移。

若题目改成父子分别重新 open同一文件，各自的新打开文件描述通常有独立初始偏移0，则都可读到 ab，在仍保留子先父后的等待条件下输出 abab。不能仅凭描述符整数数值相同或不同判断是否共享偏移。

评分建议： 共享内核打开文件描述3分；偏移0→2→4和输出3分；关闭不影响另一方引用2分；重新open的区别2分。

页大小16为 $2^4$，所以低4位是偏移，高4位是VPN。四个地址偏移都为 0xB=11，VPN依次为1、2、3、4。

所以输出为 91 -2 -3 -1。

不能在看到PTE的PFN字段后立即拼地址：不驻留项的字段可能表示后备位置而不是可访问页框；无效项也不能当作PFN0使用。本程序的-1/-2/-3是为了教学而自定义的分类，真实机器可能把多种原因编码进同一种页故障异常的错误码，内核再作区分。

若只读状态来自COW，内核还可能根据区域语义为写者创建私有副本后重试；若它是逻辑上真正只读的代码映射，则没有这个授权。仅凭“写保护触发异常”不能断定一定终止或一定复制。

这些函数只读同一张常量表，没有互相影响的副作用，所以C语言未规定函数实参求值顺序不会改变本题四个数值；不要把这种情形与多个实参同时修改同一对象混为一谈。

评分建议： 位数拆分2分；四个结果各1分，共4分；状态先于拼地址2分；COW与真正只读边界2分。

输出为

C:100,200
P:300

fork后子进程的初始 x为100，修改后为200；父进程自己的 x改为300。子进程打印并明确刷新后退出，父进程等待其结束才打印，所以这里顺序确定。没有 waitpid时，变量值仍然各自变化，但不能默认C行先出现。

逻辑上，父子拥有独立的私有地址空间。实现上，COW可以使双方暂时映射相同的只读物理页，首次写入时由内核为写者提供私有副本。这样既保留了逻辑复制语义，又避免立刻复制全部物理内存。

相同虚拟地址不证明共享可写对象；反过来，两个进程也可以通过显式共享映射访问同一个可写对象。题目必须区分普通私有变量与共享内存。

fputs("A",stdout)先把A放进用户态stdio缓冲。fork复制了包含缓冲状态的用户地址空间，但缓冲中存在一份A，不等于它已经写到了输出目标。

子进程直接 _exit(0)，不刷新继承的stdio缓冲，也不再访问该流；因此它不输出自己的A副本。父进程继续把B与换行追加到自己的缓冲，正常从main返回时刷新，最终得到 AB\n。

exit或main正常返回与 _exit的一个重要差异，就是前者会进行stdio刷新等用户态清理，后者不执行这套清理。若把子进程也改成正常退出，常见Unix教材缓冲模型下会出现继承缓冲被多次刷出的现象；但涉及父子共同使用继承的stdio流时，具体可移植行为还受流状态和多句柄协调规则约束，不应把未说明的终端、重定向、缓冲和刷新条件藏起来，再宣称唯一输出。

实践上，fork前刷新已有输出，或在子分支用适当的低层写入并在失败路径 _exit，有助于避免重复刷新。printf调用次数、实际系统写入次数和最终字节数要分别分析。

原程序中的 free(NULL)合法，不做任何事；成功分配后的合法下标为0和1，所以原程序打印9，再释放对象。

“程序这次没有崩溃”是一次观察，不能作为语言层面合法性的证明。普通页面保护通常按页与权限工作，不知道一个 malloc对象的精确边界；越界也可能撞上未映射页而触发异常，故是否立即失败取决于布局和运行环境。

调试器能在故障处检查状态，但不会自动证明没有泄漏；内存检查器可以对分配、释放和访问进行跟踪，仍应结合其覆盖范围。题目若明确存在未定义行为，答案应指出原因，不应替编译器和运行时发明一个“必然输出”。

设四行对应页0、1、2、3。A的页序列为

0 0 0 0 | 1 1 1 1 | 2 2 2 2 | 3 3 3 3

每行第一次访问缺页，随后三次都命中，共4次缺页。

B的页序列为

0 1 2 3 | 0 1 2 3 | 0 1 2 3 | 0 1 2 3

只有1个页框，每次下一页都不同于当前页，16次访问全部缺页。这里无论选择FIFO还是LRU，都只有一个可淘汰对象，结果相同。

这说明局部性来自“在短时间内复用哪些页”，不能只看两段代码做了相同次数的赋值。若改变页框数、页大小、数组布局或访问类型，必须重新生成引用序列，不能背“按列必为16次缺页”。

第19章TLB测量作业与本题相关但不相同：TLB容量限制的是地址转换缓存，页面是否驻留是另一层问题。遍历超过TLB覆盖范围可能增加TLB未命中，不意味着每次都发生需要外存I/O的缺页。