常用进程调度算法的模拟实现

2015-07-02黄祖贤

宿州学院学报 2015年8期

关键词：优先权队列进程

黄祖贤

中南大学信息科学与工程学院，湖南长沙，410083

常用进程调度算法的模拟实现

黄祖贤

中南大学信息科学与工程学院，湖南长沙，410083

在多道程序系统中，有多个进程存在于主存中且其数目一般多于处理机数目，这会导致它们互相争夺处理机。为了解决这一问题，需要采取合适的进程调度策略，常见的进程调度方法有时间片轮转算法、最高优先权优先算法和短作业(进程)优先算法等。采用Java语言用良好清晰的界面对上述三种进程调度算法进行模拟实现，加深对进程调度策略的理解，有利于进一步的研究与应用。

进程管理;进程调度;时间片轮转;优先权;短作业优先；Java

1 问题的提出

操作系统中，进程管理十分重要。如何有效管理、合理调度进程资源，对提升系统性能，提高进程的运行效率显得尤为重要。进程调度的核心问题就是采用什么样的算法把处理机分配给进程，好的算法可以提高资源利用率，减少处理机的空闲时间，避免有些作业或进程长期得不到响应的情况发生[1]。本文介绍了进程调度中的一些基本策略，并基于Java语言对其进行了实现。

2 进程调度算法

在操作系统中，调度的实质是一种资源分配。调度算法是指根据系统的资源分配策略所规定的资源分配算法[2]。对于不同的系统和系统目标，通常采用不同的调度算法[3]。进程调度是系统内部的低级调度[4]。常见的进程调度算法有先来先服务算法、最高优先权优先算法、时间片轮转算法、短进程(作业)优先调度算法等。

3 进程调度的模拟设计

3.1 设计思想

在本设计中，用良好清晰的界面向用户展示了进程调度算法中的时间片轮转算法、最高优先权优先算法和短作业优先调度算法。在最终实现的成果中，用户可输入需要模拟的进程名，到达时间和进程的执行时间、优先级、需求内存大小等信息，并且选择需要演示的算法，算法演示界面将会显示进程调度的运行结果。通过此进程调度模拟程序，可以对上述的三种算法有进一步的了解。

3.2 调度算法

设计程序模拟三种进程调度算法：时间片轮转算法、最高优先级优先算法(非抢占式)和短作业(进程)优先算法。

3.2.1 时间片轮转算法

将所有的就绪进程按照优先权优先、先来先服务的原则排成一个队列，每次调度时把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，调度程序将停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。

3.2.2 最高优先级优先算法(非抢占式)

在就绪进程队列中选取优先级最高的执行，相同优先级按照先来先服务原则进行选取，进程开始后不可被抢占。

3.2.3 短作业(进程)优先算法

从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成。

3.3 功能模块

3.3.1 进程状态转换关系

进程状态的转换通常有以下几种情况(图1)：(1)创建进程→就绪状态；(2)就绪→执行：就绪进程被进程调度程序选中，投入到CPU中执行；(3)执行→就绪：在分时系统中，执行状态进程使用的时间片已经用完时，退出CPU而进入就绪态，等待下次被进程调度选中进入CPU执行；(4)执行状态→进程结束。

图1 进程状态转换关系图

3.3.2 进程(Process)信息

主要负责保存进程的基本信息，如进程名、进程要求运行时间、进程到达就绪队列时间和进程需求内存大小等。

3.3.3 进程控制块(PCB)信息

主要负责保存包括进程信息的进程调度的基本信息，如进程优先级、进程开始运行时间、进程运行结束时间和已经运行的时间等。提供外部状态设置和读取接口。

3.3.4 进程队列(SchduleTask)类

主要负责保存进程创建队列信息、完成队列信息和进程总数。提供获取队列数据和调度进程的接口。

3.3.5 调度(Algorithm)类

(1)向就绪队列添加新创建进程；(2)从就绪队列取相应进程执行；(3)执行完进程放入完成队列；(4)提供获取执行状态的外部接口，即各个队列数据的获取。

3.3.6 视图类

(1)提供用户操作接口(调度策略选择、进程创建)；(2)显示各队列、进程状态信息；(3)创建进程调度类线程，调用调度类的接口。

3.4 类与算法设计

依据3.3.1节进程状态的转换关系，可以制定进程调度框架，具体实现流程如下图2所示。

图2 进程调度框架

3.4.1 类图

本设计采用Java语言对三种进程调度算法进行模拟与实现。利用Java语言面向对象的特点，结合3.3节功能模块的介绍与分析，设计类结构关系如图3所示，其中SPF、FPF、RR分别是短作业优先算法类、最高优先权算法类和时间片轮转算法类。

图3 类结构设计

3.4.2 算法设计

(1)allArrivedProcess()函数。allArrivedProcess()函数返回所有已经到达的进程的集合，并将其加入就绪队列，它是抽象类Algorithm定义的方法。该函数只有一个参数，是PCB进程队列(用户初始化的进程队列_comingQueue)。该类的成员变量_totalRunTime记录系统当前进程调度的总运行时间，则参数PCB进程队列中的进程加入到达(就绪)队列有以下两种情况：①若存在到达时间小于_totalRunTime的进程，则将这些进程全部加入到到达队列当中；②如果所有的进程的到达时间都比_totalRunTime时间大，则选取与_totalRunTime绝对值相差最小的进程的集合加入到达队列。若有多个进程的到达时间相同，则将其全部添加到到达队列。将上述到达进程添加至就绪队列，并将该队列从参数队列中移除。

(2)schdule()函数。schdule()函数调度所有进程，它同样是抽象类Algorithm定义的方法。该函数只有一个参数，是SchduleTask类的对象，依据该对象中记录的_comingQueue和_finishQueue跟踪系统进行进程调度的情况。

(3)run()函数。run()函数执行被调度的进程，它是抽象类Algorithm定义的抽象方法。该方法与使用的调度算法有关，在其算法子类RR、SPF、FPF中提供具体实现。

(4)chooseProcess()函数。chooseProcess()函数从就绪队列中选择一个进程调度执行，它同样是抽象类Algorithm定义的抽象方法，它只有一个参数，是PCB进程队列(就绪队列)。该方法与使用的调度算法有关，在其算法子类RR、SPF、FPF中提供具体实现。时间片轮转算法(RR)中，总是选择就绪队列中的第一个进程；最高优先权优先算法(FPF)中，总是选择就绪队列中优先权最高的进程；短作业(进程)优先算法(SPF)中，总是选择就绪队列中作业(进程)要求运行时间最短的作业(进程)。

3.5 模拟结果

采用Java语言对三种进程调度算法进行模拟的结果如图4、图5、图6、图7所示。其中，图4显示的是用户初始化的进程信息列表，用户需要自定义进程名、进程到达时间、进程运行时间和进程优先级等。图5显示的是选择时间片轮转算法进行进程调度的运行结果，展示了在时间片轮转算法下，进程调度的开始时间、完成时间、周转时间以及带权周转时间等信息。图6、图7分别显示了在最高优先权优先算法和短作业优先算法下，进程调度的开始时间、完成时间、周转时间以及带权周转时间等信息。