操作系统 模拟试卷2

考试时间：120分钟 满分：100分

一、单项选择题（共10题，每题2分，共20分）

请从每题的四个选项中选择一个最合适的答案。

1. 下列关于TLB（转译后备缓冲器）的描述中，正确的是（ ）。
A. TLB是CPU内部的一级指令缓存
B. TLB用于缓存最近使用的页表项，加速地址转换
C. TLB存储在磁盘上，需要时调入内存
D. TLB的作用是替代MMU进行所有的地址转换

2. 下列关于线程与进程的叙述中，错误的是（ ）。
A. 同一进程中的多个线程共享该进程的地址空间
B. 线程切换的开销通常小于进程切换的开销
C. 每个线程拥有独立的程序计数器、寄存器和栈
D. 不同进程中的线程不能以任何方式共享数据

3. SPOOLing技术的主要作用是（ ）。
A. 提高CPU的运算速度
B. 将独占设备转换为共享设备
C. 增加内存的可用容量
D. 实现进程间的互斥与同步

4. 当系统发生颠簸（Thrashing）时，CPU利用率通常会（ ）。
A. 急剧上升
B. 急剧下降
C. 保持不变
D. 先上升后下降

5. 下列关于动态链接与静态链接的比较中，正确的是（ ）。
A. 静态链接生成的可执行文件比动态链接的更小
B. 动态链接的程序更新更方便，只需替换动态库文件
C. 动态链接程序的运行速度一定比静态链接快
D. 静态链接的程序需要依赖系统中存在相应的动态库

6. 在EXT4文件系统中，管理大文件数据块所采用的主要数据结构是（ ）。
A. FAT（文件分配表）
B. 直接索引块
C. 区段树（Extent Tree）
D. 三级间接索引

7. C-LOOK磁盘调度算法相比于C-SCAN算法的改进之处在于（ ）。
A. 磁头移动到磁盘的物理末端才掉头
B. 磁头只移动到最远的请求处便直接返回起点
C. 磁头在双向移动过程中都处理请求
D. 优先处理离当前磁头位置最近的请求

8. 管程（Monitor）相比于信号量（Semaphore）的主要优势是（ ）。
A. 管程的执行速度比信号量快得多
B. 管程将同步机制封装在内部，降低了编写正确并发程序的难度
C. 管程能够解决所有类型的同步问题，而信号量不能
D. 管程不需要条件变量即可实现线程同步

9. 在Peterson算法中，两个进程实现互斥所使用的共享变量是（ ）。
A. 一个二元信号量
B. 一个flag数组和一个turn变量
C. 一个互斥锁（Mutex）
D. 一个条件变量

10. 工作集模型（Working Set Model）的主要目的是（ ）。
A. 提高CPU的指令执行效率
B. 防止系统发生颠簸（Thrashing）
C. 减少页面置换算法的计算开销
D. 提高磁盘的读写速度

二、填空题（共30空，每空1分，共30分）

  1. CPU执行指令的四个基本步骤是：取指（Fetch）、____、执行（Execute）和写回（Writeback）。

  2. 在存储器层次结构中，位于寄存器与主存之间的是____。

  3. 线程的基本状态包括：就绪态、____态和阻塞态。

  4. 在动态链接中，程序运行时通过____（过程链接表）与GOT（全局偏移表）协作完成函数的延迟绑定。

  5. 位置无关代码（PIC）中不包含____地址，所有地址均为相对地址，因此可被加载到内存的任意位置。

  6. 延迟绑定（Lazy Binding）将函数的符号解析和重定位推迟到函数____被调用时执行。

  7. 时间局部性（Temporal Locality）是指最近被访问的存储器地址很可能在____再次被访问。

  8. 空间局部性（Spatial Locality）是指当前被访问地址____的地址很可能很快被访问。

  9. 写时复制（Copy-on-Write, COW）技术中，fork()之后父子进程____物理页面，仅当其中一方执行写操作时才创建副本。

  10. 虚拟文件系统（VFS）通过提供____的文件操作接口，使用户能够透明地访问不同文件系统。

  11. ____（基于角色的访问控制）模型将权限赋予角色，再将角色赋予用户。

  12. 按使用方式分类，设备可以分为独占设备、共享设备和____设备三类。

  13. ____技术利用磁盘作为缓冲区，将独占设备模拟为共享设备，提高了设备的利用率。

  14. 在USB描述符层次结构中，设备描述符之下的层次是____描述符。

  15. 中断处理分为上半部（Top-half）和____（Bottom-half）两个阶段。

  16. 在Unix/Linux文件系统中，____（索引节点）存储文件的元数据信息，但文件名除外。

  17. 硬链接（Hard Link）不能跨越____系统，也不能链接目录。

  18. 并发（Concurrency）是指多个任务在同一个时间____内交替执行。

  19. 并行（Parallelism）是指多个任务在同一个____同时执行。

  20. 在M:1线程模型中，多个____线程映射到一个内核线程。

  21. 无锁数据结构的三个级别从弱到强依次为：Obstruction-free、____和Wait-free。

  22. 在Hoare语义中，条件变量的signal操作会____将锁和处理器移交给被唤醒的线程。

  23. 在Mesa语义中，条件变量中被唤醒的线程进入____队列，条件可能已不再成立，需要重新检查。

  24. Linux中的futex机制在低竞争时使用____锁以避免系统调用开销，在高竞争时由内核管理阻塞队列。

  25. 采用固定分区存储管理方式时，会产生____碎片。

  26. 在FIFO页面置换算法中，增加分配的物理帧数反而导致缺页率上升，这种现象称为____异常。

  27. 在EXT4文件系统中，区段（Extent）树主要用于管理____的连续数据块区间。

  28. 内存映射文件（Memory-Mapped File）实现了____拷贝，减少了数据在用户态和内核态之间的复制次数。

  29. 在进程调度的三个层次中，____调度负责选择下一个将要运行的线程，执行频率最高。

  30. 在8086处理器中，SP（堆栈指针）寄存器与____段寄存器配合使用来管理堆栈操作。

三、简答题（共5题，每题4分，共20分）

1. 请简述写时复制（Copy-on-Write）技术的基本原理及其在操作系统中的作用。（4分）

2. 请简述工作集模型（Working Set Model）的概念，并说明它如何用于防止颠簸（Thrashing）。（4分）

3. 请比较管程（Monitor）与信号量（Semaphore）在解决进程同步问题时的异同。（4分）

4. 请简述连续分配、链接分配和索引分配三种文件物理分配方式各自的优缺点。（4分）

5. 请比较SCAN、C-SCAN、LOOK和C-LOOK四种磁盘调度算法的特点。（4分）

四、计算与分析题（共2题，每题10分，共20分）

第1题：银行家算法（Banker’s Algorithm）（10分）

设系统中有三种资源 A、B、C，数量分别为 A=10、B=5、C=7。现有五个进程 P0 ~ P4，在 T0 时刻的资源分配情况如下表所示（Allocation 表示已分配资源，Max 表示最大需求资源，Available 表示当前可用资源）：

T0时刻系统状态：

| 进程 | Allocation（已分配） | Max（最大需求） | Need（尚需） |
|:----😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐
| | A | B | C | A | B | C | A | B | C |
| P0 | 0 | 1 | 0 | 7 | 5 | 3 | | | |
| P1 | 2 | 0 | 0 | 3 | 2 | 2 | | | |
| P2 | 3 | 0 | 2 | 9 | 0 | 2 | | | |
| P3 | 2 | 1 | 1 | 2 | 2 | 2 | | | |
| P4 | 0 | 0 | 2 | 4 | 3 | 3 | | | |

Available（当前可用资源）： A = 3，B = 3，C = 2

请回答以下问题：
（1）计算每个进程的 Need 矩阵（尚需资源量），填入上表。（2分）
（2）T0 时刻系统是否处于安全状态？如果是，请给出一个安全序列并说明判断过程；如果不是，请说明原因。（4分）
（3）若在 T0 时刻之后，进程 P1 发出请求向量 Request1 = (1, 0, 2)，系统能否将资源分配给 P1？请逐步说明判断过程。（4分）

第2题：页面置换算法与多级页表地址转换（10分）

第一部分：页面置换算法（6分）

某程序在一个请求分页系统中运行，页面引用序列为：

3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4

分配给该程序的物理块（帧）数量为 3块，初始时所有帧均为空。

请分别计算以下三种页面置换算法的缺页次数：
（1）先进先出（FIFO）页面置换算法。（2分）
（2）最近最久未使用（LRU）页面置换算法。（2分）
（3）最佳（Optimal）页面置换算法。（2分）

要求：对每种算法，以表格形式列出每次页面访问时内存中页面的变化情况，缺页处标注"F"。

第二部分：多级页表地址转换（4分）

某32位计算机系统采用二级页表结构，页面大小为 4KB（2^12 B）。其中：

  • 顶级页表（页目录）有 2^10 = 1024 个表项，占用一页
  • 二级页表同样有 2^10 = 1024 个表项，每个占用一页
  • 页表项（PTE）大小为 4字节

给定一个虚拟地址 0x00303004（十六进制），请回答：
（1）该虚拟地址的页目录索引、二级页表索引和页内偏移量分别是多少？（用十六进制表示）（2分）
（2）假设顶级页表（页目录）的物理帧号为 0x1000，相关的二级页表的物理帧号为 0x2000，二级页表中对应页表项给出的物理帧号为 0x3000，请计算最终的物理地址。（2分）

五、综合题（共1题，共10分）

读者-写者问题（Readers-Writers Problem）

有一个共享数据文件，多个读者（Reader）和写者（Writer）进程需要同时访问该文件。同步要求如下：

  1. 多个读者可以同时读取文件，不互斥。
  2. 写者在写入时必须独占文件，即同一时间只能有一个写者写入，且读者不能同时读取。
  3. 当有写者在等待时，新到达的读者不能开始读取（写者优先策略，避免写者饥饿）。

请使用信号量机制实现上述"写者优先"的读者-写者同步方案。

完成以下问题：
（1）定义所需的全部信号量及共享变量，说明每个信号量的作用和初始值。（3分）
（2）写出读者进程的伪代码。（3分）
（3）写出写者进程的伪代码。（3分）
（4）说明该方案为什么能避免死锁，并分析是否仍存在饥饿的可能性。（1分）

参考答案与解析

一、单项选择题 答案

题号 答案
1 B
2 D
3 B
4 B
5 B
6 C
7 B
8 B
9 B
10 B

解析

