2009年408真题操作系统篇

选择题

问题23： 单处理机系统中，可并行的是（）。

Ⅰ. 进程与进程 Ⅱ. 处理机与设备 Ⅲ. 处理机与通道 Ⅳ. 设备与设备

A. Ⅰ、Ⅱ和Ⅲ B. Ⅰ、Ⅱ和Ⅳ C. Ⅰ、Ⅲ和Ⅳ D. Ⅱ、Ⅲ和Ⅳ

正确答案： D

解释： 在单处理机系统中，处理器一次只能执行一个进程，所以 进程与进程不能并行（Ⅰ错误）。但处理机与设备（Ⅱ）、处理机与通道（Ⅲ）、设备与设备之间（Ⅳ）是彼此独立的，可以并行工作。

因此，正确答案是 D. Ⅱ、Ⅲ和Ⅳ。

问题24： 下列进程调度算法中，综合考虑进程等待时间和执行时间的是（）。

A. 时间片轮转调度算法 B. 短进程优先调度算法 C. 先来先服务调度算法 D. 高响应比优先调度算法

正确答案： D

解释：

A. 时间片轮转：按时间片轮换，不考虑等待时间和服务时间，仅关注公平性和响应性。
B. 短进程优先：只看执行时间短，不考虑等待时间。
C. 先来先服务：按到达顺序执行，仅考虑到达时间，忽略服务时间与等待时间。
D. 高响应比优先（HRRN）：响应比 = (等待时间 + 服务时间) / 服务时间综合考虑了进程的等待时间和执行时间（服务时间），是一种兼顾效率与公平性的策略。

因此，正确答案是 D. 高响应比优先调度算法。

问题25：

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

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

正确答案： C

解释： 这是一个典型的死锁判断问题，可使用死锁必要条件和安全性分析来判断。

假设每个进程最多需要 3 台打印机。为了最容易发生死锁的情况，我们设每个进程已经分配了 2 台，还差 1 台才能满足需求。如果系统中有 K 个进程，则总共已经分配了 2K 台打印机。

为了能让这些进程陷入互相等待的状态（即死锁），需要让系统中剩余的打印机数量不足以再满足任何一个进程的剩余需求（1台）。所以我们希望满足：

1	2K + 1 > 8 → 2K > 7 → K ≥ 4

所以，当 K = 4 时，系统有可能发生死锁，这是最小值。

某计算机系统中有 9 台打印机，由 3 个进程 P1、P2 和 P3 竞争使用，若：

P1 需要 3 台
P2 需要 4 台
P3 需要 5 台

是否可能发生死锁？

答案：是。

解释： 最多需求之和是 3+4+5 = 12 台，但实际仅有 9 台。如果每个进程已分配 2、3、4 台（总共 9 台），且都在等待各自的剩余需求（1台），就可能形成环形等待，从而发生死锁。

问题26：

分区分配内存管理方式的主要保护措施是（）。

A. 界地址保护 B. 程序代码保护 C. 数据保护 D. 栈保护

正确答案： A

解释： 界地址保护（Bounds Address Protection） 是在分区式内存管理中最常用的保护手段，它通过设置每个进程允许访问的上限地址和下限地址来确保进程不能访问不属于自己的内存区域。

当进程试图访问超出自己分配区域的地址时，系统会检测到越界访问并中断进程，从而保护系统的稳定性与其他进程的安全。

问题27：

一个分段存储管理系统中，地址长度为 32 位，其中段号占 8 位，则最大段长是（）。

A. 2⁸ B B. 2¹⁶ B C. 2²⁴ B D. 2³² B

正确答案： C

解释： 在分段存储系统中，一个逻辑地址由两部分组成：

段号（Segment Number）
段内地址（Offset）

题中给出总地址长度是 32位，其中段号占 8位，因此段内地址占：

1	32 - 8 = 24 位

段内地址用来表示段中某个字节的偏移量，因此段的最大长度为：

1	2²⁴ 字节 = 16MB

因此，最大段长是 2²⁴ B。

✅ 答案选 C

问题28：

