动态优先级算法

/《计算机操作系统》课程设计题 目： 13采用高响应比算法的进程调度程序 班 级：小组成员: 指导教师：时 间：2013。6。24—2013。7。30地 点：7b3122013年6月

目 录TOC\o"1—2”\h\z\u工作进度表 2_Toc364521974"1。目的及意义 3HYPERLINK\l”_Toc364521975”2。课程设计任务及要求 4HYPERLINK\l”_Toc364521976”2。1设计任务 4HYPERLINK\l”_Toc364521977"2。2设计要求 4HYPERLINK\l”_Toc364521978"3.算法及数据结构 53。1算法总体设计思想 5HYPERLINK\l”_Toc364521980"3。2动态优先级算法 5_Toc364521982”4。1系统流程图 10HYPERLINK\l”_Toc364521983”4.2程序代码 10HYPERLINK\l”_Toc364521984”4.3实验结果 18HYPERLINK\l”_Toc364521985”5.结论 20HYPERLINK\l”_Toc364521986”6.收获、体会和建议 21HYPERLINK\l”_Toc364521987”参考文献 21

工作进度表时间完成工作完成人周一完成课程设计的需求分析周二编写代码测试代码周三编写代码测试代码周四编写代码测试代码周五完善程序周六完成设计报告组员分工（组长)2011XXXX设计并编写界面部分代码；

将代码运行并调试；编写课程设计报告和心得体会；1、画算法的程序流程图;

2、编写课程设计报告和心得体会；

1.目的及意义本课程设计主要任务就是在多用户操作系统支持下建立多用户多级文件系统的设计。具体说来，主要是为了达到下述实验目的:（1）了解并掌握文件系统中用于管理所必须的数据结构。（2）了解并掌握主要的文件操作命令的实现方法.（3)通过课程实践掌握课程设计的方法和流程，并总结设计经验,提出更好的改进方法.

2。课程设计任务及要求2.1设计任务在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个，且进程之间也存在着同步与互斥的关系，要求采用指定的调度策略,使系统中的进程有条不紊地工作，通过观察诸进程的运行过程,以巩固和加深处理机调度的概念2。2设计要求每一个进程有一个PCB，其内容可以根据具体情况设定。可以在界面设定的互斥资源（包括两种:输入设备与输出设备）的数目进程数、进入内存时间、要求服务时间可以在界面上进行设定进程之间存在一定的同步与互斥关系，可以通过界面进行设定，其表示方法如下：进程的服务时间由三段组成：I2C10O5（表示进程的服务时间由2个时间片的输入，10个时间片的计算，5个时间片的输出）进程间的同步关系用一个段表示：W2，表示该进程先要等待P2进程执行结束后才可以运行因此，进程间的同步与互斥关系、服务时间可以统一用四段表示为：I2C10O5W2可以在运行中显示各进程的状态：就绪、阻塞、执行采用可视化界面,可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列具有一定的数据容错性3。算法及数据结构3。1算法总体设计思想动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变，以便获得更好的调度性能。例如,我们可以规定，在就绪队列中的进程，随其等待时间的增长,其优先权以速率a提高.若所有的进程都有相同的优先权初始值则显然是最先进入就绪队列的进程将因其动态优先权变得最高而优先获得处理机,此即FCFS算法.若所有的就绪队列进程具有各不相同的优先权初始值,那么，对于优先权初始值低的进程,在等待足够的时间后，其优先权便可能升为最高从而获得处理机.而采用抢占式调度算法时，如果再规定当前进程的优先权以速率b下降，则可防止一个长作业长期地垄断处理机。3。2动态优先级算法3。2.1功能最高响应比优先法（HRRN）是对FCFS方式和SJF

方式的一种综合平衡。HRRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。

响应比R定义如下：

