某学院操作系统课程设计报告(存储管理实验)

1、存储管理实验 城院03软件工程（1）班第一组指导老师：古新生（教授）组长：冯xx 学号：20034931104组员：聂xx 学号：20034931108陈xx 学号：20034931111林xx 学号：20034931113叶xx 学号：20034931115秦xx 学号：20034931121提交日期：2005年5月1日存储管理内存页面调度算法比较【实验目的】 理解内存页面调度的机理，掌握几种理论调度算法实现，并通过实验比较各种调度算法的优劣。此外通过实验了解hash表数据结构的使用。【准备知识】1 c+。指针、结构体（类）。2 据结构hash表查找方式。3 作系统相关内存交换知识。4可能用

2、到的几个linux函数： int getpid() /获得当前进程的id void srand(int a) /以a为种子，为后面产生随机数作准备 int rand() /根据前面的种子，返回一个随机数【实验内容】对比几种算法的命中率。1先进先出的算法。fifo（first in first out）2最近最少使用的算法。lru（least recently used）3最近未使用算法。nur（never used recently）4最佳置换算法。opt（optimal replacement）【实验指导】 拥有页面交换机制的操作系统总是把当前进程中急需处理的部分页面换入到内存当中，而把更多

3、暂时不需处理的页面放置在外存当中，由于进程需要处理页面的顺序不同，而需要在内存与外存之间进行页面交换，交换算法也就应运而生。本实验并没有进入系统空间对实际进程页面进行控制，而是在用户空间用线性表的连续存储方式对进程页面交换进行的模拟。一fifo1原理简述：（1）在分配内存页面数（ap）小于进程页面数（pp）时，当然是最先的ap个页面放入内存；（2）这时有需要处理新的页面，则将原理在内存中的ap个页面中最先进入的调出（是以称为fifo），然后放入新页面；（3）以后如果有新页面需要调入，按（2）之规则进行。算法特点：所使用的内存页面构成一个队列。2图表描述：假设某个进程在硬盘上被化为5个页面（pp

4、=5），以1、2、3、4、5分别表示，而下面是处理机调用它们的顺序（这取决于进程本身）：1、4、2、5、3、3、2、4、2、5而内存可以控制的页面数为3（ap3），那么在使用fifo算法时，这3个页面的内存使用情况应该是这样的：队列第1位1425333425队列第2位142555342队列第3位14222534页面5进入，而最先进入的页面1被调出页面3进入，而此时3个页面中最先进入的页面4被调出虽然有页面需要处理，但是页面本身以在内存中，不需再调入了图 11 不难看出本例共换入页面8次，diseffect=8。3算法实现提示：要得到“命中率”，必然应该有一个常量total_instructio

5、n记录页面总共使用次数；此外需要一个变量记录总共换入页面的次数（需要换出页面，总是因为没有命中而产生的）diseffect。利用公式可以得到命中率。 初始化。设置两个数组pageap和pagecontrolpp分别表示进程页面数和内存分配的页面数，并产生一个的随机数序列maintotal_instruction（当然这个序列由page的下标随机构成），表示待处理的进程页面顺序，diseffect置零。 看main中是否有下一个元素，有就由main中获取该页面下标，并转到；没有，就转到。 如果该page业已在内存中，就转到；否则就到，同时未命中的diseffect加1。 观察pagecontro

6、l是否占满，如果占满需将使用队列（中建立的）中最先进入的（就是队列第一个单元）pagecontrol单元“清干净”，同时将对应的page单元置为“不在内存中”。 将该page与pagecontrol建立关系（可以改变pagecontrol的标示位，也可以采用指针连接，总之至少要使对应的pagecontrol单元包含两个信息：一是它被使用了，另外是哪个page单元使用的；page单元包含两个信息：对应的pagecontrol单元号、本page单元已在内存中）； 将用到的pagecontrol置入使用队列（这里的队列当然是一种先进先出的数据结构了，而不是泛指），返回； 显示，完成。二lru1原理简

7、述： 在分配内存页面数（ap）小于进程页面数（pp）时，当然是最先的ap个页面放入内存； 然则当需要调页面进入内存，而当前分配的内存页面全部不空闲时，选择其中最长时间没有用到那个页面调出，以空出内存来放置新调入的页面（是以称为lru）；算法特点：每个页面都有属性表示有多长时间未被cpu使用的信息。2图表描述： 为了便于比较学习，例子和前面的一样。某进程在硬盘上被划为5个页面，用1、2、3、4、5表示，而处理机处理它们的顺序为：1、4、2、5、3、3、2、4、2、5而内存可以控制的页面数为3（ap3），那么在使用fifo算法时，这3个页面的内存使用情况应该是这样的：最近1步使用142533242

