#include<stdio.h>
#include<stdlib.h>
#define N 320
int num[N]; //存放隨機(jī)數(shù) 
int page[N]; //存放頁(yè)地址流 
int mc[33]; //memory capacity內(nèi)存容量 ，并初始化為0 
 
void randomnumber()//random number隨機(jī)數(shù) 程序第一步，產(chǎn)生320個(gè)指令序列 
{ 
 int pc;
 int flag=0; 
 scanf("%d",&pc); 
 printf("\n在0-319之間產(chǎn)生的320個(gè)隨機(jī)數(shù)如下:\n"); 
 for(int i=0;i<320;i++) 
 { 
 num[i]=pc; 
 if(flag%2==0) pc=++pc%320; //flag=0||2 50%的指令是順序執(zhí)行的 
 if(flag==1) pc=rand()% (pc-1); //flag=1 25%的指令是均勻分布在前地址部分 
 if(flag==3) pc=pc+1+(rand()%(320-(pc+1))); //flag=3 25%的指令是均勻分布在后地址部分 
 flag=++flag%4; 
 printf("%3d ",num[i]); 
 if((i+1)%10==0) printf("\n"); //每行輸出10個(gè)數(shù) 
 } 
} 
 
void pageaddress() //pageaddress頁(yè)地址 程序第二步，將指令序列變換為頁(yè)地址流 
{ 
 for(int i=0;i<320;i++) 
 { 
 printf("%3d ",page[i]=num[i]/10); 
 if((i+1)%10==0) printf("\n"); //每行輸出10個(gè)數(shù) 
 } 
}
 
int FIFO(int capacity)
{
 int j,x,y,m;
 int sum=0; //mc中分配的個(gè)數(shù) 
 int exist=0; //命中次數(shù) 
 int flag; //標(biāo)志是否命中 flag=0沒(méi)命中 flag=1命中 
 int ep=1; //elimination position淘汰位置 
 mc[1]=page[0];
 printf(" %2d加入 \t",page[0]);
 for(m=1;m<=capacity;m++) //輸出當(dāng)前內(nèi)存塊的存儲(chǔ)情況 
 printf("%2d ",mc[m]);
 printf("\n");
 sum+=1; 
 for(j=1;j<320;j++)
 { 
 flag=0; 
 for(y=1;y<=sum;y++) //判斷這個(gè)頁(yè)地址流是否命中 
 if(mc[y]==page[j]) {
 exist++;
 flag=1;
 printf(" %2d命中 \t",page[j]);
 for(m=1;m<=capacity;m++) //輸出當(dāng)前內(nèi)存塊的存儲(chǔ)情況 
 printf("%2d ",mc[m]);
 printf("\n");
 break;} 
 //沒(méi)命中 
 if(flag==0) 
 {
 if(sum<capacity) //還有空塊 
 {for(x=1;x<=capacity;x++) //查找內(nèi)存塊中第一個(gè)空塊 
 if(mc[x]==-1) {
 mc[x]=page[j];
 sum++;
 printf(" %2d加入 \t",page[j]);
 for(m=1;m<=capacity;m++) //輸出當(dāng)前內(nèi)存塊的存儲(chǔ)情況 
 printf("%2d ",mc[m]);
 printf("\n");
 break;}
 }
 else if(sum>=capacity)
 {
 int t=mc[ep];
 mc[ep]=page[j];
 printf(" %2d置換%2d\t",page[j],t);
 for(m=1;m<=capacity;m++) //輸出當(dāng)前內(nèi)存塊的存儲(chǔ)情況 
 printf("%2d ",mc[m]);
 printf("\n");
 ep+=1;
 if(ep==capacity+1) ep=1; 
 } 
 }
 } 
 printf("\nexist=%d\n命中率=%lf",exist,exist/320.0);
} 
int main()
{
 int capacity; //內(nèi)存塊數(shù) 
 printf("請(qǐng)輸入第一條指令號(hào)(0~319):");
 randomnumber();
 printf("\n指令序列對(duì)應(yīng)的頁(yè)地址流:\n"); 
 pageaddress(); 
 printf("\n\n\n\t\t先進(jìn)先出算法(FIFO):\n\n");
 printf("請(qǐng)輸入內(nèi)存塊數(shù)（4-32）：");
 scanf("%d",&capacity);
 for(int i=1;i<=32;i++) //給數(shù)組賦初值 
 mc[i]=-1;
 FIFO(capacity); 
 return 0;
}