这里回顾第7章，本章介绍了进程调度：介绍。

书籍介绍：

https://book.douban.com/subject/34994608/

学习资料：

参考资料：

https://github.com/joshuap233/Operating-Systems-Three-Easy-Pieces-NOTES/blob/main/07.%E7%AC%AC%E4%B8%83%E7%AB%A0-%E8%BF%9B%E7%A8%8B%E8%B0%83%E5%BA%A6:%E4%BB%8B%E7%BB%8D/%E9%97%AE%E9%A2%98%E7%AD%94%E6%A1%88.md

第7 章进程调度：介绍

内容回顾

关键概念

调度策略（sheduling policy）
调度指标
- 分为性能指标和公平指标
- 周转时间（性能指标）
  $T_{\text {周转时间}}=T_\text{完成时间}-T_\text {到达时间}$
- 响应时间（公平指标）
  $T_{\text {响应时间}}=T_{\text {首次运行}}-T_{\text {到达时间}}$
调度算法
- 先进先出调度（First In First Out或FIFO，First Come First Served或FCFS）
  - 可能会产生护航效应（convoy effect）：一些耗时较少的潜在资源消费者被排在重量级的资源消费者之后
- 最短任务优先（Shortest Job First或SJF）
  - 优化周转时间
  - 最短任务优先是非抢占式调度程序：会将每项工作做完，再考虑是否运行新工作。
- 最短完成时间优先（Shortest Time-to-Completion First，STCF）/ 或抢占式最短作业优先（Preemptive Shortest Job First ，PSJF）
  - 优化周转时间
  - 每当新工作进入系统时，它就会确定剩余工作和新工作中，谁的剩余时间最少，然后调度该工作。
- 轮转（Round-Robin，RR）调度
  - 响应时间
  - RR在一个时间片（time slice，称为调度量子，scheduling quantum）内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束。反复执行，直到所有任务完成。
  - 时间片长度必须是时钟中断周期的倍数。
结合I/O
- 保证交互式作业正在执行I/O时，其他CPU密集型作业在运行。

作业

1

FIFO：

Here is the job list, with the run time of each job:           
  Job 0 ( length = 200.0 )                                     
  Job 1 ( length = 200.0 )                                     
  Job 2 ( length = 200.0 )    

Final statistics:
  Job   0 -- Response: 0.00  Turnaround 200.00  Wait 0.00
  Job   1 -- Response: 200.00  Turnaround 400.00  Wait 200.00
  Job   2 -- Response: 400.00  Turnaround 600.00  Wait 400.00

  Average -- Response: 200.00  Turnaround 400.00  Wait 200.00

验证：

λ python ./scheduler.py -p FIFO -l 200,200,200 -c
ARG policy FIFO
ARG jlist 200,200,200

Here is the job list, with the run time of each job:
  Job 0 ( length = 200.0 )
  Job 1 ( length = 200.0 )
  Job 2 ( length = 200.0 )


** Solutions **

Execution trace:
  [ time   0 ] Run job 0 for 200.00 secs ( DONE at 200.00 )
  [ time 200 ] Run job 1 for 200.00 secs ( DONE at 400.00 )
  [ time 400 ] Run job 2 for 200.00 secs ( DONE at 600.00 )

Final statistics:
  Job   0 -- Response: 0.00  Turnaround 200.00  Wait 0.00
  Job   1 -- Response: 200.00  Turnaround 400.00  Wait 200.00
  Job   2 -- Response: 400.00  Turnaround 600.00  Wait 400.00

  Average -- Response: 200.00  Turnaround 400.00  Wait 200.00

SJF:

因为时长一样，所以和FIFO相同：

Here is the job list, with the run time of each job:           
  Job 0 ( length = 200.0 )                                     
  Job 1 ( length = 200.0 )                                     
  Job 2 ( length = 200.0 )    

Final statistics:
  Job   0 -- Response: 0.00  Turnaround 200.00  Wait 0.00
  Job   1 -- Response: 200.00  Turnaround 400.00  Wait 200.00
  Job   2 -- Response: 400.00  Turnaround 600.00  Wait 400.00

  Average -- Response: 200.00  Turnaround 400.00  Wait 200.00

验证：

λ python ./scheduler.py -p SJF -l 200,200,200 -c               
ARG policy SJF                                                 
ARG jlist 200,200,200                                          
                                                               
Here is the job list, with the run time of each job:           
  Job 0 ( length = 200.0 )                                     
  Job 1 ( length = 200.0 )                                     
  Job 2 ( length = 200.0 )                                     
                                                               
                                                               
** Solutions **                                                
                                                               
Execution trace:                                               
  [ time   0 ] Run job 0 for 200.00 secs ( DONE at 200.00 )    
  [ time 200 ] Run job 1 for 200.00 secs ( DONE at 400.00 )    
  [ time 400 ] Run job 2 for 200.00 secs ( DONE at 600.00 )    
                                                               
Final statistics:                                              
  Job   0 -- Response: 0.00  Turnaround 200.00  Wait 0.00      
  Job   1 -- Response: 200.00  Turnaround 400.00  Wait 200.00  
  Job   2 -- Response: 400.00  Turnaround 600.00  Wait 400.00  
                                                               
  Average -- Response: 200.00  Turnaround 400.00  Wait 200.00

