请求分页存储管理.pdf

实验3请求分页存储管理

实验目的

（1）熟悉主存的分配与回收；

（2）了解虚拟存储技术的特点；

（3）掌握请求页式存储管理的页面置换算法；

实验内容与步骤

1、实验准备知识

(1)通过随机数产生一个指令序列

(2)将指令序列变换成为页地址流设：

(3)计算并输出下述各种算法在不同内存容量下的命中率

a)先进先出的算法（FIFO）；

b)最近最少使用算法（LRU）；

c)最佳淘汰算法（OPT）；

(4)所涉及的算法

1）FIFO算法

定义变量ptr。

一开始先预调页填满内存。在这一部分，ptr指向下一个要存放的位置。

之后继续执行剩下的指令。此时，ptr表示队列最前面的位置，即最先进来的位

置，也就是下一个要被替换的位置。ptr用循环加，即模拟循环队列。

2）LRU算法

定义数组ltu[],即last_time_use来记录该页最近被使用的时间。

定义变量ti模拟时间的变化，每执行一次加一。

这个算法，我没有预调页，而是直接执行所有指令。

若当前需要的页没在内存里，就寻找最近最少使用的页，也就是ltu[]最小的页，

即最近一次使用时间离现在最久的页，然后替换掉它。或者在内存还未满时，直

接写入，这个我以初始化内存里所有页为-1来实现。

若已经在内存里了，则只遍历内存内的页，把当前页的最近使用时间改一下即可。

3）OPT算法

定义数组ntu[],即next_time_use来记录下一次被使用的时间，即将来最快使用

时间。初始化为-1.

开始时预调页填满内存里的页。同样利用变量ptr来表示下一个要存放的位

置从而控制预调页的过程。

接着初始化ntu数组为-1。然后求出每一页下一次被使用的指令号，以此代

替使用时间。如果所有剩下的序列都没有用该页时，则还是-1.这种值为-1的页

显然是最佳替换对象。

然后执行所有剩下的指令。当该页不在内存里时，遍历ntu数组，遇到-1的

直接使用该页，没有则用ntu[]值最大的，也就是最晚使用的。

无论该页在不在内存里，因为这一次已经被使用了，所以都应该更新这个页

的ntu[]，只需往前看要执行的页流，记录下第一个遇到的该页即可。如果没有

找到同样添-1即可。

2、实验步骤

（1）首先，初始化数据

（2）测试地址转换机构

参考代码如下：

privatevoidAddressTransform(stringfunctionName)

{

//该数组用来存储调用页面号的序列

int[]numbers=_pageNumbers;

//调用页面列表的副本，用于循环调用列表时的操作

ListPageTableEntrycopyInvokeTable=newListPageTableEntry();

//初始化调用页表和快表

for(inti=0;inumbers.Length;i++)

{

varentry=newPageTableEntry{PageNumber=numbers[i],BlockNumber=

numbers[i]+1};

//形成页面部分在快表的情况，规定：页面号为偶数的在快表中有记录

if(i%2==0)

{

entry.IsInMemory=true;

fastTable.Add(newFastTable{PageNumber=entry.PageNumber,

BlockNumber=entry.BlockNumber});

}

else

{

entry.IsInMemory=false;

}

entry.Visi