8、5最近2步使用142553242虽然页面的位置发生改变，但是没有发生页面交换最近3步使用14225334图 21 不难看出页面换入共7次，diseffect=7。3算法实现提示：与前述算法一样，只有先得到diseffect才能获得最终的“命中率”。 初始化。主要是进程页面page和分配的内存页面pagecontrol，同时产生随机序列main，diseffect置零。 看序列main是否有下一个元素，如果有就从main获取该page的下标，并转到；如果没有就转到。 如果该page单元在内存中便改变页面属性，使它保留“最近使用”的信息，转到；否则转到，同时diseffct加。 判断是否有空闲的内

9、存页面，如果有就返回页面指针，转到；否则，在内存页面中找出最长时间没有使用到的页面，将其“清干净”，并返回该页面指针。 将需处理的page与中得到的pagecontrol建立联系，同时需让对应的page单元保存“最新使用”的信息，返回。 如果序列处理完成，就输出，并结束。三nur1原理简述：所谓“最近未使用”首先是要对“近”作一个界定，比如clear_period50，便是在cpu最近的50次进程页面处理工作中，找出这50次都没有处理到的页面；如果 这样的页面只有一个，就将其换出，放入需处理的新页面； 有不只一个这样的页面，在这些页面中任取一个换出（可以是下标最小的，或者下标最大的，都随便），

10、放入需处理的页面； 没有一个这样的页面，随意换出一个页面（可以是下标最小的，或者下标最大的，都随便）。算法特点：有一个循环周期，每到达这个周期，所有页面存放是否被cpu处理信息的属性均被置于初始态（没有被访问）。2图表描述：还用前面的例子，某进程在硬盘上被划为5个页面，用1、2、3、4、5表示，而处理机处理它们的顺序为：1、4、2、5、3、3、2、4、2、5而内存可以控制的页面数为3（ap3），clear_period取5；循环周期内，如果所有内存页面均被cpu处理或有多个页面未被cpu处理，取页码最小的页面换出。内存页1号1115333335内存页2号444444444内存页3号222222

11、22进程的5号页面进入，由于内存中3个页面均使用到了，故换出页码最小的1号页面。进程的5号页面进入，由于内存中3个页面均使用到了，故换出页码最小的1号页面。所有页面设为“未访问图 31 页面交换共6次，disaffect=6。3算法实现提示： 初始化。设置两个数组pageap和pagecontrolpp分别表示进程页面数和内存分配的页面数，并产生一个的随机数序列maintotal_instruction（当然这个序列由page的下标随机构成），表示待处理的进程页面顺序，diseffect置零，设定循环周期clear_period。 看main是否有下一个元素。有，就从main中获得一个cpu将

12、处理页面的序号；没有，转到。 如果待处理的页面在内存之中，就转到；否则，diseffect加，并转到。 看是否有空闲的内存页面，如果有，返回空闲内存页面指针，并转到；否则，在所有没有被访问且位于内存中的页面中按任意规则（或者取最近的一个页面；或者取下标最小的）取出一个，返回清空后的内存页面指针。 将待处理进程页面与内存页面建立连续，并标注该页被访问。 如果cpu业已处理了clear_perod个页面，就将所有页面均设为“未访问” 返回。 如果cpu所有处理工作完成，就返回。四opt1原理简述：前提还是在分配的内存页面占满的情况下。所谓的最佳置换法是一种理想状况下的算法，它要求先遍历所有的cpu

13、待处理的进程页面序列（实际上由于待处理的页面有时取决于先前处理的页面，所有很多情况下不可能得到完整的待处理页面序列。在这个层面上，才说该算法是理想的。），在这些页面中，如果有已经在内存当中，而cpu不再处理的，就将其换出；如果页面在内存中，并且cpu待处理，就取从当前位置算起，最后处理到的页面，将其换出，比如cpu待处理的页面序列号为：13224525143411553421已经处理了5个页面（底纹为灰色），那么页面5是第一个待处理的页面；2是第二个；1是第四个；4是第五个；3是第六个。那么页面3就是针对当前位置而言，最后处理到的页面。2图表描述：还用前面的例子，某进程在硬盘上被划为5个页面，

14、用1、2、3、4、5表示，而处理机处理它们的顺序为：1、4、2、5、3、3、2、4、2、5而内存可以控制的页面数为3（ap3），内存页1号1115333335内存页2号444444444内存页3号22222222经分析发现以后不再处理页面1，故将其替换掉页面5是最后处理到的，故将其替换掉页面3以后不用到，换出。图 41 共发生页面交换6次，diseffect=6。3算法实现提示： 初始化。设置两个数组pageap和pagecontrolpp分别表示进程页面数和内存分配的页面数，并产生一个的随机数序列maintotal_instruction（当然这个序列由page的下标随机构成），表示待处理的