2

FIFO：

Here is the job list, with the run time of each job:           
  Job 0 ( length = 100.0 )                                     
  Job 1 ( length = 200.0 )                                     
  Job 2 ( length = 300.0 )    

Final statistics:
  Job   0 -- Response: 0.00  Turnaround 100.00  Wait 0.00
  Job   1 -- Response: 100.00  Turnaround 300.00  Wait 100.00
  Job   2 -- Response: 300.00  Turnaround 600.00  Wait 300.00

  Average -- Response: 133.33  Turnaround 333.33  Wait 133.00

验证：

λ python ./scheduler.py -p FIFO -l 100,200,300 -c
ARG policy FIFO
ARG jlist 100,200,300

Here is the job list, with the run time of each job:
  Job 0 ( length = 100.0 )
  Job 1 ( length = 200.0 )
  Job 2 ( length = 300.0 )


** Solutions **

Execution trace:
  [ time   0 ] Run job 0 for 100.00 secs ( DONE at 100.00 )
  [ time 100 ] Run job 1 for 200.00 secs ( DONE at 300.00 )
  [ time 300 ] Run job 2 for 300.00 secs ( DONE at 600.00 )

Final statistics:
  Job   0 -- Response: 0.00  Turnaround 100.00  Wait 0.00
  Job   1 -- Response: 100.00  Turnaround 300.00  Wait 100.00
  Job   2 -- Response: 300.00  Turnaround 600.00  Wait 300.00

  Average -- Response: 133.33  Turnaround 333.33  Wait 133.33

SJF:

没变化，因为完成时长递增：

Here is the job list, with the run time of each job:           
  Job 0 ( length = 100.0 )                                     
  Job 1 ( length = 200.0 )                                     
  Job 2 ( length = 300.0 )    

Final statistics:
  Job   0 -- Response: 0.00  Turnaround 100.00  Wait 0.00
  Job   1 -- Response: 100.00  Turnaround 300.00  Wait 100.00
  Job   2 -- Response: 300.00  Turnaround 600.00  Wait 300.00

  Average -- Response: 133.33  Turnaround 333.33  Wait 133.00

验证：

λ python ./scheduler.py -p SJF -l 100,200,300 -c
ARG policy SJF
ARG jlist 100,200,300

Here is the job list, with the run time of each job:
  Job 0 ( length = 100.0 )
  Job 1 ( length = 200.0 )
  Job 2 ( length = 300.0 )


** Solutions **

Execution trace:
  [ time   0 ] Run job 0 for 100.00 secs ( DONE at 100.00 )
  [ time 100 ] Run job 1 for 200.00 secs ( DONE at 300.00 )
  [ time 300 ] Run job 2 for 300.00 secs ( DONE at 600.00 )

Final statistics:
  Job   0 -- Response: 0.00  Turnaround 100.00  Wait 0.00
  Job   1 -- Response: 100.00  Turnaround 300.00  Wait 100.00
  Job   2 -- Response: 300.00  Turnaround 600.00  Wait 300.00

  Average -- Response: 133.33  Turnaround 333.33  Wait 133.33

3

对于Job 0，响应时间为$0$，完成时间为$199+ 199 + 200=598$，等待时间为$598-200= 398$；
对于Job 1，响应时间为$1$，完成时间为$199+ 200 + 200=599$，等待时间为$599-200= 399$；
对于Job 2，响应时间为$2$，完成时间为$200+ 200 + 200=600$，等待时间为$600-200= 400$；

Here is the job list, with the run time of each job:           
  Job 0 ( length = 200.0 )                                     
  Job 1 ( length = 200.0 )                                     
  Job 2 ( length = 200.0 )    

Final statistics:
  Job   0 -- Response: 0.00  Turnaround 598.00  Wait 398.00
  Job   1 -- Response: 1.00  Turnaround 599.00  Wait 399.00
  Job   2 -- Response: 2.00  Turnaround 600.00  Wait 400.00

  Average -- Response: 1.00  Turnaround 599.00  Wait 399.00

4

JOB时长单调递增。

5

量子长度大于最大工作长度。

6

假设$N$个工作时分别为$t_1,\ldots, t_N$，按照升序排列得到：

$t_{(1) } \le \ldots \le t_{(N)}$

SJF的平均响应时间为：

$\frac{\sum_{i=1}^N \sum_{j < i} t_{(j)}}{N} = \sum_{i=1}^{N-1} \frac{N - i} Nt_{(i)}$

随着$t_i \to \infty$，平局响应时间

$\sum_{i=1}^{N-1} \frac{N - i} Nt_{(i)} \to \infty$

7

假设$N$个工作时分别为$t_1,\ldots, t_N$，假设量子长度为$t$，当$t$增加时，最终会有

$t> t_i ,i=1,\ldots ,N$

此时退化为FIFO，平均响应时间为

$\frac{\sum_{i=1}^N \sum_{j < i} t_j}{N} = \sum_{i=1}^{N-1} \frac{N - i} Nt_i$

第7 章 进程调度：介绍

内容回顾

关键概念

作业

1

2

3

4

5

6

7

第7 章进程调度：介绍