动态优先级算法

计算机操作系统》课程设计目：13采用高响应比算法的进程调度程序班级： 小组成员： 指导教师： 时间： 2013624—2013・7・30 地点： 7b312 2013年6月目录TOC\o"1-5"\h\z\o"CurrentDocument"工作进度表 2\o"CurrentDocument"组员分工 2\o"CurrentDocument"1.目的及意义 3\o"CurrentDocument"课程设计任务及要求 42.1设计任务 42.2设计要求 4\o"CurrentDocument"3.算法及数据结构 5\o"CurrentDocument"3.1算法总体设计思想 5\o"CurrentDocument"3.2动态优先级算法 5\o"CurrentDocument"4.程序设计与实现 10\o"CurrentDocument"4.1系统流程图 10\o"CurrentDocument"4.2程序代码 104.3实验结果 18\o"CurrentDocument"5.结论 20\o"CurrentDocument"6.收获、体会和建议 21\o"CurrentDocument"参考文献 21工作进度表时间完成工作完成人周一完成课程设计的需求分析周二编写代码测试代码周三编写代码测试代码周四编写代码测试代码周五完善程序周六完成设计报告组员分工（组长）2011XXXX1、 设计并编写界面部分代码；2、 将代码运行并调试；3、 编写课程设计报告和心得体会；1、 画算法的程序流程图；2、 编写课程设计报告和心得体会；1.目的及意义本课程设计主要任务就是在多用户操作系统支持下建立多用户多级文件系统的设计。具体说来，主要是为了达到下述实验目的：（1）了解并掌握文件系统中用于管理所必须的数据结构。（2）了解并掌握主要的文件操作命令的实现方法。（3）通过课程实践掌握课程设计的方法和流程，并总结设计经验，提出更好的改进方法。2.课程设计任务及要求2.1设计任务在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个，且进程之间也存在着同步与互斥的关系，要求采用指定的调度策略，使系统中的进程有条不紊地工作通过观察诸进程的运行过程，以巩固和加深处理机调度的概念2.2设计要求每一个进程有一个PCB,其内容可以根据具体情况设定。可以在界面设定的互斥资源（包括两种：输入设备与输出设备）的数目进程数、进入内存时间、要求服务时间可以在界面上进行设定进程之间存在一定的同步与互斥关系,可以通过界面进行设定,其表示方法如下：进程的服务时间由三段组成：I2C10O5（表示进程的服务时间由2个时间片的输入，10个时间片的计算,5个时间片的输出）进程间的同步关系用一个段表示：W2,表示该进程先要等待P2进程执行结束后才可以运行因此，进程间的同步与互斥关系、服务时间可以统一用四段表示为：I2C10O5W2可以在运行中显示各进程的状态：就绪、阻塞、执行采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列具有一定的数据容错性算法及数据结构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算法流程图

开始N被等待进程结束?输入设YN是否有空闲输输出完成?进程到达输入设备未占有无等待等待进程输入完成，CPU二、CPU未分配分配输出设备，输出设备数量-1>CPU开始N被等待进程结束?输入设YN是否有空闲输输出完成?进程到达输入设备未占有无等待等待进程输入完成，CPU二、CPU未分配分配输出设备，输出设备数量-1>CPU释放，优先级置0等待进程状态：没有等待进程输入设备-1,进程状态：运行进程状态：等待输出设备+1，进程状态：结束CPU忙碌，进程等待时间增加图3.4CSCAN算法流程图程序设计与实现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("被等的进程J");JLabelidl=newJLabel("输入设备)");JLabelodl=newJLabel("输出设备)");JLabelpl=newJLabel("进程数J");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);pl.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);pl.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,"添加成功"，"请确认"，JOptionPane.INFORMATION_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(int订=0;订<MAXPRO;订++)playerInfo[i1][0]=订+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,ml;//时间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;〃此进程的开始时间playerlnfo[quantity2][l]=m0;}elseif(id<=0)//如果设备小于等于了零{waittime[quantity2]++:〃进程等待时间力口114程大于0个程大于0个current值唯一进程state[quantity2]="BLOCK";//进程控制块状态转变为阻塞playerlnfo[quantity2][8]="阻塞"；}}elseif(inputown[quantity2]==1)//已经占有输入设备{_ml=second-instatime[quantity2];//运行时间-开始时间if(inputtime[quantity2]<=m1)//当前时间是否输入完成{inputdone[quantity2]=1;//进程r输入结束playerlnfo[quantity2][2]=second;inputown[quantity2]=0;//进程未输入id=id+1;//输入设备增加1}}}if(arrival[quantity2]==1&&inputdone[quantity2]==0&&waitpro[quantity2]>0)//如果进程已经到达,输入未完成且等待进{num=waitpro[quantity2]-1;//等待进程数减1state[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],在某一时刻，}}}for(k=0;k<MAXPRO;k++)//第二次检查：对内存试分配{if(inputdone[k]==1&&cpudone[k]==0)//是否在等待中{state[k]="READY";playerlnfo[k]⑻="就绪"；if(cpuown[k]==0)//未完成的{if(c==0){waittime[k]++;//cpu使用中，等待时间加1state[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;

值给n备没有运行完成输出值给n备没有运行完成输出}}elseif(cpuown[k]==1){state[k]="RUN";playerlnfo[k][8]="运行中"；n=second-cpustatime[k];//将当前时间减去CUP开始的时间的值赋if(cputime[k]<=n)〃如果该进程达到运行时间{playerInfo[k][4]=second;state[k]="OUTCPU";//该进程离开CPuplayerlnfo[k][8]="运行完成"；cpudone[k]=1;//该进程cpu运行完成cpuown[k]=0;//不对该进程分配内存prio[k]=0;//将优先权置0C++；}}}}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;//将现在的时间赋值于pplayerInfo[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("确定")；JPanelpl=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.setBounds(250,120,75,25);Enter.setBou