¡¶²Ù×÷ϵͳ¡·´æ´¢¹ÜÀíʵÑ鱨¸æ

____´óѧ____ѧԺʵÑ鱨¸æ

µÚ¶þƪ£º±±ÓÊ´óÈýÉÏ-²Ù×÷ϵͳ-´æ´¢¹ÜÀíʵÑ鱨¸æ

²Ù×÷ϵͳʵÑéÈý´æ´¢¹ÜÀíʵÑé

°à¼¶£º

ѧºÅ£º

ÐÕÃû£º

Ŀ ¼

1. ʵÑéÄ¿µÄ... 2

2. ʵÑéÄÚÈÝ... 2

(1) ͨ¹ýËæ»úÊý²úÉúÒ»¸öÖ¸ÁîÐòÁУ¬¹²320ÌõÖ¸Áî... 2

(2) ½«Ö¸ÁîÐòÁб任³ÉΪҳµØÖ·Á÷... 2

(3) ¼ÆËã²¢Êä³öÏÂÊö¸÷ÖÖËã·¨ÔÚ²»Í¬ÄÚ´æÈÝÁ¿ÏµÄÃüÖÐÂÊ... 2

3. Ëæ»úÊý²úÉú°ì·¨... 3

»·¾³ËµÃ÷... 3

4. ³ÌÐòÉè¼Æ˵Ã÷... 3

4.1. È«¾Ö±äÁ¿... 3

4.2. Ëæ»úÖ¸ÁîÐòÁеIJúÉú... 4

4.3. FIFOËã·¨... 4

4.4. LRUËã·¨... 4

4.5. OPTËã·¨... 5

5. ±à³ÌʵÏÖ£¨Ô´³ÌÐò£©£º... 5

6. ÔËÐнá¹û¼°·ÖÎö... 11

6.1. ÔËÐУ¨ÒÔijÁ½´ÎÔËÐнá¹ûΪÀý£¬ÁбíÈçÏ£º£©... 11

6.2. Belady¡¯s anomaly. 11

1. ʵÑéÄ¿µÄ

´æ´¢¹ÜÀíµÄÖ÷Òª¹¦ÄÜÖ®Ò»ÊǺÏÀíµØ·ÖÅä¿Õ¼ä¡£ÇëÇóҳʽ¹ÜÀíÊÇÒ»ÖÖ³£ÓõÄÐéÄâ´æ´¢¹ÜÀí¼¼Êõ¡£

±¾ÊµÑéµÄÄ¿µÄÊÇͨ¹ýÇëÇóҳʽ´æ´¢¹ÜÀíÖÐÒ³ÃæÖû»Ë㷨ģÄâÉè¼Æ£¬Á˽âÐéÄâ´æ´¢¼¼ÊõµÄÌص㣬ÕÆÎÕÇëÇóҳʽ´æ´¢¹ÜÀíµÄÒ³ÃæÖû»Ëã·¨¡£

2. ʵÑéÄÚÈÝ

(1) ͨ¹ýËæ»úÊý²úÉúÒ»¸öÖ¸ÁîÐòÁУ¬¹²320ÌõÖ¸Áî

Ö¸ÁîµÄµØÖ·°´ÏÂÊöÔ­ÔòÉú³É£º

a) 50% µÄÖ¸ÁîÊÇ˳ÐòÖ´Ðеģ»

b) 25% µÄÖ¸ÁîÊǾùÔÈ·Ö²¼ÔÚÇ°µØÖ·²¿·Ö£»

c) 25% µÄÖ¸ÁîÊǾùÔÈ·Ö²¼ÔÚºóµØÖ·²¿·Ö£»

¾ßÌåµÄʵʩ·½·¨ÊÇ£º

a) ÔÚ[0£¬319]µÄÖ¸ÁîµØÖ·Ö®¼äËæ»úÑ¡È¡Ò»Æðµãm£»

b) ˳ÐòÖ´ÐÐÒ»ÌõÖ¸Á¼´Ö´ÐеØַΪm+1µÄÖ¸Á

