#include "UsedReplacement.h"
void begin(){
int i,j,k;
printf("Please enter the number of page frames（1-7）：");
scanf("%d",&j);
for(k=0;;k++){
printf("Whether to use random number to generate input string（0：是， 1：否）");
scanf("%d",&j);
if(j==0){
randomnum();
break;
}else if(j==1){
break;
}else{
printf("Please enter the correct selection！\n");
}
}
printf("The page reference string is：\n");
for(i=0;i<20;i++){
printf("%d ",numbers[i]);
}
printf("\n");
init();
}
void randomnum(){
int i;
srand(time(0)); //设置随机数种子
for(i=0;i<20;i++){
numbers[i]=rand()%10; //生成0~9的随机页面引用串
}
}
void init(){
int i,j;
for(i=0;i<20;i++)
for(j=0;j<nums;j++){
stack[i][j]=10;
}
}
void printShow(){
int i,j;
for(i=0;i<nums;i++){
for(j=0;j<20;j++){
if(stack[j][i]==10)
printf("* ");
else
printf("%d ",stack[j][i]);
}
printf("\n");
}
}
void FIFO(){
init();
int i,j=1,n=20,k,f,m;
stack[0][0]=numbers[0];
for(i=1;i<20;i++){
f=0;
for(m=0;m<nums;m++){
stack[i][m]=stack[i-1][m];
}
for(k=0;k<nums;k++){
if(stack[i][k]==numbers[i]){
n--;
f=1;
break;
}
}
if(f==0){
stack[i][j]=numbers[i];
j++;
}
if(j==nums)
j=0;
}
printf("\n");
printf("FIFO Algorithm：\n");
printShow();
printf("The number of page missing errors is: %d\n",n);
}
void LRU(){
int i,j,m,k,sum=1;
int sequence[7]={0}; // 记录序列
init();
stack[0][0]=numbers[0];
sequence[0]=nums-1;
for(i=1;i<nums;i++){
for(j=0;j<nums;j++){
stack[i][j]=stack[i-1][j];
}
for(i=0;j<nums;j++){
if(sequence[j]=0){
stack[i][j]=numbers[i];
break;
}
}
for(j=0;j<i;j++){ //将之前的优先级序列减一
sequence[j]--;
}
sequence[i]=nums-1; //最近使用的优先级列为最高
sum++;
}
for(i=nums;i<20;i++){
int f;
f=0;
for(j=0;j<nums;j++){
stack[i][j]=stack[i-1][j];
}
for(j=0;j<nums;j++){
if(stack[i][j]==numbers[i]){
f=1;
k=j;
break;
}
}
if(f=0){
for(j=0;j<nums;j++){
if(sequence[j]==0){
m=j;
break;
}
}
for(j=0;j<nums;j++){
sequence[j]--;
}
sequence[m]=nums-1;
stack[i][m]=numbers[i];
sum++;
}else{
if(sequence[k]==0){
for(j=0;j<nums;j++){
sequence[j]--;
}
sequence[j]--;
}else if(sequence[k]==nums-1){
// nothing
}else{
for(j=0;j<nums;j++){
if(sequence[k]<sequence[j]){
sequence[j]--;
}
}
sequence[k]=nums-1;
}
}
}
printf("\n");
printf("LRU Algorithm：\n");
printShow();
printf("Number of page missing errors：%d\n",sum);
}
void OPT(){
int i,j,k,sum=1,f,q,max;
int seq[7]={0};//记录序列
init();
stack[0][0]=numbers[0];
seq[0]=nums-1;
for(i=1;i<nums;i++)//前半部分，页面空置的情况
{
for(j=0;j<nums;j++)
{
stack[i][j]=stack[i-1][j];
}
for(j=0;j<nums;j++)
{
if(seq[j]==0)
{
stack[i][j]=numbers[i];
break;
}
}
for(j=0;j<i;j++)//将之前的优先级序列都减1
{
seq[j]--;
}
seq[i]=nums-1;//最近使用的优先级列为最高
sum++;
}
for(i=nums;i<20;i++)//后半部分，页面栈中没有空的时候情况
{
//k=nums-1;//最近的数字的优先级
for(j=0;j<nums;j++)//前面的页面中内容赋值到新的新的页面中
{
stack[i][j]=stack[i-1][j];
}
for(j=0;j<nums;j++)
{
f=0;
if(stack[i][j]==numbers[i])
{
f=1;
break;
}
}
if(f==0)//页面中没有，需要替换的情况
{
for(q=0;q<nums;q++)//优先级序列中最大的就是最久未用的，有可能出现后面没有在用过的情况
{
seq[q]=20;
}
for(j=0;j<nums;j++)//寻找新的优先级
{
for(q=i+1;q<20;q++)
{
if(stack[i][j]==numbers[q])
{
seq[j]=q-i;
break;
}
}
}
max=seq[0];
k=0;
for(q=0;q<nums;q++)
{
if(seq[q]>max)
{
max=seq[q];
k=q;
}
}
stack[i][k]=numbers[i];
sum++;
}
else
{
//页面栈中有需要插入的数字，无需变化，替换的优先级也不需要变化
}
}
printf("\n");
printf("OPT Alogrithm：\n");
printShow();
printf("Number of page missing errors：%d\n",sum);
}
int main(int argc,char *argv[]){
printf("Used Replacement Algorithm...\n");
begin();
FIFO();
LRU();
OPT();
return 0;
}
