最佳置換算法（OPT）
什么是OPT
最佳置換算法旅择，其所選擇的被淘汰的頁面將是以后永不使用的，或是在最長（未來）時間內(nèi)不再被訪問的頁面。采用最佳置換算法通吃乃唬可保證最低的缺頁率这溅。但是人們目前還無法與之组民，一個進(jìn)程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不再被訪問的悲靴，因而該算法是無法實現(xiàn)的臭胜，但是可以利用該算法取評價其他的算法。
算法思想
舉例如下：
我們將頁面隊列存在一個Vector動態(tài)數(shù)組中癞尚。我們可以從圖中得知：當(dāng)發(fā)生頁面置換時耸三，就要尋找在未來最長時間內(nèi)不再被訪問的頁面，將其置換出去浇揩，比如當(dāng)內(nèi)存中存在的頁面為 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在以后的隊列中第一次出現(xiàn)的這三個頁面的下標(biāo)值最大的那一個概行。因為頁面7在后面的頁面隊列中再次被訪問到是數(shù)組中下標(biāo)為17的地方,頁面0再次被訪問到是數(shù)組下標(biāo)為4的地方，頁面1再次被訪問的是數(shù)組中下標(biāo)為13,所以頁面7是未來最久才被訪問的頁面弧岳，所以將頁面7置換出去凳忙，將頁面2調(diào)入內(nèi)存中业踏。
具體算法：
每個頁面都有兩個屬性，一個是頁面號id涧卵，一個是時間參數(shù)count（此屬性在LRU中才會用到）
//pageId 要調(diào)入內(nèi)存的頁面號
//currentPoint 記錄當(dāng)前將要調(diào)入內(nèi)存中頁面所在頁面隊列中的下標(biāo)號
void OPT::replace(int pageId, int currentPoint)
{
//cur為內(nèi)存塊下標(biāo),searchCounter紀(jì)錄是否內(nèi)存塊搜索完畢
//循環(huán)爆出最長為使用的頁面
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再次被訪問的數(shù)組的下標(biāo)號
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;
}
}
//以上面內(nèi)存中存在的是頁面7伐脖、0、1為例乐设。尋找頁面7讼庇、0、1再次被訪問的下標(biāo)號最大的 //哪個頁面
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 << "正在放入內(nèi)存近尚，頁號ID：" << outPageId << "被替換出去" << endl;
ofs_OPT << "頁號ID：" << pageId << "正在放入內(nèi)存巫俺，頁號ID：" << outPageId << "被替換出去\n";
}
運(yùn)行結(jié)果截圖：
