【操作系统】调度算法的评价指标和三种调度算法

一、调度算法的评价指标

1.1 CPU利用率

• 由于早期的CPU造价极其昂贵，因此人们会希望让CPU尽可能多地工作
• CPU利用率：指CPU“忙碌”的时间占总时间的比例。
• 利用率 = 忙碌的时间 / 总时间
• Eg:某计算机只支持单道程序，某个作业刚开始需要在CPU上运行5秒再用打印机打印输出5秒，之后再执行5秒，才能结束。在此过程中，CPU利用率、打印机利用率分别是多少？

• CPU利用率 = （5 + 5） / （5 + 5 + 5） = 66.66%
• 打印机利用率 = 5 / （5 + 5 + 5 ） = 33.33%

1.2 系统吞吐量

• 对于计算机来说，希望能用尽可能少的时间处理完尽可能多的作业
• 系统吞吐量：单位时间内完成作业的数量
• 系统吞吐量 = 总共完成了多少道作业 / 总共花了多少时间

• Eg:某计算机系统处理完10道作业，共花费100秒，则系统吞吐量为？

• 10/100=0.1道/秒

1.3 周转时间

• 对于计算机的用户来说，他很关心自己的作业从提交到完成花了多少时间。
• 周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。
• 它包括四个部分：作业在外存后备队列上等待作业调度（高级调度）的时间、进程在就绪队列上等待进程调度（低级调度）的时间、进程在CPU上执行的时间、进程等待/O操作完成的时间。后三项在一个作业的整个处理过程中，可能发生多次。
• (作业)周转时间 = 作业完成时间 - 作业提交时间
• 对于用户来说，更关心自己的单个作业的周转时间
• 平均周转时间= 各作业周转时间之和 / 作业数
• 对于操作系统来说，更关心系统的整体表现，因此更关心所有作业周转时间的平均值
• 带权周转时间 = 作业周转时间 / 作业实际运行的时间 = （作业完成时间 - 作业提交时间）/ 作业实际运行的时间
• 对于周转时间相同的两个作业，实际运行时间长的作业在相同时间内被服务的时间更多带权周转时间更小，用户满意度更高
• 对于实际运行时间相同的两个作业，周转时间短的带权周转时间更小，用户满意度更高
• 平均带权周转时间 = 各作业带权周转时间之和 / 作业数

1.4 等待时间

• 计算机的用户希望自己的作业尽可能少的等待处理机
• 等待时间，指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。
• 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待/O完成的期间其实进程也是在被服务的，所以不计入等待时间。
• 一个作业总共需要被CU服务多久，被I/O设备服务多久一般是确定不变的，因此调度算法其实只会影响作业/进程的等待时间。当然，与前面指标类似，也有“平均等待时间”来评价整体性能。

1.5 响应时间

• 对于计算机用户来说，会希望自己的提交的请求（比如通过键盘输入了一个调试命令）尽早地开始被系
  统服务、回应。
• 响应时间，指从用户提交请求到首次产生响应所用的时间。

二、 调度算法

2.1 先来先服务（FCFS）

例题：各进程到达就绪队列的时间、需要的运行时间如下表示。使用先来先服务调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

• 先来先服务调度算法：按照到达的先后顺序调度，事实上就是等待时间越久的越优先得到服务。
• 因此，调度顺序为：P1→P2→P3→P4

• 周转时间 = 完成时间 - 到达时间
• 周转时间： P1=7-0=7;P2=11-2=9:P3=12-4=8;P4=16-5=11
• 带权周转时间 = 周转时间 / 运行时间
• 带权周转时间：P1=7/7=1;2=9/4=2.25;P3=8/1=8;P4=11/4=2.75
• 等待时间 = 周转时间 - 运行时间
• 等待时间：P1=7-7=0;P2=9-4=5;P3=8-1=7;P4=11-4=7
• 平均周转时间=(7+9+8+11)/4=8.75
• 平均带权周转时间=（1+2.25+8+2.75)/4=3.5
• 平均等待时间=(0+5+7+7)/4=4.75

