pagereplacemnet.cpp

操作系统实验(进程调度和页面置换算法)的原码和电子书

// PageReplacemnet.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#include "iomanip.h"

bool bPageTableCreated();
bool bDisplay();
bool bDisplayReferenceString();
bool bCreateReferenceString();
bool bIsInMemory(int &iPageNumber);
bool InMemory(int &iPageNumber, int &iPageFrame);
bool OutMemory(int &iPageNumber);
bool bDisplayPageInMemory();
bool bExecuteFIFOAlgorithm(int &iPageFrame);
int GetPageFrameAccordingToPage(int & iPageNumber);

struct PageTable
{
	int iPageTableItemID;
	int iCachingDisabled;
	int iReferenced;
	int iModified;
	int iProtection;
	int iPresentOrAbsent;
    int iPageFrameNumber;
	struct PageTable *next;
};
struct ReferenceString
{
	int iPageNumber;
	struct ReferenceString *next;
};
struct ExecuteList 
{
	int iPageNumber;
	int iReferenceTime;
	struct ExecuteList *next;
};
struct ReferenceString *pReferenceString=NULL;
struct PageTable *pPageTable=NULL;
struct ExecuteList *pExecuteList;
int iPageID=0;
int iReferencedPageID=0;
int iPageTableItemNumber;
int iPageFrameCount;
int iReferencedPageCount=0;
int iCurrentPageFrameNumber=0;

int main(int argc, char* argv[])
{
	bPageTableCreated();
	bCreateReferenceString();
	bExecuteFIFOAlgorithm(iPageFrameCount);
	return 0;
}

bool bPageTableCreated()
{
    int m_iCachingDisabled;
	int m_iProtection;
	struct PageTable *pTemp;
	struct PageTable *pCurrentPageTableItem;
	
	cout<<"Please input the Page Table Item number:";
	cin>>iPageTableItemNumber;
    cout<<endl<<endl;

	for (int i=0;i<iPageTableItemNumber;i++)
	{
		try
		{
		    pTemp=new struct PageTable;
		}
	    catch(...)
		{
		    cout<<"the memory is not enough! Creating Table failed!";
		    return false;
		}
        pTemp->iPageTableItemID=iPageID;
	    cout<<"please input the cachingdisableed bit(0/1):";
	    cin>>m_iCachingDisabled;
        cout<<"please input the protection bit(0/1):";
	    cin>>m_iProtection;
		cout<<endl;
	    
	    pTemp->iCachingDisabled=m_iCachingDisabled;
	    pTemp->iModified=0;
	    pTemp->iPageTableItemID=iPageID;
		pTemp->iPresentOrAbsent=0;
		pTemp->iProtection=m_iProtection;
		pTemp->iPageFrameNumber=-1;//means this page is not in memory now, so no page frame is allocated to it
		pTemp->iReferenced=0;
	
		if(iPageID==0)
		{
			pPageTable=pTemp;
			pCurrentPageTableItem=pTemp;
		    pCurrentPageTableItem->next=NULL;
		}
		else
		{
			pCurrentPageTableItem->next=pTemp;
			pCurrentPageTableItem=pTemp;
		    pCurrentPageTableItem->next=NULL;
		}
		iPageID++;
	}

	bDisplay();
	return true;
}

bool bDisplay()
{
    struct PageTable *pTemp=NULL;
	pTemp=pPageTable;
    if(pTemp==NULL)
		cout<<"No Page Pable Item exists!";
	else 
	{
		cout<<endl;
		cout<<setw(5)<<"Page"<<setw(16)<<"CachingDisabled"<<setw(9)<<"Modified"<<setw(11)<<"Page-Frame"<<setw(15)<<"Present/Absent"<<setw(11)<<"Protection"<<setw(11)<<"Referenced";
		cout<<endl;
		while(pTemp!=NULL)
		{
			cout<<setw(3);
			cout<<pTemp->iPageTableItemID;
	        cout<<setw(16);
			cout<<pTemp->iCachingDisabled;
	        cout<<setw(9);
			cout<<pTemp->iModified;
	        cout<<setw(11);
			cout<<pTemp->iPageFrameNumber;
            cout<<setw(15);
			cout<<pTemp->iPresentOrAbsent;
            cout<<setw(11);
			cout<<pTemp->iProtection;
			cout<<setw(11);
			cout<<pTemp->iReferenced;
			cout<<endl;
			pTemp=pTemp->next;
		}
	}
    cout<<endl;

	return true;
}
bool bCreateReferenceString()
{
	struct ReferenceString *pTemp;
	struct ReferenceString *pCurrent;
	int iCount;
	int iPageNumber;
		
	cout<<"please input the referenced page count:";
	cin>>iCount;
    cout<<endl<<endl;

	for (int i=0;i<iCount;i++)
	{
		try
		{
		    pTemp=new struct ReferenceString;
		}
	    catch(...)
		{
		    cout<<"the memory is not enough! Creating Referenced string failed!";
		    return false;
		}
        
	    iReferencedPageID++;
	    cout<<"please input the Referenced page number:";
	    cin>>iPageNumber;
		while (iPageNumber>iPageTableItemNumber-1)
		{
			cout<<"please input the Referenced page number again:";
	        cin>>iPageNumber;
		}
	 
	    pTemp->iPageNumber=iPageNumber;
		if(iReferencedPageID==1)
		{
			pReferenceString=pTemp;
			pCurrent=pTemp;
		    pCurrent->next=NULL;
		}
		else
		{
			pCurrent->next=pTemp;
			pCurrent=pTemp;
		    pCurrent->next=NULL;
		}
	}
	cout<<endl;
    bDisplayReferenceString();

	return true;
}
bool bDisplayReferenceString()
{
    struct ReferenceString *pTemp=NULL;
	pTemp=pReferenceString;
    
	cout<<"Reference String......:";
	if(pTemp==NULL)
		cout<<"No Reference String exists!";
	else 
	{		
		while(pTemp!=NULL)
		{
			cout<<setw(5);
			cout<<pTemp->iPageNumber;
			pTemp=pTemp->next;
		}
	}
    cout<<endl;
	cout<<endl;
	return true;
}