1. 选B。 TLB（Translation Lookaside Buffer）是CPU内部的一个高速缓存，专门用于缓存最近使用过的页表项，以加速逻辑地址到物理地址的转换。A错误：TLB是指令缓存，它是页表项的专门缓存。C错误：TLB在CPU内部，不在磁盘上。D错误：TLB是MMU的一部分，辅助MMU进行地址转换，但不能完全替代MMU（TLB缺失时仍需MMU查询页表）。

2. 选D。 D错误：不同进程中的线程虽然不能直接访问对方的地址空间，但可以通过各种IPC机制（如共享内存、消息队列、管道等）实现数据共享。A正确：同一进程的所有线程共享该进程的地址空间。B正确：线程共享地址空间，切换时不需要切换内存映射，所以开销小于进程切换。C正确：每个线程有自己的程序计数器、寄存器集合和栈空间。

3. 选B。 SPOOLing（Simultaneous Peripheral Operation Online，假脱机操作）技术通过在磁盘上设置输入井和输出井，将独占设备（如打印机）模拟为共享设备，多个进程可以同时请求输出，由SPOOLing守护进程统一管理实际设备的输出。A、C、D均不是SPOOLing的主要作用。

4. 选B。 颠簸（Thrashing）是指系统花费大量时间在页面置换上，而非执行程序。当发生颠簸时，CPU大部分时间处于等待页面调入/调出的状态，导致CPU利用率急剧下降。此时操作系统可能会误判CPU空闲而引入更多进程，进一步加剧颠簸。

5. 选B。 动态链接在运行时加载所需的动态库，当库需要更新时，只需替换动态库文件即可，无需重新链接整个程序。A错误：动态链接不包含库代码，可执行文件更小。C错误：动态链接在运行时有额外的符号解析开销，不一定比静态链接快。D错误：动态链接需要系统中存在相应的动态库，部署更为复杂。

6. 选C。 EXT4使用区段树（Extent Tree）来管理文件数据块，尤其适合大文件。一个区段（Extent）可以表示一段连续的物理块，减少了指针数量。FAT（A）是较旧的文件分配表方式。直接索引块（B）和三级间接索引（D）是传统Unix inode的方式，EXT4虽然兼容但主要使用区段树。

7. 选B。 C-LOOK算法是C-SCAN的改进版本。C-SCAN算法中，磁头移动到磁盘的物理末端才掉头返回起点；而C-LOOK算法中，磁头只移动到最远的请求处就直接返回起点，无需移动到磁盘物理末端。A描述的是C-SCAN。C描述的是SCAN/LOOK（双向处理）。D描述的是SSTF。

8. 选B。 管程（Monitor）是一种高级同步结构，它将共享变量、对变量的操作和同步机制封装在一起，编译器或运行时环境负责保证互斥，程序员只需关注条件变量的使用。这降低了编写正确并发程序的难度，提高了代码的可读性和可维护性。A错误：管程不一定比信号量快。C错误：管程和信号量在表达能力上是等价的。D错误：管程需要条件变量来实现同步。

9. 选B。 Peterson算法使用两个共享变量：一个布尔数组 flag[2]（表示每个进程是否想进入临界区）和一个整型变量 turn（表示当前轮到哪个进程）。通过这两个变量的配合，实现了两个进程间的互斥，并满足互斥、前进和有限等待三个条件。

10. 选B。 工作集模型通过跟踪进程在最近一段时间内访问的页面集合（工作集），确保分配给进程的物理帧数不小于其工作集大小，从而防止颠簸。如果分配给进程的帧数小于工作集大小，进程将频繁产生缺页中断，导致颠簸。

二、填空题 答案

  1. CPU执行指令的四个基本步骤是：取指（Fetch）、译码（Decode）、执行（Execute）和写回（Writeback）。

  2. 在存储器层次结构中，位于寄存器与主存之间的是缓存（Cache）。

  3. 线程的基本状态包括：就绪态、**运行（Running）**态和阻塞态。

  4. 在动态链接中，程序运行时通过PLT（过程链接表）与GOT（全局偏移表）协作完成函数的延迟绑定。

  5. 位置无关代码（PIC）中不包含绝对地址，所有地址均为相对地址，因此可被加载到内存的任意位置。

  6. 延迟绑定（Lazy Binding）将函数的符号解析和重定位推迟到函数第一次被调用时执行。

  7. 时间局部性（Temporal Locality）是指最近被访问的存储器地址很可能在**不久的将来（近期）**再次被访问。

  8. 空间局部性（Spatial Locality）是指当前被访问地址附近的地址很可能很快被访问。

  9. 写时复制（Copy-on-Write, COW）技术中，fork()之后父子进程共享物理页面，仅当其中一方执行写操作时才创建副本。

  10. 虚拟文件系统（VFS）通过提供统一的文件操作接口，使用户能够透明地访问不同文件系统。

  11. RBAC（基于角色的访问控制）（基于角色的访问控制）模型将权限赋予角色，再将角色赋予用户。

  12. 按使用方式分类，设备可以分为独占设备、共享设备和虚拟设备三类。

  13. **SPOOLing（假脱机）**技术利用磁盘作为缓冲区，将独占设备模拟为共享设备，提高了设备的利用率。

  14. 在USB描述符层次结构中，设备描述符之下的层次是**配置（Configuration）**描述符。

  15. 中断处理分为上半部（Top-half）和下半部（Bottom-half）（Bottom-half）两个阶段。

  16. 在Unix/Linux文件系统中，inode（索引节点）（索引节点）存储文件的元数据信息，但文件名除外。

  17. 硬链接（Hard Link）不能跨越文件系统，也不能链接目录。

  18. 并发（Concurrency）是指多个任务在同一个时间间隔内交替执行。

  19. 并行（Parallelism）是指多个任务在同一个时刻同时执行。

  20. 在M:1线程模型中，多个用户线程映射到一个内核线程。

  21. 无锁数据结构的三个级别从弱到强依次为：Obstruction-free、Lock-free和Wait-free。

  22. 在Hoare语义中，条件变量的signal操作会立即将锁和处理器移交给被唤醒的线程。

  23. 在Mesa语义中，条件变量中被唤醒的线程进入**就绪（Ready）**队列，条件可能已不再成立，需要重新检查。

  24. Linux中的futex机制在低竞争时使用**自旋（Spin）**锁以避免系统调用开销，在高竞争时由内核管理阻塞队列。

  25. 采用固定分区存储管理方式时，会产生内部碎片。

  26. 在FIFO页面置换算法中，增加分配的物理帧数反而导致缺页率上升，这种现象称为**Belady（贝拉迪）**异常。

  27. 在EXT4文件系统中，区段（Extent）树主要用于管理大文件的连续数据块区间。

  28. 内存映射文件（Memory-Mapped File）实现了**零（Zero）**拷贝，减少了数据在用户态和内核态之间的复制次数。

  29. 在进程调度的三个层次中，**短程（Short-term）**调度负责选择下一个将要运行的线程，执行频率最高。

  30. 在8086处理器中，SP（堆栈指针）寄存器与**SS（堆栈段）**段寄存器配合使用来管理堆栈操作。

三、简答题 参考答案

第1题：写时复制（Copy-on-Write）技术（4分）

答：

基本原理： 写时复制是一种优化技术。当操作系统通过fork()系统调用创建子进程时，子进程并不立即复制父进程的全部物理内存，而是将父子进程的页表项指向相同的物理页面，并将这些页面标记为"只读"。

  • 当父子进程都只是读取页面时，不会发生任何复制操作，它们共享同一物理页面。
  • 当其中任一进程尝试写入共享页面时，CPU触发页错误（写保护异常）。操作系统的缺页处理程序检测到这是COW场景，便为该进程分配一个新的物理页面，将原始页面的内容复制到新页面，然后更新该进程的页表指向新页面，并将新页面设置为可写。
  • 另一个进程仍然指向原始的物理页面（仍为只读）。

作用：

  • 节省内存： 避免不必要的内存复制，尤其当子进程紧接着调用exec()时，fork()时的大量复制工作被完全避免。
  • 提高效率： 加速了fork()系统调用的执行速度。
  • 在Linux、Unix等现代操作系统中被广泛采用。

第2题：工作集模型与颠簸（4分）

答：

工作集模型的概念：

  • 工作集是指在时间区间 (t - T, t] 内（即最近一段时间T内），进程所访问的所有页面的集合，记为 WS(t, T)。
  • 工作集的大小反映了进程在最近一段时间内的内存需求。
  • 工作集模型利用局部性原理：进程在一段时间内往往只访问相对固定的一部分页面。

防止颠簸的机制：

  • 颠簸（Thrashing）的根本原因是分配给进程的物理帧数小于其工作集大小，导致进程频繁产生缺页中断。
  • 操作系统通过以下方式利用工作集模型防止颠簸：
    1. 监测每个进程的缺页率。
    2. 估算每个进程的工作集大小。
    3. 确保分配给每个进程的物理帧数不少于其工作集大小。
    4. 当总的工作集大小之和超过可用物理内存时，通过挂起部分进程（中程调度/交换），将释放的物理帧分配给活跃进程，使它们的缺页率恢复正常水平。

第3题：管程（Monitor）与信号量（Semaphore）的比较（4分）

答：

相同点：

  • 两者都是用于解决进程/线程间的互斥与同步问题的机制。
  • 两者在表达能力上是等价的，即管程能解决的问题用信号量也能解决，反之亦然。

不同点：

比较维度 管程（Monitor） 信号量（Semaphore）
使用方式 高级语言结构，编译器自动管理互斥 低级的系统调用原语（P/V操作）
互斥实现 管程内部保证互斥，程序员无需显式编写互斥代码 程序员必须显式使用P/V操作保证互斥
错误风险 并发控制逻辑集中，易读易维护，出错概率低 分散在各处，容易遗漏P/V操作导致死锁或破坏互斥
封装性 将共享数据、操作和同步封装在一起，模块化好 数据与同步操作分离，封装性差
条件同步 使用条件变量（Condition Variable）的wait/signal 使用P操作阻塞、V操作唤醒
典型应用 Java synchronized + wait/notify Linux semaphore, pthread semaphore

总结： 管程是信号量的高级封装，更适合构建大型复杂的并发系统；信号量更灵活轻量，适合简单的互斥和同步场景。

第4题：三种文件物理分配方式的优缺点（4分）

答：

