常用进程调度算法的分析与评价_进程调度算法简介

常用进程调度算法的分析与评价由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“进程调度算法简介”。

常用进程调度算法的分析与评价

（一）2009-10-31 22:48

进程调度是按照某种调度算法从就绪状态的进程中选择一个进程到处理机上运行。进程调度的两种方式 ：

(1)非抢占调度方式

在这种调度方式中，OS一旦把处理机分配给某个就绪状态的进程后，就让该进程一直执行下去，直至该进程完成或由于该进程等待某事件发生而被阻塞时，才把处理机分配给其他进程。

(2)抢占调度方式

在这种调度方式中，进程调度程序可根据某种原则停止正在执行的进程，将已分配给当前进程的处理机收回，重新分配给另一个处于就绪状态的进程。

抢占进程调度的原则：

（1）时间片原则：各进程按系统分配给的一个时间片运行，当该时间片用完或由于该进程等待某事件发生而被阻塞时，系统就停止该进程的执行而重新进行调度。

（2）优先级原则：每个进程均赋于一个调度优先级，通常一些重要和紧急的进程赋于较高的优先级。当一个新的紧迫进程到达时，或者一个优先级高的进程从阻塞状态变成就绪状态的时，如果该进程的优先级比当前进程的优先级高，OS就停止当前进程的执行，将处理机分配给该优先级高的进程，使之执行。

（3）短进程优先原则：当新到达的作业对应的进程比正在执行的作业对应进程的运行时间明显短时，系统剥夺当前进程的执行，而将处理机分配给新的短进程，使之优先执行。进程调度算法评价依据

进程调度性能的衡量方法可以分为定性和定量两种，在定性衡量方面，首先是调度的安全性。比如，一次进程调度是否可能引起数据结构的破坏等。这要求对调度时机的选择和保存CPU现场十分小心。另外，系统开销也是衡量进程调度的一个重要指标，由于调度程序的执行涉及到多个进程的上下文切换，如果调度策略过于繁琐和复杂，将会耗去较大的系统开销。这在用户进程调度系统调用较多的情况下，将会造成响应时间大幅度增加。

进程调度的定量评价包括CPU的利用率评价、进程在就绪队列中的等待时间与执行时间之比等。实际上，由于进程进入就绪队列的随机模型很难确定，而且进程上下文切换等也将影响进程的执行效率，从而对进程调度进行解析是很困难的，一般情况下，大多利用模拟或测试系统响应时间的方法来评价进程调度的性能。

常用进程调度算法的分析与评价

（二）2009-11-01 20:22

四种常用进程调度算法的分析与评价

3.1 先来先服务算法

3.1.1 算法思想

该算法思想是按照进入就绪队列的先后次序来分配处理机。FCFS采用非剥夺调度方式，即

一旦某个进程占有处理机，就一直运行下去，直到该进程完成其工作或因等待某一事件而不能继续执行时才释放处理机。

3.1.2 算法实现原理图

该算法实现原理图如图1所示。

说明：Ready表示就绪队列，Pi表示新进入队列的进程，Finish表示进程运行完毕退出。

3.1.3 算法分析与评价

① 该算法原理简单，易于实现。

② 各进程平等竞争。

③ 由于各进程执行的时间不一样，从而导致相对不公平现象的产生。

④ 该算法有利于长进程，不利于短进程。

⑤ 该算法很少用来作为主调度策略，常常用作辅助调度算法使用

3.2最高优先权优先调度算法

3.2.1 算法思想

该算法的基本思想是进程优先权高者优先调度，是一种最常用的进程调度算法。该算法的关键是如何确定优先数。通常确定优先数的方法有两种，即静态法和动态法。

静态优先权是在创建进程时确定的，其运行特征是优先数确定之后在整个进行运行期间不再改变。确定静态优先权的依据有进程的类型、进程所使用的资源、进程的估计运行时间等因素。进程所申请的资源越多，估计的运行时间越长，进程的优先权越低。进程类型不同，优先权也不同，如系统进程的优先权高于用户进程的优先权。

