进程调度算法模拟-

进程调度算法模拟

专业：计算机科学与技术 学号：120602105 姓名：黄凡

实验日期：2014年12月2日

一.算法综述

调度也称dispatcher，这是内核的主要职责之一就是决定该轮到哪个任务运行了多数实时内核是基于优先级调度算法的每个任务根据其重要程度的不同被赋予一定的优先级，基于优先级的调度法指CPU 总是让处在就绪态的优先级最高的任务先运行，然而究竟何时让高优先级任务掌握CPU 的使用权，有两种不同的情况这要看用的是什么类型的内核是非占先式还是占先式的内核一个良好的任务调度算法应该主要体现在以下几个方面： 1.公平保证每个进程得到合理的CPU 时间

2.高效使CPU 保持忙碌状态即总是有进程在CPU 上运行 3.响应时间使交互用户的响应时间尽可能短

4.周转时间使批处理用户等待输出的时间尽可能短 5.吞吐量使单位时间内处理的进程尽可能多

很显然在任何操作系统中这几个目标不可能同时达到所以不同的。 操作系统会在这几个方面中做出相应的取舍从而确定自己的调度算法，常用的处理机调度算法有： 先来先服务FCFS 短作业优先SJF 优先级

时间片轮转法 多级队列法 多级反馈队列法

先来先服务：FCFS 是最简单的CPU 调度算法，即按进程到来的先后次序进行调度，这样在系统中等待时间最长的进程被优先调度，而不管其所需运行时间的长短。

作业优先SJF 算法是指当CPU 可供使用时SJF 算法把CPU 分给需要运行时间最短的进程。

多级队列调度算法：把就绪队列划分成几个单独的队列一般根据进程的某些特性如内存大小和进程类型永久性地把各个进程分别链入其中某一个队列中，每个队列都有自己的调度算法，此外在各个队列之间也要进行调度。通常采用固定优先级的抢占式调度，例如某系统中有5 个队列，各个队列的优先级自上而下降低，只有当前3 个队列中都为空的时候队列4 中的进程才可以运行，而当队列4 中的进程在运行时，如果队列1 中进入了一个就绪进程，则队列4 中的进程要立刻让出CPU 使用权。多级反馈队列法允许进程在各队列间移动，其基本思想是把具有不同CPU工作时间这一特性的进程区分开来，如果一个进程要使用很长的CPU 时间，则应把它移至较低级的队列中，这种方式把I/O 繁忙型和交互式进程放在较高优先级的队列中同样在低优先级队列中长时间等待的进程可以移到较高优先级队列中UNIX 系统采用的是多级反馈队列轮转法。 时间片轮转调度法：round-robin scheduling

当两个或两个以上任务有同样优先级，内核允许一个任务运行事先确定的一段时间叫做时间额度quantum ，然后切换给另一个任务也叫做时间片调度time slicing ，内核在满足以下条件时把CPU 控制权交给下一个任务就绪态的任务， 当前任务已无事可做，当前任务在时间片还没结束时已经完成了。轮转法主要是为分时系统设计的，其中时间片是一个重要的参数不能取的过大或过小，通常为

10 至100ms 数量级，就绪队列可以看成是一个环形队列，CPU 调度程序轮流地把CPU 分给就绪队列中地每个进程，时间长度为一个时间片Linux 操作系统就是采用时间片轮转的调度算法。

二.算法分析

1.先到先服务算法

算法思想：按照进入就绪对列的先后顺序来分配处理机。FCFS采用非剥夺式调度方式，即一旦某个进程占有处理机，就一直运行下去，直到该进程完成其工作或等待某事件而不能继续执行时才释放处理机。

优缺点：利于长作业进程，而不利于短作业进程这是因为若一个长作业先到达系统，就会使许多短作业等待很长的时间，从而引起许多短作业用户的不满。有利于CPU繁忙型作业，不利于I/O，忙的作业。

现在操作系统中，已很少用该算法作为主要调度策略，尤其是在分时系统和实时系统中。但它常被结合在其它调度策略中使用。 2.短作业优先算法 算法思想：

优缺点：降低作业的平均等待时间，提高系统吞吐量。对长作业不利；未考虑作业的紧迫程度；对进程估计执行时间难以预测。 3.高优先权优先调度算法

为了考虑作业的紧迫程度，引入了最高优先权调度算法（FPF） 1) 优先权调度算法类型 a) 非抢占式优先权算法

基本原理：系统把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直到完成；或因发生某时间使该进程放弃处理机时，系统才可将处理机重新分配给另一优先权最高的进程。

适用：批处理系统，实时性要求不高的实时系统。 b) 抢占式优先权算法

基本原理：系统把处理机优先权最高的进程，使之执行。若在其执行期间，只要又出现另一个优先权更高的进程，则立即停止当前进程的执行，重新分配处理机给新来的优先权更高的进程。

适用：实时性要求高的实时系统，对性能要求高的批处理和分时系统。 2) 优先权类型 a) 静态优先权

静态优先权是在创建进程的时确定的，且在进程的整个运行期间保持不变。一般，利用某一范围内的整数来表示，如，0~7或0～255中的整数。 b) 动态优先权

是指在创建进程时确定的优先权，在进程的运行期间会发生变化。 4.时间片轮转法 算法思想：

系统将所有就绪进程按FCFS的原则，排成一个队列，依次调度，把CPU分配给队首进程，并令其执行一个时间片/CPU时间，通常为几个毫秒～几百毫秒。时间片用完后，该进程将被抢占并插入就绪队列末尾。

三.算法设计

1.先进先出算法流程图

开始 初始化所有PCB,使PCB按作业提交的先后顺序排队 调度队首的作业投入运行 计算并打印计算作业I的完成时间，运转时间和带权运转时间 更改时间T的值（T=T+作业i的运行时间） 等待队列为空 空计算这组作业的平均周转时间和平均带权周转时间 结束 2时间片转法算法流程图

开始 初始化PCB块，输入进程信息 按进程输入顺序插入到对列 就绪对列是否为空 空 完成 不空 运行时间片，执行首进程 运行进程已占用cpu时间已达到所需的时间 已完成 未完成进程完成，撤销该进程，并插到完成对列 把运行进程插入到队尾

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库进程调度算法模拟-在线全文阅读。