一. 实验目的
（1）理解虚拟内存管理的原理和技术；
（2）掌握请求分页存储管理中的页面置换算法；
（3）理解请求分页中的按需调页机制。
二. 实验内容
设计一个虚拟存储区和一个内存工作区，并使用先进先出（FIFO）算法来计算命中率。要求如下：
(1) 通过随机数产生一个指令序列，里面共320条指令；
(2) 将指令序列转换成页面序列。假设：页面大小为1KB，用户内存容量为4~32页，用户虚存容量为32KB。在用户虚存中，按每页存放10条指令排列虚存低值，320条指令将存放在32个页面中。
(3) 计算出置换算法在不同内存容量下的访问命中率。
(4) 访问命中率=1-（页面失效次数/页面访问总数）
三. 实验步骤
（1）编写C程序：
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #define TRUE 1 #define FALSE 0 #define INVALID -1 #define total_instruction 321 #define total_vp 32 //这里是 页表项 的 数组 typedef struct { int pn; //页号 int pfn; //内存块号 int counter; int time; } p1_type; p1_type p1[total_vp]; //这里是 页表项 的 链表 typedef struct pfc_struct { int pn; int pfn; struct pfc_struct *next; } pfc_type; pfc_type pfc[total_vp]; pfc_type *freepf_head; pfc_type *busypf_head; pfc_type *busypf_tail; int diseffect; int a[total_instruction]; //指令流数组 int page[total_instruction]; //每条指令 所属页号 int offset[total_instruction]; void initialize(); void FIFO(int total_pf); int main() { int s,i,j; int pid=getpid(); printf("pid=%d\n",pid); srand(10*pid); s=(float)319*rand()/32767/32767/2+1; printf("initialize s==%d\n",s); for(i=0; i<total_instruction; i+=4) { if(s<0 || s>319) { printf("When i==%d, Error, s==%d\n",i,s); exit(0); } a[i]=s; a[i+1]=a[i]+1; //a[i+2]=(float)a[i]*rand()/32767/32767/2; a[i+2]=(float)a[i]*rand()/32767/2; //printf("a[%d+2]=%d\n",i,a[i+2]); a[i+3]=a[i+2]+1; //s=(float)(318-a[i+2])*rand()/32767/32767/2+a[i+2]+2; s=(float)(318-a[i+2])*rand()/32767/2+a[i+2]+2; //printf("s==%d\n",s); if((a[i+2]>318) ||(s>319)) printf("a[%d+2], a number which is %d and s==%d\n",i,a[i+2],s); } // for(i=0; i<total_instruction; i+=4) { for(j=0; j<4; j++) printf("%d ",a[i+j]); printf("\n"); } for(i=0; i<total_instruction; i++) { page[i]=a[i]/10; offset[i]=a[i]%10; } for(i=4; i<=32; i++) { printf("%2d page frames",i); FIFO(i); printf("\n"); } } //end main void initialize(int total_pf) { int i; diseffect=0; for(i=0; i<total_vp; i++) { p1[i].pn=i; p1[i].pfn=INVALID; p1[i].counter=0; p1[i].time=-1; } for(i=0; i<total_pf-1; i++) { pfc[i].next=&pfc[i+1]; pfc[i].pfn=i; } pfc[total_pf-1].next=NULL; pfc[total_pf-1].pfn=total_pf-1; freepf_head=&pfc[0]; } void FIFO(int total_pf) { int i,j; pfc_type *p; initialize(total_pf); busypf_head=busypf_tail=NULL; for(i=0; i<total_instruction; i++) { if(p1[page[i]].pfn==INVALID) { diseffect+=1; if(freepf_head==NULL) { p=busypf_head->next; p1[busypf_head->pn].pfn=INVALID;//释放第一个页面 freepf_head=busypf_head; freepf_head->next=NULL; busypf_head=p; } p=freepf_head->next; freepf_head->next=NULL; freepf_head->pn=page[i]; p1[page[i]].pfn=freepf_head->pfn; if(busypf_tail==NULL) busypf_head=busypf_tail=freepf_head; else { busypf_tail->next=freepf_head; busypf_tail=freepf_head; } freepf_head=p; } else //printf("mingzhong p1[page[%d]].pfn==%d\n",i,p1[page[i]].pfn); ; } printf(" FIFO:%6.4f",1-(float)diseffect/320); }
该程序主要实现了FIFO算法来模拟页面置换过程。
首先，定义了几个常量和结构体，包括页表项和页表项链表的结构。
初始化函数initialize用于初始化页表项和页表项链表，并设置了空闲页面帧和正在使用的页面帧的头节点。
FIFO函数实现了FIFO算法的页面置换过程。该算法的思想是，若所需页面不在内存中，则将内存中的最早进入的页面置换出去，并将所需页面加入内存中。具体实现过程如下：
- 初始化页面帧和页面帧链表。
- 遍历指令流数组，判断是否所需页面在内存中。
- 若所需页面不在内存中，则发生缺页中断，需要进行页面置换。
- 若空闲页面帧不为空，则将所需的页面加入内存中。更新页表项的页面帧号，并将该页面帧从空闲页面帧链表中移除，加入正在使用的页面帧链表中。
- 若空闲页面帧为空，则选择最早进入的页面帧进行置换。首先释放该页面帧对应的页表项，然后将最早进入的页面帧从正在使用的页面帧链表中移除，加入空闲页面帧链表中，最后将所需的页面加入内存中。更新页表项的页面帧号，并将该页面帧从空闲页面帧链表中移除，加入正在使用的页面帧链表中。
- 统计页面缺失次数。
- 输出FIFO算法的缺页率。
最后，在main函数中，生成了指令流数组，并通过FIFO函数模拟了不同页面帧数下的页面置换过程，并输出了相应的缺页率。
四. 实验结果
五. 实验总结
页面置换算法是操作系统中用来解决内存管理问题的一种重要技术。在计算机中，内存是有限的资源，而进程需要占用内存来运行。当内存不足时，操作系统需要进行页面置换，将部分进程从内存中调出，以便为新的进程腾出空间。
页面置换算法的目标是尽可能地提高内存利用率和进程的执行效率。常见的页面置换算法包括最佳置换算法（OPT）、先进先出置换算法（FIFO）、最近最久未使用置换算法（LRU）等。
最佳置换算法（OPT）是一种理想的页面置换算法，它假设可以预测未来的访问序列。它会将最久未被使用到的页面替换出去，以便给未来有可能被使用的页面腾出空间。然而，由于无法准确预测未来的访问序列，实际上很难实现最佳置换算法。
先进先出置换算法（FIFO）是一种简单而常用的页面置换算法。它按照进程进入内存的先后顺序进行页面置换。当内存不足时，最先进入内存的页面会被置换出去。然而，先进先出置换算法存在一种缺点，即它无法考虑页面的访问频率和重要性。
最近最久未使用置换算法（LRU）是一种基于页面访问历史的置换算法。它假设过去被访问得最近的页面最有可能在未来被再次访问。因此，最近最久未使用置换算法会选择最久未被访问的页面进行置换。相比于先进先出置换算法，LRU算法更加智能化，能够更好地适应不同的页面访问特征。
除了上述几种页面置换算法外，还有一些其他的算法，如时钟算法、工作集算法等。这些算法都有各自的特点和适用场景。
页面置换算法是操作系统中内存管理的关键技术之一。通过合理地选择和使用页面置换算法，可以提高内存利用率和进程执行效率，从而提升系统的整体性能。
