页面置换算法---最佳置换算法（OPT）

最佳置换算法（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";
}

运行结果截图：

源代码工程下载(包含FIFO和LRU)