常见的作业调度和进程调度算法总结

作业调度和进程调度的区别： 作业调度是按一定的算法从磁盘上选择资源能得到满足的作业装入内存，使作业有机会去占用处理器执行。但是，一个作业能否占用处理器，什么时间能够占用处理器，必须由进程调度来决定。所以，作业调度选中 了一个作业且把它装入内存时，就应为该作业创建一个进程，若有多个作业被装入内存，则内存中同时存在多个进程，这些进程的初始状态为就绪状态，然后，由进程调度来选择当前可占用处理器的进程，进程运行中由于某种原因状态发生变化，当它让出处理器时，进程调度就再选另一个作业的进程运行。 因此，作业调度与进程调度相互配合才能实现多道作业的并行执行。

作业调度 、先来先服务（FCFS, First Come First Serve）： 简介：先来先服务调度算法是根据进程进入就绪队列的顺序来占用cpu，一个进程一旦分得处理机，便一直执行下去，直到该进程完成或阻塞时，才释放处理机。

原理： 当作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，优先从后备队列中，选择一个或多个位于队列头部的作业，把他们调入内存，分配所需资源、创建进程，然后放入“就绪队列”,直到该进程运行到完成或发生某事件堵塞后，进程调度程序才将处理机分配给其他进程。

优缺点： 有利于长作业而不利于短作业。 有利于CPU繁忙型作业。而不利于I/O繁忙型作业（交换少）。

、短作业优先（SJF, Shortest Job First） 描述： 这是对FCFS算法的改进，其目标是减少平均周转时间 优先调度并处理短作业，所谓短是指作业的运行时间短。而在作业未投入运行时，并不能知道它实际的运行时间的长短，因此需要用户在提交作业时同时提交作业运行时间的估计值。

优点： 比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；

缺点： 对长作业非常不利，可能长时间得不到执行； 未能依据作业的紧迫程度来划分执行的优先级； 难以准确估计作业（进程）的执行时间，从而影响调度性能。

、轮转法 描述： （1）将系统中所有的就绪进程按照FCFS原则，排成一个队列。 （2）每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。 （3）在一个时间片结束时，发生时钟中断。 （4）调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。 （5）进程可以未使用完一个时间片，就出让CPU（如阻塞）。

目的： 每个进程在就绪队列中的等待时间与享受服务的时间成正比例。 次算法与时间片的大小有关，进程越多时间片越小。

、多级反馈队列 描述： 设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍。 新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成。 仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。

优点 为提高系统吞吐量和缩短平均周转时间而照顾短进程。 为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程。 不必估计进程的执行时间，动态调节。

进程调度算法 、先进先出算法(FIFO) 描述： 按照进程进入就绪队列的先后次序来选择。即每当进入进程调度，总是把就绪队列的队首进程投入运行。

优缺点： 比较有利于长进程，而不利于短进程，有利于CPU 繁忙的进程，而不利于I/O 繁忙的进程。

、时间片轮转算法(RR) 描述： 该算法采用剥夺策略。让就绪进程以FCFS 的方式按时间片轮流使用CPU 的调度方式，即将系统中所有的就绪进程按照FCFS 原则，排成一个队列，每次调度时将CPU 分派给队首进程，让其执行一个时间片，时间片的长度从几个ms 到几百ms。在一个时间片结束时，发生时钟中断，调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程，进程可以未使用完一个时间片，就出让CPU（如阻塞）。时间片轮转调度算法的特点是简单易行、平均响应时间短，但不利于处理紧急作业。在时间片轮转算法中，时间片的大小对系统性能的影响很大，因此时间片的大小应选择恰当。

短进程优先调度算法（SPN）

该算法也采用非剥夺策略，对预计执行时间短的进程优先分派处理机。通常后来的短进程不抢先正在执行的进程。相比FCFS 算法，该算法可改善平均周转时间和平均带权周转时间，缩短进程的等待时间，提高系统的吞吐量。缺点是对长进程非常不利，可能长时间得不到执行，且未能依据进程的紧迫程度来划分执行的优先级，以及难以准确估计进程的执行时间，从而影响调度性能。

、多级队列调度算法 描述： 把就绪队列划分成几个单独的队列一般根据进程的某些特性如内存大小和进程类型永久性地把各个进程分别链入其中某一个队列中，每个队列都有自己的调度算法，此外在各个队列之间也要进行调度。通常采用固定优先级的抢占式调度，例如某系统中有5 个队列，各个队列的优先级自上而下降低，只有当前3 个队列中都为空的时候队列4 中的进程才可以运行，而当队列4 中的进程在运行时，如果队列1 中进入了一个就绪进程，则队列4 中的进程要立刻让出CPU 使用权。多级反馈队列法允许进程在各队列间移动，其基本思想是把具有不同CPU工作时间这一特性的进程区分开来，如果一个进程要使用很长的CPU 时间，则应把它移至较低级的队列中，这种方式把I/O 繁忙型和交互式进程放在较高优先级的队列中同样在低优先级队列中长时间等待的进程可以移到较高优先级队列中UNIX 系统采用的是多级反馈队列轮转法