《动态优先级算法》由会员分享，可在线阅读，更多相关《动态优先级算法（22页珍藏版）》请在金锄头文库上搜索。
1、计算机操作系统课程设计题 目： 13 采用高响应比算法的进程调度程序 班 级： 小组成员： 指导教师： 时 间： 2013.6.24 2013.7.30 地 点： 7b312 2013 年 6 月1目 录工作进度表 .2组员分工 .21. 目的及意义 .32. 课程设计任务及要求 .42.1 设计任务 .42.2 设计要求 .43. 算法及数据结构 .53.1 算法总体设计思想 .53.2 动态优先级算法 .54. 程序设计与实现 .104.1 系统流程图 .104.2 程序代码 .104.3 实验结果 .185. 结论 .206. 收获、体会和建议 .21参考文献 .212工作进度表时间 完
2、成工作 完成人周一 完成课程设计的需求分析周二 编写代码测试代码周三 编写代码测试代码周四 编写代码测试代码周五 完善程序周六 完成设计报告组员分工（组长） 2011XXXX 1、 设计并编写界面部分代码； 2、 将代码运行并调试；3、 编写课程设计报告和心得体会；1、 画算法的程序流程图；2、 编写课程设计报告和心得体会；31. 目的及意义本课程设计主要任务就是在多用户操作系统支持下建立多用户多级文件系统的设计。具体说来，主要是为了达到下述实验目的： （1）了解并掌握文件系统中用于管理所必须的数据结构。（2）了解并掌握主要的文件操作命令的实现方法。（3）通过课程实践掌握课程设计的方法和流程，
3、并总结设计经验，提出更好的改进方法。42. 课程设计任务及要求2.1 设计任务在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个，且进程之间也存在着同步与互斥的关系，要求采用指定的调度策略，使系统中的进程有条不紊地工作，通过观察诸进程的运行过程，以巩固和加深处理机调度的概念2.2 设计要求每一个进程有一个 PCB，其内容可以根据具体情况设定。可以在界面设定的互斥资源（包括两种：输入设备与输出设备）的数目进程数、进入内存时间、要求服务时间可以在界面上进行设定进程之间存在一定的同步与互斥关系，可以通过界面进行设定，其表示方法如下：进程的服务时间由三段组成：I2C10O5 （表示进程
4、的服务时间由 2 个时间片的输入，10 个时间片的计算，5 个时间片的输出）进程间的同步关系用一个段表示：W2，表示该进程先要等待 P2 进程执行结束后才可以运行因此，进程间的同步与互斥关系、服务时间可以统一用四段表示为：I2C10O5W2可以在运行中显示各进程的状态：就绪、阻塞、执行采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列具有一定的数据容错性53. 算法及数据结构3.1 算法总体设计思想动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变，以便获得更好的调度性能。例如，我们可以规定，在就绪队列中的进程，随其等待时间
5、的增长，其优先权以速率 a 提高。若所有的进程都有相同的优先权初始值则显然是最先进入就绪队列的进程将因其动态优先权变得最高而优先获得处理机，此即FCFS 算法。若所有的就绪队列进程具有各不相同的优先权初始值，那么，对于优先权初始值低的进程，在等待足够的时间后，其优先权便可能升为最高从而获得处理机。而采用抢占式调度算法时，如果再规定当前进程的优先权以速率 b 下降，则可防止一个长作业长期地垄断处理机。3.2 动态优先级算法3.2.1 功能最高响应比优先法（HRRN）是对 FCFS 方式和 SJF 方式的一种综合平衡。 HRRN 调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中
6、选出响应比最高的作业投入执行。 响应比 R 定义如下： R=(W+T)/T=1+W/T 其中 T 为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。 每当要进行作业调度时，系统计算每个作业的响应比，选择其中 R 最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W/T 也就随着增加，也就有机会获得调度执行。这种算法是介于 FCFS 和 SJF 之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于 SJF 法，从而采用 HRRN 方式时其吞吐量将小于采用 SJF 法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。3.2.2
7、数据结构float arrtime; / 作业到达时间float inputtime;/ /输入时间float cputime;/ CPU 运行时间float outputtime;/ 输出时间6float waittime; / 等待时间float instatime; / 开始运行时间float cpustatime;/ CPU 开始时间float outstatime;/ 输出开始时间float fintime; / 结束运行时间float prio; / 优先权String state; / 是否已经完成int arrival;/ 是否到达int inputdone;/ 是否输入完成i
8、nt inputown;/ 是否分配输入设备int cpudone;/ 是否运行完成int cpuown;/ 是否分配内存int outputdone;/ 是否输出完成int outputown;/ 是否分配输出设备int waitpro;/ 等待的进程号73.2.3 算法流程图8开始进程到达输入设备未占有无等待等待进程进程状态 ： 等待N被等待进程结束 ？N等待进程状态 ： 没有等待进程输入设备 0 ?Y输入设备 - 1 ，Y输入完成 ， C P U未工作C P U 未分配Y进程状态 ： 运行C P U 运行完成 ？C P U 忙碌 ， 进程等待时间增加NC P U 释放 ， 优先级置 0Y
9、是否有空闲输出设备分配输出设备 ， 输出设备数量 - 1Y输出完成 ？输出设备 + 1 ， 进程状态 ： 结束YNNN9图 3.4 CSCAN 算法流程图104. 程序设计与实现4.1 系统流程图输入进程数 ， 输入 、 输出设备数量输入等待 、被等待进程开始运行图 4.1 系统流程图4.2 程序代码import java.awt.*;import java.awt.event.*;import java.util.*;import javax.swing.*;import javax.swing.table.DefaultTableModel;import javax.swing.table
10、.JTableHeader;public class StopWatch implements ActionListener float arrtime; / 作业到达时间float inputtime;/ /输入时间float cputime;/ CPU 运行时间float outputtime;/ 输出时间float waittime; / 等待时间float instatime; / 开始运行时间float cpustatime;/ CPU 开始时间float outstatime;/ 输出开始时间float fintime; / 结束运行时间float prio; / 优先权String state; / 是否已经完成int arrival;/ 是否到达int inputdone;/ 是否输入完成int inputown;/ 是否分配输入设备int cpudone;/ 是否运行完成int cpuown;/ 是否分配内存int outputdone;/ 是否输出完成int outputown;/ 是否分配输出设备int waitpro;/ 等待的进程号/* 秒表线程启动控制
