Question

（4）虚拟内存程序设计，包括FIFO和LRU算法。 设计一个能模拟内存管理行为的系统程序，该系统至少应包括FI

（4）虚拟内存程序设计，包括FIFO和LRU算法。
设计一个能模拟内存管理行为的系统程序，该系统至少应包括FIFO和LRU算法（Least Recently Used）（当需要置换一页时，选择最长时间未被使用的那一页淘汰掉。）的实现。
参考程序 page.c
#include <stdio.h>
#include <stdlib.h>
#define INVALID -1
#define page_len 16 //页序列总长
#define total_vp 18 //作业的总页数+1，即序列中出现的最大页号+1，为了开pl[total_vp]数组所用
typedef struct{
int pn,pfn,counter,time;
}pl_type;
pl_type pl[total_vp];
struct pfc_struct{
int pn,pfn;
struct pfc_struct *next;
};
typedef struct pfc_struct pfc_type;
pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;

int diseffect;
int page[]={0,1,7,2,3,2,17,1,0,3,0,3,0,3,0,10};

void initialize(int total)
{ int i;
diseffect=0;
for(i=0; i<total_vp;i++)
{ pl[i].pn=i;
pl[i].pfn=INVALID;
pl[i].counter=0;
pl[i].time=-1; //printf("pl[i]=%d",pl[i].pn);printf("\n");
}
for(i=1;i<total;i++)
{ pfc[i-1].next=&pfc[i];
pfc[i-1].pfn=i-1;}
pfc[total-1].next=NULL;
pfc[total-1].pfn=total-1;
freepf_head=&pfc[0];
}

