一、例题

1.Explain the difference between preemptive and nonpreemptive scheduling.

Answer:

如果调度方案是非抢占的（nonpreemptive），一旦CPU分配给一个进程，那么该进程会一直使用CPU直到进程终止或切换到等待状态。而抢占的调度方案会在进程未达到终止或等待状态就切换进程（比如出现中断或 等待状态的进程的I/O完成而切换到就绪状态）。

简而言之就是CPU是否允许当前进程未结束或到达等待状态就进行进程切换。

 

2.Discuss how the following pairs of scheduling criteria conflict in certain settings.

a. CPU utilization and response time (CPU利用率和响应时间)

CPU利用率一定程度上取决于进程上下文切换的频繁程度，比如我们采用FCFS的调度方案那么CPU利用率也许会比较大但是不可避免的是响应时间会增加（显然这种方式进程等待时间会很不理想）。

 

b. Average turnaround time and maximum waiting time （平均周转时间和最大等待时间）

为使平均周转时间少，需要优先处理所需时间少的任务，然后这样时间长度长的进程的等待时间无疑会被加长。

 

c. I/O device utilization and CPU utilization（I/O设备利用率和CPU利用率）

CPU利用率的提高需要减少上下文切换的次数，而I/O设备利用率的提高需要让I/O设备一准备就绪就能马上运行—这需要上下文切换来实现，所以两者是矛盾的。

 

3.Consider the following set of processes,with the length of the CPU burst given in milliseconds:

The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.

a. Draw four Gantt charts that illustrate the execution of these processes using the following scheduling algorithms: FCFS, SJF, nonpreemptive priority(a larger priority number implies a higher priority), and RR (quantum = 2).

b. What is the turnaround time of each process for each of the scheduling algorithms in part a?

c. What is the waiting time of each process for each of these scheduling algorithms?

d. Which of the algorithms results in the minimum average waiting time (over all processes)?

Answer: a & b 如图

c：由上面的计算知SJF调度算法在本题的平均等待时间最少。

注意RR算法：如果进程在时间片用完之前就结束了，那么会进行上下文切换（就绪队列的下一进程）而不是浪费剩余的时间。如果进程在一个时间片内还没结束，那么它会被抢占，其会被放回就绪队列。

注意turnaround time是进程提交到结束而不是开始被调度到结束

 

4.

Consider two processes, P1 and P2,where p1 =50,  t1 =25,  p2 =75,  and t2 =30.

a. Can these two processes be scheduled using rate-monotonic scheduling（速率单调调度算法）? Illustrate your answer using a Gantt chart such as the ones in Figure 6.16–Figure 6.19.

b. Illustrate the scheduling of these two processes using earliest deadline-first(EDF 最早截止期限优先调度) scheduling.

Answer:

a.

p1=50， p2=75，P1 的优先级更高，所以在初始时间，先调度 P1 到 CPU，P1 执行 25 后结束，满 足截止期限，调度 P2，P2 执行 25 后，在时刻 50，第二个 P1 到达，因为 P1 的周期短， 所以 P2 被 P1 抢占，P1 在时刻 75 完成，再恢复 P2，P2 执行 5 后在 80 结束，超出截止期限。从 80 开始，第二轮 P2 开始执行，执行20，到100时被第三轮 P1 抢占，P1 执行 25 到 125，然后 P2 再继续执行 10 到 135,135-150CPU 空闲，因为可能使进程错过截止期限所以不能采用单调速率调度，

这里把一个进程的下一个周期到达时间点称为截止期限

b.

在时刻 0，P1 的截止期限为 50，P2 为 75，所以先调度 P1，并在 25 完成执行，然后调度 P2，在时刻 50 又会到达一个 P1，但正在执行的 P2 截止期限为 75，而到达的第二 轮 P1 截止期限为 100，所以 P2 继续执行，在 55 完成，然后开始执行第二轮 P1，在时刻 75 第二轮 P2 到达，但 P1 截止期限为 100，P2 为 150，所以不会被抢占，P1 在 80 完成， 然后 P2 执行，在 100 又到达一个 P1，此时截止期限都为 150，不被抢占，P2 在 110 完 成，开始执行 P1，在 135 结束，此时没有新的进程，直到 150 再次到达一个 P2。Gantt 图如上，括号内表示其截止期限.

 

二、调度准则

①CPU 使用率:需要使 CPU 尽可能忙。从概念上讲， CPU 使用率从 0%~100%。对 于真实系统，它应从 40% (轻负荷系统) ~90% (重负荷系统)。

②吞吐量:如果 CPU忙于执行进程，那么就有工作在完成。一种测量工作量的方法称 为在吞吐量，它指一个时间单元内所完成进程的数量。对于长进程，吞吐量可能为每小时一 个进程;对于短进程，吞吐量可能为每秒 10 个进程。

③周转时间:从一个特定进程的角度来看，一个重要准则是运行该进程需要多长时间。

从进程提交到进程完成的时间段称为周转时间。周转时间为所有时间段之和，包括等待进入内存、在就绪队列中等待、在 CPU 上执行和I/O执行。

