OS学习周报告-3
页面置换算法模拟-FIFO
页面置换算法是虚拟内存技术中重要的技术之一，该算法是在搜索页表发生缺页时决定哪块页面该被调出。FIFO先进先出算法是最简单的一种页面置换算法。之所以模拟这个算法是因为FIFO有一个很奇特的belady现象。
-
代码如下
#include <stdio.h> typedef struct reco //定义结构体，用来存储页面号，和缺页标记 { int no; int misspage; }reco; int main() { int n,count,no; printf("请输入进程分区大小: \n"); scanf("%d",&n); int que[n]; //定义循环队列 int size=0 //用size记录队列中存放元素个数，用来判断循环队列，队满队空。 int front=0,rear=0; for(int i=0;i<n;i++) que[i]=0; printf("请输入页号序列长度：\n"); scanf("%d",&count); reco page[count]; //reco型的数组，记录每次输入页号时，当前物理块否缺页 int block[n][count]; //用二维数组记录各物理块中存放过的页号 for(int i=0;i<n;i++) //初始化,i表示物理块编号，j表示页面输入时的顺序 { for(int j=0;j<count;j++) { block[i][j]=-1; } } printf("请依次输入页号序列:\n"); for(int i=0;i<count;i++) { scanf("%d",&no); page[i].no=no; for(int j=0;j<n;j++) //在物理块队列中查找当前输入页号，若没找到则标记缺页，反之，未缺页 { if(que[j]==no) { page[i].misspage=0; break; } else page[i].misspage=1; } if(page[i].misspage==1) //缺页，进行页面置换。若物理块队列不满，则将该页号插入队尾 { //未缺页，则只需记录未缺页标记即可 if(size<n) { que[rear]=no; rear=(rear+1)%n; size++; } else //队列满，则将队头页号覆盖 { que[rear]=no; rear=(rear+1)%n; } for(int k=0;k<n;k++) block[k][i]=que[k]; //记录下缺页时页面置换后，各物理块中存储的页号 } } printf("访问页面"); for(int i=0;i<count;i++) printf("%2d",page[i].no); printf("\n"); for(int j=0;j<n;j++) { printf("物理块%d ",j); for(int k=0;k<count;k++) { if(block[j][k]==-1) printf(" "); else printf("%2d",block[j][k]); } printf("\n"); } printf("缺页否 "); float temp=0; for(int i=0;i<count;i++) { if(page[i].misspage==1) printf(" *"),temp++; else printf(" "); } printf("\n缺页率:%.2f%\n",temp/count*100); return 1; } -
bleady现象：
物理块为3块时：
hawl29@hawl29-PC:~/Desktop/cprogram/OS_experiment$ ./fifo_execfile 请输入进程分区大小: 3 请输入页号序列长度： 12 请依次输入页号序列: 1 2 3 4 1 2 5 1 2 3 4 5 访问页面 1 2 3 4 1 2 5 1 2 3 4 5 物理块0 1 1 1 4 4 4 5 5 5 物理块1 0 2 2 2 1 1 1 3 3 物理块2 0 0 3 3 3 2 2 2 4 缺页否 * * * * * * * * * 缺页率:75.00%物理块为4块时：
hawl29@hawl29-PC:~/Desktop/cprogram/OS_experiment$ ./fifo_execfile 请输入进程分区大小: 4 请输入页号序列长度： 12 请依次输入页号序列: 1 2 3 4 1 2 5 1 2 3 4 5 访问页面 1 2 3 4 1 2 5 1 2 3 4 5 物理块0 1 1 1 1 5 5 5 5 4 4 物理块1 0 2 2 2 2 1 1 1 1 5 物理块2 0 0 3 3 3 3 2 2 2 2 物理块3 0 0 0 4 4 4 4 3 3 3 缺页否 * * * * * * * * * * 缺页率:83.33%物理块增多了，缺页率反而提高了，听起来相当反直觉，但它确实发生了，这是只有在FIFO算法中才会出现的一种现象，由Belady发现。原因据说与队列的性质有关，具体我还在查找资料。
