《操作系统》第一学期期末试卷A (精选08)

一、选择题（每题 1 分，共 25 分）

main() { int x; while((x = fork()) == -1); if(x == 0) printf("a"); else printf("b"); printf("c"); }

上面程序执行过程中，可能的输出结果有（）

Ⅰ.abcc Ⅱ.bcac Ⅲ.bacc Ⅳ.acbc Ⅴ.cabc Ⅵ.abc

A．Ⅰ，Ⅱ，Ⅲ，Ⅳ B. Ⅰ，Ⅱ，Ⅲ，Ⅴ

C．Ⅳ，Ⅴ，Ⅵ D. Ⅱ，Ⅲ，Ⅳ，Ⅴ

查看答案与解析

答案：A

解析： 本题考查进程创建与并发执行。

第一步：分析 fork() 的返回值fork() 系统调用用于创建子进程。

在父进程中，返回子进程的 PID（大于 0）。
在子进程中，返回 0。
若出错则返回 -1。

第二步：分析控制流while((x = fork()) == -1); 确保成功创建进程。

子进程中 x == 0，执行 if 分支：printf("a");，接着执行 printf("c");。因此子进程的输出顺序一定是 a -> c。
父进程中 x > 0，执行 else 分支：printf("b");，接着执行 printf("c");。因此父进程的输出顺序一定是 b -> c。

第三步：并发执行与输出交织 父子进程并发执行，它们的输出字符可能会交织在一起，但必须满足各自的内部顺序（a 在 c 前，b 在 c 前）。

Ⅰ. abcc：顺序为 a (子), b (父), c (子/父), c (父/子)。满足顺序。
Ⅱ. bcac：顺序为 b (父), c (父), a (子), c (子)。满足顺序。
Ⅲ. bacc：顺序为 b (父), a (子), c (父/子), c (子/父)。满足顺序。
Ⅳ. acbc：顺序为 a (子), c (子), b (父), c (父)。满足顺序。
Ⅴ. cabc：第一个字符是 c，由于 c 必须在 a 或 b 之后，所以不可能第一个输出。
Ⅵ. abc：总共只有 3 个字符，由于父子进程都会输出 c，最终必然有 4 个字符。

综上，可能的输出结果有 Ⅰ、Ⅱ、Ⅲ、Ⅳ。

难度: ⭐⭐⭐ 考点: #进程管理 #fork #并发执行

💡 学习锦囊

📖 相关公式与知识点:

fork() 系统调用返回两次。
并发进程的执行顺序是不可预测的（异步性）。

思路分析

画出父子进程的执行路径，确定每个进程必须打印的字符顺序，然后将它们进行合理的归并排序（拓扑排序）。

易错点

混淆 fork() 在父子进程中的不同返回值。
忽略父子进程都会执行 if-else 之后的 printf("c");。

🔄 举一反三

若将程序中的 printf("c"); 移入 if-else 中，子进程打印 "a"，父进程打印 "b"，输出结果可能是什么？
查看练习答案与解析
答案：ab 或 ba解析：此时两个进程各打印一个字符，由于并发执行，顺序可能是 ab 或 ba。

在 7 个生产者、6 个消费者共享容量为 5 的缓冲区的生产者-消费者问题中，互斥使用的缓冲区的信号量初值为（）。

A．7 B. 6 C. 5 D. 1

查看答案与解析

答案：D

解析： 本题考查信号量的初值设置。

第一步：明确信号量的作用 题目中提到“互斥使用”，意味着在任意时刻，只允许一个进程（生产者或消费者）进入临界区访问缓冲区。

第二步：确定互斥信号量的初值 实现互斥的信号量（通常命名为 mutex）其初值一般设置为 1。当一个进程进入临界区时执行 $$P(mutex)$$ ，初值减 1 变为 0；其他进程再尝试进入时会被阻塞。

难度: ⭐ 考点: #信号量 #进程同步 #互斥

💡 学习锦囊

📖 相关公式与知识点:

互斥信号量初值一般为 1。
资源信号量（如空闲缓冲区数）初值一般为资源总量（本题中为 5）。

思路分析

看到“互斥”二字，信号量初值必然是 1。

🔄 举一反三

在该问题中，表示缓冲区中“空闲空间”的信号量初值应为多少？
查看练习答案与解析
答案：5 解析：缓冲区的初始状态是完全空的，因此空闲空间数量等于缓冲区的总容量，即 5。

Linux 系统的管道通信中，如果读端关闭，则写端再进行写入操作会得到什么结果？（）

A. 写入操作会阻塞
B. 写入操作会成功
C. 写端会收到信号通知读端已关闭
D. 写入操作会导致进程终止，并发送 SIGPIPE 信号

查看答案与解析

答案：D

解析： 本题考查 Linux 管道通信机制。

第一步：分析管道的读写规则 管道是一种半双工的通信方式。

如果写端关闭，读端读取完管道内的数据后，再次 read 会返回 0（表示文件结束符 EOF）。
如果读端关闭，写端继续 write，内核会向写进程发送 SIGPIPE 信号。

第二步：分析信号的默认处理 对于 SIGPIPE 信号，系统的默认处理动作是终止接收到信号的进程。

难度: ⭐⭐ 考点: #管道通信 #信号机制 #SIGPIPE

💡 学习锦囊

📖 相关公式与知识点:

管道读端关闭，写端写数据 -> 产生 SIGPIPE 信号 -> 默认终止进程。

思路分析

管道通信需要两端存在。没有读者的管道写入是无意义的，操作系统采用强力手段（信号终止）来处理这种异常。

🔄 举一反三

如果写端不想因为读端关闭而被终止，应该怎么做？
查看练习答案与解析
答案：捕获或忽略 SIGPIPE 信号。解析：在代码中使用 signal(SIGPIPE, SIG_IGN) 忽略该信号，此时 write 操作会失败并返回 -1，同时设置 errno 为 EPIPE。

在多处理器系统中，自旋锁相比于信号量的一个主要缺点是（）

A. 自旋锁更容易实现
B. 自旋锁不消耗 CPU时间等待
C. 自旋锁会导致忙等待，浪费 CPU资源
D. 自旋锁不能用于实现互斥

查看答案与解析

答案：C

解析： 本题考查自旋锁与信号量的区别。

第一步：理解自旋锁的工作原理 自旋锁（Spinlock）在获取锁失败时，不会让进程进入睡眠状态，而是让 CPU 一直循环检查锁的状态（即忙等待，Busy Waiting）。

第二步：分析优缺点

优点：避免了进程上下文切换的开销，适用于锁持有时间极短的场景。
缺点：如果锁被持有的时间较长，自旋等待的 CPU 会一直空转，极大地浪费了 CPU 资源。信号量则会让进程睡眠，不占用 CPU。

难度: ⭐ 考点: #自旋锁 #信号量 #忙等待

💡 学习锦囊

📖 相关公式与知识点:

自旋锁 vs 信号量：忙等待 vs 睡眠等待。

思路分析

自旋 = 旋转 = 循环等待 = 消耗 CPU。

🔄 举一反三

在单处理器系统中，自旋锁是否适用？
查看练习答案与解析
答案：通常不适用（除非抢占式内核且锁持有时间极短）。解析：在单处理器上，如果自旋锁忙等待，持有锁的进程无法运行来释放锁，导致死锁或资源严重浪费。

计算机中有 8 台打印机，K 个进程竞争使用，每个进程最多需要 3 台打印机，该系统可能会发生死锁的 K 最小值是（）

A. 5 B. 4 C. 3 D. 2

查看答案与解析

答案：B

解析： 本题考查死锁预防中的资源分配公式。

第一步：分析发生死锁的极端情况 每个进程最多需要 $$Max = 3$$ 台打印机。为了让它们尽可能卡住，我们可以给每个进程分配 $$Max - 1 = 2$$ 台。

第二步：建立资源不等式 如果有 $$K$$ 个进程，它们持有的资源总数为 $K \times (3 - 1) = 2K$ 。此时，如果系统只剩 0 台资源，且所有进程都在请求最后 1 台，就会发生死锁。也就是说，当资源总数 $R < K \times (Max - 1) + 1$ 时，可能会死锁。

第三步：代入数据计算 已知 $$R = 8, Max = 3$$ 。不发生死锁的条件是： $8 \geq K \times (3 - 1) + 1 \Rightarrow 8 \geq 2K + 1 \Rightarrow 7 \geq 2K \Rightarrow K \leq 3.5$ 。即最大安全进程数 $$K = 3$$ 。当 $$K = 4$$ 时，资源分配为 2, 2, 2, 2，总共 8 台，全部耗尽，每个进程都还缺 1 台，产生死锁。

难度: ⭐⭐ 考点: #死锁预防 #资源分配

💡 学习锦囊

📖 相关公式与知识点:

保证不发生死锁的条件： $R \geq \sum (Max_i - 1) + 1$ 。

思路分析

用“最坏情况”来思考：每个进程都拿到“差一个就满足”的数量，如果此时资源用尽，就会死锁。

🔄 举一反三

假设有 10 个资源，每个进程需要 4 个，最大不发生死锁的进程数是多少？
查看练习答案与解析
答案：3 解析： $10 \geq K \times (4 - 1) + 1 \Rightarrow 10 \geq 3K + 1 \Rightarrow 9 \geq 3K \Rightarrow K \leq 3$ 。

当操作系统完成用户程序请求的“系统调用”功能后， CPU 将会（）。

