OS实验报告之内存管理

操作系统实验课--基于windows的

OS实验报告之内存管理

软工0801罗小兰 U200818069

实验目的

理解操作系统虚拟存储管理的原理，理解程序执行局部性的概念。

实验内容

设计一个虚拟存储区和内存工作区,并使用下列算法计算访问命中率。

（1） 进先出的算法（FIFO）

（2） 最近最少使用的算法（LRU）

（3） 最佳淘汰算法(OPT)

命中率=(1-页面失效次数)/页地址流长度

实验环境

VS2010, CONSOLE程序，（已生成 .exe 可执行文件）

实验要求

1、 理解FIFO,LRU算法原理，理解参考程序的原理和实现思路。

2、

3、 完成程序的设计，重点完成FIFO,LRU算法 分析运算结果，在分配不同的物理块情况下，各算法的缺

操作系统实验课--基于windows的

页情况有什么规律？

4、

完成OPT算法

程序设计思想

本实验的程序设计基本上按照实验内容进行。即首先用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。实验中我们产生320条指令，每个虚拟页存放10条指令。进程分配的物理块从4变化到32。

程序设计

本实验分为三部分：

1． main函数负责获得指令，并且对指令进行纸质转变操作，

再调用三种不同的算法。

2． Initialize函数负责初始化内存区域和虚拟地址数组

3． FIFO函数以先进先出的方式淘汰内存

LRU函数以最近最少使用的方式淘汰内存

OPT函数以最佳的方式淘汰内存

关键代码粘贴：

//先进先出淘汰算法

操作系统实验课--基于windows的

void FIFO(int total_pf)

{

int i,j;

pp_type *p,*t;

initialize(total_pf);

busy_pp_head=busy_pp_tail=NULL;

for(i=0;i<NUMBER_OF_INSTRUCTION;i++)

{

if(vp_array[page_of_instruction[i]].no_of_pp==INVALID) {

counter_page_default+=1;

if(free_pp_head==NULL)

{

p=busy_pp_head->next;

vp_array[busy_pp_head->no_of_vp].no_of_pp=INVALID; free_pp_head=busy_pp_head;

free_pp_head->next=NULL;

busy_pp_head=p;

}

p=free_pp_head->next;

free_pp_head->next=NULL;

free_pp_head->no_of_vp=page_of_instruction[i];

操作系统实验课--基于windows的

vp_array[page_of_instruction[i]].no_of_pp=free_pp_head->no_of_pp;

if(busy_pp_tail==NULL)

busy_pp_head=busy_pp_tail=free_pp_head;

else

{

busy_pp_tail->next=free_pp_head;

busy_pp_tail=free_pp_head;

}

free_pp_head=p;

}

}

printf("FIFO缺页率： %6.4f

",(float)counter_page_default/320);

return;

}

//最近最少淘汰使用算法

void LRU(int total_pf)

{

操作系统实验课--基于windows的

int min,minj,i,j,present_time;//访问时刻¨¬

initialize(total_pf);

present_time=0;

for(i=0;i<NUMBER_OF_INSTRUCTION;i++)

{

if(vp_array[page_of_instruction[i]].no_of_pp==INVALID) {

counter_page_default++;

if(free_pp_head==NULL) //无空闲页面?

{

min=MAXI;

for(j=0;j<NUMBER_OF_VP;j++)

if(min>vp_array[j].time&&vp_array[j].no_of_pp!=INVALID) {

min=vp_array[j].time;

minj=j;

}

free_pp_head=&pp_control[vp_array[minj].no_of_pp]; vp_array[minj].no_of_pp=INVALID;

vp_array[minj].time=-1;

free_pp_head->next=NULL;

操作系统实验课--基于windows的

}

vp_array[page_of_instruction[i]].no_of_pp=free_pp_head->no_of_pp;

vp_array[page_of_instruction[i]].time=present_time; free_pp_head=free_pp_head->next;

}

else

vp_array[page_of_instruction[i]].time=present_time;// 使用

present_time++;

}

printf("LRU缺¨¡À页°3率¨º：êo%6.4f

",(float)counter_page_default/320);

return ;

}

//最佳淘汰算法

void OPT(int total_pf)

{

操作系统实验课--基于windows的

int i, j, k;

int distance_of_page[NUMBER_OF_VP] = {0}; //记录每个在内存块中页面离下次使用的距离

int max_distance_page=0; //记录最大距离块号

initialize(total_pf);

for(i=0;i<NUMBER_OF_INSTRUCTION;i++)

{

if(vp_array[page_of_instruction[i]].no_of_pp==INVALID) {

counter_page_default++; //记录缺页次数

if(free_pp_head==NULL) //无空闲页面?

{ //释放最远将用到的页面

free_pp_head = &pp_control[max_distance_page]; //将空页指针指向淘汰的页面

vp_array[free_pp_head->no_of_vp].no_of_pp = INVALID;

//设置该页已经不在内存中

pp_control[max_distance_page].no_of_vp = -1; //清空该内存块的引用

操作系统实验课--基于windows的

free_pp_head->next = NULL; //单个空页，无next

}

distance_of_page[free_pp_head->no_of_pp] = 1; //该页将要调用的页面在前一个

vp_array[page_of_instruction[i]].no_of_pp = free_pp_head->no_of_pp;

//将该页放到空页中

pp_control[free_pp_head->no_of_pp].no_of_vp =

vp_array[page_of_instruction[i]].no_of_vp; //设置内存引用 free_pp_head = free_pp_head->next;

//指向下一个空页，如果为NULL，说明执行了之前的if段代码

}

for(j=0 ; j<total_pf && pp_control[j].no_of_vp != -1 ; j++)

//循环所有已占用的内存

{

distance_of_page[j]--; //引用一个页面后，所有

操作系统实验课--基于windows的

if(distance_of_page[j] == 0) //及当前为新页面或者有相同引用

{

for(k = i+1 ; k < NUMBER_OF_INSTRUCTION ; k++) {

distance_of_page[j]++; //距离+1 if(pp_control[j].no_of_pp ==

vp_array[page_of_instruction[k]].no_of_pp)

{

break; //当发现最近一个将来会引用的相同页面后记录位置

}

}

//max_distance_page为最远一个将要用到的page的序号

max_distance_page =

distance_of_page[max_distance_page] > distance_of_page[j]? max_distance_page : j;

}

}

操作系统实验课--基于windows的

printf("OPT缺¨¡À页°3率¨º：êo%6.4f

",(float)counter_page_default/320);

return ;

}

【输出结果】

操作系统实验课--基于windows的

【重要变量、结构和函数的建议】

(1)页面类型

typedef struct

{

int pn;

int pfn;

int counter;

int time

} pl-type;

其中pn 为页号,pfn为面号, counter为一个周期内访问该页面的次数, time为访问时间。

(2) 页面控制结构

pfc_struct

{

int pn,pfn;

struct pfc_struct *next;

}

typedef struct pfc_struct pfc_type;

pfc_type pfc_struct[total_vp], *freepf_head, *busypf_head; pfc_type *busypf_tail;

其中:

操作系统实验课--基于windows的

pfc[total_vp]定义用户进程虚页控制结构。

*freepf_head为空页面头的指针。

*busypf_head为忙页面头的指针。

*busypf_tail为忙页面尾的指针。

（3）函数定义

void initialize( ):初始化函数,给每个相关的页面赋值。 void FIFO( ):计算使用FIFO算法时的缺页率。

void LRU( ):计算使用LRU算法时的缺页率。

void OPT( ):计算使用OPT算法时的缺页率。

（4）变量定义

int a[total_instruction]: 指令流数据组。

int page[total_instruction]: 每条指令所属的页号。

int offset[total_instruction]: 每页装入10条指令后取模运算页号偏移值。

int total_pf: 用户进程的内存页面数。

int counter_page_default: 页面失效次数。

本文来源：https://www.bwwdw.com/article/swhi.html