cun_chu_guan_li.rar_320条_site:www.pudn.com

#include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<time.h> struct Link_S { int page; Link_S * next; }; FILE * fp; void create_rad(int instructions[],int n); void print_arr(int instructions[],int n); void changeto_page(int instructions[],int n); int LRU_link(int x,Link_S * S,int size); void LRU(int instructions[],int n,int cache); int siteinline(int In[],int x,int size); int OPT_link(Link_S * S,int size,int x,int In[],int n); void OPT(int instructions[],int n,int cache); Link_S * FIFO_link(Link_S * S,Link_S * CS,int * flag,int x,int size); void FIFO(int instructions[],int n,int cache); void printlink(Link_S * S); int main(void) { fp=fopen("result.txt","w"); int instructions[320]; int add=320; int cache=0; fprintf(fp,"随机生成访问地址：\n"); create_rad(instructions,add); print_arr(instructions,add); fprintf(fp,"=================================================\n"); fprintf(fp,"转换成访问页：\n"); changeto_page(instructions,add); print_arr(instructions,add); fprintf(fp,"=================================================\n"); printf("请输入cache容量(4-32)："); scanf("%d",&cache); while(cache<4||cache>32) { printf("!!请输入一个4-32的数!!\n"); scanf("%d",&cache); } fprintf(fp,"下面以上示页表访问序列，以及cache为%d个页表大小的情况进行模拟：\n\n",cache); fprintf(fp,"LRU:\n"); LRU(instructions,add,cache); fprintf(fp,"OPT:\n"); OPT(instructions,add,cache); fprintf(fp,"FIFO:\n"); FIFO(instructions,add,cache); fclose(fp); return 0; } void create_rad(int instructions[],int n) { srand((int)time(0)); int i,x,y; for(i=0;i<n;) { x=rand()%n; y=rand()%(x+1); instructions[i]=y; i++; y=rand()%(n-x); instructions[i]=y+x; i++; } } void changeto_page(int instructions[],int n) { int i; for(i=0;i<n;i++) { instructions[i]=instructions[i]/10; } } void print_arr(int instructions[],int n) { int i; for(i=0;i<n;i++) { fprintf(fp,"%5d",instructions[i]); if((i+1)%10==0) { fprintf(fp,"\n"); } } } //最近最少使用算法（LRU） void printlink(Link_S * S) { Link_S * C_S=S->next; fprintf(fp,"cache列表："); while(C_S) { fprintf(fp,"%3d",C_S->page); C_S=C_S->next; } fprintf(fp,"\n"); } int LRU_link(int x,Link_S * S,int size) { Link_S * C_S1=S->next; Link_S * C_S2=S->next; Link_S * C_S3=S; Link_S * New; for(;C_S1;) { if(C_S1->page==x) { if(C_S1==S->next) { } else { C_S3->next=C_S1->next; S->next=C_S1; C_S1->next=C_S2; } fprintf(fp,"—！！！命中！！！—\n"); printlink(S); return 1; } C_S3=C_S3->next; C_S1=C_S1->next; } New=(Link_S*)malloc(sizeof(Link_S)); New->page=x; New->next=S->next; S->next=New; S->page++; C_S1=S->next; C_S2=S; if(S->page>size) { while(C_S1->next) { C_S2=C_S1; C_S1=C_S1->next; } C_S2->next=NULL; S->page--; free(C_S1); } fprintf(fp,"——产生缺页中断——\n"); fprintf(fp,"———缺 %d 页———\n",x); printlink(S); return 0; } void LRU(int instructions[],int n,int cache) { int U=0; float per; Link_S * S; S=(Link_S*)malloc(sizeof(Link_S)); S->page=0; S->next=NULL; int i=0,flag=0; for(i=0;i<n;i++) { fprintf(fp,"访问%d页表\n",instructions[i]); flag=LRU_link(instructions[i],S,cache); if(flag==1){U++;} fprintf(fp,"\n"); } per=(float)U/n; printf("LRU算法命中率为：%d/%d %f\n",U,n,per); fprintf(fp,"LRU算法命中率为：%d/%d %f\n",U,n,per); } //最佳淘汰算法（OPT） int siteinline(int In[],int x,int size) { int i=0; for(i=0;i<size;i++) { if(In[i]==x) return i; } return i; } int OPT_link(Link_S * S,int size,int x,int In[],int n) { Link_S * C_S1=S->next; Link_S * C_S2=S->next; Link_S * C_S3=S; Link_S * New; for(;C_S1;) { if(C_S1->page==x) { fprintf(fp,"—！！！命中！！！—\n"); printlink(S); return 1; } C_S3=C_S3->next; C_S1=C_S1->next; } New=(Link_S*)malloc(sizeof(Link_S)); New->page=x; New->next=NULL; if(S->page<size) { C_S3->next=New; S->page++; } else { C_S1=S->next; int num1,num2; Link_S * Values; num1=siteinline(In,C_S1->page,n); Values=C_S1; for(;C_S1;) { num2=siteinline(In,C_S1->page,n); if(num2>num1) { num1=num2; Values=C_S1; } C_S1=C_S1->next; } Values->page=x; } fprintf(fp,"——产生缺页中断——\n"); fprintf(fp,"———缺 %d 页———\n",x); printlink(S); return 0; } void OPT(int instructions[],int n,int cache) { int U=0; float per; Link_S * S; S=(Link_S*)malloc(sizeof(Link_S)); S->page=0; S->next=NULL; int i=0,flag=0; for(i=0;i<n;i++) { fprintf(fp,"访问%d页表\n",instructions[i]); flag=OPT_link(S,cache,instructions[i],instructions+i,n-i); if(flag==1){U++;} fprintf(fp,"\n"); } per=(float)U/n; printf("OPT算法命中率为：%d/%d %f\n",U,n,per); fprintf(fp,"OPT算法命中率为：%d/%d %f\n",U,n,per); } //先进先出的算法（FIFO） Link_S * FIFO_link(Link_S * S,Link_S * CS,int * flag,int x,int size) { Link_S * C_S1=S->next; Link_S * C_S2=S; while(C_S1) { if(C_S1->page==x) { fprintf(fp,"—！！！命中！！！—\n"); printlink(S); (*flag)=1; return CS; } C_S2=C_S1; C_S1=C_S1->next; } fprintf(fp,"——产生缺页中断——\n"); fprintf(fp,"———缺 %d 页———\n",x); (*flag)=0; if(S->page<size) { Link_S * New; New=(Link_S*)malloc(sizeof(Link_S)); New->page=x; New->next=NULL; C_S2->next=New; S->page++; printlink(S); return S->next; } else { CS->page=x; CS=CS->next; if(CS==NULL) { CS=S->next; } printlink(S); return CS; } } void FIFO(int instructions[],int n,int cache) { int U=0; float per; Link_S * S; Link_S * CS; S=(Link_S*)malloc(sizeof(Link_S)); S->page=0; S->next=NULL; CS=S; int i=0,flag=0; for(i=0;i<n;i++) { fprintf(fp,"访问%d页表\n",instructions[i]); CS=FIFO_link(S,CS,&flag,instructions[i],cache); if(flag==1){U++;} fprintf(fp,"\n"); } per=(float)U/n; printf("FIFO算法命中率为：%d/%d %f\n",U,n,per); fprintf(fp,"FIFO算法命中率为：%d/%d %f\n",U,n,per); }