A. 维持在用户态 B. 维持在内核态 C. 从用户态转到内核态 D. 从内核态转到用户态

查看答案与解析

答案：D

解析： 本题考查操作系统运行状态的切换。

第一步：理解系统调用的执行过程 当用户程序需要操作系统提供服务（如读写文件、创建进程）时，会通过系统调用（System Call）进入操作系统。

系统调用的执行必须在内核态（Kernel Mode）下进行，以访问受保护的硬件资源。

第二步：分析状态转换

用户程序发起系统调用时，CPU 从用户态转到内核态。
操作系统完成系统调用功能后，需要返回用户程序继续执行，此时 CPU 必须从内核态转回到用户态。

难度: ⭐ 考点: #系统调用 #内核态 #用户态

💡 学习锦囊

📖 相关公式与知识点:

状态转换：用户态 $\to$ 内核态（通过中断/异常/系统调用）；内核态 $\to$ 用户态（执行特权指令如返回）。

思路分析

系统调用是用户态进入内核态的唯一合法途径，执行完毕后自然要“原路返回”用户态。

🔄 举一反三

下列哪项操作会导致 CPU 从用户态切换到内核态？ A. 执行加法指令
B. 发生缺页中断
C. 释放动态内存
D. 访问用户栈
查看练习答案与解析
答案：B 解析：中断和异常（如缺页中断）会强制 CPU 进入内核态进行处理。

下列选项中,在用户态执行的是（）。

A . 命令解释程序 B . 缺页处理程序
C. 进程调度程序 D. 时钟中断处理程序

查看答案与解析

答案：A

解析： 本题考查操作系统核心组件的运行状态。

第一步：区分用户态与内核态程序

内核态：操作系统内核核心功能的执行状态，具有访问硬件 and 特权指令的权限。
用户态：普通应用程序 and 非核心系统服务的运行状态。

第二步：逐项分析

A. 命令解释程序：即 Shell（如 bash），它是运行在用户空间的一个应用程序，负责解析用户命令并调用系统调用。
B. 缺页处理程序：属于内存 management 的核心功能，涉及物理内存分配，必须在内核态执行。
C. 进程调度程序：负责 CPU 资源的分配，涉及特权指令，必须在内核态执行。
D. 时钟中断处理程序：响应硬件时钟中断，属于中断处理，必须在内核态执行。

难度: ⭐⭐ 考点: #用户态 #内核态 #命令解释程序

💡 学习锦囊

📖 相关公式与知识点:

常见的内核态程序：中断处理、系统调用处理、核心算法（调度、内存 management）。
常见的用户态程序：编译器、文本编辑器、数据库管理系统、Shell。

思路分析

寻找最“接近用户”的那个程序，Shell 是用户与操作系统交互的界面，显然是用户态程序。

🔄 举一反三

操作系统中，负责将逻辑地址转换为物理地址的地址映射机制通常在什么态下运行？
查看练习答案与解析
答案：内核态（或硬件 MMU）解析：地址映射涉及页表操作，属于特权操作，由硬件 MMU 自动完成，相关页表维护由内核态代码负责。

设系统中有 3 个进程 P1、P2、P3，它们分别需要资源 R 的数量为 2、3、4，则系统不会发生死锁的最少资源数为（）。

A. 6 B. 7 C. 8 D. 9

查看答案与解析

答案：B

解析： 本题考查死锁避免中的资源数下界计算。

第一步：计算最坏情况 当每个进程都已获得"所需资源数 - 1"个资源，但都还差 1 个才能运行完毕时，系统处于最危险的死锁边界：

P1 已分配 1 个（还需 1 个）
P2 已分配 2 个（还需 1 个）
P3 已分配 3 个（还需 1 个）

此时共分配 $$1 + 2 + 3 = 6$$ 个资源，所有进程都无法继续。

第二步：多加 1 个资源打破僵局 若系统再增加 1 个资源（共 7 个），则至少有一个进程可以获得所需资源并运行完毕，释放资源后其他进程也能依次完成。

因此，不会发生死锁的最少资源数为 $$6 + 1 = 7$$ 。

难度: ⭐⭐ 考点: #死锁避免 #资源分配 #最坏情况分析

💡 学习锦囊

📖 相关公式与知识点:

不发生死锁的最少资源数 = $\sum_{i=1}^{n}(Max_i - 1) + 1$ 。

思路分析

让所有进程都处于"差一个就能完成"的状态，此时再多给一个资源即可打破死锁。

🔄 举一反三

系统中有 4 个并发进程，每个进程最多需要 3 台同类资源，则系统不会发生死锁的最少资源数为（）。
查看练习答案与解析
答案：9 解析：最坏情况每个进程已分配 2 台，共 $4 \times 2 = 8$ 台，再加 1 台即可，共 9 台。

Linux 系统的整体式内核结构具有的特点是（）。

Ⅰ. 较高的效率； Ⅱ. 较高的可靠性；

Ⅲ. 系统灵活性好； Ⅳ. 较强的可扩展性；

A. 仅Ⅰ、Ⅱ B. 仅Ⅰ、Ⅲ

C. Ⅰ、Ⅱ、Ⅲ D. Ⅱ、Ⅲ

查看答案与解析

答案：B

解析： 本题考查宏内核（整体式内核）与微内核的特点对比。

第一步：分析“宏内核”的设计理念 Linux 采用宏内核设计，将进程管理、内存管理、文件系统、设备驱动等所有服务都集成在一个巨大的内核地址空间中。

第二步：逐项评估

Ⅰ. 较高的效率：正确。模块间通信通过直接的函数调用实现，避免了上下文切换的开销。
Ⅱ. 较高的可靠性：错误。由于缺乏隔离，任何一个模块崩溃都可能导致整个系统崩溃（微内核可靠性更高）。
Ⅲ. 系统灵活性好：正确。Linux 引入了可加载内核模块（LKM）机制，允许在运行时动态增删功能。
Ⅳ. 较强的可扩展性：相比于微内核的即插即用，宏内核的可扩展性较弱。

因此，只有 Ⅰ 和 Ⅲ 符合。

难度: ⭐⭐ 考点: #宏内核 #微内核 #操作系统结构

💡 学习锦囊

📖 相关公式与知识点:

宏内核：高效率，低隔离性（可靠性相对低）。
微内核：低效率（IPC开销大），高隔离性（高可靠性）。

思路分析

通过排除法，已知宏内核可靠性不如微内核，排除含有 Ⅱ 的选项（A, C, D），直接得出 B。

🔄 举一反三

下列哪个操作系统结构最符合“高可靠性、高可扩展性”的理论特征？
查看练习答案与解析
答案：微内核结构（Microkernel）解析：微内核将服务移至用户态，通过消息传递通信，故障隔离性好，易于扩展。

在 Linux 中，以下哪种文件类型不能创建硬链接？

A. 普通文件 B. 目录文件

C. 设备文件 D. 所有文件类型都可以

查看答案与解析

答案：B

解析： 本题考查 Linux 文件系统的硬链接规则。

第一步：理解硬链接的本质 硬链接是指向文件索引节点（Inode）的多个目录项。

第二步：分析目录硬链接的限制 Linux 不允许普通用户对目录文件创建硬链接。

原因：为了防止在文件系统的目录树中产生环路（Loops），导致系统遍历目录（如 find 命令）时陷入死循环。

难度: ⭐ 考点: #硬链接 #文件系统 #Inode

💡 学习锦囊

📖 相关公式与知识点:

硬链接不能跨文件系统，不能对目录创建。
软链接（符号链接）可以跨文件系统，可以对目录创建。

思路分析

记住硬链接的两大铁律：不可跨分区、不可链目录。

🔄 举一反三

软链接（符号链接）是否可以指向一个目录？
查看练习答案与解析
答案：可以解析：软链接存储的是目标文件的路径名，不会导致底层 Inode 环路问题，因此支持对目录创建。

某系统采用双缓冲区连续传送磁盘上的一组数据，设从磁盘将数据传送到缓冲区所用的时间为 T1，将缓冲区中的数据传送到用户区所用的时间为 T2（假设 T2 远小于 T1），CPU处理数据所用的时间为T3且T3小于T1，则处理该数据，系统所用的总时间为（）。

A. $\mathbf { T 1 + T } 2 \mathbf { + } \mathbf { T } 3$ B. max(T2, T3)+T1

C. max (T1, T3)+T2 D. max(T1, T2+T3)

查看答案与解析

答案：D

解析： 本题考查双缓冲区的性能计算。

第一步：理解双缓冲区的工作原理 双缓冲区允许 I/O 设备（磁盘）与 CPU 并行工作。当磁盘向缓冲区 A 输入数据时，CPU 可以从缓冲区 B 处理数据。

第二步：分析流水线处理过程 假设系统连续传送 $$n$$ 个数据块。

第一块数据从磁盘读入缓冲区需要 $$T1$$ 。
从第二块开始，磁盘读入操作（ $$T1$$ ）与上一块数据的【传送到用户区（ $$T2$$ ）+ CPU 处理（ $$T3$$ ）】是并行进行的。
因此，处理每个后续数据块的有效节拍取决于这两者中较慢的一个，即 $\max(T1, T2+T3)$ 。

综上，系统所用的总时间主要受流水线节拍控制，答案为 D。

难度: ⭐⭐⭐ 考点: #双缓冲区 #I/O管理 #流水线分析

💡 学习锦囊

📖 相关公式与知识点:

单缓冲区每块处理时间： $\max(T1, T3) + T2$ 。
双缓冲区每块处理时间： $\max(T1, T2+T3)$ 。

思路分析

双缓冲区的精髓在于“读入”与“传出+处理”完全重叠，取二者最大值。

🔄 举一反三

在该题背景下，若采用单缓冲区，处理该数据的总时间公式是什么？
查看练习答案与解析
答案： $\max(T1, T3) + T2$ 解析：单缓冲区在读入时不能同时传出，数据传输到用户区必须独立占用时间，因此公式为 $\max(T1, T3) + T2$ 。

使用 SPOOLing 技术实现共享打印机时，若有进程请求打印操作，系统不会为进程做的工作是（）。

A.将用户要打印的数据保存到输出井
B.为请求进程分配打印机
C.为打印请求填写打印请求表
D.从输出井中提取数据进行打印

查看答案与解析

答案：B

解析： 本题考查 SPOOLing（假脱机）技术。

第一步：理解 SPOOLing 的核心思想 SPOOLing 技术通过在磁盘上建立“输入井”和“输出井”，将独占设备（如打印机）改造为共享的虚拟设备。

第二步：分析打印请求的处理流程 当进程请求打印时：

系统不会直接把物理打印机分配给该进程（B 错误）。
系统会把要打印的数据存入磁盘的输出井（A 正确）。
为进程建立打印请求表并挂入打印队列（C 正确）。
真正的打印机在空闲时，由守护进程从输出井中提取数据进行物理打印（D 正确）。

难度: ⭐⭐ 考点: #SPOOLing #虚拟设备 #I/O管理

💡 学习锦囊

📖 相关公式与知识点:

SPOOLing 系统组成：输入井/输出井、输入缓冲区/输出缓冲区、输入进程/输出进程。

思路分析

虚拟化技术的核心就是“欺骗”进程，让进程以为自己独占了打印机，实际上进程根本没有接触到物理设备。

🔄 举一反三

SPOOLing 技术主要解决了独占设备利用率低的问题，它属于哪种操作系统功能？
查看练习答案与解析
答案：I/O 设备管理（虚拟设备管理）
解析：SPOOLing 是在共享设备（如磁盘）上模拟独占设备（如打印机）的假脱机技术，属于 I/O 设备管理的核心部分。

当系统中的通道数量较少时，可能会产生瓶颈现象，导致整个系统吞吐量的下降。下面（）不是解决此问题的有效方法。

A. 增加一些硬件缓冲区

B. 采用虚拟设备技术

C. 提高 CPU 的速度

D. 增加设备与通道之间的通路

查看答案与解析

答案：C

解析： 本题考查 I/O 通道瓶颈问题。

第一步：明确瓶颈的本质 通道是负责控制 I/O 设备与内存间数据交换的硬件。通道数量少导致“I/O 瓶颈”，即 I/O 速度跟不上，而非计算速度不足。

第二步：评估解决方案

A. 增加硬件缓冲区：可以平滑 I/O 突发流量，减轻通道压力。
B. 采用虚拟设备技术：如 SPOOLing，利用磁盘作为中介，提高设备并行度。
D. 增加设备与通道之间的通路：采用多道程序设计中的“交叉通道”或多通路技术，让设备可以通过多个通道访问内存，直接解决路径不足问题。
C. 提高 CPU 速度：瓶颈在 I/O 设备与通道，提升 CPU 算力无法加快 I/O 传输，是无效的。

难度: ⭐ 考点: #通道技术 #I/O瓶颈

💡 学习锦囊

📖 相关公式与知识点:

设备控制器连接设备，通道连接设备控制器。

思路分析

“头痛医头，脚痛医脚”。I/O 问题要靠优化 I/O 架构来解决，升级 CPU 属于南辕北辙。

🔄 举一反三

在设备、控制器、通道、总线组成的 I/O 架构中，它们之间的控制关系是怎样的？
查看练习答案与解析
答案：CPU $\to$ 通道 $\to$ 控制器 $\to$ 设备。
解析：掌握 I/O 硬件的四层控制路径，即 CPU 负责发送通道程序指令，通道指挥控制器，控制器驱动具体设备进行 I/O 操作。

在操作系统中，哪个组件负责将 I/O 请求翻译成设备能理解的命令？（）

A. 用户空间的 I/O 库函数

B. 设备独立性软件

C. 设备驱动程序

D. 文件系统

查看答案与解析

答案：C

解析： 本题考查 I/O 软件的层次结构。

第一步：回顾 I/O 软件层次 操作系统通常将 I/O 软件分为四层：

用户层 I/O 软件（如库函数）
设备独立性软件（提供统一接口）
设备驱动程序（具体硬件相关的适配）
中断处理程序

第二步：定位翻译职责 由于各种硬件设备的控制命令千差万别，设备驱动程序正是为了屏蔽这种差异而存在的。它接收上层下达的抽象请求，并将其转换为特定硬件能够识别的底层控制命令（如操作寄存器）。

难度: ⭐ 考点: #I/O软件层次 #设备驱动程序

💡 学习锦囊

📖 相关公式与知识点:

设备独立性软件实现：逻辑设备名到物理设备名的映射、设备分配与回收、缓冲区管理。

思路分析

驱动程序就是硬件的“翻译官”。

🔄 举一反三

负责实现“逻辑设备名到物理设备名映射”的是哪一层 I/O 软件？
查看练习答案与解析
答案：设备独立性软件
解析：逻辑设备到物理设备的转换通常需要查表，由操作系统为了向用户屏蔽物理特性而提供的设备独立性软件来负责处理。

某文件系统中，盘块大小为 4KB，盘块号占用 4B。文件系统采用混合索引，每条 FCB中的物理地址字段包含 10 条直接索引，3 条 1 级索引，1 条 4 级索引，那么在该系统中，可以创建的最大文件大小（）？

A. 约 28MB

B. 约 4GB

C. 约 4TB

D. 约 4PB

查看答案与解析

答案：D

解析： 本题考查混合索引文件系统的最大文件大小计算。

第一步：计算一个索引盘块包含的地址项数 盘块大小为 4KB，盘块号长 4B。一个索引盘块可以存放的盘块号数量为： $4KB / 4B = 1024 = 2^{10}$ 。

第二步：逐级计算各部分容量

直接索引：10 条 $\to 10 \times 4KB = 40KB$ 。
1级索引：3 条 $\to 3 \times 1024 \text{ 盘块} \times 4KB = 12MB$ 。
4级索引：1 条 $\to 1024^4 \text{ 盘块} \times 4KB = 2^{40} \times 4KB = 4 \times 2^{50} B = 4PB$ 。

第三步：求和 由于 4 级索引的容量（4PB）远大于低级索引，因此最大文件大小约为 4PB。

难度: ⭐⭐⭐ 考点: #混合索引 #文件管理 #最大文件计算

💡 学习锦囊

📖 相关公式与知识点:

$$N$$ 级索引的盘块数 = $(\text{盘块容量} / \text{盘块号大小})^N$ 。

思路分析

当出现极高级别的索引（如本题的 4 级）时，直接计算最高级即可，低级部分在数量级上可以忽略。

🔄 举一反三

若去掉 4 级索引，改为 1 条 3 级索引，最大文件大小约为多少？
查看练习答案与解析
答案：约 4TB 解析：3 级索引容量为 $1024^3 \times 4KB = 4TB$ 。

文件系统中，若采用成组链接法管理空闲磁盘块，当需要分配一个磁盘块时，系统将会（）。

A. 在空闲表中查找一个空闲块
B. 在位图中查找一个值为 0的位
C. 返回超级块中空闲盘块栈的栈顶指向的盘块
D. 从磁盘的固定位置开始扫描空闲块

查看答案与解析

答案：C

解析： 本题考查空闲磁盘块的成组链接法。

第一步：理解成组链接法的工作机制 成组链接法（常用于 UNIX/Linux）将空闲盘块分成若干组，每组的第一个盘块记录了下一组的盘块号和空闲块总数。最顶层的空闲块信息存放在内存的**超级块（Superblock）**的空闲盘块栈中。

第二步：分析分配过程 当需要分配一个空闲块时：

系统直接从超级块的空闲盘块栈顶弹出一个盘块号。
返回该盘块号给请求者。
（特殊情况）如果栈中只剩最后一个盘块（指向下一组），则需要先将下一组的盘块号读入超级块栈中，再进行分配。

难度: ⭐⭐ 考点: #成组链接法 #空闲空间管理 #文件系统

💡 学习锦囊

📖 相关公式与知识点:

常见的空闲空间管理方法：空闲表法、空闲链表法、位示图法、成组链接法。

思路分析

成组链接法利用栈进行管理，分配即“出栈”，释放即“入栈”。

🔄 举一反三

在位示图法中，若字长为 32 位，位图中的第 0 组第 5 位对应物理块号是多少（假设从 0 开始编号）？
查看练习答案与解析
答案：5 解析：块号 = 字号 $\times$ 字长 + 位号 = $0 \times 32 + 5 = 5$ 。

17．以下关于文件系统的叙述，正确的是（）

A. 逻辑结构上连续的文件在物理结构上也是连续的
B. 逻辑上的索引文件由索引表与记录数据组成，其中索引表指示了各条记录在外存中的保存位置
C. 隐式链接文件系统与显式链接文件系统都需要通过搜索链表来确定下一个文件块的位置，因此同一文件不论用隐式还是显示链接方法进行存储，随机访问的时间没有明显区别
D. 索引文件系统所能管理的最大磁盘空间大小与索引的级数没有关系