④等待时间: CPU 调度算法并不影响进程运行和执行 I/O 的时间:它只影响进程在就绪队列中等待所花的时间。等待时间为在就绪队列中等待所花费时间之和。

⑤响应时间:对于交互系统，周转时间并不是最佳准则。通常，进程能相当早就产生输出，井继续计算新结果同时输出以前的结果给用户。因此，另一时间是从提交请求到产生第一响应的时间。这种时间称为响应时间，是开始响应所需要的时间，而不是输出响应所需要的时间。周转时间通常受输出设备速度的限制。

优化设计：一般情况下，需要使CPU使用率和吞吐量最大化，周转时间、等待时间和响应时间最小化，绝大多数情况下要优化平均值。不过在有的情况下，需要优化最小值或最大值，例如，保证所有用户都得到好的服务，可能要使最大响应时间最小。

三、调度算法（Scheduling algorithm）

 

1.先到先服务（FCFS）（first-come,first-served(FCFS) Scheduling algorithm）

FCFS调度算法是非抢占的，先请求CPU的进程先分配到CPU（Arrive time）。

一旦CPU被分配给了一个进程，该进程就会保持CPU直到释放CPU为止，即程序终止或是请求I/O。

护航效果（convoy effect）指所有其他进程等待一个大进程释放CPU，这样会导致CPU和设备的使用率变得很低。且对分时系统（每个用户需要定时地得到一定的CPU时间）是不可行的。

 

2.最短作业调度优先（SJF  shortest-job-first）

SJF调度算法是非抢占/抢占（两者都有可能）的，优先调度（就绪队列中）CPU区间最短的（更确切地说，是下一个CPU区间最短的（不等于总长度））进程。

SJF算法将大大减少平均等待时间，但是难度在于怎么知道下一个CPU区间的长度。SJF通常用于长期调度，即将用户提交作业时所指定的进程时间极限作为长度。

将SJF应用于短期CPU调度的一种方法是近似SJF调度，该调度算法认为进程下一个CPU区间的长度与以前的相似，通过该及近似值来预测……

当一个新进程到达就绪队列而之前的进程正在执行时，就需要选择。如果与当进程相比，新进程有一个更短的CPU时间，抢占SJF（最短剩余时间优先调度（shortest-remaining-time-first scheduling））就会允许其抢占CPU，而非抢占SJF会让正在运行的进程先完成其CPU区间。

 

3.优先级调度(priority scheduling algorithm)

根据进程的优先级选择调度次序......

 

4.轮转法调度(round-robin,RR)

简单举例：如果进程在时间片用完之前就结束了，那么会进行上下文切换（就绪队列的下一进程）而不是浪费剩余的时间。如果进程在一个时间片内还没结束，那么它会被抢占，其会被放回就绪队列。

该算法的性能取决于时间片的选取

尽管时间片应该比上下文切换时间长，但也不能太大。如果时间片太大，那么 RR 调 度就演变成了 FCFS 调度。根据经验， 80% 的 CPU 区间应该小于时间片。

 

5.多级队列调度

将就绪队列分成多个独立队列，根据进程的属性，如内存大小、进程优先级、进程类型，一个进程将永久地分配到一个队列。每个队列有自己的调度算法，队列之间必须有调度，通常采用固定优先级抢占调度。例如，前台队列可以比后台队列具有绝对的优先级。

 

6.多级反馈队列调度

其与多级队列调度的区别是，允许进程在队列间移动，如果进程使用过多CPU时间，那么它会被转移到更低优先级队列，而且在优先级队列中等待时间过长的进程会被转移到更高优先级队列，这种形式的老化组织饥饿的发生。该调度算法需要多个参数定义，最为复杂。

 

7. rate-monotonic scheduling速率单调调度算法 和 earliest deadline-first(EDF) 最早截止期限优先调度

这两个算法应该归于优先级调度？

单调速率调度算法为每个周期性任务分配一个优先级，周期越短，优先级越高

最早截止期限优先调度（EDF）根据截止期限动态分配优先级，截止期限越早，优先级越高

 

附：线程调度

• 内核线程由系统调度
• 用户线程由线程库管理
• 进程竞争范围PCS方法（cpu的竞争发生在属于相同进程的线程之间）- 在执行多对一和多对多模型的系统上，线程库调度用户级线程到一个有效的LWP上运行。
• 系统竞争范围SCS方法（cpu的竞争发生在系统的所有线程之间）- 决定哪个内核线程到cpu
• 采用一对一模型的系统（xp.linux），调度仅适用SCS方法

Question:Distinguish between PCS and SCS scheduling.

Answer:

线程库调度用户级线程到一个有效的LWP上运行，这被称为进程竞争范围（process-contention scope，PCS）方法，因为CPU竞争发生在属于相同进程的线程之间。为了决定调度哪个内核线程到CPU，内核采用系统竞争范围（system-contention scope，SCS）方法来进行，竞争CPU发生在系统所有线程中，采用一对一的模型的系统，调度仅使用SCS方法。PCS 一般是根据优先级完成的一一调度程序选择具有最高优先级的可运行的线程来运行。