设计和实现最佳置换算法、先进先出置换算法、最近最久未使用置换算法、页面缓冲置换算法、改进的clock算法;通过页面访问序列随机发生器实现对上述算法的测试及性能比较。
请求分页虚拟内存管理是建立在基本分页基础上的,为了能支持虚拟存储器功能,而增加了请求调页功能和置换功能。
工作集多数程序都显示出高度的局部性,也就是说,在一个时间段内,一组页面被反复引用。这组被反复引用的页面随着时间的推移,其成员也会发生变化。有时这种变化是剧烈的,有时这种变化则是渐进的。我们把这组页面的集合称为工作集
缺页率缺页中断次数/总的页面访问次数
最佳置换算法的主要思想是,在发生页面替换时,被替换的对象应该满足,在以后的页面访问中,该对象不会再次被访问或者较晚被访问。是一种理想化算法,具有最好性能(对于固定分配页面方式,本法可保证获得最低的缺页率),但实际上却难于实现,故主要用于算法评价参照
先进先出置换算法先进先出置换算法的主要思想是,在发生页面替换时,被替换的对象应该是最早进入内存的。
最近最久未使用置换算法最近最久未使用置换算法的主要思想是,在发生页面替换时,被替换的页面应该满足,在之前的访问队列中,该对象截止目前未被访问的时间最长
改进型Clock置换算法改进型Clock置换算法的主要思想是,在每次页面替换时,总是尽可能地先替换掉既未被访问又未被修改的页面。
页面缓冲算法设立空闲页面链表和已修改页面链表采用可变分配和基于先进先出的局部置换策略,并规定被淘汰页先不做物理移动,而是依据是否修改分别挂到空闲页面链表或已修改页面链表的末尾,空闲页面链表同时用于物理块分配,当已修改页面链表达到一定长度如Z个页面时,一起将所有已修改页面写回磁盘,故可显著减少磁盘I/O操作次数
根据各个算法的特点,程序实现的过程中用到的数据结构主要有以下两种
数组:定义的时候利用指针定义,然后根据全局变量block设定的给进程分配的物理内存的块数动态分配内存。一旦完成内存分配,不再改变数组的大小。用到数组结构来实现的算法程序有:最佳置换算法,先进先出置换算法,最近最久未使用置换算法,改进型置换算法。
队列:为单向队列,队列长度仍然由全局变量指定。用到队列的算法程序有:先进先出置换算法。队列结点元素的结构体如下
typedef struct node
{
int num;//页号
node* next;//下一个结点页面
} Node, *pNode;
typedef struct queue
{
int n;//总的结点数
pNode front;//队首指针
pNode rear; //队尾指针
} Queue, *pQueue;
链表:主要是将装入内存的页块串联起来。
用到链表的算法程序:页面缓冲算法。链表结点元素的结构体如下
struct LNode
{
int data;//页号
int flag;//访问位
int modify;//修改位
LNode* next;
};
struct Link
{
int num;//当前链表上的结点数
LNode* next;
};
全局共享函数
void initMemo();//初始化存储空间,主要是设置分配空间的大小
void generate();//生成访问序列
bool isInMemo (int n); //指定页号是否已经在内存中
最佳置换算法
void optimal (int n); //访问一个页面,执行一次最佳置换算法
void testOptimal();//算法实现函数
先进先出置换算法
void initQueue (pQueue q);//初始化队列
void push (pQueue q, int num);//队列中加入新的页面结点
void pop (pQueue q);//将页面移出内存
void destroy (pQueue q);//销毁队列
bool findInQueue (pQueue q, int num);//查找页面是否已经调入内存
void generate();//生成访问序列
void fifoTest();//每访问一个页面,执行一次算法
void fifo (pQueue q, int num);//先进先出置换算法实现函数
最近最久未使用置换算法
void LRU (int n);//每访问一个新的页面,执行一次LRU算法
void testLRU();//LRU算法实现函数
改进型clock置换算法
void updated_Clock (int n);//改进型clock算法实现函数
void test_Clock();//每访问一个新的页面,执行一次算法
页面缓冲算法
bool isInNodes (int n); //页面是否已经在链表中
void addToLink (int data, int type);//页面添加到已修改页面链表和空闲链表上
void emptyIdle();//将空闲链表上的所有页面送出内存
void emptyModi();//将已修改页面链表上所有的链表送出内存
void PBA (int n);//PBA算法实现函数
每个算法实现的代码量不同,以及不同算法使用的数据结构有差别,为了不至于程序过于臃肿庞大,所以所有的算法总共是在三个程序实现的(具体代码如8附录所示).其中,最佳置换算法,LRU算法,改进型clock置换算法是在test.cpp中实现的,先进先出置换算法是在FIFO.cpp中实现的,页面缓冲置换算法是在PBA.cpp中实现的。为了便于对比,程序中会先用genenrate()函数产生大小为32的访问序列,然后在每种算法下运行。测试过程如下:
利用generate函数产生访问序列如下access[32]={ 2, 3, 3, 7, 2, 8, 3, 7, 9, 7, 10, 8, 12, 11, 8, 8, 61, 61, 3, 61, 62, 60, 2,60, 3,62,62, 3, 3, 4, 2, 62}
各算法执行结果如下a)、最佳置换算法
b)、最近最久未使用
c)、改进的clock算法
d)、页面缓冲置换算法
e)、先进先出置换算法
最佳置换算法>页面缓冲置换算法>改进型clock置换算法>最近最久未使用算法>=先进先出置换算法。
源码链接:https://github.com/bjtucs/-/tree/master/实验4