1. 先来先服务调度算法：先来先服务(FCFS)调度算法是⼀种最简单的调度算法，该算法既可⽤于作业调度，也可⽤于进程调度。当在作 业调度中采⽤该算法时，每次调度都是从后备作业队列中选择⼀个或多个最先进⼊该队列的作业，将它们调⼊内存，为它们分配资源、创建进程，然后放⼊就绪队列。在进程调度中采⽤FCFS算法时，则每次调度是从就绪队列中选择⼀个最先进⼊该队列的进程，为之分配处理机，使之投⼊运⾏。该进程⼀直运⾏到完成或发⽣某事件⽽阻塞后才放弃处理机。开元释教录
2. 短作业(进程)优先调度算法：短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别⽤于作业调度
和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择⼀个或若⼲个估计运⾏时间最短的作业，将它们调⼊内存运⾏。⽽短进程优先(SPF)调度算法则是从就绪队列中选出⼀个估计运⾏时间最短的进程，将处理机分配给它，使它⽴即执⾏并⼀直执⾏到完成，或发⽣某事件⽽被阻塞放弃处理机时再重新调度。
3. ⾼优先权优先调度算法：为了照顾紧迫型作业，使之在进⼊系统后便获得优先处理，引⼊了最⾼优先权优先(FPF)调度算法。此算法常
被⽤于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可⽤于实时系统中。当把该算法⽤于作业调度时，系统将从后备队列中选择若⼲个优先权最⾼的作业装⼊内存。当⽤于进程调度时，该算法是把处理机分配给就绪队列中优先权最⾼的进程，这时，⼜可进⼀步把该算法分成如下两种。
3.1) ⾮抢占式优先权算法：在这种⽅式下，系统⼀旦把处理机分配给就绪队列中优先权最⾼的进程后，该进程便⼀直执⾏下去，直
⾄完成；或因发⽣某事件使该进程放弃处理机时，系统⽅可再将处理机重新分配给另⼀优先权最⾼的进程。这种调度算法主要⽤于批处理系统中；也可⽤于某些对实时性要求不严的实时系统中。
3.2) 抢占式优先权调度算法：在这种⽅式下，系统同样是把处理机分配给优先权最⾼的进程，使之执⾏。但在其执⾏期间，只要⼜
出现了另⼀个其优先权更⾼的进程，进程调度程序就⽴即停⽌当前进程(原优先权最⾼的进程)的执⾏，重新将处理机分配给新到的优先权最⾼的进程。因此，在采⽤这种调度算法时，是每当系统中出现⼀个新的就绪进程i 时，就将其优先权Pi与正在执⾏的进程j 的优先权Pj进⾏⽐较。如果Pi≤Pj，原进程Pj便继续执⾏；但如果是Pi>Pj，则⽴即停⽌Pj的执⾏，做进程切换，使i 进程投⼊执⾏。显然，这种抢占式的优先权调度算法能更好地满⾜紧迫作业的要求，故⽽常⽤于要求⽐较严格的实时系统中，
南通市第三中学以及对性能要求较⾼的批处理和分时系统中。
什么是宪法
3.3)容易出现优先级倒置现象：优先级反转是指⼀个低优先级的任务持有⼀个被⾼优先级任务所需要的共享资源。⾼优先任务由于因资源缺乏⽽处于受阻状态，⼀直等到低优先级任务释放资源为⽌。⽽低优先级获得的CPU时间少，如果此时有优先级处于两者之间的任务，并且不需要那个共享资源，则该中优先级的任务反⽽超过这两个任务⽽获得CPU时间。如果⾼优先级等待资源时不是阻塞等待，⽽是忙循环，则可能永远⽆法获得资源，因为此时低优先级进程⽆法与⾼优先级进程争夺CPU时间，从⽽⽆法执⾏，进⽽⽆法释放资源，造成的后果就是⾼优先级任务⽆法获得资源⽽继续推进。
3.4)优先级反转案例解释：不同优先级线程对共享资源的访问的同步机制。优先级为⾼和低的线程tall和线程low需要访问共享资
源，优先级为中等的线程mid不访问该共享资源。当low正在访问共享资源时，tall等待该共享资源的互斥锁，但是此时low被mid抢先了，导致mid运⾏tall阻塞。即优先级低的线程mid运⾏，优先级⾼的tall被阻塞。
3.5)优先级倒置解决⽅案：
(3.5.1）设置优先级上限，给临界区⼀个⾼优先级，进⼊临界区的进程都将获得这个⾼优先级，如果其他试图进⼊临界区的进程的
优先级都低于这个⾼优先级，那么优先级反转就不会发⽣。
（3.5.2）优先级继承，当⼀个⾼优先级进程等待⼀个低优先级进程持有的资源时，低优先级进程将暂时获得⾼优先级进程的优先级别，在释放共享资源后，低优先级进程回到原来的优先级别。嵌⼊式系统VxWorks就是采⽤这种策略。
这⾥还有⼀个⼋卦，1997年的美国的⽕星探测器（使⽤的就是vxworks)就遇到⼀个优先级反转问题引起的故障。简单说下，⽕星探测器有⼀个信息总线，有⼀个⾼优先级的总线任务负责总线数据的存取，访问总线都需要通过⼀个互斥锁（共享资源出现了）；还有⼀个低优先级的，运⾏不是很频繁的⽓象搜集任务，它需要对总线写数据，也就同样需要访问互斥锁；最后还有⼀个中优先级的通信任务，它的运⾏时间⽐较长。平常这个系统运⾏毫⽆问题，但是有⼀天，在⽓象任务获得互斥锁往总线写数据的时候，⼀个中断发⽣导致通信任务被调度就绪，通信任务抢占了低优先级的⽓象任务，⽽⽆巧不成书的是，此时⾼优先级的总线任务正在等待⽓象任务写完数据归还互斥锁，但是由于通信任务抢占了CPU并且运⾏时间⽐较长，导致⽓象任务得不到CPU时间也⽆法释放互斥锁，本来是⾼优先级的总线任务也⽆法执⾏，总线任务⽆法及时执⾏的后果被探路者认为是⼀个严重错误，最后就是整个系统被重启。Vxworks允许优先级继承，然⽽遗憾的⼯程师们将这个选项关闭了。
（3.5.3）第三种⽅法就是临界区禁⽌中断，通过禁⽌中断来保护临界区，采⽤此种策略的系统只有两种优先级：可抢占优先级和中断禁⽌优先级。前者为⼀般进程运⾏时的优先级，后者为运⾏于临界区的优先级。⽕星探路者正是由于在临界区中运⾏的⽓象任务被中断发⽣的通信任务所抢占才导致故障，如果有临界区的禁⽌中断保护，此⼀问题也不会发⽣。
4、⾼响应⽐优先调度算法：在批处理系统中，短作业优先算法是⼀种⽐较好的算法，其主要的不⾜之处是长作业的运⾏得不到保证。如果我们能为每个作业引⼊前⾯所述的动态优先权，并使作业的优先级随着等待时间的增加⽽以速率a 提⾼，则长作业在等待⼀定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为：
在利⽤该算法时，每要进⾏调度之前，都须先做响应⽐的计算，这会增加系统开销。
5、时间⽚轮转法：在早期的时间⽚轮转法中，系统将所有的就绪进程按先来先服务的原则排成⼀个队列，每次调度时，把CPU 分配给队⾸进程，并令其执⾏⼀个时间⽚。时间⽚的⼤⼩从⼏ms 到⼏百ms。当执⾏的时间⽚⽤完时，由⼀个计时器发出时钟中断请求，调度程序便据此信号来停⽌该进程的执⾏，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队⾸进程，同时也让它
执⾏⼀个时间⽚。这样就可以保证就绪队列中的所有进程在⼀给定的时间内均能获得⼀时间⽚的处理机执⾏时间。换⾔之，系统能在给定的时间内响应所有⽤户的请求。
6、多级反馈队列调度算法：前⾯介绍的各种⽤作进程调度的算法都有⼀定的局限性。如短进程优先的调度算法，仅照顾了短进程⽽忽略了长进程，⽽且如果并未指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将⽆法使⽤。⽽多级反馈队列调度算法则不必事先知道各种进程所需的执⾏时间，⽽且还可以满⾜各种类型进程的需要，因⽽它是⽬前被公认的⼀种较好的进程调度算法。在采⽤多级反馈队列调度算法的系统中，调度算法的实施过程如下所述。
(1) 应设置多个就绪队列，并为各个队列赋予不同的优先级。第⼀个队列的优先级最⾼，第⼆个队列次之，其余各队列的优先权逐个降
低。该算法赋予各个队列中进程执⾏时间⽚的⼤⼩也各不相同，在优先权愈⾼的队列中，为每个进程所规定的执⾏时间⽚就愈⼩。例如，第⼆个队列的时间⽚要⽐第⼀个队列的时间⽚长⼀倍，……，第i+1个队列的时间⽚要⽐第i个队列的时间⽚长⼀倍。
(2)当⼀个新进程进⼊内存后，⾸先将它放⼊第⼀队列的末尾，按FCFS原则排队等待调度。当轮到该进程执⾏时，如它能在该时间⽚内
完成，便可准备撤离系统；如果它在⼀个时间⽚结束时尚未完成，调度程序便将该进程转⼊第⼆队列的末尾，再同样地按FCFS原则等待调度执⾏；如果它在第⼆队列中运⾏⼀个时间⽚后仍未完成，再依次将它放⼊第三队列，……，如此下去，当⼀个长作业(进程)从第⼀队列依次降到第n队列后，在第n 队列便采取按时间⽚轮转的⽅式运⾏。
(3) 仅当第⼀队列空闲时，调度程序才调度第⼆队列中的进程运⾏；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运⾏。如果
处理机正在第i队列中为某进程服务时，⼜有新进程进⼊优先权较⾼的队列(第1～(i-1)中的任何⼀个队列)，则此时新进程将抢占正在运⾏进程的处理机，即由调度程序把正在运⾏的进程放回到第i队列的末尾，把处理机分配给新到的⾼优先权进程。
批处理系统、分时系统和实时系统中，各采⽤哪⼏种进程（作业）调度算法？
批处理系统常⽤调度算法：
猎德小学①、先来先服务：
②、最短作业优先
③、最短剩余时间优先
④、响应⽐最⾼者优先
分时系统调度算法：
①、轮转调度
②、优先级调度
③、多级队列调度
④、调度
实时系统调度算法：
①、单⽐率调度
②、限期调度
孔子文学③、最少裕度法
华夏心理网
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议