c) ÔÚÇ°µØÖ·[0£¬m+1]ÖÐËæ»úÑ¡È¡Ò»ÌõÖ¸Áî²¢Ö´ÐУ¬¸ÃÖ¸ÁîµÄµØַΪm¢;

d) ˳ÐòÖ´ÐÐÒ»ÌõÖ¸ÁÆäµØַΪm¢+1;

e) ÔÚºóµØÖ·[m¢+2£¬319]ÖÐËæ»úÑ¡È¡Ò»ÌõÖ¸Áî²¢Ö´ÐÐ;

f) Öظ´ÉÏÊö²½Öèa)~f)£¬Ö±µ½Ö´ÐÐ320´ÎÖ¸Áî¡£

(2) ½«Ö¸ÁîÐòÁб任³ÉΪҳµØÖ·Á÷

É裺

a) Ò³Ãæ´óСΪ1K£»

b) Óû§ÄÚ´æÈÝÁ¿Îª4Ò³µ½32Ò³£»

c) Óû§Ðé´æÈÝÁ¿Îª32K¡£

ÔÚÓû§Ðé´æÖУ¬°´Ã¿K´æ·Å10ÌõÖ¸ÁîÅÅÁÐÐé´æµØÖ·£¬¼´320ÌõÖ¸ÁîÔÚÐé´æÖеĴæ·Å·½Ê½Îª£º

µÚ0Ìõ~µÚ9ÌõÖ¸ÁîΪµÚ0Ò³£¨¶ÔÓ¦Ðé´æµØַΪ[0£¬9]£©£»

µÚ10Ìõ~µÚ19ÌõÖ¸ÁîΪµÚ1Ò³£¨¶ÔÓ¦Ðé´æµØַΪ[10£¬19]£©£»

¡­

¡­

µÚ310Ìõ~µÚ319ÌõÖ¸ÁîΪµÚ31Ò³£¨¶ÔÓ¦Ðé´æµØַΪ[310£¬319]£©¡£

°´ÒÔÉÏ·½Ê½£¬Óû§Ö¸Áî¿ÉÒÔ×é³É32Ò³¡£

(3) ¼ÆËã²¢Êä³öÏÂÊö¸÷ÖÖËã·¨ÔÚ²»Í¬ÄÚ´æÈÝÁ¿ÏµÄÃüÖÐÂÊ

a) ÏȽøÏȳöµÄËã·¨£¨FIFO£©£»

b) ×î½ü×îÉÙʹÓÃËã·¨£¨LRU£©£»

c) ×î¼ÑÌÔÌ­Ëã·¨£¨OPT£©£»

ÃüÖÐÂÊ=1-Ò³ÃæʧЧ´ÎÊý/Ò³µØÖ·Á÷³¤¶È

ÔÚ±¾ÊµÑéÖУ¬Ò³µØÖ·Á÷³¤¶ÈΪ320£¬Ò³ÃæʧЧ´ÎÊýΪÿ´Î·ÃÎÊÏàÓ¦Ö¸Áîʱ£¬¸ÃÖ¸ÁîËù¶ÔÓ¦µÄÒ³²»ÔÚÄÚ´æµÄ´ÎÊý¡£

3. Ëæ»úÊý²úÉú°ì·¨

¹ØÓÚËæ»úÊý²úÉú°ì·¨£¬¿ÉÒÔ²ÉÓòÙ×÷ϵͳÌṩµÄº¯Êý£¬ÈçLinux»òUNIXϵͳÌṩº¯Êýsrand()ºÍrand()£¬·Ö±ð½øÐгõʼ»¯ºÍ²úÉúËæ»úÊý¡£ÀýÈ磺

srand();

Óï¾ä¿ÉÒÔ³õʼ»¯Ò»¸öËæ»úÊý£»

a[0]=10*rand()/32767*319+1;

a[1]=10*rand()/32767*a[0];

¡­

Óï¾ä¿ÉÒÔÓÃÀ´²úÉúa[0]Óëa[1]ÖеÄËæ»úÊý¡£

»·¾³ËµÃ÷

´ËʵÑé²ÉÓõÄÊÇWin7ÏÂCode::blocks 10.05±àÒëÆ÷±à³Ì¡£

´ËwordʵÑéÎĵµÖвÉÓÃnotepad++µÄÓï·¨¸ßÁÁ¡£

4. ³ÌÐòÉè¼Æ˵Ã÷

4.1. È«¾Ö±äÁ¿

const int maxn=320;//ÐòÁиöÊý

const int max=maxn+20;//Êý×é´óС

const int maxp=max/10;//×î´óÒ³Êý

int inst[max];//Ö¸ÁîÐòÁÐ

int page[max];//Ò³µØÖ·Á÷

int size;//ÄÚ´æÄÜÈÝÄɵÄÒ³Êý

bool in[maxp];//¸ÃÒ³ÊÇ·ñÔÚÄÚ´æÀÌá¸ßЧÂÊ

int pin[maxp];//ÏÖÔÚÔÚÄÚ´æÀïµÄÒ³

ÆäÖÐin[]Êý×éÊÇΪÁË·½±ãÖ±½ÓÅжϸÃÒ³ÊÇ·ñÔÚÄÚ´æÀ¶ø²»ÓñéÀúÄÚ´æÀïËùÓÐÒ³À´Åжϡ£

fault_nÓÃÀ´¼Ç¼ȱҳ´ÎÊý¡£

4.2. Ëæ»úÖ¸ÁîÐòÁеIJúÉú

°´ÕÕʵÑéÒªÇóµÄдÁË£¬µ«ÊÇÓÉÓÚûÓп¼ÂÇϸ½Ú£¬¿ªÊ¼Ê±³öÁ˵ãÎÊÌâ¡£

£¨1£© µ±m=319ʱ£¬ÎÒÃÇ˳ÐòÖ´ÐÐm+1»á²úÉúµÚ32Ò³µÄÒ³µØÖ·£¬´Ó¶øʹҳµØַûÄÜ°´ÒªÇóÏÞÖÆÔÚ[0, 31]Ö®¼ä¡£

½â¾ö·½·¨£º²ÉÓÃÑ­»·Ä£¼ÓÀ´±ÜÃⳬ³ö·¶Î§¡£

£¨2£© µ«ÊÇÕâÑùÖ®ºóÓпÉÄܳöÏÖÄ£0µÄÎÊÌâ¡£ËùÒÔÎÒË÷ÐÔ½«µÈÓÚ0µÄÄ£Êý¶¼¸³ÖµÎª160.

×îºóµÄ³ÌÐòÈçÏ¡£

void produce_inst()

{

int m,n;

int num=0;

while(num£¼maxn)

{

m=rand()%maxn;

inst[num++]=(m+1)%maxn;

if(num==maxn)break;

m=(m+2)%maxn;

if(m==0)m=160;

n=rand()%m;

inst[num++]=(n+1)%maxn;

if(num==maxn)break;

n=(n+2)%maxn;

m=maxn-n;

if(m==0)m=160;

m=rand()%m+n;

inst[num++]=m;

}

}

4.3. FIFOËã·¨

¶¨Òå±äÁ¿ptr¡£

Ò»¿ªÊ¼ÏÈÔ¤µ÷Ò³ÌîÂúÄÚ´æ¡£ÔÚÕâÒ»²¿·Ö£¬ptrÖ¸ÏòÏÂÒ»¸öÒª´æ·ÅµÄλÖá£

Ö®ºó¼ÌÐøÖ´ÐÐʣϵÄÖ¸Áî¡£´Ëʱ£¬ptr±íʾ¶ÓÁÐ×îÇ°ÃæµÄλÖ㬼´×îÏȽøÀ´µÄλÖã¬Ò²¾ÍÊÇÏÂÒ»¸öÒª±»Ìæ»»µÄλÖá£ptrÓÃÑ­»·¼Ó£¬¼´Ä£ÄâÑ­»·¶ÓÁС£

4.4. LRUËã·¨

¶¨ÒåÊý×éltu[],¼´last_time_useÀ´¼Ç¼¸ÃÒ³×î½ü±»Ê¹ÓõÄʱ¼ä¡£

