在操作系统的课上学到了页面替换算法，要想彻底理解还需要自己动手来实现，进行验证。
这里为了方便，先把page类的声明展示：
//Page.h
#pragma once
class Page
{
private:
int number;
int use_count;//未使用时间统计
public:
Page() :number(0), use_count(0)
{
}
friend class PageReplacement_FIFO_array;
friend class PageReplacement_FIFO_list;
friend class PageReplacement_LRU_count;
friend class PageReplacement_LRU_stack;
};
FIFO算法
下面用c++程序来为各位讲解如何实现FIFO算法。
FIFO，顾名思义，就是谁先用谁先被替换，按固定顺序循环。
(一）存储方式为数组：显然我们可以用数组索引的形式，每次替换后自动加1（或从尾到头）。
//PageReplacement_FIFO_array.h
#pragma once
#include<vector>
#include"Page.h"
class PageReplacement_FIFO_array
{
private:
int page_num; //物理内存块数
bool flag;//是否缺页的标志位,这里把刚开始页面没填充满也算作缺页
int cur;//当前将要作为淘汰的页号
std::vector<Page> pages;
public:
PageReplacement_FIFO_array(int m_page_num);
/*void create();*/
void print();
bool find(int x); //查找是否已在内存物理块中
void FIFO(int x); //FIFO页面置换算法
void PageReplace(int count);
};
//PageReplacement_FIFO_array.cpp
#include "PageReplacement_FIFO_array.h"
#include <iostream>
PageReplacement_FIFO_array::PageReplacement_FIFO_array(int m_page_num)
: page_num(m_page_num), cur(0) //默认从下标是0的位置开始替换
{
pages.resize(page_num);
}
void PageReplacement_FIFO_array::print() //将每次更新后的结果输出，以便验证自己写的程序对不对
{
for (int i = 0; i < page_num; i++)
{
std::cout << pages[i].number << " ";
}
std::cout << std::endl;
}
bool PageReplacement_FIFO_array::find(int x)
{
for (auto e:pages)
{
if (e.number == x)
{
return true;
}
}
return false;
}
void PageReplacement_FIFO_array::FIFO(int x)
{
flag = true;
if (!find(x)) //必须每次先进行查找，找不到再根据我们已经设定好的位置进行替换
{
flag = false;
pages[cur].number = x;
cur = (cur + 1) % page_num;//更新下一次替换的位置
}
std::cout << "input:" << x << " ";
print();
}
void PageReplacement_FIFO_array::PageReplace(int count) //页面替换的操作
{
int random;
static int Page_Fault_count=0;
for (int i = 0; i < count; i++)
{
random = rand()%50 + 1;
FIFO(random);
if (flag == false)
{
Page_Fault_count++;
}
}
double rate = (double)(Page_Fault_count) / (double)count;//计算缺页率
std::cout << "the rate of missing pages:" << rate << std::endl;
}
(二）存储方式为链表：显然我们需要从头遍历到尾，再从尾找到头，需要循环链表，这里以stl中的list演示：
//PageReplacement_FIFO_list.h
#pragma once
#include<list>
#include"Page.h"
class PageReplacement_FIFO_list
{
private:
int page_num; //物理内存块数
bool flag;//是否缺页的标志位
std::list<Page> pages;
std::list<Page>::iterator cur ;//当前将要作为淘汰的页
public:
PageReplacement_FIFO_list(int m_page_num);
void print();
bool find(int x); //查找是否已在内存物理块中
void FIFO(int x); //FIFO页面置换算法
void PageReplace(int count);
};
//PageReplacement_FIFO_list.cpp
#include "PageReplacement_FIFO_list.h"
#include <iostream>
#include<list>
PageReplacement_FIFO_list::PageReplacement_FIFO_list(int m_page_num)
: page_num(m_page_num)
{
pages.resize(page_num);
cur = pages.begin();
}
void PageReplacement_FIFO_list::print()
{
for (auto e:pages)
{
std::cout << e.number << " ";
}
std::cout << std::endl;
}
bool PageReplacement_FIFO_list::find(int x)
{
for (auto e : pages)
{
if (e.number == x)
{
return true;
}
}
return false;
}
void PageReplacement_FIFO_list::FIFO(int x)
{
flag = true;
if (!find(x))
{
flag = false;
cur->number = x;
std::list<Page>::iterator page_end = pages.end();
page_end--;//这里是要找到链表尾，因为list的end()是最后一个元素的下一个位置
if (cur != page_end)
{
cur++;
}
else
{
cur = pages.begin();
}
}
std::cout << "input:" << x << " ";
print();
}
void PageReplacement_FIFO_list::PageReplace(int count)
{
int random;
static int Page_Fault_count = 0;
for (int i = 0; i < count; i++)
{
random = rand() % 50 + 1;
FIFO(random);
if (flag == false)
{
Page_Fault_count++;
}
}
double rate = (double)(Page_Fault_count) / (double)count;
std::cout << "the rate of missing pages:" << rate << std::endl;
}
执行结果：
//main.cpp
#include<iostream>
using namespace std;
#include"PageReplacement_FIFO_array.h"
#include"PageReplacement_FIFO_list.h"
#include<list>
void FIFO_array()
{
PageReplacement_FIFO_array pages(3);
pages.print();
pages.PageReplace(5000);
}
void FIFO_list()
{
PageReplacement_FIFO_list pages(3);
pages.print();
pages.PageReplace(5000);
}
int main()
{
FIFO_array();
FIFO_list();
return 0;
}
FIFO_array ：
内存容量为3块：
内存容量为4块：
可以发现当内存容量提高后
命中率将会提高，缺页率（这里指的是概率，实际情况可能会相反）会降低。其他算法情况与之类似。
FIFO_list：
内存容量为3块：
内存容量为4块：
LRU算法
继续上一讲，这期讲解LRU（least recently used algorithm）算法，即从当前往前数，谁最长时间没用过就选谁替换。
下图中带星号的空格代表下一次准备替换的页面。
LRU:t=4，P4找不到，需要替换，此时看已经在内存中的页面是1,2,3,这时P1最久没使用。
OPT（optimal replacement algorithm）：属于事后诸葛亮，已经知道访问页面的顺序，从当前往后看，谁最晚再次使用就将谁替换
如下图，t=4，P4找不到，需要替换，此时看已经在内存中的页面是1,2,3,
其中P1下次使用是在t=5,P2下次使用是在t=6,P1下次使用是在t=7,所以选择3进行替换。
page类的声明：
（一）使用计数器来实现LRU算法：统计每个页面使用的时间，进行比较选择使用时间最长的那个进行替换
//PageReplacement_LRU_count.h
#pragma once
#include"Page.h"
#include<vector>
class PageReplacement_LRU_count
{
private:
int page_num; //物理内存块数
bool flag;//是否缺页的标志位
std::vector<Page> pages;
public:
PageReplacement_LRU_count(int m_page_num);
void print();
bool find(int x); //查找是否已在内存物理块中
void LRU(int x); //LRU页面置换算法
size_t LRUpos(); //返回要替换的页面在 std::vector<Page> pages的下标位置
void PageReplace(int count);
};
//PageReplacement_LRU_count.cpp
#include "PageReplacement_LRU_count.h"
#include<iostream>
#include<list>
PageReplacement_LRU_count::PageReplacement_LRU_count(int m_page_num)
:page_num(m_page_num)
{
pages.resize(page_num);
}
void PageReplacement_LRU_count::print() //将每次更新后的结果输出，以便验证自己写的程序对不对
{
std::cout <<"page numbers:";
for (auto e : pages)
{
std::cout << e.number << " ";
}
std::cout << std::endl;
std::cout <<"page used time:";
for (auto e : pages)
{
std::cout << e.use_count << " ";
}
std::cout << std::endl;
}
bool PageReplacement_LRU_count::find(int x)
{
for (auto e : pages)
{
if (e.number == x) //必须每次先进行查找，找不到再根据我们已经设定好的位置进行替换
{
e.use_count = 0;
return true;
}
}
return false;
}
size_t PageReplacement_LRU_count::LRUpos()
{
size_t res = 0;
for (int i=1;i<pages.size();i++) //找谁的use_count即使用时间最长
{
if (pages[i].use_count > pages[res].use_count)
{
res = i;
}
}
return res;
}
void PageReplacement_LRU_count::LRU(int x)
{
flag = true;
for (auto& e : pages)
{
e.use_count++;
}
if (!find(x))
{
flag = false;
size_t LRU_pos = LRUpos();
pages[LRU_pos].number = x; //替换页面，同时将新页面的使用次数即use_count置0
pages[LRU_pos].use_count = 0;
}
std::cout << "input:" << x << std::endl;
print();
}
void PageReplacement_LRU_count::PageReplace(int count)
{
int random;
static int Page_Fault_count = 0;
for (int i = 0; i < count; i++)
{
random = rand() % 50 + 1;
LRU(random);
if (flag == false)
{
Page_Fault_count++;
}
}
double rate = (double)(Page_Fault_count) / (double)count;
std::cout << "the rate of missing pages:" << rate << std::endl;
}
（二）使用栈来实现LRU算法：先使用的页面先入栈；每次取栈底的元素进行替换，然后新的元素进栈；如果命中就将其移动到栈顶。
//PageReplacement_LRU_stack.h
#pragma once
#include"Page.h"
#include<stack>
class PageReplacement_LRU_stack
{
private:
int page_num; //物理内存块数
bool flag;//是否缺页的标志位
std::stack<int> pages;
public:
PageReplacement_LRU_stack(int m_page_num);
void print();
void deleteExistPage(int x);
void deleteBottom(); //删除栈底元素
bool find(int x);
void PageReplace(int count);
};
//PageReplacement_LRU_stack.cpp
#include "PageReplacement_LRU_stack.h"
#include<stack>
#include<iostream>
PageReplacement_LRU_stack::PageReplacement_LRU_stack(int m_page_num)
:page_num(m_page_num)
{
for (int i = 0; i < page_num; i++)
{
pages.push(0);
}
}
void PageReplacement_LRU_stack::print()
{
if (!pages.empty())
{
int top_page = pages.top();
std::cout << top_page << " ";
pages.pop();
print();
pages.push(top_page);
}
else
return;
}
void PageReplacement_LRU_stack::deleteExistPage(int x) //如果栈中已经有这个元素，就将他先移除栈（之后再压栈）
{
if (!pages.empty())
{
int top_num = pages.top();
pages.pop();
if (top_num != x)
{
deleteExistPage(x);
pages.push(top_num);
}
}
else
{
return;
}
}
void PageReplacement_LRU_stack::deleteBottom()//这个函数是删除栈底元素
{
if (!pages.empty())
{
int page_size = pages.size();
int top_num = pages.top();
pages.pop();
if (page_size != 1) //这里是通过递归方法将除栈底元素以外其他元素先出栈再进栈
{
deleteBottom();
pages.push(top_num);
}
}
else
{
return;
}
}
bool PageReplacement_LRU_stack::find(int x)
{
bool find = false;
if (pages.top() == 0)//表示cache没满
{
while((!pages.empty())&&(pages.top() == 0))
{
pages.pop();
}
int new_size = pages.size();
deleteExistPage(x);
if (pages.size() == new_size)//表示cache中没有页x
{
pages.push(x);
}
else //cache已经有x，将x进入栈顶
{
find = true;
pages.push(x);
}
while (pages.size() != page_num)//表示还有页没有进入cache中
{
pages.push(0);
}
return find;
}
deleteExistPage(x);
if (pages.size() == page_num)//表示cache中没有页x
{
deleteBottom(); //将栈底元素移除，再将新元素进栈
pages.push(x);
}
else //cache已经有x，将x进入栈顶
{
find = true;
pages.push(x);
}
return find;
}
void PageReplacement_LRU_stack::PageReplace(int count)
{
int random;
static int Page_Fault_count = 0;
for (int i = 0; i < count; i++)
{
random = rand() % 50 + 1;
std::cout << "input:" << random << std::endl;
flag = find(random);
print();
if (flag == false)
{
Page_Fault_count++;
}
}
double rate = (double)(Page_Fault_count) / (double)count;
std::cout << "the rate of missing pages:" << rate << std::endl;
}
结果测试：
//main.cpp
#include<iostream>
using namespace std;
#include"PageReplacement_LRU_count.h"
#include"PageReplacement_LRU_stack.h"
#include<list>
void LRU_count()
{
PageReplacement_LRU_count pages(3);
pages.print();
pages.PageReplace(5000);
}
void LRU_stack()
{
PageReplacement_LRU_stack pages(3);
pages.print();
pages.PageReplace(5000);
}
int main()
{
LRU_count();
LRU_stack();
return 0;
}
LRU_count：
内存容量为3块：
内存容量为4块：
LRU_stack：
内存容量为3块：
内存容量为4块：
