CPU时间片轮转算法

CPU时间片轮转算法时间片轮转法进行CPU调度一、实验目的1、学会使用C++语言编写和调试一个简单的时间片轮转法进行CPU调度的程序。2、加深了解有关进程控制块和进程队列的概念。3、并体会时间片轮转算法的具体实现方法。4、理解进程调度的概念，深入理解进程控制的功能、进程的创建与删除以及进程各个状态之间的转换过程，实现时间片轮转算法调度进程。二、实验内容用时间片轮转算法模拟单处理机调度。（1）建立一个进程控制块PCB来代表。PCB包括：进程名、链接指针、到达时间、估计运行时间、剩余时间和进程状态。进程状态分为就绪（P）、运行（W）和完成（F）。（2）为每个进程任意确定一个要求运行时间和到达时间。（3）按照进程到达的先后顺序排成一个循环队列。再设一个对首指针指向第一个到达进程的首址。（4）执行处理机调度时，开始选择对首的第一个进程运行。另外再设一个当前运行进程的指针，指向当前正运行的进程。（5）执行：a)预计运行时间减去时间片长度；b)输出当前运行进程的名字。（6）进程执行一次后，若该进程的剩余运行时间为零，则将该进程的状态置为完成态F，并退出循环队列；若不为空，则将其移至队尾。继续在运行队首的进程。（7）若就绪队列不空，则重复上述的（5）和（6）步骤直到所有进程都运行完为止。三、实验原理在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程再一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能再给定的时间内响应所有用户的请求。四、算法实现1）系统初始化时给每一个进程赋以一个needtime，并将所有进程按needtime从小到大的次序排成一个队列。2）取队头进程,并投入运行。3）采用相对固定时间片（Time_piece），进程每执行一次，进程占用的CPU时间加Time_piece。4）若进程没有运行完，进程needtime减Time，并排到就绪队列的尾部。5）如果尚有进程在队列中,那么转入2）PCB结构：N进程个数name进程名Time_piece进程优先数/进程轮转时间片Cpu_time进程占用的CPU时间Need_time进程到完成还要的时间Count计数器State进程状态(P,W,F)Arrive_time到达时间next链指针run当前运行进程指针start就绪队列头指针end就绪队列尾指针finish完成队列头指针voidinsert(PCB*p)//时间片插入函数voidcreate()//时间片算法创建进程函数voidroundrobin()//时间片算法函数voidfirstin()//运行就绪队列的第一个进程五、流程图图1六、实验结果图2图3图4结果分析：首先，将进程a,b依次输入PCB并输出他们的信息，如图2。进程按照到达时间从小到大排序，即先运行进程a，将其状态改为W。设置的时间片长度为3，进程a运行1次后，剩余时间不为0，则将其调至队尾。CPU开始运行队首的进程b，运行1次后，剩余时间不为0，再将其调至队尾。CPU继续运行队首的进程a，运行1次后，进程a的剩余时间为0，则将其调至队尾。。。。直到某个进程的剩余时间为0修改其状态为F并从队列中删除。当两个进程的剩余时间都为0时，队列为空，执行结束。七、心得体会通过这次课程设计，我的收获颇丰。课程设计之初我对时间片轮转法基本上没有什么深入的研究，只是通过课堂的讲解大致了解其思想。经过这将近两周的学习后，我对时间片轮转算法的理解有了更进一步的提高，并通过自己设计程序，自己试验，自己调试对算法的内容更进一步的深刻认识。八、源代码#includeusingnamespacestd;structPCB{charName[256];//进程名structPCB*Next;//链接指针intTime_Arrive;//到达时间intTime_Run;//运行时间intTime_Remain;//剩余时间//charState;//进程状态};intmain(){intamount,timeslice;//进程个数,时间片长度inti,j,m,n;structPCB*readyfront=newPCB,*readyrear;coutcinamount;coutcintimeslice;structPCB*proc[16];for(i=0;i{proc[i]=newPCB;coutcinproc[i]-Name;coutcinproc[i]-Time_Arrive;coutcinproc[i]-Time_Run;}//进程按照到达时间排序进入就绪队列for(j=0;j{for(i=amount-1;ij;i--){if(proc[i]-Time_Arrive{structPCB*temp;temp=proc[i];proc[i]=proc[i-1];proc[i-1]=temp;}proc[i-1]-Next=proc[i];}}proc[amount-1]-Next=NULL;readyfront-Next=proc[0];readyrear=proc[amount-1];//readyrear-Next=NULL;//输出结果coutcoutfor(m=0;m{coutcout}coutwhile(readyfront!=readyrear){coutcoutcoutreadyfront-Next-Time_Run=readyfront-Next-Time_Run-timeslice;readyfront-Next-Time_Remain=readyfront-Next-Time_Run;if(readyfront-Next-Time_Remain0){coutcout}else{coutcoutcout^^^^^^^^^^^^^^^if(readyfront-Next==readyrear){readyrear=readyfront;//置空队列}else{readyfront-Next=readyfront-Next-Next;//队头后移}}coutif(readyfront-Next-Time_Remain0){readyrear-Next=readyfront-Next;readyrear=readyfront-Next;//队头变队尾readyfront-Next=readyfront-Next-Next;//队头后移readyrear-Next=NULL;}}return0;}