1-1.调度算法
一、调度算法
平均周转时间.png
Ti 是服务时间， 运行时间+等待时间
平均带权周转时间.png
Ts为实际服务时间(执行时间)。
1、先来先服务 （FCFS）:计算平均周转时间、平均带权的周转时间
特点：简单，有利于长作业 即CPU繁忙性作业
先来先服务0.png
先来先服务.png
2、短作业优先 （SJF）
假设系统中有两个等待的作业，作业1需要CPU的时间是99秒，作业2需要CPU的时间是1秒钟，它们开始运行的次序不同，系统里总的周转时间的结果也不同。
短作业优先0.png
短作业优先2.png
短作业优先1.png
先来先服务和短作业优先调度算法 ? 1.FCFS 特点：简单，有利于长作业 即CPU繁忙性作业 ? 2.短作业进程优先调度算法：SJ(P)F 提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量） 特点：对长作业不利，有可能得不到服务（饥饿） 估计时间不易确定
3、响应比高者优先
响应比： Ti / Ts 优先权： 优先权 = (等待时间 + 要求服务时间) / 要求服务时间
响应比高者优先.png
0时刻: P1运行， 10时刻: P1运行完，此时P2-P5的响应比分别为： P2：(1+9)/1=10 P3：(2+8)/2=5 P4：(1+7)/1=8 P5：(5+6)/5=2.2 因此执行P2 ? 0时刻: P1运行， 10时刻: P1运行完， P2运行 11时刻: P2运行完，此时P3-P5的响应比分别为： P3：(2+9)/2=5.5 P4：(1+8)/1=9 P5：(5+7)/5=2.4 因此执行P4 。 ? 0时刻: P1运行， 10时刻: P1运行完， P2运行 11时刻: P2运行完， P4运行 12时刻: P4运行完，此时P3、P5的响应比分别为： P3：(2+10)/2=6 P5：(5+8)/5=2.6 因此执行P3。 ? 0时刻: P1运行， 10时刻: P1运行完， P2运行，P1周转时间10 11时刻: P2运行完， P4运行，P2周转时间10 12时刻: P4运行完， P3运行，P4周转时间9 14时刻: P3运行完， P5运行，P3周转时间12 19时刻: P5运行完， P5周转时间15. ? ?平均周转时间为：(10+10+12+9+15)/5=56/5=11.2
4、高优先权优先调度算法:
1、优先级调度的含义 （1）当该算法用于作业调度时，系统从后备作业队列中选择若干个优先级最高的，且系统能满足资源要求的作业装入内存运行。 （2）当该算法用于进程调度时，将把处理机分配给就绪进程队列中优先级最高的进程。 ? 2、调度算法的两种方式 优先级调度算法细分成如下两种方式： 非抢占式优先级算法 在这种调度方式下，系统一旦把处理机分配给就绪队列中优先级最高的进程后，该进程就能一直执行下去，直至完成；或因等待某事件的发生使该进程不得不放弃处理机时，系统才能将处理机分配给另一个优先级高的就绪进程。 抢占式优先级调度算法 在这种调度方式下，进程调度程序把处理机分配给当时优先级最高的就绪进程，使之执行。一旦出现了另一个优先级更高的就绪进程时，进程调度程序就停止正在执行的进程，将处理机分配给新出现的优先级最高的就绪进程。 ? 3.优先级的类型:进程的优先级可采用静态优先级和动态优先级两种，优先级可由用户自定或由系统确定。
静态优先级：静态优先级是在创建进程时确定进程的优先级，并且规定它在进程的整个运行期间保持不变。 （2）确定优先级的依据 确定优先级的依据通常有下面几个方面： ①进程的类型。通常系统进程优先级高于一般用户进程的优先级；交互型的用户进程的优先级高于批处理作业所对应的进程的优先级。 ②进程对资源的需求。例如，进程的估计执行时间及内存需求量少的进程，应赋于较高的优先级，这有利缩小作业的平均周转时间。 ③根据用户的要求。用户可以根据自己作业的紧迫程度来指定一个合适的优先级。 （3）优缺点 静态优先级法的优点是 ①简单易行 ②系统开销小。 缺点是 ①不太灵活，很可能出现低优先级的作业(进程)，长期得不到调度而等待的情况。 ②静态优先级法仅适用于实时要求不太高的系统。 ?
动态优先级:动态优先级是在创建进程时赋予该进程一个初始优先级，然后其优先级随着进程的执行情况的 变化而改变，以便获得更好的调度性能。 （2）优缺点 动态优先级优点是使相应的优先级调度算法比较灵活、科学，可防止有些进程一直得不到调度，也可防止有些进程长期垄断处理机。动态优先级缺点是需要花费相当多的执行程序时间，因而花费的系统开销比较大。
? 4.适用场合编辑 非抢占式优先级算法 主要用于一般的批处理系统、分时系统，也常用于某些实时性要求不太高的实时系统。 抢占式优先级算法 常用于实时要求比较严格的实时系统中，以及对实时性能要求高的分时系统。</pre>
5、时间片轮转调度:最古老，最简单，最公平且使用最广的算法
算法描述： 用于分时系统中的进程调度。每次调度时，总是选择就绪队列的队首进程，让其在CPU上运行一个系统预先设置好的时间片。一个时间片内没有完成运行的进程，如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后，它返回到绪队列末尾重新排队，等待下一次调度。 ? 时间片大小的确定: 太大：退化为FCFS； 太小：系统开销过大. 系统对响应时间的要求；T=nq 就绪队列中进程的数目； 系统的处理能力：（应保证一个时间片处理完常用命令）
基于时间片的轮转调度算法1.png
基于时间片的轮转调度算法2.png
6、多级反馈队列调度算法
特点：长、短作业兼顾，有较好的响应时间 （1）短作业一次完成； （2）中型作业周转时间不长； （3）大型作业不会长期不处理。 ? 原理：
1、设有N个队列（Q1,Q2....QN），其中各个队列对于处理机的优先级是不一样的，也就是说位于各个队列中的作业(进程)的优先级也是不一样的。一般来说，优先级Priority(Q1) > Priority(Q2) > ... > Priority(QN)。怎么讲，位于Q1中的任何一个作业(进程)都要比Q2中的任何一个作业(进程)相对于CPU的优先级要高（也就是说，Q1中的作业一定要比Q2中的作业先被处理机调度），依次类推其它的队列。 ? 2、对于优先级最低的队列来说，里面是遵循时间片轮转法。也就是说，位于队列QN中有M个作业，它们的运行时间是通过QN这个队列所设定的时间片来确定的；对于其他队列，遵循的是先来先服务算法，每一进程分配一定的时间片，若时间片运行完时进程未结束，则进入下一优先级队列的末尾。 ? 3、各个队列的时间片是一样的吗？不一样，这就是该算法设计的精妙之处。各个队列的时间片是随着优先级的增加而减少的，也就是说，优先级越高的队列中它的时间片就越短。同时，为了便于那些超大作业的完成，最后一个队列QN(优先级最低的队列)的时间片一般很大(不需要考虑这个问题)。
多级反馈队列调度.png
例： 假设系统中有3个就绪队列Q1,Q2,Q3，时间片分别为2，4，8。 现在有3个作业J1,J2,J3分别在时间 0 ，1，3时刻到达。而它们所需要的CPU时间分别是3，2，1个时间片。 1、时刻0： J1到达。于是进入到队列1 ， 运行1个时刻 ， 时间片还未到，此时J2到达。 2、时刻1： J2到达。 由于时间片仍然由J1掌控，于是等待。 J1在运行了1个时间片后，已经完成了在Q1中的2个时间片的限制，于是J1置于Q2等待被调度。现在处理机分配给J2。 3、时刻2： J1进入Q2等待调度，J2获得CPU开始运行。 4、时刻3：J3到达，由于J2的时间片未到，故J3在Q1等待调度，J1也在Q2等待调度。 5、时刻4：J2处理完成，由于J3，J1都在等待调度，但是J3所在的队列比J1所在的队列的优先级要高，于是J3被调度，J1继续在Q2等待。 6、时刻5：J3经过1个时间片，完成。 7、时刻6：由于Q1已经空闲，于是开始调度Q2中的作业，则J1得到处理器开始运行。 8、时刻7：J1再经过一个时间片，完成了任务。于是整个调度过程结束。</pre>