¶¨Òå±äÁ¿tiÄ£Äâʱ¼äµÄ±ä»¯£¬Ã¿Ö´ÐÐÒ»´Î¼ÓÒ»¡£

Õâ¸öËã·¨£¬ÎÒûÓÐÔ¤µ÷Ò³£¬¶øÊÇÖ±½ÓÖ´ÐÐËùÓÐÖ¸Áî¡£

Èôµ±Ç°ÐèÒªµÄҳûÔÚÄÚ´æÀ¾ÍÑ°ÕÒ×î½ü×îÉÙʹÓõÄÒ³£¬Ò²¾ÍÊÇltu[]×îСµÄÒ³£¬¼´×î½üÒ»´ÎʹÓÃʱ¼äÀëÏÖÔÚ×î¾ÃµÄÒ³£¬È»ºóÌæ»»µôËü¡£»òÕßÔÚÄڴ滹δÂúʱ£¬Ö±½ÓдÈ룬Õâ¸öÎÒÒÔ³õʼ»¯ÄÚ´æÀïËùÓÐҳΪ-1À´ÊµÏÖ¡£

ÈôÒѾ­ÔÚÄÚ´æÀïÁË£¬ÔòÖ»±éÀúÄÚ´æÄÚµÄÒ³£¬°Ñµ±Ç°Ò³µÄ×î½üʹÓÃʱ¼ä¸Äһϼ´¿É¡£

4.5. OPTËã·¨

¶¨ÒåÊý×éntu[], ¼´next_time_useÀ´¼Ç¼ÏÂÒ»´Î±»Ê¹ÓõÄʱ¼ä£¬¼´½«À´×î¿ìʹÓÃʱ¼ä¡£³õʼ»¯Îª-1.

¿ªÊ¼Ê±Ô¤µ÷Ò³ÌîÂúÄÚ´æÀïµÄÒ³¡£Í¬ÑùÀûÓñäÁ¿ptrÀ´±íʾÏÂÒ»¸öÒª´æ·ÅµÄλÖôӶø¿ØÖÆÔ¤µ÷Ò³µÄ¹ý³Ì¡£

½Ó×ųõʼ»¯ntuÊý×éΪ-1¡£È»ºóÇó³öÿһҳÏÂÒ»´Î±»Ê¹ÓõÄÖ¸ÁîºÅ£¬ÒÔ´Ë´úÌæʹÓÃʱ¼ä¡£Èç¹ûËùÓÐʣϵÄÐòÁж¼Ã»ÓÐÓøÃҳʱ£¬Ôò»¹ÊÇ-1.ÕâÖÖֵΪ-1µÄÒ³ÏÔÈ»ÊÇ×î¼ÑÌæ»»¶ÔÏó¡£

È»ºóÖ´ÐÐËùÓÐʣϵÄÖ¸Áî¡£µ±¸ÃÒ³²»ÔÚÄÚ´æÀïʱ£¬±éÀúntuÊý×飬Óöµ½-1µÄÖ±½ÓʹÓøÃÒ³£¬Ã»ÓÐÔòÓÃntu[]Öµ×î´óµÄ£¬Ò²¾ÍÊÇ×îÍíʹÓõġ£

ÎÞÂÛ¸ÃÒ³ÔÚ²»ÔÚÄÚ´æÀÒòΪÕâÒ»´ÎÒѾ­±»Ê¹ÓÃÁË£¬ËùÒÔ¶¼Ó¦¸Ã¸üÐÂÕâ¸öÒ³µÄntu[]£¬Ö»ÐèÍùÇ°¿´ÒªÖ´ÐеÄÒ³Á÷£¬¼Ç¼ÏµÚÒ»¸öÓöµ½µÄ¸ÃÒ³¼´¿É¡£Èç¹ûûÓÐÕÒµ½Í¬ÑùÌí-1¼´¿É¡£

5. ±à³ÌʵÏÖ£¨Ô´³ÌÐò£©£º

#include

#include

#include

#include

usingnamespacestd;

const int maxn=320;//ÐòÁиöÊý

const int max=maxn+20;//Êý×é´óС

const int maxp=max/10;//×î´óÒ³Êý