分配方式 优点 缺点
连续分配 1. 顺序访问速度快（磁头移动少）
2. 随机访问方便（直接计算块号）
3. 实现简单，管理开销小		 1. 产生外部碎片，需定期压缩
2. 文件大小必须在创建时确定，不利于动态增长
3. 删除或修改大小时不灵活
链接分配 1. 无外部碎片，空间利用率高
2. 文件可以动态增长
3. 文件创建时无需声明大小		 1. 随机访问慢（需遍历链表）
2. 链接指针占用存储空间
3. 一个指针损坏会影响后续数据读取
4. 不支持高效的直接访问
索引分配 1. 随机访问速度快（直接通过索引找到块）
2. 文件可动态增长
3. 无外部碎片
4. 支持大文件（通过多级索引）		 1. 索引块本身占用存储空间
2. 小文件时索引块开销相对较大
3. 索引块的管理（多级索引）增加复杂度

结论： 现代文件系统（如EXT4）采用混合策略：小文件使用直接索引，大文件使用区段树（Extent Tree），兼顾了小文件和大文件的性能需求。

第5题：四种磁盘调度算法的比较（4分）

答：

算法 工作方式 特点
SCAN（电梯算法） 磁头从一端向另一端移动，沿途响应请求；到达一端后改变方向。 无饥饿现象；平均寻道时间优于FCFS；两端请求等待时间较长。
C-SCAN（循环SCAN） 磁头单向移动（如从外到内），沿途响应请求；到达最内端后直接返回最外端，返回途中不处理请求。 等待时间更均匀，各磁道响应公平性更好；比SCAN多一次"空跑"距离。
LOOK 改进的SCAN：磁头移动到最远的请求处即掉头，不必移动到磁盘物理末端。 比SCAN效率更高；同样无饥饿。
C-LOOK 改进的C-SCAN：磁头移动到最远的请求处即返回起点，不必移动到磁盘物理末端，返回时不处理请求。 在四种算法中平均寻道时间通常最优；等待时间最均匀；效率高于C-SCAN。

总结： 实际系统中常使用C-LOOK或LOOK算法，兼具公平性和高效率。

四、计算与分析题 详细解答

第1题 银行家算法（10分）

（1）计算 Need 矩阵（2分）

Need = Max - Allocation

| 进程 | Need（尚需） |
|:----😐:—😐:—😐:—😐
| | A | B | C |
| P0 | 7 | 4 | 3 |
| P1 | 1 | 2 | 2 |
| P2 | 6 | 0 | 0 |
| P3 | 0 | 1 | 1 |
| P4 | 4 | 3 | 1 |

计算过程（以P0为例）：

  • Need[P0] = Max[P0] - Allocation[P0] = (7, 5, 3) - (0, 1, 0) = (7, 4, 3)

类似地计算其他进程：

  • Need[P1] = (3, 2, 2) - (2, 0, 0) = (1, 2, 2)
  • Need[P2] = (9, 0, 2) - (3, 0, 2) = (6, 0, 0)
  • Need[P3] = (2, 2, 2) - (2, 1, 1) = (0, 1, 1)
  • Need[P4] = (4, 3, 3) - (0, 0, 2) = (4, 3, 1)
（2）T0 时刻是否处于安全状态？（4分）

初始条件：

  • Available = (3, 3, 2)
  • Work = Available = (3, 3, 2)
  • Finish = [false, false, false, false, false]

安全性检查过程：

| 步骤 | 进程 | Work（可用资源） | Need | 条件判断 | Allocation | 进程释放后Work |
|:----😐:----😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐
| | | A | B | C | A | B | C | | A | B | C | A | B | C |
| 初始 | | 3 | 3 | 2 | | | | | | | | | | |
| 1 | P1 | 3 | 3 | 2 | 1 | 2 | 2 | 1≤3,2≤3,2≤2 ✓ | 2 | 0 | 0 | 5 | 3 | 2 |
| 2 | P3 | 5 | 3 | 2 | 0 | 1 | 1 | 0≤5,1≤3,1≤2 ✓ | 2 | 1 | 1 | 7 | 4 | 3 |
| 3 | P0 | 7 | 4 | 3 | 7 | 4 | 3 | 7≤7,4≤4,3≤3 ✓ | 0 | 1 | 0 | 7 | 5 | 3 |
| 4 | P2 | 7 | 5 | 3 | 6 | 0 | 0 | 6≤7,0≤5,0≤3 ✓ | 3 | 0 | 2 | 10 | 5 | 5 |
| 5 | P4 | 10 | 5 | 5 | 4 | 3 | 1 | 4≤10,3≤5,1≤5 ✓ | 0 | 0 | 2 | 10 | 5 | 7 |

详细判断过程：

步骤1： 尝试P1

  • Need[P1] = (1, 2, 2) ≤ Work = (3, 3, 2) → 满足条件
  • P1运行完毕后释放资源：Work = (3, 3, 2) + (2, 0, 0) = (5, 3, 2)
  • Finish[P1] = true

步骤2： 尝试P3

  • Need[P3] = (0, 1, 1) ≤ Work = (5, 3, 2) → 满足条件
  • P3运行完毕后释放资源：Work = (5, 3, 2) + (2, 1, 1) = (7, 4, 3)
  • Finish[P3] = true

步骤3： 尝试P0

  • Need[P0] = (7, 4, 3) ≤ Work = (7, 4, 3) → 满足条件
  • P0运行完毕后释放资源：Work = (7, 4, 3) + (0, 1, 0) = (7, 5, 3)
  • Finish[P0] = true

步骤4： 尝试P2

  • Need[P2] = (6, 0, 0) ≤ Work = (7, 5, 3) → 满足条件
  • P2运行完毕后释放资源：Work = (7, 5, 3) + (3, 0, 2) = (10, 5, 5)
  • Finish[P2] = true

步骤5： 尝试P4

  • Need[P4] = (4, 3, 1) ≤ Work = (10, 5, 5) → 满足条件
  • P4运行完毕后释放资源：Work = (10, 5, 5) + (0, 0, 2) = (10, 5, 7)
  • Finish[P4] = true

结果： 所有进程的Finish均为true，系统处于安全状态。
安全序列： <P1, P3, P0, P2, P4>

注：安全序列可能不唯一，如 <P3, P1, P0, P2, P4> 也是安全的（步骤1先选P3也可行）。

（3）P1请求资源 (1, 0, 2) 能否分配？（4分）

步骤1：检查请求是否 ≤ Need

  • Request1 = (1, 0, 2)
  • Need[P1] = (1, 2, 2)
  • 1 ≤ 1 ✓，0 ≤ 2 ✓，2 ≤ 2 ✓ → 满足条件

步骤2：检查请求是否 ≤ Available

  • Request1 = (1, 0, 2)
  • Available = (3, 3, 2)
  • 1 ≤ 3 ✓，0 ≤ 3 ✓，2 ≤ 2 ✓ → 满足条件

步骤3：试探性分配，更新系统状态

  • Available’ = Available - Request1 = (3, 3, 2) - (1, 0, 2) = (2, 3, 0)
  • Allocation’[P1] = Allocation[P1] + Request1 = (2, 0, 0) + (1, 0, 2) = (3, 0, 2)
  • Need’[P1] = Need[P1] - Request1 = (1, 2, 2) - (1, 0, 2) = (0, 2, 0)

更新后的系统状态：

| 进程 | Allocation’ | Max | Need’ |
|:----😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐
| | A | B | C | A | B | C | A | B | C |
| P0 | 0 | 1 | 0 | 7 | 5 | 3 | 7 | 4 | 3 |
| P1 | 3 | 0 | 2 | 3 | 2 | 2 | 0 | 2 | 0 |
| P2 | 3 | 0 | 2 | 9 | 0 | 2 | 6 | 0 | 0 |
| P3 | 2 | 1 | 1 | 2 | 2 | 2 | 0 | 1 | 1 |
| P4 | 0 | 0 | 2 | 4 | 3 | 3 | 4 | 3 | 1 |

Available’ = (2, 3, 0)

步骤4：检查新状态是否安全

Work = (2, 3, 0)，Finish = [false, false, false, false, false]

| 步骤 | 进程 | Work | Need’ | 条件判断 | Allocation’ | 释放后Work |
|:----😐:----😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐
| | | A | B | C | A | B | C | | A | B | C | A | B | C |
| 初始 | | 2 | 3 | 0 | | | | | | | | | | |
| 1 | P1 | 2 | 3 | 0 | 0 | 2 | 0 | 0≤2,2≤3,0≤0 ✓ | 3 | 0 | 2 | 5 | 3 | 2 |
| 2 | P3 | 5 | 3 | 2 | 0 | 1 | 1 | 0≤5,1≤3,1≤2 ✓ | 2 | 1 | 1 | 7 | 4 | 3 |
| 3 | P0 | 7 | 4 | 3 | 7 | 4 | 3 | 7≤7,4≤4,3≤3 ✓ | 0 | 1 | 0 | 7 | 5 | 3 |
| 4 | P2 | 7 | 5 | 3 | 6 | 0 | 0 | 6≤7,0≤5,0≤3 ✓ | 3 | 0 | 2 | 10 | 5 | 5 |
| 5 | P4 | 10 | 5 | 5 | 4 | 3 | 1 | 4≤10,3≤5,1≤5 ✓ | 0 | 0 | 2 | 10 | 5 | 7 |

详细判断过程：

步骤1： 尝试P1

  • Need’[P1] = (0, 2, 0) ≤ Work = (2, 3, 0) → 满足条件
  • 释放后：Work = (2, 3, 0) + (3, 0, 2) = (5, 3, 2)
  • Finish[P1] = true

步骤2： 尝试P3

  • Need’[P3] = (0, 1, 1) ≤ Work = (5, 3, 2) → 满足条件
  • 释放后：Work = (5, 3, 2) + (2, 1, 1) = (7, 4, 3)
  • Finish[P3] = true

步骤3： 尝试P0

  • Need’[P0] = (7, 4, 3) ≤ Work = (7, 4, 3) → 满足条件
  • 释放后：Work = (7, 4, 3) + (0, 1, 0) = (7, 5, 3)
  • Finish[P0] = true

步骤4： 尝试P2

  • Need’[P2] = (6, 0, 0) ≤ Work = (7, 5, 3) → 满足条件
  • 释放后：Work = (7, 5, 3) + (3, 0, 2) = (10, 5, 5)
  • Finish[P2] = true

步骤5： 尝试P4

  • Need’[P4] = (4, 3, 1) ≤ Work = (10, 5, 5) → 满足条件
  • 释放后：Work = (10, 5, 5) + (0, 0, 2) = (10, 5, 7)
  • Finish[P4] = true

结论： 分配后系统仍然处于安全状态。安全序列为 <P1, P3, P0, P2, P4>。因此，系统可以分配资源(1, 0, 2)给P1。

