模拟进程调度功能的设计与实现操作系统课程设计(JAVA版本)

admin管理员组

文章数量:1532325

2024年5月24日发(作者：)

操作系统课程设计

--进程调度子系统模拟实现

一、 设计内容及意义

1. 课程设计内容

使用java语言或C++语言编程实现模拟操作系统进程调度子系统的基本功能；实现

先来先服务、时间片轮转、多级反馈轮转法对进程进行的调度过程；掌握各个调度算法的

特点。

2. 该课程设计意义

➢ 理解进程调度的概念

➢ 深入了解进程控制块的功能、进程的创建、删除以及进程各个状态间的转换过程

➢ 从实用的角度对《数据结构》课程内容进行更深入理解和更熟练的应用

➢ 进一步练习对Java及C++语言的熟练使用

二、 设计方案

1. 硬件环境

1 / 45

PC一台

2. 开发语言及工具

➢ 操作系统：MS windows XP

➢ C++版：Visual Studio 2008 + MFC

➢ Java版：Eclipse 3.4 + Java Swing

3. 设计思路

➢ 系统设备表用于存取调度过程中进程可申请的资源

➢ 进程控制块主要负责具体进程信息的保存

➢ 等待队列、就绪队列、完成队列用于保存执行过程的状态信息

➢ 进程调度进程（类、线程）在就绪队列与等待队列之间进行调度

➢ 主界面显示调度过程的三个队列的状态信息

➢ 用户创建进程放入就绪队列等待调度

三、 功能模块设计

2 / 45

1. 进程状态转换

等待

创建进程

就绪执行进程结束

2. PCB信息

➢ 主要负责保存各进程基本信息

➢ 提供外部状态设置和读取接口

3. 系统设备类

➢ 系统设备的基本信息

➢ 设备状态设置、读取接口

4. 调度类

➢ 向就绪队列添加新创建进程

➢ 从就绪队列取相应进程执行

3 / 45

➢ 将执行阻塞进程放入等待队列

➢ 检测系统设备表，分配、释放设备、唤醒等待进程

➢ 执行完成程序放入完成队列（仅为保存状态，非系统部分）

➢ 提供获取执行状态的外部接口，即各个队列数据的获取

5. 视图类

➢ 提供用户操作接口（调度策略选择、进程创建）

➢ 显示各队列状态信息

➢ 创建进程调度类线程，调用调度类的接口

四、 程序总控流程图

1. 用户接口、调度算法、进程状态转换关系示意

4 / 45

系统总体设计

初始化系统

创建进程调度进程

初始化系统设备表用户选择调度策略启动进程调度进程

根据具体算法

调度进程

请求资源

执

行

完

成

等待队列就绪队列

完成队列

初始化进程

创建进程

设置进程基本信息添加设备请求创建进程加入就绪队列

页面 1

2. 调度算法基本工作流程示意

5 / 45

进程调度框架

用户选择进程

调度算法

创建进程

初始化进程基本

信息

将进程放入就绪

队列

根据算法从就绪

队列调度

Y

N

就绪队列是否有

进程等待执行

Y

从就绪队列取出

执行

某一时刻

需要资源

Y

放入等待队列

执行完毕资源满足

页面 1

五、 数据结构设计

1. PCB（进程基本信息）

➢ 类结构

6 / 45

ProcessPCB

-

-

-

-

-

-

-

-

Pid

Pname

userName

Priotity

subtime

totalTime

runTime

DcRequestLst

: int

: String

: String

: int

: int

: int

: int

: List

➢ 说明

1. pid进程ID

2. pName进程名

3. userName进程用户

4. priority进程优先级

5. subtime进程提交时间

6. totalTime进程需要执行的总时间

7. runtime进程已经运行时间

8. dcReqlst当前进程所需要的设备请求表

2. Dispatcher（进程调度进程）

➢ 类结构

7 / 45

Dispatcher

-

-

-

-

-

-

-

Systime

isContention

preLst

waitLst

finishLst

executing

sysDcLst

: int

: boolean

: List

: List

: List

: Process

: List

➢ 说明

1.

sysTime

系统时间

2. isContention当前调度是否为抢占方式

3. prelst就绪队列

4. waitlst等待队列

5. finishlst完成队列

6. executing正在执行的进程