查看答案与解析

答案：B

解析： 本题考查文件系统的基本概念。

第一步：逐项分析

A. 错误：逻辑上连续的文件，在物理存储上可以是离散的（如链式存储、索引存储）。
B. 正确：这是逻辑索引文件的定义。索引文件由索引表和数据记录两部分组成。
C. 错误：隐式链接的指针在盘块内，随机访问需要逐块读盘；显式链接的指针在内存的 FAT 表中，寻找盘块号只需查内存，速度极快。
D. 错误：索引级数越多，能寻址的盘块数成指数级增加，直接决定了管理的最大磁盘空间。

难度: ⭐⭐ 考点: #文件系统 #索引文件 #链接存储

💡 学习锦囊

📖 相关公式与知识点:

FAT（文件分配表）常驻内存，解决隐式链接随机访问慢的问题。

思路分析

通过基础概念辨析，排除明显错误的绝对化表述。

🔄 举一反三

哪种文件物理结构最适合随机访问？
查看练习答案与解析
答案：顺序结构（连续分配）
解析：顺序物理结构通过起始块号和块数进行定位，可支持基于逻辑块号的直接地址计算（块号 = 起始块 + 逻辑偏移），因此最快。

下列哪种磁盘调度算法在处理磁道访问请求时，会优先考虑距离磁头当前位置最近的请求，但可能会导致某些请求长时间等待？（）

A. 先进先出（FCFS）

B. 最短寻道时间优先（SSTF）

C. 最高优先级优先（HPF）

D. 循环扫描（CSAN）

查看答案与解析

答案：B

解析： 本题考查磁盘调度算法的特点。

第一步：分析算法策略

SSTF（Shortest Seek Time First）：每次都选择与当前磁头所在磁道距离最近的请求进行服务。

第二步：分析其缺点 该算法倾向于服务局部的磁道请求。如果在当前磁头附近不断有新的请求到达，磁头就会一直在这一区域徘徊，导致远离磁头的请求被“饿死”（饥饿现象，即长时间等待）。

难度: ⭐ 考点: #磁盘调度 #SSTF #饥饿现象

💡 学习锦囊

📖 相关公式与知识点:

FCFS：公平，但平均寻道时间长。
SCAN（电梯算法）：解决饥饿，兼顾寻道时间。

思路分析

“贪心”策略（如 SSTF）往往会带来局部最优但全局产生饥饿的副作用。

🔄 举一反三

哪种磁盘调度算法完全消除了“饥饿”现象，同时比 FCFS 效率更高？
查看练习答案与解析
答案：SCAN 算法（或其变体）
解析：SCAN 算法即“电梯调度”算法，磁头单向移动访问，遇到尽头才折返，避免了远端磁道等待导致的饥饿。

在 Linux 系统中，以普通用户身份对脚本文件“test”执行“sudo chmod 123 test”指令成功后，会使得（）。

A. 文件的所有者能够读取该文件
B. 文件所有者的同组用户均可执行该文件
C. 文件所有者所在组以外的用户均可执行该文件
D. 没有用户可以写该文件的内容

查看答案与解析

答案：C

解析： 本题考查 Linux 文件权限管理。

第一步：解析权限数字 123 Linux 权限由三位八进制数表示，分别对应：文件所有者（User）、同组用户（Group）、其他用户（Others）。

权限值对应关系： $$r = 4, w = 2, x = 1$$ 。
1 $\to$ $$001_2$$ $\to$ --x（仅执行）
2 $\to$ $$010_2$$ $\to$ -w-（仅写入）
3 $\to$ $$011_2$$ $\to$ -wx（写入 + 执行）

第二步：逐项评估

A. 错误：所有者权限为 1（执行），无法读取（需要 4）。
B. 错误：同组用户权限为 2（写入），无法执行。
C. 正确：其他用户（组外用户）权限为 3（写入 + 执行），可以执行。
D. 错误：同组用户和其他用户都有写入权限。

难度: ⭐⭐ 考点: #Linux权限 #chmod

💡 学习锦囊

📖 相关公式与知识点:

权限掩码： $$rwx$$ 对应二进制位，存在为 1，不存在为 0。

思路分析

将八进制权限数字拆解为二进制或 $$rwx$$ 组合，对号入座即可。

🔄 举一反三

若要赋予所有用户读取和执行权限，但禁止写入，chmod 的数字应该设为多少？
查看练习答案与解析
答案：555 解析： $$r+x = 4+1 = 5$$ 。

下列关于文件系统中“文件打开”和“文件关闭”操作的描述，错误的是（）。
A. 文件打开时，系统会在打开文件表中创建一个条目
B. 文件关闭时，系统会释放该文件在内存中的所有资源
C. 文件关闭时，该文件在外存上的目录项会被释放
D. 文件打开时，系统会检查文件的访问权限

查看答案与解析

答案：C

解析： 本题考查文件的打开与关闭操作。

第一步：理解“文件打开”的本质open 操作将外存中的文件控制块（FCB）复制 to 内存的“打开文件表”中，并返回一个文件描述符，以避免后续操作重复读盘。

第二步：辨析各选项

A. 正确：建立内存映射记录。
B. 正确：清空内存缓冲区，移除打开文件表项。
D. 正确：防止非法越权访问。
C. 错误：文件关闭绝不会删除外存上的目录项。目录项（记录文件名、Inode号等）是文件存在的基石，只有在执行**删除文件（rm / unlink）**时才会被释放。

难度: ⭐⭐ 考点: #文件操作 #文件控制块 #打开文件表

💡 学习锦囊

📖 相关公式与知识点:

文件操作原语：create, delete, open, close, read, write。

思路分析

分清“内存状态”与“外存持久化状态”。关闭文件只是结束当前的内存会话，不影响外存实体。

🔄 举一反三

执行什么文件操作会导致外存上的盘块被真正回收？
查看练习答案与解析
答案：删除文件（Delete）
解析：执行文件的 Delete 操作会清空 Inode 数据、断开目录项，并使外存对应的物理空间位示图被重置，释放空间。

某系统采用改进型 Clock 页面置换算法，页表项中字段 A 为访问位，M 为修改位。

$\mathbf { A } { = } \mathbf { 0 }$ 表示页最近没有被访问, $\mathbf { A } { = } \mathbf { 1 }$ 表示页最近被访问过。 $\mathbf { M } { = } \mathbf { 0 }$ 表示页没有被修改过， $\mathbf { M } { = } \mathbf { 1 }$ 表示页被修改过。按(A,M)形式可将页分为 4 类:(0,0)、(1,0)、(0,1)、(1,1)，则该页面置换算法淘汰页的次序为（）

A、(0,0)、(1,0)、(0,1)、(1,1)

B、(0,0)、(1,1)、(0,1)、(1,0)

C、(0,0)、(0,1)、(1,0)、(1,1)

D、(0,0)、(0,1)、(1,1)、(1,0)

查看答案与解析

答案：C

解析： 本题考查改进型 Clock 页面置换算法的淘汰规则。

第一步：理解算法的四轮扫描机制 改进型 Clock 算法为了减少磁盘 I/O 次数，优先淘汰未被修改的页面。

第一轮：寻找 $$(0, 0)$$ ，即最近未访问且未修改的页面。
第二轮：若第一轮失败，寻找 $$(0, 1)$$ ，即最近未访问但被修改的页面。在此过程中，将所有扫描过的页面的访问位 $$A$$ 置为 0。
第三轮：若第二轮失败，重新寻找 $$(0, 0)$$ （原为 $$(1, 0)$$ ，已被清零）。
第四轮：若第三轮失败，寻找 $$(0, 1)$$ （原为 $$(1, 1)$$ ，已被清零）。

第二步：总结淘汰次序 由扫描机制可知，页面的淘汰优先级从高到低依次为： (0,0) $\to$ (0,1) $\to$ (1,0) $\to$ (1,1)。

难度: ⭐⭐⭐ 考点: #改进型Clock #页面置换算法 #虚拟内存

💡 学习锦囊

📖 相关公式与知识点:

淘汰 $$(0, 1)$$ 比淘汰 $$(1, 0)$$ 更好的原因：修改过的页写回磁盘代价高，但最近访问过的页 $$(1, 0)$$ 未来再次访问的概率大，保留它收益更高。

思路分析

改进型 Clock 的核心是“先看访问位，再看修改位”，但优先保留访问位为 1 的页。

🔄 举一反三

简单 Clock 算法与改进型 Clock 算法的主要区别是什么？
查看练习答案与解析
答案：简单 Clock 仅考虑访问位，改进型 Clock 同时考虑访问位 and 修改位。
解析：简单 Clock 算法只维护 1 位访问位（0/1），而改进型引入了修改位 M，从而形成了 4 种优先级状态降低磁盘 I/O。

在可变分区分配方案中，某一作业完成后，系统将回收其主存空间，并与相邻空闲区合并，引起空闲区数减 1 的是（）

A.无上邻接空闲区，也无下邻接空闲区。
B.无上邻接空闲区，但有下邻接空闲区。
C.有上邻接空闲区，但无下邻接空闲区。
D.有上邻接空闲区，也有下邻接空闲区。

查看答案与解析

答案：D

解析： 本题考查动态分区分配中的空间回收算法。

第一步：分析四种回收场景 当作业释放空间时，系统会检查其上下相邻区域的状态：

