/*
计算三种缺页中断的缺页数，缺页率和命中率
FIFO,LRU,OPT
*/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
/*
** 默认页表大小为3
*/
#define PAGETABLELENGTH 3
//输出函数，四个参数，缺页数，缺页率和命中率,算法名称
//无返回值
void output( int pageFault, double pageFaultRate, double hitProbability , char *name)
{
printf("\n=====================\n%s:\n",name);
printf("缺页数是: %d\n",pageFault);
printf("缺页率是: %2.2lf%\n",pageFaultRate*100);
printf("命中率是: %2.2lf%\n",hitProbability*100);
}
//判断是否命中
int pageHited(int *arr,int begin, int length, int equNum)
{
for(int i=begin;i<length;++i)
{
if(arr[i]==equNum)
return i;
}
return -1;
}
void arrayInit( int *arr, int length)
{
for(int i=0;i<length;++i)
arr[i] = 0;
}
//FIFO
//参数是一个指针以及数组长度
//无返回参数
//输出，缺页数，缺页率和命中率
void fifo( const int *const arr, int length)
{
int pageTable[PAGETABLELENGTH];
int hitCount = 0;
int firstIn = 0;
int pageCount = 0;
arrayInit(pageTable, PAGETABLELENGTH);
for(int i=0; i< length; ++i)
{
//判断是否命中
int hit = pageHited( pageTable, 0, pageCount, arr[i]);
if(hit!=-1)
{
++hitCount;
}
else
{
//page已经填满
if(pageCount== PAGETABLELENGTH)
{
pageTable[firstIn] = arr[i];
firstIn = (++firstIn)%PAGETABLELENGTH;
}
//pagetable未填满
else
{
pageTable[pageCount] = arr[i];
pageCount++;
}
}
}
output(length-hitCount,(length-hitCount)/(double)length, (double)hitCount/length, "FIFO" );
}
//LRU
//参数是一个指针以及数组长度
//无返回参数
//输出，缺页数，缺页率和命中率
void lru( const int *const arr, int length)
{
int hitCount = 0;
int pageTable[PAGETABLELENGTH];
//记录page元素里最近使用的位置
int pageLastUsed[PAGETABLELENGTH];
int pageCount = 0;
arrayInit(pageTable, PAGETABLELENGTH);
arrayInit(pageLastUsed, PAGETABLELENGTH);
for(int i=0;i<length;++i)
{
int hit = pageHited(pageTable,0,pageCount,arr[i]);
if(hit!=-1)
{
++hitCount;
pageLastUsed[hit] = i;
}
else
{
if(pageCount==PAGETABLELENGTH)
{
int min = 0;
for(int plu = 1; plu<PAGETABLELENGTH; ++plu)
{
min = pageLastUsed[min] < pageLastUsed[plu]?min:plu;
}
pageTable[min] = arr[i];
}
else
{
pageTable[pageCount] = arr[i];
pageLastUsed[pageCount++] = i;
}
}
}
output(length-hitCount,(length-hitCount)/(double)length, (double)hitCount/length ,"LRU");
}
//OPT
//参数是一个指针以及数组长度
//无返回参数
//输出，缺页数，缺页率和命中率
void opt( int *arr, int length)
{
int hitCount = 0;
int pageTable[PAGETABLELENGTH];
int pageFuture[PAGETABLELENGTH];
int pageCount = 0;
arrayInit(pageTable,PAGETABLELENGTH);
arrayInit(pageFuture,PAGETABLELENGTH);
for(int i=0; i<length; ++i)
{
int hit = pageHited(pageTable, 0, pageCount, arr[i]);
if(hit!=-1)
{
++hitCount;
}
else
{
//table 满 ,计算在最近的将来谁不会被用到
if(pageCount == PAGETABLELENGTH)
{
for(int pi=0; pi<pageCount; ++pi)
{
int find = pageHited(arr,i+1,length,pageTable[pi]);
if(find!=-1)
{
pageFuture[pi] = find;
}
else
{
pageFuture[pi] = length+1;
}
}
int max = 0;
for(int pii=1; pii<pageCount; ++pii)
{
max = pageFuture[max] > pageFuture[pii]? max:pii;
}
pageTable[max] = arr[i];
}
//table未满
else
{
pageTable[pageCount++] = arr[i];
}
}
}
output(length-hitCount,(length-hitCount)/(double)length, (double)hitCount/length,"OPT");
}
//参数是一个int型指针，数组长度
//随机生成一个长度为11-20的数组，代表着页的执行顺序,
//数字大小为1-9，随机生成，返回数组head指针
int* productRandomArray( int *length)
{
//随机数种子
srand(int(time(0)));
*length = rand()%10+11;
//数组长度
int *head = (int *)malloc(sizeof(int)*(*length));
if(head ==NULL)
{
printf("malloc error!\n");
return NULL;
}
//数组赋值
for(int i=0;i<(*length);++i)
{
head[i] = rand()%9+1;
}
return head;
}
int main()
{
int length;
int *head;
head = productRandomArray(&length);
if(head == NULL)
return -1;
printf("=====================Table 大小设置为 3 ==========================\n");
printf("====== 实验发现在大多数情况下FIFO 和 LRU 的命中率是一样的 ========\n");
printf("======================实验数据是随机生成的========================\n");
for(int i=0;i<length;i++)
printf("%d ",head[i]);
//fifo
fifo(head,length);
//lru
lru(head, length);
//opt
opt(head, length);
getchar();
getchar();
return 0;
}
