Question

页面置换算法的实验

一．实验目的
通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。
二．实验内容
设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。
1．最佳淘汰算法（OPT）
2．先进先出的算法（FIFO）
3．最近最久未使用算法（LRU）
三、实验指导
1．假设分给一作业的内存块数为 4 ，每条指令占一个存储单元，每个页面中可存放 10 条指令；
2．设计一个程序，模拟一作业的执行过程。设该作业共有 160 条指令，即它的地址空间为16页，最初作业的所有页面都还未调入内存。在模拟过程中，如果所访问的指令已经在内存，则显示其物理地址，并转下一条指令。如果所访问的指令尚未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果 4 个内存块中均已装入该作业的虚页面，则需进行页面置换；在所有 160条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。
3 ．作业中指令的访问次序要求按下述原则生成：
具体的实施办法是：
(1)在[0，159]之间随机选取一条起始执行指令，其序号为 m ；
(2)顺序执行两条指令，即序号为 m+1、m+2 的指令；
(3)通过随机数，跳转到前地址部分[0，m-1]中的某条指令处，其序号为 m1 ；
(4)顺序执行两条指令，即序号为 m1+1 ，m1+2的指令；
(5)通过随机数，跳转到后地址部分 [m1+3，159] 中的某条指令处，其序号为 m2 ；
(6)顺序执行两条指令，即序号为 m2+1，m2+2 的指令；若m2+2>159只执行一条指令；
(7)重复“跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行”的过程，直至执行完全部160条指令。

大家帮帮忙了，实在是看不懂~~~~
希望大家把代码给我写出来啊~~~谢谢谢谢~~~

Answer 1

#include<stdlib.h>
#include<iostream.h>
#include<time.h>
#include<stdio.h>

#define total_instruction 200 /*指令流长*/
#define M 16 /*实际页数*/

#define N 4 //可用页面数
struct Pro
{
int num,time;
};
int a[total_instruction];

int page[N];

void Input(Pro p[total_instruction])
{
int m,i,m1,m2;
srand( (unsigned int )time(NULL));
m=rand( )%160; //
for(i=0;i<total_instruction;) /*产生指令队列*/
{
if(m<0||m>159)
{
printf("When i==%d,Error,m==%d\n",i,m);
exit(0);
}
a[i]=m; /*任选一指令访问点m*/
a[i+1]=a[i]+1;
a[i+2]=a[i]+2; /*顺序执行两条指令*/
int m1=rand( )%m; /*执行前地址指令m1 */
a[i+3]=m1;
a[i+4]=m1+1;
a[i+5]=m1 + 2;/*顺序执行两条指令*/

// s=(158-a[i+5])*rand( )/32767/32767/2+a[i+5]+2;
m2 = rand()%(157-m1)+m1+3;
a[i+6]=m2;
if( (m2+2) > 159 )
{
a[i+7] = m2+1;
i +=8;
}
else
{
a[i+7] = m2+1;
a[i+8] = m2+2;
i = i+9;
}
m = rand()%m2;

}
for (i=0;i<total_instruction;i++) /*将指令序列变换成页地址流*/
{
p[i].num=a[i]/10;
p[i].time = 0;
}
}
void print(Pro *page1)//打印当前的页面
{
Pro *page=new Pro[N];
page=page1;
for(int i=0;i<N;i++)
cout<<page[i].num<<" ";
cout<<endl;
}

int Search(int e,Pro *page1 )
{
Pro *page=new Pro[N];
page=page1;
for(int i=0;i<N;i++)if(e==page[i].num)return i;
return -1;
}

int Max(Pro *page1)
{
Pro *page=new Pro[N];
page=page1;
int e=page[0].time,i=0;
while(i<N)//找出离现在时间最长的页面
{
if(e<page[i].time)e=page[i].time;
i++;
}
for( i=0;i<N;i++)if(e==page[i].time)return i;

return -1;
}

