# 基于C++的请求分页虚拟页面替换算法
# 一、需求分析
实现OPT、FIFO、LRU、Clock等页面替换算法。接收用户输入参数，包括程序长度（页面数）、页框个数及页面大小，输出结果采用不同颜色区分命中、替换及直接加入空闲块。
- OPT（最佳置换算法）：其所选择的被淘汰页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面，但是由于无法预知一个进程在内存中的若干个页面中，哪一个页面是未来最长时间内不被访问的，因而该算法无法实现
- FIFO（先进先出页面是换算法）：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰
- LRU（最近最久未使用置换算法）：只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰
- Clock：使用的较多的一种LRU近似算法
# 二、概要设计
- FIFO算法：在该模拟系统中，使用队列来存储页面并且按照其到达队列的先后顺序进行排序，因此，每次需要进行页面替换时，便选择队首或者标识符指示其驻留时间最长的页面进行替换
- LRU算法：同样使用数组队列来模拟，数组下标指示位置，而数组值则作为标识符来计算该页面自最后一次被访问到现在为止经历了多长时间，当选择被置换的页面时，则扫描该数组队列，找到标识符最大的页面进行替换
- Clock算法：同样使用数组队列来模拟，数组下标指示内存位置，而数组值则作为标识符在替换过程中发挥作用。当选择被替换的页面时，则扫描该数组队列，检查数组值，若值为0，则进行替换；若数组值为1，则将数组值置为1，继续扫描下一个数组值。若扫描完毕没有合适的页面进行替换时，则对数组进行第二次扫描
# 三、详细设计
## 3.1 设计思想
- FIFO算法：先进先出思想，即选择在内存中驻留时间最久的页面给予淘汰
- LRU算法：根据页面调入内存后的使用情况作出决策，选择最近最久未使用耳朵页面予以淘汰
- Clock算法：设置访问位，循环检查各页面使用情况，是一种LRU近似算法
## 3.2 模块设计
- 输入子模块：接收用户的输入，用户的输入共有程序长度（页面数）、页框个数及页面大小三种
- 模拟页面置换子模块：该模块共有三种函数，分别模拟FIFO算法，LRU算法，Clock算法
**FIFO算法描述**
```C++
void fifo(int pageNum,int pageFrameNum,int size)
{
int m[pageFrameNum];
for(int i = 0 ; i < pageFrameNum ; i++)
m[i] = 0;
//模拟页面访问
for(int i = 0 ; i < pageNum; i++)
{
for(int k = 0; ; k++)
{
for(int j = 0 ; j < pageFrameNum ; j++)
{
if(m[j] == k)
{
m[j] = k+1;
for(int h = 0 ; h < pageFrameNum ; h++)
{
if(m[h] == 0)
cout << "# ";
else
{
if(k == 0)
{
if(h!=j)
cout << "% ";
else
cout << "+ ";
}
else
{
if(h!=j)
cout << "% ";
else
cout << "t ";
}
}
}
cout << endl;
k = -1;
break;
}
}
if(k < 0 )
break;
}
}
}
```
**LRU算法描述**
```C++
void lru(int pageNum,int pageFrameNum,int size)
{
int m[pageFrameNum];
for(int i = 0 ; i < pageFrameNum ; i++)
{
m[i] = 0;
}
for(int i = 0 ; i < pageNum; i++)
{
int j;
for(j = 0; j < pageFrameNum; j++)
{
if(m[j] == 0)
{
m[j] = 1;
for(int k = 0 ; k < pageFrameNum; k++)
{
if(m[k] == 0)
cout << "# ";
else
{
if(k != j)
cout << "% ";
else
cout << "+ ";
}
}
cout << endl;
break;
}
}
if(j > pageFrameNum-1)
{
int max = 0,tmp;
for(int d = 0; d < pageFrameNum; d++)
{
if(m[d] > max)
{
max = m[d];
tmp = d; //该位置页面被替换
}
}
m[tmp] = 1;
for(int f = 0; f < pageFrameNum; f++)
{
if(f != tmp)
cout << "% ";
else
cout << "t ";
}
cout << endl;
}
//模拟页面访问过程
while(true)
{
int tmp = rand()%(pageFrameNum+1);
if(m[tmp] > 0)
{
for(int t = 0; t < pageFrameNum; t++)
{
if(m[t] > 0)
m[t]++;
}
m[tmp] = 1;
}
break;
}
}
}
```
**Clock算法描述**
```C++
void clock(int pageNum,int pageFrameNum,int size)
{
int m[pageFrameNum];
for(int i = 0 ; i < pageFrameNum ; i++)
{
m[i] = -1;
}
for(int i = 0 ; i < pageNum; i++)
{
int j;
for(j = 0; j < pageFrameNum; j++)
{
if(m[j] == -1)
{
m[j] = 1;
for(int k = 0 ; k < pageFrameNum; k++)
{
if(m[k] == -1)
cout << "# ";
else
{
if(k != j)
cout << "% ";
else
cout << "+ ";
}
}
cout << endl;
break;
}
}
if(j > pageFrameNum-1)
{
int flag = 0,tmp;
for(int d = 0; d < pageFrameNum; d++)
{
if(m[d] == 0)
{
m[d] = 1;
tmp = d;
flag = 1;
break;
}
else
{
m[d] = 0;
}
}
if(flag == 0)
{
for(int d = 0; d < pageFrameNum; d++)
{
if(m[d] == 0)
{
m[d] = 1;
break;
}
}
}
for(int f = 0; f < pageFrameNum; f++)
{
if(f != tmp)
cout << "% ";
else
cout << "t ";
}
cout << endl;
}
//模拟页面访问过程
while(true)
{
int tmp = rand()%(pageFrameNum+1);
if(m[tmp] == 0)
{
m[tmp] = 1;
}
break;
}
}
}
```
**输出子模块**：输出页面置换后的内存调用结果，其中输出符号表示：
- t:替换
- +:直接加入空闲区
- \#:页框空闲
- %:页框不空闲
# 四、调试�
