OS课设之CPU调度算法的模拟实现

CPU调度算法的模拟实现一、设计目的利用C++编写CPU调度算法，实现先来先服务调度算法FCFS、优先级调度算法PS、短作业优先调度算法SJF、时间片轮转调度算法RR的运行过程和实现的结果，针对模拟进程，利用编写的CPU调度算法对需要运行的进程进行调度。进行算法评价，计算平均周转时间和平均等待时间。二、设计要求针对模拟进程，利用CPU调度算法进行调度，最后要进行算法评价，计算平均周转时间和平均等待时间，并且输出调度结果和输出算法评价指标。调度所需的进程参数由输入产生（手工输入或者随机数产生）。三、设计说明CPU调度决策可在如下4种情况环境下发生：（1）当一个进程从运行切换到等待状态（如：I/O请求，或者调用wait等待一个子进程的终止）（2）当一个进程从运行状态切换到就绪状态（如：出现中断）⑶当一个进程从等待状态切换到就绪状态（如：I/O完成）（4）当一个进程终止时对于第1和4两种情况，没有选择而只有调度。一个新进程（如果就绪队列中已有一个进程存在）必须被选择执行。对于第2和第3两种情况，可以进行选择。当调度只能发生在第1和4两种情况下时，称调度是非抢占的（nonpreemptive）或协作的（cooperative）；否则，称调度方案为抢占的（preemptive）。采用非抢占调度，一旦CPU分配给一个进程，那么该进程会一直使用CPU直到进程终止或切换到等待状态。抢占调度对访问共享数据是有代价（如加锁）的，有可能产生错误，需要新的机制（如，同步）来协调对共享数据的访问。抢占对于操作系统内核的设计也有影响。在处理系统调用时，内核可能忙于进程活动。这些活动可能涉及要改变重要内核数据（如I/O队列）。因为根据定义中断能随时发生，而且不能总是被内核所忽视，所以受中断影响的代码段必须加以保护以避免同时访问。操作系统需要在任何时候都能够接收中断，否则输入会丢失或输出会被改写。为了这些代码段不被多个进程同时访问，在进入时就要禁止中断，而在退出时要重新允许中断。调度准则为了比较CPU调度算法所提出的准则：CPU使用率:需要使CPU尽可能忙吞吐量:指一个时间单元内所完成进程的数量周转时间:从进程提交到进程完成的时间段称为周转时间，周转时间是所有时间段之和，包括等待进入内存、在就绪队列中等待、在CPU上执行和I/O执行平均周转时间:即周转时间的算数平均值等待时间:在就绪队列中等待所花费时间之和平均等待时间:即等待时间的算数平均值响应时间:从提交请求到产生第一响应的时间。需要使CPU使用率和吞吐量最大化，而使周转时间、等待时间和响应时间最小化。绝大多数情况下需要优化平均值，有时需要优化最大值或最小值，而不是平均值四、详细设计4.1先到先服务调度（First-Come，First-Servedscheduling）最简单的CPU调度算法是先到先服务算法（First-Come，First-Servedscheduling）：先请求CPU的进程先分配到CPU。FCFS策略可以用FIFO队列来容易实现。当一个进程进入就绪队列，其PCB链接到队列的尾部。当CPU空闲时，CPU分配给位于队列头的进程，接着运行进程从队列中删除。FCFS策略的代码编写简单且容易理解，不过采用FCFS策略的平均等待时间通常比较长。当进程CPU区间时间变化很大，平均等待时间会变化很大。算法原理:假设有n个进程分别在T1,„,Tn时刻到达系统，它们需要的服务时间分别为S1,„,Sn。分别采用先来先服务FCFS调度算法进行调度，计算每个进程的完成时间，周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。程序要求如下：1）进程个数n；每个进程的到达时间T1,„,Tn和服务时间S1,„,Sn。2）要求采用先来先服务FCFS调度进程运行，计算每个进程的周转时间，带权周转时间，并且计算所有进程的平均周转时间，带权平均周转时间；3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程B开始运行”等等；4）输出：要求输出计算出来的每个进程的周转时间，带权周转时间，所有进程的平均周转时间，带权平均周转时间。实现简要过程：1）变量初始化；2）接收用户输入n，T1,„,TnS1,„,Sn；3）按照选择算法进行进程调度，计算进程的完成时间、周转时间和带权周转时间；4）按格式输出调度结果。测试结果：C:\WindowsVsystem32\cmdl.exe选择调度算法：1：FCFS2：选择调度算法：1：FCFS2：时间片轮换1输入进程个数:输入此进程时间片大小：1103：优先级调度4：最短作业优先5：最短剩余时间优先输入第个进程的名字、cpu时间和优先级：P1101［输入第P2102个进程的名字、cpu时间和优先级［输入第P2102个进程的名字、cpu时间和优先级：输入第P3103个进程的名字、cpu时间和优先级：<说明；F程名字IPlP2P3共需占用CPU<说明；F程名字IPlP2P3共需占用CPU时间101010还需要占用时间01010优先级状态在本程序所列进程信息中，优先级一项是指进程运行后的优先级”>请按任意键继续.一.P2P310P2P31010运行