7. sysDclst系统设备表

3. Device（系统设备）

➢ 类结构

8 / 45

Device

-

-

-

-

-

-

dcId

dcType

dcDisc

dcTime

dcPid

dcleftTime

: int

: int

: String

: int

: int

: int

➢ 说明

1. dcid设备标识

2. dcType设备类型

3. dcTime该设备一次I/O服务需要时间

4. dcPid使用该设备的进程

5. dcDisc设备描述

6. dcLefTime设备剩余服务时间

六、 程序代码结构

1. 类层次关系

9 / 45

FIFODispatcher

PLevelDispatcherRRDispatcherMRDispatcher

Dispatcher

0..1

0..1

0..*

0..*

DeviceReq

0..*

ProcessPCB

Device

0..1

2. 详细说明

➢ Dispatcher定义进程调度进程的基本信息和接口

➢ FIFODispatcher、PLevelDispatcher、RRDispatcher、

相应的调度算法

➢ Device为系统设备

➢ DeviceReq为进程设备请求，包括请求设备ID和时间

七、 代码实现分析

1. 算法分析（各算法过程见下流程图）

➢ 设备的分配释放

10 / 45

分别实现MRDispatcher

➢ 先来先服务

➢ 优先级调度

➢ 时间片轮转

➢ 多级反馈轮转

11 / 45

设备分配释放

设备分配

扫描等待队列

设备释放

扫描系统设备表

取下一等待进程

取下一设备

是否得到设备

N

扫描系统设备表

取相应设备

Y

N

设备忙碌

Y

执行设备指令

N

为下一进程

分配设备

取下一设备

设备指令

执行完毕

Y

查询等待进程

查找被服务进程

检查下一设备

设备是否空闲

Y

为进程分配设备

N

从等待队列

删除该进程

添加进程到

就绪队列

初始化设备

标识设备状态

释放设备

重置设备状态

页面 1

12 / 45

先进先出进程调度算法

进程调度

处理机空转

Y

从就绪队列取下

一进程

N

N

正确取得

就绪进程

Y

进程申请资源

N

执行进程

Y

进程结束

Y

将进程放入

完成队列

N放入等待队列

处理资源请求

页面 1

13 / 45

优先级进程调度算法（抢占式）

进程调度

处理机空转

Y

从就绪队列取下

一进程

N

N

正确取得

就绪进程

Y

进程申请资源

N

执行进程

释放处理机

放入等待队列

就绪队列有

更高优先级进程

进程结束

Y

释放处理机

放入完成队列

N

Y

放入就绪队列

让出处理机

N

Y

处理资源请求

页面 1

14 / 45

时间片轮转调度算法

进程调度

处理机空转

Y

从就绪队列取下

一进程

N

N

正确取得

就绪进程

Y

进程申请资源

N

执行进程

时间片 减 1

释放处理机

放入等待队列

时间片用完

进程结束

Y

释放处理机

放入完成队列

N

Y

放入就绪队列

让出处理机

N

Y

处理资源请求

页面 1

15 / 45

多级反馈轮转调度算法（抢占式）

进程调度

处理机空转

Y

从就绪队列取下

一进程

N

Y

N

正确取得

就绪进程

Y

进程申请资源

N

Y

是否有更高

优先级进程

N

进程优先级减1

时间片用完

执行进程

时间片 减 1

释放处理机

放入等待队列

Y

进程优先级减1

进程结束

Y

释放处理机

放入完成队列

N

放入就绪队列

让出处理机

N

处理资源请求

页面 1

2. 具体实现（代码部分有详细注释）

16 / 45

➢ 进程的插入

@Override

public void addPreProc(Process proc) {

//按优先级加到就绪队列

(proc);

int loc;

for(loc=()-2; loc>=0; loc--){

//比proc大的元素后移一个位置

Process temp = (loc);

if(ty

( loc+1, temp);

}

else{ //将proc放入空闲位置

17 / 45

( loc+1, proc);

break;

}

}

if(loc<0){

(0, proc);

}

}

➢ 取出进程

@Override

public Process delPreProc() {

//取优先级最高者，即为第一个

if(()<=0){

18 / 45

return null;

}

return (0); //返回最小一个

}

➢ 先进先出算法的调度

@Override

