进程调度算法spffpf时间片轮转算法实现

node{}};

sum=-booloperator()(nodea,nodeb){node{}};

sum=-booloperator()(nodea,nodeb){i(a.time==b.timeretura.start>b.start;return

int1,ans=0,avg=0.00;a.time>b.time;

j=0,num=ready.size(),ok=1;

调度的基本概念：从就绪队列中按照⼀定的算法选择⼀个进程并将处理机分配给它运⾏，以实现进程并发地执⾏。

进程信息

1structstrinname//进程名称inid//进程idintime//进程服务时间inrtime//进程服务时间（主要⽤于时间⽚轮转算法）inlevel//进程优先级instart//进程提交时间inlst//进程调度时间};

1set<string>pname;//存放进程名称，防⽌创建重复进程queue<node>qq//时间⽚轮转时⽤到的就绪队列queue<node>pp//进程的执⾏队列queue<node>db//时间⽚算法中的调度顺序priority_queue<node,vector<node>,cmpspf>spf//短时间优先算法队列priority_queue<node,vector<node>,cmpfpf>fpf//优先级算法队列vector<node>ready//就绪队列vector<node>emy//已删除的进程

⽤vector容器存放就绪的进程（每插⼊⼀个，sort⼀下，依据进程提交时间升序排列）

spf（短作业优先算法）

算法思想：服务时间短的进程在就绪队列前⾯。

算法规则：要求服务时间最短的进程/作业优先得到服务。

算法实现：模拟时间，将已提交的进程插⼊优先队列，在依据时间是否到达完成时间来判断哪个进程被移⼊内存中运⾏

代码：

struccmpspf{234567891//sum作为在执⾏进程的完成时间1i(t==1){1for(inti=0;i<=100000;i++){1i(i==sum)//⾸先判断是否到达在执⾏进程的完成时间1nodetemp;1temp=spf.top();spf.pop();1temp.lst=i-temp.start//计算周转时间1ans+=temp.lst//总的周转时间1avg+=double(temp.lst)/double(temp.time);//总的带权周转时间1pp.push(temp);/执⾏完毕的进程放⼊执⾏队列2i(!spf.empty())sum+=spf.top().time;2}2whil(j<num&&i==ready[j].start)//将到达进程提交时间的进程放⼊就绪队列2spf.push(ready[j]);2//当CPU执⾏过程中出现空闲时，更新sum值2i(i>sum&&sum<=spf.top().start)sum=spf.top().start+spf.top().time;2j++;2}2i(ok&&!spf.empty())//第⼀个执⾏的进程的完成时间2sum=i+spf.top().time;3ok=0;3}3i(j==num&&spf.empty()break;//所有进程执⾏完毕3}3printfprintf进程周转时带权周转时间带权周转时间);3whil(!pp.empty()){3nodeout;3ou=pp.front();pp.pop();3cout<<;3printfprintf(,out.lst,double(out.lst)/double(out.time));4}4printfprintf平均平均周转时间为：周转时间为：,double(ans)/double(num));

,avg);printf(进周转时,avg);printf(进周转时带权周转时间带权周转时间

printf(,out.lst,

printf(平均周转时间为：平均周转时间为：,double(ans)/double(num));printf(平均带权周转时间为平均带权周转时间为,avg);

fpf（优先级调度算法）

算法思想：进程优先级⾼的进程在就绪队列前⾯。

算法规则：要求进程优先级⾼的进程/作业优先得到服务。

算法实现：模拟时间，将已提交的进程插⼊优先队列，在依据时间是否到达完成时间来判断哪个进程被移⼊内存中运⾏

代码：逻辑跟spf算法是⼀样的这⾥不过多叙述。

1//spf、fpf的区别就在于优先队列中的规则不同2structcmpfpf{booloperator()(nodea,nodeb){if(a.level==b.levelretura.start>b.start;retura.level<b.level;}};

for(inti=0;i<=10000;i++){if(i==sum){nodetemp;temp=fpf.top();fpf.pop();temp.lst=i-temp.start;ans+=temp.lst;avg+=double(temp.lst)/double(temp.time);pp.push(temp);if(!fpf.empty())sum+=fpf.top().time;}whil(j<num&&i==ready[j].start){fpf.push(ready[j]);if(i>sum&&sum<=fpf.top().start)sum=fpf.top().start+fpf.top().time;j++;}if(ok&&!fpf.empty()){sum=i+fpf.top().time;ok=0;}if(j==num&&fpf.empty()break;}printf();whil(!pp.empty()){nodeout;out=pp.front();pp.pop();cout<<;printf(double(out.lst)/double(out.time));}printf(printf(

时间⽚轮转算法

算法思想：公平的、轮流的为各个进程服务，让每个进程在⼀定时间间隔内都可以得到响应

算法规则：系统根据FCFS策略，将所有的就绪进程排成⼀个就绪队列。

轮流让各个进程执⾏⼀个时间⽚的，若进程未在⼀个时间⽚内执⾏完，则被剥夺处理机，将进程放到就绪队列队尾重新排队。

算法实现：利⽤队列模拟就绪队列，模拟时间，每次时间增加⼀个时间⽚长度，先判断是否有进程在时间⽚内结束，如果有的话，就对时间进⾏修改回退到刚完成进程的时间，再判断时间⽚内是否有进程提交，有的话加⼊队列。

代码

1printfprintf(请设置请设置时间⽚时间⽚⼤⼩⼤⼩);sf(m);3fointi=0;i<=100000;i+=m){//每次⾃增⼀个时间⽚4if(!qq.empty()){/当运⾏队列有进程时，则运⾏该进程5nodetemp;temp=qq.front();qq.pop();db.push(temp);if(temp.time>m)//若进程不能在该时间⽚内运⾏完毕，则将服务时间减去时间⽚，再重新放⼊队列，这也是使rtime⽤计算带权周转时间的原因9temp.time-=m;10qq.push(temp);11}12els//反之回退时间，并将已完成的进程放⼊执⾏完毕队列1i=i-m+temp.time;14temp.lst=i-temp.start;

1ans+=temp.lst;16pp.push(temp);17}18}19whil(j<num&&i>=ready[j].start)//到达时间⽚的进程放⼊队列2if(ok||qq.empty()){21i=ready[j].start;22ok=0;23}24ready[j].rtime=ready[j].time;25qq.push(ready[j]);26j++;27}28if(j==num&&qq.empty()break;29}30printfprintf(进程调度顺序：进程调度顺序：);31while(!db.empty()){cout<<db.front().name<<(!db.empty()){cout<<db.front().name<<;db.pop();}32printfprintf(进程执⾏完毕顺序周转时带权周转时间带权周转时间);33whil(!pp.empty()){34nodeout;35out=pp.front();pp.pop();36cout<<;37printfprintf(,out.lst,double(out.lst)/double(out.rtime));38avg+=double(out.lst)/double(out.rtime);39}40printfprintf(平均周转时间平均周转时间,double(ans)/double(num));41printfprintf(平均带权周转时间为平均带权周转时间为,avg/double(num));

总代码如下：

1#include<bits/stdc++.h>2usingnamespacstd;typedeflonglonLL;typedefvectorint>vi;typedefpairint,int>ii;6#defininf1e97#definFfirst8#definSsecond9#define#define10#definrep(i,j,k)for(inti=(j);i<=(k);i++)11#definrep__(i,j,k)for(inti=(j);i<(k);i++)12#definper(i,j,k)for(inti=(j);i>=(k);i--)13#definper__(i,j,k)for(inti=(j);i>(k);i--)14#definmst(a,b)memset(a,b,sizeof(a))15#define#define16#define#define17#define#define18#define#define19#define#define20constintN=1e3+10;2priority_queueint,vector<int>,less<int>>q;22intt,x,sum,ans,m;23doublavg;24strink;25structnode{2strinname;//进程名称27intid;//进程id2inttime;//进程服务时间29intrtime;//进程服务时间（主要⽤于时间⽚轮转算法）30intlevel;//进程优先级31intstart;//进程提交时间32intlst;//进程调度时间33};34structcmpspf{3booloperator()(nodea,nodeb){3if(a.time==b.timeretura.start>b.start;3retura.time>b.time;3}3};40structcmpfpf{4booloperator()(nodea,nodeb){4if(a.level==b.levelretura.start>b.start;4retura.level<b.level;4}4};46set<string>pname;//存放进程名称，防⽌创建重复进程47queue<node>qq//时间⽚轮转时⽤到的就绪队列48queue<node>pp//进程的执⾏队列49queue<node>db//时间⽚算法中的调度顺序50priority_queue<node,vector<node>,cmpspf>spf//短时间优先算法队列51priority_queue<node,vector<node>,cmpfpf>fpf//优先级算法队列52vector<node>ready//就绪队列

53vector<node>emy//已删除的进程54boolcmpconstnode&a,constnode&b){5retura.start<b.start;5}57voicreate(){5nodea;5printfprintf(请输⼊新进程的名称请输⼊新进程的名称);6cin>>;6if(pname.find()!=pname.end()){6printfprintf(进程已存在，请从新输⼊：进程已存在，请从新输⼊：);6create();6return;6}6pname.insert();6printfprintf(请输⼊新进程的到达时间、服务时间请输⼊新进程的到达时间、服务时间);6sf(a.start);sf(a.time);6printfprintf(请输⼊新进程的请输⼊新进程的);sf(a.id);7printfprintf(请输⼊新进程的优先级请输⼊新进程的优先级);sf(a.level);7ready.push_back(a);7sort(ready.begin(),ready.end(),cmp);7}74voikill(){7nodeb;7printfprintf(请输⼊要终⽌的进程名字请输⼊要终⽌的进程名字);7cin>>k;7if(pname.find(k)!=pname.end()){7intnum=ready.size();8fointi=0;i<num;i++){8if(ready[i].name==k){8b=ready[i];8emy.push_back(b);8ready.erase(ready.begin()+i);8printfprintf(终⽌进程成功！终⽌进程成功！);8}8if(num==ready.size()){8printfprintf(该进程已在空队列中该进程已在空队列中);8}9}9}9els{9printfprintf(该进程不存在，请输⼊正确的进程名该进程不存在，请输⼊正确的进程名);9kill();9return;9}9}98voidisplay(){9whil(!pp.empty())pp.pop();10whil(!spf.empty())spf.pop();10whil(!fpf.empty())fpf.pop();10whil(!qq.empty())qq.pop();10if(ready.empty()){10printfprintf(就绪队列为空！就绪队列为空！);10return;10}10printfprintf(请选择调度算法请选择调度算法);10printfprintf(、spf调度算法调度算法);10printfprintf(、fpf调度算法调度算法);11printfprintf(、时间⽚轮转算法、时间⽚轮转算法);11printfprintf(、返回菜单、返回菜单);11sf(t);11intj=0,num=ready.size(),ok=1;11sum=1,ans=0,avg=0.00;11//sum作为在执⾏进程的完成时间11if(t==1){11rep(i,0,100000){11if(i==sum)//⾸先判断是否到达在执⾏进程的完成时间11nodetemp;12temp=spf.top();spf.pop();12temp.lst=i-temp.start//计算周转时间12ans+=temp.lst//总的周转时间12avg+=double(temp.lst)/double(temp.time);//总的带权周转时间12pp.push(temp);12if(!spf.empty())sum+=spf.top().time;12}12whil(j<num&&i==ready[j].start)//将到达进程提交时间的进程放⼊就绪队列12spf.push(ready[j]);12//当CPU执⾏过程中出现空闲时，更新sum值13if(i>sum&&sum<=spf.top().start)sum=spf.top().start+spf.top().time;13j++;13}13if(ok&&!spf.empty())//第⼀个执⾏的进程的完成时间13sum=i+spf.top().time;13ok=0;13}

13if(j==num&&spf.empty()break;//所有进程执⾏完毕13}13printfprintf(进程周转时带权周转时间带权周转时间);14whil(!pp.empty()){14nodeout;14out=pp.front();pp.pop();14cout<<;14printfprintf(,out.lst,double(out.lst)/double(out.time));14}14printfprintf(平均周转时间为：平均周转时间为：,double(ans)/double(num));14printfprintf(平均带权周转时间为平均带权周转时间为,avg);14}14elseif(t==2){15rep(i,0,100000){15if(i==sum){15nodetemp;15temp=fpf.top();fpf.pop();15temp.lst=i-temp.start;15ans+=temp.lst;15avg+=double(temp.lst)/double(temp.time);15pp.push(temp);15if(!fpf.empty())sum+=fpf.top().time;15}16whil(j<num&&i==ready[j].start){16fpf.push(ready[j]);16if(i>sum&&sum<=fpf.top().start)sum=fpf.top().start+fpf.top().time;16j++;16}16if(ok&&!fpf.empty()){16sum=i+fpf.top().time;16ok=0;16}16if(j==num&&fpf.empty()break;17}17printfprintf(进周转时带权周转时间带权周转时间);17whil(!pp.empty()){17nodeout;17out=pp.front();pp.pop();17cout<<;17printfprintf(,out.lst,double(out.lst)/double(out.time));17}17printfprintf(平均周转时间为：平均周转时间为：,double(ans)/double(num));17printfprintf(平均带权周转时间为平均带权周转时间为,avg);18}18elseif(t==3){18printfprintf(请设置时间⽚⼤⼩请设置时间⽚⼤⼩);18sf(m);18fointi=0;i<=100000;i+=m){//每次⾃增⼀个时间⽚18if(!qq.empty())//当运⾏队列有进程时，则运⾏该进程18nodetemp;18temp=qq.front();qq.pop();18db.push(temp);18if(temp.time>m)//若进程不能在该时间⽚内运⾏完毕，则将服务时间减去时间⽚，再重新放⼊队列，这也是使⽤rtime计算带权周转时间的原因19temp.time-=m;19qq.push(temp);19}19els//反之回退时间，并将已完成的进程放⼊执⾏完毕队列19i=i-m+temp.time;19temp.lst=i-temp.start;19ans+=temp.lst;19pp.push(temp);19}19}20whil(j<num&&i>=ready[j].start)//到达时间⽚的进程放⼊队列20if(ok||qq.empty()){20i=ready[j].start;20ok=0;20}20ready[j].rtime=ready[j].time;20qq.push(ready[j]);20j++;20}20if(j==num&&qq.empty()break;21}21printfprintf(进程调度顺序：进程调度顺序：);21whil(!db.empty()){cout<<db.front().name<<(!db.empty()){cout<<db.front().name<<;db.pop();}21printfprintf(进程执⾏完毕顺序周转时带权周转时间带权周转时间);21printfprintf(进程周转时带权周转时间带权周转时间);21whil(!pp.empty()){21nodeout;21out=pp.front();pp.pop();21cout<<;21printfprintf(,out.lst,double(out.lst)/double(out.rtime));22avg+=double(out.lst)/double(out.rtime);

22}22prin