#include
#include
#define?Bsize?4

typedef?struct?BLOCK????????//定義物理塊結構體
{
????int?pageNum;????????????//頁號
????int?accessed_time;??????//訪問字段，其值表示多久未被訪問

}?BLOCK;

int?pc;?????????????????????//程序計數器，用來記錄指令的序號
int?n;??????????????????????//缺頁計數器，用來記錄缺頁的次數
static?int?temp[320];???????//用來存儲320條隨機數
BLOCK?block[Bsize];?????????//定義一大小為4的物理塊數組

void?init（）;????????????????//程序初始化函數
int?findExist（int?curpage）;?//查找物理塊中是否有該頁面
int?findSpace（）;????????????//查找空閑物理塊
int?findReplace（）;??????????//查找應予置換的頁面
void?random（）;??????????????//產生320條隨機數顯示并存儲到temp[320]
void?show_Q_Page（）;?????????//顯示調用的頁面隊列
void?OPT（）;?????????????????//OPT算法
void?LRU（）;?????????????????//LRU算法
void?FIFO（）;????????????????//FIFO算法

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

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

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

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

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

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

void?show_Q_Page（）
{
????//顯示隨機數
????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（“訪問頁???物理地址\t缺頁\t\t訪問頁???物理地址\t缺頁“）;
????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）;//查找內存中是否有當前頁面
????????if（exist?==?-1）???????????//若沒有
????????{
????????????space?=?findSpace（）;???????????//在內存中查找是否有空閑塊
????????????if（space?!=?-1）????????