【最新】操作系统进程调度模拟实验
?ø?̵??ÈÄ?ÄâʵÑé
1.ʵÑéÄ?µÄ
????Í??ý?Ô?ø?̵??ÈËã??µÄÄ?Äâ?ÓÉî?Ô?ø?Ì?ÅÄîºÍ?ø?̵??È?ý?̵ÄÀí?â?? 2.ʵÑéÄÚÈÝ
????ÓÃCÓïÑÔ??PascalÓïÑÔ?òÆäËû?ª?????ßʵÏÖ?ÔN??N=5???ö?ø?̵ĵ??ÈÄ?Äâ??ÒªÇóÖÁÉÙ?ÉÓÃÁ?ÖÖ??Í?µÄµ??ÈËã????Èç?òµ?ÂÖת??Round RobinºÍÓÅÏÈÈ??ßÕßÓÅÏÈËã??Highest Priority
First?????Ö?ð?øÐÐÄ?Äâµ??È??
????Ã??öÓÃÀ??êÊ??ø?̵Ä?ø?Ì?ØÖÆ?éPCBÓÃ?á?????ÇÂ???À?
ÃèÊö???ù?ÝÐèÒª??Ëü?üÀ?ÒÔÏÂ×Ö?Î?º
?????ø?Ì?êÊ?ÊýID??
?????ø?ÌÓÅÏÈÊýPriority?????æ??ÓÅÏÈÊýÔ??óµÄ?ø?Ì??ÆäÓÅÏÈÈ?Ô??ß???ÉÓÃ?òµ?ÂÖת??Ê??Ã×Ö?ÎÎÞÓÃ??
?????ø?ÌÒÑ?,Õ?ÓõÄCPUÊ??äCPUTIME??ÒÔÊ??äÆ?Ϊµ?Î???ÏÂÍ????? ?????ø?Ì??ÐèÕ?ÓõÄCPUÊ??äALLTIME??µ??ø?ÌÔËÐÐÍê?ÏÊ???ALLTIME?äΪ0?? ?????ø?̵Ä×èÈûÊ??äSTARTBLOCK???íÊ?µ??ø?ÌÔÙÔËÐÐSTARTBLOCK?öÊ??äÆ?ºó???ø?Ì???øÈë×èÈû×?Ì???
?????ø?Ì??×èÈûµÄÊ??äBLOCKTIME???íÊ?ÒÑ?,×èÈûµÄ?ø?ÌÔÙµÈ?ýBLOCKTIME?öÊ??äÆ?ºó????ת???É?ÍÐ?×?Ì???
?????ø?Ì×?Ì?STATE??
?????ÓÁÐÖ?ÕëNEXT??ÓÃÀ???PCBÅÅ?É?ÓÁÐ??
????ÓÅÏÈÊý?Ä?äµÄÔ,Ôò???ÉÓÃ?òµ?ÂÖת??Ê??Ã×Ö?ÎÎÞÓÃ???º ?????ø?ÌÔÚ?ÍÐ??ÓÁÐÖеÈ?ýÒ??öÊ??äÆ???ÓÅÏÈÊýÔö?Ó1??
?????ø?ÌÃ?ÔËÐÐÒ??öÊ??äÆ???ÓÅÏÈÊý?õ3??
?????ÙÉèÔÚ?øÐе??ÈÇ???ϵÍ?ÖÐÓÐ5?ö?ø?Ì??ËüÃǵÄ?õÊ?×?Ì??ÉÒÔ?à?ÌÊäÈë???ü?ßÓÐÁé?îÐÔ????Ò??ÉÒÔ?õÊ???ΪÈçÏÂÄÚÈÝ?º
ID PRIORITY CPUTIME ALLTIME STARTBLOCK BLOCKTIME STATE 0 9 0 3 2 3 READY
1 38 0 3 -1 0 READY
2 30 0 6 -1 0 READY
3 29 0 3 -1 0 READY
4 0 0 4 -1 0 READY
????ΪÁËÇå?þµØ?Û?ìÖî?ø?̵ĵ??È?ý?Ì???ÌÐòÓ??Ã??Ã??öÊ??äÆ?ÄÚ???ø?̵ÄÇé?öÏÔÊ??öÀ???ÔÝÍ????Î???ñÊ?ÈçÏÂ?º
ÔËÐÐ/Running?ºI
?ÍÐ??ÓÁÐ/Ready Queue?ºIdi??Idj??...
×èÈû?ÓÁÐ/Block Queue?ºIdk??Idl??...
======================================================================
?ø?̺ŠÓÅÏÈÊý ÒÑÔËÐÐÊ??ä ÐèÒªÊ??ä ?ªÊ?×èÈûÊ??ä ×èÈûÊ??ä ×?Ì? 0 P0 C0 A0 T0 B0 S0
1 P1 C1 A1 T1 B1 S1 2 P2 C2 A2 T2 B2 S2 3 P3 C3 A3 T3 B3 S3 4 P4 C4 A4 T4 B4 S4 ======================================================================
3.ʵÑé?ÖÎöºÍË???
????ÔÚʵ?ʵÄ?ø?̵??ÈÖÐ????ÓÐÄÄÐ??ÉÐеÄËã????ÔõÑùÄ?Äâ?? ????ÔÚʵ?ʵÄ?ø?̵??ÈÖÐ???ýÁË??Ëã??Ñ?ÔñÏÂÒ??öÔËÐеÄ?ø?ÌÖ?Íâ???Ù×?ϵÍ???Ó??Ã×öÄÄÐ???×???
????ΪÊ?Ã??Ô?ø?̵ÄÓÅÏÈÊý?ÉÒÔ??ÉÏÊöÔ,Ôò?øÐÐÐÞ?Ä??ÓÐÊ?Ã?ºÃ???? 4.ʵÑéÑ?Ê???ÅÅ?º
????6Ñ?Ê???ÔÚµ??ÈÓëËÀËøÄÚÈÝÑ?Ï?Ö?ºó?øÐÐ??
//
Ä?Äâ?Ù×?ϵÍ?ËÄÖÖ?ø?̵??ÈËã????ÏÈ?øÏÈ?ö???Ì?ø?ÌÓÅÏÈ???ßÓÅÏÈÈ?ÓÅÏÈ???òµ?Ê??äÆ?ÂÖת??
//
??ʵÑé?ÉÒÔÄ?ÄâÈÎÒâÒ?ÖÖ???ÉÒÔ×Ô??Òå?ø?Ì?öÊý??×Ô??Òå?õÊ???ËûÃǵÄ?Ð?Ã?Â??
//?Ã?????úÂë?º
#include "stdafx.h"
#include
using std::cout;
using std::cin;
using std::cerr;
enum Status{running,ready,blocked};
enum Policy{fifo,spf,hpf,rr};
typedef class PCB
{//??Òå?Ð?Ã?ÂÀà??
public:
int id,priority,cputime,alltime,startblock,blocktime;
Status state;
class PCB *next;
PCB()
{
priority=0;
}
}PCB,*PCBptr,**PCBpp;
char x;
PCBpp pp;//Á??öÈ??Ö?äÁ?
void Print(PCBptr head)
{//?òÓ?headΪÍ?Ö?ÕëµÄ?Ð?Ã?ÂÁ??íÐÅÏ???
PCBptr p;
cout<<"\nÔËÐÐ/Running?º";
for(p=head;p->next;p=p->next)
{
if(p->next->state==running)
{
cout<<"ID"<next->id;
break;
}
}
cout<<"\n?ÍÐ??ÓÁÐ/Ready Queue?º";
for(p=head;p->next;p=p->next)
if(p->next->state==ready)
cout<<"ID"<next->id<<' ';
cout<<"\n×èÈû?ÓÁÐ/Block Queue?º";
for(p=head;p->next;p=p->next)
if(p->next->state==blocked)
cout<<"ID"<next->id<<' ';
cout<<"\n---------------------------------------------------------
--------------\n"
<<"???ø?̺Å??ÓÅÏÈÊý??ÒÑÔËÐÐÊ??ä????ÐèÒªÊ??ä???ªÊ?×èÈûÊ??ä??×èÈûÊ??
ä??×?Ì?\n";
for(p=head;p->next;p=p->next)
{
cout<<"????"<next->id<<" ??????"<next->priority<<"??
?? ??
"<next->cputime<<"??????????"<next->alltime<<"????????????
"<next->startblock<<"??????????"<next->blocktime<<"????";
switch(p->next->state)
{
case ready:cout<<"?ÍÐ?";break;
case running:cout<<"ÔËÐÐ";break;
case blocked:cout<<"×èÈû";break;
default:exit(0);
}
cout<<'\n';
}
cout<<"-----------------------------------------------------------
-------------\n"
<<"??ÈÎÒâ?üÒÔ?ÌÐø...";
cin>>x;
}
void Delete(PCBptr head,PCBptr p)
{//É??ýÒÔheadΪÍ?Ö?ÕëµÄ?Ð?Ã?ÂÁ??íÖÐpËùÖ?ÏòµÄ?áµã??
PCBptr q=head;
while(q->next!=p) q=q->next;
q->next=p->next;
delete p;
}
void InsertSort(PCBpp Rdy,PCBpp RdyEd,Policy algthm)
{//Ö??Ó?åÈëÅÅÐò??
if(*(Rdy+1))//?ÓÁÐ??Ϊ?Õ
if(RdyEd-1!=Rdy+1)
{//Ready+1?ÓÁÐÖÐ??Ö?Ò??ö??
switch(algthm)
{
case hpf:
if((*(RdyEd-1))->priority>(*(RdyEd-2))->priority)
{
PCBpp tt;
*Rdy=*(RdyEd-1);
*(RdyEd-1)=*(RdyEd-2);
for(tt=RdyEd-3;(*Rdy)->priority>(*tt)->priority;tt--)
*(tt+1)=*tt;
*(tt+1)=*Rdy;
}
break;
case spf:
if((*(RdyEd-1))->alltime<(*(RdyEd-2))->alltime)
{
PCBpp tt;
*Rdy=*(RdyEd-1);
*(RdyEd-1)=*(RdyEd-2);
for(tt=RdyEd-3;(*Rdy)->alltime<(*tt)->alltime;tt--)
*(tt+1)=*tt;
*(tt+1)=*Rdy;
}
}
}
}
void RunToBlk(PCBpp Run,PCBpp &BlkEd) {//??ÒåÔËÐÐÌ?תΪ×èÈûÌ???
(*Run)->state=blocked;
*BlkEd=*Run;
BlkEd++;
}
void RdyToRun(PCBpp &Rdy,PCBpp Run,Policy algthm)
{//??Òå?ÍÐ?Ì?תΪÔËÐÐÌ???
if(algthm==hpf||algthm==spf)
{
if(*(Rdy+1))
{
(*(Rdy+1))->state=running;
*Run=*(Rdy+1);
Rdy++;
}
}
else
{
if(*Rdy)
{
(*Rdy)->state=running;
*Run=*Rdy;
Rdy++;
}
}
}
void RunToRdy(PCBpp Run,PCBpp Rdy,PCBpp &RdyEd,Policy algthm)
{//??ÒåÔËÐÐÌ?תΪ?ÍÐ?Ì???
(*Run)->state=ready;
*RdyEd=*Run;
RdyEd++;
if(algthm==hpf||algthm==spf)
InsertSort(Rdy,RdyEd,algthm); }
int main()
{
cout<<"*******************ʵÑé?ªÊ?*******************\n\nÐèÒª×ö???ö?ø?Ì????Ö?ÐеÄʵÑé??";
int n;
if(!(cin>>n)) {cerr<<"?íÎó?ºÊäÈë??ÕýÈ???"; exit(0);}
PCBptr Listhead,Listp,Listq;//??Á?n?ö
Listhead=new PCB; //
Listp=Listhead; //
for(int i=0;i<=n-1;i++) //
{
Listq=new PCB; //
Listp->next=Listq; //
Listp=Listq; //
}
Listp->next=0; //?Ð?Ã?µÄ?ÓÁÐ??
Policy algorithm;
int num1,num2;
L1:
cout<<"\nÇëÑ?ÔñËã???????íÊ??Æ?É?Æ?Ï?????íÊ??Ó?Ð?Æ?????íÊ??È?Ð?Æ?????íÊ??Ò?Ò???º";
if(!(cin>>num1)) {cerr<<"?íÎó?ºÊäÈë??ÕýÈ???"; exit(0);}
algorithm=Policy(num1);
if(algorithm!=fifo&&algorithm!=spf&&algorithm!=hpf&&algorithm!=rr)
{cout<<"ÎÞÐ?µÄËã????ÕýÈ???ÇëÖØÐÂÊäÈë?º\n"; goto L1;}
cout<<"\nÏÖÔÚÓÐ"<next;
for(int i=0;i<=n-1;i++)
{
cout<<"ÇëÊäÈë"<id=i;
if(algorithm==hpf)
{
cout<<"????ÓÅÏÈÊý??ÕûÊý??ÖµÔ??ó?íÃ?ÓÅÏÈÈ?Ô??ß???º";
if(!(cin>>Listp->priority))
{cerr<<"?íÎó?ºÊäÈë??ÕýÈ???";exit(0);}
}
cout<<"????ÒÑÕ?ÓÃ?Ã?Ð?ÕÊ??ä??ÕûÊý??ÒÔÊ??äÆ?Ϊµ?Î????º";
if(!(cin>>Listp->cputime))
{cerr<<"?íÎó?ºÊäÈë??ÕýÈ???";exit(0);}
cout<<"??????ÐèÕ?ÓÃ?Ã?Ð?ÕÊ??ä??ÕûÊý??ÒÔÊ??äÆ?Ϊµ?Î????º";
if(!(cin>>Listp->alltime))
{cerr<<"?íÎó?ºÊäÈë??ÕýÈ???";exit(0);}
cout<<"?????ªÊ?×èÈûÊ??ä??ÕûÊý??ÒÔÊ??äÆ?Ϊµ?Î????º";
if(!(cin>>Listp->startblock))
{cerr<<"?íÎó?ºÊäÈë??ÕýÈ???";exit(0);}
cout<<"????×èÈûÊ??ä??ÕûÊý??ÒÔÊ??äÆ?Ϊµ?Î????º";
if(!(cin>>Listp->blocktime))
{cerr<<"?íÎó?ºÊäÈë??ÕýÈ???";exit(0);}
L2:
cout<<"?????ø?Ì×?Ì??????íÊ?ÔËÐÐ?????íÊ??ÍÐ??????íÊ?×èÈû???º";
if(!(cin>>num2)) {cerr<<"?íÎó?ºÊäÈë??ÕýÈ???";exit(0);}
if(num2!=0&&num2!=1&&num2!=2)
{cout<<"×?Ì???ÕýÈ???ÇëÖØÐÂÊäÈë?º\n";goto L2;}
Listp->state=Status(num2);
Listp=Listp->next;
}
PCBpp Run=new PCBptr(); //??Éú?É
PCBpp Ready=new PCBptr[100]; //
for(int i=0;i<=99;i++) *(Ready+i)=0; //??????ÔËÐÐ
PCBpp ReadyEnd=Ready; //?????????ÍÐ?
PCBpp Block=new PCBptr[100]; //??????????×èÈû
for(int i=0;i<=99;i++) *(Block+i)=0; //
PCBpp BlockEnd=Block; //???????????????ÓÁÐ
if(algorithm==hpf||algorithm==spf)
ReadyEnd++;//Èç?ûÊÇ?È?Ð?ÆËã????ÓÃÖ??Ó?åÈëÅÅÐò??*ReadyÊÇÉÚ?ø??Ready+1?ÉΪ?ÓÍ???
for(Listp=Listhead;Listp->next;Listp=Listp->next)
{//?Ñ?õÊ???µÄ?ø?Ì?Å?ø??×Ô?ÓÁÐ
switch(Listp->next->state)
{
case running:*Run=Listp->next;break;
case ready:
{
*ReadyEnd=Listp->next;ReadyEnd++;
if(algorithm==hpf||algorithm==spf)
InsertSort(Ready,ReadyEnd,algorithm);
break;
}
case blocked:*BlockEnd=Listp->next;BlockEnd++;break;
}
}
cout<<"\nÏÖÔÚÕâ"<>x;
for(int time=1;Listhead->next;time++)
{//?ªÊ?????Ö?ÐÐ??
cout<<"\nµÚ"<priority-=3;
(*Run)->cputime++;
if((*Run)->alltime>0)
(*Run)->alltime--;
if((*Run)->startblock>0)
(*Run)->startblock--;
}
if(algorithm==hpf)
{//Ready+1?ÓÁеÄ?ä???? if(*(Ready+1))
for(pp=Ready+1;pp!=ReadyEnd;pp++)
(*pp)->priority++;
}
if(*Block)
{//Block?ÓÁеÄ?ä???? for(pp=Block;pp!=BlockEnd;pp++)
if((*pp)->blocktime>0)
(*pp)->blocktime--;
}
Print(Listhead);
if(*Block)
{
pp=Block;
while(pp!=BlockEnd)
{//?ÑÒÑ?,×èÈûºÃÁ˵Ä?ø?ÌÒƵ??ÍÐ??ÓÁÐ??
if((*pp)->blocktime==0)
{
(*pp)->state=ready;
*ReadyEnd=*pp;ReadyEnd++;
if(algorithm==hpf||algorithm==spf)
InsertSort(Ready,ReadyEnd,algorithm);
for(PCBpp ss=pp;ss!=BlockEnd;ss++)
*ss=*(ss+1);
BlockEnd--;
}
else pp++;
}
}
if(*Run)
{
if((*Run)->alltime==0)
{//Èç?ûÔËÐÐÍêÁË???Ñ?Ã?ø?Ì??Ïú????ÄÃ?ÍÐ??ÓÍ?µÄ?ø?ÌÀ?ÔËÐÐ??
Delete(Listhead,*Run);
RdyToRun(Ready,Run,algorithm); }
else
{//Ã?ÔËÐÐÍê
if((*Run)->startblock==0)
{//Èç?û?Ã×èÈûÁË??Ôò?ÅÈë×èÈû?ÓÁÐ????ÄÃ?ÍÐ??ÓÍ?µÄ?ø?ÌÀ?ÔËÐÐ??
RunToBlk(Run,BlockEnd);
RdyToRun(Ready,Run,algorithm);
}
else
{//Èç?ûÃ?×èÈû
if(algorithm==hpf)
{//ÔÚ?È?Ð?ÆËã??ÏÂ???È?ÏÏÖÔÚÔËÐеÄ?ø?̵ÄÓÅÏÈÈ?ºÍ*(Ready+1)µÄÓÅÏÈÈ?µ
Ä?óÐ???
if(*(Ready+1))
if((*Run)->priority<(*(Ready+1))->priority)
{//ÏÂÌ?ÁË??
(*Run)->state=ready;
*ReadyEnd=*Run;ReadyEnd++;
InsertSort(Ready,ReadyEnd,algorithm);
if(*(Ready+1))
{
(*(Ready+1))->state=running;
*Run=*(Ready+1);
Ready++;
}
}
}
if(algorithm==rr)
{//ÔÚ?ò?òËã??ÏÂ?Í?ÓÈë?ÍÐ??ÓÎ???
(*Run)->state=ready;
*ReadyEnd=*Run;
ReadyEnd++;
if(*Ready)
{
(*Ready)->state=running;
*Run=*Ready;
Ready++;
}
}
}
}
}
else
RdyToRun(Ready,Run,algorithm);
}
return 0;
}
浙公网安备 33021202002483