第2题 页面置换算法与多级页表地址转换（10分）

第一部分：页面置换算法（6分）

页面引用序列：3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4
物理块数 = 3，初始均为空。

（1）FIFO（先进先出）算法（2分）

FIFO置换最早进入内存的页面。

步骤 页面 帧0 帧1 帧2 缺页 说明
1 3 3 F 空闲，装入
2 2 3 2 F 空闲，装入
3 1 3 2 1 F 空闲，装满
4 0 0 2 1 F 置换3（最早进入）
5 3 0 3 1 F 置换2
6 2 0 3 2 F 置换1
7 4 4 3 2 F 置换0
8 3 4 3 2 命中
9 2 4 3 2 命中
10 1 4 1 2 F 置换3
11 0 4 1 0 F 置换2
12 4 4 1 0 命中

缺页次数：9次（步骤1, 2, 3, 4, 5, 6, 7, 10, 11）

缺页率：9/12 = 75%

（2）LRU（最近最久未使用）算法（2分）

LRU置换最近最久未被使用的页面。

步骤 页面 帧0 帧1 帧2 缺页 最近使用顺序（左→右：最近→最久） 说明
1 3 3 F [3] 空闲，装入
2 2 3 2 F [2, 3] 空闲，装入
3 1 3 2 1 F [1, 2, 3] 空闲，装满
4 0 0 2 1 F [0, 1, 2] 置换3（最久未使用）
5 3 0 3 1 F [3, 0, 1] 置换2
6 2 0 3 2 F [2, 3, 0] 置换1
7 4 4 3 2 F [4, 2, 3] 置换0
8 3 4 3 2 [3, 4, 2] 命中，3移到最近
9 2 4 3 2 [2, 3, 4] 命中，2移到最近
10 1 4 1 2 F [1, 2, 4] 置换3（最久未使用）
11 0 0 1 2 F [0, 1, 2] 置换4（最久未使用）
12 4 0 1 4 F [4, 0, 1] 置换2（最久未使用）

缺页次数：10次（步骤1, 2, 3, 4, 5, 6, 7, 10, 11, 12）

缺页率：10/12 ≈ 83.3%

（3）OPT / LFD（最佳置换）算法（2分）

OPT算法置换未来最远才会被访问的页面，或永不使用的页面。其置换过程如下：

步骤 页面 帧0 帧1 帧2 缺页 说明
1 3 3 F 空闲，装入
2 2 3 2 F 空闲，装入
3 1 3 2 1 F 空闲，装满
4 0 3 2 0 F 置换1：3未来用(5), 2(6), 1(10最远)
5 3 3 2 0 命中
6 2 3 2 0 命中
7 4 3 2 4 F 置换0：3(8), 2(9), 0(11最远)
8 3 3 2 4 命中
9 2 3 2 4 命中
10 1 1 2 4 F 置换3：3不再用, 2不再用, 4(12)
11 0 0 2 4 F 置换1：1不再用, 2不再用, 4(12). 选1
12 4 0 2 4 命中（4已在帧2中）

置换过程详细分析：

  • 步骤4（页面0）： 内存中有[3, 2, 1]。未来引用位置：3(步骤5)、2(步骤6)、1(步骤10→最远)。因此置换页面1，将页面0装入帧2。
  • 步骤7（页面4）： 内存中有[3, 2, 0]。未来引用位置：3(步骤8)、2(步骤9)、0(步骤11→最远)。因此置换页面0，将页面4装入帧2。
  • 步骤10（页面1）： 内存中有[3, 2, 4]。未来引用位置：3(不再使用)、2(不再使用)、4(步骤12)。因此选择3或2，置换页面3，将页面1装入帧0。
  • 步骤11（页面0）： 内存中有[1, 2, 4]。未来引用位置：1(不再使用)、2(不再使用)、4(步骤12)。4即将被使用，因此置换页面1或2，将页面0装入帧0。
  • 步骤12（页面4）： 页面4已在帧2中，命中。

缺页次数：7次（步骤1, 2, 3, 4, 7, 10, 11）

缺页率：7/12 ≈ 58.3%

三种算法对比：

算法 缺页次数 缺页率
FIFO 9 75%
LRU 10 83.3%
OPT 7 58.3%
第二部分：多级页表地址转换（4分）

（1）虚拟地址划分（2分）

虚拟地址 0x00303004，页面大小 4KB = 2^12 B，所以偏移量为12位。

第一步：将 0x00303004 转换为二进制
0x00303004 = 0000 0000 0011 0000 0011 0000 0000 0100 (32位)

第二步：划分虚拟地址

  • 页目录索引（bits 31-22，共10位）：0000 0000 00 = 0x000
  • 二级页表索引（bits 21-12，共10位）：11 0000 0011 = 0x303
  • 页内偏移量（bits 11-0，共12位）：0000 0000 0100 = 0x004

所以：

  • 页目录索引 = 0x000（= 0）
  • 二级页表索引 = 0x303（= 771）
  • 页内偏移量 = 0x004（= 4）

（2）物理地址计算（2分）

步骤1： 查找页目录（顶级页表）

  • 页目录物理帧号 = 0x1000
  • 页目录的物理基地址 = 0x1000 << 12 = 0x1000000
  • 使用索引 0x000 查找页目录：从物理地址 0x1000000 + 0x000 × 4 = 0x1000000 处读取页表项
  • 该页表项指向二级页表的物理帧号 = 0x2000

步骤2： 查找二级页表

  • 二级页表物理帧号 = 0x2000
  • 二级页表的物理基地址 = 0x2000 << 12 = 0x2000000
  • 使用索引 0x303 查找二级页表：从物理地址 0x2000000 + 0x303 × 4 = 0x2000000 + 0xC0C = 0x2000C0C 处读取页表项
  • 该页表项给出的物理帧号 = 0x3000

步骤3： 计算最终物理地址

  • 物理帧号 = 0x3000
  • 物理基地址 = 0x3000 << 12 = 0x3000000
  • 物理地址 = 物理基地址 + 页内偏移量 = 0x3000000 + 0x004 = 0x3000004

验证地址划分：

虚拟地址 0x00303004:
  二进制：0000 0000 0011 0000 0011 0000 0000 0100
          |--页目录--|--二级页表---|----偏移量----|
              00          303         004

因此：页目录索引=0，二级页表索引=0x303，页内偏移=0x004

五、综合题 详细解答（10分）

读者-写者问题（写者优先）

（1）信号量与共享变量定义（3分）

定义以下信号量和共享变量：

semaphore mutex_r = 1;       // 保护读者计数器 read_count 的互斥信号量
semaphore mutex_w = 1;       // 保护写者计数器 write_count 的互斥信号量
semaphore write_first = 1;   // 写者优先信号量，用于阻塞读者（当有写者在等待时）
semaphore rw_mutex = 1;      // 读写互斥信号量，控制对共享文件的访问

int read_count = 0;          // 当前正在读取的读者数量
int write_count = 0;         // 当前正在等待或正在写入的写者数量

各信号量的作用和初始值：

信号量 初始值 作用
mutex_r 1 保护对 read_count 变量的互斥访问
mutex_w 1 保护对 write_count 变量的互斥访问
write_first 1 实现写者优先：当有写者等待时，阻止新读者开始读取
rw_mutex 1 读写互斥：写者独占文件，读者之间可共享
（2）读者进程伪代码（3分）
void reader() {
    while (true) {
        // 读者进入区
        P(write_first);      // 检查是否有写者在等待，若有则阻塞
        
        P(mutex_r);          // 互斥访问 read_count
        read_count++;        // 读者数量+1
        if (read_count == 1) // 第一个读者
            P(rw_mutex);     // 锁定文件，阻止写者写入
        V(mutex_r);          // 释放 read_count 互斥
        
        V(write_first);      // 释放写者优先信号量，让其他读者可以进入
        
        // 临界区：读取共享文件
        读者读取文件...
        
        // 读者退出区
        P(mutex_r);          // 互斥访问 read_count
        read_count--;        // 读者数量-1
        if (read_count == 0) // 最后一个读者
            V(rw_mutex);     // 解锁文件，允许写者写入
        V(mutex_r);          // 释放 read_count 互斥
    }
}
（3）写者进程伪代码（3分）
void writer() {
    while (true) {
        // 写者进入区
        P(mutex_w);          // 互斥访问 write_count
        write_count++;       // 写者数量+1
        if (write_count == 1)// 第一个写者
            P(write_first);  // 阻止新读者进入（写者优先的关键）
        V(mutex_w);          // 释放 write_count 互斥
        
        P(rw_mutex);         // 请求文件独占访问（等待所有读者退出）
        
        // 临界区：写入共享文件
        写者写入文件...
        
        // 写者退出区
        V(rw_mutex);         // 释放文件访问权限
        
        P(mutex_w);          // 互斥访问 write_count
        write_count--;       // 写者数量-1
        if (write_count == 0)// 最后一个写者
            V(write_first);  // 允许读者进入
        V(mutex_w);          // 释放 write_count 互斥
    }
}
（4）死锁与饥饿分析（1分）

为什么不会发生死锁：

  • 信号量的P操作顺序是固定的，不存在循环等待。
  • 读者先P(write_first)再P(mutex_r)再P(rw_mutex)（只有第一个读者才需要rw_mutex）。
  • 写者先P(mutex_w)再P(write_first)再P(rw_mutex)。
  • 没有形成循环等待链，因此不会发生死锁。

饥饿可能性分析：

  • 该方案实现了写者优先策略：
    • 当有写者等待时（write_count > 0），新到达的读者会被 write_first 信号量阻塞。
    • 只有当所有写者都完成时（write_count == 0），write_first 才会被释放，阻塞的读者才能进入。
  • 读者可能存在饥饿：如果有源源不断的写者到达，读者可能长时间无法访问文件。在极端情况下，读者可能无限期被推迟。
  • 写者不会饥饿：读者在读的过程中，其他读者可以同时进入，但写者只需等待最后一个读者读完即可。且写者优先策略保证了新读者不会插在写者前面。

注：若要完全避免饥饿，可采用"公平"策略（如按到达顺序排队），但会降低并发度。实际系统可根据需求在公平性和性能之间权衡。

（完）

操作系统 模拟试卷2

考试时间：120分钟 满分：100分

一、单项选择题（共10题，每题2分，共20分）

请从每题的四个选项中选择一个最合适的答案。

1. 下列关于TLB（转译后备缓冲器）的描述中，正确的是（ ）。
A. TLB是CPU内部的一级指令缓存
B. TLB用于缓存最近使用的页表项，加速地址转换
C. TLB存储在磁盘上，需要时调入内存
D. TLB的作用是替代MMU进行所有的地址转换