A. 无上无下：回收区成为一个新的独立空闲区，空闲区数 +1。
B. 无上建下：回收区与下邻空闲区合并，空闲区数不变。
C. 有上无下：回收区与上邻空闲区合并，空闲区数不变。
D. 有上有下：回收区将上、下两个空闲区连成一片，原本的两个空闲区合并为一个，空闲区数 -1。

难度: ⭐ 考点: #可变分区分配 #空间回收 #内存管理

💡 学习锦囊

📖 相关公式与知识点:

动态分区分配算法：首次适应（FF）、最佳适应（BF）、最坏适应（WF）。

思路分析

“左右逢源”导致三区合一，数量自然减少。

🔄 举一反三

在场景 A（无上无下）中，回收操作后空闲区链表会发生什么变化？
查看练习答案与解析
答案：在链表中新增一个节点。
解析：无上邻无下邻时，回收区无法与其他任何空闲区合并，只能作为单独的新记录插入到空闲列表中，增加 1 项。

在下列存储管理方式中，会产生内部碎片的是（）。

A. 页式和段式

B. 页式和段页式

C. 动态分区方式和段式

D. 动态分区方式和段页式

查看答案与解析

答案：B

解析： 本题考查各种内存管理方式的碎片特点。

第一步：区分内部碎片与外部碎片

内部碎片：分配给进程的存储块内部未被利用的部分（进程占用了但没用完）。
外部碎片：内存中由于太小而无法分配给任何进程的空闲区域。

第二步：逐项分析

页式管理：按固定大小的页分配，文件最后一页通常装不满，产生内部碎片。
段式管理：按逻辑段的实际大小分配，无内部碎片，但会产生外部碎片。
段页式管理：段内采用分页，因此仍会产生页内内部碎片。
动态分区：产生外部碎片。

综上，产生内部碎片的是页式和段页式。

难度: ⭐ 考点: #内部碎片 #外部碎片 #页式存储 #段页式存储

💡 学习锦囊

📖 相关公式与知识点:

页式：有内部碎片，无外部碎片。
段式：无内部碎片，有外部碎片。

思路分析

只要包含“页”字的管理方式，都会因为最后一页填不满而产生内部碎片。

🔄 举一反三

哪种内存分配方式既能消除内部碎片，又能消除外部碎片？
查看练习答案与解析
答案：紧凑技术支持下的动态分区分配（通过内存搬移消除外部碎片）。
解析：动态分区分配配合“紧凑”（Compaction）机制可以将正在运行的各个作业集中移动，把离散的外部碎片拼凑成一块完整可用的大空间。

24.在 openEuler 操作系统中，大页机制主要用于优化哪种类型的内存使用？（）

A. 小型数据结构的频繁分配和释放

B. 大规模、连续的内存块分配

C. 线程栈的分配和管理

D. 缓存数据的快速访问

查看答案与解析

答案：B

解析： 本题考查 openEuler 操作系统的大页内存机制。

第一步：理解大页（Huge Pages）的优势 常规内存页大小一般为 4KB。大页机制（如 2MB 或 1GB）通过增大单页容量，显著减少了大规模内存应用中的页表项数量。

第二步：定位适用场景 大页最适合大规模、连续内存分配的场景（如大型数据库、虚拟化宿主机）。

优势：极大提高了 TLB（快表）的命中率，降低了地址转换的开销。

难度: ⭐⭐ 考点: #大页机制 #openEuler #TLB

💡 学习锦囊

📖 相关公式与知识点:

开启大页（如 Linux 的 HugeTLB）可以减少内存页表自身的内存占用。

思路分析

大页对应大块内存，属于典型的“以空间换时间”策略。

🔄 举一反三

大页机制的主要缺点是什么？
查看练习答案与解析
答案：可能导致严重的内部碎片（如只用几KB却分配了2MB）。
解析：大页（如 2MB 或 1GB）将造成内存利用颗粒度增大，若进程仅需要几 KB 的变量，却占据一整页，会加剧页内的内部碎片浪费。

中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（）

A.程序计数器

B. 程序状态字寄存器

C. 通用数据寄存器

D. 通用地址寄存器

查看答案与解析

答案：B

解析： 本题考查中断处理与子程序调用的区别。

第一步：分析现场保护的内容 现场主要包括：程序计数器（PC）、程序状态字寄存器（PSW）和通用寄存器。

第二步：对比两者的触发机制

子程序调用：是程序员在代码中有意安排的（同步的）。调用前后的状态通常由编译器通过通用寄存器管理，不需要硬件自动保存 PSW。
中断处理：是随机发生的（异步的）。可能发生在任何指令之间，中断发生时的条件码、中断屏蔽位等状态必须被精确恢复，因此硬件必须自动保存 PSW。

难度: ⭐⭐ 考点: #中断处理 #PSW #现场保护

💡 学习锦囊

📖 相关公式与知识点:

PC：两者都需要保存，以记录返回地址。

思路分析

中断是“意外”，必须完美还原一切痕迹（包括状态字）；子程序是“计划内”，只需记下回家的路（PC）。

🔄 举一反三

中断返回指令（如 IRET）在恢复现场时，会从栈中弹出什么？
查看练习答案与解析
答案：PSW 和 PC
解析：当触发 IRET 返回时，CPU 需将内核模式切回用户模式，故必须从内核栈的受保护区域按相反顺序弹出中断保存的 PSW 与 PC 还原现场。

二、综合题（共 75 分）

1.（6 分）“虚拟”体现在操作系统的各方面应用当中，请举出三个应用“虚拟”的例子。

查看答案与解析

【参考答案】

操作系统中“虚拟”技术的本质是：通过某种技术将一个物理实体变为若干个逻辑上的对应物，或将多个物理实体变为一个逻辑上的对应物。常见应用例子包括：

虚拟内存（Virtual Memory）：通过页表映射和请求调页机制，将物理内存与外存（如磁盘的 Swap 分区）结合，为每个进程提供一个庞大且连续的虚拟地址空间（如 32 位系统下的 4GB），使用户感觉拥有比实际内存大得多的内存空间。
虚拟设备（Virtual Device / SPOOLing 技术）：利用磁盘上的输入井和输出井，将独占设备（如物理打印机）改造为可由多个进程共享的虚拟共享设备，极大地提高了设备利用率。
虚拟 CPU（分时技术）：通过时间片轮转（RR）调度算法，让多个进程分时共享同一个物理 CPU。在宏观上，每个用户都感觉自己独占了一个 CPU。
虚拟机（Virtual Machine）：通过虚拟化技术（如 KVM、Hyper-V），在单一的物理硬件平台上虚拟出多台独立的逻辑计算机，每台虚拟机可运行不同的操作系统。

难度: ⭐ 考点: #虚拟技术 #操作系统特征

💡 学习锦囊

📖 相关公式与知识点:

操作系统的四大特征：并发、共享、虚拟、异步。其中并发和共享是互为存在条件的。

思路分析

紧扣“以虚代实”或“一实多虚”的核心，从内存、设备、CPU 三个维度作答即可。

🔄 举一反三

虚拟技术中，“时分复用”和“空分复用”有什么区别？
查看练习答案与解析
答案：
- 时分复用：利用空闲时间分时使用，如虚拟 CPU。
- 空分复用：利用空间分割同时使用，如虚拟内存。

2.（12 分）若有 5 个作业 J1、J2、J3、J4、J5 在时刻 0 以 1，2，3，4，5 的顺序到达，各作业要求执行时间和优先级如下表所示：

作业	执行时间	优先级
J1	10	3
J2	1	1
J3	2	3
J4	1	4
J5	5	2

回答以下问题：

（1）使用时间片轮转调度算法（时间片 ${ \bf \Pi } = 1$ ）进行调度，这些作业的平均周转时间、平均带权周转时间是多少?
（2）使用静态优先级、非剥夺式优先级调度算法进行调度，这些作业的平均周转时间、平均带权周转时间是多少?
（3）分析上面（2）中的优先级调度算法的性能优缺点，针对其缺点给出一种合理的改进方案。

查看答案与解析

【参考答案】

IMPORTANT

前提假设：本题中优先级数值越小代表优先级越高（即优先级顺序为 $$1 > 2 > 3 > 4$$ ）。若两个作业优先级相同，则按先来先服务（FCFS）原则调度。

（1）时间片轮转调度算法（ $$q=1$$ ）

调度推演过程（队列初始顺序为 J1, J2, J3, J4, J5）：
- $t=0 \sim 1$ : J1 执行 1s，剩余 9s。队列变为：J2, J3, J4, J5, J1
- $t=1 \sim 2$ : J2 执行 1s，剩余 0s。J2 完成。队列变为：J3, J4, J5, J1
- $t=2 \sim 3$ : J3 执行 1s，剩余 1s。队列变为：J4, J5, J1, J3
- $t=3 \sim 4$ : J4 执行 1s，剩余 0s。J4 完成。队列变为：J5, J1, J3
- $t=4 \sim 5$ : J5 执行 1s，剩余 4s。队列变为：J1, J3, J5
- $t=5 \sim 6$ : J1 执行 1s，剩余 8s。队列变为：J3, J5, J1
- $t=6 \sim 7$ : J3 执行 1s，剩余 0s。J3 完成。队列变为：J5, J1
- 此后 J1 与 J5 轮流执行：
  - $t=7 \sim 8$ : J5 (剩3) | $t=8 \sim 9$ : J1 (剩7) | $t=9 \sim 10$ : J5 (剩2) | $t=10 \sim 11$ : J1 (剩6) | $t=11 \sim 12$ : J5 (剩1) | $t=12 \sim 13$ : J1 (剩5) | $t=13 \sim 14$ : J5 (剩0) $\to$ J5 完成。