int Compfu(Pro *page1,int i,int t,Pro p[M])
{
Pro *page=new Pro[N];
page=page1;

int count=0;
for(int j=i;j<M;j++)
{
if(page[t].num==p[j].num )break;
else count++;
}
return count;

}

int main()
{
Pro p[total_instruction];
Pro *page=new Pro[N];
char c;
int t=0;
float n=0;
Input(p);

do{
for(int i=0;i<N;i++)//初试化页面基本情况
{
page[i].num=0;
page[i].time=2-i;
}

i=0;
cout<<"f:FIFO页面置换"<<endl;
cout<<"l:LRU页面置换"<<endl;
cout<<"o:OPT页面置换"<<endl;
cout<<"按其它键结束"<<endl;
cin>>c;

if(c=='f')//FIFO页面置换
{
n=0;
cout<<"页面置换情况: "<<endl;
while( i< total_instruction)
{
if(Search(p[i].num,page)>=0)
i++;//找到相同的页面
else
{
if(t==N)t=0;
else
{
n++;//
page[t].num=p[i].num;
print(page);
t++;
}
}
}
cout<<"缺页次数："<<n<<" 缺页率："<<n/total_instruction<<endl;

}
if(c=='l')//LRU页面置换
{
n=0;
cout<<"页面置换情况: "<<endl;
while(i<total_instruction)
{
int k;
k=t=Search(p[i].num,page);
if(t>=0)

page[t].time=0;

else
{
n++;
t=Max(page);

page[t].num=p[i].num;
page[t].time=0;
}
if(t==0){page[t+1].time++;page[t+2].time++;}
if(t==1){page[2].time++;page[0].time++;}
if(t==2){page[1].time++;page[0].time++;}
if(k==-1) print(page);
i++;
}
cout<<"缺页次数："<<n<<" 缺页率："<<n/total_instruction<<endl;
}
if(c=='o')//OPT页面置换
{
n=0;
while(i<total_instruction)
{
if(Search(p[i].num,page)>=0)i++;
else
{
int temp=0,cn;
for(t=0;t<N;t++)
{
if(temp<Compfu(page,i,t,p))
{
temp=Compfu(page,i,t,p);
cn=t;
}
}
page[cn]=p[i];
n++;
print(page);
i++;
}
}
cout<<"缺页次数："<<n<<" 缺页率："<<n/total_instruction<<endl;
}

}while(c=='f'||c=='l'||c=='o');

return 0;
}

Answer 2

#include <stdio.h>
#define PROCESS_NAME_LEN 32 /*进程名称的最大长度*/
#define MIN_SLICE 10 /*最小碎片的大小*/
#define DEFAULT_MEM_SIZE 1024 /*默认内存的大小*/
#define DEFAULT_MEM_START 0 /*默认内存的起始位置*/

/* 内存分配算法 */
#define MA_FF 1
#define MA_BF 2
#define MA_WF 3

int mem_size=DEFAULT_MEM_SIZE; /*内存大小*/
int ma_algorithm = MA_FF; /*当前分配算法*/
static int pid = 0; /*初始pid*/
int flag = 0; /*设置内存大小标志*/

struct free_block_type
{
int size;
int start_addr;
struct free_block_type *next;
};
struct free_block_type *free_block;

struct allocated_block
{
int pid;
int size;
int start_addr;
char process_name[PROCESS_NAME_LEN];
struct allocated_block *next;
};
struct allocated_block *allocated_block_head;

/*初始化空闲块，默认为一块，可以指定大小及起始地址*/
struct free_block_type* init_free_block(int mem_size)
{

struct free_block_type *fb;

fb=(struct free_block_type *)malloc(sizeof(struct free_block_type));
if(fb==NULL)
{
printf("No mem\n");
return NULL;
}
fb->size = mem_size;
fb->start_addr = DEFAULT_MEM_START;
fb->next = NULL;
return fb;
}

void display_menu()
{
printf("\n");
printf("1 - Set memory size (default=%d)\n", DEFAULT_MEM_SIZE);
printf("2 - Select memory allocation algorithm\n");
printf("3 - New process \n");
printf("4 - Terminate a process \n");
printf("5 - Display memory usage \n");
printf("0 - Exit\n");
}

