2023年操作系统最高响应比优先调度算法实验报告广西民大

进程调度模拟设计——最高响应比优先调度算法实验报告一、实验题目与规定1、实验题目:加深对作业概念的理解。进一步了解批解决系统如何组织作业、管理作业和调度作业。2、实验规定：编写程序完毕批解决系统中的作业调度,规定采用响应比高者优先的作业调度算法。实现具体涉及：一方面拟定作业控制块的内容和组成方式;然后完毕作业调度；最后编写主函数，对所做工作进行测试。二、总的设计思想及语言环境、工具1、总的设计思想：最高响应比优先法（HRＲN）是对FCＦS方式和SJF方式的一种综合平衡。ＨRＲN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。响应比R定义如下:R=(Ｗ+T)/Ｔ＝1+W/Ｔ其中Ｔ为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系记录算每个作业的响应比,选择其中R最大者投入执行。这样,即使是长作业，随着它等待时间的增长，W／T也就随着增长,也就有机会获得调度执行。这种算法是介于FCFS和ＳＪF之间的一种折中算法。由于长作业也有机会投入运营,在同一时间内解决的作业数显然要少于SJF法,从而采用HRRＮ方式时其吞吐量将小于采用SJＦ法时的吞吐量。此外，由于每次调度前要计算响应比，系统开销也要相应增长。２、语言环境：计算机基本配置规定:操作系统:WIN98／２０２３/XＰ/20２3等Windows平台内存:２５6MB及以上主存６4KB（Mｅmｏry）(以KB为单位分派）开发语言:VｉsuaｌＣ＋＋6．0３、工具：Ｗindoｗs平台+VisuaｌC＋+6．０三、数据结构与模块说明(功能与框图)作业调度的实现重要有两个问题：一个是如何将系统中的作业组织起来;另一个是如何进行作业调度。为了将系统中的作业组织起来，需要为每个进入系统的作业建立档案以记录和作业相关的信息，例如，作业名、作业所需资源、作业执行时间、作业进入系统的时间、作业信息在存储器中的位置、指向下一个作业控制块的指针等信息。这个记录作业相关信息的数据块称为作业控制块(JＣB），并将系统中档待作业调度的作业控制块组织成一个队列,这个队列称为后备队列。当进行作业调度时,从后备队列中查找选择作业。由于实验中没有实际作业,作业控制块中的信息内容只使用了实验中需要的数据。作业控制块中一方面应当涉及作业名;另一方面是作业所需资源（内存大小、打印机的数量和磁带机的数量）；采用响应比高者优先作业调度算法,为了计算响应比，还需要有作业的估计执行时间、作业在系统中的等待时间；此外，指向下一个作业控制块的指针必不可少。实验中，作业控制块及队列的数据结构定义如下:sｔructｔaｓk{ ｓtｒiｎgname;/*作业号*／ intａrrＴｉmｅ;/*作业到达时间*/ﻩintserTｉme;/*作业规定服务时间*/ intwａiTｉｍe;／*等待时间*／ iｎtbegTime;/*开始运营时间*/ inｔfinTiｍe;/＊结束运营时间*/ﻩｉnttｕｒTiｍｅ;/*周转时间＊/ ｉntwTuTｉｍe；／*带权周转时间*/ﻩｉntpriority；/*优先权*／ intfinish;/＊是否已经完毕＊/｝JCB[１0];存放作业控制块的区域:#definen10JCBjoｂtabｌe[10];intjobｃount；将作业控制块组织成一个队列,实验中采用静态链表的方式模拟作业的后备队列,作业队列头指针定义为:ｉｎt*head;实验中，内存采用可移动的动态分区管理方法，即只要内存空闲区总和比作业大就可以满足作业对内存的需求;对打印机和磁带机这两种独占设备采用静态分派法,即作业执行前必须获得所需资源，并且执行完才归还。采用响应比高者优先调度算法进行调度时,必须计算出系统中所有满足必要条件作业的响应比，从中选择响应比最高的一个作业装入主存储器分派资源。由于是实验,所以就将作业控制块出队,并输出作业名代替装入处存储器，同时修改系统的资源数量。最高响应比优先调度算法的作业调度程序流程图(如下）四、参考源程序:#ｉncｌｕｄe＜doｓ.h>#ｉnclude<time.ｈ>#iｎclude<stdlib.ｈ>＃iｎcluｄe＜stdio．ｈ>#ｉncｌｕde<ｃoｎiｏ．ｈ>#inclｕde<strｉng.ｈ>ｔypeｄeｆchａrｓｔring[１０］;/*//定义sｔrｉng为具有1０个字符元素的字符数组类型*/sｔｒｕcttaｓk｛ﻩｓtｒinｇname；／*作业号*/ﻩintarｒTiｍe；/*作业到达时间＊／ﻩintserTime;/＊作业规定服务时间＊/ inｔwaｉＴime；/*等待时间*/ inｔbegTimｅ;／*开始运营时间*/ﻩintfｉnTime;/*结束运营时间*/ﻩiｎtturＴime;／*周转时间＊/ intwTuTime;／*带权周转时间*／ intprｉority；/＊优先权＊/ inｔfｉｎｉsｈ；/*是否已经完毕*／｝JCB[10];intnum;voidiｎpuｔ（){ﻩintｉ；ｓyｓtem("cls"）;ﻩprｉntf("\n请输入作业数量：");ﻩscaｎf("%d"，&ｎum);ﻩfｏr（i＝０;i＜num;ｉ+＋) { ﻩｐrintf（"＼n请输入作业NＯ．％d:\n",i);ﻩ prｉntf(＂作业名称:"）;ﻩﻩscanf("%s",JＣB［i].nａmｅ);ﻩﻩpｒinｔf(＂到达时间:"); ﻩｓcanf("%ｄ＂,＆ＪCB[ｉ].ａｒrTime); ﻩpriｎtf(＂服务时间：");ﻩﻩsｃaｎf("%ｄ"，&ＪＣＢ[i].sｅrTiｍe）； JＣB[ｉ]．ｐrioｒiｔy=0; JCB[ｉ].finiｓｈ=０;ﻩ｝}iｎtHRN(iｎｔpｒe）{ iｎｔcurrent＝1,i，j;/＊优先权＝(等待时间+服务时间)/服务时间*/ for(ｉ=０;ｉ<ｎum；i+＋)ﻩ{JCＢ[ｉ].wａiTime＝JCB[pｒｅ］．fｉｎTｉｍe-JCB[ｉ]．arrTｉme;/*等待时间=上一个作业的完毕时间-到达时间*/JCB[i].pｒiority=(JＣB［i]．waｉTｉmｅ+ＪＣB[ｉ］．seｒTime)/ＪCＢ[i].serTime;ﻩ} ｆoｒ（i＝0;ｉ<nuｍ;ｉ++) { iｆ(!JＣＢ[i].fｉnｉｓh)ﻩﻩ{ ﻩ cｕrｒent＝i;／*找到第一个还没完毕的作业*／ ﻩﻩｂreａk; }ﻩ}ﻩfoｒ(j＝i;ｊ<num;j++）/＊和后面的作业比较*／ {ﻩ ｉf(!JＣB[j].fiｎisｈ)／*还没完毕(运营）＊/ﻩﻩ{ ﻩﻩif(JCB[ｃurrenｔ]．ａｒrTime<=ＪＣB[ｐre].fｉｎTiｍｅ)/*假如作业在上一个作业完毕之前到达*/ﻩﻩﻩ{ﻩﻩ if(JCＢ［ｊ].ａｒrＴime＜=JCB[pre］．ｆiｎTｉme＆＆ＪCB[j］.prｉoriｔy＞JＣB[ｃuｒrenｔ]．prｉority)ﻩﻩﻩ ﻩｃurrｅnt=j;/*找出到达时间在上一个作业完毕之前，优先权高的作业＊/ﻩ ﻩ}ﻩﻩﻩelse/*假如作业是在上一个作业完毕之后到达*/ﻩﻩﻩ｛ ﻩ ﻩif(JCＢ[j］.aｒｒTimｅ<JCB[ｃurrent].arｒＴｉmｅ） ﻩﻩ ﻩｃurｒｅnｔ=ｊ;/*找出比较早到达的一个*/ ﻩif(JCＢ[j]．aｒrTｉme==ＪCＢ[cuｒreｎｔ].arrTｉme)/*假如同时到达*/ ﻩif(ＪCB[j].prioriｔy>JCB[cuｒrｅnt］．pｒioｒiｔy) ﻩ ﻩﻩcｕrrｅnt=j;/*找出服务时间比较短的一个*/ﻩ ｝ } }ﻩretｕrncｕrrenｔ;/*返回当前作业*/｝ｖｏｉdruniｎg(ｉｎｔi,inttimes，ｉｎtｐｒe,intstａTｉme,iｎtｅndTiｍe）{ ｉf（times==0)ﻩ{ JCＢ[i].beｇTｉｍe=JＣB［i］.arrTime；ﻩ ﻩ ﻩ ﻩJＣB[i]．ｆｉnTimｅ=ＪCB[i］.begＴiｍｅ+JCB［i]．ｓeｒＴiｍe； ﻩJCB[i].ｔurTime=JCB［i].ｓerＴime; ﻩ ﻩ ﻩJCＢ［i].ｗＴuTｉme=１.０; ﻩ ﻩ ﻩﻩ ﻩﻩ sｔaTime＝JCＢ[i].begTime;ﻩ｝ﻩｅlsｅﻩ{ if（ＪCB[i].ａrrＴimｅ>JCB[pre].finTimｅ)ﻩ ﻩJＣB[i].begTime＝JCＢ[i].arrTiｍｅ； eｌsｅ JＣB[i].begTime=JCB[ｐre].finTｉme;ﻩ ＪCＢ[ｉ]．ｆinTime＝JCB[i].begTｉｍe+JCＢ[i]．ｓerTimｅ;ﻩ JCB[i]．turＴｉmｅ＝JCB[ｉ].finTime-JCB[i］.arrTime; JCＢ[ｉ］.wTuTimｅ=ＪCB[ｉ］.turTｉme／ＪＣB［i]．ｓｅrＴiｍe;ﻩﻩ}ﻩｉf(tiｍes＝＝ｎum-1)ﻩﻩendTｉme＝ＪCB[i].fiｎTime； JCB[ｉ].fｉｎｉsh=1;ﻩ}voiｄｐrinｔ(ｉｎti,inｔｔｉｍes）{ﻩif(ｔimｅｓ==0) {ﻩﻩｐrｉntf("名称到达时间服务时间开始时间完毕时间周转时间带权周转时间\ｎ"）; }ﻩpｒintf(＂%9s%９d％９ｄ%9ｄ%9d％9d％９d＼n", ﻩJCB[ｉ].name，JＣＢ[ｉ].arｒＴｉｍｅ,JCB[i]．seｒＴime,ﻩ JCB[i]．begTime,JCB[ｉ]．fｉnTime，JCB［i].turTiｍe，JCB［i].wTｕTｉme）;}voidcheck(){ inｔi;ﻩiｎtstaTime,enｄTｉme,suｍTurTimｅ＝0.０,sｕmWTuTiｍｅ=０．0,aｖeTurTiｍe,aｖｅWTuＴime; intcurrent=０,tｉmｅs=0,prｅ＝0;ﻩJCＢ[ｐre]．finTiｍe＝０; for（ｉ=0;i<num;i++) {ﻩﻩJCＢ[ｉ]．ｆinｉsh＝0； ｝ﻩstaTｉme,endTime,sumTｕrTiｍｅ=０.０,suｍＷTuＴｉmｅ＝0．0,aｖeTurTｉme,avｅＷTuTiｍe; cuｒrent=0;timeｓ=0；pre=0; ＪCＢ[prｅ].fｉnTime=0; ｐrinｔf（＂－-－－--－－--－-－－--－－---－--－－-----－--－--－---－-－-－------－－-----------------－-＼n")； for(ｉ=0;i<nｕm;i++)ﻩ{ JCＢ[i].finiｓh＝０; ﻩ}ﻩstaTiｍe,endＴime,ｓumTｕrＴime=0．0,ｓｕmWTuTｉｍe=0.０，aｖeＴｕrＴime,aveWTuTｉme; cｕrrent=0;tiｍeｓ=０;pre＝0； JCＢ［ｐre］.finTimｅ＝0；ﻩｐｒintf（"\n－-HRRＮ-－-－----－----－--－-－－-－-------------－－－---－----－---－---－------－－-－＼n"); foｒ(times＝０;times<nuｍ;tiｍes+＋)ﻩ{ﻩﻩｃuｒrent＝HRN(pre); ﻩruninｇ(cuｒrｅnt,tｉmes，pre,ｓtaＴiｍe,ｅndTimｅ);ﻩﻩpｒint(current,timeｓ);ﻩ pre=cuｒreｎt; ｝ foｒ(ｉ=0；i＜nｕｍ;i++) ｛ﻩﻩ ｓumTｕｒTiｍe＋=JCB［i].ｔurTimｅ; ﻩﻩsumWTｕTime＋=JCＢ[i].wTuTimｅ; ｝ﻩaｖeTurTｉmｅ＝sumTurTime/ｎum；ﻩaｖｅWTuＴiｍe=sumWTuTime/ｎum;ﻩprintf（"(计与平均值)%9d%9d％9d%９d＼ｎ",ＮULL,sumTurTiｍe,aｖeTｕｒＴime，ａｖｅWTuＴime）;ﻩｐrintｆ(＂---------－－------------－－－-－－---－--－-------－----－-－---－-－--------－---－---＼n"）;}ｖｏｉdmaiｎ(){ﻩcharaｇain; do{ ﻩsystｅm（"ｃlｓ"）;／*清屏*/ ﻩpriｎｔf（"ｐｌｅaｓｅｉnput4ｇｒｏuｐsｏfdaｔas:＼n")；ﻩ inpｕt();ﻩﻩｃｈeｃk()；ﻩﻩｐrinｔf(＂Coｎtiｎu