动态优先权是指在创建进程时，其运行特征是根据系统资源的使用情况和进程的当前特点确定一个优先权，在进程运行过程中再根据情况的变化调整优先权。动态优先权一般根据进程占有CPU时间的长短、进程等待CPU时间的长短等因素确定。占有处理机的时间越长，则优先权越低；等待时间越长，则优先权越高。

3.3.2 算法分析与评价

① 静态优先级调度算法实现较为简单，但不能反映系统以及进程在运行过程中发生的各种变化。而动态优先级法可以满足这个方面的需要。

② 动态优先级调度算法的性能一般介于时间片轮转算法和先来先服务算法之间。

常用进程调度算法的分析与评价

（三）2009-11-01 20:23

3.3时间片轮转调度算法

3.3.1 算法思想

该算法思想是使每个进程在就绪队列中的等待时间与享受服务的时间成比例。即将CPU的处理时间分成固定大小的时间片，如果在执行的一个进程把它分给它的时间片用完了，但任务还没有完成，则它也只能停止下来，释放它所占的CPU资源，然后排在相应的就绪队列的后面去。

3.3.2 算法实现原理图

该算法实现原理图如图2所示

说明：Ready表示就绪队列，Pi表示新进入队列的进程，Finish表示进程运行完毕退出。Not Finish表示分配给某进程的时间片已用完但任务还没有完成，从而插入到Ready队列尾部。

3.3.3 算法分析与评价

① 时间片的长度选择比较困难

时间片的长度选择比较困难是因为时间片长度的选择直接关系到系统开销和进程的响应时间。如果时间片长度过短→导致调度程序剥夺处理器的次数增加→进程的上下文切换的次数增加→系统的开销也加重；如果时间片长度过长，长到能使就绪队列中所需要执行时间最长的进程执行完

毕→轮转法就变成了FCFS算法→FCFS短处不足就显示出来了。

又因为CPU的整个执行时间＝各进程执行时间之和＋系统开销（各进程切换所花费的CPU时间之和，假定存储开销忽略不计）。即。因此，时间片的长短通常需要由以下因素确定：↙系统的响应时间。

↙就绪队列中的进程数。

↙进程的切换时间。

↙ 计算机的处理能力，计算机的速度越高，时间片就可越短。

② 时间片长度选择的动态性

以上仅仅作了静态分析，通常情况下，就绪队列里地进程个数是不断变化的。因此，每一次的调度都需要计算新一轮的时间片长度，不能用固定的时间片长度来进行所有进程的轮转执行。③ 该算法的扩充——多级反馈轮转法

在上面的算法中，未对就绪队列中的进程加以条件分析（即进入就绪队列的因素），由于进入就绪队列的原因不一样，要求占用处理机的紧急程度也不一样。主要因素有：↙分给该进程的时间片用完，但进程还未完成。

↙ 分给其时间片未用完，而发生了I/O等请求后由阻塞态转变成就绪态。

↙新的进程进入。

因此，根据紧急程度的不一样，建立多个就绪队列，同时赋予不同的的优先级，优先权高的就绪队列优先执行，同一就绪队列中，优先级相同，按照先来先服务进行调度，运行一个给定的时间片，如果没有执行完成则转入到相应的就绪队列中去（运行一次，优先级降低一个等级，等待一个时间片，则优先级升高一个等级）。其实现原理图如图3所示。

3.4 短进程优先调度算法

3.4.1 算法思想

该算法的基本思想是从就绪队列（内存）中选择一个估计运行时间最短的进程，将处理机分配给它。

3.4.2 算法分析与评价

① 该算法能有效降低作业的平均等待时间，提高系统吞吐量。

② 对长进程不利，甚至导致长期得不到处理。

③ 该算法完全未考虑进程的紧迫程度。

④ 进程的长短通常由某种策略估计提供，不能做到真正的短进程优先。

4结语

综述所述，本文从算法思想、算法的实现原理、算法的优缺点等几个方面对先来先服务算法、时间片轮转算法、最高优先权优先调度算法、短进程优先调度算法等四种进程调度算法进行详细地论述。（转自《计算机与信息技术》）