2. 下列关于线程与进程的叙述中，错误的是（ ）。
A. 同一进程中的多个线程共享该进程的地址空间
B. 线程切换的开销通常小于进程切换的开销
C. 每个线程拥有独立的程序计数器、寄存器和栈
D. 不同进程中的线程不能以任何方式共享数据

3. SPOOLing技术的主要作用是（ ）。
A. 提高CPU的运算速度
B. 将独占设备转换为共享设备
C. 增加内存的可用容量
D. 实现进程间的互斥与同步

4. 当系统发生颠簸（Thrashing）时，CPU利用率通常会（ ）。
A. 急剧上升
B. 急剧下降
C. 保持不变
D. 先上升后下降

5. 下列关于动态链接与静态链接的比较中，正确的是（ ）。
A. 静态链接生成的可执行文件比动态链接的更小
B. 动态链接的程序更新更方便，只需替换动态库文件
C. 动态链接程序的运行速度一定比静态链接快
D. 静态链接的程序需要依赖系统中存在相应的动态库

6. 在EXT4文件系统中，管理大文件数据块所采用的主要数据结构是（ ）。
A. FAT（文件分配表）
B. 直接索引块
C. 区段树（Extent Tree）
D. 三级间接索引

7. C-LOOK磁盘调度算法相比于C-SCAN算法的改进之处在于（ ）。
A. 磁头移动到磁盘的物理末端才掉头
B. 磁头只移动到最远的请求处便直接返回起点
C. 磁头在双向移动过程中都处理请求
D. 优先处理离当前磁头位置最近的请求

8. 管程（Monitor）相比于信号量（Semaphore）的主要优势是（ ）。
A. 管程的执行速度比信号量快得多
B. 管程将同步机制封装在内部，降低了编写正确并发程序的难度
C. 管程能够解决所有类型的同步问题，而信号量不能
D. 管程不需要条件变量即可实现线程同步

9. 在Peterson算法中，两个进程实现互斥所使用的共享变量是（ ）。
A. 一个二元信号量
B. 一个flag数组和一个turn变量
C. 一个互斥锁（Mutex）
D. 一个条件变量

10. 工作集模型（Working Set Model）的主要目的是（ ）。
A. 提高CPU的指令执行效率
B. 防止系统发生颠簸（Thrashing）
C. 减少页面置换算法的计算开销
D. 提高磁盘的读写速度

二、填空题（共30空，每空1分，共30分）

  1. CPU执行指令的四个基本步骤是：取指（Fetch）、____、执行（Execute）和写回（Writeback）。

  2. 在存储器层次结构中，位于寄存器与主存之间的是____。

  3. 线程的基本状态包括：就绪态、____态和阻塞态。

  4. 在动态链接中，程序运行时通过____（过程链接表）与GOT（全局偏移表）协作完成函数的延迟绑定。

  5. 位置无关代码（PIC）中不包含____地址，所有地址均为相对地址，因此可被加载到内存的任意位置。

  6. 延迟绑定（Lazy Binding）将函数的符号解析和重定位推迟到函数____被调用时执行。

  7. 时间局部性（Temporal Locality）是指最近被访问的存储器地址很可能在____再次被访问。

  8. 空间局部性（Spatial Locality）是指当前被访问地址____的地址很可能很快被访问。

  9. 写时复制（Copy-on-Write, COW）技术中，fork()之后父子进程____物理页面，仅当其中一方执行写操作时才创建副本。

  10. 虚拟文件系统（VFS）通过提供____的文件操作接口，使用户能够透明地访问不同文件系统。

  11. ____（基于角色的访问控制）模型将权限赋予角色，再将角色赋予用户。

  12. 按使用方式分类，设备可以分为独占设备、共享设备和____设备三类。

  13. ____技术利用磁盘作为缓冲区，将独占设备模拟为共享设备，提高了设备的利用率。

  14. 在USB描述符层次结构中，设备描述符之下的层次是____描述符。

  15. 中断处理分为上半部（Top-half）和____（Bottom-half）两个阶段。

  16. 在Unix/Linux文件系统中，____（索引节点）存储文件的元数据信息，但文件名除外。

  17. 硬链接（Hard Link）不能跨越____系统，也不能链接目录。

  18. 并发（Concurrency）是指多个任务在同一个时间____内交替执行。

  19. 并行（Parallelism）是指多个任务在同一个____同时执行。

  20. 在M:1线程模型中，多个____线程映射到一个内核线程。

  21. 无锁数据结构的三个级别从弱到强依次为：Obstruction-free、____和Wait-free。

  22. 在Hoare语义中，条件变量的signal操作会____将锁和处理器移交给被唤醒的线程。

  23. 在Mesa语义中，条件变量中被唤醒的线程进入____队列，条件可能已不再成立，需要重新检查。

  24. Linux中的futex机制在低竞争时使用____锁以避免系统调用开销，在高竞争时由内核管理阻塞队列。

  25. 采用固定分区存储管理方式时，会产生____碎片。

  26. 在FIFO页面置换算法中，增加分配的物理帧数反而导致缺页率上升，这种现象称为____异常。

  27. 在EXT4文件系统中，区段（Extent）树主要用于管理____的连续数据块区间。

  28. 内存映射文件（Memory-Mapped File）实现了____拷贝，减少了数据在用户态和内核态之间的复制次数。

  29. 在进程调度的三个层次中，____调度负责选择下一个将要运行的线程，执行频率最高。

  30. 在8086处理器中，SP（堆栈指针）寄存器与____段寄存器配合使用来管理堆栈操作。

三、简答题（共5题，每题4分，共20分）

1. 请简述写时复制（Copy-on-Write）技术的基本原理及其在操作系统中的作用。（4分）

2. 请简述工作集模型（Working Set Model）的概念，并说明它如何用于防止颠簸（Thrashing）。（4分）

3. 请比较管程（Monitor）与信号量（Semaphore）在解决进程同步问题时的异同。（4分）

4. 请简述连续分配、链接分配和索引分配三种文件物理分配方式各自的优缺点。（4分）

5. 请比较SCAN、C-SCAN、LOOK和C-LOOK四种磁盘调度算法的特点。（4分）

四、计算与分析题（共2题，每题10分，共20分）

第1题：银行家算法（Banker’s Algorithm）（10分）

设系统中有三种资源 A、B、C，数量分别为 A=10、B=5、C=7。现有五个进程 P0 ~ P4，在 T0 时刻的资源分配情况如下表所示（Allocation 表示已分配资源，Max 表示最大需求资源，Available 表示当前可用资源）：

T0时刻系统状态：

| 进程 | Allocation（已分配） | Max（最大需求） | Need（尚需） |
|:----😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐
| | A | B | C | A | B | C | A | B | C |
| P0 | 0 | 1 | 0 | 7 | 5 | 3 | | | |
| P1 | 2 | 0 | 0 | 3 | 2 | 2 | | | |
| P2 | 3 | 0 | 2 | 9 | 0 | 2 | | | |
| P3 | 2 | 1 | 1 | 2 | 2 | 2 | | | |
| P4 | 0 | 0 | 2 | 4 | 3 | 3 | | | |

Available（当前可用资源）： A = 3，B = 3，C = 2

请回答以下问题：
（1）计算每个进程的 Need 矩阵（尚需资源量），填入上表。（2分）
（2）T0 时刻系统是否处于安全状态？如果是，请给出一个安全序列并说明判断过程；如果不是，请说明原因。（4分）
（3）若在 T0 时刻之后，进程 P1 发出请求向量 Request1 = (1, 0, 2)，系统能否将资源分配给 P1？请逐步说明判断过程。（4分）

第2题：页面置换算法与多级页表地址转换（10分）

第一部分：页面置换算法（6分）

某程序在一个请求分页系统中运行，页面引用序列为：

3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4

分配给该程序的物理块（帧）数量为 3块，初始时所有帧均为空。

请分别计算以下三种页面置换算法的缺页次数：
（1）先进先出（FIFO）页面置换算法。（2分）
（2）最近最久未使用（LRU）页面置换算法。（2分）
（3）最佳（Optimal）页面置换算法。（2分）

要求：对每种算法，以表格形式列出每次页面访问时内存中页面的变化情况，缺页处标注"F"。

第二部分：多级页表地址转换（4分）

某32位计算机系统采用二级页表结构，页面大小为 4KB（2^12 B）。其中：

  • 顶级页表（页目录）有 2^10 = 1024 个表项，占用一页
  • 二级页表同样有 2^10 = 1024 个表项，每个占用一页
  • 页表项（PTE）大小为 4字节

给定一个虚拟地址 0x00303004（十六进制），请回答：
（1）该虚拟地址的页目录索引、二级页表索引和页内偏移量分别是多少？（用十六进制表示）（2分）
（2）假设顶级页表（页目录）的物理帧号为 0x1000，相关的二级页表的物理帧号为 0x2000，二级页表中对应页表项给出的物理帧号为 0x3000，请计算最终的物理地址。（2分）

五、综合题（共1题，共10分）

读者-写者问题（Readers-Writers Problem）

有一个共享数据文件，多个读者（Reader）和写者（Writer）进程需要同时访问该文件。同步要求如下：

  1. 多个读者可以同时读取文件，不互斥。
  2. 写者在写入时必须独占文件，即同一时间只能有一个写者写入，且读者不能同时读取。
  3. 当有写者在等待时，新到达的读者不能开始读取（写者优先策略，避免写者饥饿）。

请使用信号量机制实现上述"写者优先"的读者-写者同步方案。

完成以下问题：
（1）定义所需的全部信号量及共享变量，说明每个信号量的作用和初始值。（3分）
（2）写出读者进程的伪代码。（3分）
（3）写出写者进程的伪代码。（3分）
（4）说明该方案为什么能避免死锁，并分析是否仍存在饥饿的可能性。（1分）

参考答案与解析

一、单项选择题 答案

题号 答案
1 B
2 D
3 B
4 B
5 B
6 C
7 B
8 B
9 B
10 B

解析

1. 选B。 TLB（Translation Lookaside Buffer）是CPU内部的一个高速缓存，专门用于缓存最近使用过的页表项，以加速逻辑地址到物理地址的转换。A错误：TLB是指令缓存，它是页表项的专门缓存。C错误：TLB在CPU内部，不在磁盘上。D错误：TLB是MMU的一部分，辅助MMU进行地址转换，但不能完全替代MMU（TLB缺失时仍需MMU查询页表）。