int bCreatePageFrameNumber()
{
	int iCount;
	cout<<"Please input the page frame number:";
	cin>>iCount;
	iPageFrameCount=iCount;//put the page frame number to viarable iPageFrameNumber
	cout<<endl;
	return iCount;
}
bool bExecuteFIFOAlgorithm(int &iPageFrame)
{
    bCreatePageFrameNumber();//create page frame number
	struct ReferenceString *pRS;
	pRS=pReferenceString;//reference string
	struct ExecuteList *pTemp;
	struct ExecuteList *pCurrent=NULL;
    int iCurrentPageNumber;//current page number
	int iCountInMemory=0;
	int iTemp;
	
    while(pRS!=NULL)
	{	
		iCurrentPageNumber=pRS->iPageNumber;
		iReferencedPageCount++;
	    if(bIsInMemory(iCurrentPageNumber))//the page is in the memory now
		{
			cout<<"the page is in the memory now!";
			cout<<"[";
			cout<<iCurrentPageNumber;
			cout<<"]";
			cout<<endl;
		}
	    else//the page is not in the memory now 
		{
			if (iCountInMemory<iPageFrame)//if the page frames is not full
			{
				try
				{
					pTemp=new struct ExecuteList;
				}
	            catch(...)
				{
					cout<<"the memory is not enough! failed!";
		            return false;
				}
			    if(iCountInMemory==0)
				{
					pExecuteList=pTemp;
			        pCurrent=pTemp;
				    pCurrent->iPageNumber=iCurrentPageNumber;
				    pCurrent->iReferenceTime=iReferencedPageCount;
		            pCurrent->next=NULL;
				}
		        else
				{
					pCurrent->next=pTemp;
			        pCurrent=pTemp;
				    pCurrent->iPageNumber=iCurrentPageNumber;
				    pCurrent->iReferenceTime=iReferencedPageCount;
		            pCurrent->next=NULL;
				}
			    iCountInMemory++;
				InMemory(iCurrentPageNumber,iCurrentPageFrameNumber);//get in the memory
				iCurrentPageFrameNumber++;
			}
		    else//if the page frames is full
			{
				pCurrent=pExecuteList;
			    int iOutPageNumber=pCurrent->iPageNumber;
			    while(pCurrent!=NULL&&pCurrent->next!=NULL)
				{
				    pCurrent->iPageNumber=pCurrent->next->iPageNumber;
				    pCurrent->iReferenceTime=pCurrent->next->iReferenceTime;
			 	    pCurrent=pCurrent->next;
				}
			    pCurrent->iPageNumber=iCurrentPageNumber;
			    pCurrent->iReferenceTime=iReferencedPageCount;
			   				
				iTemp=GetPageFrameAccordingToPage(iOutPageNumber);
                InMemory(iCurrentPageNumber,iTemp);//get in the memory
                OutMemory(iOutPageNumber);//out of the memory
			}
			iCurrentPageNumber++;
		}
	    pRS=pRS->next;
	    bDisplayPageInMemory();
        bDisplay();
    }
	return true;
}
bool bIsInMemory(int &iPageNumber)//is the page in the memory
{
	struct PageTable *pPT;
	pPT=pPageTable;
	int iID;
    int iPresent;
	while(pPT!=NULL)
	{
		iID=pPT->iPageTableItemID;
		if (iID==iPageNumber)
		{
			iPresent=pPT->iPresentOrAbsent;
		    break;
		}
		pPT=pPT->next;
	}
	if (iPresent==1)
		return true;
	else
		return false;
}
bool InMemory(int &iPageNumber, int &iPageFrame)//a page get in the memory
{
	struct PageTable *pTemp;
	pTemp=pPageTable;
	while (pTemp!=NULL)
	{
		if (pTemp->iPageTableItemID==iPageNumber)
		{
			pTemp->iPresentOrAbsent=1;
			pTemp->iPageFrameNumber=iPageFrame;
			break;
		}
		pTemp=pTemp->next;
	}
	return true;
}
bool OutMemory(int &iPageNumber)//a page get out of the memory
{
	struct PageTable *pTemp;
	pTemp=pPageTable;
	while (pTemp!=NULL)
	{
		if (pTemp->iPageTableItemID==iPageNumber)
		{
			pTemp->iPresentOrAbsent=0;
			pTemp->iPageFrameNumber=-1;
			break;
		}
		pTemp=pTemp->next;
	}
	return true;
}
bool bDisplayPageInMemory()//display the pages in the memory
{
	struct  ExecuteList *pTemp=NULL;
	pTemp=pExecuteList;
    
	cout<<"Page in memmory now......:";
	if(pTemp==NULL)
		cout<<"No ReferenceString exists!";
	else 
	{		
		while(pTemp!=NULL)
		{
			cout<<setw(5);
			cout<<pTemp->iPageNumber;
			pTemp=pTemp->next;
		}
	}
    cout<<endl;
	return true;
}

int GetPageFrameAccordingToPage(int &iPageNumber)
{
	struct PageTable *pTemp;
	pTemp=pPageTable;
	int iReturn;
	while (pTemp!=NULL)
	{
		if (pTemp->iPageTableItemID==iPageNumber)
		{
			iReturn=pTemp->iPageFrameNumber;
			break;
		}
		pTemp=pTemp->next;
	}
	return iReturn;
}