void FIFO(int total)
{ int i,j;
pfc_type *p,*t;
initialize(total);
busypf_head=busypf_tail=NULL;
for(i=0;i<page_len;i++)
{
if(pl[page[i]].pfn==INVALID)
{ diseffect+=1;
if(freepf_head==NULL)
{p=busypf_head->next;
pl[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];
pl[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;
}}
printf("FIFO:%d",diseffect);
}

main()
{ int i;
for(i=4;i<=7;i++)
{
printf("\n%2d page frames ",i);
FIFO(i);
}
}

（5）设计一个字符菜单的接口界面，其功能是能根据用户的选择，运行相应的程序模块，实现诸如改名文件、删除文件、显示文件等功能。(提示：要先将各模块分别命名成各函数，以便于主程序（MAIN.C）调用。可参考程序中的命名方法，各函数名可以自定。)
参考程序MAIN.C：
#include “stdio.h”
#include “dir.h”
#include “stdlib.h”
#include “io.h”
#include “alloc.h”
#include “conio.h”
main( )
{ int selection;
char filename[16];
printf(“input filename\n”);
scanf(“%s”,filename);
do {
printf(“input selection\n”);
printf(“1-create file\n”);
printf(“2-copy file\n”);
printf(“3-type file\n”);
printf(“4-rename file\n”);
printf(“5-delete file\n”);
printf(“0-quit\n”);
scanf(“%d, &selection);
getchar( );
switch (selection) {
case 1: create_f (filename); break;
case 2: copy_f (filename1, filename2); break;
case 3: type_f (filename); break;
case 4: rename_f (filename1,filename2); break;
case 5: delete_f (filename); break;
}
} while (selection !=0);
}

Answer 1

#include"stdio.h"
#include"stdlib.h"
#include"time.h"

void FIFO(void);
void LRU(void);

char a;
int m=4,n=12,i,y[12]=; /*m为物理块数，n为要访问的页面数*/
typedef struct page{
int num;
int time;
}Page;
Page x[10];

int GetMax(page *x) /*求出那个物理块中的页面呆的时间最长，返回物理块号*/
{
int i;
int max=-1;
int tag=0;
for(i=0;i<m;i++)
{
if(x[i].time>max)
{ max=x[i].time;
tag=i;
}
}
return tag;
}

void Xunhuan()
{
printf("Please select 1:FIFO算法\n 2:LRU算法\n");
scanf("%s",&a);
printf("物理块数：4\n");
//scanf("%d",&m);
for(i=0;i<m;i++) /*将空的物理块中数据置为-1*/
{
x[i].num=-1;
}
printf("所要访问的页面数：12\n");
//scanf("%d",&n);
//srand(time(NULL));

printf("所要访问的页面号序列为：");
for(i=0;i<n;i++)
printf("%d ",y[i]);
printf("\n");
printf("页面置换步骤如下：\n");
switch(a)
{
case '1':FIFO();break;
case '2':LRU(); break;
}
}

void main()
{
char a;
Xunhuan();
while(1)
{
printf("Continue or Exit:C/Anykey:\n");
scanf("%s",&a);
if(a=='c'||a=='C')
Xunhuan();
else break;
}
exit(0);
}

void FIFO(void)
{
int i,j,u;
for(i=0;i<m;i++)
x[i].time=0;
x[0].num=y[0];
x[0].time=1;
printf(" %d \n",x[0].num);
for(i=1;i<n;i++)
{ u=0;
for(j=0;j<m;j++)
if(x[j].num==y[i])
{
u=1;
break;
}
if(u!=1&&x[m-1].num!=-1)
{
j=GetMax(x);
x[j].num=y[i];
x[j].time=0;
}
if(u!=1&&x[m-1].num==-1)
{
for(j=0;j<m;j++)
{
if(x[j].num==-1)
{x[j].num=y[i];
break;}
}
}
for(j=0;j<m;j++)
if(x[j].num!=-1)
x[j].time++;

for(j=0;j<m;j++)
if(x[j].num==-1)
printf("%2c ",32);
else
printf("%2d ",x[j].num);
printf("\n");
}
}

void LRU()
{
int i,j,u;
for(i=0;i<m;i++)
x[i].time=0;
x[0].num=y[0];
x[0].time=1;
printf(" %d \n",x[0].num);
for(i=1;i<n;i++)
{ u=0;
for(j=0;j<m;j++)
if(x[j].num==y[i]) /*物理块中存在相同页面*/
{
x[j].time=0; /*将相同的物理块的time置为0*/
u=1;
break;
}
if(u!=1&&x[m-1].num!=-1) /*物理块中无相同页面且物理块已填满*/
{
j=GetMax(x);
x[j].num=y[i];
x[j].time=0; /*将刚替换的页面所在的物理块time置为0*/
}
if(u!=1&&x[m-1].num==-1) /*物理块中无相同页面且物理块未填满*/
{
for(j=0;j<m;j++)
{
if(x[j].num==-1)
{x[j].num=y[i];
break;}
}
}
for(j=0;j<m;j++)
if(x[j].num!=-1)
x[j].time++; /*每执行完一次time加1*/

for(j=0;j<m;j++)
if(x[j].num==-1)
printf("%2c ",32);
else
printf("%2d ",x[j].num);
printf("\n"); /*格式化输出*/
}
}

Answer 2

#include"stdio.h"
#include"stdlib.h"
#include"time.h"

void FIFO(void);
void LRU(void);

char a;
int m=4,n=12,i,y[12]=; /*m为物理块数，n为要访问的页面数*/
typedef struct page{
int num;
int time;
}Page;
Page x[10];

int GetMax(page *x) /*求出那个物理块中的页面呆的时间最长，返回物理块号*/
{
int i;
int max=-1;
int tag=0;
for(i=0;i<m;i++)
{
if(x[i].time>max)
{ max=x[i].time;
tag=i;
}
}
return tag;
}

void Xunhuan()
{
printf("Please select 1:FIFO算法\n 2:LRU算法\n");
scanf("%s",&a);
printf("物理块数：4\n");
//scanf("%d",&m);
for(i=0;i<m;i++) /*将空的物理块中数据置为-1*/
{
x[i].num=-1;
}
printf("所要访问的页面数：12\n");
//scanf("%d",&n);
//srand(time(NULL));

printf("所要访问的页面号序列为：");
for(i=0;i<n;i++)
printf("%d ",y[i]);
printf("\n");
printf("页面置换步骤如下：\n");
switch(a)
{
case '1':FIFO();break;
case '2':LRU(); break;
}
}

void main()
{
char a;
Xunhuan();
while(1)
{
printf("Continue or Exit:C/Anykey:\n");
scanf("%s",&a);
if(a=='c'||a=='C')
Xunhuan();
else break;
}
exit(0);
}

void FIFO(void)
{
int i,j,u;
for(i=0;i<m;i++)
x[i].time=0;
x[0].num=y[0];
x[0].time=1;
printf(" %d \n",x[0].num);
for(i=1;i<n;i++)
{ u=0;
for(j=0;j<m;j++)
if(x[j].num==y[i])
{
u=1;
break;
}
if(u!=1&&x[m-1].num!=-1)
{
j=GetMax(x);
x[j].num=y[i];
x[j].time=0;
}
if(u!=1&&x[m-1].num==-1)
{
for(j=0;j<m;j++)
{
if(x[j].num==-1)
{x[j].num=y[i];
break;}
}
}
for(j=0;j<m;j++)
if(x[j].num!=-1)
x[j].time++;

for(j=0;j<m;j++)
if(x[j].num==-1)
printf("%2c ",32);
else
printf("%2d ",x[j].num);
printf("\n");
}
}

void LRU()
{
int i,j,u;
for(i=0;i<m;i++)
x[i].time=0;
x[0].num=y[0];
x[0].time=1;
printf(" %d \n",x[0].num);
for(i=1;i<n;i++)
{ u=0;
for(j=0;j<m;j++)
if(x[j].num==y[i]) /*物理块中存在相同页面*/
{
x[j].time=0; /*将相同的物理块的time置为0*/
u=1;
break;
}
if(u!=1&&x[m-1].num!=-1) /*物理块中无相同页面且物理块已填满*/
{
j=GetMax(x);
x[j].num=y[i];
x[j].time=0; /*将刚替换的页面所在的物理块time置为0*/
}
if(u!=1&&x[m-1].num==-1) /*物理块中无相同页面且物理块未填满*/
{
for(j=0;j<m;j++)
{
if(x[j].num==-1)
{x[j].num=y[i];
break;}
}
}
for(j=0;j<m;j++)
if(x[j].num!=-1)
x[j].time++; /*每执行完一次time加1*/

for(j=0;j<m;j++)
if(x[j].num==-1)
printf("%2c ",32);
else
printf("%2d ",x[j].num);
printf("\n"); }
}