操作系统课程设计任务书-

操作系统课程设计任务书1安徽理工大学计算机系软件教研室管建军－－存储器管理设计1设计目的2安徽理工大学计算机系软件教研室管建军⑴理解内存页面调度的机理。⑵掌握几种理论页面置换算法的实现方法。⑶了解HASH表数据结构的使用。⑷通过课程设计比较各种调度算法的优劣。页面置换算法是虚拟存储管理实现的关键，通过本次课程设计理解内存页面调度的机制，在模拟实现FIFO、LRU、

NRU和OPT几种经典页面置换算法的基础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。2准备知识3安徽理工大学计算机系软件教研室管建军基本概念⑴C(或C++)、指针、结构体(类)⑵HASH(哈希)表查找方式⑶操作系统相关内存交换知识⑷用到的Linux函数int

getpid()void

srand(int

a)int

rand()获得当前进程的id以a为种子产生随机数根据前面的种子，返回一个随机数3设计内容设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。⑴先进先出的算法(FIFO)⑵最近最少使用算法(LRU)⑶最佳淘汰算法(OPT)⑷最少访问页面算法(LRU)⑸最近最不经常使用算法(NUR)命中率＝(1－页面失效次数)/页地址流长度设计程序时先用Srand()和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。4安徽理工大学计算机系软件教研室管建军4设计指导5安徽理工大学计算机系软件教研室管建军拥有页面交换机制的操作系统总是把当前进程急需处理的部分页面换入到内存中，而把更多暂时不需要处理的页面放置到外存中。由于进程需要处理的页面顺序不同，因此必须在内存与外存之间进行页面交换，交换算法也就应运而生。本设计并没有进入系统空间对实际进程进行控制，而是在用户空间用线性表的连续存储方式对进程页面交换进行模拟。1

FIFO页面置换算法6安徽理工大学计算机系软件教研室管建军2

LRU页面置换算法7安徽理工大学计算机系软件教研室管建军3

NUR页面置换算法8安徽理工大学计算机系软件教研室管建军4

OPT页面置换算法9安徽理工大学计算机系软件教研室管建军5参考源程序代码#ifndef

_PAGE_H#define

_PAGE_Hclass

cpage

{public:int

m_nPageNumber,m_nPageFaceNumber,m_nCounter,m_nTime;};#endif10安徽理工大学计算机系软件教研室管建军#ifndef

_PAGECONTROL_H#define

_PAGECONTROL_Hclass

CpageControl

{public:intm_nPageNumber,m_nPageFaceNumber;class

CPageControl

*m_pNext;};#endif11安徽理工大学计算机系软件教研室管建军#ifndef

_MEMORY_H#define

_MEMORY_Hclass

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);12安徽理工大学计算机系软件教研室管建军private:13安徽理工大学计算机系软件教研室管建军vector<CPage>

_vDiscPages;vector<CPageControl>_vMemoryPages;CPageControl

*_pFreepf_head,*_pBusypf_head,

*_pBusypf_tail;vector<int>_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);14安徽理工大学计算机系软件教研室管建军nRand=rand()%32767;S=(float)319*nRand/32767+1;for(i=0;i<TOTAL_INSTRUCTION;i+=4)

{_vMain[i]=S;_vMain[i+1]=_vMain[i]+1;nRand=rand()%32767;_vMain[i+2]=(float)_vMain[i]*nRand/32767;_vMain[i+3]=_vMain[i+2]+1;nRand=rand()%32767;15安徽理工大学计算机系软件教研室管建军S=(float)nRand

*

(318-_vMain[i+2])/32767+_vMain[i+2]+2;}for(i=0;i<TOTAL_INSTRUCTION;i++)

{_vPage[i]=_vMain[i]/10;_vOffset[i]=_vMain[i]%10;_vPage[i]%=32;}}16安徽理工大学计算机系软件教研室管建军{17安徽理工大学计算机系软件教研室管建军void

CMemory::initialize(const

int

nTotal_pf){int

ix;_nDiseffect=0;for(ix=0;ix<_vDiscPages.size();ix++)_vDiscPages[ix].m_nPageNumber=ix;_vDiscPages[ix].m_nPageFaceNumber=INVALID;_vDiscPages[ix].m_nCounter=0;_vDiscPages[ix].m_nTime=-1;{}for(ix=1;ix<nTotal_pf;ix++)_vMemoryPages[ix-1].m_pNext=&_vMemoryPages[ix];_vMemoryPages[ix-1].m_nPageFaceNumber=ix-1;}_vMemoryPages[nTotal_pf-1].m_pNext=NULL;_vMemoryPages[nTotal_pf-1].m_nPageFaceNumber=nTotal_pf-1;_pFreepf_head=&_vMemoryPages[0];}18安徽理工大学计算机系软件教研室管建军void

CMemory::FIFO(const

int

nTotal_pf)