下列文件物理结构中，适合随机访问且易于文件扩展的是（）。

A. 连续结构 B. 索引结构 C. 链式结构且磁盘块定长 D. 链式结构且磁盘块变长

正确答案： B

解释：

连续结构（A）：
- 类似于数组，适合随机访问（可以直接通过偏移地址定位）。
- 但文件扩展不方便，因为需要连续空间，文件大小变更时容易发生碎片或重写。 ❌ 不利于扩展。
索引结构（B）：
- 类似于索引表或 B+树，提供地址映射。
- 可快速定位任意块 → 支持随机访问。
- 新增数据时，只需更新索引表，结构支持扩展。 ✅ 兼具随机访问和扩展性。
链式结构（C 和 D）：
- 类似链表，适合顺序访问，不适合随机访问。
- 定长和变长块对“扩展性”有影响，但都不擅长随机访问。 ❌ 排除 C 和 D。

✅ 答案选 B

SCAN 调度算法（电梯调度）
CSCAN 调度算法（循环电梯调度）

✅ 第1题：SCAN 调度算法

题目： 假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为： 35, 45, 12, 68, 110, 180, 170, 195，采用 SCAN 调度（电梯调度）算法 得到的磁道访问序列是（）。

选项： A. 110, 170, 180, 195, 68, 45, 35, 12 B. 110, 68, 45, 35, 12, 170, 180, 195 C. 110, 170, 180, 195, 12, 35, 45, 68 D. 12, 35, 45, 68, 110, 170, 180, 195

参考答案： ✅ A

解释：

当前磁头位置是 105，方向为向上（磁道号增大方向）。
所以先访问大于等于 105 的请求：110, 170, 180, 195
到达最大磁道号请求后，磁头掉头，开始向下处理剩下的请求（小于105）：68, 45, 35, 12

最终访问顺序： 110 → 170 → 180 → 195 → 68 → 45 → 35 → 12

✅ 第2题：CSCAN 调度算法

题目： 假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为： 35, 45, 12, 68, 110, 180, 170, 195，采用 CSCAN 调度（循环电梯调度）算法 得到的磁道访问序列是（）。

选项： A. 110, 170, 180, 195, 68, 45, 35, 12 B. 110, 68, 45, 35, 12, 170, 180, 195 C. 110, 170, 180, 195, 12, 35, 45, 68 D. 12, 35, 45, 68, 110, 170, 180, 195

参考答案： ✅ C

解释：

当前磁头位置是 105，方向为向上（磁道号增大方向）。
CSCAN 先处理所有比105大的请求：110, 170, 180, 195
然后回到最小磁道（如0），继续向上处理剩下的小请求：12, 35, 45, 68

最终访问顺序： 110 → 170 → 180 → 195 → 12 → 35 → 45 → 68

当然可以，以下是你要求的两道题的整理版本，包含问题、选项、答案和详细解释，适合用于笔记或复习。

✅ 第30题：文件访问控制信息存储位置

题目： 文件系统中，文件访问控制信息存储的合理位置是（）。

选项： A. 文件控制块 B. 文件分配表 C. 用户口令表 D. 系统注册表

正确答案： ✅ A. 文件控制块

解释：

文件控制块（File Control Block, FCB） 是操作系统中用于描述文件的内部数据结构。它包含了文件的元数据和控制信息。
其中包括：文件名、文件类型、大小、创建时间、修改时间、文件位置（指向磁盘块）、访问权限、所有者信息、访问控制列表（ACL） 等。
操作系统在访问文件前，会读取 FCB 中的权限信息来决定是否允许当前用户进行读/写/执行等操作。

其他选项说明：

B. 文件分配表：主要记录磁盘块的分配情况，如 FAT 表，不存储权限。
C. 用户口令表：存储的是用户登录凭证，与文件权限无关。
D. 系统注册表：特指 Windows 系统设置，不属于文件系统权限控制范畴。

✅ 第31题：软链接与硬链接的引用计数