R=(W+T）/T=1+W/T

其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。

每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加,W/T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF

之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF

法，从而采用HRRN

方式时其吞吐量将小于采用SJF

法时的吞吐量。另外，由于每次调度前要计算响应比,系统开销也要相应增加。3.2.2数据结构floatarrtime[］；//作业到达时间 floatinputtime［］；////输入时间 floatcputime[];//CPU运行时间 floatoutputtime[]；//输出时间 floatwaittime［];//等待时间 floatinstatime［］；//开始运行时间 floatcpustatime［］；//CPU开始时间 floatoutstatime[］;//输出开始时间 floatfintime［]；//结束运行时间 floatprio[]；//优先权 Stringstate[];//是否已经完成 intarrival[]；//是否到达 intinputdone[]；//是否输入完成 intinputown［];//是否分配输入设备 intcpudone[];//是否运行完成 intcpuown[］；//是否分配内存 intoutputdone［］；//是否输出完成 intoutputown[]；//是否分配输出设备 intwaitpro[］;//等待的进程号3。2.3算法流程图图3.4CSCAN算法流程图4。程序设计与实现4。1系统流程图图4。1系统流程图4.2程序代码importjava。awt.＊；importjava.awt。event。*；importjava.util。*；importjavax。swing。＊；importjavax。swing.table。DefaultTableModel；importjavax。swing.table.JTableHeader；publicclassStopWatchimplementsActionListener｛ floatarrtime［］;//作业到达时间 floatinputtime[];////输入时间 floatcputime［];//CPU运行时间 floatoutputtime［];//输出时间 floatwaittime[];//等待时间 floatinstatime[］;//开始运行时间 floatcpustatime［］；//CPU开始时间 floatoutstatime［］；//输出开始时间 floatfintime［]；//结束运行时间 floatprio［］;//优先权 Stringstate[];//是否已经完成 intarrival［］;//是否到达 intinputdone[］;//是否输入完成 intinputown[］;//是否分配输入设备 intcpudone［];//是否运行完成 intcpuown［］；//是否分配内存 intoutputdone［];//是否输出完成 intoutputown[];//是否分配输出设备 intwaitpro[］；//等待的进程号 /**秒表线程启动控制*/ publicbooleanisRun=false; /＊*记录开始时间＊/ privatelongstarTime; /＊＊记录暂停时间*/ privatelongstopTime; /＊＊记录暂停到继续的总时间＊/ privatelongwasteTime； /**基于Frame的窗口*/ privateJFramestopWatchFrame； privateJButtonstarButton; privateJButtonstopButton； privateJButtoncontinueButton； JLabelTIME=newJLabel(””）; JLabelWAIT=newJLabel（”等待的进程↓")； JLabelBEIW=newJLabel(”被等的进程↓"）； JLabelidl=newJLabel（"输入设备↓”）； JLabelodl=newJLabel（”输出设备↓"）; JLabelpl=newJLabel("进程数↓”)； JPanelp1=newJPanel（); intMAXPRO；//最大数量的进程数 intIDMAX，ODMAX;//输入、输出设备 JTabletable; TextFieldbeideng=newTextField(）;// TextFielddeng=newTextField(）；// TextFieldID=newTextField();// TextFieldOD=newTextField（）；// TextFieldMAXP=newTextField（）;// JButtonEnter=newJButton（”确定"）； /**创建一个基于Frame的窗口。其中显示一个秒表（时:分：秒：毫秒)，还有“开始”“暂停“继续“停止"新建秒表"按钮*/ publicStopWatch（inti,intidmax，intodmax）｛ MAXPRO=i； IDMAX=idmax； ODMAX=odmax; arrtime=newfloat［i]; inputtime=newfloat［i]； cputime=newfloat[i］; outputtime=newfloat[i］； fintime=newfloat［i]； prio=newfloat［i]； waittime=newfloat[i]; instatime=newfloat[i]； cpustatime=newfloat［i]； outstatime=newfloat[i］; state=newString［i］; arrival=newint［i］； inputdone=newint[i］; inputown=newint[i］； cpudone=newint［i]； cpuown=newint［i］； outputdone=newint[i]； outputown=newint[i］; waitpro=newint［i］； Randomrnd=newRandom(); for(intj=0;j〈i;j++）｛//初始化数量 arrtime[j]=rnd.nextFloat(）＊5; inputtime[j］=rnd.nextFloat（）*5； cputime［j]=rnd。nextFloat()＊5； outputtime[j]=rnd.nextFloat（）*5； fintime[j]=0; prio[j]=rnd。nextFloat（）＊5; waitpro[j]=0； instatime［j］=0； cpustatime[j]=0; cpustatime［j]=0； outstatime［j］=0； state[j]=”READY"; arrival[j］=0； inputdone[j]=0; inputown[j］=0； cpudone[j]=0； cpuown[j］=0; outputdone［j]=0; outputown[j]=0； } ID.setText(IDMAX+”"）; OD.setText(ODMAX+”")； MAXP。setText(MAXPRO+””）； ID。setEditable(false）; OD.setEditable(false）； MAXP。setEditable(false）; TIME.setBounds(80，0,70，70）; p1。setLayout（null）; stopWatchFrame=newJFrame（"StopWatch”); starButton=newJButton（”开始”); stopButton=newJButton(”暂停”）； continueButton=newJButton("继续")； stopWatchFrame.addWindowListener(newWindowAdapter()//关闭窗口程序 ｛ publicvoidwindowClosing(WindowEvente）｛ System.exit（0）； ｝ }）； TIME。setBounds（80，0,200,70）；//设置位置大小 BEIW.setBounds(80，0，200，70）; WAIT.setBounds(80,0,200,70）; starButton.setBounds(0，80，75,25）； stopButton.setBounds(80，80，75,25); beideng.setBounds(600，80，75,25); deng.setBounds(680，80，75,25)； WAIT.setBounds（680，40，200,25)； BEIW.setBounds（600,40，100，25）； Enter。setBounds（760，80,75，25）； ID.setBounds（240，80,75,25）； OD。setBounds(320,80,75,25)； MAXP.setBounds(400,80,75,25）; odl。setBounds（320,40，75,25）； idl。setBounds(240，40，75，25)； pl.setBounds（400，40,75,25）; continueButton.setBounds(160，80,75，25）； starButton。addActionListener（this)；//按钮添加监听器 stopButton。addActionListener(this）; continueButton。addActionListener（this）； p1.setBounds（0,0，1000，700）; p1.add（idl); p1.add(odl)； p1。add(pl); p1。add（ID）； p1.add(OD)； p1.add（MAXP)； p1。add(BEIW）； p1。add（WAIT）； p1.add(TIME）; p1。add(beideng）; p1.add（deng）； p1.add（Enter)； p1。add（starButton）；//将按钮加进面板中 p1。add（stopButton）； p1。add（continueButton）; stopWatchFrame.setLayout(null)； stopWatchFrame.add（p1）;//将面板加进窗口 stopWatchFrame.setVisible（true）；//显示窗口 stopWatchFrame。setSize（1000,600）; Enter.addActionListener(newActionListener(）{ publicvoidactionPerformed(ActionEvente）｛ { Integer。parseInt(deng.getText（))； Integer.parseInt（beideng.getText(）)； waitpro［Integer.parseInt（deng.getText(））-1]=Integer .parseInt(beideng。getText(））; JOptionPane.showMessageDialog（null，"添加成功"，"请确认”, RMATION_MESSAGE）; } } }）； } /*＊按钮响应，当按下“开始”按钮时，秒表开始计时,按下暂停时暂停及时,按下继续时接着计时，只至按下“停止”按钮＊/ publicvoidactionPerformed（ActionEvente){ watchRunwatch=newwatchRun(）; ThreadwatchThread=newThread(watch);//产生一个秒表线程 Objectobj=e.getSource(）;//返回：最初发生Event的对象 Enter.setEnabled(false）； if(obj==starButton）//对象为开始按钮时 { if(！isRun)｛ isRun=true; starTime=System。currentTimeMillis(); watchThread.start（); } ｝elseif(obj==stopButton）//对象为暂停按钮时 { if（isRun）｛ isRun=false; stopTime=System。currentTimeMillis（）; } ｝ elseif(obj==continueButton）//对象为继续按钮时 { if(!isRun)｛ isRun=true； wasteTime=wasteTime+System.currentTimeMillis(）—stopTime； watchThread.start（); ｝ ｝ } /＊**＊＊＊***＊＊*＊*＊*＊＊＊＊*****＊＊*＊＊**＊＊**＊＊＊＊＊*＊＊＊＊＊*＊＊******＊＊＊**＊**＊***＊*＊**** *实现表格 ＊ */ /＊*秒表线程类实现Runnable接口＊/ publicclasswatchRunimplementsRunnable{ publicvoidrun(）｛ intmsec=0； intsecond=0； intminute=0; inthour=0； Stringbiaotou［]={"进程号","输入开始”，"输入结束"，"cpu开始","CPU结束", ”输出开始”，"输出结束”，"优先级",”状态”}； Object[][]playerInfo=newObject［MAXPRO］[9］; for(inti1=0;i1〈MAXPRO;i1++) playerInfo［i1］［0]=i1+1; table=newJTable（playerInfo,biaotou）； table。setAutoResizeMode(JTable.AUTO_RESIZE_OFF）; table.getTableHeader（）。setReorderingAllowed(false）; table.setBounds（20，150,400，250)； table.setEnabled(false）； table。setBackground(newColor(250，250,250)); table。getTableHeader（).setResizingAllowed（false)； JScrollPanescroll=newJScrollPane（table); scroll。setBounds(20,150，800，500)； table.setPreferredScrollableViewportSize（newDimension(550,100）)； stopWatchFrame.add(scroll）； while（isRun）//线程执行 ｛ table.repaint（)； for(intyanyu=0；yanyu<MAXPRO；yanyu++) playerInfo［yanyu］［7］=prio[yanyu］； intcount； Stringstr=””； count=（int)（System。currentTimeMillis()-starTime-wasteTime)； second=（int）((count—hour＊3600000—minute＊60000)/1000)； str=second+"”； /＊**＊*＊＊＊***＊＊*＊**＊*＊**＊******＊＊＊*＊＊**/ intquantity；//进程数量 intquantity2;//进程数量 intid=IDMAX；//输入进程的数量 floatm0,m1;//时间 intnum;//等待进程 intcurrentcpu=0;//CPU是否忙碌 intk；//进程数量 intc=1；//默认CPU当前可用 floatn;//时间 intod=ODMAX；//输出设备 intl；//进程数量 floatp;//时间 for（quantity=0；quantity<MAXPRO；quantity++){ if（arrtime［quantity］<=second）//输入设备 { arrival[quantity]=1;//到达 } } for(quantity2=0;quantity2<MAXPRO;quantity2++){//System。out.print("代号998"); if(arrival［quantity2]==1&＆inputdone[quantity2]==0 &&waitpro［quantity2]==0）//已经到达，还没完成而且等待进程等于零 { if（inputown［quantity2]==0）//未进行输入 ｛ if(id>0）// ｛ //还留有输入设备 id=id-1；//设备减一 inputown[quantity2］=1； m0=second;//初始时间 instatime［quantity2]=m0；//此进程的开始时间 playerInfo［quantity2][1]=m0; }elseif(id〈=0)//如果设备小于等于了零 ｛ waittime［quantity2]++；//进程等待时间加1 state［quantity2]=”BLOCK”；//进程控制块状态转变为阻塞 playerInfo[quantity2］［8］="阻塞"； } ｝elseif(inputown[quantity2］==1）//已经占有输入设备 { m1=second-instatime[quantity2]；//运行时间—开始时间 if(inputtime［quantity2]〈=m1)//当前时间是否输入完成 { inputdone［quantity2]=1;//进程r输入结束 playerInfo［quantity2］[2］=second; inputown［quantity2]=0；//进程未输入 id=id+1；//输入设备增加1 ｝ ｝ ｝ if（arrival［quantity2］==1&＆inputdone［quantity2］==0 &＆waitpro［quantity2］〉0）//如果进程已经到达,输入未完成且等待进程大于0个 { num=waitpro［quantity2]-1；//等待进程数减1 state［quantity2]=”WAIT";//进程状态为等待 playerInfo［quantity2］［8]=”等待”; if（outputdone[num]==1)//第num进程输出完成 { waitpro[quantity2］=0;//第r个进程的等待进程为0 } } } intj； for(j=0;j〈MAXPRO;j++)//第一次检查:选出等待队列中优先级最大的 ｛ if(inputdone［j]==1＆&cpudone［j］==0）//输入完成而未进入cpu，即在等待 ｛ prio［j]=（waittime［j]+cputime[j])/cputime［j];//计算进程J优先级 if(prio[j]〉prio[currentcpu])//如进程J的优先级大于当前进程的优先级 ｛ currentcpu=j;//将优先权最大的赋给PCB［current］，在某一时刻,current值唯一 } ｝ ｝ for（k=0；k<MAXPRO;k++)//第二次检查:对内存试分配 { if(inputdone［k］==1＆＆cpudone［k］==0）//是否在等待中 ｛ state[k]=”READY”; playerInfo［k]［8]="就绪"; if(cpuown[k］==0)//未完成的 ｛ if（c==0)｛ waittime［k]++;//cpu使用中，等待时间加1 state［k]="READY”; playerInfo［k］［8］=”CPU被占用"； ｝elseif(c==1）｛ if(k==currentcpu）{//cpu空闲，而且当前进程是优先权最大的进程 c—-； cpuown［k］=1； playerInfo[k］[3]=second; n=second； cpustatime［k]=n； } } ｝elseif(cpuown[k]==1）{ state［k]="RUN”； playerInfo［k］[8]=”运行中”； n=second-cpustatime［k］;//将当前时间减去CUP开始的时间的值赋值给n if（cputime［k]〈=n）//如果该进程达到运行时间 ｛ playerInfo［k]［4］=second; state［k］="OUTCPU";//该进程离开CPu playerInfo［k］[8］="运行完成"; cpudone［k]=1;//该进程cpu运行完成 cpuown[k]=0；//不对该进程分配内存 prio［k］=0;//将优先权置0 c++; ｝ } } ｝ for(l=0;l<MAXPRO；l++)｛ if（cpudone[l]==1&＆outputdone［l］==0）//如该进程已经运行完成但是输出设备没有运行 { if（outputown［l]==0)//如果该进程没有分配输出设备 ｛ if(od>0)//如果有空闲的输出设备，分配输出设备 ｛ od——；//输出设备减一 outputown［l]=1;//该进程获得输出设备 playerInfo［l］[8]="输出开始”； p=second;//将现在的时间赋值于p playerInfo[l］［5]=second； outstatime[l］=p；//该进程获取输出设备的时间 }elseif(od〈=0）{//如果没有空闲的输出设备 waittime［l］++;//该进程等待 ｝ }elseif（outputown［l］==1)//如果该进程已经获取输出设备 { p=second—outstatime［l］；//计算运行输出设备的时间 if(outputtime［l］〈=p）//判断该进程是否完成输出，如果已经完成 ｛ playerInfo［l]［6］=second; outputdone［l]=1；//该进程输出完成 outputown[l]=0；//不分配输出设备 od++;//输出设备增加1 } ｝ ｝elseif(cpudone[l］==1＆＆outputdone[l]==1）//如果该进程已经使用完cpu且完成输出 { state［l]="DONE"；//该进程状态修改为完成 playerInfo［l］［8］=”进程结束"; ｝ } TIME。setText("系统运行时间：”+str)； try{ Thread.sleep（1000）; ｝catch（Exceptione）｛ e。printStackTrace（）； ｝ } ｝ } /**主程序初始化一个秒表＊/ publicstaticvoidmain（Stringargs［]){ newtt(）； }｝classttextendsJFrame{ JFramef=newJFrame（); JLabelpt=newJLabel（"进程数”); JLabelit=newJLabel(”输入设备数量"); JLabelot=newJLabel（”输出设备数量"); TextFieldpp=newTextField（)； TextFieldii=newTextField()； TextFieldoo=newTextField（）； JButtonEnter=newJButton（”确定")； JPanelp1=newJPanel()； tt(）{ pt.setBounds（0，40,75，25）； it。setBounds（00，80，150,25）； ot。setBounds(00，120，150,25); pp.setBounds（250，40,75，25）； ii。setBounds（250,80，75,25); oo.se