2. 选D。 D错误：不同进程中的线程虽然不能直接访问对方的地址空间，但可以通过各种IPC机制（如共享内存、消息队列、管道等）实现数据共享。A正确：同一进程的所有线程共享该进程的地址空间。B正确：线程共享地址空间，切换时不需要切换内存映射，所以开销小于进程切换。C正确：每个线程有自己的程序计数器、寄存器集合和栈空间。

3. 选B。 SPOOLing（Simultaneous Peripheral Operation Online，假脱机操作）技术通过在磁盘上设置输入井和输出井，将独占设备（如打印机）模拟为共享设备，多个进程可以同时请求输出，由SPOOLing守护进程统一管理实际设备的输出。A、C、D均不是SPOOLing的主要作用。

4. 选B。 颠簸（Thrashing）是指系统花费大量时间在页面置换上，而非执行程序。当发生颠簸时，CPU大部分时间处于等待页面调入/调出的状态，导致CPU利用率急剧下降。此时操作系统可能会误判CPU空闲而引入更多进程，进一步加剧颠簸。

5. 选B。 动态链接在运行时加载所需的动态库，当库需要更新时，只需替换动态库文件即可，无需重新链接整个程序。A错误：动态链接不包含库代码，可执行文件更小。C错误：动态链接在运行时有额外的符号解析开销，不一定比静态链接快。D错误：动态链接需要系统中存在相应的动态库，部署更为复杂。

6. 选C。 EXT4使用区段树（Extent Tree）来管理文件数据块，尤其适合大文件。一个区段（Extent）可以表示一段连续的物理块，减少了指针数量。FAT（A）是较旧的文件分配表方式。直接索引块（B）和三级间接索引（D）是传统Unix inode的方式，EXT4虽然兼容但主要使用区段树。

7. 选B。 C-LOOK算法是C-SCAN的改进版本。C-SCAN算法中，磁头移动到磁盘的物理末端才掉头返回起点；而C-LOOK算法中，磁头只移动到最远的请求处就直接返回起点，无需移动到磁盘物理末端。A描述的是C-SCAN。C描述的是SCAN/LOOK（双向处理）。D描述的是SSTF。

8. 选B。 管程（Monitor）是一种高级同步结构，它将共享变量、对变量的操作和同步机制封装在一起，编译器或运行时环境负责保证互斥，程序员只需关注条件变量的使用。这降低了编写正确并发程序的难度，提高了代码的可读性和可维护性。A错误：管程不一定比信号量快。C错误：管程和信号量在表达能力上是等价的。D错误：管程需要条件变量来实现同步。

9. 选B。 Peterson算法使用两个共享变量：一个布尔数组 flag[2]（表示每个进程是否想进入临界区）和一个整型变量 turn（表示当前轮到哪个进程）。通过这两个变量的配合，实现了两个进程间的互斥，并满足互斥、前进和有限等待三个条件。

10. 选B。 工作集模型通过跟踪进程在最近一段时间内访问的页面集合（工作集），确保分配给进程的物理帧数不小于其工作集大小，从而防止颠簸。如果分配给进程的帧数小于工作集大小，进程将频繁产生缺页中断，导致颠簸。

二、填空题 答案

  1. CPU执行指令的四个基本步骤是：取指（Fetch）、译码（Decode）、执行（Execute）和写回（Writeback）。

  2. 在存储器层次结构中，位于寄存器与主存之间的是缓存（Cache）。

  3. 线程的基本状态包括：就绪态、**运行（Running）**态和阻塞态。

  4. 在动态链接中，程序运行时通过PLT（过程链接表）与GOT（全局偏移表）协作完成函数的延迟绑定。

  5. 位置无关代码（PIC）中不包含绝对地址，所有地址均为相对地址，因此可被加载到内存的任意位置。

  6. 延迟绑定（Lazy Binding）将函数的符号解析和重定位推迟到函数第一次被调用时执行。

  7. 时间局部性（Temporal Locality）是指最近被访问的存储器地址很可能在**不久的将来（近期）**再次被访问。

  8. 空间局部性（Spatial Locality）是指当前被访问地址附近的地址很可能很快被访问。

  9. 写时复制（Copy-on-Write, COW）技术中，fork()之后父子进程共享物理页面，仅当其中一方执行写操作时才创建副本。

  10. 虚拟文件系统（VFS）通过提供统一的文件操作接口，使用户能够透明地访问不同文件系统。

  11. RBAC（基于角色的访问控制）（基于角色的访问控制）模型将权限赋予角色，再将角色赋予用户。

  12. 按使用方式分类，设备可以分为独占设备、共享设备和虚拟设备三类。

  13. **SPOOLing（假脱机）**技术利用磁盘作为缓冲区，将独占设备模拟为共享设备，提高了设备的利用率。

  14. 在USB描述符层次结构中，设备描述符之下的层次是**配置（Configuration）**描述符。

  15. 中断处理分为上半部（Top-half）和下半部（Bottom-half）（Bottom-half）两个阶段。

  16. 在Unix/Linux文件系统中，inode（索引节点）（索引节点）存储文件的元数据信息，但文件名除外。

  17. 硬链接（Hard Link）不能跨越文件系统，也不能链接目录。

  18. 并发（Concurrency）是指多个任务在同一个时间间隔内交替执行。

  19. 并行（Parallelism）是指多个任务在同一个时刻同时执行。

  20. 在M:1线程模型中，多个用户线程映射到一个内核线程。

  21. 无锁数据结构的三个级别从弱到强依次为：Obstruction-free、Lock-free和Wait-free。

  22. 在Hoare语义中，条件变量的signal操作会立即将锁和处理器移交给被唤醒的线程。

  23. 在Mesa语义中，条件变量中被唤醒的线程进入**就绪（Ready）**队列，条件可能已不再成立，需要重新检查。

  24. Linux中的futex机制在低竞争时使用**自旋（Spin）**锁以避免系统调用开销，在高竞争时由内核管理阻塞队列。

  25. 采用固定分区存储管理方式时，会产生内部碎片。

  26. 在FIFO页面置换算法中，增加分配的物理帧数反而导致缺页率上升，这种现象称为**Belady（贝拉迪）**异常。

  27. 在EXT4文件系统中，区段（Extent）树主要用于管理大文件的连续数据块区间。

  28. 内存映射文件（Memory-Mapped File）实现了**零（Zero）**拷贝，减少了数据在用户态和内核态之间的复制次数。

  29. 在进程调度的三个层次中，**短程（Short-term）**调度负责选择下一个将要运行的线程，执行频率最高。

  30. 在8086处理器中，SP（堆栈指针）寄存器与**SS（堆栈段）**段寄存器配合使用来管理堆栈操作。

三、简答题 参考答案

第1题：写时复制（Copy-on-Write）技术（4分）

答：

基本原理： 写时复制是一种优化技术。当操作系统通过fork()系统调用创建子进程时，子进程并不立即复制父进程的全部物理内存，而是将父子进程的页表项指向相同的物理页面，并将这些页面标记为"只读"。

  • 当父子进程都只是读取页面时，不会发生任何复制操作，它们共享同一物理页面。
  • 当其中任一进程尝试写入共享页面时，CPU触发页错误（写保护异常）。操作系统的缺页处理程序检测到这是COW场景，便为该进程分配一个新的物理页面，将原始页面的内容复制到新页面，然后更新该进程的页表指向新页面，并将新页面设置为可写。
  • 另一个进程仍然指向原始的物理页面（仍为只读）。

作用：

  • 节省内存： 避免不必要的内存复制，尤其当子进程紧接着调用exec()时，fork()时的大量复制工作被完全避免。
  • 提高效率： 加速了fork()系统调用的执行速度。
  • 在Linux、Unix等现代操作系统中被广泛采用。

第2题：工作集模型与颠簸（4分）

答：

工作集模型的概念：

  • 工作集是指在时间区间 (t - T, t] 内（即最近一段时间T内），进程所访问的所有页面的集合，记为 WS(t, T)。
  • 工作集的大小反映了进程在最近一段时间内的内存需求。
  • 工作集模型利用局部性原理：进程在一段时间内往往只访问相对固定的一部分页面。

防止颠簸的机制：

  • 颠簸（Thrashing）的根本原因是分配给进程的物理帧数小于其工作集大小，导致进程频繁产生缺页中断。
  • 操作系统通过以下方式利用工作集模型防止颠簸：
    1. 监测每个进程的缺页率。
    2. 估算每个进程的工作集大小。
    3. 确保分配给每个进程的物理帧数不少于其工作集大小。
    4. 当总的工作集大小之和超过可用物理内存时，通过挂起部分进程（中程调度/交换），将释放的物理帧分配给活跃进程，使它们的缺页率恢复正常水平。

第3题：管程（Monitor）与信号量（Semaphore）的比较（4分）

答：

相同点：

  • 两者都是用于解决进程/线程间的互斥与同步问题的机制。
  • 两者在表达能力上是等价的，即管程能解决的问题用信号量也能解决，反之亦然。

不同点：

比较维度 管程（Monitor） 信号量（Semaphore）
使用方式 高级语言结构，编译器自动管理互斥 低级的系统调用原语（P/V操作）
互斥实现 管程内部保证互斥，程序员无需显式编写互斥代码 程序员必须显式使用P/V操作保证互斥
错误风险 并发控制逻辑集中，易读易维护，出错概率低 分散在各处，容易遗漏P/V操作导致死锁或破坏互斥
封装性 将共享数据、操作和同步封装在一起，模块化好 数据与同步操作分离，封装性差
条件同步 使用条件变量（Condition Variable）的wait/signal 使用P操作阻塞、V操作唤醒
典型应用 Java synchronized + wait/notify Linux semaphore, pthread semaphore

总结： 管程是信号量的高级封装，更适合构建大型复杂的并发系统；信号量更灵活轻量，适合简单的互斥和同步场景。

第4题：三种文件物理分配方式的优缺点（4分）

答：

分配方式 优点 缺点
连续分配 1. 顺序访问速度快（磁头移动少）
2. 随机访问方便（直接计算块号）
3. 实现简单，管理开销小		 1. 产生外部碎片，需定期压缩
2. 文件大小必须在创建时确定，不利于动态增长
3. 删除或修改大小时不灵活
链接分配 1. 无外部碎片，空间利用率高
2. 文件可以动态增长
3. 文件创建时无需声明大小		 1. 随机访问慢（需遍历链表）
2. 链接指针占用存储空间
3. 一个指针损坏会影响后续数据读取
4. 不支持高效的直接访问
索引分配 1. 随机访问速度快（直接通过索引找到块）
2. 文件可动态增长
3. 无外部碎片
4. 支持大文件（通过多级索引）		 1. 索引块本身占用存储空间
2. 小文件时索引块开销相对较大
3. 索引块的管理（多级索引）增加复杂度

