常考计算机操作系统面试习题（三上）

目录

1. 为何要引入与设备的无关性？如何实现设备的独立性？

2. 页面置换先进先出算法

3. 页面置换先进先出算法，4个页框

4. 进程优先级调度算法

5. 短作业优先调度策略

6. 平均内存访问时间计算

7. 页式存储和段式存储的物理地址计算

8. 进程调度下等待时间的计算

9. 银行家算法的安全性检查

10. 分页系统查询时间

11. 页结构的地址转换机制

12. 最近最少使用（LRU）页面置换算法

13. 银行家算法安全性检查

14. 银行家算法死锁检测

15. 用 P、V 操作实现并发同步

16. 短作业优先（SJF）和最高响应比优先（HRRN）调度算法

17. 页面置换算法缺页率计算

18. 爸爸、儿子、女儿取放水果的同步实现

19. 银行家算法：需求矩阵计算与资源分配安全性分析

1. 为何要引入与设备的无关性？如何实现设备的独立性？

参考答案：

引入设备无关性是为了简化操作系统的设计，使其能够支持多种硬件设备，增强操作系统的可扩展性与适应性。设备无关性使得应用程序不依赖于具体的硬件设备，从而提高了软件的通用性和移植性。在现代操作系统中，设备驱动程序通常与具体硬件紧密相关，而设备无关的软件层位于设备驱动程序之上。通过这一层，应用程序可以与硬件解耦，实现设备的独立性。

2. 页面置换先进先出算法

题目：

引用以下页面：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5，共有3个页框，确定每次引用装入哪个页框？

参考答案：

页面：  1  2  3  4  1  2  5  1  2  3  4  5
页框：  1  2  3  4  1  2  5  1  2  3  4  5

3. 页面置换先进先出算法，4个页框

题目：

引用串: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5，共有4个页框，分析会发生哪些次页面替换？

参考答案：

引用串: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
替换的页面为：5，1，3，4，5

4. 进程优先级调度算法

题目：

进程 P1, P2, P3, P4, P5 的优先级和运行时间如下： 使用非抢占式优先级调度算法，给出执行顺序和开始时间。

参考答案：

5. 短作业优先调度策略

题目：

三个作业的提交时间及运行时间如下表： 采用短作业优先调度策略，求开始时间、完成时间、周转时间，并计算平均周转时间。

参考答案：

平均周转时间 = (4 + 7 + 14) / 3 = 8.33

6. 平均内存访问时间计算

题目：

已知：

• 存取内存时间 = 200 纳秒

• 平均缺页处理时间 = 8 毫秒

• 每 1000 次访问中有 1 次页错误

求平均内存访问时间（EAT）。

参考答案：

EAT = (1 - p) × 200 + p × 8,000,000
p = 0.001
EAT = 0.999 × 200 + 0.001 × 8,000,000 = 200 + 7,999.8 = 8,200 纳秒

7. 页式存储和段式存储的物理地址计算

题目：

(1) 页式存储： 页号和页内地址计算，给定逻辑地址 8300，页表如下。

页表：

参考答案：

页号 P = 8300 / 1024 = 8
页内地址 d = 8300 % 1024 = 108
物理地址 = 4 × 1024 + 108 = 4204

8. 进程调度下等待时间的计算

题目：

进程集如下，计算 FCFS、SJF 和优先级调度下的等待时间：

参考答案：

9. 银行家算法的安全性检查

题目：

银行家算法中，已知 5 个进程 P0 到 P4 和 3 类资源 (A: 10 实例，B: 5 实例，C: 7 实例)，在时刻 Tn 的快照如下：

参考答案：

(1) 判断系统是否处于安全状态： 系统是安全的，安全序列为：<P1, P3, P4, P0, P2>。

(2) 检查 Request1 = (1, 0, 2) 是否可以满足： Request1 ≤ Available (3, 3, 2)，因此可以满足。执行后，系统依然处于安全状态，安全序列为：<P1, P3, P4, P0, P2>。

10. 分页系统查询时间

题目：

a. 如果内存的查询需要 200 毫秒，那么一个分页内存的查询需要多长时间？
b. 如果加上 TLB（相关联寄存器），75% 的页表查询可以在 TLB 中找到，那么有效查询时间是多少？

参考答案：

a. 分页查询时间：
分页内存查询需要两次内存访问：一次访问页表，另一次访问数据。
分页查询时间 = 200 + 200 = 400 毫秒。

b. 有效查询时间：
有效查询时间 = 0.75 × 200 + 0.25 × 400 = 250 毫秒。

11. 页结构的地址转换机制

题目：

描述逻辑地址转换为物理地址的过程。

参考答案：

逻辑地址由 p1、p2 和 d 构成：

1. 通过 p1 在外页表中检索页 p2；

2. 通过 p2 在页表中检索页框基址 base；

3. 通过 d 得到页内偏移量； 最终物理地址 = base + d。

12. 最近最少使用（LRU）页面置换算法

题目：

页面引用串：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5，分配 4 个页框，计算缺页次数。

参考答案：

页框变化如下：

缺页次数：8 次。

13. 银行家算法安全性检查

题目：

五个进程 P0 到 P4，三个资源类型 A（7 个实例），B（2 个实例），C（6 个实例），时刻 Tn 的状态如下：

P1 请求资源 Request1 = (1, 0, 2)，是否可以满足？给出详细过程。

参考答案：

Request1 = (1, 0, 2) ≤ Available = (3, 3, 2)，可以满足。

调整后的状态： Available = (2, 3, 0)

安全序列为：P1 → P3 → P4 → P0 → P2，故请求可以满足。