- 最后由 J1 独占剩余 5s： $t=14 \sim 19 \to$ J1 完成。
性能指标计算（到达时间均为 0）：
作业执行时间完成时间周转时间带权周转时间
J1 10 19 19 $$19/10 = 1.9$$
J2 1 2 2 $$2/1 = 2.0$$
J3 2 7 7 $$7/2 = 3.5$$
J4 1 4 4 $$4/1 = 4.0$$
J5 5 14 14 $$14/5 = 2.8$$
- 平均周转时间： $T = (19 + 2 + 7 + 4 + 14) / 5 = 46 / 5 = \mathbf{9.2 \text{ s}}$
- 平均带权周转时间： $W = (1.9 + 2.0 + 3.5 + 4.0 + 2.8) / 5 = 14.2 / 5 = \mathbf{2.84}$

作业	执行时间	完成时间	周转时间	带权周转时间
J1	10	19	19	$$19/10 = 1.9$$
J2	1	2	2	$$2/1 = 2.0$$
J3	2	7	7	$$7/2 = 3.5$$
J4	1	4	4	$$4/1 = 4.0$$
J5	5	14	14	$$14/5 = 2.8$$

（2）静态优先级、非剥夺式调度

调度顺序：根据优先级 $$J2(1) > J5(2) > J1(3) = J3(3) > J4(4)$$ ，以及 FCFS，执行顺序为 J2 $\to$ J5 $\to$ J1 $\to$ J3 $\to$ J4。
调度推演：
- J2: 执行 $0 \sim 1 \text{ s}$ ，完成时间为 1。
- J5: 执行 $1 \sim 6 \text{ s}$ ，完成时间为 6。
- J1: 执行 $6 \sim 16 \text{ s}$ ，完成时间为 16。
- J3: 执行 $16 \sim 18 \text{ s}$ ，完成时间为 18。
- J4: 执行 $18 \sim 19 \text{ s}$ ，完成时间为 19。
性能指标计算：
作业执行时间完成时间周转时间带权周转时间
J1 10 16 16 $$16/10 = 1.6$$
J2 1 1 1 $$1/1 = 1.0$$
J3 2 18 18 $$18/2 = 9.0$$
J4 1 19 19 $$19/1 = 19.0$$
J5 5 6 6 $$6/5 = 1.2$$
- 平均周转时间： $T = (16 + 1 + 18 + 19 + 6) / 5 = 60 / 5 = \mathbf{12.0 \text{ s}}$
- 平均带权周转时间： $W = (1.6 + 1.0 + 9.0 + 19.0 + 1.2) / 5 = 31.8 / 5 = \mathbf{6.36}$

作业	执行时间	完成时间	周转时间	带权周转时间
J1	10	16	16	$$16/10 = 1.6$$
J2	1	1	1	$$1/1 = 1.0$$
J3	2	18	18	$$18/2 = 9.0$$
J4	1	19	19	$$19/1 = 19.0$$
J5	5	6	6	$$6/5 = 1.2$$

（3）性能分析与改进方案

优点：实现简单，能够保证紧急、高优先级的任务获得快速响应。
缺点：可能会导致低优先级任务长期得不到调度，产生**“饥饿”甚至“饿死”**现象（如本题中的 J4）。
改进方案：
1. 老化算法（Aging）：随着作业在就绪队列中等待时间的增加，逐步动态提高其优先级。
2. 高响应比优先算法（HRRN）：将优先级设计为 $R = (\text{等待时间} + \text{要求服务时间}) / \text{要求服务时间}$ ，兼顾了短作业和长等待作业。

难度: ⭐⭐⭐ 考点: #作业调度 #时间片轮转 #优先级调度 #周转时间

💡 学习锦囊

📖 相关公式与知识点:

周转时间 $$T_i = C_i - A_i$$
带权周转时间 $$W_i = T_i / E_i$$

易错点

时间片轮转中，当某作业恰好用完时间片退出时，若有新作业同时到达，通常新作业先入队，旧作业后入队。本题中作业同时到达，只需按初始顺序入队即可。

🔄 举一反三

若有 3 个作业 J1、J2、J3 同时在时刻 0 到达，执行时间分别为 5ms、2ms、8ms。采用短作业优先（SJF）非剥夺调度算法，它们的平均周转时间是多少？
查看练习答案与解析
答案：8ms
解析：
- SJF 调度顺序为：J2 (2ms) $\to$ J1 (5ms) $\to$ J3 (8ms)。
- 完成时间：J2 为 2ms，J1 为 $2 + 5 = 7\text{ms}$ ，J3 为 $7 + 8 = 15\text{ms}$ 。
- 周转时间：J2 为 2ms，J1 为 7ms，J3 为 15ms。
- 平均周转时间： $(2 + 7 + 15) / 3 = 24 / 3 = \mathbf{8\text{ms}}$ 。

3.（9分）某文件系统盘块号长4B，盘块大小为 4KB，请回答以下问题：

（1）假如文件系统为 FAT32，且 FAT 表不在内存，所有文件的 FCB 已在内存中，那么读取大小为 4GB 的文件的最后一个盘块，最少需要访问几次磁盘？在不考虑优化策略的情况下，最多需要访问几次磁盘？需给出推理计算过程
（2）假如文件系统为 Ext2，所有文件的 FCB 已在内存中，那么访问一个大小为 8MB 的文件的最后一个盘块，需要访问几次磁盘？
（3）假设有一个 4GB 的文件在逻辑结构上是一个索引文件，使用 Ext2 文件系统存放时，为了提高文件访问效率，索引表部分应该存放在文件的哪个位置（文件头部、文件中部、文件尾部）？为什么？

查看答案与解析

【参考答案】

（1）FAT32 磁盘访问次数计算

基础数据：
- 盘块大小 $$= 4KB = 4096B$$ 。
- FAT32 表项大小 $$= 4B$$ 。一个 FAT 盘块可容纳的表项数 $$= 4KB / 4B = 1024$$ 个。
- 文件大小 $= 4GB = 2^{20} \times 4KB$ 。该文件共包含 $2^{20}$ 个数据盘块，对应的 FAT 表链长度也为 $2^{20}$ 。
- FAT 表总盘块数 $= 2^{20} / 1024 = 1024$ 块。
推理过程：要读取最后一个盘块，必须通过 FAT 表项构成的链表顺藤摸瓜找到最后一个盘块的物理块号。
- 最少访问次数：假设系统内存足够大，读入的 FAT 盘块能够常驻内存。则只需将 FAT 表的 1024 个盘块一次性全部读入内存，最后读取 1 次数据盘块。 $\text{总次数} = 1024 (\text{读FAT}) + 1 (\text{读数据}) = \mathbf{1025} \text{ 次}$
- 最多访问次数：在不考虑优化的情况下（例如内存中仅有 1 个 FAT 缓冲块，且没有做连续块预读），每次追踪下一个块号都可能导致 FAT 缓冲块发生缺页置换。由于链表长 $2^{20}$ ，最多可能读取 $2^{20}$ 次 FAT 表项盘块。 $\text{总次数} = 2^{20} (\text{读FAT}) + 1 (\text{读数据}) \approx \mathbf{1M} \text{ 次}$

（2）Ext2 磁盘访问次数计算

基础数据：
- 文件大小 $= 8MB = 2048 \times 4KB$ 。该文件占用 2048 个盘块。
- Ext2 索引结构包含：12 个直接索引，1 个一级间接，1 个二级间接。
确定盘块位置：
- 直接索引可寻址： $12 \times 4KB = 48KB$ 。
- 一级间接可寻址： $1024 \times 4KB = 4MB$ 。
- 二级间接可寻址： $1024^2 \times 4KB = 4GB$ 。
- 前两级寻址范围 $$= 48KB + 4MB = 1036$$ 块。因为 $1036 < 2048 \leq 1024^2$ ，所以第 2048 个块必定落在二级间接索引内。
计算访问次数：由于 FCB 已在内存，包含二级间接指针。访问二级索引块的流程为：
1. 读取二级间接索引表的第一级盘块（1次）。
2. 读取二级间接索引表的第二级盘块（1次）。
3. 读取最终的数据盘块（1次）。
$$\text{总次数} = 1 + 1 + 1 = \mathbf{3} \text{ 次}$$

（3）索引表的存放位置决策

推荐位置：文件中部（或中心）。
原因：当文件很大（4GB）且采用索引结构访问时，磁头需要频繁地在“索引表”与“数据盘块”之间来回移动（寻道）。
- 若存放在文件头部或尾部，磁头移动到数据块的平均寻道距离为文件长度的 $$1/2$$ 。
- 若存放在文件中部，磁头到任意数据块的平均寻道距离将降至文件长度的 $$1/3$$ ，从而大幅减少磁头寻道时间，提高访问效率。

难度: ⭐⭐⭐⭐ 考点: #FAT32 #Ext2混合索引 #寻道时间

💡 学习锦囊

📖 相关公式与知识点:

混合索引寻址范围的阶梯式计算是核心得分点。

思路分析

第一问是考查链式与连续的差异，第二问考查层级计算。

🔄 举一反三

