2016年408真题操作系统篇

选择题

---

23. 下列关于批处理系统的叙述中，正确的是（ ）。

选项：

Ⅰ. 批处理系统允许多个用户与计算机直接交互 Ⅱ. 批处理系统分为单道批处理系统和多道批处理系统 Ⅲ. 中断技术使得多道批处理系统的 I/O 设备可与 CPU 并行工作

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

---

✅正确答案：A（仅Ⅱ、Ⅲ）

✅解释：

• Ⅰ 错误： 批处理系统不允许用户与计算机直接交互，用户将作业打包提交后，系统自动依次执行。这种方式不具有交互性，不同于分时系统。

• Ⅱ 正确： 批处理系统确实分为单道批处理系统（一次只运行一个作业）和多道批处理系统（同时加载多个作业，提高资源利用率）。

• Ⅲ 正确： 多道批处理系统中引入中断机制，使得I/O 和 CPU 可以并行工作。例如，一个作业在执行 I/O 操作时，CPU 可以切换去执行另一个作业，提高系统效率。

---

24. 某单CPU系统中有输入和输出设备各1台，现有3个并发执行的作业，每个作业的输入、计算和输出时间均分别为2ms、3ms和4ms，且都按输入、计算和输出的顺序执行，则执行完3个作业需要的时间最少是（ ）。

选项：

A. 15ms B. 17ms C. 22ms D. 27ms

---

✅正确答案：B（17ms）

对于这种题，画个图可以很快解决问题！！

---

25. 系统中有3个不同的临界资源 R1、R2 和 R3，被4个进程 p1、p2、p3 和 p4 共享。各进程对资源的需求为：

• p1申请 R1 和 R2
• p2申请 R2 和 R3
• p3申请 R1 和 R3
• p4申请 R2

若系统出现死锁，则处于死锁状态的进程数至少是（ ）。

选项：

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

---

✅正确答案：C（3）

✅解释：

• 死锁的必要条件包括互斥、占有并等待、不可抢占、循环等待。
• 若系统出现死锁，说明系统中存在资源请求的环。
• 分析进程对资源的请求可以建立资源分配图（简化为请求边），由于每个资源只有1个实例，每个进程最多请求2个资源，可以构造出3个进程构成的循环等待（比如：p1等p2，p2等p3，p3等p1）。

✅结论：

最少有 3个进程 会进入死锁状态。

---

26. 改进型 CLOCK 置换算法中，页表项包含访问位 A 和修改位 M。A=0 表示页最近未被访问，M=0 表示页未被修改。按 (A, M) 可能取值将页分为四类：

• (0, 0)
• (1, 0)
• (0, 1)
• (1, 1)

该算法淘汰页的优先顺序为（ ）。

选项：

A. (0, 0), (0, 1), (1, 0), (1, 1) B. (0, 0), (1, 0), (0, 1), (1, 1) C. (0, 0), (0, 1), (1, 1), (1, 0) D. (0, 0), (1, 1), (0, 1), (1, 0)

---

✅正确答案：A

✅解释：

改进型 CLOCK 算法（又称 NRU – Not Recently Used）根据 访问位（A） 和 修改位（M） 的组合来选择被淘汰的页，原则是优先淘汰最近未被访问且未被修改的页，这样既不影响命中率，也不增加写回磁盘的代价。

优先级从高到低（最先淘汰 → 最后淘汰）如下：

1. (0, 0)：未访问、未修改 → 最理想的淘汰目标
2. (0, 1)：未访问、已修改 → 要写回磁盘，但没被访问过
3. (1, 0)：已访问、未修改
4. (1, 1)：已访问、已修改 → 最不适合淘汰

该顺序即：

(0, 0) → (0, 1) → (1, 0) → (1, 1)

---

27. 使用 TSL（Test and Set Lock）指令实现进程互斥的伪代码如下：

do {
    ...
    while (TSL(&lock));
    critical section;
    lock = FALSE;
    ...
} while (TRUE);

下列与该实现机制相关的叙述中，正确的是（ ）。

选项：