public void run(int time) {

int proctimeslice = 1; //假设处理器指令周期为1个时钟周期

while(time>0){ //处理机运行time时间

if(ing==null){ //没有进程占用处理机则空转

ing = Proc();

}

else{ //执行当前进程

19 / 45

Process proc = ing;

//下一次执行需要的设备

DcRequest req = tReq();

if(req!=null && time()<=e){

//进程需要请求设备，而且执行到请求时间

tProc(proc);

ing = Proc();

}else{ //无资源请求

(proctimeslice);

if(shed()){

//当前进程是已完成进程，放入完成队列,取下一进程

ishTime(

Dispatcher.

getBeginTime

()

20 / 45

+ Dispatcher.

getRunTime

());

//设置当前执行结束时间

ishProc(proc);

ing = Proc();

}

}

}

sWaitlst(proctimeslice);

++Dispatcher.

runTime

;

--time;

}

}

➢ 优先级抢占算法的调度

21 / 45

@Override

public void run(int time, boolean isContention) {

if(!isContention){ //非抢占方式

(time);

return;

}

int proctimeslice = 1; //假设处理器时钟周期

while(time>0){ //处理机运行time时间

if(ing==null){ //没有进程占用处理机则空转

ing = Proc();

}

else{ //执行当前进程

Process proc = ing;

22 / 45

//下一次执行需要的设备

DcRequest req = tReq();

if(req!=null && time()<=e){

//进程需要请求设备，而且执行到请求时间

//放入等待队列,取下一进程

tProc(proc);

ing = Proc();

}else{ //无资源请求

(proctimeslice);

if(shed()){

//当前进程是已完成进程，放入完成队列,取下一进程

ishTime(//设置当前执行结束时间

Dispatcher.

getBeginTime

()+

23 / 45

Dispatcher.

getRunTime

());

ishProc(proc);

ing = Proc();

}

}

if(!y()){ //抢占

Process preproc = (0);

if(ty>

ty){ //按优先级抢占

Proc(ing);

ing = Proc();

}

}

24 / 45

}

sWaitlst(proctimeslice);

++Dispatcher.

runTime

;

--time;

}

}

➢ 时间片轮转

@Override

public void run(int time) {

int proctimeslice = 1; //假设处理器时钟周期

while(time>0){ //处理机运行time时间

if(ing==null){ //没有进程占用处理机则空转

ing = Proc();

25 / 45

}

else{ //执行当前进程

Process proc = ing;

//下一次执行需要的设备

DcRequest req = tReq();

if(req!=null && time()<=e){

//进程需要请求设备，而且执行到请求时间

//放入等待队列,取下一进程

tProc(proc);

ing = Proc();

}else{ //无资源请求

(proctimeslice);

if(shed()){

26 / 45

//当前进程是已完成进程，放入完成队列,取下一进程

ishTime( //设置当前执行结束时间

Dispatcher.

getBeginTime

()+

Dispatcher.

getRunTime

());

ishProc(proc);

ing = Proc();

}else{

//如果当前时间片没有执行完，则从就绪队列头移到队列尾部

Proc(ing);

//当前执行进程放入就绪队列

ing = Proc();

//从就绪队列取下一个进程占用cpu

}

27 / 45

}

}

sWaitlst(proctimeslice);

++Dispatcher.

runTime

;

--time;

}

}

➢ 多级反馈轮转抢占方式

@Override

public void run(int time, boolean isContention) {

int proctimeslice = 1; //假设处理器时钟周期

while(true){

--time;

28 / 45

if(ing==null){ //没有进程占用处理机则空转

ing = Proc();

if(ing!=null){ //每调度一次重新计算时间片

time = ority()*3+1;

}

break;

}

else{ //执行当前进程

Process proc = ing;

//下一次执行需要的设备

DcRequest req = tReq();

time()<=e){

//进程需要请求设备，而且执行到请求时间

29 / 45

if(req!=null &&

//TODO 放入等待队列,取下一进程

tProc(proc);

ing = Proc();

break; //时间片未完，设备请求，重新调度

}else{ //无资源请求

(proctimeslice);

if(shed()){

//当前进程是已完成进程，放入完成队列,取下一进程

ishTime(//设置当前执行结束时间

Dispatcher.

getBeginTime

()+

Dispatcher.

getRunTime

());

ishProc(proc);

ing = Proc();

30 / 45

break; //时间片没用完，程序执行完，下一次调度

}else{

if(time<=0){ //时间片用完

//当前执行进程放入就绪队列

Proc(proc);

//从就绪队列取下一个进程占用cpu

ing = Proc();

//时间片用完，程序未执行完，下一次调度

}

}

}

if(!y()){ //抢占

Process preproc = (0);

31 / 45

break;

if(ty>

(ty+1)){

//取出时优先级已经降一级

ority(

//恢复优先级，放入当前进程被取出队列尾部

ty+1);

Proc(ing);

ing = Proc();

break; //抢占，下一次调度

}

}

}

sWaitlst(proctimeslice);

32 / 45

++Dispatcher.

runTime

;

}

}

