OSTEP Chapter 7 回顾

距离上次更新已经 1116 天了，文章内容可能已经过时。

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

书籍介绍：

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

学习资料：

• https://pages.cs.wisc.edu/~remzi/OSTEP/
• https://github.com/remzi-arpacidusseau/ostep-translations/tree/master/chinese
• https://github.com/joshuap233/Operating-Systems-Three-Easy-Pieces-NOTES

参考资料：

• https://www.cnblogs.com/bwbfight/p/11181631.html
• https://blog.csdn.net/u014530704/article/details/73848573
• https://www.cnblogs.com/kunhu/p/3608109.html
• https://blog.csdn.net/qq_42914528/article/details/82023408

参考资料：

• 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,\dots ,t_N$，按照升序排列得到：

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

SJF的平均响应时间为：

$$\frac{\sum _{i=1}^N\sum _{j<i}{t}_{(j)}}{N}=\sum _{i=1}^{N-1}\frac{N-i}{N}{t}_{(i)}$$

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

$$\sum _{i=1}^{N-1}\frac{N-i}{N}{t}_{(i)}\to \mathrm{\infty }$$

7

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

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

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

$$\frac{\sum _{i=1}^N\sum _{j<i}{t}_j}{N}=\sum _{i=1}^{N-1}\frac{N-i}{N}{t}_i$$