题目： 设文件 F1 的当前引用计数为 1，先建立 F1 的符号链接（软链接）文件 F2，再建立 F1 的硬链接文件 F3，然后删除 F1。此时，F2 和 F3 的引用计数值分别是（）。

选项： A. 0、1 B. 1、1 C. 1、2 D. 2、1

正确答案： ✅ B. 1、1

解释： 过程如下：

初始状态： F1 的引用计数为 1（即它自己占用 1 个硬链接）。
建立软链接 F2：
- F2 是一个独立的文件，拥有自己的 inode，指向 F1 的路径。
- 它不增加 F1 的引用计数。
- F2 的引用计数为 1。
建立硬链接 F3：
- F3 是另一个名字，指向与 F1 相同的 inode。
- 增加原 inode 的引用计数：此时 inode 引用计数为 2（F1 和 F3）。
删除 F1：
- 删除名字 F1，inode 引用计数减 1，变为 1（F3 仍存在）。
- F3 依然指向原文件数据。
- F2 仍然是一个指向 F1 的路径，但目标文件已被删除，F2 成为悬挂链接（dangling link）。

因此最终状态：

F2 是软链接，引用计数仍为 1（它本身作为文件）。
F3 是硬链接，引用计数为 1（还指向原 inode）。

✅ 举一反三题：软链接、硬链接与引用计数

题目： 设文件 F1 的当前引用计数值为 1，先建立 F1 的符号链接（软链接）文件 F2 和 F3，再建立 F1 的硬链接文件 F4，然后删除 F2。此时，F3 和 F4 的引用计数值分别是（）。

选项： A. 0、1 B. 1、1 C. 1、2 D. 2、1

正确答案： ✅ C. 1、2

解释：

初始状态：F1 的引用计数为 1。
建立软链接 F2、F3：
- 软链接是独立的文件，它们各有自己的 inode，指向 F1 的路径。
- 不影响 F1 的引用计数。F2、F3 各自的引用计数是 1。
建立硬链接 F4：
- F4 是硬链接，直接指向与 F1 相同的 inode，引用计数 +1，变成 2。
删除 F2（软链接）：
- F2 被删除，它自身的引用计数变为 0，被释放，不会影响 F1 的引用计数。

最终结果：

F3（软链接） 是一个独立文件，引用计数仍为 1。
F4（硬链接） 与 F1 共享 inode，F1 和 F4 的引用计数为 2（因为 F1 还在）。

✅ 拓展知识：引用计数与内存管理

引用计数不仅用于文件系统，也广泛用于内存管理（如垃圾回收）。

引用计数法：每个对象维护一个计数器，记录被引用的次数。
- 引用 +1：有变量引用它；
- 引用 -1：变量不再引用它；
- 计数为 0：对象无用，可以回收。

对比类比：

强引用：像硬链接，会增加引用计数。
弱引用：像软链接，不增加引用计数，对象可以被 GC（垃圾收集）回收。

✅ 第32题：设备标识的使用

题目： 程序员利用系统调用打开 I/O 设备时，通常使用的设备标识是（）。

选项： A. 逻辑设备 B. 物理设备 C. 主设备号 D. 从设备号

正确答案： ✅ A. 逻辑设备

解释：

逻辑设备 是对实际设备的抽象，提供更友好的接口。
程序员在使用系统调用（如 open()）时，通常通过逻辑设备名（如 /dev/ttyS0、LPT1）打开设备。
操作系统根据逻辑设备名找到对应的物理设备或驱动程序。

其他选项说明：

物理设备：硬件实体，程序员通常不直接接触。
主设备号 / 从设备号：由内核使用的编号，标识设备类型与具体设备，对程序员不可见。

示例：

在 Linux 中，/dev/sda1 是逻辑设备名，程序员通过它访问硬盘分区，而不需要关心底层设备号。

PV问题

✅ 第45题

题目（7分）：

三个进程 P1、P2、P3 互斥使用一个包含 N（N > 0）个单元的缓冲区。

P1 每次用 produce() 生成一个正整数，并用 put() 放入缓冲区某一空单元；
P2 每次用 getodd() 从缓冲区中取出一个奇数，并用 countodd() 统计奇数数量；
P3 每次用 geteven() 从缓冲区中取出一个偶数，并用 counteven() 统计偶数数量。