15、进程页面顺序，diseffect置零。 看main是否有下一个元素。有，就从序列main中获取一个cpu待处理的页面号；没有，转到。 如果该页面已经在内存中了，就转到；否则转到。 *看是否有空闲的内存页面，如果有就直接返回该页面指针；如果没有，遍历所有未处理的进程页面序列，如果有位于内存中的页面，而以后cpu不再处理的，首先将其换出，返回页面指针；如果没有这样的页面，找寻出cpu最晚处理到的页面，将其换出，返回该内存页面指针。 将内存页面和待处理的进程页面建立联系，返回。 输出，结束。注意：* 关于第4步的实现有个小小的技巧，可以为每个进程页面设一个“间隔”属性distance表示cpu将在第

16、几步处理到该页面，如果页面不再被cpu处理，可以设为某个很大的值（比如32767）,这样每次就换出distance最大的那个页面。【流程图】计算命中率1-diseffect/total_instruction*100%n开始fifo流程图初始化，设置两个数组pageap和pagecontrolpp 分别表示进程页面数和内存分配的页面数，并产生随机数序列maintotal_instruction, diseffect置0main中是否有下一个元素？y从main获取page下标n该page单元是否在内存中？ydiseffect+1pagecontrol是否占满？ny清理最先进入pagecontro

17、l单元，同时清理对应的page单元将该page与pagecontrol建立联系，将用到的pagecontrol置入使用队列结束返回该页面指针计算命中率1-diseffect/total_instruction*100%n开始从main获取page下标lru流程图初始化，主要是进程页面page和分配的内存页面pagecontrol，同时产生随机序列main，diseffect置零main中是否有下一个元素？y改变页面属性，使它保留“最近使用”的信息该page单元是否在内存中？yndiseffect+1是否有空闲的内存页面？ny在内存页面中找出最长时间没有使用到的页面，将其清干净结束将需处理的pa

18、ge与所得到的pagecontrol建立联系，同时需让对应的page单元保存最新使用的信息返回该页面指针计算命中率1-diseffect/total_instruction*100%n开始nur流程图初始化，设置两个数组pageap和pagecontrolpp 分别表示进程页面数和内存分配的页面数，并产生随机数序列maintotal_instruction, diseffect置0，设定循环周期clear_perodmain中是否有下一个元素？y从main获得一个cpu将处理页面的序号n待处理的 页面是否在内存中？ydiseffect+1将所有页面均设为未访问是否有空闲的页面？ynncpu是否

19、处理了clear_perod个页面？y在所有没有被访问且位于内存中按任意规律取出一个在待处理进程页面与内存页面之间建立联系，并标注该页被访问结束返回该页面指针计算命中率1-diseffect/total_instruction*100%开始opt流程图初始化，设置两个数组pageap和pagecontrolpp 分别表示进程页面数和内存分配的页面数，并产生随机数序列maintotal_instruction, diseffect置0。然后扫描整个页面访问序列，对vdistancetotal_vp数组进行赋值，表示该页面将在第几步被处理从main获取一个 cpu待处理得页面号main中是否有下一

20、个元素？y该page单元是否在内存中？yndiseffect+1npagecontrol是否占满？遍历所有进程页面序列ny是否有位于内存中、以后cpu不再处理的页面？yn将其换出找出cpu最晚处理到的页面，将其换出返回该页面指针将内存页面和待处理的进程页面建立联系结束【代码】page.h文件：#ifndef _page_h /（条件编译命令）如果page_h之前未被定义则编译#define_page_h#define _page_h /宏定义class cpage public: /以下的为公用部分 int m_npagenumber, m_npagefacenumber, m_ncounte

21、r, m_ntime; / 以上是定义4个类成员,都定义为整形变量;#endifpagecontrol.h文件:#ifndef _pagecontrol_h /若_pagecontrol_h之前的未被定义则编译#define_pagecontrol_h#define _pagecontrol_hclass cpagecontrol public: int m_npagenumber,m_npagefacenumber; class cpagecontrol * m_pnext; /类似于一个结构体;#endifmemory.h文件:#ifndef _memory_h /（条件编译）若_memo

22、ry_h之前没被定义过，则编译#ifndef _memory_h #define _memory_h /宏定义class cmemory /声明一个名为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); /最近未

