操作系统第五章作业 CPU 调度¶

5.1. Why is it important for the scheduler to distinguish I/O-bound programs from CPU-bound programs?¶

对于长期调度程序，知道进程是 IO 约束的还是 CPU 约束的之后，便可以按照一定比例组合被调度的进程，使得 CPU 和 IO 设备都会一直处于负载状态，从而提高资源的使用率。对于短期调度（CPU 调度），IO 约束的进程 CPU 区间都比较短，而 CPU 越苏进程则比较长，因而根据最短作业优先准则，可以优先调度 IO 约束进程。

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

a. CPU utilization and response time CPU 利用率与上下文交换频率成负相关，而响应时间与之成正相关，故冲突。

b. Average turnaround time and maximum waiting time 为了减小平均周转时间，通常会采用短作业优先算法，而这会令长作业的等待时间增大。

c. I/O device utilization and CPU utilization 为了提高 I/O 设备的利用率，需要优先执行 IO bound 进程，因为 IO 约束的进程 CPU 区间短，因而导致频繁的上下文交换，因而降低 CPU 效率。

5.4 Consider the following set of processes, with the length of the CPU-burst time given in milliseconds¶

Process	Burst Time	Priority
$ P_1 $	10	3
$ P_2 $	1	1
$ P_3 $	2	3
$ P_4 $	1	4
$ P_5 $	5	2

The processes are assumed to have arrived in the order $ P_1,P_2,P_3,P_4,P_5 $, all at time 0.

a. Draw four Gantt charts illustrating the execution of these processes using FCFS , SJF , a nonpreemptive priority (a smaller priority number implies a higher priority), and RR (quantum = 1) scheduling. 1. FCFS $ P_1 $ (10) | $ P_2 $(1) | $ P_3 $(2) | $ P_4 $(1) |$ P_5 $ (5) --- | --- | --- | --- | --- 2. SJF $ P_2 $(1) | $ P_4 $(1) | $ P_3 $(2) | $ P_5 $ (5) | $ P_1 $ (10) --- | --- | --- | --- | --- 3. nopreemptive priority $ P_2 $(1) | $ P_5 $ (5) | $ P_1 $ (10) | $ P_3 $(2) | $ P_4 $(1) --- | --- | --- | --- | --- 4. Round Robin $ P_1 $| $ P_2 $ | $ P_3 $ | $ P_4 $ |$ P_5 $ | $ P_1 $| $ P_3 $ | $ P_5 $ | $ P_1 $ |$ P_5 $ | $ P_1 $ | $ P_5 $ | $ P_1 $ | $ P_5 $ | $ P_1 $ | $ P_1 $ | $ P_1 $ | $ P_1 $ | $ P_1 $ | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
b. What is the turnaround time of each process for each of the scheduling algorithms in part a?

FCFS SJF nopreemptive priority RR

$ P_1 $ 10 19 16 19

$ P_2 $ 11 1 1 2

$ P_3 $ 13 4 18 7

$ P_4 $ 14 2 19 4

$ P_5 $ 19 9 6 14

c. What is the waiting time of each process for each of the scheduling algorithms in part a?

	FCFS	SJF	nopreemptive priority	RR
$ P_1 $	0	9	6	9
$ P_2 $	10	0	0	1
$ P_3 $	11	2	16	5
$ P_4 $	13	1	18	3
$ P_5 $	14	4	1	9
sum	48	16	41	27
- d. Which of the schedules in part a results in the minimal average waiting time (over all processes)?

答：SJF with 3.2 ms

5.10 Explain the differences in the degree to which the following scheduling algorithms discriminate in favor of short processes¶

a. FCFS
b. RR
c. Multilevel feedback queues

答：

FCFS 哪个先到哪个优先，因此对待短进程和长进程是平等的。
RR 给每个进程分配相同的时间片，因此也是平等的。
对于一种典型的多级反馈队列算法（有三个队列，前两个使用 RR 算法，时间片分别为 8ms，16ms，第三个使用 FCFS 算法，队列间使用抢占式优先级算法），短作业都会处于前面的队列，以此短作业的优先级更高。

5. Please prove: SJF gives the minimum average waiting time for a given set of processes to arrive at the same time¶

假设 CPU 按照一定顺序执行这些进程，每个进程 CPU 区间分别为$ t_1,t_2,\dots,t_n $。（非抢占）则平均等待时间为： $$ \overline t = \frac{1}{n}\sum_{i=1}^n{(i-1)t_i} $$ 由排序不等式知$ t_1,t_2,\dots,t_n $降序时最短，即 SJF 算法。

6. What is Processor Affinity? What is load balancing? What is the relationship between the two?¶

处理器亲和性指在多处理器调度算法中，由于 cache miss 的代价比较高，应该努力让一个进程在一个处理器上运行。而负载平衡指将工作负载平均分配到每个处理器上，从而保持每个处理器使用率都比较高。因此当一个处理器负载较高时，负载平平衡策略会倾向让负载分配到多个处理器上，而处理器亲和则倾向保持该状态。因此这两种策略有矛盾的关系。