页面置换算法实验报告.docx

J线交城乂挈
页面置换算法
实验报告
实验目的：
设计和实现最佳置换算法、 随机置换算法、 先进先出置换算法、 最近最久未使用
置换算法、 简单 Clock 置换算法及改进型 Clock 置换算法； 通过支持页面访问序
列随机发生实现有关算法的测试及性能比较。
、实验内容:
虚拟内存页面总数为 N ，页号从 0 到 N-1
物理内存由 M 个物理块组成
页面访问序列串是一个整数序列， 整数的取值范围为 0 到 N - 1 。 页面访问序
列串中的每个元素 p 表示对页面 p 的一次访问
页表用整数数组或结构数组来表示
符合局部访问特性的随机生成算法
确定虚拟内存的尺寸N,工作集的起始位置p,工作集中包含的贡 数e,工作集移动率mi (每处理m个页面访问则将起始位置p +1), 以及一个范围在 0 和 1 之间的值 t；
生成 m 个取值范围在 p 和 p + e 间的随机数， 并记录到页面访问序
列串中；
生成一个随机数r, 0 < r < 1;
如果 r < t ，则为 p 生成一个新值，否则 p = (p + 1) mod N；
如果想继续加大页面访问序列串的长度， 请返回第 2 步， 否则结束。
三、实验环境：
操作系统： Windows 7
软件： VC++
四、实验设计：
本实验包含六种算法，基本内容相差不太，在实现方面并没有用统一的
数据结构实现，而是根据不同算法的特点用不同的数据结构来实现：
1、最佳置换和随机置换所需操作不多，用整数数组模拟内存实现；
2、先进先出置换和最近最久未使用置换具有队列的特性， 故用队列模拟内
存来实现；
3、 CLOCK 置换和改进的 CLOCK 置换具有循环队列的特性，故用循环队
列模拟内存实现；
4、所有算法都是采用整数数组来模拟页面访问序列。
五、数据结构设计:
g^yemianziiihuan classes viHMHiiiiBaaiaiiiMHiiiaMMaiiizaBiii iimhiii ihbi ikbiHilbbii iimmiii ihbi nr
-■ ■ LinkQueue
q front % rear
-"iJLNode y data ■ flag 学 modify V next
-QNode 学 data 酬 next
//页面访问序列数组:
int ref[ref_size];
//内存数组： int phy[phy_size];
//队列数据结构定义：
typedef struct QNode /定义队列数据结构 {
int data;
struct QNode *next; }QNode,*QueuePtr; typedef struct {
QueuePtr front; //头指针
QueuePtr rear; //尾指针
}LinkQueue;
//定义链表数据结构
typedef struct LNode //定义循环链表数据结构 {
int data;
int flag; //访问位
int modify; //修改位
struct LNode *next; }LNode,*LinkList;
六、主要函数说明:
-_J Globals
q CLOCK。
.CfeatList[LinkList &L]
/ DelMid QueuefLinkQiJeue &Q, int £e]
♦ DcQueue[LinkQueue £Q, ini £e]
.DestroyLinkLisl[LinkList &L)
4 DestroyQueue[LinkQueue &Q)
.EnQueu efLinkQueue 区Q, ini e]
/ Exchange LN ode (Li nkList &L int a int i)
| , Fl FOO "
.getnum(int a, int b]
| 令 InitQucucfLinkQueuc &Q)
* lnsert_LNode(LinkLisi &L int e)
；9LRU「
♦ mainQ
.maxi (1 nt . int h* int g)
!…◎ Modified_CloclcO
[-* ORAO
|-令 RAN DO
Search_LinkLisl[LinkList &L int e. int &i]
Search_LL-FlagJLinkList XL int Ai)
Search LL ModifyClock|LinkList 虱L ini Smodify num]
SearchQueue(LinkQueuc &Q, int