八、 测试结果

1. 先来先服务

➢ 申请资源及阻塞

33 / 45

➢ 中间状态

34 / 45

➢ 执行结果

2. 优先级

➢ 按优先顺序放入就绪队列

35 / 45

➢ 优先级抢占及执行结果

36 / 45

3. 时间片轮转

➢ 测试数据

37 / 45

➢ 中间过程

38 / 45

➢ 测试结果

4. 多级反馈轮转

➢ 测试数据

39 / 45

➢ 抢占测试

40 / 45

➢ 执行状态

➢ 执行结果

41 / 45

九、 设计过程难点

1. 遇到的问题

1) 调度时机决策

2) 迭代器的破坏

3) 多级反馈队列兼容

4) 设备分配、释放

5) 外部统一接口，类型兼容、上转型对象

42 / 45

6) 进程的抢占

2. 解决方法

1) 设置进程相应状态（空转、结束、阻塞、时间片用完、抢断）

2) 修改循环嵌套层次，或标记迭代位置、跳出该层循环重构迭代器

3) 采用单一就绪队列，各进程转入就绪队列进行插入排序，插入相应位置

4) 扫描设备请求表，判断系统设备表中申请的设备是否空闲；扫描系统设备表，判断

设备是否运转完毕，修改设备状态及进程状态

5) 为提供外部统一调用接口，采用类的继承及上转型对象，用同一调用实现不同算法；

为实现类型兼容，采用抽象类及虚函数

6) 没执行一次，判断就绪队列首端元素是否有更高优先级，就绪队列插入元素直接进

行插入排序，平均复杂度为O(n),实际上只需要常数级的比较和移动

十、 总结

1. 系统实现情况

➢ 该系统实现了C++及Java两个版本

➢ Java版本实现了上述各调度算法，设备的自动分配及释放，有良好的用户操作接口、

43 / 45

有很好的容错提示能力

➢ C++版本实现了上述调度算法、提供用户选择设备接口、MFC实现良好的操作界

面

➢ 采用纯面向对象的思想，有良好的封装性，接口统一

➢ 用到了抽象类及虚函数、类型兼容、函数重载及运算符重载

➢ 采用了泛化的变成思想，解决了迭代器的完整性问题

➢ 逻辑与控制显示分离，算法与界面分离并使用不同的现成执行

2. 系统特点

➢ 根据要求实现了各类调度算法，并实现了抢占和非抢占工作方式

➢ 用户可在创建进程时发出多个设备请求

➢ 程序自动检测设备请求，阻塞进程并在适当时机唤醒

➢ 在插入队列是对进程排序预处理、减少执行过程中的比较次数

3. 收获

➢ 掌握了进程调度的完整过程

44 / 45

➢ 进一步复习了C++语言，加强了面向对象的思想，掌握了如何实现逻辑、控制、显

示的分离

➢ 复习了多线程的编程思想

➢ 掌握了抽象类及虚函数的应用，学习了上转型对象的应用

➢ 进一步学习泛化编程思想，掌握了如何保证迭代器的完整性

➢ 进一步实践如何在面向对象工程中分工合作，采用逻辑分离的思想使得各个模块并

行实现以及各模块的单元测试

十一、 参考文献

1. 著作：[1] 张尧学,史美林.计算机操作系统教程第2版.清华大学出版社2000年

2. 著作：[2] 张尧学.计算机操作系统教程第2版 习题与实验指导. 清华大学出版

45 / 45

本文标签： 进程队列设备调度执行