Tips：此为⬛⬛⬛⬛⬛⬛大学⬛⬛⬛⬛⬛⬛⬛学院2019级《操作系统原理》课程中的部分课程作业题目解析和展示
6.2，6.3，6.6，6.9，6.10，6.13，6.16，6.17，6.19，6.21，6.23，6.28
6.2 解释抢占式和非抢占式调度的区别
抢占式调度：
这个调度是灵活的，但它也是与成本相关的，它有开销。一个进程只能占用CPU一个有限的时间，因为如果有一个高优先级的进程来了，它将中断第一个进程，新的进程将控制CPU。然而，如果高优先级的进程继续加入队列，它们将始终轮流在CPU优先，这意味着它可能让低优先级进程陷入饥饿状态。
非抢占式调度调度不能被中断：
只有当调度终止或进程处于等待状态时，其他事件才能依次执行。一旦一个进程从队列中开始运行CPU，它就会保持处理器繁忙，直到它终止或进入等待状态。这种调度也可能导致饥饿，因为如果一个具有长突发时间的进程正在运行处理器，那么其他进程将不得不等待很长时间。与抢占式调度不同，它没有开销。不是成本关联，也不灵活。
结论：
在抢占式调度中，新进程可以中断其他进程的执行，而在非抢占式调度中不能被中断。
抢占式调度是灵活的，但它也是成本相关的，它有开销。
非抢占式调度没有开销，但不灵活，也不耗费关联性。
6.3 假设下列流程在指定的时间到达并执行。每个进程将运行列出的时间。在回答这些问题时，请使用非抢占式调度，并根据必须做出决策时所掌握的信息做出所有决策。
概念补充：周转时间=完成时间-到达时间，平均则除以数量
a）使用FCFS调度算法，这些流程的平均周转时间是多少？
FCFS调度算法，先来先服务(FCFS: first come first service)总是把当前处于就绪队列之首的那个进程调度到运行状态
使用FCFS调度算法：
T(P1)=8-0=8; T(P2)=12-0.4=11.6; T(P3)=13-1=12
T(average)=(8+11.6+12)/3=10.53s
b）使用SJF调度算法，这些流程的平均周转时间是多少？
最短作业优先（SJF）调度算法将每个进程与其下次 CPU 执行的长度关联起来。当 CPU 变为空闲时，它会被赋给具有最短 CPU 执行的进程。如果两个进程具有同样长度的 CPU 执行，那么可以由 FCFS来处理。
使用SJF调度算法：
T(P1)=8-0=8; T(P3)=9-1=8; T(P2)=13-0.4=12.6
T(average)=(8+8+12.6)/3=9.53s
c）SJF算法应该提高性能，但是请注意，我们选择在时间0时运行进程P1，因为我们不知道两个较短的进程会很快到达。计算如果CPU为前一个单元空闲，然后使用SJF调度，那么平均周转时间将是多少。请记住，进程P1和P2在此空闲时间内正在等待，因此它们的等待时间可能会增加。这种算法可以称为Future-Knowledge Scheduling。
Future-Knowledge Scheduling:
T(P3)=2-1=1; T(P2)=6-0.4=5.6; T(P3)=14-0=14
T(average)=(1+5.6+14)/3=6.87s
6.6 假设调度算法(在短期CPU调度级别上)倾向于那些最近使用了最少处理器时间的进程。为什么这种算法有利于I/O绑定的程序，而且也不会使绑定CPU的程序永久饥饿？
我们的调度器将偏爱I/O绑定程序，因为当它们执行时，它们花费大部分时间等待某些设备上的I/O操作。这就决定了I/O绑定程序的速度。
因此，它们不需要大量的CPU时间或大量的短CPU时间，这反过来会使它们受到调度器的青睐。
调度器更喜欢I/O绑定的程序，因为它们在CPU上花费的时间更少。
CPU绑定的程序不会永久挨饿，因为I/O绑定的程序最终会终止。
6.9 传统的UNIX调度器强制优先级号与优先级之间的反向关系:优先级号越高，优先级越低。调度程序使用以下函数每秒重新计算一次进程优先级……
Q：传统的UNIX调度器强制优先级号与优先级之间的反向关系:优先级号越高，优先级越低。调度程序使用以下函数每秒重新计算一次进程优先级:Priority =(最近的CPU使用率/ 2)+ base，其中base = 60，最近的CPU使用率是指自上次重新计算优先级以来进程使用CPU的频率。假设进程P1的最近CPU使用率为40，进程P2的最近CPU使用率为18，进程P3的最近CPU使用率为10。当重新计算优先级时，这三个过程的新优先级是什么?基于此信息，传统UNIX调度器是提高还是降低CPU绑定进程的相对优先级?
使用6.9给予的公司那个是对每个进程进行计算：
Priority1=40/2+60=80
Priority2=18/2+60=69
Priority3=10/2+60=65
给予这些信息，传统的UNIX调度将会降低与CPU绑定的进程的相对优先权。
6.10 为什么调度程序区分I/O绑定程序和CPU绑定程序很重要？
由于I/O绑定的进程受到数据传输速度的限制，所以不要太频繁地调度它们，因为用户可能会看到计算机的卡顿。
6.13 在第五章中，我们讨论了各种内核数据结构上可能存在的竞争条件。大多数调度算法都维护一个运行队列，其中列出了可以在处理器上运行的进程。在多核系统上，一般有两种选择：
（1）每个处理核都有自己的运行队列。
（2）所有处理核共享一个运行队列。
这些方法的优缺点是什么？
每个处理核心都有自己的运行队列的优点:
- 每个处理核心可以将运行队列放置在自己的缓存中或具有特殊的硬件支持，使排队任务之间的上下文切换更快。
- 在多处理环境中，真正的并行性是通过平衡内核的负载做到的，调度程序可以尝试公平地处理所有处理内核的运行队列，并保持队列的运行均衡。
缺点是:
- 如果一个处理核心比其他处理核心更快地完成任务，而且没有新的任务到达它的运行队列，它将什么也不做。如果这种情况发生在多个核心上，那么这个问题就会变得更糟。
优点: 可以缓存运行队列，平衡工作负载。
失误: 没有核心可以从别的核心“窃取”工作，有些核心完成后可能什么也做不了。
6.16 考虑以下一组进程，CPU突发的长度以毫秒为单位
假设过程以P1、P2、P3、P4、P5的顺序到达，全部在时间0时刻到达。
a）绘制四个甘特图，用以下调度算法演示这些进程的执行: FCFS，SJF。非抢占优先级(优先级数较大意味着优先级较高)和 RR (量程 = 2)
FCFS:
SJF:
Priority(优先级数较大意味着优先级较高):
RR (量程 = 2):
b）a部分中每个调度算法的每个进程的周转时间是多少？
| FCFS | SJF | Priority | RR | |
|---|---|---|---|---|
| P1 | 2 | 3 | 15 | 2 |
| P2 | 3 | 1 | 20 | 3 |
| P3 | 11 | 20 | 8 | 20 |
| P4 | 15 | 7 | 19 | 13 |
| P5 | 20 | 12 | 13 | 18 |
c）对于这些调度算法，每个进程的等待时间是多少？
| FCFS | SJF | Priority | RR | |
|---|---|---|---|---|
| P1 | 0 | 1 | 13 | 0 |
| P2 | 2 | 0 | 19 | 2 |
| P3 | 3 | 12 | 0 | 12 |
| P4 | 11 | 3 | 15 | 9 |
| P5 | 15 | 7 | 8 | 13 |
d）哪种算法的平均等待时间最小（在所有进程中）
SJF
6.17 使用抢占式循环调度算法对以下进程进行调度。每个进程都分配了一个数字优先级，数字越大表示相对优先级越高……
Q：使用抢占式循环调度算法对以下进程进行调度。每个进程都分配了一个数字优先级，数字越大表示相对优先级越高。除了下面列出的进程之外，系统还有一个空闲任务（不消耗CPU资源，标识为P(idle)）。此任务的优先级为0，并且在系统没有其他可用进程可运行时安排此任务。时间量子的长度是10个单位。如果一个进程被优先级更高的进程抢占，则抢占的进程被放置在队列的末尾。
a）使用甘特图显示进程的调度顺序
b）每个流程的周转时间是多少？
P1-20;P2-25;P3-60;P4-15;P5-20;P6-10.
c）每个进程的等待时间是多少？
P1-0;P2-0;P3-35;P4-0;P5-10;P6-0.
d）CPU利用率是多少？
CPU运行了120个时间单位。在这120个时间单位中，有15个单位在执行空闲进程，而这个进程没有任何用处。
因此，利用率为：105=0.875=87.5%
6.19 以下哪种调度算法会导致饥饿？
a. FCFS; b. SJF; c. RR; d. Priority.
b& d
6.21 考虑一个运行十个 I/O 密集型任务和一个 CPU 密集型任务的系统。 假设 I/O 密集型任务每执行一次 CPU 计算就会发出一次 I/O 操作，并且每个 I/O 操作需要 10 毫秒才能完成。 还假设上下文切换开销为 0.1 毫秒，并且所有进程都是长时间运行的任务。 在以下情况下描述循环调度程序的 CPU 利用率：
a）时间量是1ms
利用率的计算：
(10 x I/O进程 + 1 x CPU进程) / (10 x I/O进程 + 1 x CPU进程 + 10 x 上下文切换) = (10 x 1ms + 1 x 1ms) / (10 x 1ms + 1 x 1ms + 10 x 0.1ms ) = 91%
b）时间量是10ms
利用率的计算：
(10 x I/O进程 + 1 x CPU进程) / (10 x I/O进程 + 1 x CPU进程 + 10 x 上下文切换) = (10 x 1ms + 1 x 10ms) / (10 x 1ms + 1 x 10ms + 10 x 0.1ms ) = 94%
6.23 考虑基于动态改变优先级的抢占优先级调度算法……
Q：考虑基于动态改变优先级的抢占优先级调度算法。较大的优先级数意味着更高的优先级。当一个进程正在等待 CPU（在就绪队列中，但未运行）时，其优先级以α 的速率变化。 当它运行时，它的优先级以 β 的速率变化。所有进程在进入就绪队列时都被赋予 0 的优先级。 可以设置参数 α 和 β 以给出许多不同的调度算法。
a）从β > α > 0得出的算法是什么？
FCFS。
当一个进程进入等待队列时，它的优先级为0。它在等待队列中停留的时间越长，该进程的优先级就越高。由此我们可以得出结论，在等待队列中排在第一位的进程具有最大的优先级，当一个进程运行时，它的优先级会增加一个更大的因子，所以直到它完成时才被中断。
b）从α > β > 0得出的算法是什么？
LCFS。
一个过程在队列中花费的时间越少，它就会得到奖励。当进程进入等待队列时，它的优先级为0。它在等待队列中停留的时间越长，进程的优先级就越小。
6.28 假设两个任务 A 和 B 正在 Linux 系统上运行。 A 和 B 的 nice 值分别为 -5 和 +5。 使用 CFS 调度程序作为指南，描述给定以下每个场景，两个进程之间 Vruntime 的各自值如何变化？
A和B都是CPU绑定：
Vruntime(A) < Vruntime(B)
A是I/O绑定，B是CPU绑定：
Vruntime(A) < Vruntime(B)
A是CPU绑定，B是I/O绑定：
Vruntime(A) > Vruntime(B)
