进程调度算法磁盘调度算法银行家算法操作系统课程设

1操作系统课程设计说明书学院名称：专业班级：姓名：学号：2013年1月1日2评分标准优秀：有完整的符合标准的文档，文档有条理、文笔通顺，格式正确，程序完全实现设计要求，独立完成；良好：有完整的符合标准的文档，文档有条理、文笔通顺，格式正确；程序完全实现设计要求，独立完成，但存在少量错误；中等：有完整的符合标准的文档，有基本实现设计方案的软件，设计方案正确；及格：有完整的符合标准的文档，有基本实现设计方案的软件，设计方案基本正确；不及格：没有完整的符合标准的文档，软件没有基本实现设计方案，设计方案不正确。没有独立完成，抄袭或雷同。成绩评定为：。指导教师：年月日3目录一．进程调度算法4-----23页二．银行家算法24-----34页三．磁盘调度算法35------46页4进程调度算法1．设计目的在多道程序设计中，经常是若干个进程同时处于就绪状态，必须依照某种策略决定哪个进程优先占有处理机，因而必须解决进程调度的问题，进程调度算法就是要解决进程调度的问题。2.任务及要求2.1设计任务设计程序来模拟进程的四种调度算法，模拟实现调度的基本功能。2.2设计要求产生的各种随机数要加以限制，如alltime限制在40以内的整数。进程的数量n不能取值过大。3.算法及数据结构3.1算法的总体思想（流程）每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：（1）进程优先数ID，其中0为闲逛进程，用户进程的标识数为1，2，3…。（2）进程优先级Priority，闲逛进程（idle）的优先级为0，用户进程的优先级大于0，且随机产生，优先数越大，优先级越高。（3）进程占用的CPU时间CPUtime，进程每运行一次，累计值等于4。（4）进程总共需要运行时间Alltime，利用随机函数产生。（5）进程状态，0：就绪态；1：运行态；2：阻塞态。利用链表将数据连接起来，实现数据的存储。3.2链表模块3.2.1功能实现链表的存储功能，以及实现存储的查找功能。53.2.2数据结构构造链表这个数据结构，以及链表的初始化，链表的插入，链表的长度。3.2.3算法typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;StatusInitList(SqList&l){l.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!l.elem)exit(OVERFLOW);l.length=0;l.listsize=LIST_INIT_SIZE;returnOK;}intListLength(SqListl){return(l.length);}StatusListInsert_Sq(SqList&L,inti,ElemTypee){6//在顺序表L的第i个位置前插入元素e,i的合法值为1..L.length+1if(i1||iL.length+1)returnERROR;if(L.length=L.listsize){ElemType*newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}ElemType*q=&L.elem[i-1],*p=&L.elem[L.length-1];while(p=q){*(p+1)=*p;--p;}//插入位置后的元素右移*q=e;++L.length;returnOK;}StatusGetElem(SqListL,inti,ElemType&e){if(i=0||iL.length)returnERROR;else7e=*(L.elem+i-1);returnOK;}voidOutputlist(SqList&L){if(0==L.length)printf(空集!);elsefor(inti=0;iL.length;++i){printf(%c,*(L.elem+i));}}3.3主函数模块3.3.1功能实现进程调度的四种算法，以及人机交互的菜单。3.3.2数据结构主要包括五个部分，分别是四种算法，和进程的输入和菜单部分，功能分别实现。3.3.3算法voidmain(){8for(1;;){intnumber;PCBpcb[100];srand(time(0));intmax;intppp[100];inttime=0;inttime1;intm;inta[100];a[0]=0;printf(\n*************************进程调度算法的模拟***************************\n);printf(*1.先到先服务调度2.最短作业优先调度*\n);printf(*3.优先权调度4.轮转发调度*\n);printf(**********************************************************************);printf(\n请选择调度的方法:);scanf(%d,&m);if(m!=1&&m!=2&&m!=3&&m!=4){printf(输入错误!重新输入:);scanf(%d,&m);if(m!=1&&m!=2&&m!=3&&m!=4){printf(输入错误!重新输入:);9scanf(%d,&m);if(m!=1&&m!=2&&m!=3&&m!=4){printf(输入错误!重新输入:);scanf(%d,&m);if(m!=1&&m!=2&&m!=3&&m!=4){printf(输入错误!重新输入:);scanf(%d,&m);}}}}printf(请输入进程的个数:);scanf(%d,&number);printf(\n开始时用户进程均为就绪状态,运行时间随机产生\n\n);SqListsq;InitList(sq);for(intr=0;rnumber;r++){pcb[r].CPUtime=0;}for(inti=0;inumber;i++)10{pcb[i].Priority=rand()%50;while(1){if(pcb[i].Priority20){pcb[i].Priority=rand()%50;}elsebreak;}pcb[i].Alltime=rand()%40;while(1){if(pcb[i].Alltime10){pcb[i].Alltime=rand()%40;}elsebreak;}}11for(intj=0;jnumber;j++){ListLength(sq);ListInsert_Sq(sq,ListLength(sq),pcb[i]);}if(m==1){printf(\n****************程序演示开始*****************\n);intcoun=0;//计数变量intwait[100];//等待时间数组wait[0]=0;intAllwait=0;for(inti1=0;i1number;i1++){printf(下面开始调用第%d个进程；\n,i1);printf(开始时间为%d执行时间为%d\n,coun,pcb[i1].Alltime);coun+=pcb[i1].Alltime;if(i1!=0){wait[i1]=pcb[i1-1].Alltime+wait[i1-1];}}for(inti2=0;i2number;i2++)12{Allwait=wait[i2]+Allwait;}printf(平均等待时间为:%d\n,Allwait/number);}if(m==2){intmin=pcb[0].Alltime;intwait1[100];wait1[0]=0;intin=0;intcoun1=0;printf(*****************最短作业优先调度!********************\n);cout进程所需时间分别是:endl;for(i=0;inumber;i++){coutpcb[i].Alltimeendl;}printf(进程调度的顺序为:);for(i=0;inumber;i++){min=50;for(j=0;jnumber;j++)13{if(pcb[j].Alltimemin){min=pcb[j].Alltime;in=j;}}printf(%d,in+1);pcb[in].Alltime+=50;}}if(m==3){printf(ID优先级运行总时间进程状态\n);for(intk=0;knumber;k++){printf(%d%d%d就绪\n,k+1,pcb[k].Priority,pcb[k].Alltime);}printf(\n***********************程序调度演示开始***********************\n);for(intf=1;f1000;f++)14{intcount=0,count1=0;for(inti=0;inumber;i++){ppp[i]=pcb[i].Priority;if(pcb[i].Alltime!=0){count1++;}}count1--;time=time+count1*4;max=Max(ppp,number);if(pcb[max].Alltime==0){ppp[max]=-1;pcb[max].Priority=-1;max=Max(ppp,number);}pcb[max].Priority-=4;pcb[max].Alltime-=4;pcb[max].CPUtime+=4;if(pcb[max].Alltime=0){pcb[max].Alltime=0;}15for(intw=0;wnumber;w++){if(pcb[w].Alltime==0){ppp[w]=-1;pcb[w].Priority=-1;}}for(inte=0;enumber;e++){pcb[e].Priority++;}printf(\n##########第%d个进程正在执行!##########\n,max+1);printf(\n第%d次调度结束，运行结果为:\n\n,f);printf(ID优先级需要总时间执行时间\n);for(intk=0;knumber;k++){printf(%d%d%d%d\n,k+1,16pcb[k].Priority,pcb[k].Alltime,pcb[k].CPUtime);}for(intl=0;lnumber;l++){if(pcb[l].Alltime==0)count++;}if(count==number){break;}}time1=time/number;printf(\n*****************************用户进程全部执行完毕!******************************);printf(\n\n平均等待时间是:);printf(%d\n\n,time1);}if(m==4){printf(ID运行总时间进程状态\n);for(intk=0;knumber;k++)17{printf(%d%d就绪\n,k+1,pcb[k].Alltime);}printf(\n***********************程序调度演示开始***********************\n);for(intf=1;f1000;f++){intcount=0;for(i=0;inumber;i++){if(pcb[i].Alltime==0){continue;}if(pcb[i].Alltime0){pcb