A. 退出临界区的进程负责唤醒阻塞态进程 B. 等待进入临界区的进程不会主动放弃CPU C. 上述伪代码满足“让权等待”的同步准则 D. while (TSL(&lock)) 应在关中断状态下执行

---

✅正确答案：B

✅解释：

TSL（Test and Set Lock）指令是原子操作（不可中断），常用于实现自旋锁，即通过不断测试并设置一个标志（锁变量）来实现进程互斥。

• TSL(&lock) 的作用是：
  • 返回原先的锁值
  • 并将 lock 设置为 TRUE（表示加锁）

逐项分析：

• A ❌ 错误： 使用 TSL 的机制是“忙等待”（busy waiting），进程不会阻塞，而是不断轮询锁变量；所以没有“唤醒”阻塞态进程这一说法。
• B ✅ 正确： 在 while (TSL(&lock)) 中，进程在不停循环测试锁，因此它不会进入阻塞状态，也不会主动让出 CPU。是主动占用 CPU的轮询行为。
• C ❌ 错误： “让权等待”是指当进程无法进入临界区时，主动让出 CPU，进入阻塞态等待调度。而 TSL 采用的是自旋（busy-waiting）方式，不满足这一准则。
• D ❌ 错误： 在现代系统中，TSL 是一种硬件原语，不需要在关中断的状态下执行。关中断会影响整个系统调度，不适用于多核系统。

---

✅结论：本题选 B

---

28. 某进程的段表内容如下：

段号	段长	内存起始地址	权限	状态
0	100	6000	只读	在内存
1	200	——	读写	不在内存
2	300	4000	读写	在内存

当访问 段号为 2，段内地址为 400 的逻辑地址时，进行地址转换的结果是（ ）。

---

选项：

A. 段缺失异常 B. 得到内存地址 4400 C. 越权异常 D. 越界异常

---

✅正确答案：D

✅解释：

访问逻辑地址的处理过程如下：

• 逻辑地址形式：<段号，段内地址> 题中访问：段号 = 2，段内地址 = 400

1. 查看段 2：
   • 段长：300，→ 合法段内地址应为 0 ~ 299
   • 段内地址为 400，超过段长
2. 所以，这是越界访问（segment limit violation）。

---

其他选项分析：

• A ❌ 段缺失异常： 段 2 状态为“在内存”，不属于段缺失。
• B ❌ 得到地址 4400： 如果段内地址合法，4400=4000+400，但这里地址越界。
• C ❌ 越权异常： 该段为“读写”权限，题目也未涉及非法权限访问。

---

✅结论：本题选 D

---

---

29. 某进程访问页面的序列如下所示：

（假设访问序列为：1,3,4,5,6,0,3,2,3,2,(t)0,4,0,3,9,2,1，在时刻 t 访问完这些页面）

若工作集的窗口大小为 6，则在 t 时刻的工作集为（ ）。

---

选项：

A. {6, 0, 3, 2} B. {2, 3, 0, 4} C. {0, 4, 3, 2, 9} D. {4, 5, 6, 0, 3, 2}

---

✅正确答案：A

✅解释：

• 工作集定义（Working Set）：

  • 在操作系统中，工作集是指进程在某一时刻 t 前、长度为 Δ 的时间窗口内实际访问过的页面的集合。
  • 它用于衡量进程当前运行所“活跃使用”的页面集合。

• 题设窗口大小为 6，表示我们需要查看时刻 t 向前数的6次页面访问记录，假设这6次访问顺序为：

  访问序列：6, 0, 3, 2, 3, 2（共6次）

• 去重并保留首次出现顺序，得到工作集为：

  W = {6, 0, 3, 2}

---

❌ 其他选项分析：

• B：{2, 3, 0, 4} → 页面 4 没在这 6 次访问中出现
• C：{0, 4, 3, 2, 9} → 包含了不在最近6次访问中的页面（4 和 9）
• D：{4, 5, 6, 0, 3, 2} → 也是包含无关页面 4 和 5

---

✅结论：本题选 A

---

30. 进程 P1 和 P2 各包含并发线程，部分伪代码如下：

img

下列选项中，需要互斥执行的操作是（ ）。

---

选项：

A. a = 1 与 a = 2 B. a = x 与 b = x C. x += 1 与 x += 2 D. x += 1 与 x += 3