• 优点：公平、算法实现简单
• 缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即，FCFS算法对长作业有利，对短作业不利

2.2 短作业优先（SJF）

• 算法思想：

• 追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间

• 算法规则：

• 最短的作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短）

• 用于作业/进程调度：

• 即可用于作业调度，也可用于进程调度。用于进程调度时称为“短进程优先(SPE,Shortest Process First)算法”

• SJF和SPF是非抢占式的算法。但是也有抢占式的版本一一最短剩余时间优先算法（SRTN,Shortest Remaining Time Next）

例题：各进程到达就绪队列的时间、需要的运行时间如下表示。使用非抢占式的短作业优先调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

• 短作业/进程优先调度算法：每次调度时选择当前己到达且运行时间最短的作业/进程。
• 因此，调度顺序为：P1→P3→P2→P4

• 周转时间 = 完成时间 - 到达时间
  
• 周转时间：P1=7-0=7;P3=8-4=4:P2=12-2=10:P4=16-5=11
  Access token invalid or no longer valid
  
• 带权周转时间 = 周转时间 / 运行时间
  
• 带权周转时间：P1=7/7=1;P3=4/1=4;P2=10/4=2.5;P4=11/4=2.75
  
• 等待时间 = 周转时间 - 运行时间
  
• 等待时间：P1=7-7=0:P3=4-1=3;P2=10-4=6;P4=11-4=7
  
• 平均周转时间=(7+4+10+11)/4=8
  
• 平均带权周转时间=(1+4+2.5+2.75)/4=2.56
  
• 平均等待时间=(0+3+6+7)/4=4
  

例题：各进程到达就绪队列的时间、需要的运行时间如下表示。使用抢占式的短作业优先调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

• 最短剩余时间优先算法：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度

• 周转时间=完成时间-到达时间
• 周转时间：P1=16-0=16:P2=7-2=5:P3=5-4=1:P4=11-5=6
• 带权周转时间=周转时间/运行时间
• 带权周转时间：P1=16/7=2.28;P2=5/4=1.25;P3=1/1=1;P4=6/4=1.5
• 等待时间=周转时间-运行时间
• 等待时间：P1=16-7=9:P2=5-4=1;P3=1-1=0;P4=6-4=2
• 平均周转时间=(16+5+1+6)/4=7
• 平均带权周转时间=(2.28+1.25+1+1.5)/4=1.5
• 平均等待时间=(9+1+0+2)/4=3

• 优点：“最短的”平均等待时间、平均周转时间
• 缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
• 会导致饥饿，如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。如果一直得不到服务，则称为“饿死”

2.3 高响应比优先（HRRN）

• 算法思想：
• 要综合考虑作业/进程的等待时间和要求服务的时间
• 算法规则：
• 在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
• 既可用于作业调度，也可用于进程调度
• 非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比
• 响应比 = （等待时间+要求服务时间）/ 要求服务时间

例题：各进程到达就绪队列的时间、需要的运行时间如下表示。使用高响应比优先调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

• 高响应比优先算法：非抢占式的调度算法，只有当前运行的进程主动放弃CPU时（正常/异常完成，或主动阻塞），才需要进行调度，调度时计算所有就绪进程的响应比，选响应比最高的进程上处理机。
• 0时刻：只有P1到达就绪队列，P1上处理机
• 7时刻(P1主动放弃CPU):就绪队列中有P2(响应比=(5+4)/4=2.25)、P3(3+1)/1=4)、P4(2+4)/4=1.5),
• 8时刻(P3完成)：P2(2.5)、P4(1.75)
• 12时刻(P2完成)：就绪队列中只剩下P4

• 综合考虑了等待时间和运行时间（要求服务时间）
• 等待时间相同时，要求服务时间短的优先(SF的优点)
• 要求服务时间相同时，等待时间长的优先(FCFS的优点)
• 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题