14. 银行家算法死锁检测

题目：

五个进程 P0 到 P4，三个资源类型 A（7 个实例），B（2 个实例），C（6 个实例），时刻 Tn 的状态如下：

Available = (0, 0, 0)。检测是否发生死锁，并给出详细过程。

参考答案：

P0 和 P2 不需要资源，完成后释放资源，Available = (3, 1, 3)。
接着，P3 可完成，释放资源后 Available = (5, 2, 4)。
随后，P1 可完成，释放资源后 Available = (7, 2, 6)。
最后，P4 可完成，释放资源后所有进程完成。
结论：无死锁。

15. 用 P、V 操作实现并发同步

题目：

有三个进程：爸爸（Dad），儿子（Son），女儿（Daughter），使用 P、V 操作实现同步。

参考答案：

semaphore Empty = 5, Orange = 0, Apple = 0, Mutex = 1;

Dad() {
    while (1) {
        P(Empty);            // 等待有空位
        P(Mutex);            // 获取操作盘子的互斥锁
        将水果放入盘中；     // 放入苹果或桔子
        V(Mutex);            // 释放锁
        if (放入的是桔子) {
            V(Orange);        // 增加桔子的计数
        } else {
            V(Apple);         // 增加苹果的计数
        }
    }
}

Son() {
    while (1) {
        P(Orange);           // 等待桔子
        P(Mutex);            // 获取操作盘子的互斥锁
        从盘中取出一个桔子； // 取出桔子
        V(Mutex);            // 释放锁
        V(Empty);            // 增加空位计数
        享用桔子；
    }
}

Daughter() {
    while (1) {
        P(Apple);            // 等待苹果
        P(Mutex);            // 获取操作盘子的互斥锁
        从盘中取出一个苹果； // 取出苹果
        V(Mutex);            // 释放锁
        V(Empty);            // 增加空位计数
        享用苹果；
    }
}

16. 短作业优先（SJF）和最高响应比优先（HRRN）调度算法

题目：

四个作业的到达时间和运行时间如下表：

参考答案：

(a) SJF 调度顺序： 调度顺序：J1 → J4 → J2 → J3
平均周转时间 = (2 + 1.6 + 5 + 7.5) / 4 = 4.025

(b) HRRN 调度顺序： 调度顺序：J1 → J2 → J4 → J3
平均周转时间 = (2 + 4 + 4.1 + 7.5) / 4 = 4.4

17. 页面置换算法缺页率计算

题目：

页面走向：4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5。
块数分别为 3 和 4，采用以下算法计算缺页率：
a. FIFO（先进先出）
b. LRU（最近最久使用）

参考答案：

(a) FIFO 算法：

• 块数为 3，缺页次数：9，缺页率 = 9/12 = 75%

• 块数为 4，缺页次数：10，缺页率 = 10/12 = 83.3%

(b) LRU 算法：

• 块数为 3，缺页次数：10，缺页率 = 10/12 = 83.3%

• 块数为 4，缺页次数：8，缺页率 = 8/12 = 66.7%

现象：
FIFO 算法可能会出现 Belady 异常，即增加内存块数后，缺页次数反而增加。

18. 爸爸、儿子、女儿取放水果的同步实现

题目：

桌上有一个能盛得下五个水果的空盘。爸爸不停地向盘中放苹果或桔子，儿子不停地从盘中取出桔子享用，女儿不停地从盘中取出苹果享用。规定三人不能同时从盘中取放水果。试用 P、V 原语实现爸爸、儿子、女儿三个并发进程的同步。

参考答案：

semaphore Empty = 5, Orange = 0, Apple = 0, Mutex = 1;

Dad() {
    while (1) {
        P(Empty);            // 等待有空位
        P(Mutex);            // 获取操作盘子的互斥锁
        将水果放入盘中；     // 放入苹果或桔子
        V(Mutex);            // 释放锁
        if (放入的是桔子) {
            V(Orange);        // 增加桔子的计数
        } else {
            V(Apple);         // 增加苹果的计数
        }
    }
}

Son() {
    while (1) {
        P(Orange);           // 等待桔子
        P(Mutex);            // 获取操作盘子的互斥锁
        从盘中取出一个桔子； // 取出桔子
        V(Mutex);            // 释放锁
        V(Empty);            // 增加空位计数
        享用桔子；
    }
}

Daughter() {
    while (1) {
        P(Apple);            // 等待苹果
        P(Mutex);            // 获取操作盘子的互斥锁
        从盘中取出一个苹果； // 取出苹果
        V(Mutex);            // 释放锁
        V(Empty);            // 增加空位计数
        享用苹果；
    }
}

19. 银行家算法：需求矩阵计算与资源分配安全性分析

题目：

假定系统中有四种类型资源（A、B、C、D）和五个进程 P1、P2、P3、P4、P5。T0 时刻系统资源分配情况如下：

参考答案：

(1) 计算需求矩阵（Need）：

进程    Need
P1      1 2 2 1
P2      1 2 2 2
P3      2 3 5 6
P4      0 6 5 2
P5      4 4 2 2

(2) 判断是否为安全状态：

• 系统处于安全状态，安全序列为：P1 → P3 → P4 → P0 → P2

(3) P3 请求资源 Request3 = (1, 1, 1, 1)，是否能实施分配：

• Request3 ≤ Need3 和 Request3 ≤ Available，都满足条件。

• 分配后，系统状态仍然安全，安全序列为：P1 → P3 → P4 → P0 → P2

(4) P4 请求资源 Request4 = (1, 2, 1, 2)，是否能实施分配：

• Request4 > Need4，故不能满足请求。