结论： 现代文件系统（如EXT4）采用混合策略：小文件使用直接索引，大文件使用区段树（Extent Tree），兼顾了小文件和大文件的性能需求。

第5题：四种磁盘调度算法的比较（4分）

答：

算法 工作方式 特点
SCAN（电梯算法） 磁头从一端向另一端移动，沿途响应请求；到达一端后改变方向。 无饥饿现象；平均寻道时间优于FCFS；两端请求等待时间较长。
C-SCAN（循环SCAN） 磁头单向移动（如从外到内），沿途响应请求；到达最内端后直接返回最外端，返回途中不处理请求。 等待时间更均匀，各磁道响应公平性更好；比SCAN多一次"空跑"距离。
LOOK 改进的SCAN：磁头移动到最远的请求处即掉头，不必移动到磁盘物理末端。 比SCAN效率更高；同样无饥饿。
C-LOOK 改进的C-SCAN：磁头移动到最远的请求处即返回起点，不必移动到磁盘物理末端，返回时不处理请求。 在四种算法中平均寻道时间通常最优；等待时间最均匀；效率高于C-SCAN。

总结： 实际系统中常使用C-LOOK或LOOK算法，兼具公平性和高效率。

四、计算与分析题 详细解答

第1题 银行家算法（10分）

（1）计算 Need 矩阵（2分）

Need = Max - Allocation

| 进程 | Need（尚需） |
|:----😐:—😐:—😐:—😐
| | A | B | C |
| P0 | 7 | 4 | 3 |
| P1 | 1 | 2 | 2 |
| P2 | 6 | 0 | 0 |
| P3 | 0 | 1 | 1 |
| P4 | 4 | 3 | 1 |

计算过程（以P0为例）：

  • Need[P0] = Max[P0] - Allocation[P0] = (7, 5, 3) - (0, 1, 0) = (7, 4, 3)

类似地计算其他进程：

  • Need[P1] = (3, 2, 2) - (2, 0, 0) = (1, 2, 2)
  • Need[P2] = (9, 0, 2) - (3, 0, 2) = (6, 0, 0)
  • Need[P3] = (2, 2, 2) - (2, 1, 1) = (0, 1, 1)
  • Need[P4] = (4, 3, 3) - (0, 0, 2) = (4, 3, 1)
（2）T0 时刻是否处于安全状态？（4分）

初始条件：

  • Available = (3, 3, 2)
  • Work = Available = (3, 3, 2)
  • Finish = [false, false, false, false, false]

安全性检查过程：

| 步骤 | 进程 | Work（可用资源） | Need | 条件判断 | Allocation | 进程释放后Work |
|:----😐:----😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐
| | | A | B | C | A | B | C | | A | B | C | A | B | C |
| 初始 | | 3 | 3 | 2 | | | | | | | | | | |
| 1 | P1 | 3 | 3 | 2 | 1 | 2 | 2 | 1≤3,2≤3,2≤2 ✓ | 2 | 0 | 0 | 5 | 3 | 2 |
| 2 | P3 | 5 | 3 | 2 | 0 | 1 | 1 | 0≤5,1≤3,1≤2 ✓ | 2 | 1 | 1 | 7 | 4 | 3 |
| 3 | P0 | 7 | 4 | 3 | 7 | 4 | 3 | 7≤7,4≤4,3≤3 ✓ | 0 | 1 | 0 | 7 | 5 | 3 |
| 4 | P2 | 7 | 5 | 3 | 6 | 0 | 0 | 6≤7,0≤5,0≤3 ✓ | 3 | 0 | 2 | 10 | 5 | 5 |
| 5 | P4 | 10 | 5 | 5 | 4 | 3 | 1 | 4≤10,3≤5,1≤5 ✓ | 0 | 0 | 2 | 10 | 5 | 7 |

详细判断过程：

步骤1： 尝试P1

  • Need[P1] = (1, 2, 2) ≤ Work = (3, 3, 2) → 满足条件
  • P1运行完毕后释放资源：Work = (3, 3, 2) + (2, 0, 0) = (5, 3, 2)
  • Finish[P1] = true

步骤2： 尝试P3

  • Need[P3] = (0, 1, 1) ≤ Work = (5, 3, 2) → 满足条件
  • P3运行完毕后释放资源：Work = (5, 3, 2) + (2, 1, 1) = (7, 4, 3)
  • Finish[P3] = true

步骤3： 尝试P0

  • Need[P0] = (7, 4, 3) ≤ Work = (7, 4, 3) → 满足条件
  • P0运行完毕后释放资源：Work = (7, 4, 3) + (0, 1, 0) = (7, 5, 3)
  • Finish[P0] = true

步骤4： 尝试P2

  • Need[P2] = (6, 0, 0) ≤ Work = (7, 5, 3) → 满足条件
  • P2运行完毕后释放资源：Work = (7, 5, 3) + (3, 0, 2) = (10, 5, 5)
  • Finish[P2] = true

步骤5： 尝试P4

  • Need[P4] = (4, 3, 1) ≤ Work = (10, 5, 5) → 满足条件
  • P4运行完毕后释放资源：Work = (10, 5, 5) + (0, 0, 2) = (10, 5, 7)
  • Finish[P4] = true

结果： 所有进程的Finish均为true，系统处于安全状态。
安全序列： <P1, P3, P0, P2, P4>

注：安全序列可能不唯一，如 <P3, P1, P0, P2, P4> 也是安全的（步骤1先选P3也可行）。

（3）P1请求资源 (1, 0, 2) 能否分配？（4分）

步骤1：检查请求是否 ≤ Need

  • Request1 = (1, 0, 2)
  • Need[P1] = (1, 2, 2)
  • 1 ≤ 1 ✓，0 ≤ 2 ✓，2 ≤ 2 ✓ → 满足条件

步骤2：检查请求是否 ≤ Available

  • Request1 = (1, 0, 2)
  • Available = (3, 3, 2)
  • 1 ≤ 3 ✓，0 ≤ 3 ✓，2 ≤ 2 ✓ → 满足条件

步骤3：试探性分配，更新系统状态

  • Available’ = Available - Request1 = (3, 3, 2) - (1, 0, 2) = (2, 3, 0)
  • Allocation’[P1] = Allocation[P1] + Request1 = (2, 0, 0) + (1, 0, 2) = (3, 0, 2)
  • Need’[P1] = Need[P1] - Request1 = (1, 2, 2) - (1, 0, 2) = (0, 2, 0)

更新后的系统状态：

| 进程 | Allocation’ | Max | Need’ |
|:----😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐
| | A | B | C | A | B | C | A | B | C |
| P0 | 0 | 1 | 0 | 7 | 5 | 3 | 7 | 4 | 3 |
| P1 | 3 | 0 | 2 | 3 | 2 | 2 | 0 | 2 | 0 |
| P2 | 3 | 0 | 2 | 9 | 0 | 2 | 6 | 0 | 0 |
| P3 | 2 | 1 | 1 | 2 | 2 | 2 | 0 | 1 | 1 |
| P4 | 0 | 0 | 2 | 4 | 3 | 3 | 4 | 3 | 1 |

Available’ = (2, 3, 0)

步骤4：检查新状态是否安全

Work = (2, 3, 0)，Finish = [false, false, false, false, false]

| 步骤 | 进程 | Work | Need’ | 条件判断 | Allocation’ | 释放后Work |
|:----😐:----😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐:—😐
| | | A | B | C | A | B | C | | A | B | C | A | B | C |
| 初始 | | 2 | 3 | 0 | | | | | | | | | | |
| 1 | P1 | 2 | 3 | 0 | 0 | 2 | 0 | 0≤2,2≤3,0≤0 ✓ | 3 | 0 | 2 | 5 | 3 | 2 |
| 2 | P3 | 5 | 3 | 2 | 0 | 1 | 1 | 0≤5,1≤3,1≤2 ✓ | 2 | 1 | 1 | 7 | 4 | 3 |
| 3 | P0 | 7 | 4 | 3 | 7 | 4 | 3 | 7≤7,4≤4,3≤3 ✓ | 0 | 1 | 0 | 7 | 5 | 3 |
| 4 | P2 | 7 | 5 | 3 | 6 | 0 | 0 | 6≤7,0≤5,0≤3 ✓ | 3 | 0 | 2 | 10 | 5 | 5 |
| 5 | P4 | 10 | 5 | 5 | 4 | 3 | 1 | 4≤10,3≤5,1≤5 ✓ | 0 | 0 | 2 | 10 | 5 | 7 |

详细判断过程：

步骤1： 尝试P1

  • Need’[P1] = (0, 2, 0) ≤ Work = (2, 3, 0) → 满足条件
  • 释放后：Work = (2, 3, 0) + (3, 0, 2) = (5, 3, 2)
  • Finish[P1] = true

步骤2： 尝试P3

  • Need’[P3] = (0, 1, 1) ≤ Work = (5, 3, 2) → 满足条件
  • 释放后：Work = (5, 3, 2) + (2, 1, 1) = (7, 4, 3)
  • Finish[P3] = true

步骤3： 尝试P0

  • Need’[P0] = (7, 4, 3) ≤ Work = (7, 4, 3) → 满足条件
  • 释放后：Work = (7, 4, 3) + (0, 1, 0) = (7, 5, 3)
  • Finish[P0] = true

步骤4： 尝试P2

  • Need’[P2] = (6, 0, 0) ≤ Work = (7, 5, 3) → 满足条件
  • 释放后：Work = (7, 5, 3) + (3, 0, 2) = (10, 5, 5)
  • Finish[P2] = true

步骤5： 尝试P4

  • Need’[P4] = (4, 3, 1) ≤ Work = (10, 5, 5) → 满足条件
  • 释放后：Work = (10, 5, 5) + (0, 0, 2) = (10, 5, 7)
  • Finish[P4] = true

结论： 分配后系统仍然处于安全状态。安全序列为 <P1, P3, P0, P2, P4>。因此，系统可以分配资源(1, 0, 2)给P1。

第2题 页面置换算法与多级页表地址转换（10分）

第一部分：页面置换算法（6分）

页面引用序列：3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4
物理块数 = 3，初始均为空。

（1）FIFO（先进先出）算法（2分）

FIFO置换最早进入内存的页面。

