最佳置换算法（OPT）
什么是OPT
最佳置换算法，其所选择的被淘汰的页面将是以后永不使用的，或是在最长（未来）时间内不再被访问的页面。采用最佳置换算法通常可保证最低的缺页率。但是人们目前还无法与之，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但是可以利用该算法取评价其他的算法。
算法思想
举例如下：
我们将页面队列存在一个Vector动态数组中。我们可以从图中得知：当发生页面置换时，就要寻找在未来最长时间内不再被访问的页面，将其置换出去，比如当内存中存在的页面为 7、0、1,且要访问页面2时，此时我们要寻找页面队列中将要访问到的页面2以后的页面队列（0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1）中，页面7、0、1哪个最久未被访问到，即寻找页面7、0、1在以后的队列中第一次出现的这三个页面的下标值最大的那一个。因为页面7在后面的页面队列中再次被访问到是数组中下标为17的地方,页面0再次被访问到是数组下标为4的地方，页面1再次被访问的是数组中下标为13,所以页面7是未来最久才被访问的页面，所以将页面7置换出去，将页面2调入内存中。
具体算法：
每个页面都有两个属性，一个是页面号id，一个是时间参数count（此属性在LRU中才会用到）
//pageId 要调入内存的页面号
//currentPoint 记录当前将要调入内存中页面所在页面队列中的下标号
void OPT::replace(int pageId, int currentPoint)
{
//cur为内存块下标,searchCounter纪录是否内存块搜索完毕
//循环爆出最长为使用的页面
int max = 0, perCount, outPageId = -1, cur = 0;
int search_count[PRO_MEMORY];
for (int i = 0; i < PRO_MEMORY; i++)
{
//比如，从页面2后面的页面开始扫描记录页面7、0、1再次被访问的数组的下标号
for (int j = currentPoint + 1; j < length; j++)
{
if (pages_OPT[i].getId() == usePageNumList_OPT[j])
{
search_count[i] = j;
break;
}
}
if (search_count[i] == 0)
{
search_count[i] = length;
}
}
//以上面内存中存在的是页面7、0、1为例。寻找页面7、0、1再次被访问的下标号最大的 //哪个页面
for (int k = 0; k < PRO_MEMORY; ++k)
{
perCount = search_count[k];
if (max < perCount)
{
max = perCount;
cur = k;
}
}
outPageId = pages_OPT[cur].getId();
pages_OPT[cur].setId(pageId);
cout << "页号ID：" << pageId << "正在放入内存，页号ID：" << outPageId << "被替换出去" << endl;
ofs_OPT << "页号ID：" << pageId << "正在放入内存，页号ID：" << outPageId << "被替换出去\n";
}
运行结果截图：