/*设置内存的大小*/
int set_mem_size()
{
int size;
if(flag!=0)
{ /*防止重复设置*/
printf("Cannot set memory size again\n");
return 0;
}
printf("Total memory size =");
scanf("%d", &size);
if(size>0)
{
mem_size = size;
free_block->size = mem_size;
}
flag=1;
return 1;
}
/*Best-fit使用最小的能够放下将要存放数据的块，First-first使用第一个能够放下将要存放数据的块，Worst-fit使用最大的能够放下将要存放数据的块。*/
/* 设置当前的分配算法 */
/*分区分配算法(Partitioning Placement Algorithm)
*/
void set_algorithm()
{
int algorithm;
printf("\t1 - First Fit\n");/*首次适应算法(FF)：。 */
printf("\t2 - Best Fit\n");/*最佳适应算法(BF)： */

printf("\t3 - Worst Fit\n");
scanf("%d", &algorithm);
if(algorithm>=1 && algorithm <=3) ma_algorithm=algorithm;
/*按指定算法重新排列空闲区链表*/
rearrange(ma_algorithm);
}

void swap(int* data_1,int* data_2)
{
int temp;
temp=*data_1;
*data_1=*data_2;
*data_2=temp;
}

void rearrange_FF()
{
struct free_block_type *tmp, *work;
printf("Rearrange free blocks for FF \n");
tmp = free_block;
while(tmp!=NULL)
{
work = tmp->next;
while(work!=NULL)
{
if( work->start_addr < tmp->start_addr)
{ /*地址递增*/
swap(&work->start_addr, &tmp->start_addr);
swap(&work->size, &tmp->size);
}
else
{
work=work->next;
}
}
tmp=tmp->next;
}
}
/*按BF算法重新整理内存空闲块链表(未完成)
void rearrange_BF()
{
struct free_block_type *tmp,*work;
printf("Rearrange free blocks for BF\n");
tmp=free_block;
while(tmp!=NULL)
{
work=tmp->next;
while(work!=NULL)
{

}
}

}

*/
/*按WF算法重新整理内存空闲块链表(未完成)
void rearrange_WF()
{
struct free_block_type *tmp,*work;
printf("Rearrange free blocks for WF \n");
tmp=free_block;
while(tmp!=NULL)
{
work=tmp->next;
while(work!=NULL)
{

}
}
}
*/

/*按指定的算法整理内存空闲块链表*/
int rearrange(int algorithm)
{
switch(algorithm)
{
case MA_FF: rearrange_FF(); break;
/*case MA_BF: rearrange_BF(); break; */
/*case MA_WF: rearrange_WF(); break; */
}
}

/*创建新的进程，主要是获取内存的申请数量*/
int new_process()
{
struct allocated_block *ab;
int size;
int ret;
ab=(struct allocated_block *)malloc(sizeof(struct allocated_block));
if(!ab)
exit(-5);
ab->next = NULL;
pid++;
sprintf(ab->process_name, "PROCESS-%02d", pid);
ab->pid = pid;

printf("Memory for %s:", ab->process_name);
scanf("%d", &size);
if(size>0) ab->size=size;
ret = allocate_mem(ab); /* 从空闲区分配内存，ret==1表示分配ok*/
/*如果此时allocated_block_head尚未赋值，则赋值*/
if((ret==1) &&(allocated_block_head == NULL))
{
allocated_block_head=ab;
return 1;
}
/*分配成功，将该已分配块的描述插入已分配链表*/
else if (ret==1)
{
ab->next=allocated_block_head;
allocated_block_head=ab;
return 2;
}
else if(ret==-1)
{ /*分配不成功*/
printf("Allocation fail\n");
free(ab);
return -1;
}
return 3;
}

