第4章 存储器管理实验

1、第四章 存储器管理实验 课程名称：操作系统实验 授课教师：王铁军 电子邮箱： 理解内存页面调度的机理，掌握几种理论调度算法实现，并通过实验比较各种调度算法的优劣。此外通过实验了解HASH表数据结构的使用。 原理简述 算法实现提示 初始化。设置两个数组pageap和pagecontrolpp分别表示进程页面数和内存分配的页面数，并产生一个的随机数序列maintotal_instruction（当然这个序列由page的下标随机构成），表示待处理的进程页面顺序，diseffect置零。看main中是否有下一个元素，有就由main中获取该页面下标，并转到；没有，就转到。 如果该page业已在内存中，就

2、转到；否则就到，同时未命中的diseffect加1。观察pagecontrol是否占满，如果占满需将使用队列（中建立的）中最先进入的（就是队列第一个单元）pagecontrol单元“清干净”，同时将对应的page单元置为“不在内存中”。将该page与pagecontrol建立关系（可以改变pagecontrol的标示位，也可以采用指针连接，总之至少要使对应的pagecontrol单元包含两个信息：一是它被使用了，另外是哪个page单元使用的；page单元包含两个信息：对应的pagecontrol单元号、本page单元已在内存中）； 将用到的pagecontrol置入使用队列（这里的队列当然是一

3、种先进先出的数据结构了，而不是泛指），返回； 显示命中率 ：%100_1ninstructiototaldiseffectPage.h#ifndef _PAGE_H#define _PAGE_Hclass cpage public:int m_nPageNumber,m_nPageFaceNumber,m_nCounter,m_nTime;#endifPageControl.h#ifndef _PAGECONTROL_H#define _PAGECONTROL_Hclass CpageControl public:int m_nPageNumber, m_nPageFaceNumber;cla

4、ss CPageControl *m_pNext;#endifMemory.h#ifndef _MEMORY_H#define _MEMORY_H class CMemory public:CMemory();void initialize(const int nTotal_pf);void FIFO(const int nTotal_pf);void LRU(const int nTotal_pf);void NUR(const int nTotal_pf);void OPT(const int nTotal_pf);private:vector _vDiscPages;vector _vM

5、emoryPages;CPageControl *_pFreepf_head, *_pBusypf_head, *_pBusypf_tail;vector _vMain,_vPage,_vOffset;int _nDiseffect; CMemory:CMemory(): _vDiscPages(TOTAL_VP), _vMemoryPages(TOTAL_VP), _vMain(TOTAL_INSTRUCTION), _vPage(TOTAL_INSTRUCTION), _vOffset(TOTAL_INSTRUCTION) int S,i,nRand;srand(getpid()*10);

6、nRand=rand()%32767;S=(float)319*nRand/32767+1;for(i=0;iTOTAL_INSTRUCTION;i+=4) _vMaini=S;_vMaini+1=_vMaini+1;nRand=rand()%32767;_vMaini+2=(float)_vMaini * nRand/32767;_vMaini+3=_vMaini+2+1;nRand=rand()%32767;S=(float)nRand * (318-_vMaini+2)/32767+_vMaini+2+2;for(i=0;iTOTAL_INSTRUCTION;i+) _vPagei=_v

7、Maini/10;_vOffseti=_vMaini%10;_vPagei%=32;Memory.hvoid CMemory:initialize(const int nTotal_pf)int ix;_nDiseffect=0;for(ix=0;ix_vDiscPages.size();ix+) _vDiscPagesix.m_nPageNumber=ix;_vDiscPagesix.m_nPageFaceNumber=INVALID;_vDiscPagesix.m_nCounter=0;_vDiscPagesix.m_nTime=-1;for(ix=1;ixnTotal_pf;ix+) _

