操作系统中典型的调度算法

这是在学习过程中学习到的知识，把它记录下来并按自己的理解写下来。如果帮到你的话，请点个赞

调度：在多道程序系统中，进程的数量往往多于处理机的个数，因此进程竞争处理机的现象难以避免。处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法将处理机分配给挑中的进程，使进程可以并发得执行。进程调度算法可以调高CPU的利用率，使处理机处于繁忙状态。而作业调度则是按照一定的算法从后背队列中选取合适的作业调入内存，并为它们创建进程，分配必要的资源，然后插入就绪队列，等待处理机的分配。

操作系统中存在多种调度算法，有的调度算法适用于作业调度，有的调度算法适用于进程调度，有的两者都适用。

1.先来先服务(FCFS)调度算法

FCFS调度算法是一种最简单的调度算法，它即可用于作业调度，又可用于进程调度。

在作业调度中，算法每次从后背队列中选取最先进入该队列的一个或几个作业，将它们调入内存，并为之创建进程分配相应的资源，放入就绪队列。

在进程调度中，算法每次从就绪队列中选取最先进入该队列的进程，并分配给其处理机使之运行，直至完成或因某种原因而阻塞时才释放处理机。

                                                                   FCFS调度算法的性能展示

平均等待时间=(0+1.7+2+3)/4=1.675  平均周转时间=(2+2.7+4+4)/4=3.175  平均带权周转时间=(1+2.7+2+4)/4=2.425

FCFS算法属于不可剥夺算法，从表面上看，它似乎是不公平的，但若一个长作业率先进入队列，而后面的许多短作业需要等待很长时间，而短作业可能需要先完成，比较着急，但是因为先来先服务又只能处于就绪状态。因此它不能作为分时系统和实时系统的主要调度策略，但它常被结合在其它调度策略中使用。比如，在使用优先级作为调度策略的系统中，往往对多个优先级相同的进程采用FCFS算法来调度（短作业优先也是）。

FCFS算法的优点是算法简单，但效率较低，不适合对处理机比较急切的短进程。但是对长作业有利，不利于短作业，适合于CPU繁忙性的作业，不适合于I\O繁忙型的作业。

2. 短作业优先(SJF)调度算法

短作业(进程)优先调度算法是指对短作业(进程)优先调度的算法。短作业优先是指从后备队列中选择一个或若干个估计运行时间最短的作业，并将它们调入内存运行(创建进程，并分配相应的资源放入就绪队列)。短进程优先是指从就绪队列中选取一个运行时间最短的进程将处理机分配给它，使之立即运行，直到完成或因某种原因阻塞时，才释放处理机。

                                           对上表执行短作业优先调度算法如下

平均等待时间=(0+1.7+3+1)/4=1.425 平均周转时间=(2+2.7+5+2)/4=2.925 平均带权周转时间=(1+2.7+2.5+2)/4=2.05

SJF(Short Job First)有缺点也有优点

（1）该算法对长作业不利，容易出现饥饿现象

（2）该算法不考虑作业的紧迫程度

（3）作业长短根据用户所提供的估计时间而定的，而用户可能有意无意的改变其运行时间，不一定能真实反映运行时间

注意：SJF调度算法的平均等待时间，平均周转时间最少

3. 优先级调度算法作业调入内存，并为它们创建进程抢占

优先级算法又称优先权调度算法。它即可用于作业调度，又可用于进程调度，该算法中的优先级被用来描述任务的紧迫程度。

在作业调度中，在后备队列中选择一个或多个作业调入内存，并为它们创建进程且分配相应的资源，放入就绪队列，

在进程调度中，从就绪队列中选择一个优先级最高的进程，将处理机分配给它，直到该进程运行完成或因某种原因阻塞而让出处理机。

根据新的更高优先级能否抢占现有的正在执行的进程，可将该算法分为两类

（1）非剥夺式优先级调度算法：当一个进程正在处理机上运行时，即使出现一个优先级更为高的进程，当前进程也不会出让处理机，直到该进程执行完成或因某种原因而让出处理机(阻塞),才分配处理机给优先级更高的进程。

