操作系统实验-存储管理

实验三 存储管理

【实验目的和要求】

1、请求页式存储管理中页面置换算法模拟设计。 2、了解虚拟存储技术的特点。

3、掌握请求页式存储管理的页面置换算法。 【实验原理】

1、存储管理的主要功能之一是合理地分配空间。

2、请求页式管理是一种常用的虚拟存储管理技术。。

3、命中率=1-(页面失效次数/页地址流长度)。本实验页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。 【实验步骤】

一、问题描述与分析

1、通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： (1)50%的指令是顺序执行的；

(2)25%的指令是均匀分布在前地址部分； (3)25%的指令是均匀分布在后地址部分。 具体的实施方法是：

(1)在[0,319]的指令地址之间随机选取一起点m； (2)顺序执行一条指令，即执行地址为m+l的指今；

(3)在前地址[0,m+l]中随机选取一条指令并执行，该指令的地址为m’； (4)顺序执行一条指今，其地址为m’ +l；

(5)在后地址[m’ +2,319]中随机选取一条指令并执行； (6)重复上述步骤(1)一(5)，直到执行320次指令。 2、将指令序列变换成为页地址流 (1)页面大小为1K；

(2)用户内存容量为4页到32页； (3)用户虚存容量为32K。

在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：

第0条~第9条指令为第0页(对应虚存地址为[0,9])；

第10条~第19条指令为第1页(对应虚存地址为[10, l9])； … …

第310条~第319条指令为第31页(对应虚存地址为[310,3191])； 按以上方式，用户指令可组成32页。

3、考虑计算并输出下述各种算法在不同内存容量下的命中率。

(1)先进先出的算法(FIFO) ； (2)最近最少使用算法(LRU)；

其中(1)和(2)必做 三、程序设计与调试

在VC++6.0环境下进行程序设计和调试。 程序分析：

问题1：怎样使模拟的指令随机？

答：

通过使用C++的rand函数生成随机数，来产生指令，并用算法保证指定指令序列的需求。

问题2：指令序列如何变换成页地址流的？页地址主要包括哪两部分? 答：

for(i=0;i

由page[i]=a[i]/10;计算出页号。再执行offset[i]=a[i];计算出偏移量。

页地址包括页号和偏移量两部分

问题3：实验中的页帧可以设置从多少到多少？页帧>32是什么意思？ 答：

页帧可以设置4到32页

用户虚拟内存为32k，虚拟页面无法映射到这些地址，没有意义。

问题4：FIFO的已经分配的页面是如何管理的？

答：

由操作系统维护一个队列(链表)，新页面由队尾进入，时间最久的页面从队头出去。当发生缺页中断时，淘汰表头的页面并把新调度的页面加到表尾。

问题5：LRU算法是如何确定哪一页被置换的？主要思想是什么？ 答：

LRU算法的置换在发生中断的时侯未使用时间最长的页面。

LRU的主要思想：已经很久没使用的页面很有可能在未来较长的一段时间内 仍然不会被使用。在缺页中断发生时，置换未使用时间最长的页面。

四、数据分析

分析数据输出结果（文字阐述分析即可）。

问题1：为什么命中率最高为90%？ 答：

因为一共32个页帧，一共出现320次，一共占总页帧的10%。每一个页帧在第一次进入内存时都会产生缺页，所以最高只有90%的命中率。

问题2：FIFO和LRU比较，命中率怎样？主要原因是什么？ 答：

FIFO比LRU命中率低，因为在FIFO算法中经常被访问的很有可能是先进入的那些页面，由于它先进入内存，在算法的规定下导致内存中经常会进行缺页置换。这种操作会导致命中率变低。

问题3：void initialize(int total_pf)都做了什么？

答：页面的初始化函数，给相关的页面赋值。

【实验主要仪器及材料】

Windows/X86计算机 VC++6.0

程序源代码：(Dev-C++编译通过)

#define INVALID -1

#define total_instruction 320 //指令流长

#define total_vp 32 //虚拟页表长度 //#define clear_period 50 //清零周期

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 a[total_instruction];

int page[total_instruction],offset[total_instruction];

void initialize(int); void FIFO(int); void LRU(int); //void OPT(int);

#include #include #include int main() {

int S,i;

srand(_getpid()*10);//每次运行时进程号不同，可以作为初始化随机数队列的种子

S=319*rand()/32767 ; //得到一个0到319之间的一个数

for (i=0;i

//S=rand()*(318-a[i+2])/32767+a[i+2]+1;

S=319*rand()/32767 ; }

for(i=0;i

for(i=4;i<=32;i++) { printf(\ FIFO(i); LRU(i); //OPT(i); //LFU(i); //NUR(i); printf(\ } return 1; }

void FIFO(int total_pf) //total_pf是用户进程页面数目 {

int i;

pfc_type *p;

initialize(total_pf);

busypf_head=busypf_tail=NULL; for(i=0;inext; 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(\ \}

void LRU(int total_pf) //total_pf是用户进程页面数目,即进程物理内存pageframe数目 {

int min,minj,i,j,present_time;

initialize(total_pf); present_time=0;

for(i=0;ipl[j].time && (pl[j].pfn !=INVALID)) {min=pl[j].time ;minj=j;} freepf_head=&pfc[pl[minj].pfn]; pl[minj].pfn=INVALID; pl[minj].time=-1; freepf_head->next =NULL; }

//有空闲页面时分配一页 pl[page[i]].pfn=freepf_head->pfn; pl[page[i]].time=present_time; freepf_head=freepf_head->next; }

else

pl[page[i]].time=present_time; present_time++; }

printf(\}

void initialize(int total_pf) {

int i;

diseffect=0;

for(i=0;i

for(i=1;i

pfc[total_pf-1].next =NULL;pfc[total_pf-1].pfn =total_pf-1; freepf_head=&pfc[0]; }

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