要求： 请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义（要求用伪代码描述）。

✅ 参考答案（伪代码 + 信号量解释）

🧠 思路分析：

本题是 生产者-消费者问题的变形：

P1 是生产者，P2 和 P3 是“分类消费者”。
P2 只消费奇数，P3 只消费偶数。
缓冲区总容量有限，需要互斥访问。
对应使用信号量机制解决同步与互斥问题。

✅ 定义信号量及其含义：

semaphore mutex = 1;     // 互斥访问缓冲区的信号量
semaphore empty = N;     // 表示缓冲区空闲单元数
semaphore odd = 0;       // 缓冲区中奇数的数量
semaphore even = 0;      // 缓冲区中偶数的数量

✅ 伪代码实现：

cobegin

// 生产者进程 P1
Process P1() {
    while (1) {
        x = produce();          // 生成一个正整数
        P(empty);               // 等待空闲单元
        P(mutex);               // 互斥访问缓冲区
        put(x);                 // 将 x 放入缓冲区
        V(mutex);               // 释放互斥
        if (x % 2 == 0) {
            V(even);            // 是偶数，唤醒等待偶数的进程
        } else {
            V(odd);             // 是奇数，唤醒等待奇数的进程
        }
    }
}

// 消费奇数的进程 P2
Process P2() {
    while (1) {
        P(odd);                 // 等待奇数可用
        P(mutex);               // 互斥访问缓冲区
        getodd();               // 从缓冲区中取出奇数
        V(mutex);               // 释放互斥
        V(empty);               // 空闲单元数加一
        countodd();             // 统计奇数数量
    }
}

// 消费偶数的进程 P3
Process P3() {
    while (1) {
        P(even);                // 等待偶数可用
        P(mutex);               // 互斥访问缓冲区
        geteven();              // 从缓冲区中取出偶数
        V(mutex);               // 释放互斥
        V(empty);               // 空闲单元数加一
        counteven();            // 统计偶数数量
    }
}

coend

✅ 总结：

mutex：保证三个进程互斥访问共享缓冲区。
empty：确保缓冲区未满时才能插入新数据。
odd / even：分类控制奇数、偶数的消费，避免类型混用或错误提取。

这种写法是经典生产者-消费者模型的分类扩展版本，合理拆分 full 信号量为 odd 和 even，实现了多消费者分类消费的同步控制。

PV问题

✅ 题目（自行车装配同步问题）

设自行车生产线上有一个传送带，其中有 N（N ≥ 3）个位置，每个位置可存放一个车架或者一个车轮。设有 3 名工人：

进程 P1 表示工人 1，每次加工一个车架并放入传送带；
进程 P2 表示工人 2，每次加工一个车轮并放入传送带；
进程 P3 表示工人 3，每次从传送带上取出一个车架和两个车轮并组装成一辆自行车。

要求：用信号量机制实现三个进程的同步与互斥活动，并说明所定义的信号量的含义，伪代码描述即可。

✅ 参考答案与伪代码实现

🧠 思路分析：

这是一个多生产者 + 合成消费者的变形生产者-消费者模型：

P1 和 P2 是不同类型的生产者（车架、车轮）；
P3 是复合型消费者，需要1 个车架 + 2 个车轮才能消费一次；
传送带作为共享缓冲区，需要互斥控制访问；
同时还要控制车架/车轮数量的平衡和空间的分配。

✅ 定义信号量及其含义：

semaphore mutex = 1;           // 互斥访问传送带
semaphore empty = N;           // 传送带空位数量
semaphore wheel = 0;           // 传送带中车轮的数量
semaphore frame = 0;           // 传送带中车架的数量
semaphore wheel_empty = N-1;   // 允许放车轮的“逻辑空位”数量
semaphore frame_empty = N-2;   // 允许放车架的“逻辑空位”数量

