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

HUNANUNIVERSITY进程调度算法题目进程调度算法学生姓名学生学号专业班级完成日期 2013.12.06一、实验题目实现短进程优先调度算法（SPF）实现时间片轮转调度算法（RR）二、实验目的通过对进程调度算法的设计，深入理解进程调度的原理。进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。进程调度分配处理机，是控制协调进程对CPU的竞争，即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。三、实验内容1.先来先服务（FCFS）调度算法原理：每次调度是从就绪队列中，选择一个最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。该进程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最普遍和最简单的方法。它优先考虑在系统中等待时间最长的作业，而不管要求运行时间的长短。按照就绪进程进入就绪队列的先后次序进行调度，简单易实现，利于长进程，CPU繁忙型作业，不利于短进程，排队时间相对过长。2.时间片轮转调度算法RR原理：时间片轮转法主要用于进程调度。采用此算法的系统，其程序就绪队列往往按进程到达的时间来排序。进程调度按一定时间片(q)轮番运行各个进程.进程按到达时间在就绪队列中排队，调度程序每次把CPU分配给就绪队列首进程使用一个时间片，运行完一个时间片释放CPU，排到就绪队列末尾参加下一轮调度，CPU分配给就绪队列的首进程。固定时间片轮转法：1所有就绪进程按FCFS规则排队。2处理机总是分配给就绪队列的队首进程。3如果运行的进程用完时间片，则系统就把该进程送回就绪队列的队尾，重新排队。4因等待某事件而阻塞的进程送到阻塞队列。5系统把被唤醒的进程送到就绪队列的队尾。可变时间片轮转法：1进程状态的转换方法同固定时间片轮转法。2响应时间固定，时间片的长短依据进程数量的多少由T=N×(q+t)给出的关系调整。3根据进程优先级的高低进一步调整时间片，优先级越高的进程，分配的时间片越长。3.算法类型:4.模拟程序可由两部分组成，先来先服务(FCFS)调度算法，时间片轮转。流程图如下图所示:四打印的源程序及附上的注释#include<iostream>usingnamespacestd;#defineP_NUM3//cpu4种状态就绪运行等待完成enumstate{ ready, waiting, block, finish};//PCB进程控制块包括名称、优先级、占用CPU时间、需要时间structpcb{ charname[4]; intpriority; intcputime; intneedtime; intcount; intround; stateprocess; pcb*next;//构建优先级队列};//建立一个优先权的队列pcb*get_process(){ pcb*q=NULL;; pcb*t=NULL;; pcb*p=NULL; inti=0; cout<<"inputnameandtime"<<endl; while(i<P_NUM){ q=(structpcb*)malloc(sizeof(pcb)); cin>>q->name; cin>>q->needtime; q->cputime=0; q->priority=P_NUM-i; q->process=ready; q->next=NULL; if(i==0){ p=q; t=q; } else{ t->next=q; t=q; } i++; }//while returnp;}//输出当前队列各个进程各种状态voiddisplay(pcb*p){ cout<<"name"<<""<<"cputime"<<""<<"needtime"<<""<<"priority"<<""<<"state"<<endl; while(p){ cout<<p->name; cout<<""; cout<<p->cputime; cout<<""; cout<<p->needtime; cout<<""; cout<<p->priority; cout<<""; switch(p->process){ caseready:cout<<"ready"<<endl;break; casewaiting:cout<<"waiting"<<endl;break; caseblock:cout<<"block"<<endl;break; casefinish:cout<<"finish"<<endl;break; } p=p->next; }}//检查队列中进程是否完成intprocess_finish(pcb*q){ intbl=1; while(bl&&q){ bl=bl&&q->needtime==0; if(q->next!=NULL) q=q->next; } returnbl;}//找到优先权最大的进程执行voidcpuexe(pcb*q){ pcb*t=q; inttp=0; while(q){ if(q->process!=finish){ q->process=ready; if(q->needtime==0){ q->process=finish; } } if(tp<q->priority&&q->process!=finish){ tp=q->priority; t=q; } q=q->next; } if(t->needtime!=0){ t->needtime--; t->process=waiting; t->cputime++; }}//优先权调度voidpriority_cal(){ pcb*p=NULL; p=get_process(); intcpu=0; while(!process_finish(p)){ cpu++; cout<<"cputime:"<<cpu<<endl; cpuexe(p); display(p); } printf("Allprocesseshavefinished,pressanykeytoexit");}//初始化界面voiddisplay_menu(){ cout<<"选择CPU调度算法："<<endl; cout<<"1优先权"<<endl; cout<<"2转轮法"<<endl; cout<<"3退出"<<endl;}//轮转法调度初始化pcb*get_process_round(){ pcb*q=NULL; pcb*t=NULL; pcb*p=NULL; inti=0; cout<<"inputnameandtime："<<endl; while(i<P_NUM){ q=(structpcb*)malloc(sizeof(pcb)); cin>>q->name; cin>>q->needtime; q->cputime=0; q->round=0; q->count=0; q->process=ready; q->next=NULL; if(i==0){ p=q; t=q; } else{ t->next=q; t=q; } i++; }//while returnp;}//cpu单位时间为1voidcpu_round(pcb*q){ q->cputime+=1; q->needtime-=1; if(q->needtime<=0){ q->needtime=0; q->process=finish; return; } q->count++; q->round++; q->process=waiting;}//轮转法找到下一个可以CPU执行的程序pcb*get_next(pcb*k,pcb*head){ pcb*t; t=k; t=t->next; while(t&&t->process==finish){ t=t->next; } if(t==NULL){ t=head; while(t->next!=NULL&&t->process==finish){ if(t->next==k) t=t->next; if(t->next!=NULL) t=t->next; } } returnt;}//整理队列里的进程状态voidset_state(pcb*p){ while(p){ if(p->needtime<=0){ p->process=finish; } if(p->process==waiting){ p->process=ready; } p=p->next; }}//每个CPU时间后输出每个进程状态voiddisplay_round(pcb*p){ cout<<"NAME"<<""<<"CPUTIME"<<""<<"NEEDTIME"<<""<<"COUNT"<<""<<"ROUND"<<""<<"STATE"<<endl; while(p){ cout<<p->name; cout<<""; cout<<p->cputime; cout<<""; cout<<p->needtime; cout<<""; cout<<p->count; cout<<""; cout<<p->round; cout<<""; switch(p->process){ caseready:cout<<"ready"<<endl;break; casewaiting:cout<<"waiting"<<endl;break; casefinish:cout<<"finish"<<endl;break; } p=p->next; }}//转轮调度voidround_cal(){ pcb*p=NULL; pcb*r=NULL; p=get_process_round(); intcpu=0; r=p; while(!process_finish(p)){ cpu+=1; cpu_round(r); r=get_next(r,p);