---

✅正确答案：C

✅解释：

• 局部变量（local variable）：只在当前线程内有效，不需要互斥
• 全局变量（global/shared variable）：多个线程或进程共享，需要互斥访问

---

分析各项：

• A ❌ 错误： a = 1 和 a = 2 中的 a 是两个不同线程的局部变量，互不干扰，无需互斥。
• B ❌ 错误： a = x 与 b = x 的 a 和 b 是局部变量，x 是共享变量，但只是读取，不存在冲突修改，也不需要互斥。
• C ✅ 正确： x += 1 和 x += 2 都是对同一共享变量 x（P1 的全局变量）进行修改，而且在线程 Thread1 和 Thread2 中并发执行。 若不互斥，可能出现竞态条件（race condition）。需要互斥。
• D ❌ 错误： x += 1 与 x += 3 分别属于不同进程（P1 和 P2），各自的 x 是各自的私有变量，不共享，无需互斥。

---

✅结论：本题选 C

---

31. 下列关于 SPOOLing 技术的叙述中，错误的是（ ）。

---

选项：

A. 需要外存的支持 B. 需要多道程序设计技术的支持 C. 可以让多个作业共享一台独占设备 D. 由用户作业控制设备与输入/输出井之间的数据传送

---

✅正确答案：D

---

✅解释：

• SPOOLing（Simultaneous Peripheral Operation On-Line）技术： 是一种通过“假脱机”机制，让系统更高效地使用低速设备（如打印机）的输入输出技术。

各项分析：

• A ✅ 正确： SPOOLing 需要外存支持（如磁盘），用作输入井/输出井，暂存数据。
• B ✅ 正确： SPOOLing 建立在多道程序设计技术的基础上，依靠多个程序并发执行才能提高效率。
• C ✅ 正确： SPOOLing 允许多个作业共享独占设备，如多个用户共享一台打印机。
• D ❌ 错误： 错误在于“由用户作业控制数据传送”。实际上，设备与输入/输出井之间的数据传送是由操作系统负责控制的，并不是用户程序直接控制的。

---

✅结论：本题选 D

---

32. 下列关于“管程（Monitor）”的叙述中，错误的是（ ）。

---

选项：

A. 管程只能用于实现进程的互斥 B. 管程是由编程语言支持的进程同步机制 C. 任何时候只能有一个进程在管程中执行 D. 管程中定义的变量只能被管程内的过程访问

---

✅正确答案：A

---

✅解释：

• 管程（Monitor）是一种高级的进程同步机制，用于协调对共享资源的访问。

各项分析：

• A ❌ 错误： 错误在于“只能”，管程不仅实现互斥，还能用于进程之间的同步，如利用条件变量（condition variable）实现等待与唤醒等机制。
• B ✅ 正确： 管程依赖于编程语言的语法和语义支持，是语言级的同步机制。
• C ✅ 正确： 管程通过互斥进入机制，同一时刻只允许一个进程在管程中执行，确保共享资源的安全访问。
• D ✅ 正确： 管程中定义的变量是私有的（private），只能被管程内的过程访问，保障封装性和一致性。

---

✅结论：本题选 A

---

优先级调度

---

46.（6分）

某进程调度程序采用基于优先数（priority）的调度策略，即选择优先数最小的进程运行。进程创建时由用户指定一个 nice 值作为静态优先数。

为实现动态调整优先数，引入两个变量：

• cpuTime: 表示该进程处于运行态的累计时间（初值为0，运行时定时 +1，等待时重置为0）
• waitTime: 表示该进程处于就绪态的累计时间（初值为0，就绪时定时 +1，运行时重置为0）

---

问题（1）

若调度程序只将 nice 的值作为进程的优先数，即 priority = nice，则可能会出现**饥饿（starvation）**现象，为什么？

---

✅答案（1）：

因为 nice 值是一个静态优先数，在调度过程中不会随着时间动态变化。如果就绪队列中某个进程的 nice 值较大（优先级较低），而有其他新来的进程的 nice 值一直比它小（优先级更高），那么这个进程将始终无法被调度执行，从而导致 饥饿现象。

