目录
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 的优先级和运行时间如下： 使用非抢占式优先级调度算法，给出执行顺序和开始时间。
| 进程 | 执行时间 | 优先级 |
|---|---|---|
| P1 | 6 | 3 |
| P2 | 1 | 1 |
| P3 | 10 | 4 |
| P4 | 2 | 2 |
| P5 | 3 | 2 |
参考答案：
| 进程 | 开始时间 | 顺序号 |
|---|---|---|
| P2 | 0 | 1 |
| P4 | 1 | 2 |
| P1 | 3 | 3 |
| P3 | 9 | 4 |
| P5 | 19 | 5 |
5. 短作业优先调度策略
题目：
三个作业的提交时间及运行时间如下表： 采用短作业优先调度策略，求开始时间、完成时间、周转时间，并计算平均周转时间。
| 作业 | 提交时间 | 运行时间 |
|---|---|---|
| J1 | 0 | 4 |
| J2 | 2 | 5 |
| J3 | 3 | 8 |
参考答案：
| 作业 | 开始时间 | 完成时间 | 周转时间 |
|---|---|---|---|
| J1 | 0 | 4 | 4 |
| J2 | 4 | 9 | 7 |
| J3 | 9 | 17 | 14 |
平均周转时间 = (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，页表如下。
页表：
| 页号 | 块号 |
|---|---|
| 0 | 5 |
| 1 | 7 |
| 2 | 1 |
| 3 | 3 |
| 4 | 4 |
参考答案：
页号 P = 8300 / 1024 = 8
页内地址 d = 8300 % 1024 = 108
物理地址 = 4 × 1024 + 108 = 4204
8. 进程调度下等待时间的计算
题目：
进程集如下，计算 FCFS、SJF 和优先级调度下的等待时间：
| 进程 | 执行时间 | 优先级 |
|---|---|---|
| P1 | 2 | 2 |
| P2 | 1 | 1 |
| P3 | 8 | 4 |
| P4 | 4 | 2 |
| P5 | 5 | 3 |
参考答案：
| 调度算法 | P3 等待时间 | P4 等待时间 |
|---|---|---|
| FCFS | 3 | 6 |
| SJF | 0 | 5 |
| 优先级调度 | 6 | 3 |
9. 银行家算法的安全性检查
题目：
银行家算法中，已知 5 个进程 P0 到 P4 和 3 类资源 (A: 10 实例，B: 5 实例，C: 7 实例)，在时刻 Tn 的快照如下：
| 进程 | Allocation | Max | Available |
|---|---|---|---|
| P0 | 0 1 0 | 7 5 3 | 3 3 2 |
| 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 |
参考答案：
(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 构成：
-
通过 p1 在外页表中检索页 p2；
-
通过 p2 在页表中检索页框基址 base；
-
通过 d 得到页内偏移量； 最终物理地址 = base + d。
12. 最近最少使用（LRU）页面置换算法
题目：
页面引用串：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5，分配 4 个页框，计算缺页次数。
参考答案：
页框变化如下：
| 页面 | 页框状态 |
|---|---|
| 1 | 1 |
| 2 | 1, 2 |
| 3 | 1, 2, 3 |
| 4 | 1, 2, 3, 4 |
| 1 | 1, 2, 3, 4 |
| 2 | 1, 2, 3, 4 |
| 5 | 5, 2, 3, 4 |
| 1 | 1, 5, 3, 4 |
| 2 | 1, 2, 3, 4 |
| 3 | 1, 2, 3, 4 |
| 4 | 1, 2, 3, 4 |
| 5 | 5, 2, 3, 4 |
缺页次数：8 次。
13. 银行家算法安全性检查
题目：
五个进程 P0 到 P4，三个资源类型 A（7 个实例），B（2 个实例），C（6 个实例），时刻 Tn 的状态如下：
| 进程 | Allocation | Max | Available |
|---|---|---|---|
| P0 | 0 1 0 | 7 5 3 | 3 3 2 |
| 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 |
P1 请求资源 Request1 = (1, 0, 2)，是否可以满足？给出详细过程。
参考答案：
Request1 = (1, 0, 2) ≤ Available = (3, 3, 2)，可以满足。
调整后的状态： Available = (2, 3, 0)
| 进程 | Allocation | Need |
|---|---|---|
| P0 | 0 1 0 | 7 4 3 |
| P1 | 3 0 2 | 0 2 0 |
| P2 | 3 0 2 | 6 0 0 |
| P3 | 2 1 1 | 0 1 1 |
| P4 | 0 0 2 | 4 3 1 |
安全序列为：P1 → P3 → P4 → P0 → P2，故请求可以满足。
14. 银行家算法死锁检测
题目：
五个进程 P0 到 P4，三个资源类型 A（7 个实例），B（2 个实例），C（6 个实例），时刻 Tn 的状态如下：
| 进程 | Allocation | Request |
|---|---|---|
| P0 | 0 1 0 | 0 0 0 |
| P1 | 2 0 0 | 2 0 2 |
| P2 | 3 0 2 | 0 0 0 |
| P3 | 2 1 1 | 1 0 0 |
| P4 | 0 0 2 | 2 0 2 |
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）调度算法
题目：
四个作业的到达时间和运行时间如下表：
| 作业 | 到达时间 | 运行时间 |
|---|---|---|
| J1 | 8.0 | 2.0 |
| J2 | 8.5 | 4.0 |
| J3 | 9.0 | 7.5 |
| J4 | 9.4 | 1.6 |
参考答案：
(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 时刻系统资源分配情况如下：
| 进程 | Allocation | Max | Available |
|---|---|---|---|
| P1 | 0 1 0 1 | 1 3 2 2 | 1 7 3 3 |
| P2 | 2 0 0 0 | 3 2 2 2 | |
| P3 | 3 0 2 1 | 5 3 7 7 | |
| P4 | 1 2 2 1 | 1 8 7 3 | |
| P5 | 0 0 2 2 | 4 4 4 4 |
参考答案：
(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，故不能满足请求。
