操作系统进程调度实验报告

计算机学院计算机科学与技术专业班姓名学号教师评定_________________实验题目进程调度一、实验目的用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解。二、实验内容和要求设计一个有N个进程并发的进程调度程序，要采用FIFO（先进先出）、简单时间片轮转法、多级反馈队列调度算法这三种算法。每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息：进程名、到达时间、需要运行时间、已运行时间、进程状态等等。进程的到达时间及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的运行时间以时间片为单位进行计算。每个进程的状态可以是就绪W（Wait）、运行R（Run）、或完成F(Finish)三种状态之一。就绪进程获得CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应分配时间片给就绪队列中排在该进程之后的进程，并将它插入就绪队列队尾。每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB，以便进行检查。重复以上过程，直到所要进程都完成为止。三、实验原理及设计方案1、FIFO算法：其基本思想是所有进程按先进来就排在前头，一个一个往后接下去的顺序排成一个队列，总是把全部的处理机分配给先进来的进程，然后等待它运行完，释放CPU资源，把处理机重新分配给下一个先进来的进程。直至所有的进程运行完毕。2、轮转法：所有就绪进程按FCFS排成一个队列，总是把处理机分配给队首的进程，各进程占用CPU的时间片相同。如果运行进程用完它的时间片后还未完成，就把它送回到就绪队列的队尾，把处理机重新分配给队首的进程。直至所有的进程运行完毕。3、多级反馈队列调度算法。其基本思想是：当一个新进程进入内在后，首先将它放入第一个队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚为完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行，以此类推。四、流程图1.FIFO和轮转法：开始初始化PCB，输入进程信息各进程按到达到时间先后顺序排成一个队列就绪队列为空？就绪队列首进程投入运行时间片到，运行进程运行时间+1i==1ori==2选择算法i==1或i==2i==1FIFOs算法时间轮转法i==2Ni==1i==2运行时间是否小于所需要时间Y执行进程进程执行完毕，调度下一进程运行时间是否等于所需时间YN将该进程放到就绪队列的队尾，再等待激发执行下一个进程结束2、多级反馈队列算法：五、给出程序中源程序名和执行程序名1、FIFO和时间轮转法源程序名：FIFOlunzhuan，执行程序名：FIFOANDLUNZHUAN.CPP2、多级反馈队列源程序名：duoji，执行程序名：d.cpp六、程序清单1.FIFO和时间轮转#includestdio.h#includestdlib.h#includeconio.h#definegetpch(type)(type*)malloc(sizeof(type))/*用getpcb(type)给type类型的变量申请一个空间*/structpcb{/*定义进程控制块PCB*/charname[10];/*进程名*/charstate;/*进程状态*/intntime;/*进程需要运行时间*/intrtime;/*进程已经运行的时间*/开始运行时间是否到达所需时间Y进程完成，撤销该进程Y将该进程插入到下一个就绪队列的队尾初始化PCB,输入进程信息各进程按到达时间先后顺序排列就绪队列i空N就绪队列首进程投入运行当前就绪队列时间片到，运行时间+时间片N指向下一个就绪队列就绪队列i空?结束Ystructpcb*link;/*定义了一个指向pcb结构类型的指针link作为自己的成员函数*/}*ready=NULL,*p;/*定义了两个指向pcb结构类型的指针ready和p,ready的初值为空*/typedefstructpcbPCB;/*定义PCB为structpcb的别名*/voidsort()/*对进程进行轮转调度排列函数*/{PCB*first;if(ready==NULL)/*如果就绪队列为空*/{ready=p;/*将新建进程放入就绪队列中，将ready指向队首进程*/}else/*就绪队列中有进程在等待，将新建进程插入到队尾*/{first=ready;/*first指针指向队首进程*/while(first-link!=NULL)first=first-link;/*当first指针没有指向队尾时，指针后移*/first-link=p;/*将P指向的进程插入队尾*/}}voidinput()/*建立进程控制块函数*/{inti,num;printf(\n输入进程个数：);scanf(%d,&num);for(i=0;inum;i++){printf(\n进程号No.%d:\n,i);p=getpch(PCB);/*给进程申请一个空间,并用指针p指向这个空间*/printf(\n进程名字:);scanf(%s,p-name);/*输入进程的名字*/printf(\n进程运行时间:);scanf(%d,&p-ntime);/*输入进程的运行时间*/printf(\n);p-rtime=0;/*进程已运行的时间的初值为0*/p-state='w';p-link=NULL;/*新建进程的指针域为空*/sort();/*调用sort1函数*/}}intspace()/*计算进程控制块个数的函数*/{intl=0;PCB*pr=ready;/*pr指向队首进程*/while(pr!=NULL)/*pr为空,则说明计数完成*/{l++;pr=pr-link;/*pr向下以一个进程*/}return(l);}voiddisp(PCB*pr)/*建立进程显示函数,用于显示使用FCFS算法的当前进程*/{printf(\nname\tstate\tntimertime\n);printf(|%s\t,pr-name);/*显示当前进程的进程名*/printf(|%c\t,pr-state);/*显示当前进程的状态*/printf(|%d\t,pr-ntime);/*显示当前进程的运行时间*/printf(|%d\t,pr-rtime);/*显示当前进程的已运行时间*/printf(\n);}voidcheck()/*进程查看函数*/{PCB*pr;printf(\n***当前正在运行的进程是:%s,p-name);/*显示当前运行进程*/disp(p);/*标志变量不为1，调用disp1()函数*/pr=ready;/*pr指向等待队列的队首进程*/printf(\n****当前就绪队列状态为:\n);/*显示就绪队列状态*/while(pr!=NULL)/*就绪队列不为空时*/{/*根据标识符值显示不同算法下的就绪队列状态*/disp(pr);pr=pr-link;}}voiddestroy()/*建立进程撤消函数(进程运行结束,撤消进程)*/{printf(\n进程[%s]已完成.\n,p-name);free(p);}voidrunning1()/*建立进程就绪函数(进程运行时间到,置就绪状态)*/{(p-rtime)+=2;/*进程的运行时间加2*/if(p-rtime=p-ntime)/*如果已运行时间等于进程运行所需的时间,则将进程释放*/{p-rtime=p-ntime;printf(\n\n****该进程执行完成的状态：\n);p-state='F';disp(p);destroy();/*调用destroy函数*/}else{p-state='w';/*将状态置为等待*/sort();/*调用sort1函数*/}}voidrunning2(){while(p-rtimep-ntime)//运行时间还没达到所需时间时继续运行{p-state='R';(p-rtime)++;}printf(\n\n****该进程执行完成的状态：\n);p-state='F';disp(p);destroy();}voidmain()/*轮转法，FCFS算法的程序入口*/{inti,len,h=0;/*len用来存放进程的个数*/charch;printf(*********************************************************\n);printf(计科班\n);printf(FIFO算法或时间轮转法\n);printf(*********************************************************\n);input();/*调用input1函数，输入进程信息*/len=space();/*进程个数赋给len*/printf(\n选择算法:);scanf(%d,&i);switch(i){case1:printf(FIFO算法：\n);break;case2:printf(时间片轮转算法：\n);break;default:printf(FAULSE);}if(i==1||i==2){while((len!=0)&&(ready!=NULL)){ch=getchar();h++;printf(\nTheexecutenumber:%d\n,h);p=ready;/*将队首指针赋给p*/ready=p-link;/*ready指向原p的下一个进程*/p-link=NULL;/*p的link赋空*/p-state='R';/*p的运行状态置为运行*/check();/*调用check函数，运用值传递*/if(i==1)running2();if(i==2)running1();/*调用running1函数*/printf(\n按任意键继续......);ch=getchar();}printf(\n\n进程已完成.\n);ch=getchar();}}2、多级反馈队列算法#includestdio.h#includestdlib.h#includeconio.h#definegetpch(type)(type*)malloc(sizeof(type))structpcb{charname[10];charstate;intatime;intntime;intrtime;intqueue;structpcb*link;}*ready=NULL,*ready1=NULL,*p;typedefstructpcbPCB;voidsort()/*建立对进程进行提交时间排列函数*/{PCB*first,*second;intinsert=0;if((ready==NULL)||((p-atime)(ready-atime)))/*进程提交时间最短的,插入队首*/{p-link=ready;ready=p;}else/*进程比较提交时间,插入适当的位置中*/{first=ready;second=first-link;while(second!=NULL){if((p-atime)(second-atime))/*若插入进程比当前进程提交时间短,*/{/*插入到当前进程前面*/p-link=second;first-link=p;second=NULL;insert=1;}else/*插入进程到达时间最长,则插入到队尾*/{first=first-link;second=second-link;}}if(insert==0)first-link=p;}}voidinput()/*建立进程控制块函数*/{inti,num;printf