等待情按任意键继续...进程P2已经执行完毕?情按任意键继续...P310运行P310运行进程P3已经执行完毕*请按任意键继续...年已经执行完毕!箍续案例分析：进程区间时间P124P23P33如果按照P1P2P3顺序到达，Gantt图如下:242730242730P1P2P3平均等待时间：（0+24+27）-3=17平均周转时间：（24+27+30）-3=27如果按照P2P3P1顺序到达，平均等待时间：（0+3+6）-3=3平均周转时间：（3+6+30）-3=13另外考虑在动态情况下的性能，假设有一个CPU约束进程和许多I/O约束进程，CPU约束进程会移回到就绪队列并被分配到CPU。再次所有I/O进程会在就绪队列中等待CPU进程的完成。由于所有其他进程都等待一个大进程释放CPU，这称之为护航效果（convoyeffect）。与让较短进程最先执行相比，这样会导致CPU和设备使用率变的很低。FCFS调度算法是非抢占的。对于分时系统（每个用户需要定时的等待一定的CPU时间）是特别麻烦。允许一个进程保持CPU时间过长是个严重错误。优先级调度（priorityschedulingalgorithm）算法：每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。进程的运行时间以时间片为单位进行计算。每个进程的状态可以是就绪W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。就绪进程获得CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB，以便进行检查。重复以上过程，直到所要进程都完成为止。SJF算法可作为通用的优先级调度算法的一个特例。每个进程都有一个优先级与其关联，具有最高优先级的进程会分配到CPU。具有相同优先级的进程按FCFS顺序调度。SJF，其优先级（p）为下一个CPU区间的倒数。CPU区间越大，则优先级越小，反之亦然。优先级通常是固定区间的数字，如0〜7,但是数字大小与优先级的高低没有定论。测试结果：