mutex: 保证多个进程互斥访问缓冲区。
empty: 控制实际物理缓冲区空位。
wheel: 记录可用车轮数（初始为 0）。
frame: 记录可用车架数（初始为 0）。
wheel_empty: 避免过多车轮堵满缓冲区。
frame_empty: 避免过多车架堵满缓冲区。

✅ 伪代码：

cobegin

Process P1() { // 工人1：车架生产者
    while (1) {
        加工一个车架;
        P(frame_empty);   // 保证车架数量不会溢出
        P(empty);         // 占用一个传送带空位
        P(mutex);
        将车架放入传送带;
        V(mutex);
        V(frame);         // 增加一个可用车架数
    }
}

Process P2() { // 工人2：车轮生产者
    while (1) {
        加工一个车轮;
        P(wheel_empty);   // 保证车轮数量不会溢出
        P(empty);         // 占用一个传送带空位
        P(mutex);
        将车轮放入传送带;
        V(mutex);
        V(wheel);         // 增加一个可用车轮数
    }
}

Process P3() { // 工人3：消费者，组装一辆车
    while (1) {
        P(frame);         // 等待有车架
        P(mutex);
        从传送带取出一个车架;
        V(mutex);
        V(empty);         // 空位+1
        V(frame_empty);   // 释放可放车架的名额

        P(wheel); P(wheel); // 等待两个车轮
        P(mutex);
        从传送带取出两个车轮;
        V(mutex);
        V(empty); V(empty); // 空位+2
        V(wheel_empty); V(wheel_empty); // 释放可放车轮的名额

        组装为一辆车;
    }
}

coend

✅ 总结：

本题的关键在于：消费者一次消耗多个资源（1 车架 + 2 车轮），因此要设置不同的资源计数器。
同时通过 wheel_empty 和 frame_empty 控制同类资源不要塞满缓冲区，避免死锁。
empty 控制总容量，mutex 控制互斥访问。

✅ 请求分页管理系统

在请求分页管理系统中，某进程的页表内容如下表所示：

页号	页框号	有效位
0	101H	1
1	0	0
2	254H	1

页面大小为 4KB (即 2122^{12} 字节)，一次内存的访问时间为 100ns，一次快表（TLB）的访问时间为 10ns，处理一次缺页的平均时间为 10810^8 ns（已包含更新 TLB 和页表的时间）。进程的驻留集大小固定为 2，采用最近最少使用置换算法（LRU）和局部淘汰策略。

设定：

TLB 初始为空；
地址转换时，先访问 TLB，若 TLB 未命中，再访问页表（忽略访问页表之后的 TLB 更新时间）；
有效位为 0 表示页面不在内存中，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。

虚拟地址访问序列：2362H、1565H、25A5H

✅ 解答：

(1) 依次访问虚拟地址 2362H、1565H 和 25A5H 各需多少时间？

第一步：访问虚拟地址 2362H

虚拟地址 2362H 的虚拟页号为 2，页内地址为 362H。
TLB 初始为空，第一次访问 TLB 时未命中。
访问页表，查找页号 2：
- 页号 2 对应的页框号为 254H，有效位为 1，页表命中。
- 拼接页框号 254H 和页内地址 362H，得到物理地址：254362H。
更新 TLB，TLB 中保存页号 2 和对应的页框号 254H。
访问内存，读取数据的时间：100ns。

所需时间：

TLB 访问：10ns
页表访问：100ns
访问内存：100ns
总时间：10ns + 100ns + 100ns = 210ns

第二步：访问虚拟地址 1565H

虚拟地址 1565H 的虚拟页号为 1，页内地址为 565H。
访问 TLB，未命中，TLB 中没有页号 1。
访问页表，查找页号 1：
- 页号 1 的有效位为 0，发生缺页中断，缺页处理中需要淘汰一个页面。
- 根据 LRU 算法，淘汰最近访问的页面（2号页面），保留 2 号页面，淘汰 0 号页面。
- 更新页表：页号 1 的有效位为 1，页框号为 101H。
更新 TLB，页号 1 对应页框号 101H。
访问内存，读取数据的时间：100ns。
处理缺页中断的时间：10810^8ns。

所需时间：