int inst[max];//Ö¸ÁîÐòÁÐ

int page[max];//Ò³µØÖ·Á÷

int size;//ÄÚ´æÄÜÈÝÄɵÄÒ³Êý

bool in[maxp];//¸ÃÒ³ÊÇ·ñÔÚÄÚ´æÀÌá¸ßЧÂÊ

int pin[maxp];//ÏÖÔÚÔÚÄÚ´æÀïµÄÒ³

void welcome()

{

printf("******************************************\n");

printf("** By schnee On20##-12-06 **\n");

printf("** °à¼¶:09211311 °àÄÚÐòºÅ£º30 **\n");

printf("******************************************\n\n");

}

void input_hint()

{

printf("\n1--create new instruction sequence 2--set memory page number(4 to 32)\n");

printf("3--solve by FIFO algorithm 4--solve by LRU algorithm\n");

printf("5--solve by OPT algorithm 0--exit\n");

printf("*********Please input Your choice: ");

}

/*ͨ¹ýËæ»úÊý²úÉúÒ»¸öÖ¸ÁîÐòÁУ¬¹²320ÌõÖ¸Áî*/

void produce_inst()

{

int m,n;

int num=0;

while(num£¼maxn)

{

m=rand()%maxn;

inst[num++]=(m+1)%maxn;

if(num==maxn)break;

m=(m+2)%maxn;

if(m==0)m=160;

n=rand()%m;

inst[num++]=(n+1)%maxn;

if(num==maxn)break;

n=(n+2)%maxn;

m=maxn-n;

if(m==0)m=160;

m=rand()%m+n;

inst[num++]=m;

}

}

/*½«Ö¸ÁîÐòÁб任³ÉΪҳµØÖ·Á÷*/

void turn_page_address()

{

for(int i=0;i£¼maxn;i++)

page[i]=inst[i]/10;

}

void FIFO_solve()

{

memset(in,false,sizeof(in));

int fault_n=0;//ȱҳÂÊ

int ptr,i;

//Ô¤µ÷Ò³ÌîÂú¿Õ¼ä

ptr=0;//ÏÂÒ»¸öÒª·ÅµÄλÖÃ

for(i=0;i£¼maxn&&ptr£¼size;i++)

if(!in[page[i]])

{

pin[ptr++]=page[i];

in[page[i]]=true;

fault_n++;

}

//¼ÌÐøÖ´ÐÐʣϵÄÖ¸Áî

ptr=0;//¶ÓÁÐÀï×îÏȽøÀ´µÄλÖ㬼´ÏÂÒ»¸öÒª±»Ìæ»»µÄλÖÃ

for(;i£¼maxn;i++)

if(!in[page[i]])

{

in[pin[ptr]]=false;

in[page[i]]=true;

pin[ptr]=page[i];

fault_n++;

ptr=(ptr+1)%size;

}

printf("\nBy FIFO algorithm, the fault-page number is: %d\n",fault_n);

printf(" the hit ratio is : %.2lf\n",(1-(fault_n+0.0)/320.0));

}

void LRU_solve()

{

int ltu[maxp];//last_time_use

int ti=1;//Ä£Äâʱ¼ä

int fault_n=0;

memset(ltu,0,sizeof(ltu));

memset(in,false,sizeof(in));

memset(pin,-1,sizeof(pin));

int min,ptr,i,j;

for(i=0;i£¼maxn;i++)

{

if(!in[page[i]])

{

//Ñ°ÕÒlru

min=1000000;ptr=0;

for(j=0;j£¼size;j++)

{

if(ltu[j]£¼min)

{

min=ltu[j];

ptr=j;

}

}

//Ìæ»»»òдÈë

if(pin[ptr]!=-1)

in[pin[ptr]]=false;

in[page[i]]=true;

pin[ptr]=page[i];

fault_n++;

ltu[ptr]=ti++;

}

else//ÒѾ­ÔÚÄÚ´æÀïÔòÖ»Ðè¸ü¸Ä×î½üʹÓÃʱ¼ä

{

for(j=0;j£¼size;j++)

if(pin[j]==page[i])

{

ltu[j]=ti++;

break;

}

}

}

printf("\nBy LRU algorithm, the fault-page number is: %d\n",fault_n);

printf(" the hit ratio is : %.2lf\n",(1-(fault_n+0.0)/320.0));

}