/*分配内存模块*/
int allocate_mem(struct allocated_block *ab)
{
struct free_block_type *fbt,*pre,*r;
int request_size=ab->size;
fbt=pre=free_block;
while(fbt!=NULL)
{
if(fbt->size>=request_size)
{
if(fbt->size-request_size>=MIN_SLICE)
{
fbt->size=fbt->size-request_size;
}
/*分配后空闲空间足够大，则分割*/

else
{
r=fbt;
pre->next=fbt->next;
free(r);
/*分割后空闲区成为小碎片，一起分配*/

return 1;
}
}
pre = fbt;
fbt = fbt->next;
}

return -1;
}

/*将ab所表示的已分配区归还，并进行可能的合并*/
int free_mem(struct allocated_block *ab)
{
int algorithm = ma_algorithm;
struct free_block_type *fbt, *pre, *work;

fbt=(struct free_block_type*) malloc(sizeof(struct free_block_type));
if(!fbt)
return -1;
fbt->size = ab->size;
fbt->start_addr = ab->start_addr;
/*插入到空闲区链表的头部并将空闲区按地址递增的次序排列*/
fbt->next = free_block;
free_block=fbt;
rearrange(MA_FF);
fbt=free_block;
while(fbt!=NULL)
{
work = fbt->next;
if(work!=NULL)
{
/*如果当前空闲区与后面的空闲区相连，则合并*/
if(fbt->start_addr+fbt->size == work->start_addr)
{
fbt->size += work->size;
fbt->next = work->next;
free(work);
continue;
}
}
fbt = fbt->next;
}
rearrange(algorithm); /*重新按当前的算法排列空闲区*/
return 1;
}

/*?释放ab数据结构节点*/
int dispose(struct allocated_block *free_ab)
{
struct allocated_block *pre, *ab;

if(free_ab == allocated_block_head)
{ /*如果要释放第一个节点*/
allocated_block_head = allocated_block_head->next;
free(free_ab);
return 1;
}
pre = allocated_block_head;
ab = allocated_block_head->next;

while(ab!=free_ab)
{
pre = ab;
ab = ab->next;
}
pre->next = ab->next;
free(ab);
return 2;
}
/*查找要删除的进程*/
struct allocated_block* find_process(int pid)
{
struct allocated_block *temp;
temp=allocated_block_head;
while(temp!=NULL)
{
if(temp->pid==pid)
{
return temp;
}
temp=temp->next;
}
}

/*删除进程，归还分配的存储空间，并删除描述该进程内存分配的节点*/
void kill_process()
{
struct allocated_block *ab;
int pid;
printf("Kill Process, pid=");
scanf("%d", &pid);
ab=find_process(pid);
if(ab!=NULL)
{
free_mem(ab); /*释放ab所表示的分配区*/
dispose(ab); /*释放ab数据结构节点*/

}
}

/* 显示当前内存的使用情况，包括空闲区的情况和已经分配的情况 */

int display_mem_usage()
{
struct free_block_type *fbt=free_block;
struct allocated_block *ab=allocated_block_head;
if(fbt==NULL) return(-1);
printf("----------------------------------------------------------\n");

/* 显示空闲区 */
printf("Free Memory:\n");
printf("%20s %20s\n", " start_addr", " size");
while(fbt!=NULL)
{
printf("%20d %20d\n", fbt->start_addr, fbt->size);
fbt=fbt->next;
}
/* 显示已分配区 */
printf("\nUsed Memory:\n");
printf("%10s %20s %10s %10s\n", "PID", "ProcessName", "start_addr", " size");
while(ab!=NULL)
{
printf("%10d %20s %10d %10d\n", ab->pid, ab->process_name, ab->start_addr, ab->size);
ab=ab->next;
}
printf("----------------------------------------------------------\n");
return 0;
}

**********************************************************************
楼主啊，小女子给你的是残缺版滴，要是你给我分，我就把剩下滴给你,上次在北京大学贴吧都被人骗了，世道炎凉啊O(∩_∩)O~

Answer 3

太专业了，去一些职业论坛提问吧。
这，估计就算你找到答案也是复制的一大堆。