若 Ext2 盘块大小改为 2KB，则一级间接索引可以寻址多少空间？
查看练习答案与解析
答案： $$1MB$$ 解析：表项数 $$= 2KB / 4B = 512$$ 项。寻址空间 $= 512 \times 2KB = 1024KB = 1MB$ 。

4.（12 分）某文件系统采用 3 级索引结构，盘块大小为 4KB。目录项结构设计为【文件名的 HASH 值，FCB 编号】两项，每项各占 4 字节，其中没有包含文件的物理地址信息。文件的 FCB 中包括了完整的文件名和 3 级索引盘块的指针，对于目录文件还有指向目录盘块的指针，所有文件的 FCB 以 FCB 编号为序，顺序连续存放在磁盘上指定位置。请回答以下问题：

（1）假设该系统采用单级目录结构，目录盘块以连续方式分配，目录项以无序列表的方式存储，当前保存了 800 个文件。目录检索采用 HASH 查找方式，假设文件名的 HASH 值不重复，打开任意文件平均需要访问磁盘几次？（需给出计算过程）如果文件名的 HASH算法可能产生重复值，可以用什么方法解决（策略合理即可）？
（2）假设系统采用多级目录结构，并且任意目录的文件不超过 100 项，物理文件采用三级索引文件。假设根目录盘块常驻内存中，且当前目录为根目录，如何根据文件路径/home/user/test.pak找到对应的文件并打开？给出过程描述，并回答该过程共需要访问几次磁盘。（4分）
（3）在（2）的基础上，继续打开并读取/home/user/work.pak 文件的某一块数据，需要几次磁盘访问？给出推理计算过程。

查看答案与解析

【参考答案】

（1）单级目录打开文件磁盘访问次数

推理计算：
1. 计算目录大小：每个目录项占 $$4B + 4B = 8B$$ 。800 个文件共占 $800 \times 8B = 6400B$ 。
2. 计算目录盘块数：盘块大小为 4KB，因此目录占用 $\lceil 6400B / 4096B \rceil = 2$ 个盘块。
3. 查找目录项读盘次数：由于采用无序列表存储，在 2 个连续盘块中顺序查找。查找成功时，平均需要扫描一半的目录项。即有 $50\%$ 的概率在第 1 块找到（读 1 次）， $50\%$ 的概率在第 2 块找到（读 2 次）。 $\text{平均读目录盘块数} = 0.5 \times 1 + 0.5 \times 2 = 1.5 \text{ 次}$
4. 读取 FCB：找到 FCB 编号后，需要到磁盘指定位置读取该文件的 FCB（1 次）。
$$\text{总平均磁盘访问次数} = 1.5 + 1 = \mathbf{2.5} \text{ 次}$$
解决 HASH 冲突的方法：
1. 开放定址法（如线性探测法）：产生冲突时，顺次寻找下一个空闲的目录项槽位。
2. 链地址法（拉链法）：将 HASH 值相同的目录项通过指针链接成一个单链表。

（2）多级目录路径解析过程

解析过程：
1. 根目录常驻内存，在根目录中查找到 home 的 FCB 编号（0 次读盘）。
2. 根据编号读取 home 的 FCB（1 次读盘）。
3. 根据 FCB 找到 home 的目录盘块并读入（1 次读盘），在其中查找到 user 的 FCB 编号。
4. 根据编号读取 user 的 FCB（1 次读盘）。
5. 根据 FCB 找到 user 的目录盘块并读入（1 次读盘），在其中查找到 test.pak 的 FCB 编号。
6. 根据编号读取 test.pak 的 FCB（1 次读盘），将文件信息载入打开文件表。
总访问磁盘次数： $0 + 1 + 1 + 1 + 1 + 1 = \mathbf{5} \text{ 次}$ 。

（3）继续打开并读取新文件

推理计算：
1. 打开文件：路径为 /home/user/work.pak。由于在上一步中，user 目录的盘块已经被读入内存缓存中，因此无需再次读盘。直接在内存的 user 目录中查找 work.pak 的 FCB 编号（0 次）。随后读取 work.pak 的 FCB（1 次）。
2. 读取数据块：文件采用 3 级索引。
  - 若目标数据块在直接索引：需读盘 1 次。
  - 若在一级间接：需读索引 1 次 + 读数据 1 次 = 2 次。
  - 若在二级间接：需读索引 2 次 + 读数据 1 次 = 3 次。
  - 若在三级间接：需读索引 3 次 + 读数据 1 次 = 4 次。
最终答案：取决于读取的具体块位置，总访问磁盘次数为 2 到 5 次。

难度: ⭐⭐⭐⭐ 考点: #文件检索 #多级目录 #索引结构访问

💡 学习锦囊

📖 相关公式与知识点:

目录项不包含物理地址，而是包含 FCB 指针/编号，这是 UNIX inode 思想的体现。

思路分析

在第（3）小问中，一定要注意到上一次查询留下的内存缓存（/home/user 的目录项已经在内存中）。

🔄 举一反三

假设系统采用多级目录，路径解析过程为 /a/b/c.txt。根目录不常驻内存，每读取一个目录文件需要 1 次读盘，读取 FCB 需 1 次读盘。在没有任何内存缓存的情况下，打开该文件共需访问几次磁盘？
查看练习答案与解析
答案：6 次
解析：
- 第一步：读取根目录的 FCB 并载入（1 次），读取根目录盘块（1 次）找到 a 的 FCB 编号。
- 第二步：根据编号读取 a 的 FCB（1 次），读取 a 的目录盘块（1 次）找到 b 的 FCB 编号。
- 第三步：根据编号读取 b 的 FCB（1 次），读取 b 的目录盘块（1 次）找到 c.txt 的 FCB 编号并打开。
- 统计： $1+1+1+1+1+1 = \mathbf{6}$ 次。

5.（12 分）在虛拟存储管理系统中，采用 LRU 页面置换算法，一个进程有 3 页内存空间，每页可以存放 200 个整数。其中第 1 页存放程序，且假定程序已在内存中。分别有如下 A、B 两个程序，已知数组 int A[100][100]按行存储。

程序 A：

\begin{array}{l} f o r \quad (i n t i = 0; i < 1 0 0; i + +) \\ f o r (i n t j = 0; j < 1 0 0; j + +) \\ A [ i, j ] = 0; \\ \end{array}

程序 B：

\begin{array}{l} f o r (i n t j = 0; j < 1 0 0; j + +) \\ f o r (i n t i = 0; i < 1 0 0; i + +) \\ A [ i, j ] = 0; \\ \end{array}

请回答下面的问题：

（1）分别计算程序 A和程序 B 在执行过程中的缺页中断次数。要求给出计算过程。
（2）分析（1）中两个程序执行过程中缺页中断次数不同的原因。
（3）给出两种能改进内存有效访问时间的方法。

查看答案与解析

【参考答案】

（1）缺页中断次数计算

基础数据分析：
- 数组 int A[100][100] 共包含 $100 \times 100 = 10000$ 个整数。
- 内存页面大小 $$= 200$$ 个整数。因此数组共占用 $$10000 / 200 = 50$$ 个页面。
- 数组按行存储：每行 100 个整数。因此 1 个内存页面刚好存放 2 行数据。
  - 页面 0 存放 A[0] 和 A[1]；页面 1 存放 A[2] 和 A[3] ... 页面 49 存放 A[98] 和 A[99]。
- 分配的页框：共 3 页，第 1 页存程序，剩余 2 页用于存放数组数据。
程序 A（按行访问）：
- 访问顺序为 A[0][0], A[0][1], ..., A[0][99], A[1][0], ..., A[99][99]。
- 当访问 A[0][0] 时，发生缺页，调入页面 0（含前 2 行）。此后访问 A[0][1] 到 A[1][99] 均命中。
- 当访问 A[2][0] 时，发生缺页，调入页面 1。
- 以此类推，每访问 2 行（即 1 个页面）仅发生 1 次缺页。
$$\text{程序 A 缺页次数} = 50 \text{ 页} \times 1 = \mathbf{50} \text{ 次}$$
程序 B（按列访问）：
- 访问顺序为 A[0][0], A[1][0], A[2][0], ..., A[99][0], A[0][1], A[1][1], ...。
- 在访问第一列时：
  - i=0: 访问 A[0][0]，缺页，调入页面 0（含 0, 1 行）。
  - i=1: 访问 A[1][0]，命中。
  - i=2: 访问 A[2][0]，缺页，调入页面 1（含 2, 3 行）。
  - i=3: 访问 A[3][0]，命中。
  - i=4: 访问 A[4][0]，缺页，由于数据页框仅有 2 个，此时淘汰页面 0，调入页面 2。
  - 以此类推，访问第一列的 100 个元素，每隔 2 个元素发生一次缺页，共缺页 50 次。此时内存中仅剩最后调入的两个页面。
- 在访问第二列（及后续列）时：
  - 由于内存中已经没有之前被置换出的页面，每一次按列跨步访问都会导致页面重新调入。
$$\text{程序 B 缺页次数} = 100 \text{ 列} \times 50 \text{ 次/列} = \mathbf{5000} \text{ 次}$$

（2）原因分析

局部性原理的差异：
- 程序 A 采用了行优先访问，与其在内存中的物理存储顺序完全一致，具有极好的空间局部性。
- 程序 B 采用了列优先访问，产生了跨页的“跳跃式”访问，导致内存产生严重的抖动现象（Thrashing）。