23、使用算法 void opt(const int ntotal_pf); /最佳置换算法 /以上是对构造函数的原型声明 private: /声明以下部分为私有的成员变量 vector _vdiscpages; vector _vmemorypages; /以上是分别创建两个向量的对象,_vdiscpages和_vmemorypag cpagecontrol *_pfreepf_head,*_pbusypf,*_pbusypf_tail; /定义3个指针变量，依次是空页面头的指针， 忙页面头的指针，忙页尾的指针 vectorint_vmain,_vpage,_voffset; /定义3个增长数组

24、int _ndiseffect; /定义一个整型变量，表示页面换入的次数;cmemory:cmemory():_vdicspages(total_vp), /以下是对构造函数里用到的成员函数 _vmemorypages(total_vp), /内存也 _vmain(total_vp), _vpage(total_instruction), _voffset(total_instruction), /offset是，320份中每页的平均偏移量 int s,i nrand; /定义3个整型变量，以备下面计算随机序列所用 srand(getpid()*10); /以getpid()*10为种子产生随

25、机数 nrand=rand()%32767; /根据前面的种子，返回一个随机数，对其取模余后赋给nrand s=(float)319*nrand/32767+1; /计算s for(i=0;itotal_instruction;i+=4) _vmaini=s; /将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+

26、_vmaini+2+2;for(i=0;itotal_instruction;i+) _vpage= _vmaini/10; _voffseti= _vmaini%10; /偏移量为随即序列对10取模余 _vpagei%=32;/* 以上程序用于产生一个随机的进程页面序列*/void cmemory:initialize(const nt ntoatl_pf) /对构造函数initialize的定义 int ix; /定义一个临时变量 _ndiseffect=0; /初始化页面换入次数为零 for(ix=0;ix_vdiscpages.size();ix+) /for循环，如果ix少于物理页的

27、size，则进行下面操作 _vdiscpagesix.m_npagenumber=ix; /将ix赋为进程页面的页号 _vdiscpagesix.m_npagefacenumber=invalid;/初始化页面号码为invalid,此时没把页面调入内存 _vdiscpagesix.m_ncounter=0； /计数器初始化为零 _vdiscpagesix.m_ntime=-1; /m_ntime是一个用来记录某页面多久没被cpu使用的属性，将其初始化为-1for(ix=1;ixntotal_pf;ix+) /当ix少于总共页面数时，执行for循环 _vmemorypagesix.m_pnext