P2P5P1P3P4画出Gantt图:01616 181931pPI进进比亩十完完-丁rJ.ll.ll经经已已P211P324P415P55231pPI进进比亩十完完-丁rJ.ll.ll经经已已P211P324P415P552平均等待时间：(0+1+6+16+18)-5=8.2平均周转时间：(1+6+16+18+19)-5=12优先级可通过内部或外部方式来定义。内部定义优先级使用一些测量数据以计算进程优先级。外部优先级是通过操作系统之外的准则来定义，如进程重要性等。优先级调度可以是抢占的或非抢占的。优先级调度算法的一个重要问题是无限阻塞(indefiniteblocking)或饥饿(starvation)。可以运行但缺乏CPU的进程可认为是阻塞的，它在等待CPU。优先级调度算法会使某个有低优先级无穷等待CPU。低优先级进程务求等待问题的解决之一是老化(aging)。老化是一种技术，以逐渐增加在系统中等待很长时间的进程的优先级。时间片轮转调度算法(round-robin,RR)专门为分时系统设计。它类似于FCFS调度，但是增加了抢占以切换进程。定义一个较小的时间单元，称为时间片(timequantum，ortimeslice)。将就绪队列作为循环队列。CPU调度程序循环就绪队列，为每个进程分配不超过一个时间片段的CPU。系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后,它被移到队列的末尾。RR策略的平均等待时间通常较长测试结果：平均等待时间：［0+4+7+(10-4)卜3=5.66平均周转时间：(7+10+30)-3=15.67如果就绪，那么每个进程会得到1n的CPU时间，其长度不超过q时间单元。每个进程必须等待CPU时间不会超过(n1)Xq个时间单元，直到它的下一个时间片为止。RR算法的性能很大程度上依赖于时间片的大小。在极端情况下，如果时间片非常大，那么RR算法与FCFS算法一样。如果时间片很小，那么RR算法称为处理器共享，n个进程对于用户都有它自己的处理器，速度为真正处理器速度的1/n。小的时间片会增加上下文切换的次数，因此，希望时间片比上下文切换时间长，事实上，绝大多数现代操作系统，上下文切换的时间仅占时间片的一小部分。周转时间也依赖于时间片的大小。最短作业优先调度(shortest-job-firstscheduling,SJF)将每个进程与下一个CPU区间段相关联。当CPU为空闲时，它会赋给具有最短CPU区间的进程。如果两个进程具有同样长度，那么可以使用FCFS调度来处理。注意，一个更为适当地表示是最短下一个CPU区间的算法，这是因为调度检查进程的下一个CPU区间的长度，而不是其总长度。这种策略是下一次选择所需处理时间最短的进程。是非抢占策略，目的也是为减少FCFS策略对长进程的偏向。测试结果：

