常见进程调度算法

2/22/2017来源:ASP.NET技巧人气:2175

调度算法是指:根据系统的资源分配策略所规定的资源分配算法。 调度也称dispatcher 这是内核的主要职责之一就是决定该轮到哪个任务运行了多数实时内核是基于优先级调度算法的每个任务根据其重要程度的不同被赋予一定的优先级基于优先级的调度法指CPU 总是让处在就绪态的优先级最高的任务先运行然而究竟何时让高优先级任务掌握CPU 的使用权有两种不同的情况这要看用的是什么类型的内核是非占先式还是占先式的内核一个良好的任务调度算法应该主要体现在以下几个方面   公平保证每个进程得到合理的CPU 时间   高效使CPU 保持忙碌状态即总是有进程在CPU 上运行   响应时间使交互用户的响应时间尽可能短   周转时间使批处理用户等待输出的时间尽可能短   吞吐量使单位时间内处理的进程尽可能多 很显然在任何操作系统中这几个目标不可能同时达到所以不同的操作系统会在这几个方面中做出相应的取舍从而确定自己的调度算法,常用的处理机调度算法有:   1、先来先服务FCFS   2、短作业优先SJF   3、优先级   4、时间片轮转法   5、多级队列法   6、多级反馈队列法 一、先来先服务和短作业(进程)优先调度算法   1. 先来先服务调度算法。先来先服务(FCFS)调度算法是一种最简单的调度算法,该算法既可用于作业调度, 也可用于进程调度。FCFS算法比较有利于长作业(进程),而不利于短作业(进程)。由此可知,本算法适合于CPU繁忙型作业, 而不利于I/O繁忙型的作业(进程)。   2. 短作业(进程)优先调度算法。短作业(进程)优先调度算法(SJ/PF)是指对短作业或短进程优先调度的算法,该算法既可用于作业调度, 也可用于进程调度。但其对长作业不利;不能保证紧迫性作业(进程)被及时处理;作业的长短只是被估算出来的。 二、高优先权优先调度算法   1. 优先权调度算法的类型。为了照顾紧迫性作业,使之进入系统后便获得优先处理,引入了最高优先权优先(FPF)调度算法。 此算法常被用在批处理系统中,作为作业调度算法,也作为多种操作系统中的进程调度,还可以用于实时系统中。当其用于作业调度, 将后备队列中若干个优先权最高的作业装入内存。当其用于进程调度时,把处理机分配给就绪队列中优先权最高的进程,此时, 又可以进一步把该算法分成以下两种:     1)非抢占式优先权算法     2)抢占式优先权调度算法(高性能计算机操作系统)   2. 优先权类型 。对于最高优先权优先调度算法,其核心在于:它是使用静态优先权还是动态优先权, 以及如何确定进程的优先权。   3. 高响应比优先调度算法     为了弥补短作业优先算法的不足,我们引入动态优先权,使作业的优先等级随着等待时间的增加而以速率a提高。 该优先权变化规律可描述为:优先权=(等待时间+要求服务时间)/要求服务时间;即 =(响应时间)/要求服务时间 三、基于时间片的轮转调度算法   1. 时间片轮转法。时间片轮转法一般用于进程调度,每次调度,把CPU分配队首进程,并令其执行一个时间片。 当执行的时间片用完时,由一个记时器发出一个时钟中断请求,该进程被停止,并被送往就绪队列末尾;依次循环。   2. 多级反馈队列调度算法 多级反馈队列调度算法多级反馈队列调度算法,不必事先知道各种进程所需要执行的时间,它是目前被公认的一种较好的进程调度算法。 其实施过程如下:     1) 设置多个就绪队列,并为各个队列赋予不同的优先级。在优先权越高的队列中, 为每个进程所规定的执行时间片就越小。     2) 当一个新进程进入内存后,首先放入第一队列的末尾,按FCFS原则排队等候调度。 如果他能在一个时间片中完成,便可撤离;如果未完成,就转入第二队列的末尾,在同样等待调度…… 如此下去,当一个长作业(进程)从第一队列依次将到第n队列(最后队列)后,便按第n队列时间片轮转运行。     3) 仅当第一队列空闲时,调度程序才调度第二队列中的进程运行;仅当第1到第(i-1)队列空时, 才会调度第i队列中的进程运行,并执行相应的时间片轮转。     4) 如果处理机正在处理第i队列中某进程,又有新进程进入优先权较高的队列, 则此新队列抢占正在运行的处理机,并把正在运行的进程放在第i队列的队尾。 四、多级队列调度算法:把就绪队列划分成几个单独的队列一般根据进程的某些特性如内存大小和进程类型永久性地把各个进程分别链入其中某一个队列中,每个队列都有自己的调度算法,此外在各个队列之间也要进行调度。通常采用固定优先级的抢占式调度,例如某系统中有5 个队列,各个队列的优先级自上而下降低,只有当前3 个队列中都为空的时候队列4 中的进程才可以运行,而当队列4 中的进程在运行时,如果队列1 中进入了一个就绪进程,则队列4 中的进程要立刻让出CPU 使用权。多级反馈队列法允许进程在各队列间移动,其基本思想是把具有不同CPU工作时间这一特性的进程区分开来,如果一个进程要使用很长的CPU 时间,则应把它移至较低级的队列中,这种方式把I/O 繁忙型和交互式进程放在较高优先级的队列中同样在低优先级队列中长时间等待的进程可以移到较高优先级队列中UNIX 系统采用的是多级反馈队列轮转法。