操作系统中有很多调度算法，有的适合作业调度，有的适合进程调度，有的两者都适合。下面介绍几种常用的调度算法。先来先服务（FCFS）调度算法FCFS调度算法是最简单的调度算法，既可以用于作业调度，也可以用于进程调度。在作业调度中，算法每次从备份作业队列中选择一个或几个进入队列的作业，将其调入内存，分配必要的资源，创建进程，放入就绪队列。在进程调度中，FCFS调度算法每次从就绪队列中选择第一个进入队列的进程，将处理器分配给它，使其投入运行，直到完成或由于某种原因阻塞，才释放处理器。下面举例说明FCFS调度算法的性能。假设系统中有4个作业，它们的提交时间分别为8、8.4、8.8、9，运行时间依次为2、1、0.5、0.2，系统采用FCFS调度算法，平均等待时间,average周转时间和平均加权周转时间见表2-3。平均等待时间t=(0+1.6+2.2+2.5)/4=1.575平均周转时间T=(2+2.6+2.7+2.7)/4=2.5平均加权周转时间W=(1+2.6+5.M13.5)/4=5.625FCFS调度算法是不可分割的算法。表面上看对所有作业都是公平的，但是如果一个长作业先到达系统，很多短作业会等待很长时间，所以不能作为分时系统和实时系统的主要调度策略。时间系统。但它经常与其他调度策略结合使用。例如，在一个使用优先级作为调度策略的系统中，多个具有相同优先级的进程往往会按照FCFS原则进行处理。FCFS调度算法的特点是算法简单，但效率低；有利于长作业，不利于短作业（对比SJF和高响应率）；它有利于CPU繁忙的作业，但不利于I/O繁忙的作业。短作业优先（SJF）调度算法短作业（进程）优先级调度算法是指优先调度短作业（进程）的算法。短作业优先（SJF）调度算法是从备份队列中选择一个或多个估计运行时间最短的作业，调入内存中运行。短进程优先级（shortprocesspriority，SPF）调度算法从就绪队列中选择一个估计运行时间最短的进程，为其分配一个处理器，并立即执行，直到完成或被事件机阻塞后释放该进程。例如，考虑表2-3中给出的一组作业。如果系统采用短作业优先级调度算法，其平均等待时间、平均周转时间、平均加权周转时间如表2-4所示。平均等待时间t=(0+2.3+1.4+1)/4=1.175平均周转时间T=(2+3.3+1.9+1.2)/4=2.1平均加权周转时间W=(1+3.3+3.8+6)/4=3.525SJF调度算法也有不可忽视的缺点：该算法不适用于长作业。从表2-3和表2-4可以看出，SJF调度算法中长作业的周转时间会增加。更严重的是，如果一个长作业进入了系统的备份队列，由于调度器总是优先处理那些短作业（即使是后来进来的作业），会导致长作业长时间得不到调度（“饥饿”）现象，注意区分“死锁”。后者是系统循环等待，前者是调度策略问题）。该算法根本没有考虑作业的紧急性，因此不能保证紧急作业会被及时处理。由于作业的长度只是根据用户提供的预估执行时间来确定的，而用户可能有意无意地缩短了作业的预估运行时间，因此该算法可能无法真正做到short-job-first调度。请注意，SJF调度算法的平均等待时间和平均周转时间最少。优先级调度算法优先级调度算法也称为优先级调度算法。该算法既可用于作业调度，也可用于进程调度。该算法中的优先级用来描述作业操作的紧急程度。在作业调度中，优先级调度算法每次从备份作业队列中选择一个或多个优先级最高的作业，将其调入内存，分配必要的资源，创建进程，放入就绪队列。在进程调度中，优先级调度算法每次从就绪队列中选择优先级最高的进程，为其分配一个处理器，并投入运行。根据新的更高优先级进程是否可以抢占正在执行的进程，调度算法可以分为：非抢占式优先级调度算法。当一个进程在处理器上运行时，即使有更重要或更紧急的进程进入就绪队列，正在运行的进程也会继续运行，直到由于自身原因（任务完成或等待事件）主动放弃处理器为止将处理者分配给更重要或更紧急的流程。抢占式优先级调度算法。当一个进程正在处理器上运行时，如果有更重要或更紧急的进程进入就绪队列，则正在运行的进程将立即挂起，处理器将分配给更重要或更紧急的进程。根据进程创建后优先级是否可以改变，进程优先级可以分为以下两种类型：静态优先级。优先级在创建进程时确定，并在进程的整个生命周期中保持不变。确定静态优先级的主要依据是进程类型、进程的资源需求和用户需求。动态优先级。在运行过程中，根据进程情况的变化动态调整优先级。动态调整优先级的主要依据是进程占用CPU时间的长短和就绪进程等待CPU的时间长短。高响应比优先调度算法高响应比优先调度算法主要用于作业调度。该算法是FCFS调度算法和SJF调度算法的综合平衡，同时考虑了每个作业的等待时间和估计运行时间。在每次作业调度中，首先计算备份作业队列中每个作业的响应率，选择响应率最好的作业投入运行。响应率的变化规律可以描述为：根据公式：当作业的等待时间相同时，需要服务时间越短，响应率越高，有利于短作业.当所需服务时间相同时，作业的响应率由其等待时间决定。等待时间越长，响应率越高，实现先到先得。对于长作业，作业的响应率可以随着等待时间的增加而提高。当等待时间足够长时，可以将响应率提高到一个较高的水平，这样也可以获得处理器。克服饥饿状态，兼顾长期作业。时间片循环调度算法时间片循环调度算法主要适用于分时系统。在该算法中，系统将所有就绪进程按照到达时间的先后顺序排列到一个队列中，进程调度器总是选择就绪队列中的第一个进程执行，即先来先服务的原则，但它只能跑一个时间片，比如100ms。使用一个时间片后，即使进程还没有完成它的操作，它也必须释放（剥夺）处理器给下一个就绪进程，被剥夺的进程回到就绪队列的尾部重新排队，等待另一个跑步。在时间片循环调度算法中，时间片的大小对系统性能影响很大。如果时间片足够大，所有进程都可以在一个时间片内执行，则时间片循环调度算法退化为先来先服务调度算法。如果时间片很小，处理器会过于频繁地在进程之间切换，这会增加处理器的开销，减少实际用于运行用户进程的时间。Therefore,thesizeofthetimesliceshouldbeselectedappropriately.时间片的长短通常由以下因素决定：系统的响应时间、就绪队列中的进程数、系统的处理能力。多级反馈队列调度算法（结合前面算法的优点）多级反馈队列调度算法是时间片循环调度算法和优先级调度算法的综合和发展，如图2-5所示。通过动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾各种系统目标。例如，照顾短流程以提高系统吞吐量并缩短平均周转时间；照顾I/O类型的进程，以获得更好的I/O设备利用率并缩短响应时间；同时，不需要提前预估流程的执行时间。图2-5多级反馈队列调度算法多级反馈队列调度算法的实现思路如下：1.设置多个就绪队列，为每个队列分配不同的优先级。一级队列优先级为***，二级队列次之，其余队列优先级依次递减。2、分配给每个队列中的进程的执行时间片的大小也不一样。在优先级越高的队列中，每个进程的运行时间片越小。比如二级队列的时间片是一级队列的两倍，...第i+1级队列的时间片是i-的两倍第级队列。3、当有新进程进入内存时，首先放在一级队列的尾部，按照FCFS原则等待调度。轮到进程执行时，如果能在时间片内完成，就可以准备退出系统；如果一个时间片末还没有完成，调度器会将进程转移到二级队列的末尾，然后按照FCFS原则等待调度执行；如果在二级队列运行一个时间片后还没有完成，则同理放入三级队列……以此类推，当一个长进程从第一级队列开始后依次降级到第n级队列，第n级队列按照时间片轮换的方式运行。4、只有一级队列为空时，调度器才会调度二级队列中的进程运行；只有当第~(i-1)级队列全部为空时，才会调度第i级队列中的进程运行。如果处理器正在执行i级队列中的进程，有新进程进入优先级更高的队列（1st~(i-1)中的任意队列），则新进程将抢占当前进程。正在运行的进程的处理器，即调度器将正在运行的进程放回第i个队列的尾部，并将处理器分配给新到的更高优先级的进程。多级反馈队列的优点是：终端类型作业用户：优先处理短作业。短批作业用户：更快的周转时间。longbatchjob用户：通过前面的队列部分执行，不会长时间未处理。
