本次竞速实验中，我采取的基本算法是LRU算法，即最近最少使用算法，在其中综合运用了LRU-2的思想。
由于本次实验的评测方式更接近于动态数据，因此OPT算法在本次实验中完全无法使用。所以采用LRU算法是理论上的最优解。
先上代码：
#include "pageReplace.h"
#define MAX_PHY_PAGE 64
#define MAX_PAGE 12
#define get_Page(x) (x>>MAX_PAGE)
#define GROUP_SHIFT 4
#define GROUP_SIZE 16
void pageReplace(long* physic_memery, long nwAdd) {
static int age[MAX_PHY_PAGE] = {0};
static int nhave[4] = {0};
static int time = 0;
time++;
int index = get_Page(nwAdd) & 0x3;
if (nhave[index] != GROUP_SIZE) {
register int end = nhave[index] + (index<<GROUP_SHIFT);
for (register int i = (index<<GROUP_SHIFT); i < end; i++) {
if (get_Page(nwAdd) == physic_memery[i]) {
age[i] = time;
return;
}
}
physic_memery[end] = get_Page(nwAdd);
age[end] = time - 424;
nhave[index]++;
return;
} else {
register int oldest = 0;
register int oldage = time;
register int end = ((index+1)<<GROUP_SHIFT);
for (register int i = (index<<GROUP_SHIFT); i < end; i++) {
if (get_Page(nwAdd) == physic_memery[i]) {
age[i] = time;
return;
}
if (age[i] < oldage) {
oldage = age[i];
oldest = i;
}
}
physic_memery[oldest] = get_Page(nwAdd);
age[oldest] = time - 424;
return;
}
}
最近最少使用算法，指每次淘汰时淘汰最久未得到使用的页面，这种算法可以较好的利用程序的局部性。
static int age[MAX_PHY_PAGE] = {0};
由于LRU算法需要判断最久未使用的页面，因此用一个年龄数组来记录TLB中每一个已有页面的最近使用年龄，从而通过遍历这个表来判断应该删除哪一个页面。
在一般的计算机中，对于LRU-2的实现一般采用的是2Q，即双队列实现方式。
计算机中实现LRU-2算法的一种常见方式，即除了TLB以外还有一个“缓冲表”，该表不为实际内存单元，仅为一个记录器，基本算法如下：
但是在页面置换测试的官方文档中，有这样一句要求：
要求学生实现的函数被调用时接收传入的虚拟地址，并且立即执行分配，修改
physic_memery数组,评测会检测当前使用的虚拟地址是否在物理页框中有对应
也就是说此要求决定了我们不能用缓冲队列去存储页面，而是必须将页面立即分配到TLB中。
那么我们只能通过LRU-2算法的本质来进行分析，LRU-2就是让刚被装入TLB的页面在替换时优先级变高。既然在我们的算法中，第一次分入TLB和从TLB中找到进入了不同的分支，那我们就可以在第一次进入后设置一个十分极端的年龄，强行让其在替换中处于高优先级。这样就能在一个表中近似的实现LRU-2算法。
在编写代码提交测试时，发现LRU-2的算法相较于LRU反而变低。LRU的缺页在260000+，而LRU-2的算法达到了290000+。在思考后，分析出的原因如下。
在无法实现2Q算法后，用“极端年龄”实现缓存队列时，本质上将TLB分成了两个部分，即：
也就是说，TLB承担了在2Q算法中TLB+BUFFER的作用，即有效空间被减小了，所以自然而然的出现了页面缺失率增高的现象。
本身的程序结构导致被LRU-2判定为“不常使用”的页面实际上并不是只偶尔使用一次。
因此，我“突发奇想”想到一种能综合LRU-2与LRU的算法，基于年龄表和极端年龄，提出“非极端年龄惩罚值”算法，即在第一次加入时，适当提高被替换的有限度，但又不被“一棒打死”，它的优先度依然比某些用了两次以上却长期不再使用的页面低。
这个“惩罚值”也就是我的代码中那个“意义不明”的424。
在作出如此改动时，经过提交测试后发现缺页率明显减少，证明了此种算法是一种在本次测试中十分优质的算法。
最开始的对age数组的处理方式是：每有一个新的页面加入或其中的页面被使用时，就将age设置为0，替换时替换最大的age。但这种算法有个明显的问题是在每次进入函数时，都要去将age数组进行一次遍历，对时间性能有很大的影响。于是经过改进后，用一个static变量time来记录当前的时间，在页面被使用时将age设置为当前的时间，这样只需要每次将time递增即可，大大减少了时间损耗。
最开始的程序中，在循环找到需要被替换的页面时，对于“找到页面是否存在”和“遍历找到age中的极值”是采用了两个循环，后来发现这两者可以综合进一个循环里面，因此进行优化，减少时间损耗。
register变量register变量顾名思义，即该变量直接存储在寄存器中，在调用时不需要经过访存。在本次实验中，将循环变量设置为register型变量可在一定程度上提升时间性能（按理说在一般的系统中系统会将这类循环中的变量自动设置为register型，此次实验中这样做能得到优化的原因个人还无法详细解释）。
组相联映射最通俗的解释就是将TLB分成几个大小相同的组，每一个组只会接收某些特定页号的页面，这样一来在进行遍历时，不需要遍历全部的页框，能大大地节省时间。缺点是缺页率会提高。
本次实验中采取的是四路组相联结构，用页号的最低两位来分组，共分成4组，经过测试，缺页率的上升并不明显，但time的消耗大大下降。
424是怎么来的？
在确定第一次加入的年龄惩罚值时，我采用了拟合的方式，即尝试多个值，最终根据提交结果来选择最优的取值。
因此要在某个范围内确定一个最合适的值。在未采用组相联时，这个最优值大约在460左右，但假如组相联机制后，这个值下降到了420附近。
但是这个值只是由提交上的结果得出的数据，如果地毯式的寻找最优值，不可避免地会造成过拟合，在换数据后不一定能达到最优。因此我在寻找到最优值附近时就没有继续在+-10的范围内拟合了，最终的结果中缺页的排名仍然很高。
由于自己不会写数据生成器，这次的本地测试只用了课程组提供的数据，缺页率的变化趋势与提交测评的结果相当，证明此算法虽然有过拟合的成分，但普适性依然较好。
在LRU的缺页置换分析中，我采用的是age数组的方式，但从其他同学那里了解到，有一种链表插入的方式可以在遍历上取得更优的时间效率。然而在我的算法中，由于时间惩罚值的存在，新加入的页面插入链表的位置是不固定的，因此用链表难以实现此种算法。
在面向对象的第三单元中，我了解到了Java的PriorityQueue容器，发现这种容器能够较好的符合我的算法，但由于竞速时间紧张，未能在C语言中实现这种容器，且这种容器的实现有可能会增加mem的消耗，因此最终没有采用。
原文：https://www.cnblogs.com/moc-85422729/p/xwc_os_pageReplace.html