步骤 页面 帧0 帧1 帧2 缺页 说明
1 3 3 F 空闲，装入
2 2 3 2 F 空闲，装入
3 1 3 2 1 F 空闲，装满
4 0 0 2 1 F 置换3（最早进入）
5 3 0 3 1 F 置换2
6 2 0 3 2 F 置换1
7 4 4 3 2 F 置换0
8 3 4 3 2 命中
9 2 4 3 2 命中
10 1 4 1 2 F 置换3
11 0 4 1 0 F 置换2
12 4 4 1 0 命中

缺页次数：9次（步骤1, 2, 3, 4, 5, 6, 7, 10, 11）

缺页率：9/12 = 75%

（2）LRU（最近最久未使用）算法（2分）

LRU置换最近最久未被使用的页面。

步骤 页面 帧0 帧1 帧2 缺页 最近使用顺序（左→右：最近→最久） 说明
1 3 3 F [3] 空闲，装入
2 2 3 2 F [2, 3] 空闲，装入
3 1 3 2 1 F [1, 2, 3] 空闲，装满
4 0 0 2 1 F [0, 1, 2] 置换3（最久未使用）
5 3 0 3 1 F [3, 0, 1] 置换2
6 2 0 3 2 F [2, 3, 0] 置换1
7 4 4 3 2 F [4, 2, 3] 置换0
8 3 4 3 2 [3, 4, 2] 命中，3移到最近
9 2 4 3 2 [2, 3, 4] 命中，2移到最近
10 1 4 1 2 F [1, 2, 4] 置换3（最久未使用）
11 0 0 1 2 F [0, 1, 2] 置换4（最久未使用）
12 4 0 1 4 F [4, 0, 1] 置换2（最久未使用）

缺页次数：10次（步骤1, 2, 3, 4, 5, 6, 7, 10, 11, 12）

缺页率：10/12 ≈ 83.3%

（3）OPT / LFD（最佳置换）算法（2分）

OPT算法置换未来最远才会被访问的页面，或永不使用的页面。其置换过程如下：

步骤 页面 帧0 帧1 帧2 缺页 说明
1 3 3 F 空闲，装入
2 2 3 2 F 空闲，装入
3 1 3 2 1 F 空闲，装满
4 0 3 2 0 F 置换1：3未来用(5), 2(6), 1(10最远)
5 3 3 2 0 命中
6 2 3 2 0 命中
7 4 3 2 4 F 置换0：3(8), 2(9), 0(11最远)
8 3 3 2 4 命中
9 2 3 2 4 命中
10 1 1 2 4 F 置换3：3不再用, 2不再用, 4(12)
11 0 0 2 4 F 置换1：1不再用, 2不再用, 4(12). 选1
12 4 0 2 4 命中（4已在帧2中）

置换过程详细分析：

  • 步骤4（页面0）： 内存中有[3, 2, 1]。未来引用位置：3(步骤5)、2(步骤6)、1(步骤10→最远)。因此置换页面1，将页面0装入帧2。
  • 步骤7（页面4）： 内存中有[3, 2, 0]。未来引用位置：3(步骤8)、2(步骤9)、0(步骤11→最远)。因此置换页面0，将页面4装入帧2。
  • 步骤10（页面1）： 内存中有[3, 2, 4]。未来引用位置：3(不再使用)、2(不再使用)、4(步骤12)。因此选择3或2，置换页面3，将页面1装入帧0。
  • 步骤11（页面0）： 内存中有[1, 2, 4]。未来引用位置：1(不再使用)、2(不再使用)、4(步骤12)。4即将被使用，因此置换页面1或2，将页面0装入帧0。
  • 步骤12（页面4）： 页面4已在帧2中，命中。

缺页次数：7次（步骤1, 2, 3, 4, 7, 10, 11）

缺页率：7/12 ≈ 58.3%

三种算法对比：

算法 缺页次数 缺页率
FIFO 9 75%
LRU 10 83.3%
OPT 7 58.3%
第二部分：多级页表地址转换（4分）

（1）虚拟地址划分（2分）

虚拟地址 0x00303004，页面大小 4KB = 2^12 B，所以偏移量为12位。

第一步：将 0x00303004 转换为二进制
0x00303004 = 0000 0000 0011 0000 0011 0000 0000 0100 (32位)

第二步：划分虚拟地址

  • 页目录索引（bits 31-22，共10位）：0000 0000 00 = 0x000
  • 二级页表索引（bits 21-12，共10位）：11 0000 0011 = 0x303
  • 页内偏移量（bits 11-0，共12位）：0000 0000 0100 = 0x004

所以：

  • 页目录索引 = 0x000（= 0）
  • 二级页表索引 = 0x303（= 771）
  • 页内偏移量 = 0x004（= 4）

（2）物理地址计算（2分）

步骤1： 查找页目录（顶级页表）

  • 页目录物理帧号 = 0x1000
  • 页目录的物理基地址 = 0x1000 << 12 = 0x1000000
  • 使用索引 0x000 查找页目录：从物理地址 0x1000000 + 0x000 × 4 = 0x1000000 处读取页表项
  • 该页表项指向二级页表的物理帧号 = 0x2000

步骤2： 查找二级页表

  • 二级页表物理帧号 = 0x2000
  • 二级页表的物理基地址 = 0x2000 << 12 = 0x2000000
  • 使用索引 0x303 查找二级页表：从物理地址 0x2000000 + 0x303 × 4 = 0x2000000 + 0xC0C = 0x2000C0C 处读取页表项
  • 该页表项给出的物理帧号 = 0x3000

步骤3： 计算最终物理地址

  • 物理帧号 = 0x3000
  • 物理基地址 = 0x3000 << 12 = 0x3000000
  • 物理地址 = 物理基地址 + 页内偏移量 = 0x3000000 + 0x004 = 0x3000004

验证地址划分：

虚拟地址 0x00303004:
  二进制：0000 0000 0011 0000 0011 0000 0000 0100
          |--页目录--|--二级页表---|----偏移量----|
              00          303         004

因此：页目录索引=0，二级页表索引=0x303，页内偏移=0x004

五、综合题 详细解答（10分）

读者-写者问题（写者优先）

（1）信号量与共享变量定义（3分）

定义以下信号量和共享变量：

semaphore mutex_r = 1;       // 保护读者计数器 read_count 的互斥信号量
semaphore mutex_w = 1;       // 保护写者计数器 write_count 的互斥信号量
semaphore write_first = 1;   // 写者优先信号量，用于阻塞读者（当有写者在等待时）
semaphore rw_mutex = 1;      // 读写互斥信号量，控制对共享文件的访问

int read_count = 0;          // 当前正在读取的读者数量
int write_count = 0;         // 当前正在等待或正在写入的写者数量

各信号量的作用和初始值：

信号量 初始值 作用
mutex_r 1 保护对 read_count 变量的互斥访问
mutex_w 1 保护对 write_count 变量的互斥访问
write_first 1 实现写者优先：当有写者等待时，阻止新读者开始读取
rw_mutex 1 读写互斥：写者独占文件，读者之间可共享
（2）读者进程伪代码（3分）
void reader() {
    while (true) {
        // 读者进入区
        P(write_first);      // 检查是否有写者在等待，若有则阻塞
        
        P(mutex_r);          // 互斥访问 read_count
        read_count++;        // 读者数量+1
        if (read_count == 1) // 第一个读者
            P(rw_mutex);     // 锁定文件，阻止写者写入
        V(mutex_r);          // 释放 read_count 互斥
        
        V(write_first);      // 释放写者优先信号量，让其他读者可以进入
        
        // 临界区：读取共享文件
        读者读取文件...
        
        // 读者退出区
        P(mutex_r);          // 互斥访问 read_count
        read_count--;        // 读者数量-1
        if (read_count == 0) // 最后一个读者
            V(rw_mutex);     // 解锁文件，允许写者写入
        V(mutex_r);          // 释放 read_count 互斥
    }
}
（3）写者进程伪代码（3分）
void writer() {
    while (true) {
        // 写者进入区
        P(mutex_w);          // 互斥访问 write_count
        write_count++;       // 写者数量+1
        if (write_count == 1)// 第一个写者
            P(write_first);  // 阻止新读者进入（写者优先的关键）
        V(mutex_w);          // 释放 write_count 互斥
        
        P(rw_mutex);         // 请求文件独占访问（等待所有读者退出）
        
        // 临界区：写入共享文件
        写者写入文件...
        
        // 写者退出区
        V(rw_mutex);         // 释放文件访问权限
        
        P(mutex_w);          // 互斥访问 write_count
        write_count--;       // 写者数量-1
        if (write_count == 0)// 最后一个写者
            V(write_first);  // 允许读者进入
        V(mutex_w);          // 释放 write_count 互斥
    }
}
（4）死锁与饥饿分析（1分）

为什么不会发生死锁：

  • 信号量的P操作顺序是固定的，不存在循环等待。
  • 读者先P(write_first)再P(mutex_r)再P(rw_mutex)（只有第一个读者才需要rw_mutex）。
  • 写者先P(mutex_w)再P(write_first)再P(rw_mutex)。
  • 没有形成循环等待链，因此不会发生死锁。

饥饿可能性分析：

  • 该方案实现了写者优先策略：
    • 当有写者等待时（write_count > 0），新到达的读者会被 write_first 信号量阻塞。
    • 只有当所有写者都完成时（write_count == 0），write_first 才会被释放，阻塞的读者才能进入。
  • 读者可能存在饥饿：如果有源源不断的写者到达，读者可能长时间无法访问文件。在极端情况下，读者可能无限期被推迟。
  • 写者不会饥饿：读者在读的过程中，其他读者可以同时进入，但写者只需等待最后一个读者读完即可。且写者优先策略保证了新读者不会插在写者前面。

注：若要完全避免饥饿，可采用"公平"策略（如按到达顺序排队），但会降低并发度。实际系统可根据需求在公平性和性能之间权衡。

（完）

# 操作系统 # 文件系统
Logo
openEuler 社区

openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构

更多推荐

cover

有PLC还要上位机软件？让设备真正“好用起来”

avatar openEuler 社区
cover

Linux

avatar openEuler 社区

国产化全兼容，适配新时代政企数字化建设

ER护照阅读器全面适配麒麟、统信UOS等国产操作系统，同时兼容Windows、Linux、鸿蒙、安卓等全平台，适配政企办公电脑、内网终端、自助设备等各类硬件环境。随着信创改造全面落地，越来越多政务窗口、事业单位、国企、园区，对设备系统兼容性、安全性、适配性提出更高要求。很多传统证件设备仅支持老旧Windows系统，无法适配国产系统，导致项目改造停滞、设备无法入网、系统对接困难。高兼容、高安全、易集

avatar openEuler 社区