🏷️ 知识点：处理机调度算法
下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（ ）。
A. 先来先服务
B. 高响应比优先
C. 时间片轮转
D. 非抢占式短任务优先
[tag_link]
正确答案：B 最高响应比优先 是一种综合考虑任务长度和等待时间的调度算法，响应比＝（等待时间＋执行时间）／执行时间。高响应比优先算法在等待时间相同的情况下，作业执行时间越短则响应比越高，满足短任务优先。随着长任务的等待时间增加，响应比也会变大，执行机会也就增大，所以不会发生饥饿现象。先来先服务和时间片轮转不符合短任务优先，非抢占式短任务优先会产生饥饿现象。
下列调度算法中，不可能导致饥饿现象的是()。
A. 时间片轮转
B. 静态优先数调度
C. 非抢占式短作业优先
D. 抢占式短作业优先
[tag_link]
正确答案：A
采用 静态优先级调度 时，当系统总是出现优先级高的任务时，优先级低的任务会总是得不到处理机而产生饥饿现象；短任务优先调度不管是抢占式或是非抢占的，当系统总是出现新来的短任务时，长任务会总是得不到处理机，产生饥饿现象，因此 B、C、D 都错误，选 A。
假设 4 个作业到达系统的时刻和运行时间如下表所示。
| 作业 | 达到时刻 t | 运行时间 |
|---|---|---|
| J1 | 0 | 3 |
| J2 | 1 | 3 |
| J3 | 1 | 2 |
| J4 | 3 | 1 |
系统在 t=2 时开始作业调度。若分别采用先来先服务和短作业优先调度算法，则选中的作业分别是（ ）。
A. J2、J3 B. J1、J4 C. J2、J4 D. J1、J3
[tag_link]
正确答案：D
先来先服务 是作业来得越早，优先级越高，因此会选择J1。 最短作业优先 是作业运行时间越短，优先级越高，因此会选择J3。所以 D 正确。
某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系统时间开销为 1us。在 T 时刻就绪队列中有 3 个进程 P1、P2 和 P3，其在就绪队列中的等待时间、需要的 CPU 时间和优先权如下表所示。若优先权值大的进程优先获得 CPU，从 T 时刻起系统开始进程调度，则系统的平均周转时间为（）。
| 进程 | 等待时间 | 需要的 CPU 时间 | 优先级 |
|---|---|---|---|
| P1 | 30us | 12us | 10 |
| P2 | 15us | 24us | 30 |
| P3 | 18us | 36us | 20 |
A. 54us B. 73us C. 74us D. 75us
[tag_link]
正确答案：D
本题考察 非抢占式优先级调度，由优先权可知，进程的执行顺序为 P2 → P3 → P1。P2 的周转时间：1 +15+24= 40μs P3 的周转时间：18+1+24+1 +36= 80μs P1 的周转时间：30+1+24 +1 +36+1 +12=105μs平均周转时间： (40+80+105) /3= 225/3= 75μs, 故选 D。
下列内核的数据结构或程序中，分时系统实现时间片轮转调度需要使用的是（ ）。
I. 进程控制块
II. 时钟中断处理程序
III. 进程就绪队列
IV. 进程阻塞队列
A. 仅 II、III B. 仅 I、IV C. 仅 I、II、III D. 仅 I、II、IV
[tag_link]
正确答案：C
在分时系统的 时间片轮转 中，当系统检测到时钟中断时，会引出时钟中断处理程序调度程序从就绪队列中选择一个进程为其分配时间片，并修改该进程的进程控制块中的进程状态等信息，同时将时间片用完的进程放入就绪队列或让其结束运行。I、II、Ⅲ 正确。阻塞队列中的进程只有被唤醒进入就绪队列后，才能参与调度，所以该调度过程不使用阻塞队列。
进程P0 、P1 、P2 和 P3 进入就绪队列的时刻、优先级(值越小优先权越高)及CPU 执行时间如下表 所示。
| 进程 | 进入就绪队列的时刻 | 优先级 | CPU 执行时间 |
|---|---|---|---|
| P0 | 0ms | 15 | 100ms |
| P1 | 10 ms | 20 | 60ms |
| P2 | 10 ms | 10 | 20ms |
| P3 | 15 ms | 6 | 10ms |
若系统采用基于优先权的抢占式进程调度算法，则从0ms 时刻开始调度，到4个进程都运行结束为止，发 生进程调度的总次数为()。
A.4
B.5
C.6
D.7
[tag_link]
正确答案：C
本题考察 优先级调度 ： 0 时刻调度进程 P0 获得 CPU；1Oms 时 P2 进入就绪队列，调度 P2 抢占获得 CPU；15ms 时 P3 进入就绪队列，调度 P3 抢占获得 CPU；25ms 时 P3 执行完毕，调度 P2 获得 CPU；40ms 时 P2 执行完毕，调度 P0 获得 CPU；130ms 时 P2 执行完毕，调度 P1 获得 CPU；190ms 时 P2 执行完毕，结束；总共调度 6 次。
在优先权调度中，采用单链表保存进程就绪队列，高优先级进程在队头。若就绪队列长度为 n，则插入进程、选出进程的时间复杂度为（ ）。
A.
[tag_link]
正确答案：C
在 优先级调度 中，如果我们采用单链表来保存进程就绪队列，并且高优先级进程在队头，那么：
- 插入进程时，需要根据优先级找到合适的位置插入，因此时间复杂度为 O(n)。
- 选出进程（即从队头选出最高优先级的进程）是一个 O(1) 的操作，因为高优先级的进程总是在队头。
下列选项中，降低进程优先级的合理时机是()。
A. 进程时间片用完 B. 进程刚完成I/O 操作，进入就绪队列 C. 进程长期处于就绪队列 D. 进程从就绪状态转为运行状态
[tag_link]
正确答案：A
进程时间片用完，可降低其优先级以让别的进程被调度进入执行状态。
B 选项中进程刚完成 I/O，进入就绪队列等待被处理机调度，为了让其尽快处理 I/O 结果，故应提高优先权。
C 选项中进程长期处于就绪队列，为不至于产生饥饿现象，也应适当提高优先级。
D 选项中进程的优先级不应该在此时降低，而应在时间片用完后再降低。
下列与进程调度有关的因素中，在设计多级反馈队列调度算法时需要考虑的是（ ）。
Ⅰ. 就绪队列的数量
Ⅱ. 就绪队列的优先级
Ⅲ. 各就绪队列的调度算法
Ⅳ. 进程在就绪队列间的迁移条件
A. 仅Ⅰ、Ⅱ B. 仅Ⅲ、Ⅳ C. 仅Ⅱ、Ⅲ、Ⅳ D. Ⅰ、Ⅱ、Ⅲ和Ⅳ
[tag_link]
正确答案：D
多级反馈队列 调度算法需要综合考虑优先级数量、优先级之间的转换规则等，就绪队列的 数量会影响长进程的最终完成时间，I 正确；就绪队列的优先级会影响进程执行的顺序，II 正确；各就绪队列的调度算法会影响各队列中进程的调度顺序，m 正确；进程在就绪队列 中的迁移条件会影响各进程在各队列中的执行时间，IV 正确。
下列有关基于时间片的进程调度的叙述中，错误的是（ ）。
A. 时间片越短，进程切换的次数越多，系统开销也越大 B. 当前进程的时间片用完后，该进程状态由执行态变为阻塞态 C. 时钟中断发生后，系统会修改当前进程在时间片内的剩余时间 D. 影响时间片大小的主要因素包括响应时间、系统开销和进程数量等
[tag_link]
正确答案：B
进程切换带来系统开销，切换次数越多，开销越大，A 正确。当前进程的时间片用完后，它的状态由执行态变为就绪态，B 错误。时钟中断是系统中特定的周期性时钟节拍。操作系统通过它来确定时间间隔，实现时间的延时和任务的超时，C 正确。现代操作系统为了保证性能最优，通常根据响应时间、系统开销、进程数量、进程运行时间、进程切换开销等因素确定 时间片大小，D 正确。
系统采用二级反馈队列调度算法进行进程调度。就绪队列 Q1 采用时间片轮转调度算法，时间片为 10ms；就绪队列 Q2 采用短进程优先调度算法；系统优先调度 Q1 队列中的进程，当 Q1 为空时系统才会调度 Q2 中的进程；新创建的进程首先进入 Q1;Q1 中的进程执行一个时间片后，若未结束，则转入 Q2。若当前 Q1，Q2 为空，系统依次创建进程 P1，P2 后即开始进程调度，P1,P2 需要的 CPU 时间分别为 30ms 和 20ms，则进程 P1，P2 在系统中的平均等待时间为（ ）。
A. 25ms B. 20ms C. 15ms D. 10ms
[tag_link]
正确答案：C
参考 多级反馈队列 。进程 P1、P2 依次创建后进入队列 Q1，根据时间片调度算法的规则，进程 P1、P2 将依次被分配 10ms 的 CPU 时间，两个进程分别执行完一个时间片后都会被转入队列 Q2，就绪队列 Q2 采用短进程优先调度算法，此时 P1 还需要 20ms 的 CPU 时间，P2 还需要 10ms 的 CPU 时间，所以 P2 会被优先调度执行，10ms 后进程 P2 执行完成，之后 P1 再调度执行，再过 20ms 后 P1 也执行完成。平均等待时间 = (P1 等待时间 + P2 等待时间) / 2 = (20 + 10) / 2 = 15。
一个多道批处理系统中仅有P1和P2两个作业，P2比P1晚 5ms 到达，它们的计算和 I/O 操作顺序如下：
P1：计算 60ms，I/O 80ms，计算 20ms
P2：计算 120ms，I/O 40ms，计算 40ms
若不考虑调度和切换时间，则完成两个作业需要的时间最少是（ ）。
A. 240ms
B. 260ms
C. 340ms
D. 360ms
[tag_link]
正确答案：B
由于P2比P1晚 5ms 到达，P1先占用 CPU, 作业运行的甘特图如下所示。
进程 P1、P2 和 P3 进入就绪队列的的时刻，优先值（越大优先权越高）以及 CPU 的执行时间如下表所示。
| 进程名 | 进入就绪队列的时刻 | 优先级 | CPU 执行时间 |
|---|---|---|---|
| P1 | 0 ms | 1 | 60 ms |
| P2 | 20 ms | 10 | 42 ms |
| P3 | 30 ms | 100 | 13 ms |
系统采用基于优先权的抢占式 CPU 调度算法，从 0ms 时刻开始进行调度，则 P1、P2 和 P3 的平均周转时间为（ ）。
A. 60 ms B. 61 ms C. 70 ms D. 71 ms
[tag_link]
正确答案：B
具体的调度表如下图所示。周转时间 = 完成时间 - 到达时间，进程 1 的周转时间为115ms-0ms=115ms，进程 2 的周转时间为 75ms-20ms=55ms，进程 3 的周转时间为 43ms-30ms=13ms。平均周转时间为 (115+55+13)/3=61ms。所以该题的答案为 B 选项。
假设磁头当前位于第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
[tag_link]
正确答案：A
SCAN 算法类似电梯的工作原理。首先，当磁头从 105 道向序号增加的方向移动时，便会按照从小到大的顺序服务 所有大于 105 的磁道号 (110,170,180,195)；往回移动时又会按照从大到小的顺序进行服务 (68, 45,35, 12)。
假设某系统使用时间片轮转调度算法进行 CPU 调度，时间片大小为 5 ms，系统共有 10 个进程，初始时均处于就绪队列，执行结束前仅处于执行态或就绪态。若队尾的进程 P 所需 CPU 时间最短，时间为 25 ms。在不考虑系统开销的情况下，则进程 P 的周转时间为（ ）。
A. 200ms B. 205ms C. 250ms D. 295ms
[tag_link]
正确答案：C
由于使用的是轮转调度算法，进程即在每次执行一个时间片后，都需要重新回到就绪队列的末尾等待下一次的时间片。所以，实际上，进程 P 的每一个时间片之间都有一个完整的轮转周期的等待时间：10×5ms=50ms，进程 P 需要执行 25/5 个时间片，所有中间有 4 个完整的轮转周期再加上 P 的周转时间为，总共需要 5 个轮转周期：5×50ms=250s。
[tag_link]
某进程调度程序采用基于优先数 (priority) 的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个 nice 作为静态优先数。为了动态调整优先数，引入运行时间 cpuTime 和等待时间 waitTime，初值均为 0。进程处于执行态时，cpuTime 定时加 1，且 waitTime 置 0；进程处于就绪态时，cpuTime 置 0，waitTime 定时加 1。请回答下列问题。
(1) 若调度程序只将 nice 的值作为进程的优先数，即 priority=nice，则可能会出现饥饿现象，为什么？
(2) 使用 nice、cpuTime 和 waitTime 设计一种动态优先数计算方法，以避免产生饥饿现象，并说明 waitTime 的作用。
1）由于采用了静态优先数，当就绪队列中总有优先数较小的进程时，优先数较大的进程一直没有机会运行，因而会出现饥饿现象。（2 分）
2）优先数 priority 的计算公式为 priority = nice + k1 × cpuTime - k2 × waitTime，其中 k1 > 0，k2 > 0，用来分别调整 cpuTime 和 waitTime 在 priority 中所占的比例。（3 分）waitTime 可使长时间等待的进程优先数减少，从而避免出现饥饿现象。（1 分）【评分说明】①公式中包含 nice 给 1 分，利用 cpuTime 增大优先数给 1 分，利用 waitTime 减少优先数给 1 分；部分正确，酌情给分。②若考生给出包含 nice、cpuTime 和 waitTime 的其他合理的优先数计算方法，同样给分。