{int

i;CPageControl

*p;initialize(nTotal_pf);_pBusypf_head=_pBusypf_tail=NULL;for(i=0;i<TOTAL_INSTRUCTION;i++){if(_vDiscPages[_vPage[i]].m_nPageFaceNumber==INVALID)

{19安徽理工大学计算机系软件教研室管建军//无空闲页面_nDiseffect+=1;if(_pFreepf_head==NULL){p=_pBusypf_head->m_pNext;_vDiscPages[_pBusypf_head->m_nPageNumber].m_nPageFaceNumber=INVALID;_pFreepf_head=_pBusypf_head;_pFreepf_head->m_pNext=NULL;_pBusypf_head=p;}p=_pFreepf_head->m_pNext;_pFreepf_head->m_pNext=NULL;_pFreepf_head->m_nPageNumber=_vPage[i];_vDiscPages[_vPage[i]].m_nPageFaceNumber=_pFreepf_head->m_nPageFaceNumber;if(_pBusypf_tail==NULL)_pBusypf_head=_pBusypf_tail=_pFreepf_head;20安徽理工大学计算机系软件教研室管建军else{_pBusypf_tail->m_pNext=_pFreepf_head;_pBusypf_tail=_pFreepf_head;}_pFreepf_head=p;}}cout<<"FIFO:

"<<1-(float)_nDiseffect/320;}void

CMemory::LRU(const

int

nTotal_pf)

{int

i,j,nMin,minj,nPresentTime(0);initialize(nTotal_pf);21安徽理工大学计算机系软件教研室管建军for(i=0;i<TOTAL_INSTRUCTION;i++)

{22安徽理工大学计算机系软件教研室管建军if(_vDiscPages[_vPage[i]].m_nPageFaceNumber==INVALID){_nDiseffect++;{if(_pFreepf_head==NULL)nMin=32767;for(j=0;j<TOTAL_VP;j++)//得到最近最少使用的页面的页号//循环结束后,iMin表示最近最少使用页面的访问次数;minj表示需要换出的页号if(nMin>_vDiscPages[j].m_nTime&&_vDiscPages[j].m_nPageFaceNumber!=INVALID){

nMin=_vDiscPages[j].m_nTime;minj=j;}_pFreepf_head=23安徽理工大学计算机系软件教研室管建军&_vMemoryPages[_vDiscPages[minj].m_nPageFaceNumber];_vDiscPages[minj].m_nPageFaceNumber=INVALID;_vDiscPages[minj].m_nTime=-1;_pFreepf_head->m_pNext=NULL;}_vDiscPages[_vPage[i]].m_nPageFaceNumber=_pFreepf_head->m_nPageFaceNumber;_vDiscPages[_vPage[i]].m_nTime=nPresentTime;_pFreepf_head=_pFreepf_head->m_pNext;}else24安徽理工大学计算机系软件教研室管建军_vDiscPages[_vPage[i]].m_nTime=nPresentTime;nPresentTime++;}cout<<"LRU:

"<<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;for(i=0;i<TOTAL_INSTRUCTION;i++)

{25安徽理工大学计算机系软件教研室管建军if(_vDiscPages[_vPage[i]].m_nPageFaceNumber==INVALID)

{{_nDiseffect++;if(_pFreepf_head==NULL)bCont_flag=true;nOld_DiscPage=nDiscPage;while(bCont_flag)

{if(_vDiscPages[nDiscPage].m_nCounter==0&&_vDiscPages[nDiscPage].m_nPageFaceNumber!=INVALID)bCont_flag=false;else

{nDiscPage++;if(nDiscPage==TOTAL_VP)

nDiscPage=0;if(nDiscPage==nOld_DiscPage)for(j=0;j<TOTAL_VP;j++)26安徽理工大学计算机系软件教研室管建军_vDiscPages[j].m_nCounter=0;}}_pFreepf_head=&_vMemoryPages[_vDiscPages[nDiscPage].m_nPageFaceNumber];_vDiscPages[nDiscPage].m_nPageFaceNumber=INVALID;_pFreepf_head->m_pNext=NULL;}_vDiscPages[_vPage[i]].m_nPageFaceNumber=_pFreepf_head->m_nPageFaceNumber;_pFreepf_head=_pFreepf_head->m_pNext;}else_vDiscPages[_vPage[i]].m_nCounter=1;if(i%CLEAR_PERIOD==0)for(j=0;j<TOTAL_VP;j++)_vDiscPages[j].m_nCounter=0;}27安徽理工大学计算机系软件教研室管建军cout<<"NUR:"<<1-(float)_nDiseffect/320;}28安徽理工大学计算机系软件教研室管建军void

CMemory::OPT(const

int

nTotal_pf){int

i,j,max,maxpage,nDistance,vDistance[TOTAL_VP];initialize(nTotal_pf);for(i=0;i<TOTAL_INSTRUCTION;i++)

{if(_vDiscPages[_vPage[i]].m_nPageFaceNumber==INVALID){

_nDiseffect++;if(_pFreepf_head==NULL)

{for(j=0;j<TOTAL_VP;j++)if(_vDiscPages[j].m_nPageFaceNumber!=INVALID)elsevDistance[j]=0;nDistance=1;for(j=i+1;j<TOTAL_INSTRUCTION;j++)

{29安徽理工大学计算机系软件教研室管建军if((_vDiscPages[_vPage[j]].m_nPageFaceNumber!=INVALID)&&(vDistance[_vPage[j]]==32767))vDistance[_vPage[j]]=nDistance;nDistance++;}max

=-1;for(j=0;j<TOTAL_VP;j++)if(max<vDistance[j]){max=vDistance[j];maxpage=j;}_pFreepf_head=&_vMemoryPages[_vDiscPages[maxpage].m_nPageFaceNumber];_pFreepf_head->m_pNext=NULL;30安徽理工大学计算机系软件教研室管建军_vDiscPages[maxpage].m_nPageFaceN