（3）改进内存有效访问时间的方法

优化算法结构：将循环嵌套顺序由列优先改为行优先（如程序 A）。
增加物理页框数：为进程分配更多的数据页框，减少置换频率。
采用大页机制：增大页面容量，使得单页能容纳更多的数据。

难度: ⭐⭐⭐⭐ 考点: #局部性原理 #LRU算法 #缺页中断计算

💡 学习锦囊

📖 相关公式与知识点:

空间局部性：如果一个存储单元被访问，其邻近的单元也可能很快被访问。

思路分析

核心在于画出“每页包含的数据范围”与“代码循环步长”的匹配图。

🔄 举一反三

若将本题的页面置换算法改为先进先出（FIFO）算法，其他条件不变，程序 A 和程序 B 的缺页中断次数会有什么变化？
查看练习答案与解析
答案：没有变化。程序 A 缺页 50 次，程序 B 缺页 5000 次。
解析：
- 程序 A：在处理时每 2 行换一个新页面，没有任何重复访问已置换出页面的场景，FIFO 与 LRU 效果相同，产生 50 次缺页。
- 程序 B：列访问时产生的置换是对连续数据框的高频循环覆盖淘汰，LRU 和 FIFO 在内存数据完全被填满并轮换淘汰时呈现相同的淘汰逻辑规律，依然是 5000 次。

（12 分）在一个成绩管理系统中，所有同学所有课程的成绩全部集中存放在同一个文件中（后称成绩表），各课程任课教师将学生成绩记录到该成绩表中，同学从该成绩表中查询各课程成绩。当一个教师在登记成绩过程中，为保证成绩登记的正确性，要求其他所有教师和同学不能访问成绩表；同时为了快速响应同学查询成绩，系统允许多个同学同时查询成绩表，但同时查询的最多人数限制在 1000 人以内，若同时查询人数达到上限1000 人时，则睡眠等待直到有人退出成绩表的查询。使用记录型信号量机制解决该同步问题。

查看答案与解析

【参考答案】

这是一个限制读者人数的“读者-写者”问题。教师相当于“写者”（排他访问），学生相当于“读者”（共享访问，但限制最大并发数为 1000）。

信号量定义：

semaphore wrt = 1; —— 互斥信号量，用于实现教师与教师互斥、教师与学生互斥。
semaphore mutex = 1; —— 互斥信号量，用于保护对读者计数器 read_count 的原子操作。
semaphore empty = 1000; —— 资源信号量，限制同时查询成绩的学生人数上限为 1000。
int read_count = 0; —— 共享变量，记录当前正在查询的学生人数。

伪代码实现：

// 教师进程（写者）
void Teacher() {
    while (TRUE) {
        P(wrt);         // 申请对成绩表的独占访问权
        
        /* 登记成绩操作 */
        
        V(wrt);         // 释放对成绩表的访问权
    }
}

// 学生进程（读者）
void Student() {
    while (TRUE) {
        P(empty);       // 检查查询名额是否达到 1000 人限制
        P(mutex);       // 互斥保护 read_count
        
        if (read_count == 0) {
            P(wrt);     // 第一个学生进入，阻止教师进行写操作
        }
        read_count++;
        V(mutex);

        /* 查询成绩操作 */

        P(mutex);       // 互斥保护 read_count
        read_count--;
        if (read_count == 0) {
            V(wrt);     // 最后一个学生离开，允许教师进行写操作
        }
        V(mutex);
        V(empty);       // 释放一个查询名额
    }
}

难度: ⭐⭐⭐⭐ 考点: #信号量 #进程同步 #读者写者问题

💡 学习锦囊

📖 相关公式与知识点:

经典读者-写者问题模板：if(count == 0) P(wrt); count++;
本题在此基础上套了一层 empty 资源限制。

易错点

不要忘记在释放 empty 之前，必须先安全退出临界区并修改 read_count。

🔄 举一反三

若要求写者优先（一旦有教师想登记，后续学生不能再进入），该如何修改？

查看练习答案与解析

答案：
通过引入额外信号量 queue 确保排队执行。

伪代码实现：

semaphore wrt = 1;
semaphore mutex = 1;
semaphore queue = 1; // 新增排队信号量
semaphore empty = 1000;
int read_count = 0;

void Teacher() {
    while (TRUE) {
        P(queue);       // 教师获取服务排队
        P(wrt);         // 互斥访问成绩表
        V(queue);       // 释放排队信号量
        
        /* 登记成绩操作 */
        
        V(wrt);
    }
}

void Student() {
    while (TRUE) {
        P(queue);       // 学生排队
        P(empty);       // 申请1000人限额
        P(mutex);
        if (read_count == 0) {
            P(wrt);     // 阻止教师进入
        }
        read_count++;
        V(mutex);
        V(queue);       // 释放排队，后续学生可获取名额
        
        /* 查询成绩操作 */
        
        P(mutex);
        read_count--;
        if (read_count == 0) {
            V(wrt);     // 释放给教师
        }
        V(mutex);
        V(empty);
    }
}

解析：当一个教师调用 P(queue) 成功后，它会等待 wrt。此时若有新的学生进入，他们将在 P(queue) 处阻塞，无法跳过教师抢占名额，从而实现了写者优先。

（12分）已知某系统为 32 位实地址，使用 48 位虚地址，页面大小为 4KB，页表项大小为 8B。请回答以下问题：

（1）若系统使用纯页式存储，要求最高级页表能存放在一个页面中，则要采用多少级页表？页内偏移多少位？
（2）在（1）中的条件下，假设 TLB 命中率为 $9 5 \%$ ，访问 TLB 时间为 10ns，访问内存时间为 100ns，并假设当 TLB 访问失败后才开始访问内存、且忽略更新 TLB 的时间，问平均内存访问时间是多少？
（3）若系统采用段页式存储方式，且每段最大为 4GB，则每用户空间最多可以有多少个段？若要求每个段的最高级页表也要保存在一个页面内，则段内采用几级页表？

查看答案与解析

【参考答案】

（1）页表级数与偏移量计算

页内偏移位：页面大小 $= 4KB = 2^{12} \text{ 字节}$ ，因此页内偏移量为 12 位。
页表级数推理：
1. 虚地址 48 位，虚页号长度 $$= 48 - 12 = 36$$ 位。
2. 一个页面的大小为 4KB，每个页表项长 $$8B$$ 。因此，一个页面能容纳的页表项数量为 $$4KB / 8B = 512 = 2^9$$ 个。
3. 为了使最高级页表刚好能装入一个页面中，每一级页表所占用的虚地址位数应等于 9 位。
4. 级数 $N = \text{虚页号长度} / \text{单级位数} = 36 / 9 = \mathbf{4}$ 级。

（2）平均内存访问时间（EAT）计算

4 级页表下，当 TLB 未命中时，需要连续访问 4 次页表内存，再加上 1 次真正的数据内存，共访问 5 次内存。
TLB 命中场景时间： $T_{hit} = T_{TLB} + T_{Mem} = 10 + 100 = 110 \text{ ns}$ 。
TLB 失败场景时间： $T_{miss} = T_{TLB} + 5 \times T_{Mem} = 10 + 5 \times 100 = 510 \text{ ns}$ 。
平均内存访问时间： $\text{EAT} = 95\% \times 110 + 5\% \times 510 = 104.5 + 25.5 = \mathbf{130 \text{ ns}}$

（3）段页式存储结构计算

最多段数：每段最大容量为 $4GB = 2^{32} \text{ 字节}$ ，说明段内偏移量（虚地址低位）占 32 位。段号长度 $$= 48 - 32 = 16$$ 位。因此，最多可划分 $2^{16} = \mathbf{65536}$ 个独立的段。
段内页表级数：
1. 段内虚地址为 32 位，扣除页内偏移 12 位，段内的虚页号长度为 $$32 - 12 = 20$$ 位。
2. 每级页表容量仍为 9 位。
3. 级数 $N = \lceil 20 / 9 \rceil = \mathbf{3}$ 级（其中最高级占用 $20 - 2 \times 9 = 2$ 位地址，占用 4 个页表项，小于 512，满足保存在单页面内的要求）。

难度: ⭐⭐⭐⭐ 考点: #多级页表 #TLB计算 #段页式管理

💡 学习锦囊

📖 相关公式与知识点:

页表项寻址范围 $= 2^{\text{虚页号位数}}$ 。
$EAT = \alpha(t + m) + (1-\alpha)(t + (N+1)m)$ 。

思路分析

注意第三问的段页式，地址结构发生了拆分（段号+页号+偏移）。

🔄 举一反三

若系统页大小改为 8KB，其余条件不变（使用 48 位虚地址，页表项 8B），最高级页表存放在一个页面中，纯页式存储需要几级页表？
查看练习答案与解析
答案：4 级
解析：
- 页内偏移： $8KB = 2^{13}$ 字节，偏移占 13 位。
- 虚页号长度： $$48 - 13 = 35$$ 位。
- 页表项容量：一个页面可存放 $8KB / 8B = 1024 = 2^{10}$ 个页表项，每级占用 10 位。
- 页表级数： $N = \lceil 35 / 10 \rceil = 4$ 级。

《操作系统》第一学期期末试卷A (精选08) ​

一、选择题（每题 1 分，共 25 分） ​

二、 综合题（共 75 分） ​

《操作系统》第一学期期末试卷A (精选08)

一、选择题（每题 1 分，共 25 分）

二、综合题（共 75 分）