操作系统课程设计-CPU时间片轮转算法

PAGE1目录TOC\o"1-1"\h\u7787一、设计目的 19430二、设计内容 16063三、设计原理 214667四、算法实现 2176五、流程图 45569六、源程序 51282七、运行示例及结果分析 126993八、心得体会 147650九、参考资料 14操作系统课程设计-时间片轮转法进行CPU调度设计目的处理机调度是操作系统中非常重要的部分。为深入理解进程管理部分的功能，设计时间片轮转法进行CPU调度算法，模拟实现处理机的调度。通过本次课程设计理解进程调度的概念，深入理解进程控制的功能、进程的创建与删除以及进程各个状态之间的转换过程，实现时间片轮转算法调度进程。学会使用C++语言编写和调试一个简单的时间片轮转法进行CPU调度的程序。加深了解有关进程控制块和进程队列的概念。并体会时间片轮转算法的具体实现方法。设计内容用时间片轮转算法模拟单处理机调度。建立一个进程控制块PCB来代表。PCB包括：进程名、链接指针、到达时间、估计运行时间、剩余时间和进程状态。进程状态分为就绪（P）、运行（W）和完成（F）。为每个进程任意确定一个要求运行时间和到达时间。按照进程到达的先后顺序排成一个循环队列。再设一个对首指针指向第一个到达进程的首址。执行处理机调度时，开始选择对首的第一个进程运行。另外再设一个当前运行进程的指针，指向当前正运行的进程。执行：a)预计运行时间减1；b)输出当前运行进程的名字。进程执行一次后，若该进程的剩余运行时间为零，则将该进程的状态置为完成态F，并退出循环队列；若不为空，则将其移至队尾。继续在运行队首的进程。若就绪队列不空，则重复上述的（5）和（6）步骤直到所有进程都运行完为止。在所设计的调度程序中，要求包含显示或打印语句。以便显示或打印每次选中进程的名称及运行一次后队列的变化情况。三、设计原理在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程再一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能再给定的时间内响应所有用户的请求。算法实现1）系统初始化时给每一个进程赋以一个needtime，并将所有进程按needtime从小到大的次序排成一个队列。取队头进程,并投入运行。采用相对固定时间片（Time_piece），进程每执行一次，进程占用的CPU时间加Time_piece。若进程没有运行完，进程needtime减Time，并排到就绪队列的尾部。如果尚有进程在队列中,那么转入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源程序Dos版：#include"iostream.h"#include"string.h"#include"stdlib.h"typedefstructnode{ charname[10];//进程名 intTime_piece;//时间片 intNeed_time;//还需要的时间 intCount;//计数器 charState;//进程的状态 structnode*next;//链指针 intArrive_time;//到达时间}PCB;//run为当前运行进程指针,start为就绪队列头指针//end为就绪队列尾指针,finish为完成队列头指针PCB*run,*start,*end,*finish;intN;//进程个数intCpu_time;//需要的CPU时间voidinsert(PCB*p){//时间片插入函数if(start->next==NULL){ PCB*q=start; if(p->Arrive_time<q->Arrive_time){ start=p; p->next=q; q->next=NULL; end=q; }else{ q->next=p; p->next=NULL; end=p; } }else{ PCB*q=start;PCB*s=start->next;while(s!=NULL){ if(q->Arrive_time>p->Arrive_time){ p->next=q; start=p; return; }else{ if(s->Arrive_time>p->Arrive_time){ q->next=p; p->next=s; return; }else{ q=q->next; s=s->next; } } } s->next=p; end=p; }}voidinsert2(PCB*p){ end->next=p;//将新的PCB插入在当前就绪队列的尾end=p;p->next=NULL;}voidshow(PCB*p)//输出函数{ cout<<"进程名到达时间剩余时间状态\n";// if(run!=NULL)//如果运行指针不为空,就输出当前正在运行的进程的PCB{ cout<<""<<p->name<<"\t"<<p->Arrive_time<<"\t"<<p->Need_time<<"\t"<<p->State<<"\n"; }}voidcreate()//时间片算法创建进程函数{ cout<<"请输入所需要运行的进程个数:"; cin>>N; PCB*p; intTime_piece;start=NULL;//就绪队列头指针finish=NULL;//完成队列头指针run=NULL;//运行队列指针 cout<<"请输入时间片长度:"; cin>>Time_piece;for(inti=1;i<=N;i++){//输入进程名字和所需时间,创建进程的PCBp=(PCB*)malloc(sizeof(PCB)); cout<<"请输入第"<<i<<"个进程的名字:"; cin>>p->name; cout<<"预计运行的时间:"; cin>>p->Need_time; cout<<"到达时间:"; cin>>p->Arrive_time; Cpu_time=0; p->Count=0;//计数器 p->State='P';//进程的初始状态设为就绪'W' p->Time_piece=Time_piece;//时间片的初始值 if(start!=NULL){ insert(p);//若就绪队列不为空,将其插入就绪队列 }else{//创建就绪队列的第一个PCB p->next=start; start=p;//头指针 end=p; //尾指针 }} cout<<endl<<endl<<"\t使用时间片轮转算法输出结果:\n";cout<<"*********************************************************\n";run=start;//将就绪队列的第一个进程投入运行start=start->next;run->State='W';}voidfirstin(){//将就绪队列的第一个进程放入运行队列 run=start; run->State='W';//改变其状态 start=start->next;}voidroundrobin(){//时间片算法函数 intm=0; while(run!=NULL){ if(run->Arrive_time>Cpu_time){ Cpu_time=Cpu_time+1;//每运行一次cputime加一 }else{ if(m==0){ cout<<"~~~~~~~~~~~~~~~~~~~~~~~~进程"<<run->name<<"开始啦~~~~~~~~~~~~~~~~~~~~~~~\n"; m++; } run->Need_time=run->Need_time-1;//每运行一次needtime减一 if(run->Need_time!=0) show(run); Cpu_time=Cpu_time+1;//每运行一次cputime加一 run->Count=run->Count+1;//每运行一次计数器count加一 if(run->Need_time==0){//若运行完后 run->next=finish; finish=run;//将其插入完成队列头部 run->State='F';//将其状态改为完成态"F" show(run);cout<<"~~~~~~~~~~~~~~~~~~~~~~~~进程"<<run->name<<"结束啦~~~~~~~~~~~~~~~~~~~~~~~\n"; run=NULL;//将运行队列清空 if(start!=NULL){ firstin();//若就绪对列不空，将第一个进程投入运行 cout<<"~~~~~~~~~~~~~~~~~~~~~~~~进程"<<run->name<<"开始啦~~~~~~~~~~~~~~~~~~~~~~~\n"; } }else{ if(run->Count==run->Time_piece){//如果时间片到 run->Count=0;//计数器置0 if(start!=NULL){//若就绪队列不空 run->State='W'; insert2(run);//将进程插入到就绪队列中等待轮转 firstin();//将就绪队列的第一个进程投入运行 cout<<"~~~~~~~~~~~~~~~~~~~~~~~~进程"<<run->name<<"开始啦~~~~~~~~~~~~~~~~~~~~~~~\n"; } } } } }cout<<"*********************************************************\n";}voidmain(){//主函数 create();//建立就绪队列 roundrobin();//调用时间片轮转调度算法的函数}MFC版：voidCYanDlg::OnButton2(){ UpdateData(TRUE); PCB*p; if(i<N){//输入进程名字和所需时间,创建进程的PCB p=(PCB*)malloc(sizeof(PCB)); cputime=0; p->arrivetime=m_arrivetime; p->needtime=m_runtime; p->name=m_name; p->count=0;//计数器 p->state='P'; p->time=T;//时间片赋值 if(ready!=NULL){ In1(p);//若就绪队列不为空,将其插入就绪队列 }else{//创建就绪队列的第一个PCB p->next=ready; ready=p;//头指针 tail=p; //尾指针 } i++; Show(p); if(i==N){ m_show+="~~~~~~~~~~~~~~~~~~~~~~~~~~~完成~~~~~~~~~~~~~~~~~~~~~~~~\r\n"; m_show+="\r\n"; } } if(i==N){run=ready;//将就绪队列的第一个进程投入运行ready=ready->next;run->state='W'; } UpdateData(false); }voidCYanDlg::In1(PCB*p){if(ready->next==NULL){ PCB*q=ready; if(p->arrivetime<q->arrivetime){ ready=p; p->next=q; q->next=NULL; tail=q; }else{ q->next=p; p->next=NULL; tail=p; } }else{ PCB*q=ready;PCB*s=ready->next;while(s!=NULL){ if(q->arrivetime>p->arrivetime){ p->next=q; ready=p; return; }else{ if(s->arrivetime>p->arrivetime){ q->next=p; p->next=s; return; }else{ q=q->next; s=s->next; } } } s->next=p; tail=p; }}voidCYanDlg::OnButton3(){//时间片算法调用程序 while(run!=NULL){ if(run->arrivetime>cputime){ cputime=cputime+1; }else{ if(i==N){ m_show+="~~~~~~~~~~~~~~~~~~~~~~~~进程"+(CString)(run->name+'0')+"开始啦~~~~~~~~~~~~~~~~~~~~~~~\r\n\r\n"; i++; } run->needtime=run->needtime-1; if(run->needtime!=0) Show(run);//输出进程信息 cputime=cputime+1; run->count=run->count+1; if(run->needtime==0){//运行完成 run->next=finish; finish=run; run->state='F'; Show(run); m_show+="~~~~~~~~~~~~~~~~~~~~~~~~进程"+(CString)(run->name+'0')+"结束啦~~~~~~~~~~~~~~~~~~~~~~~\r\n"; run=NULL; if(ready!=NULL){ InFirst();//若就绪对列不空，将第一个进程投入运行 m_show+="\r\n"; m_show+="~~~~~~~~~~~~~~~~~~~~~~~~进程"+(CString)(run->name+'0')+"开始啦~~~~~~~~~~~~~~~~~~~~~~~\r\n\r\n"; } }else if(run->count==run->time){//时间片结束 run->count=0;//计数器置0 if(ready!=NULL){//若就绪队列不空 run->state='P'; In2(run);//将进程插入到就绪队列等待轮转 InFirst();//将就绪队列的第一个进程投入运行 } m_show+="\r\n"; m_show+="~~~~~~~~~~~~~~~~~~~~~~~~进程"+(CString)(run->name+'0')+"开始啦~~~~~~~~~~~~~~~~~~~~~~~\r\n\r\n"; } } } UpdateData(false);}运行示例及结果分析图2图3图4结果分析：首先，将进程1,2依次输入PCB并输出他们的信息，如图2。进程按照到达时间从小到大排序，即先运行进程2，将其状态改为W。设置的时间片长度为3，进程2运行3次后，剩余时间