作业调度实验

实验二作业调度实验一.目的要求：

用高级语言编写和调试一个或多个作业调度的模拟程序，以加深对作业调度算法的理解。二.实习题：1、编写并调试一个单道处理系统的作业等待模拟程序。作业等待算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，以比较各种算法的优缺点。

先来先服务算法：按照作业提交给系统的先后顺序来挑选作业，先提交的先被挑选。最短作业优先算法：是以进入系统的作业所提出的“执行时间”为标准，总是优先选取执行时间最短的作业。响应比高者优先算法：是在每次调度前都要计算所有被选作业（在后备队列中）的响应比，然后选择响应比最高的作业执行。调度算法的流程图如下图所示。(4)执行结果源程序：#include<stdio.h>#include<stdlib.h>#include<conio.h>#definegetpch(type)(type*)malloc(sizeof(type))//#defineNULL0intn;floatT1=0,T2=0;inttimes=0;structjcb//作业控制块{charname[10];//作业名intreachtime;//作业到达时间intstarttime;//作业开始时间intneedtime;//作业需要运行的时间floatsuper;//作业的响应比intfinishtime;//作业完成时间floatcycletime;//作业周转时间floatcltime;//作业带权周转时间charstate;//作业状态structjcb*next;//结构体指针}*ready=NULL,*p,*q;typedefstructjcbJCB;voidinital(){inti;printf("\n输入作业数:");scanf("%d",&n);for(i=0;i<n;i++){p=getpch(JCB);printf("\n输入作业名:");scanf("%s",p->name);getch();p->reachtime=i;printf("作业默认到达时间:%d",i);printf("\n输入作业要运行的时间:");scanf("%d",&p->needtime);p->state='W';p->next=NULL;if(ready==NULL)ready=q=p;else{q->next=p;q=p;}}}voiddisp(JCB*q,intm){if(m==3){printf("\n作业%s正在运行，估计其运行情况：\n",q->name);printf("开始运行时刻：%d\n",q->starttime);printf("完成时刻：%d\n",q->finishtime);printf("周转时间：%f\n",q->cycletime);printf("带权周转时间：%f\n",q->cltime);printf("相应比:%f\n",q->super);getch();}else{printf("\n作业%s正在运行，估计其运行情况：\n",q->name);printf("开始运行时刻：%d\n",q->starttime);printf("完成时刻：%d\n",q->finishtime);printf("周转时间：%f\n",q->cycletime);printf("带权周转时间：%f\n",q->cltime);getch();}}voidrunning(JCB*p,intm){if(p==ready){ready=p->next;p->next=NULL;}else{q=ready;while(q->next!=p)q=q->next;q->next=p->next;}p->starttime=times;p->state='R';p->finishtime=p->starttime+p->needtime;p->cycletime=(float)(p->finishtime-p->reachtime);p->cltime=(float)(p->cycletime/p->needtime);T1+=p->cycletime;T2+=p->cltime;disp(p,m);times+=p->needtime;p->state='F';printf("\n%shasbeenfinished!\npressanykeytocontinue...\n",p->name);free(p);getch();}voidsuper(){JCB*padv;padv=ready;do{if(padv->state=='W'&&padv->reachtime<=times)padv->super=(float)(times-padv->reachtime+padv->needtime)/padv->needtime;padv=padv->next;}while(padv!=NULL);}voidfinal(){floats,t;t=T1/n;s=T2/n;getch();printf("\n\n作业已经全部完成!");printf("\n%d个作业的平均周转时间是：%f",n,t);printf("\n%d个作业的平均带权周转时间是%f：\n\n\n",n,s);}voidhrn(intm){JCB*min;inti,iden;system("cls");inital();for(i=0;i<n;i++){p=min=ready;iden=1;super();do{if(p->state=='W'&&p->reachtime<=times)if(iden){min=p;iden=0;}if(p->super>min->super)min=p;p=p->next;}while(p!=NULL);if(iden){i--;times++;if(times>1000){printf("\nruntimeistoolong...error...");getch();}}else{running(min,m);//调用running()函数}}//forfinal();//调用running()函数}voidsjf(intm)//最短作业优先算法{JCB*min;inti,iden;system("cls");inital();for(i=0;i<n;i++){p=min=ready;iden=1;do{if(p->state=='W'&&p->reachtime<=times)if(iden){min=p;iden=0;}if(p->needtime<min->needtime)min=p;p=p->next;}while(p!=NULL);if(iden){i--;//printf("\ntime=%d:\tnoJCBsubmib...wait...",time);times++;if(times>100){printf("\nruntimeistoolong...error");getch();}}else{running(min,m);}}//forfinal();}voidfcfs(intm){inti,iden;system("cls");inital();for(i=0;i<n;i++){p=ready;iden=1;do{if(p->state=='W'&&p->reachtime<=times)iden=0;if(iden)p=p->next;}while(p!=NULL&&iden);if(iden){i--;printf("\n没有满足要求的进程,需等待");times++;if(times>100){printf("\n时间过长");getch();}}else{running(p,m);}}final();}voidmune(){intm;system("cls");printf("\n\n\t\t*********************************************\t\t\n");printf("\t\t\t\t作业调度演示\n");printf("\t\t*********************************************\t\t\n");printf("\n\n\n\t\t\t1.先来先服务算法.");printf("\n\t\t\t2.最短作业优先算法.");printf("\n\t\t\t3.响应比高者优先算法");printf("\n\t\t\t0.退出程序.");printf("\n\n\t\t\t\t选择所要操作:");scanf("%d",&m);switch(m){case1:fcfs(m);getch();system("cls");mune();break;case2:sjf(m);getch();system("cls");mune();break;case3:hrn(m);getch();system("cls");mune();break;case0:system("cls");break;default:printf("选择错误,重新选择.");getch();system("cls");mune();}}intmain()//主函数{mune();return0;}2、编写并调度一个多道程序系统的作业调度模拟程序。作业调度算法：采用基于先来先服务的调度算法。可以参考课本中的方法进行设计。对于多道程序系统，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求。2.1实验原理及设计方案采用多道程序设计方法的操作系统，在系统中要经常保留多个运行的作业，以提高系统效率。作业调度从系统已接纳的暂存在输入井中的一批作业中挑选出若干个可运行的作业，并为这些被选中的作业分配所需的系统资源。对被选中运行的作业必须按照它们各自的作业说明书规定的步骤进行控制。采用先来先服务算法算法模拟设计作业调度程序。（1）、作业调度程序负责从输入井选择若干个作业进入主存，为它们分配必要的资源，当它们能够被进程调度选中时，就可占用处理器运行。作业调度选择一个作业的必要条件是系统中现有的尚未分配的资源可满足该作业的资源要求。但有时系统中现有的尚未分配的资源既可满足某个作业的要求也可满足其它一些作业的要求，那么，作业调度必须按一定的算法在这些作业中作出选择。先来先服务算法是按照作业进入输入井的先后次序来挑选作业，先进入输入井的作业优先被挑选，当系统中现有的尚未分配的资源不能满足先进入输入井的作业时，那么顺序挑选后面的作业。(2)假定某系统可供用户使用的主存空间共100k，并有5台磁带机。2.2执行结果：2.3代码源代码#include<stdio.h>#include<stdlib.h>#include<string.h>#include<conio.h>#definegetjcb()(JCB*)malloc(sizeof(JCB))typedefstruct{ intmemory; inttape;}RESOURCE;typedefstructJCB{//作业控制块 charusername[20];//用户名 charjobname[10];//作业名 charstate;//作业状态 charatime[5];//到达时间 floatrtime;//运行时间 RESOURCEresource;//资源数量 structJCB*link;}JCB;RESOURCEsource={100,5};JCB*pjcb=getjcb();charnowtime[5];FILE*ignore(FILE*fp){ if(feof(fp))returnfp; charch=fgetc(fp); while(!feof(fp)&&(ch==''||ch==' ')){ ch=fgetc(fp); } //if(!feof(fp))returnfp; fseek(fp,-1,SEEK_CUR); returnfp; }FILE*findchar(FILE*fp,charc){ if(feof(fp))returnfp; charch=fgetc(fp); while(!feof(fp)&&(ch!=c)){ ch=fgetc(fp); } fseek(fp,-1,SEEK_CUR); returnfp;}voiddestory()//{ JCB*p=pjcb->link; while(pjcb){ free(pjcb); pjcb=p; if(p) p=p->link; }}floatstof(char*time)//{ floath=0,m=0; inti=0; while(time[i]!=':'){ h=h*10+time[i]-'0'; i++; } i++; while(time[i]!='\0'){ m=m*10+time[i]-'0'; i++; } return(h+m/60);}char*ftos(doubleftime)//{ inth,m; h=int(ftime); m=int((ftime-h)*60); sprintf(nowtime,"%c:%c%c",h+'0',int(m/10)+'0',int(m%10)+'0'); returnnowtime;}floattimesub(char*time1,char*time2){ returnstof(time1)-stof(time2);}voidprint()//打印输出{ JCB*p=pjcb->link; printf("现在时间是%s\n",nowtime); printf("现在资源的数量%d\t\t%d\n",source.memory,source.tape); printf("\t\t\t\t\t\t\t资源要求\n"); printf("用户名\t作业名\t状态\t到达时间\t运行时间(小时)\t主存(K)\t磁带机\n"); while(p){ printf("%s\t%s\t%c\t%s\t\t\t%.2f\t%d\t%d\n",p->username,p->jobname,p->state,p->atime,p->rtime,p->resource.memory,p->resource.tape); p=p->link; }}voidsendsource()//为作业分配资源{ JCB*p; p=pjcb->link; while(p){//为到达的作业调度 if(p->state=='W'&&source.memory-p->resource.memory>=0&&source.tape-p->resource.tape>=0){ p->state='R'; source.memory-=p->resource.memory; source.tape-=p->resource.tape; printf("\n%s\t%s被调入内存\n",p->username,p->jobname); } p=p->link; } }voidinit(){ FILE*fp; JCB*p=NULL,*q=pjcb; if((fp=fopen("jobs.txt","r"))==NULL){ printf("Cannotopenthefile!"); exit(1); } rewind(fp); fp=findchar(fp,'A'); while(!feof(fp)){ p=getjcb(); fscanf(fp,"%s",p->username); fp=ignore(fp); fscanf(fp,"%s",p->jobname); fp=ignore(fp); fscanf(fp,"%c",&p->state); fp=ignore(fp); fscanf(fp,"%s",p->atime); fp=ignore(fp); p->rtime=0;//不初始化则会发生错误，？？？？？ fscanf(fp,"%f",&(p->rtime)); fp=ignore(fp); fscanf(fp,"%d",&p->resource.memory); fp=ignore(fp); fscanf(fp,"%d",&p->resource.tape); fp=ignore(fp); q->link=p; q=p; } p->link=NULL; sendsource(); fclose(fp);}intcheckend() { JCB*p=pjcb->link; while(p){ if(p->state!='F'){ return0; } p=p->link; } return1;}voidrun()//运行作业{ if(checkend()){ printf("所有作业都已经完成...\n"); exit(0); } JCB*p=pjcb->link; doubletime; while(p){//作业运行完毕释放资源 time=stof(nowtime)-stof(p->atime); if(p->state=='R'&&time>=p->rtime){ p->state='F'; source.memory+=p->resource.memory; source.tape+=p->resource.tape; printf("\n%s\t%s已经执行结束\n",p->username,p->jobname); break; } p=p->link; } p=pjcb->link; while(p){//计算到达的作业 if(strcmp(nowtime,p->atime)==0&&p->state=='N'){ p->state='W'; printf("\n%s\t%s作业已到达\n",p->username,p->jobname); } p=p->link; } sendsource();//为作业分配资源 print(); }intmain(){ charch; doubletime=9.00; doublestep=float(5)/60+0.00001; ftos(9.0); init(); do{ run(); puts("**************************************************\n"); puts("是否继续运行,每次运行5分钟Y/N。。。。"); puts("**************************************************\n"); ch=getche(); time+=step; ftos(time); }while(toupper(ch)=='Y'); destory(); return0;}3、编写并调试一个多道程序系统的作业调度模拟程序。作业调度算法：采用基于优先级的作业调度。二．实验代码#include<stdio.h>#include<stdlib.h>#definegetjch(type)(type*)malloc(sizeof(type))#defineN10structjcb{/*定义作业控制块PCB*/ charname[10]; floatneedtime;/*运行时间*/ floatarrivetime;/*提交时刻*/ floatstorage[N];/*系统资源*/ structjcb*link;}*ready=NULL,*pb=NULL,*p;typedefstructjcbJCB;floatTc,Ti,Wi,T=0;/*完成时刻,周转时间,带权周转时间,时间量*/floatTiSum=0,WiSum=0;/*平均周转时间,带权a平均周转时间*/floatsource[N];intn;voidinput();/*输入作业信息*/intspace();/*返回就绪队列中作业的数目*/voidfcfs();/*先来先服务算法*/voiddisp(JCB*pr);/*显示相应的作业*/voidrunning();/*运行作业组*/voiddestroy();/*撤销作业*/voidinput()/*建立作业控制块函数*/{ inti,k,num; printf("请输入所拥有的资源种类:"); scanf("%d",&n); printf("输入系统所拥有资源数:\n"); for(i=0;i<n;i++) { printf("资源[%d]:",i); scanf("%f",&source[i]); } printf("\n输入作业数量:"); scanf("%d",&num); for(i=0;i<num;i++) { printf("\n作业号[%d]:\n",i); p=getjch(JCB); printf("输入作业名:"); scanf("%s",p->name); printf("输入提交时间:"); scanf("%f",&p->arrivetime); printf("输入运行时间:"); scanf("%f",&p->needtime); printf("输入所需资源数:\n"); for(k=0;k<n;k++) { printf("资源[%d]:",i); scanf("%f",&p->storage[k]); } printf("\n"); p->link=NULL; fcfs(); }}intspace(){ intl=0; JCB*pr=ready; while(pr!=NULL) { l++; pr=pr->link; } return(l);}voiddisp(JCB*pr)/*建立作业显示函数,用于显示当前作业*/{ inti; printf("\n%6s\t%6s\t%6s\t","作业名","运行时间","提交时刻"); for(i=0;i<n;i++) printf("资源[%d]\t",i); printf("\n%6s\t%6.2f\t\t%6.2f\t",pr->name,pr->needtime,pr->arrivetime); for(i=0;i<n;i++) printf("\t%6.2f",pr->storage[i]); printf("\n"); }voiddestroy()/*建立作业撤消函数(作业运行结束,撤消作业)*/{ free(p);}voidcheck(){ JCB*first,*fir,*p; intflag=0,i,test=0; first=pb; while(first&&(T>=first->arrivetime)&&(flag==0)) { for(i=0;i<n;i++) { if(source[i]>=first->storage[i]) source[i]=source[i]-first->storage[i]; else test=1; } if(test==0) { p=first; first=first->link; p->link=NULL; if(ready==NULL) ready=p; else { fir=ready; while(fir->link!=NULL) { fir=fir->link; } fir->link=p; } } else flag=1; } pb=first;}voidfcfs(){ JCB*first,*second; intins=0; if((pb==NULL)||(p->arrivetime<pb->arrivetime)) { p->link=pb; pb=p; } else { fir