调度算法的介绍及优缺点

末蓝、 2024-02-19 14:14 46阅读 0赞

调度算法是根据系统的资源分配策略所规定的资源分配算法。有的调度算法适用于作业调度，有的适用于进程调度，有的两者都适用。  
先了解几个术语  
到达时间、服务时间、开始时间  
完成时间、等待时间  
周转时间：完成时间-到达时间  
带权周转时间：周转时间/服务时间

一、先来先服务(FCFS)/先进先出(FIFO)调度算法  
（1）概念：按照作业/进程进入系统的先后次序进行调度，先进入系统者先调度；即启动等待时间最长的作业/进程。是一种最简单的调度算法，即可用于作业调度，也可用于进程调度  
  
（2） 先来先服务（先进先出）优缺点  
\* 比较有利于长作业（进程），而不利于短作业（进程）  
\* 有利于CPU繁忙型作业（进程） ，而不利于I/O繁忙型作业（进程）  
\* 用于批处理系统，不适于分时系统

![这里写图片描述][SouthEast]  
二、短作业优先调度算法（SJF）

1、概念：从队列中选出一个估计运行时间最短的作业优先调度，即可用于作业调度，也可用于进程调度

2、SJ(P)F调度算法也存在不容忽视的缺点  
\*对长作业不利。严重的是，若一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度——饥饿  
\*完全未考虑作业(进程)的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理  
\*由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。

![SouthEast 1][]  
三、高优先权调度算法  
即可用于作业调度，也可用于进程调度

1、优先调度算法的类型  
（1）非抢占式优先权调度算法  
特点：系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成，或因发生某事件使该进程放弃处理机时，系统才将处理机重新分配给另一优先权最高的进程  
主要用于批处理系统中，也可用于某些对实时性要求不严的实时系统中  
（2）抢占式优先权调度算法  
特点：把处理机分配给优先权最高的进程，但在执行期间，只要出现另一个优先权更高的进程，则进程调度程序就立即停止当前进程的执行，并将处理机分配给新到的优先权最高的进程  
注意：只要系统中出现一个新的就绪进程，就进行优先权比较  
该调度算法，能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中

2、优先权类型  
高优先权调度算法，需要比较作业或进程的优先级，所以我们需要了解一下优先级  
优先权分为静态优先权、动态优先权  
（1）静态优先权  
静态优先权在创建进程时确定，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，例如，0∼7或0∼255， 又把该整数称为优先数  
确定进程优先权的依据有如下三个方面：  
进程类型：系统进程的优先权高于一般用户进程。  
进程对资源的需求：如进程的估计执行时间及内存需要量少的进程，应赋予较高的优先权。  
用户要求：由用户进程的紧迫程度和用户所付费用的多少来确定优先权。  
（2）动态优先权  
概念：在创建进程时赋予的优先权是随进程的推进或随其等待时间的增加而改变，以获得更好的调度性能。可规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高  
特征：具有相同优先权初值的进程，则最先进入就绪队列，其将因其动态优先权变得最高而优先获得处理机，此即FCFS算法  
具有各不相同的优先权初值的就绪进程，则优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机  
注意：当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下降，则可防止一个长作业长期地垄断处理机

四、高响应比优先调度算法  
（1）概念：高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。  
该算法中的响应比是指作业等待时间与运行比值，响应比公式定义如下：  
响应比 =（等待时间+要求服务时间）/ 要求服务时间,即RR=（w+s）/s=1+w/s，因此响应比一定是大于1的。  
（2）优缺点  
优点：等待时间相同的作业，则要求服务的时间愈短，其优先权愈高，——对短作业有利  
要求服务的时间相同的作业，则等待时间愈长，其优先权愈高，——是先来先服务  
长作业，优先权随等待时间的增加而提高，其等待时间足够长时，其优先权便可升到很高， 从而也可获得处理机——对长作业有利  
是一种折衷，既照顾了短作业，又考虑了作业到达的先后次序，又不会使长作业长期得不到服务。  
缺点：要进行响应比计算，增加了系统开销

五、简单的时间片轮转法(RR—Round Robin)  
（1）概念：系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片；当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便停止该进程的执行，并将其放就绪队列尾；然后，再把处理机分配给就绪队列中新的队首；时间片的大小从几ms到几百ms  
（2）缺点：紧迫任务响应慢。  
UNIX中采用：时间片+优先权  
（3）时间片选取  
太小，会频繁发生中断、进程上下文切换，增加系统开销，但利于短作业  
太大，退化成FCFS  
——时间片应该略大于一次典型交互的时间

[SouthEast]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/93ac5139888a41709d437bb053c48cd6.png
[SouthEast 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/648ed72893764ac29513b69fa44a482a.png