P43P43画出Gantt图:P4P1P3P20 3 9 16 24SJF平均等待时间：(0+3+9+16)-4=7SJF平均周转时间：(3+9+16+24)-4=13FCFS平均等待时间：(0+6+14+21)-4=10.25FCFS平均周转时间：(6+14+21+24)-4=16.25SJF算法的平均等待时间最小。SJF算法的真正困难是如何知道下一个CPU区间的长度。对于批处理系统的长期(作业)调度，可以将用户提交作业时间所制定的进程时间极限作为长度。SJF调度经常用于长期调度。它不能在短期CPU调度层次上加以实现。我们可以预测下一个CPU区间。认为下一个CPU区间的长度与以前的相似。因此通过计算下一个CPU区间长度的近似值，能选择具有最短预测CPU区间的进程来运行。下一个CPU区间通常可预测为以前CPU去剪的测量长度的指数平均（exponentialaverage）。最短剩余时间优先调度（shortest-remaining-time-firstscheduling）SJF算法可能是抢占的或非抢占的。抢占SJF算法可抢占当前运行的进程，而非抢占的SJF算法会允许当前的进程先完成其CPU区间。抢占SJF调度有时称为最短剩余时间优先调度。这种策略下调度器总是选择预期剩余时间最短的进程。是抢占策略。测试结果：.rawC:\Windows\system32\cmd,exe请输入计算机中的进程数目;4输入第1个进程的到达时间及剩余执行时间;08输入第2个进程的到达时间及剩余执行时间：4输入第3个进程的到达时间及剩余执行时间：9输入第4个进程的到达时间及剩余执行时间：进程按顺序运行依次为:12413用均等待时间是：平均周转时间是：13.000000请按案例分析：.P1P2P4P1P3画出Gantt图:01 510 1726平均等待时间：［0+0+（5-3）+（17-2）］M=6.5平均周转时间：［（17-0）+（5-1）+（26-2）+（10-3）卜4=13非抢占的SJF平均等待时间：［0+（8-1）+（12-3）+（17-2）卜4=7.75源代码//最短剩余时间优先算法的实现#include<stdio.h>#include<stdlib.h>#include<time.h>typedefstruct{intremain_time;intarrive_time;intTp;typedefstruct{intremain_time;intarrive_time;intTp;intTc;intTo;intnumber;}Process_Block;typedefstruct_Queue{Process_BlockPB;struct_Queue*next;}_Block,*Process;typedefstruct{Processhead;Processend;}Process_Queue;Process_QueuePQ;int t;Process Run_Now;//进程剩余执行时间//进程到达时间//进入就绪队列的时间//进入执行队列的时间//进程执行结束的时间//进程编号//定义进程模块//定义一个进程模块队列中结点//队列头指针//队列尾指针//进程队列//定义一个全局队列变量//全局时间//当前正在运行的进程，作为全局变量voidInitQueue(Process_QueuePQ){PQ.head->next=NULL;PQ.end->next=PQ.head;}/*初始化队列*/intIsEmpty(Process_QueuePQ){if(PQ.end->next==PQ.head)return1; //队列空的条件为头指针指向尾指针并且尾指针指向头指针elsereturn0;}/*判定队列是否为空队列*/voidEnQueue(Process_QueuePQ,ProcessP){Processtemp=(Process)malloc(sizeof(_Block));temp=PQ.end;temp->next->next=P;PQ.end->next=P;}/*插入队列操作*/ProcessDeQueue(Process_QueuePQ){if(IsEmpty(PQ))returnNULL;Processtemp=PQ.head->next;PQ.head->next=temp->next;if(PQ.end->next==temp)PQ.end->next=PQ.head;returntemp;}/*出列操作*/ProcessShortestProcess(Process_QueuePQ){if(IsEmpty(PQ)){ //如果队列为空，返回if(!Run_Now)returnNULL;elsereturnRun_Now;}Processtemp,shortest,prev;intmin_time;if(Run_Now){ //如果当前有进程正在执行，shortest=Run_Now;//那么最短进程初始化为当前正在执行的进程，min_time=Run_Now->PB.remain_time;}else{ //如果当前没有进程执行，shortest=PQ.head->next; //则最短进程初始化为队列中第一个进程min_time=PQ.head->next->PB.remain_time;}temp=PQ.head;prev=temp;while(temp->next){if(temp->next->PB.remain_time<min_time){//如果当前进程的剩余时间比min_time短，shortest=temp->next; //则保存当前进程，min_time=shortest->PB.remain_time;prev=temp; //及其前驱}temp=temp->next;}if(shortest==PQ.end->next)//如果最短剩余时间进程是队列中最后一个进程，PQ.end->next=prev; //则需要修改尾指针指向其前驱prev->next=shortest->next;//修改指针将最短剩余时间进程插入到队头returnshortest;}/*调度最短剩余时间的进程至队头*/voidRun(){Run_Now->PB.remain_time--;//某一时间运行它的剩余时间减return;}/*运行函数*/voidWait(){return;}intsum(intarray[],intn){inti,sum=0;for(i=0;i<n;i++)sum+=array[i];returnsum;}intmain(){PQ.head=(Process)malloc(sizeof(_Block));PQ.end=(Process)malloc(sizeof(_Block));Run_Now=(Process)malloc(sizeof(_Block));Run_Now=NULL;InitQueue(PQ);inti,N,Total_Time=0; 〃Total_Time为所有进程的执行时间之和printf("请输入计算机中的进程数目：\/);scanf("%d",&N);Process*P,temp;P=(Process*)malloc(N*sizeof(Process));int*wt,*circle_t;wt=(int*)malloc(N*sizeof(int));circle_t=(int*)malloc(N*sizeof(int));for(i=0;i<N;i++){P[i]=(Process)malloc(sizeof(_Block));P[i]->PB.number=i+1;P[i]->next=NULL;wt[i]=0;circle_t[i]=0;printf("输入第%d个进程的到达时间及剩余执行时间:\n",i+1);scanf("%d%d",&P[i]->PB.arrive_time,&P[i]->PB.remain_time);}for(i=0;i<N;i++)Total_Time+=P[i]->PB.remain_time;printf("\n进程按顺序运行依次为:\n");i=0;intk=0;for(t=0;;t++){if(Run_Now){ //如果当前有进程正在执行Run();if(t==P[i]->PB.arrive_time){//如果当前时间正好有进程进入if(P[i]->PB.remain_time<Run_Now->PB.remain_time){temp=P[i];P[i]=Run_Now;Run_Now=temp; //则调度它至运行队列中，Run_Now->PB.Tp=t;Run_Now->PB.Tc=t;wt[Run_Now->PB.number-1]+=Run_Now->PB.Tc-Run_Now->PB.Tp;printf("%d",Run_Now->PB.number);}EnQueue(PQ,P[i]); //并将当前运行进程重新插入队列中P[i]->PB.Tp=t;k++;i=(i+1)>(N-1)?(N-1):(i+1);}if(Run_Now->PB.remain_time==0){//如果当前进程运行结束，Run_Now->PB.To=t;//进程运行结束的时间circle_t[Run_Now->PB.number-1]+=t-Run_Now->PB.arrive_time;free(Run_Now); //则将它所占资源释放掉，Run_Now=NULL; 〃并修改Run_Now为NULLRun_Now=ShortestProcess(PQ)//从就绪队列中调出最短剩余时间进程至队头，if(!Run_Now){//如果队列为空，转为等待状态if(IsEmpty(PQ)&&k>=N)break;Wait();continue;}else{Run_Now->PB.Tc=t;wt[Run_Now->PB.number-1]+=Run_Now->PB.Tc-Run_Now->PB.Tp;printf("%d",Run_Now->PB.number);}}}else{ //如果当前运行进程为空，那么if(t==P[i]->PB.arrive_time){ //如果正好这时有进程入队k++;EnQueue(PQ,P[i]);Run_Now=DeQueue(PQ);//则直接被调入运行队列中Run_Now->PB.Tp=t;Run_Now->PB.Tc=t;printf("%d",Run_Now->PB.number);i=(i+1)>(N-1)?(N-1):(i+1);}else{Wait();continue;}}}printf("\n");printf("平均等待时间是:\n%f\n",((float)sum(wt,N))/N);printf("平均周转时间是:\n%f\n",((float)sum(circle_t,N))/N);return0;}//////////////////////////////////////////////////////#include<iostream>#include<string>usingnamespacestd;classProcess{public:stringProcessName;//进程名字intTime;//进程需要时间intleval;//进程优先级intLeftTime;//进程运行一段时间后还需要的时间};voidCopy(Processproci,Processproc2);//把proc2赋值给procivoidSort(Processpr[],intsize);//此排序后按优先级从大到小排列voidsort1(Processpr[],intsize);//此排序后按需要的cpu时间从小到大排列voidFcfs(Processpr[],intnum,intTimepice);//先来先服务算法voidTimeTurn(Processprocess[],intnum,intTimepice);//时间片轮转算法voidPriority(Processprocess[],intnum,intTimepice);//优先级算法voidmain(){inta;cout<<endl;cout<<"选择调度算法："<<endl;cout<<"i:FCFS2:时间片轮换3:优先级调度4:最短作业优先5:最短剩余时间优先"<<endl;cin>>a;constintSize=30;Processprocess[Size];intnum;intTimePice;cout<<"输入进程个数:"<<endl;cin>>num;cout<<"输入此进程时间片大小:"<<endl;cin>>TimePice;for(inti=0;i<num;i++){stringname;intCpuTime;intLeval;cout<<〃输入第〃<<i+1<<"个进程的名字、cpu时间和优先级:〃<<endl;cin>>name;cin>>CpuTime>>Leval;process[i].ProcessName=name;process[i].Time=CpuTime;process[i].leval=Leval;cout<<endl;}for(intk=0;k<num;k++)process[k].LeftTime=process[k].Time;//对进程剩余时间初始化cout<<"(说明:在本程序所列进程信息中，优先级一项是指进程运行后的优先级!!)";cout<<endl;cout<<endl;cout<<"进程名字"<<"共需占用CPU时间"<<"还需要占用时间"<<"优先级"<<"状态"<<endl;if(a==1)Fcfs(process,num,TimePice);elseif(a==2)TimeTurn(process,num,TimePice);elseif(a==3){Sort(process,num);Priority(process,num,TimePice);}else{//最短作业算法，先按时间从小到大排序，再调用Fcfs算法即可sort1(process,num);Fcfs(process,num,TimePice);}}voidCopy(Processproc1,Processproc2){proc1.leval=proc2.leval;proc1.ProcessName=proc2.ProcessName;proc1.Time=proc2.Time;}voidSort(Processpr[],intsize){//以进程优先级高低排序//直接插入排序for(inti=1;i<size;i++){Processtemp;temp=pr[i];intj=i;while(j>0&&temp.leval<pr[j-1].leval){pr[j]=pr[j-1];j--;}pr[j]=temp;}//直接插入排序后进程按优先级从小到大排列for(intd=size-1;d>size/2;d--){Processtemp;temp=pr[d];pr[d]=pr[size-d-1];pr[size-d-1]=temp;}//此排序后按优先级从大到小排列}/*最短作业优先算法的实现*/voidsort1(Processpr[],intsize){//以进程时间从低到高排序//直接插入排序for(inti=1;i<size;i++){Processtemp;temp=pr[i];intj=i;while(j>0&&temp.Time<pr[j-1].Time){pr[j]=pr[j-1];j--;}pr[j]=temp;}}/*先来先服务算法的实现*/voidFcfs(Processprocess[],intnum,intTimepice){//process口是输入的进程，num是进程的数目，Timepice是时间片大小while(true){if(num==0){cout<<"所有进程都已经执行完毕!"<<endl;exit(1);}if(process[0].LeftTime==0){cout<<"进程"<<process[0].ProcessName<<"已经执行完毕!"<<endl;for(inti=0;i<num;i++)process[i]=process[i+1];num--;}elseif(process[num-1].LeftTime==0){cout<<"进程"<<process[num-1].ProcessName<<"已经执行完毕!"<<endl;num--;}else{cout<<endl;//输出正在运行的进程process[0].LeftTime=process[0].LeftTime-Timepice;process[0].leval=process[0].leval-1;cout<<""<<process[0].ProcessName<<""<<process[0].Time<<"";cout<<process[0].LeftTime<<""<<process[0].leval<<"运行";cout<<endl;for(ints=1;s<num;s++){cout<<""<<process[s].ProcessName<<""<<process[s].Time<<"";cout<<process[s].LeftTime<<""<<process[s].leval<<"等待"<<endl;;}}//elsecout<<endl;system("pause");cout<<endl;}//while}/*时间片轮转调度算法实现*/voidTimeTurn(Processprocess[],intnum,intTimepice){while(true){if(num==0){cout<<"所有进程都已经执行完毕!"<<endl;exit(1);}if(process[0].LeftTime==0){cout<<"进程"<<process[0].ProcessName<<"已经执行完毕!"<<endl;for(inti=0;i<num;i++)process[i]=process[i+1];num--;}if(process[num-1].LeftTime==0){cout<<"进程"<<process[num-1].ProcessName<<"已经执行完毕!"<<endl;num--;}elseif(process[0].LeftTime>0){cout<<endl;//输出正在运行的进程process[0].LeftTime=process[0].LeftTime-Timepice;process[0].leval=process[0].leval-1;cout<<""<<