操作系统理论作业 5：调度、死锁与 I/O

1. 五个进程的调度

五个进程依次同时进入就绪队列，信息如下。优先级数越小，优先级越高。

进程	处理器时间	优先级
P1	10	3
P2	1	1
P3	2	3
P4	1	4
P5	5	2

忽略调度开销：

1. 写出先来先服务、短作业优先、非抢占式优先级和时间片轮转的执行次序。时间片为 2。
2. 分别计算各进程的周转时间、等待时间和平均周转时间。

查看我当时提交的答案

执行次序：

• 先来先服务：P1、P2、P3、P4、P5。
• 短作业优先：P2、P4、P3、P5、P1。
• 非抢占式优先级：P2、P5、P1、P3、P4。
• 时间片轮转：P1、P2、P3、P4、P5、P1、P3、P5、P1、P5、P1。

先来先服务：

进程	周转时间	等待时间
P1	10	0
P2	11	10
P3	13	11
P4	14	13
P5	19	14
平均	13.4	9.6

短作业优先：

进程	周转时间	等待时间
P2	1	0
P4	2	1
P3	4	2
P5	9	4
P1	19	9
平均	7	3.2

非抢占式优先级：

进程	完成时间	周转时间	等待时间
P2	1	1	0
P5	6	5	1
P1	16	10	6
P3	18	2	16
P4	19	1	18
平均		3.8	8.2

时间片轮转：

进程	完成时间	周转时间	等待时间
P1	20	10	10
P2	3	1	2
P3	7	2	5
P4	4	1	3
P5	15	5	10
平均		3.8	6

2. 时间片轮转的周转时间

某系统使用时间片轮转算法，时间片为 5 ms。系统共有 10 个进程，初始时都在就绪队列中，结束前只处于执行态或就绪态。队尾进程 P 所需的 CPU 时间最短，为 25 ms。不考虑系统开销，求 P 的周转时间。

查看我当时提交的答案

250 ms。

3. 动态优先级

调度程序总是选择优先数最小的进程。进程创建时由用户给出静态优先数 nice。为动态调整优先级，再引入 cpuTime 和 waitTime，初值均为 0：进程执行时 cpuTime 定时加 1 且 waitTime 置 0；进程就绪时 cpuTime 置 0 且 waitTime 定时加 1。

1. 若只取 priority = nice，为什么可能发生饥饿？
2. 使用三个量设计一种避免饥饿的动态优先数，并说明 waitTime 的作用。

查看我当时提交的答案

若只使用静态 nice，高优先级进程持续就绪时总会先被调度；低优先级进程的优先数不会随等待时间改善，因此可能无限期等待。

我当时提交的动态优先数为：

$$priority = nice + \beta \times cpuTime - \alpha \times waitTime$$

waitTime 用于避免饥饿。等待越久，优先数越小、优先级越高，使低优先级进程最终也能得到 CPU。进程一旦被调度，waitTime 归零，再从基础 nice 优先级开始。

4. 同类资源与死锁

1. 有 $m$ 个同类资源供 $n$ 个进程共享，每个进程最多申请 $k$ 个资源（$k\ge 1$）。采用银行家算法时，为保证不发生死锁，各进程的最大需求量之和应满足什么条件？说明理由。
2. 有 8 台打印机，由 $K$ 个进程竞争，每个进程最多使用 3 台。求使系统可能发生死锁的最小 $K$。
3. 某系统有 $n$ 台互斥使用的同类设备，三个并发进程分别需要 3、4、5 台。求保证不发生死锁的最小 $n$。

查看我当时提交的答案

条件为：

$$n k \le m+n-1$$

最坏情况下，每个进程都已获得 $k-1$ 个资源，并各自申请最后一个资源。此时已分配 $n(k-1)$ 个资源。为让至少一个进程取得最后一个资源并完成，需要：

$$m-n(k-1)\ge 1$$

整理即得上述条件。

第 2 问：最小 $K$ 为 4。

第 3 问：最小 $n$ 为 10。

5. 银行家算法

系统有 5 个进程和 A、B、C 三类资源，某时刻状态如下：

进程	Allocation A	B	C	Max A	B	C
P0	0	0	3	0	0	4
P1	1	0	0	1	7	5
P2	1	3	5	2	3	5
P3	0	0	2	0	6	4
P4	0	0	1	0	6	5

1. 当 Available = (1, 4, 0) 时，系统是否安全？
2. 若改为 Available = (0, 6, 2)，系统是否安全？若安全，给出安全序列；否则说明原因。

查看我当时提交的答案

1. 系统安全。
2. 系统安全，安全序列为 P0、P2、P1、P3、P4。

6. 磁盘调度

磁盘请求按柱面 10、35、20、70、2、3、38 的次序到达。磁头每移动一个柱面需要 5 ms，初始位置为柱面 15。对于 SCAN 和 C-SCAN，磁头初始向大柱面号方向运行，最大柱面号为 85。分别求以下算法的寻道时间：

1. 先来先服务。
2. 最短寻道时间优先。
3. SCAN。
4. C-SCAN，且始终从小柱面号向大柱面号扫描。

查看我当时提交的答案

• 先来先服务：995 ms。
• 最短寻道时间优先：405 ms。
• SCAN：775 ms。
• C-SCAN：1200 ms。

7. 单缓冲与双缓冲

在 I/O 系统中引入缓冲区的主要目标是什么？某文件占 8 个磁盘块，要把磁盘块逐个读入主存缓冲区，再送入用户区分析。缓冲区与磁盘块等大；读一块到缓冲区用时 100 μs，从缓冲区送入用户区用时 50 μs，CPU 分析一块用时 50 μs。分别计算单缓冲和双缓冲下处理完整个文件的时间。

查看我当时提交的答案

引入缓冲区的主要目标包括：

• 减少 CPU 等待，让 CPU 与 I/O 设备并行工作。
• 匹配生产者与消费者的速度差异，平滑数据流。
• 重叠 I/O 与计算，提高吞吐量。
• 支持异步操作，改善响应性。
• 累积数据，减少中断频率。

单缓冲需要 1250 μs，双缓冲需要 900 μs。