惠州学院操作系统-实验四

惠州学院操作系统-实验四 一、 实验目的 通过模拟实现请求分页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。 二、 实验器材 微型计算机、fedora版本的Linux系统 三、 实验5，„，32个 //页结构 //pn是页号，pfn是块号，counter是访问次数 //页数组 //块(页面)结构 { int pn, pfn; struct pfc_type *next; }pfc_type; pfc_type pfc[32], *freepf_head, *busypf_head, *busypf_tail; //块数组，空闲队列头指针，FIFO队列头、尾指针 int diseffect; //缺页计数器 int a[320], page[320], offset[320]; void initialize(int); void FIFO(int); void LRU(int); int main( ) { int s,i,j; srand(10*getpid()); //初始化随机数发生器。由于每次运行时 进程号不同，故可用来作为初始化随机数序列的“种子” s=(float)319*rand( )/32767/32767/2+1; //产生一个0~319之间的随机数，即计算第一条要访问指令的地址s for(i=0;i<320;i+=4) { a[i]=s; a[i+1]=a[i]+1; s的下一条指令*/ /*产生指令访问的地址序列*/ /*地址s存入a[i]*/ 地址s+1存入a[i+1]，示顺序执行 /* a[i+2]=(float)a[i]*rand( )/32767/32767/2; /*产生0~a[i+1]之间的随机数，即计算 s的一条任意的前地址指令的地址s’，并存入a[i+2]，表示向前跳转*/ a[i+3]=a[i+2]+1; /*地址s’+1存入a[i+3]，表示顺序执行s’的下一条指令*/ s=(float)(318-a[i+2])*rand( )/32767/32767/2+a[i+2]+2; /*产生a[i+3]~319之间的随机数，即 计算s’的一条任意的后地址指令的地址s，表示向后跳转*/ } /*(1)end，产生了320指令的访问序列*/ for (i=0;i<320;i++) { } /*(2)end*/ for(i=4;i<=32;i++) page[i]=a[i]/10; offset[i]=a[i]%10; /*将指令访问序列变换成页地址流*/ /*计算地址a[i]的页号*/ /*计算地址a[i]的页内偏移地址*/ /*用户内存工作区从4个块(页面)到32 个块(页面)*/ { } /*(3)end*/ } void FIFO(total_pf) int total_pf; { int i; pfc_type *p; initialize(total_pf); /*初始化相关页面控制用数据结构*/ busypf_head=busypf_tail=NULL; /*FIFO队列(已调入 /*对于指令访问序列中的每一个地址*/ { if(pl[page[i]].pfn==-1) /*如果缺页，则需要调入页*/ { diseffect+=1; /*计算失效次数*/ if(freepf_head==NULL)/*如果无空闲块，则需要换页*/ { /*先进先出页面置换算法*/ /*用户进程的 /*先入先出算法*/ LRU(i); /*最少访问页淘汰算法*/ printf("\n"); p=busypf_head; busypf_head=busypf_head->next; } pl[p->pn].pfn=-1; /*换出FIFO队列的第一个块中的页*/ freepf_head=p; /*将换得的块放入空闲队列*/ freepf_head->next=NULL; p=freepf_head; freepf_head=freepf_head->next; p->next=NULL; /*摘下第一个空闲块*/ p->pn=page[i]; pl[page[i]].pfn=p->pfn; /*将新调入的页装进摘下的空闲块*/ if(busypf_tail==NULL) /*如果 busypf_tail=p; } /*新调入的页挂在FIFO队列的尾上*/ } } printf("FIFO:%6.4f\n",1-(float)diseffect/320); } void LRU(total_pf) int total_pf; { int i,j,min,minpage; pfc_type *t; initialize(total_pf); /*初始化相关页面控制用数据结构*/ /*最不经常使用页面置换法*/ for(i=0;i<320;i++) /*对于指令访问序列中的每一个地址*/ { if (pl[page[i]].pfn==-1) /*如果缺页，则需要调入页*/ { diseffect++; if(freepf_head==NULL) /*如果无空闲页面，则需要换页*/ { min=32767; for(j=0;j<32;j++) /*找在 { if(min>pl[j].counter && pl[j].pfn!=-1) } */ { min=pl[j].counter; minpage=j; pl[j].counter=0;/*将所有页的访问计数器清零} freepf_head=&pfc[pl[minpage].pfn]; freepf_head->next=NULL; /*将换得的块挂到空闲队列上*/ pl[minpage].pfn=-1; /*将访问次数最小的页换出*/ } pl[page[i]].pfn=freepf_head->pfn; /*将调入的页放进空闲队列的第一块*/ freepf_head->pn=page[i]; pl[page[i]].counter++; freepf_head=freepf_head->next; /*减少一个free页面*/ } else /*如果不缺页*/ pl[page[i]].counter++; } printf("LRU:%6.4f\n",1-(float)diseffect/320); } void initialize(total_pf) /*初始化相关数据结构*/ int total_pf; /*用户进程获得的for(i=0;i<32;i++) pl[i].pn=i; pl[i].pfn=-1; /*置每一页结构中的块号为-1，表示还没调入 pl[i].counter=0; /*置每一页结构中的访问次数为0*/ /*块的数据结构初始化*/ } for(i=0;i<total_pf-1;i++) { pfc[i].pfn=i; pfc[i].next=&pfc[i+1]; } /*将进程获得的total_pf个块链接成空闲块队列*/ pfc[total_pf-1].pfn=total_pf-1; pfc[total_pf-1].next=NULL; /*处理最后一块*/ freepf_head=&pfc[0]; } 程序运行截图如下: /*空闲块队列的头指针指向pfc[0]*/ EXCEL截图如下: 框图如下: 1、LRU框图: 2、FIFO框图