#include
#include
#define?Bsize?4

typedef?struct?BLOCK????????//定義物理塊結(jié)構(gòu)體
{
????int?pageNum;????????????//頁(yè)號(hào)
????int?accessed_time;??????//訪問(wèn)字段，其值表示多久未被訪問(wèn)

}?BLOCK;

int?pc;?????????????????????//程序計(jì)數(shù)器，用來(lái)記錄指令的序號(hào)
int?n;??????????????????????//缺頁(yè)計(jì)數(shù)器，用來(lái)記錄缺頁(yè)的次數(shù)
static?int?temp[320];???????//用來(lái)存儲(chǔ)320條隨機(jī)數(shù)
BLOCK?block[Bsize];?????????//定義一大小為4的物理塊數(shù)組

void?init（）;????????????????//程序初始化函數(shù)
int?findExist（int?curpage）;?//查找物理塊中是否有該頁(yè)面
int?findSpace（）;????????????//查找空閑物理塊
int?findReplace（）;??????????//查找應(yīng)予置換的頁(yè)面
void?random（）;??????????????//產(chǎn)生320條隨機(jī)數(shù)顯示并存儲(chǔ)到temp[320]
void?show_Q_Page（）;?????????//顯示調(diào)用的頁(yè)面隊(duì)列
void?OPT（）;?????????????????//OPT算法
void?LRU（）;?????????????????//LRU算法
void?FIFO（）;????????????????//FIFO算法

void?init（）
{
????//初始化內(nèi)存物理塊數(shù)組，缺頁(yè)次數(shù)和程序計(jì)數(shù)器
????for（int?i?=?0;?i?????{
????????block[i].pageNum?=?-1;
????????block[i].accessed_time?=?0;
????????pc?=?n?=?0;
????}
}

int?findExist（int?curpage）
{
????//查找物理塊中是否有curpage頁(yè)面

????for（int?i?=?0;?i?????{
????????//若檢測(cè)到內(nèi)存中有該頁(yè)面，返回在block中的位置
????????if（block[i].pageNum?==?curpage?）
????????????return?i;
????}
????return?-1;??????????????//若沒(méi)有則返回-1.
}

int?findSpace（）
{
????//查找是否有空閑物理塊
????for（int?i?=?0;?i?????{
????????//若找到空閑的block，返回在block的位置
????????if（block[i].pageNum?==?-1）
????????????return?i;
????}
????return?-1;??????????????//否則返回-1.
}

int?findReplace（）
{
????//找到應(yīng)予置換頁(yè)面，即最近最久未使用的頁(yè)面，返回其所在塊的位置
????int?pos?=?0;
????for（int?i?=?0;?i?????{
????????if（block[i].accessed_time?>?block[pos].accessed_time）
????????????pos?=?i;
????}
????return?pos;
}

void?random（）
{
????//產(chǎn)生320條隨機(jī)數(shù)顯示并存儲(chǔ)到temp[320]
????int?flag?=?0;
????scanf（“%d“?&pc）;????????????????//在[0，319]的指令地址之間隨機(jī)選取一起點(diǎn)m
????printf（“?????????-?-?-?-?-?-?產(chǎn)生的320條指令序列：-?-?-?-?-\n“）;
????for（int?i?=?0;?i?????{
????????temp[i]?=?pc;
????????if（flag?%?2?==?0）?pc?=?++pc?%?320;?//產(chǎn)生50%的順序執(zhí)行指令（flag=0或2時(shí)順序執(zhí)行）
????????if（flag?==?1）?pc?=?rand（）?%?（pc?-?1）;?//產(chǎn)生25%的均勻分布在前地址部分指令
????????if（flag?==?3）?pc?=?pc?+?1?+?（rand（）?%?（320?-?（pc?+?1）））;
????????//產(chǎn)生25%的均勻分布在后地址部分指令
????????flag?=?++flag?%?4;
????????printf（“?%03d“?temp[i]）;
????????if（（i?+?1）?%?15?==?0）?printf（“\n“）;
????}
}

void?show_Q_Page（）
{
????//顯示隨機(jī)數(shù)
????for（int?i?=?0;?i?????{
????????printf（“?%03d“?temp[i]?/?10）;
????????if（（i?+?1）?%?15?==?0）?printf（“\n“）;
????}

}

void?OPT（）
{???
????int?exist?space?position?;
????int?curpage;
????int?f?=?0;
????printf（“訪問(wèn)頁(yè)???物理地址\t缺頁(yè)\t\t訪問(wèn)頁(yè)???物理地址\t缺頁(yè)“）;
????for（int?i?=?0;?i?????{
????????f++;
????????if（f?%?2?==?1）printf（“\n“）;
????????if（i?%?100?==?0）?getchar（）;
????????pc?=?temp[i];
????????curpage?=?pc?/?10;
????????printf（“%4d“?curpage）;
????????exist?=?findExist（curpage）;//查找內(nèi)存中是否有當(dāng)前頁(yè)面
????????if（exist?==?-1）???????????//若沒(méi)有
????????{
????????????space?=?findSpace（）;???????????//在內(nèi)存中查找是否有空閑塊
????????????if（space?!=?-1）????????