void OPT_solve()

{

int ntu[maxp];//next_time_use

int fault_n=0;

int i,j;

memset(in,false,sizeof(in));

memset(ntu,-1,sizeof(ntu));

//Ô¤µ÷Ò³ÌîÂú

int ptr=0;

for(i=0;i£¼maxn&&fault_n£¼size;i++)

{

if(!in[page[i]])

{

in[page[i]]=true;

pin[ptr]=page[i];

fault_n++;

ptr++;

}

}

//³õʼ»¯ntuÊý×é

ptr=0;

for(j=i;j£¼maxn&&ptr£¼32;j++)

{

if(ntu[page[j]]==-1)

{

ntu[page[j]]=j;

ptr++;

}

}

int max;

for(;i£¼maxn;i++)

{

if(!in[page[i]])

{

max=0;ptr=0;

for(j=0;j£¼size;j++)

{

if(ntu[pin[j]]==-1)

{

ptr=j;

break;

}

if(ntu[pin[j]]£¾max)

{

max=ntu[pin[j]];

ptr=j;

}

}

in[pin[ptr]]=false;

in[page[i]]=true;

pin[ptr]=page[i];

fault_n++;

}

ntu[page[i]]=-1;

for(j=i+1;j£¼maxn;j++)

if(page[j]==page[i])

{

ntu[page[i]]=j;

break;

}

}

printf("\nBy OPT algorithm, the fault-page number is: %d\n",fault_n);

printf(" the hit ratio is : %.2lf\n",(1-(fault_n+0.0)/320.0));

}

int main()

{

srand(time(NULL));

welcome();

int choice;

while(1)

{

input_hint();

scanf("%d",&choice);

printf("\n");

if(choice==0)

{

printf("BYE-BYE!!!\n");

break;

}

if(choice==1)

{

produce_inst();

turn_page_address();

printf("New page address sequence is set OK!!!\n");

}

elseif(choice==2)

{

printf("Please input the size of memory page number: ");

scanf("%d",&size);

}

elseif(choice==3)

FIFO_solve();

elseif(choice==4)

LRU_solve();

elseif(choice==5)

OPT_solve();

else

printf("INPUT ERROR !!! \n");

}

return0;

}

6. ÔËÐнá¹û¼°·ÖÎö

6.1. ÔËÐУ¨ÒÔijÁ½´ÎÔËÐнá¹ûΪÀý£¬ÁбíÈçÏ£º£©

Ëæ×ÅÒ³ÊýµÄÔö¶à£¬³ýÁËFIFO¶ÔijЩÐòÁлáÓÐBelady¡¯s anomaly£¨Ïê¼û6.2£©Í⣬´ó²¿·ÖÇé¿öºÍLRUËã·¨¡¢OPTËã·¨¶¼ÊÇȱҳÂʼõС¡£

OPTÊÇÀíÏëÇé¿ö£¬Ð§ÂÊÊÇ×î¸ßµÄ¡£µ±È»µ±²»È±Ò³Ê±£¬ËùÓеÄË㷨ȱҳ´ÎÊý¶¼ÊÇ°ÑËùÓÐÒ³µ÷½øÈ¥µÄ´ÎÊý¡£

LRUËã·¨ÓÐʱºòºÍFIFOËã·¨µÄЧÂʲî±ð²¢²»´ó¡£ÉõÖÁÓÐʱºòËü»¹±ÈFIFOµÍһЩµÄ¡£

6.2. Belady¡¯s anomaly

ÈçÏ£¬ÎÒÉÔ΢¸ÄÁËÏÂÊäÈ룬ÊÖ¶¯ÊäÈë¿Î±¾ÉϵÄÑùÀý£¬±à³Ì¼ûÖ¤ÁËBeladyÒì³£ÏÖ¡£ÕâÊÇÖ»ÓÐFIFOËã·¨²ÅÓеÄÒì³£¡£