实验五 存储管理

实验五 存储管理

1.实验目的：

存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。

本实验的目的是通过请求页式存储管理中页面置换算法的模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法

2.实验内容：

设计程序实现下述三个算法，并计算下述算法的命中率。

A. OPTIMAL：最佳置换算法 B. FIFO：先进先出置换算法 C. LRU：最近最久未使用置换算法 [预备内容]

地址映射过程中，若发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。以下分别是三个算法的设计思想。

OPTIMAL：最佳置换算法。其所选择的被淘汰页面，将是以后永不使用的，或是在未来最长时间内不再被访问的页面。

FIFO：先进先出置换算法。该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。

LRU：最近最久未使用置换算法。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的的时间T，当须淘汰一个页面时，选择现有页面中其T值最大的给予淘汰。在该实现中是选择Timer值最大的淘汰。 2）举例即将被访问的页面如下 page

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

内存情况 Block -1 FIFO

-1 -1 7 -1 -1 7 0 -1 7 0 1 2

OPT

0 1 2 3 1 …… 2 3 0 ……

2 0 1

2 0 3 2

4 3 ……

LRU

2 0 1 2 0 3 4

0 3 ……

具体实现：

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

Block

FIFO

-1 -1 -1 7 -1 -1 7 0 -1 7 0 1 OPT

Block -1 -1 -1 7 -1 -1 7 0 -1 7 0 1 Block

LRU

-1

-1 -1 7 -1 -1 7 0 -1 7 0 1 参考程序如下： #include #define Bsize 3 #define Psize 20 typedef struct page {

int content;//页面号 int timer;//被访问标记 }page;

page block[Bsize];//物理块

page page[Psize];//页面号串

void Init(void) {//初始化

int QString[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};

for(int i=0; iblock[i].content = -1; block[i].timer = 0; }

for(i=0; ipage[i].content = QString[i]; page[i].timer = 0; } }

int findSpace(void) {//查找是否有空闲内存 for(int i=0; ireturn i;//找到空闲内存，返回BLOCK中位置 return -1; }

int findExist(int curpage) {//查找内存中是否有该页面 for(int i=0; iif(block[i].content == page[curpage].content)

return i;//找到内存中有该页面，返回BLOCK中位置 return -1; }

int findReplace(void)

{//查找应予置换的页面，被置换的页面的Timer值最大 int pos = 0;

for(int i=0; iif(block[i].timer >= block[pos].timer)

pos = i;//找到应予置换页面，返回BLOCK中位置 return pos; }

void display(void) {//显示

for(int i=0; iif(block[i].content != -1) cout<void Optimal(void) {//OPTIMAL算法 int exist,space,position ; for(int i=0; iexist = findExist(i); if(exist != -1)

{ cout<<\"不缺页\"<space = findSpace(); if(space != -1)

{block[space]=page[i];//block[space].content=page[i].content,block[space].timer=page[i].timer display(); } else

{//没有找到空闲分区，需找一个页面进行置换 for(int k=0; kif(block[k].content != page[j].content)

{ block[k].timer = 1000; }//将来不会用，设置大数 else {

block[k].timer = j; break; } }

position = findReplace(); block[position] = page[i]; display(); } } } }

void LRU(void) {//

TIMER为一个很

}

void FIFO(void) {// }

void BlockClear(void) {

for(int i=0; iblock[i].content = -1; block[i].timer = 0; } }

void main(void){ Init();

cout<<\"|----------页 面 置 换 算 法----------|\"<cout<<\"页面号引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1\"<应用Optimal算法\"<应用FIFO算法\"<应用LRU算法\"<退出\"<int select;

while(select) {

cin>>select; switch(select) { case 0: break; case 1:

cout<<\"Optimal算法结果如下:\"<cout<<\"----------------------\"<cout<<\"FIFO算法结果如下:\"<cout<<\"----------------------\"<case 3:

cout<<\"LRU算法结果如下:\"<cout<<\"----------------------\"<cout<<\"请输入正确功能号\"<