LINUX操作系统教程课件第四章幻灯片.pptVIP

* * 1、先来先服务算法（FCFS——First Come First Serve） 按照进程就绪的先后次序来调度进程。实现时可以按照进程就绪的先后次序排列就绪队列，最先就绪的排在队列头部，这样每次调度只要从就绪队列头部取一个进程即可。 先来先服务是一个非剥夺式调度算法。 该算法的优点是实现简单；缺点是没考虑进程的优先级。 2、短进程优先算法（SPF——Shortest Process First） 对短进程（其CPU周期短）优先的调度算法。 SPF算法对系统中占较大比例的短进程有利。 在调度时，调度程序从就绪队列中选择一个最短的进程（其下一个CPU周期最短），使之占有CPU执行一直到其完成或因等待某事件而主动放弃CPU为止。 短进程优先调度算法减少了平均周转时间和平均带权周转时间。它能有效地减少短进程的平均等待时间，从而提高了系统的吞吐量。 但是这种调度算法对短进程是照顾了，但对长进程却有可能产生很不良的后果。比如就绪队列中有一个长进程，若一直不断有比它短的进程进入就绪队列，则这个长进程可能相当长的时期内得不到调度。 另外，由于在把CPU分配给该进程前，它还未执行，故而其下一个CPU周期只是一个估计值，难免与真实的情况有出入，有时这种出入还很大。 3、时间片轮转算法（RR——Round Robin） 时间片轮转调度算法是分时系统中普遍采用的一种基本调度算法。它轮流调度就绪队列中的进程，每个进程执行一个时间片。 在系统中，就绪进程依照变为就绪状态的先后次序被排在就绪队列中，最先到的排在队列的首部。每次调度时，调度程序总是选择队首的那个进程，把CPU分配给它一小段时间，称为时间片。一般时间片以毫秒计，为几十或几百毫秒。当时间片用完时，若进程当前的CPU周期还未完成，则停止该进程的执行，将其插入就绪队列的尾部，等待下一次调度。然后调度程序又将CPU分配给就绪队列的下一个队首进程，也是一个时间片。 时间片到是进程调度的时机。但若当前进程不到一个时间片就执行完了或阻塞了，那自然也要重新开始调度。 时间片的选择的原则，一般就是使得大部分命令能在一个时间片内完成。 * 3、优先权算法（HPF——Highest Priority First） 选择就绪队列中优先权最高的进程占有CPU执行。系统中的每个进程被赋予一个优先权。对于那些重要的或紧急的进程常被赋予一个高优先权，这样就可以让这些进程尽快地被调度执行。在这种算法中，就绪队列是按进程优先权来排序的。 这种算法又可细分为两种方式： （1）非剥夺式优先权算法：在这种方式下，调度程序一旦将CPU分配给一个优先权最高的进程后，该进程就一直执行下去，直到走完它的CPU周期期间不能被剥夺。 （2）剥夺式优先权算法：在这种方式下，调度程序将CPU分配给一个优先权最高的进程使之占有CPU执行后，一旦出现了一个新的优先权更高的就绪进程时，调度程序就被用来停止当前进程的执行，而将CPU分配给现在优先权最高的进程。剥夺式优先权算法是一个彻底的优先权算法，它能保证高优先权的进程总能被及时调度。 这种算法的调度依据就是进程的优先权，优先权的实现一般也有两种： （1）静态优先权：静态优先权是在进程建立时就确定的，并且在进程的整个生命周期内保持不变。静态优先权的优点是简单，开销较小；而其缺点是公平性差，可能造成低优先级进程长期等待。 （2）动态优先权：进程创建时所赋予的初始优先权可以在进程运行期间进程本身的状况和系统环境的变化而不断调节。 4、多级反馈队列算法 多级反馈队列调度算法就是一种综合了FCFS、RR、HPF的调度算法，它可以满足各类进程的需要。它的基本思路如下： （1）系统中设置多个就绪队列，并赋予各个队列不同的优先权。这样就根据优先权将进程分成几个级别。第一个队列的优先权最高，第二个次之，第n个 队列的优先权最低。 （2）赋予各个就绪队列不同的时间片qi(i=1,2,…,n)，并且q1q2…qn。一般取qi+1=2qi。 （3）当一个进程创建后，首先将其放至第一个就绪队列的末尾，按FCFS算法进行调度，但只执行一个时间片。当轮到该进程执行时，若能在一个时间片内完成便罢；否则，当时间片到时还未完成，则调度程序就停止该进程的执行，将其放至第二个队列的末尾。若它在第二个队列中若执行一个时间片还未完成，则再将其放至第三个队列的末尾。依此类推，直到将该进程放至第n个就绪队列的末尾。第n个就绪队列中采取的时时间片轮转调度算法，一个时间片用完后，若