#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <time.h>
#ifndef _UNISTD_H
#define _UNISTD_H
#include <io.H>
#include <process.H>
#endif
#define TRUE 1
#define FALSE 0
#define INVALIDPAGE -1
/*total simulation vitual pages */
#define TOTALVITUALPAGE 32
/*each arPage has 10 instructions */
#define TOTALINST (10*TOTALVITUALPAGE)
/*page structure*/
typedef struct _PageInfo{
int nPageNo; //page index no.
int nPageFrameNo; //page frame no.
int nCount; //visit times per unit
int nTimeLastVisit; //last visit time
} PAGEINFO;
/*page contril structure*/
typedef struct _PageControl {
int nPageNo; //page index no.
int nPageFrameNo; //page frame no.
struct _PageControl *pNext; //the next page control
}PAGECONTROL;
PAGEINFO g_stPageInfo[TOTALVITUALPAGE]; //page structure array
PAGECONTROL g_stPageControl[TOTALVITUALPAGE]; //virtual memory page control
int arInstruction[TOTALINST]; //Random instruction stream
void GenerateInstruction(int* pnInstruction)
{
int i, s;
printf("\n------------Generate The Random Instruction Stream-----------\n");
srand(time(NULL)); /*initialize the random seed"*/
s = rand() * (TOTALINST - 1) / (RAND_MAX);
for (i = 0; i < TOTALINST; i += 4) {
/*generation the instruction queue ,first random */
pnInstruction[i] = s;
/*the next is ordinal*/
pnInstruction[i+1] = pnInstruction[i] + 1;
/*the next is before this instruction */
pnInstruction[i+2] = pnInstruction[i] * rand() / (RAND_MAX);
/*the next is ordinal*/
pnInstruction[i+3] = pnInstruction[i+2] + 1;
s = rand() * (TOTALINST - 1 - pnInstruction[i+2]) / (RAND_MAX) + pnInstruction[i+2];
printf("%6d%6d%6d%6d\n", pnInstruction[i], pnInstruction[i+1], pnInstruction[i+2], pnInstruction[i+3]);
}
printf("--------------------------------------\n");
}
//initialize the page structure and virtual memory struct*/
int Initialize(int nTotalPageFrame)
{
int i;
for(i = 0; i < TOTALVITUALPAGE; i++) {
g_stPageInfo[i].nPageNo = i;
g_stPageInfo[i].nPageFrameNo = INVALIDPAGE;
g_stPageInfo[i].nCount = 0;
g_stPageInfo[i].nTimeLastVisit = -1;
}
for(i = 0; i < nTotalPageFrame - 1; i++) {
g_stPageControl[i].nPageFrameNo = i;
g_stPageControl[i].pNext = &g_stPageControl[i+1];
}
/*i == nTotalPageFrame - 1 */
g_stPageControl[i].pNext = NULL;
g_stPageControl[i].nPageFrameNo = i;
return 0;
}
float LRU (int nTotalPageFrame)
{
/*the min visited time, and the reciprocal page no*/
int nMinVisitTime, nMinTimePageNo;
int i, j, nPageNo;
int nCurTime = 0, nMissPageCount = 0;
/*pointer to free pages pFreePageFramesHeadAlways, busy pages pFreePageFramesHeadAlways, and busy pages tail*/
PAGECONTROL *pFreePageFramesHead;
/*at the beginning, the free pFreePageFramesHeadAlways is the page pFreePageFramesHeadAlways*/
pFreePageFramesHead = g_stPageControl;
Initialize(nTotalPageFrame);
for(i = 0; i < TOTALINST; i++) {
nPageNo = arInstruction[i]/10;
if(g_stPageInfo[nPageNo].nPageFrameNo == INVALIDPAGE) {
/*the page is invalid*/
nMissPageCount++;
if(pFreePageFramesHead == NULL) {
/*no free pages, nBeSwap*/
nMinTimePageNo = -1;
nMinVisitTime = 100000;
/*find the page which has the min visit time*/
for(j = 0; j < TOTALVITUALPAGE; j++) {
if (nMinVisitTime > g_stPageInfo[j].nTimeLastVisit &&
g_stPageInfo[j].nPageFrameNo != INVALIDPAGE) {
nMinVisitTime = g_stPageInfo[j].nTimeLastVisit;
nMinTimePageNo = j;
}
}
if(nMinTimePageNo != -1) {
/*find it, and free it!*/
pFreePageFramesHead = &g_stPageControl[g_stPageInfo[nMinTimePageNo].nPageFrameNo];
g_stPageInfo[nMinTimePageNo].nPageFrameNo = INVALIDPAGE;
g_stPageInfo[nMinTimePageNo].nTimeLastVisit = -1;
pFreePageFramesHead->pNext = NULL;
}
else {
/* an error occur*/
}
}
/*nBeSwap the page to the main storage, and decrease the free pages*/
g_stPageInfo[nPageNo].nPageFrameNo = pFreePageFramesHead->nPageFrameNo;
g_stPageInfo[nPageNo].nTimeLastVisit = nCurTime;
pFreePageFramesHead = pFreePageFramesHead->pNext;
}
else {
/*refresh the page visit time*/
g_stPageInfo[nPageNo].nTimeLastVisit = nCurTime;
}
nCurTime++; /*increase the current system time*/
}
return (1 - (float)nMissPageCount / 320);
}
float OPT(int nTotalPageFrame)
{
int i, j, nDisCount, nPageNo;
/* the max distanse of lastest visit , and it's page no*/
int nMaxDistanse, nMaxDisPage;
/* the array of last twice visit time margin*/
int arnDist[TOTALVITUALPAGE];
int nMissPageCount = 0;
PAGECONTROL *pFreePageFramesHead;
Initialize(nTotalPageFrame);
pFreePageFramesHead = g_stPageControl;
for(i = 0; i < TOTALINST; i++) {
nPageNo = arInstruction[i]/10;
if(g_stPageInfo[nPageNo].nPageFrameNo == INVALIDPAGE) {
nMissPageCount++;
if(pFreePageFramesHead == NULL) {
for(j = 0; j < TOTALVITUALPAGE; j++) {
/*reassign the distanse of each page*/
arnDist[j] = (g_stPageInfo[j].nPageFrameNo != INVALIDPAGE) ? 100000 : 0;
}
nDisCount = 1;
for(j = i + 1; j < TOTALINST; j++) {
/*calculate from the next instruction*/
int nPageTmp = arInstruction[j]/10;
/* the page is in memory, and it's the next visit page*/
if(g_stPageInfo[nPageTmp].nPageFrameNo != INVALIDPAGE && g_stPageInfo[nPageTmp].nCount == 0) {
arnDist[nPageTmp] = nDisCount; /*change the distance*/
g_stPageInfo[nPageTmp].nCount = 1;
}
nDisCount++;
}
/*fine the max distance and it's page*/
nMaxDistanse = -1;
for(j = 0; j < TOTALVITUALPAGE; j++) {
g_stPageInfo[j].nCount = 0;
if(nMaxDistanse < arnDist[j]) {
nMaxDistanse = arnDist[j];
nMaxDisPage = j;
}
}
/*free the virtual page, wait to nBeSwap*/
pFreePageFramesHead = &g_stPageControl[g_stPageInfo[nMaxDisPage].nPageFrameNo];
pFreePageFramesHead->pNext = NULL;
g_stPageInfo[nMaxDisPage].nPageFrameNo = INVALIDPAGE;
}
g_stPageInfo[nPageNo].nPageFrameNo = pFreePageFramesHead->nPageFrameNo;
pFreePageFramesHead = pFreePageFramesHead->pNext;
}
}
return (1 - (float)nMissPageCount / 320);
}
float FIFO(int nTotalPageFrame)
{
int i, nBeSwap = 0, nPageNo;
int nMissPageCount = 0;
int nUsedBitmap[TOTALVITUALPAGE];
PAGECONTROL *pFreePageFramesHead, *pFreePageFramesNext, *pFreePageFramesHeadAlways;
Initialize(nTotalPageFrame);
pFreePageFramesHeadAlways = pFreePageFramesNext = pFreePageFramesHead = g_stPageControl;
for(i = 0; i < TOTALVITUALPAGE; i++) {
nUsedBitmap[i] = 0;
}
for(i = 0; i < TOTALINST; i++) {
nPageNo = arInstruction[i]/10;
if (g_stPageInfo[nPageNo].nPageFrameNo == INVALIDPAGE) {
nMissPageCount++;
if(pFreePageFramesHead == NULL) {
while(nUsedBitmap[pFreePageFramesNext->nPageFrameNo] == 1) {
nUsedBitmap[pFreePageFramesNext->nPageFrameNo] = 0;
pFreePageFramesNext = pFreePageFramesNext->pNext;
if(pFreePageFramesNext == NULL) {
pFreePageFramesNext = pFreePageFramesHeadAlways;
}
}
/*swap the page*/
g_stPageInfo[pFreePa
评论0