---

问题（2）

使用 nice、cpuTime 和 waitTime 设计一种动态优先数计算方法，以避免饥饿现象，并说明 waitTime 的作用。

---

✅答案（2）：

为避免饥饿现象，可以采用如下 动态优先数计算公式：

\[ \text{priority} = \text{nice} + k_1 \cdot \text{cpuTime} - k_2 \cdot \text{waitTime} \]

其中：

• k₁ 和 k₂ 是大于 0 的常数，用于调节影响权重。
• cpuTime 越大 → priority 越大（优先级降低）→ 避免长时间独占 CPU 的进程继续运行。
• waitTime 越大 → priority 越小（优先级升高）→ 提升长时间等待的进程，防止饥饿。

✅waitTime 的作用：

waitTime 表示进程在就绪队列中等待的时间，它反映了进程等待资源的“耐心”程度。通过将 waitTime 作为负权项纳入优先级计算，可以逐渐提升长时间未被调度的进程的优先级，从而防止其因优先级长期过低而饿死（无法获得 CPU）。

---

磁盘文件系统（链接分配、FAT）

---

题目：

某磁盘文件系统使用链接分配方式组织文件，簇大小为4KB。目录文件的每个目录项包含文件名和该文件的第一个簇号。其余簇号存放在**文件分配表（FAT）**中，每个FAT表项占2个字节，表示“当前簇的下一个簇号”。

已知目录树如下（略图），文件对应簇如下表：

文件名	簇号
dir	1
dir1	48
file1	100 → 106 → 108
file2	200 → 201 → 202

---

问题 (1)

请给出所有目录文件（即 dir 和 dir1）中的内容。

---

✅答案 (1)：

• dir 目录文件的簇号为 1，其内容为：

  • <dir1, 48>（表示 dir1 是子目录，起始簇号为48）

• dir1 目录文件的簇号为 48，其内容为：

  • <file1, 100>
  • <file2, 200>

---

问题 (2)

FAT的每个表项仅占2字节：

1. FAT的最大长度是多少字节？
2. 该文件系统支持的最大文件长度是多少？

---

✅答案 (2)：

1. 每个簇号占2字节，共有 \(2^{16}\) 个簇，则 FAT 最长为：

   \[ 2^{16} \times 2B = 131072B = \boxed{128\text{KB}} \]

2. 每个簇大小为4KB，最大支持 \(2^{16}\) 个簇，最大文件长度为：

   \[ 2^{16} \times 4\text{KB} = 256 \text{MB} \]

   ✅ 答案为：最大支持 的文件。

---

问题 (3)

file1 的106和108两个簇号分别存放在 FAT 的哪个表项中？

---

✅答案 (3)：

• file1 是链式分配，簇号为：100 → 106 → 108

• 所以：

  • 106 是 file1 的第二个簇号，存放在 FAT 的 100号表项中
  • 108 是 file1 的第三个簇号，存放在 FAT 的 106号表项中

✅ 答案：106 存放在 FAT[100]；108 存放在 FAT[106]

---

问题 (4)

仅 FAT 和 dir 目录文件在内存中，若要读入文件 dir/dir1/file1 的第5000个字节，需访问哪几个簇？

---

✅答案 (4)：

1. 簇大小为 4KB = 4096B

   • 第5000个字节属于第 \(\lceil \frac{5000}{4096} \rceil = 2\) 个簇

2. 获取 file1 的第2个簇：

   • 根据 dir 中 <dir1, 48> → 访问簇 48（dir1 的目录文件）
   • 查得 <file1, 100> → file1 起始簇为 100
   • 根据 FAT[100] = 106 → 第2个簇是 106

✅ 所需访问簇：

• 48号簇（dir1 目录文件）
• 106号簇（file1 的第2个簇）

---

总结关键点 ✅：

知识点	内容说明
链接分配方式	文件数据不连续存储，靠 FAT 链接下一个簇
目录项内容	文件名 + 第一个簇号
FAT表项内容	当前簇的“下一个簇号”
最大文件长度计算	最大簇数 × 每簇大小
按名访问流程	目录查找 → 得到首簇号 → FAT 追踪链