页面置换算法学习之FIFO，Optimal，LRU
数据定义：
typedef struct item
{
int num; //页号
int time; //等待时间，LRU算法会用到这个属性
}Pro; int pageNum; //系统分配给作业的主存中的页面数
int memoryNum; //可用内存页面数
int curmemory; //调入内存中的页面个数
int missNum; //缺页次数
float missRate; //缺页率
char c; //得到用户的输入字符，来选择相应的置换算法
Pro *page; //作业页面集
Pro *memory; //内存页面集
page = (Pro*)malloc(sizeof(Pro)*pageNum);
memory = (Pro*)malloc(sizeof(Pro)*memoryNum);
A．先进先出(FIFO)页面置换算法
这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO 算法并不能保证这些页面不被淘汰。
这里，我们仍用上面的例子，但采用 FIFO 算法进行页面置换(图
4-27)。当进程第一次访问页面 2 时，将把第 7 页换出，因为它是最先被调入内存的；在第一次访问页面 3 时，又将把第 0 页换出，
因为它在现有的 2， 0，
1 三个页面中是最老的页。 由图 4-27 可以看出，利用 FIFO 算法时进行了
12 次页面置换，比最佳置换算法正好多一倍。
//FIFO页面置换
void fifoPage(Pro *page, Pro *memory)
{
missNum = 0;
printf("FIFO页面置换情况: \n");
for (i = 0; i<pageNum; i++)
{
if (Search(page[i].num, memory)<0)//若在内存中没有找到该页面
{
missNum++;
memory[curmemory].num = page[i].num;
print(memory);
curmemory = (curmemory + 1) % memoryNum; //找出最先进入内存的页面
}
}//end for
missRate = (float)missNum / pageNum;
printf("缺页次数：%d 缺页率: %f\n", missNum, missRate);
}
B．最佳(Optimal)置换算法
最佳置换算法是由 Belady 于
1966 年提出的一种理论上的算法。 其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。现举例说明如下。
假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
进程运行时，先将 7，0，1
三个页面装入内存。以后，当进程要访问页面 2 时，将会产生缺页中断。
此时 OS 根据最佳置换算法， 将选择页面 7 予以淘汰。
这是因为页面 0 将作为第 5 个被访问的页面，页面
1 是第 14 个被访问的页面，而页面 7 则要在第
18 次页面访问时才需调入。 下次访问页面 0 时， 因它已在内存而不必产生缺页中断。当进程访问页面 3时，又将引起页面 1 被淘汰；因为，它在现有的
1，2，0 三个页面中，将是以后最晚才被访问的。图 4-26 示出了采用最佳置换算法时的置换图。由图可看出，采用最佳置换算法发生了 6 次页面置换。
void OptimalPage(Pro *page, Pro *memory)
{
missNum = 0;
curmemory = 0;
printf("Optimal页面置换情况: \n");
for (i = 0; i<pageNum; i++)
{
if (Search(page[i].num, memory) < 0)//若在内存中没有找到该页面
{
//找出未来最长时间内不再被访问的页面
int tem;
int opt = 0;
for (int k = 0; k < memoryNum; k++)
{
if (memory[k].num == -1)
{
curmemory = k;
break;
} //endif
tem = 0; //页面k在未来tem时间内不会出现
int j;
for (j = i+1; j < pageNum; j++)
{
if (page[j].num == memory[k].num)
{
if (tem > opt)
{
opt = tem;
curmemory = k;
}
break;
}
else
tem++;
} //end for
if (j == pageNum)
{
opt = tem;
curmemory = k;
}
}
missNum++;
memory[curmemory].num = page[i].num;
print(memory);
}
}//end for
missRate = (float)missNum / pageNum;
printf("缺页次数：%d 缺页率: %f\n", missNum, missRate);
}
C．最近最久未使用LRU(Least
Recently Used)置换算法
FIFO 置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU 置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最久未使用的页面予以淘汰。
利用 LRU 算法对上例进行页面置换的结果如图 4-28 所示。当进程第一次对页面
2 进行访问时，由于页面 7 是最近最久未被访问的，故将它置换出去。当进程第一次对页面 3进行访问时，第
1 页成为最近最久未使用的页，将它换出。由图可以看出，前 5 个时间的图像与最佳置换算法时的相同，但这并非是必然的结果。因为，最佳置换算法是从“向后看”的观点出发的，即它是依据以后各页的使用情况；而 LRU 算法则是“向前看”的，即根据各页以前的使用情况来判断，而页面过去和未来的走向之间并无必然的联系。
void LRUPage(Pro *page, Pro *memory)
{
missNum = 0;
curmemory = 0;
printf("LRU页面置换情况: \n");
for (i = 0; i<pageNum; i++)
{
int rec=Search(page[i].num, memory);
if (rec < 0) //若在内存中没有找到该页面
{
missNum++;
for (int j = 0; j<memoryNum; j++) //找出最近最久未使用的页面
if (memory[j].time == -1)
{
curmemory = j;
break;
}
else if (memory[j].time > memory[curmemory].time)
curmemory = j;
memory[curmemory].num = page[i].num;
memory[curmemory].time = 0;
print(memory);
}
else
memory[rec].time = 0;
for (int j = 0; j<memoryNum; j++) //内存中的所有页面等待时间+1
if (memory[j].num != -1)
memory[j].time++;
}//end for
missRate = (float)missNum / pageNum;
printf("缺页次数：%d 缺页率: %f\n", missNum, missRate);
}