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

1、精选优质文档-倾情为你奉上操作系统课程设计-进程调度子系统模拟实现一、 设计内容及意义1. 课程设计内容使用java语言或C+语言编程实现模拟操作系统进程调度子系统的基本功能；实现先来先服务、时间片轮转、多级反馈轮转法对进程进行的调度过程；掌握各个调度算法的特点。2. 该课程设计意义Ø 理解进程调度的概念Ø 深入了解进程控制块的功能、进程的创建、删除以及进程各个状态间的转换过程Ø 从实用的角度对数据结构课程内容进行更深入理解和更熟练的应用Ø 进一步练习对Java及C+语言的熟练使用二、 设计方案1. 硬件环境PC一台2. 开发语言及工具Ø 操作

2、系统：MS windows XPØ C+版：Visual Studio 2008 + MFCØ Java版：Eclipse 3.4 + Java Swing3. 设计思路Ø 系统设备表用于存取调度过程中进程可申请的资源Ø 进程控制块主要负责具体进程信息的保存Ø 等待队列、就绪队列、完成队列用于保存执行过程的状态信息Ø 进程调度进程（类、线程）在就绪队列与等待队列之间进行调度Ø 主界面显示调度过程的三个队列的状态信息Ø 用户创建进程放入就绪队列等待调度三、 功能模块设计1. 进程状态转换2. PCB信息Ø

3、主要负责保存各进程基本信息Ø 提供外部状态设置和读取接口3. 系统设备类Ø 系统设备的基本信息Ø 设备状态设置、读取接口4. 调度类Ø 向就绪队列添加新创建进程Ø 从就绪队列取相应进程执行Ø 将执行阻塞进程放入等待队列Ø 检测系统设备表，分配、释放设备、唤醒等待进程Ø 执行完成程序放入完成队列（仅为保存状态，非系统部分）Ø 提供获取执行状态的外部接口，即各个队列数据的获取5. 视图类Ø 提供用户操作接口（调度策略选择、进程创建）Ø 显示各队列状态信息Ø 创建进程调度类线程，调

4、用调度类的接口四、 程序总控流程图1. 用户接口、调度算法、进程状态转换关系示意2. 调度算法基本工作流程示意五、 数据结构设计1. PCB（进程基本信息）Ø 类结构Ø 说明1. pid进程ID2. pName进程名3. userName进程用户4. priority进程优先级5. subtime进程提交时间6. totalTime进程需要执行的总时间7. runtime进程已经运行时间8. dcReqlst当前进程所需要的设备请求表2. Dispatcher（进程调度进程）Ø 类结构Ø 说明1. sysTime系统时间2. isContention当前

5、调度是否为抢占方式3. prelst就绪队列4. waitlst等待队列5. finishlst完成队列6. executing正在执行的进程7. sysDclst系统设备表3. Device（系统设备）Ø 类结构Ø 说明1. dcid设备标识2. dcType设备类型3. dcTime该设备一次I/O服务需要时间4. dcPid使用该设备的进程5. dcDisc设备描述6. dcLefTime设备剩余服务时间六、 程序代码结构1. 类层次关系2. 详细说明Ø Dispatcher定义进程调度进程的基本信息和接口Ø FIFODispatcher、PLev

6、elDispatcher、RRDispatcher、MRDispatcher分别实现相应的调度算法Ø Device为系统设备Ø DeviceReq为进程设备请求，包括请求设备ID和时间七、 代码实现分析1. 算法分析（各算法过程见下流程图）Ø 设备的分配释放Ø 先来先服务Ø 优先级调度Ø 时间片轮转Ø 多级反馈轮转2. 具体实现（代码部分有详细注释）Ø 进程的插入Overridepublic void addPreProc(Process proc) /按优先级加到就绪队列this.prelst.add(proc)

7、; int loc;for(loc=prelst.size()-2; loc>=0; loc-)/比proc大的元素后移一个位置Process temp = prelst.get(loc);if(proc.Priority<temp.Priority)prelst.set( loc+1, temp);else/将proc放入空闲位置prelst.set( loc+1, proc);break;if(loc<0)prelst.set(0, proc);Ø 取出进程Overridepublic Process delPreProc() /取优先级最高者，即为第一个if(

8、prelst.size()<=0)return null;return this.prelst.remove(0);/返回最小一个Ø 先进先出算法的调度Overridepublic void run(int time) int proctimeslice = 1;/假设处理器指令周期为1个时钟周期while(time>0)/处理机运行time时间if(this.executing=null)/没有进程占用处理机则空转this.executing = this.delPreProc();else/执行当前进程Process proc = this.executing; /下

9、一次执行需要的设备DcRequest req = proc.getNextReq();if(req!=null && req.getReqtime()<=proc.runtime)/进程需要请求设备，而且执行到请求时间this.addWaitProc(proc);this.executing = this.delPreProc();else/无资源请求proc.run(proctimeslice);if(proc.isFinished()/当前进程是已完成进程，放入完成队列,取下一进程proc.setFinishTime(Dispatcher.getBeginTime()

10、+ Dispatcher.getRunTime();/设置当前执行结束时间this.addFinishProc(proc);this.executing = this.delPreProc();cessWaitlst(proctimeslice);+Dispatcher.runTime;-time;Ø 优先级抢占算法的调度Overridepublic void run(int time, boolean isContention) if(!isContention)/非抢占方式this.run(time);return;int proctimeslice = 1;/

11、假设处理器时钟周期while(time>0)/处理机运行time时间if(this.executing=null)/没有进程占用处理机则空转this.executing = this.delPreProc();else/执行当前进程Process proc = this.executing;/下一次执行需要的设备DcRequest req = proc.getNextReq();if(req!=null && req.getReqtime()<=proc.runtime)/进程需要请求设备，而且执行到请求时间/放入等待队列,取下一进程this.addWaitProc

12、(proc);this.executing = this.delPreProc();else/无资源请求proc.run(proctimeslice);if(proc.isFinished()/当前进程是已完成进程，放入完成队列,取下一进程proc.setFinishTime(/设置当前执行结束时间Dispatcher.getBeginTime()+ Dispatcher.getRunTime();this.addFinishProc(proc);this.executing = this.delPreProc();if(!this.prelst.isEmpty()/抢占Process pre

13、proc = this.prelst.get(0);if(this.executing.Priority>preproc.Priority) /按优先级抢占this.addPreProc(this.executing);this.executing = this.delPreProc();cessWaitlst(proctimeslice);+Dispatcher.runTime;-time;Ø 时间片轮转Overridepublic void run(int time) int proctimeslice = 1;/假设处理器时钟周期while(time&g

14、t;0)/处理机运行time时间if(this.executing=null)/没有进程占用处理机则空转this.executing = this.delPreProc();else/执行当前进程Process proc = this.executing; /下一次执行需要的设备DcRequest req = proc.getNextReq();if(req!=null && req.getReqtime()<=proc.runtime)/进程需要请求设备，而且执行到请求时间/放入等待队列,取下一进程this.addWaitProc(proc);this.executin

15、g = this.delPreProc();else/无资源请求proc.run(proctimeslice);if(proc.isFinished()/当前进程是已完成进程，放入完成队列,取下一进程proc.setFinishTime(/设置当前执行结束时间Dispatcher.getBeginTime()+ Dispatcher.getRunTime();this.addFinishProc(proc);this.executing = this.delPreProc();else/如果当前时间片没有执行完，则从就绪队列头移到队列尾部this.addPreProc(this.executi

16、ng);/当前执行进程放入就绪队列this.executing = this.delPreProc();/从就绪队列取下一个进程占用cessWaitlst(proctimeslice);+Dispatcher.runTime;-time;Ø 多级反馈轮转抢占方式Overridepublic void run(int time, boolean isContention) int proctimeslice = 1;/假设处理器时钟周期while(true) -time;if(this.executing=null)/没有进程占用处理机则空转this.execu

17、ting = this.delPreProc();if(this.executing!=null) /每调度一次重新计算时间片time = this.executing.getPriority()*3+1;break;else/执行当前进程Process proc = this.executing; /下一次执行需要的设备DcRequest req = proc.getNextReq();if(req!=null && req.getReqtime()<=proc.runtime)/进程需要请求设备，而且执行到请求时间/TODO 放入等待队列,取下一进程this.addW

18、aitProc(proc);this.executing = this.delPreProc();break;/时间片未完，设备请求，重新调度else/无资源请求proc.run(proctimeslice);if(proc.isFinished()/当前进程是已完成进程，放入完成队列,取下一进程proc.setFinishTime(/设置当前执行结束时间Dispatcher.getBeginTime()+ Dispatcher.getRunTime();this.addFinishProc(proc);this.executing = this.delPreProc();break;/时间片

19、没用完，程序执行完，下一次调度elseif(time<=0)/时间片用完/当前执行进程放入就绪队列this.addPreProc(proc); /从就绪队列取下一个进程占用cputhis.executing = this.delPreProc();break;/时间片用完，程序未执行完，下一次调度if(!this.prelst.isEmpty()/抢占Process preproc = this.prelst.get(0);if(this.executing.Priority>(preproc.Priority+1)/取出时优先级已经降一级this.executing.setPri

20、ority(/恢复优先级，放入当前进程被取出队列尾部this.executing.Priority+1); this.addPreProc(this.executing);this.executing = this.delPreProc();break;/抢占，下一次调度cessWaitlst(proctimeslice);+Dispatcher.runTime;八、 测试结果1. 先来先服务Ø 申请资源及阻塞Ø 中间状态Ø 执行结果2. 优先级Ø 按优先顺序放入就绪队列Ø 优先级抢占及执行结果3. 时间片轮转Ø 测

21、试数据Ø 中间过程Ø 测试结果4. 多级反馈轮转Ø 测试数据Ø 抢占测试Ø 执行状态Ø 执行结果九、 设计过程难点1. 遇到的问题1) 调度时机决策2) 迭代器的破坏3) 多级反馈队列兼容4) 设备分配、释放5) 外部统一接口，类型兼容、上转型对象6) 进程的抢占2. 解决方法1) 设置进程相应状态（空转、结束、阻塞、时间片用完、抢断）2) 修改循环嵌套层次，或标记迭代位置、跳出该层循环重构迭代器3) 采用单一就绪队列，各进程转入就绪队列进行插入排序，插入相应位置4) 扫描设备请求表，判断系统设备表中申请的设备是否空闲；扫描系统设备表，判断设备是否运转完毕，修改设备状态及进程状态5) 为提供外部统一调用接口，采用类的继承及上转型对象，用同一调用实现不同算法；为实现类型兼容，采用抽象类及虚函数6) 没执行一次，判断就绪队列首端元素是否有更高优先级，就绪队列插入元素直接进行插入排序，平均复杂度为O(n),实际