进程管理和调度的算法实现

《操作系统》课程实验（二）—进程管理和调度的算法实现一、实验目的进程调度是处理机管理的核心内容。本设计要求用高级语言编写和调试一个简单的进程调度程序。通过本实验可以加深理解有关进程控制块、进程队列的概念，并体会和了解优先权调度算法和时间片轮转调度算法的具体实施办法。二、实验内容1．设计进程控制块PCB表结构，分别适用于优先权调度算法和时间片轮转调度算法。2．PCB结构包括以下信息：进程名、进程优先数（或轮转时间片），进程所占用的CPU时间，进程的状态，当前队列指针等。根据调度算法的不同，PCB结构的内容可以作适当的增删。3．建立进程就绪队列。对两种不同算法编制入链子程序。4．编制两种进程调度算法：a）优先数调度；b）时间片轮转调度。允许用户在程序运行时选择使用某一种调度算法。三、编程工具：C、Java、VC或其它可视化语言平台任选四、具体设计要求及有关说明选用优先数算法和简单时间片轮转法对五个进程进行调度，每个进程可有三种状态：运行状态（RUN）、就绪状态（READY）和完成状态。并假定初始状态为就绪状态。1．设计进程控制块PCB结构如下：NAME//进程标识符；PRIO/ROUND//PRIO表示进程优先数，ROUND表示进程轮转时间片大小；CPUTIME//进程占用CPU时间；COUNT//计数器；NEEDTIME/进程到完成还要的CPU时间；STATE//进程的状态；NEXT//链指针2．进程控制块链结构如图所示。…∧……∧…∧………READYFINISHRUNTAIL……其中：RUN——当前运行进程指针；READY——就绪队列头指针；TAIL——就绪队列尾指针；FINISH——完成队列头指针。为了便于处理，程序中进程的运行时间以时间片为单位计算。各进程的优先数或轮转时间片数以及进程需运行的时间片数的初值均由用户给定。3．程序说明：a）在优先数算法中，进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。在轮转法中，采用固定时间片，时间片数为2，进程每执行一次，CPU时间片数加2，进程还需要的时间片数减2，并排到就绪队列的尾上。b）程序结构说明如下：整个程序由CREATE，FIRSTIN，INSERT1，INSERT2，PRINT，PRISCH和ROUNDSCH过程组成。其中：CREATE的功能是创建新的进程，即创立进程的PCB，并将此PCB链入到就绪队列中去。FIRSTIN的功能是将就绪队列中的第一个进程投入运行。INSERT1的功能是把还未完成且优先数小于别的进程PCB按进程优先数的顺序插入到就绪队列中。INSERT2是轮转法使用的过程，将执行了一个单位时间片数（为2）且还未完成的进程的PCB插入到就绪队列的队尾。PRINT打印每执行一次后的所有进程的状态，这里，就绪（等待）用“W”代表。PRISCH按优先数算法调度进程。ROUNDSCH按时间片轮转法调度进程。c）主程序中定义了PCB的结构和其它变量NUMBER——进程数，ALGO为10个字符长的字符串，存放要求输入的算法的名，输入“PRIORITY”表示调用优先数算法，输入“ROUNDROBIN”表示调用循环轮转法，要求用户在程序运行时输入其中的一个。五、实验描述#includeiostream#includevector#includealgorithm#includeiomanipusingnamespacestd;bool_state=0;classPCB//类定义PCB表，适用于优先数{public:intID;intpriority;intCPUtime;intALLtime;intState;//1运行2就绪3等待intflag;voidset_PCB(inta,intb,intc,intd,inte,intf){ID=a;priority=b;CPUtime=c;ALLtime=d;State=e;flag=f;}};classPCB2{public:intID;intCPUtime;intALLtime;intState;intflag;voidset_PCB2(inta,intb,intc,intd,inte){ID=a;CPUtime=b;ALLtime=c;State=d;flag=e;}};boolpriority_sort_higher(constPCB&m,constPCB&n)//sort函数，定义按优先数排序，当优先数相同时按序号排序（即先进先出）{if(m.priority==n.priority)returnm.IDn.ID;returnm.priorityn.priority;}voidpriority_way(vectorPCB&pcb,vectorPCB&wait){vectorPCB::iteratorit1;it1=pcb.begin();intflag=5;while(flag){wait.erase(wait.begin());(*it1).State=1;(*it1).priority-=3;(*it1).CPUtime+=1;(*it1).ALLtime-=1;if((*it1).ALLtime==0){flag-=1;(*it1).flag=1;coutleftsetw(10)(*it1).IDsetw(10)(*it1).Statesetw(10)(*it1).prioritysetw(10)(*it1).CPUtimesetw(10)(*it1).ALLtimesetw(10)(*it1).flagendl;pcb.erase(pcb.begin());sort(wait.begin(),wait.end(),priority_sort_higher);sort(pcb.begin(),pcb.end(),priority_sort_higher);}else{coutleftsetw(10)(*it1).IDsetw(10)(*it1).Statesetw(10)(*it1).prioritysetw(10)(*it1).CPUtimesetw(10)(*it1).ALLtimesetw(10)(*it1).flagendl;(*it1).State=2;wait.push_back(*it1);sort(wait.begin(),wait.end(),priority_sort_higher);sort(pcb.begin(),pcb.end(),priority_sort_higher);}}}voidround_robin_way(vectorPCB2&pcb2,vectorPCB2&wait2)/{vectorPCB2::iteratorit2;it2=wait2.begin();intflag=5;while(flag){it2=pcb2.begin();wait2.erase(wait2.begin());//出队（等待队列）(*it2).State=1;if((*it2).ALLtime==1){(*it2).CPUtime+=1;(*it2).ALLtime-=1;flag-=1;(*it2).flag=1;coutleftsetw(10)(*it2).IDsetw(10)(*it2).Statesetw(10)(*it2).CPUtimesetw(10)(*it2).ALLtimesetw(10)(*it2).flagendl;pcb2.erase(pcb2.begin());continue;}elseif((*it2).ALLtime==2){(*it2).CPUtime+=2;(*it2).ALLtime-=2;flag-=1;(*it2).flag=1;coutleftsetw(10)(*it2).IDsetw(10)(*it2).Statesetw(10)(*it2).CPUtimesetw(10)(*it2).ALLtimesetw(10)(*it2).flagendl;pcb2.erase(pcb2.begin());continue;}else{(*it2).State=1;(*it2).CPUtime+=2;(*it2).ALLtime-=2;coutleftsetw(10)(*it2).IDsetw(10)(*it2).Statesetw(10)(*it2).CPUtimesetw(10)(*it2).ALLtimesetw(10)(*it2).flagendl;(*it2).State=2;wait2.push_back(*it2);PCB2q=*it2;pcb2.erase(pcb2.begin());pcb2.push_back(q);}}}intmain(){cout-------------------------------模拟进程调度----------------------------------endl;intflag_0,a[5],b;cout请输入想要模拟进程调度算法的编号endl;cout1.优先数调度；2.时间片轮转调度。endl;cinflag_0;if(flag_0==1){vectorPCBpcb;vectorPCB::iteratorit;it=pcb.begin();cout创建5个进程，请为5个进程设置优先数(优先数越大优先级越高)endl;cout例如：142061211，即将5个进程的优先数分别设置为142061211endl;for(inti=1;i=5;i++)cina[i-1];cout请为5个进程设置其需运行的时间片数endl;for(inti=1;i=5;i++){cinb;PCBq;q.set_PCB(i,a[i-1],0,b,2,0);pcb.push_back(q);}sort(pcb.begin(),pcb.end(),priority_sort_higher);vectorPCBwait(5);copy(pcb.begin(),pcb.end(),back_inserter(wait));cout该进程运行情况如下（flag=0代表未完成，flag=1代表已完成）endl;coutleftsetw(10)IDsetw(10)Statesetw(10)prioritysetw(10)CPUtimesetw(10)ALLtimesetw(10)flag1endl;priority_way(pcb,wait);}elseif(flag_0==2){vectorPCB2pcb2;vectorPCB2::iteratorit2;it2=pcb2.begin();cout创建5个进程，请为5个进程设置轮转时间数endl;for(inti=1;i=5;i++){cinb;PCB2q2;q2.set_PCB2(i,0,b,2,0);pcb2.push_back(q2);}vectorPCB2wait2(5);copy(pcb2.begin(),pcb2.end(),back_inserter(wait2));cout该进程运行情况如下（flag=0代表未完成，flag=1代表已完成）endl;coutleftsetw(10)IDsetw(10)Statesetw(10)CPUtimesetw(10)ALLtimesetw(10)flag1endl;round_robin