（2）剥夺式优先级调度算法：当一个进程正在处理机上运行时，如果出现一个优先级更为高的进程，则保存当前的工作环境并出让处理机，分配给优先级更为高的进程。

根据进程优先级是否可以改变，可将进程优先级分为两种

（1）静态优先级  优先级是在创建进程的时候确定的，在进程的整个运行期间保持不变。确定静态优先级的主要依据有进程类型，进程对资源的要求，用户要求。

（2）动态优先级 在创建进程的时候赋予一个值，随着进程的运行，根据情况的变化来动态调整优先级。调整优先级的主要依据有进程占有CPU时间的长短，就绪进程等待CPU时间的长短。

进程优先级的设置可参照以下原则：

（1）系统进程>用户进程 

（2）交互型进程>非交互型进程

（3）I/O型进程>计算型进程

4. 高响应比优先调度算法

高响应比优先调度算法主要用于作业调度，是对FCFS算法和SJF算法的一种综合考虑，同时考虑了每个作业的运行时间和等待时间。在每次进行作业调度时，先计算后备队列中每个作业的响应比，然后将响应比最高的作业调入内存。

响应比公式： 响应比=(等待时间+要求服务时间)/要求服务时间

根据公式可以知道：

（1）等待时间相同时，要求服务时间越短，响应比越高，照顾了短作业。

（2）要求服务时间相同时，等待时间越长，响应比越高，照顾了长时间等待的作业，类似于先来先服务。

（3）而且长作业会随着等待时间的变长而响应比越来越高，最终被调入内存执行，也考虑了长作业的情况（相比于短作业优先调度算法），避免了饥饿现象。

5. 时间片轮转调度算法

时间片轮转调度算法主要适应于分时系统，在这种算法中，系统将所有就绪进程按到达的先后顺序排成一个队列，进程调度程序总是选择就绪队列中的第一个进程执行，类似于先来先服务的原则，但是只能运行一个时间片，如100ms。在使用完一个时间片后，若该进程仍未完成，则让出处理机并排到队列末尾，等待下一轮的执行。

时间片的大小对系统性能的影响很大，若时间片足够大，导致所有进程都能在一个时间片内执行完毕，则时间片轮转调度算法退化为先来先服务算法。若时间片太小，则处理机在进程间过于频繁的切换，将会导致处理机的开销增大，而真正用于处理用户进程的时间将减少。因此，时间片的大小选取要适当。

时间片的选择取决于：系统的响应时间，队列中就绪进程的数目以及系统的处理能力。

6.多级反馈队列调度算法

多级反馈队列算法是时间片轮转调度算法和优先级调度算法的结合与发展。通过动态调整优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面的系统目标。比如：为提高系统吞吐量和缩短平均周转时间而照顾短进程；为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程；同时，也不需要事先预估进程的运行时间。

（1）设置多个就绪队列，并为各个队列赋予不同的优先级，第一级队列的优先级最高，第二级次之，其余队列的优先级依次降低。

（2）赋予各个队列进程时间片的大小不同，第一级队列的时间片最小，其余队列的时间片依次增加，优先级越高的队列所分配的时间片越小。例如，第二级队列比第一级队列的时间片长一倍..........第i级队列的时间片比第i-1级的时间片长一倍。

（3）一个新进程进入内存后，首先将它放入第一级队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在时间片呃逆完成，则准备撤离系统。若它在一个时间片内未完成，则把它调入下一级队列的末尾，同样按FCFS原则等待运行，如此下去.........当一个长进程噢鞥第一级队列降到第n级队列后，在第n级队列中采用时间片轮转的方式运行。

（4）仅当上一级队列为空时，下一级队列中的进程才能分配到处理机运行。只有1~（i-1）级的队列都为空时，才运行第i级队列的进程。如果处理机正在处理第i级队列中的某进程，这时又有新进程进入优先级较高的队列（1~（i-1）中的任何有一个队列），则此时进程将抢占正在运行进程的处理机，把被剥夺处理机的进程放入该级队列的末尾，把处理机分配给优先级更高的进程。

多级反馈队列的优点：

（1）终端型作业用户，短作业优先

（2）短批处理作业用户，周转时间短

（3）长批处理作业用户，经过前面几个队列得到部分执行，不会长期得不到处理

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！