8、vMemoryPagesix-1.m_pNext = &_vMemoryPagesix;_vMemoryPagesix-1.m_nPageFaceNumber=ix-1;Memory.h_vMemoryPagesnTotal_pf-1.m_pNext=NULL;_vMemoryPagesnTotal_pf-1.m_nPageFaceNumber = nTotal_pf-1;_pFreepf_head=&_vMemoryPages0; void CMemory:FIFO(const int nTotal_pf) int i;CPageControl *p;initialize(n

9、Total_pf);_pBusypf_head=_pBusypf_tail=NULL;for(i=0;im_pNext; _vDiscPages_pBusypf_head-m_nPageNumber.m_nPageFaceNumber = INVALID; _pFreepf_head=_pBusypf_head; _pFreepf_head-m_pNext=NULL; _pBusypf_head=p;Memory.hp=_pFreepf_head-m_pNext;_pFreepf_head-m_pNext=NULL;_pFreepf_head-m_nPageNumber=_vPagei;_vD

10、iscPages_vPagei.m_nPageFaceNumber = _pFreepf_head-m_nPageFaceNumber;if(_pBusypf_tail=NULL)_pBusypf_head=_pBusypf_tail=_pFreepf_head;else _pBusypf_tail-m_pNext=_pFreepf_head; _pBusypf_tail=_pFreepf_head;Memory.h_pFreepf_head=p; coutFIFO: 1-(float)_nDiseffect/320; void CMemory:LRU(const int nTotal_pf)

11、 int i,j,nMin,minj,nPresentTime(0); initialize(nTotal_pf);Memory.hfor(i=0;iTOTAL_INSTRUCTION;i+) if(_vDiscPages_vPagei.m_nPageFaceNumber = INVALID) _nDiseffect+; if(_pFreepf_head=NULL) nMin=32767;for(j=0;j_vDiscPagesj.m_nTime &_vDiscPagesj.m_nPageFaceNumber!=INVALID) nMin=_vDiscPagesj.m_nTime; m

12、inj=j;Memory.h_pFreepf_head=&_vMemoryPages_vDiscPagesminj.m_nPageFaceNumber;_vDiscPagesminj.m_nPageFaceNumber=INVALID;_vDiscPagesminj.m_nTime=-1;_pFreepf_head-m_pNext=NULL; _vDiscPages_vPagei.m_nPageFaceNumber= _pFreepf_head-m_nPageFaceNumber;_vDiscPages_vPagei.m_nTime=nPresentTime;_pFreepf_head

13、=_pFreepf_head-m_pNext;Memory.helse_vDiscPages_vPagei.m_nTime=nPresentTime;nPresentTime+; coutLRU: 1-(float)_nDiseffect/320;void CMemory:NUR(const int nTotal_pf) int i,j,nDiscPage,nOld_DiscPage; bool bCont_flag; initialize(nTotal_pf); nDiscPage=0;Memory.hfor(i=0;iTOTAL_INSTRUCTION;i+) if(_vDiscPages

14、_vPagei.m_nPageFaceNumber =INVALID) _nDiseffect+; if(_pFreepf_head=NULL) bCont_flag=true; nOld_DiscPage=nDiscPage; while(bCont_flag)if(_vDiscPagesnDiscPage.m_nCounter=0&_vDiscPagesnDiscPage.m_nPageFaceNumber!=INVALID) bCont_flag=false;Memory.helse nDiscPage+; if(nDiscPage=TOTAL_VP) nDiscPage=0;

15、if(nDiscPage=nOld_DiscPage) for(j=0;jm_pNext=NULL; _vDiscPages_vPagei.m_nPageFaceNumber=_pFreepf_head-m_nPageFaceNumber; _pFreepf_head=_pFreepf_head-m_pNext;else _vDiscPages_vPagei.m_nCounter=1; if(i%CLEAR_PERIOD=0) for(j=0;jTOTAL_VP;j+) _vDiscPagesj.m_nCounter=0; Memory.h coutNUR:1-(float)_nDiseffe

16、ct/320; void CMemory:OPT(const int nTotal_pf) int i,j,max,maxpage,nDistance,vDistanceTOTAL_VP; initialize(nTotal_pf); for(i=0;iTOTAL_INSTRUCTION;i+) if(_vDiscPages_vPagei.m_nPageFaceNumber=INVALID) _nDiseffect+; if(_pFreepf_head=NULL) for(j=0;jTOTAL_VP;j+) if(_vDiscPagesj.m_nPageFaceNumber!=INVALID)

17、 vDistancej=32767;else vDistancej=0;Memory.hnDistance=1; for(j=i+1;jTOTAL_INSTRUCTION;j+) if(_vDiscPages_vPagej.m_nPageFaceNumber!=INVALID)& (vDistance_vPagej=32767) vDistance_vPagej=nDistance; nDistance+; max=-1; for(j=0;jTOTAL_VP;j+)if(maxm_pNext=NULL; _vDiscPagesmaxpage.m_nPageFaceNumber=INVALID; _vDiscPages_vPagei.m_nPageFaceNumber=_pFreepf_head-m_nPageFaceNumber; _pFreepf_head=_pFreepf_head-m_pNext; coutOPT:1-(float)_nDiseffect/320;#endifmain.cpp#include #include #include #include #include #include using namespace std;#define INVALID -1const int TOTAL_INSTRUCTION(320);const int TO