28、=&_vmemorypagesix; /将内存页的地址赋给它的下一页 _vmemorypagesix.m_npagefacenumber=ix-1; /内存页面号码为ix-1 /*此时，跳出 for 循环 */_vmemorypagesntotal_pf-1.m_pnext=null; /内存最后一页的所指向的下一页为空 _vmemorypagesntotal_pf-1.m_npagefacenumber=ntotal_pf-1; /内存最后一页的页面号码为ntotal_pf-1 _pfreepf_head=&_vmemorypages0; /将空页面的头指针指向内存页中下标为0的那一页 /*

29、initialize () 是对程序执行前进行初始化，尚未有页面调入内存*? void cmemory:fifo(const int ntotal_pf) int i; cpagecontrol *p; /定义cpagecontrol的指针p initialize(ntotal_pf); /调用构造函数initialize() _pbustpf_head=_pbustpf_tail=null; /忙时的头指针和忙时的尾指针置空 for(i=0;im_pnext; /将忙时的头指针指向m_pnext并赋给p _vdiscpages_pbusypf_head-m_npagenumber.m_npa

30、gefagenumber=invalid;/将page 置为空 _pfreepf_head=_pbusypf_head; /将忙时的头指针赋给空闲时的头指针 _pfreepf_head-m_pnext=null; /将空闲时的头指针的m_pnext置为空 _pbusypf_head=p; /将p赋给忙时的头指针 p=_pfreepf_head-m_pnext; /将空闲时的头指针的m_pnext(指向下一个分配的内存块)附给p _pfreepf_head-m_pnext=null; /返回空闲内存页面指针 _pfreepf_head-m_npagenumber=_vpagei; _vdiscp

31、ages_vpagei.m_npagefagenumber=_pfreepf_head-m_npagefagenumber;/给待处理页面分配内存空间 if(_pbusypf_tail=null) /如果忙时的尾指针为空时就执行if语句 _pbusypf_head=_pbusypf_tail=_pfreepf_head; else _pbusypf_tail-m_pnext=_pfreepf_head; _pbusypf_tail=_pfreepf_head; /将空闲时的头指针赋给空闲时的头指针 _pfreepf_head=p; coutfifo: 1-(float)_ndiseffect/

32、320; /计算结果void cmemory:nur(const int ntotal_pf) int i,j,ndiscpage,nold_discpage; /声明进程页面数和内存分配的页面数 bool bcont_flag; /声明一个布尔变量,用来控制循环 initialize(ntotal_pf); /nur的参数调用前面的initialize()函数 ndiscpage=0; /初始化ndiscpage置0 for(i=0;itotal_instruction;i+) /main中是否有下一个元素 if(_vdiscpages_vpagei.m_npagefacenumber=in

33、valid) /该页面是否在内存中 _ndiseffect+; /页面换入次数相应加1 if(_pfreepf_head=null) /如果没有空的内存页面 bcont_flag=true; /如有空闲页面,设bcont_flag为真 nold_discpage=ndiscpage; while(bcont_flag) /当bcont_flag为真时循环if(_vdiscpagesndiscpage.m_ncounter=0&_vdiscpagesndiscpage.m_npagefacenumber!=invalid) /在内存中的页面是否被访问 bcont_flag=false; /在内存

34、中的页面未被访问时 bcont_flag设为假,跳出循环 else ndiscpage+; if(ndiscpage=total_vp) ndiscpage=0; /*在待处理的进程页面*/ if(ndiscpage=nold_discpage) /*与内存页面之间建立联系*/ for(j=0;jm_pnext=null; /返回空闲内存页面指针 _vdiscpages_vpagei.m_npagefacenumber=_pfreepf_head-m_npagefacenumber; /给待处理页面分配内存空间 _pfreepf_head=_pfreepf_head-m_pnext; /指向下

35、一个分配的内存块 else _vdiscpages_vpagei.m_ncounter=1; /待处理的页面在内存中 if(i%clear_period=0) /*如果cpu已处理了clear_period*/ for(j=0;jtotal_vp;j+) _vdiscpagesj.m_ncounter=0; /*个页面,所有页面设为没访问 */ coutnur:1-(float)_ndiseffect/320; /*计算结果*/void cmemory:opt(const int ntotal_pf) int i,j,max,maxpage,ndistance,vdistancetotal_v

36、p; /声明进程页面数 initialize(ntotal_pf); /opt的参数调用前面的initialize()函数 for(i=0;itotal_instruction;i+) /调入内存的次数i小于页面使用总数，执行for语句 if(_vdiscpages_vpagei.m_npagefacenumber=invalid) /要调入的页面号不存在内存页面中，则执行if语句 _ndiseffect+; /页面交换总数加1 if(_pfreepf_head=null) /如果没有空的内存页面，则执行if语句 for(j=0;jtotal_vp;j+) /j小于内存分配的页面数，执行for

37、语句 if(_vdiscpagesj.m_npagefacenumber!=invalid) /若要调入的页面号在内存页面中，则执行if语句 vdistancej=32767; /置页面属性为cpu不再处理else vdistancej=0; /置页面属性为0 ndistance=1; /初始化 for(j=i+1;jtotal_instruction;j+) if(_vdiscpages_vpagej.m_npagefacenumber!=invalid)&(vdistance_vpagej=32767) /若要调入同存的页面在内存且不再被cpu处理 vdistance_vpagej=ndi

38、stance; /将要调入内存的页面号置为ndistance值 ndistance+; /ndistance加1 max=-1; /初始化max 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_pne

39、xt; /指向下一个分配的内存块 coutopt:1-(float)_ndiseffect/320; /计算命中率#endif main.cpp文件:#include /输入输出流调用#include /导入字符串#include /向量#include /声明标准库函数和宏#include / 支持标准输入输出的函数和全局符号#include / 用于定义函数using namespace std;#define invalid -1const int total_instruction(320); /页面总共使用次数const int total_vp(32); /内存分配页面const

40、int clear_period(50); /清零周期#include page.h /包含页面头文件#include pagecontrol.h /包含页面控制头文件int main() int i;cmemory a; /定义一个cmemory的实例afor(i=4;i=32;i+) a.fifo(i); /调用对象a里面的fifo算法 a.lru(i); a.nur(i); a.opt(i); /对a发生一个”消息”通知cmomory执行某置换算法 coutn; /换行输出 return 0;【结果和分析】结果：bankeyrh9 memory$ ./mainfifo:0.53125 lur:0.54375 nur:0.546875 opt:0.6375fifo:0.546875 lur:0.55625 nur:0.553125 opt:0.671875fifo:0.565625 lur:0.559375 nur:0.553125 opt:0.7fifo:0.578125 lur:0.575 nur:0.590625 opt:0.721875fifo:0.584375 lur:0.596875 nur:0.6125 opt:0.74375f