一、调度算法
平均周转时间.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>
网友评论