操作系统课程设计--- 请求调页存储管理.doc

计算机科学与应用系操作系统原理课程设计报告题目 请求调页存储管理 linux的安装及用户接口 班级 xxx 学号 xxx 姓名 xxx 专业 计算机科学与技术 指导教师 实验一 请求调页存储管理1实验目的(1) 通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。(2) 通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。(3) 掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。2实验内容 1假设每个页面中可存放10条指令，分配给作业的内存块数为4。2用c语言或c+语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。3置换算法：请分别考虑最佳置换算法（opt）、先进先出（fifo）算法和最近最久未使用（lru）算法。4作业中指令的访问次序按下述原则生成；50%的指令是顺序执行的；25%的指令是均匀分布在前地址部分；25%的指令均匀分布在后地址部分。具体的实现办法是：（1）在0，319之间随机选取一条起始执行指令，其序号为m；（2）顺序执行下一条指令，其序号为m+1条指令；（3）通过随机数，跳转到前地址部分0，m-1中的某条指令处，其序号为m1；（4）顺序执行下一条指令，即序号为m1+1的指令；（5）通过随机数，跳转到后地址部分m1+2,319中的某条指令处，其序号为m2；（6）顺序执行下一条指令，则序号为m2+1的指令；（7）重复跳转到前地址部分，顺序执行，跳转到后地址部分；顺序执行的过程，直至执行320条指令。3实验步骤1分析及概要设计在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，所以需要根据一定的算法来确定。在这一过程中，选择换出页面的算法称为页面置换算法。一个好的页面置换算法，应具有较低的页面更换频率。页面置换算法的好坏，将直接影响到系统的性能。以下分别是实验要求的两个页面置换算法的介绍及设计思想。（1）先进先出法（first in first out）：该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。在该算法的模拟过程中，每当页面被置换进入内存时，将置换页面所在的物理块中访问标记设为-1；并且每执行一次指令，便将物理块的访问标记自动加1，需要置换时将访问标记最大的物理块中的页面置换出去，这样能防止当物理块访问标记出现两个以上相同的值的错误执行，更好地模拟了先进先出法；（2）最近最久未使用（least recently used）： 该算法以最近的过去作为不久将来的近似， 将过去最长一段时间里不曾被使用的页面置换掉。在该算法的模拟过程中，每当物理块中的页面被访问时（包括原先存在的和后来置换进入的页面），便将其物理块访问标记置为1。以后每执行一条指令，便将物理块中各页面的访问标记加1，需置换时访问标记最大的便是将要被置换的。（3）最佳置换算法（opt）：发生缺页时，有些页面在内存中，其中有一页见很快被访问（也包含紧接着的下一条指令的那页），而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。 最佳页面置换算法只是简单地规定：标记最大的页应该被置换。如果某页在八百万条指令内不会被使用，另一页在600万条指令内不会被使用，则置换前一个页面，从而把因需要调回这一页发生的缺页推到将来，越远越好。这个算法唯一的一个问题就是它无法实现。当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。虽然这个算法不可能实现，但是最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。2流程图开始调用fifo算法调用lru算法调用opt算法提示输入数据非法输出指令执行顺序和页面调用顺序得到指令执行的顺序接收键盘输入数值判断输入数是否在1320选择页面置换算法结束3程序代码#include #include#include#include#define size 4typedef struct block/声明一种新类型物理块类型 int pagenum;/页号 int accessed;/访问字段，其值表示多久未被访问block; int count;/程序计数器，用来记录指令的序号int n;/缺页计数器，用来记录缺页的次数static int temp320;/用来存储320条随机数block blocksize; /定义一大小为4的物理块数组void init( ); /程序初始化函数int findexist(int curpage);/查找物理块中是否有该页面int findspace( );/查找是否有空闲物理块int findreplace( );/查找应予置换的页面void display ( );/显示void random( );/产生320条随机数,显示并存储到temp320void pagestring( );/显示调用的页面队列void opt( );/opt算法void lru( );/ lru算法void fifo( );/fifo算法void init( ) for(int i=0;isize;i+) blocki.pagenum=-1; blocki.accessed=0; count=n=0; int findexist(int curpage) /查找物理块中是否有该页面for(int i=0; isize; i+) if(blocki.pagenum = curpage ) return i; /检测到内存中有该页面，返回block中的位置 return -1;int findspace( ) /查找是否有空闲物理块 for(int i=0; isize; i+) if(blocki.pagenum = -1) return i; /找到空闲的block，返回block中的位置return -1;int findreplace( ) /查找应予置换的页面int pos = 0; for(int i=0; iblockpos.accessed) pos = i;/找到应予置换页面，返回block中位置 return pos;void display( ) for(int i=0; isize; i+) if(blocki.pagenum != -1) /物理块不空 printf( %02d,blocki.pagenum); coutcount; cout*按照要求产生的320个随机数：*endl; for(int i=0;i320;i+) tempi=count;if(flag%2=0)count=+count%320;/产生50%的顺序执行指令（flag=0或2时顺序执行） if(flag=1) count=rand( )% (count-1); /产生25%的均匀分布在前地址部分指令 if(flag=3) count=count+1+(rand( )%(320-(count+1); /产生25%的均匀分布在后地址部分指令 flag=+flag%4;printf( %03d,tempi); if(i+1)%10=0) coutendl;void pagestring( ) /显示调用的页面队列 for(int i=0;i320;i+) printf( %02d,tempi/10); if(i+1)%10=0) coutendl;/-最佳置换算法void opt( )int exist,space,position ; int curpage; for(int i=0;i320;i+) if(i%100=0) getch( ); count=tempi; curpage=count/10; exist = findexist(curpage); if(exist=-1) space = findspace ( ); if(space != -1)blockspace.pagenum = curpage; display( ); n=n+1; elsefor(int k=0;ksize;k+)for(int j=i;j320;j+)if(blockk.pagenum!= tempj/10)blockk.accessed = 1000;/将来不会用，设置为一个很大数 elseblockk.accessed = j;break; position = findreplace( ); blockposition.pagenum = curpage; display( ); n+; cout缺页次数:nendl; cout缺页率:(n/320.0)*100%endl;/- 最近最少使用算法 void lru( ) int exist,space,position ; int curpage; for(int i=0;i320;i+) if(i%100=0) getch( ); /getch直接从键盘获取键值 count=tempi; /指令在数组中的位置 curpage=count/10; /指令所在页面 exist = findexist(curpage); /查找物理块中是否有该页面,若有返回物理块号 if(exist=-1) /物理块中不存在该页space = findspace( ); /查找是否有空闲物理块 if(space != -1) /有空闲物理块blockspace.pagenum = curpage; display( ); n=n+1; else /无空闲物理块，则寻找置换页面 position = findreplace( ); /查找应予置换的页面 blockposition.pagenum = curpage; blockposition.accessed = -1; /恢复刚调入的block中页面accessed为-1 display( ); n+; else blockexist.accessed = -1;/恢复存在的并刚访问过的block中页面accessed为-1 for(int j=0; j4; j+) blockj.accessed+; cout缺页次数:nendl; cout缺页率:(n/320.0)*100%endl;/- 先进先出算法void fifo( ) int exist,space,position ; int curpage; for(int i=0;i320;i+) if(i%100=0) getch( ); /getch直接从键盘获取键值 count=tempi; curpage=count/10; exist = findexist(curpage); /查找物理块中是否有该页面 if(exist=-1)space = findspace( ); /查找是否有空闲物理块 if(space != -1) /有空闲物理块 blockspace.pagenum = curpage; display( ); n=n+1; else /无空闲物理块，则寻找置换页面 position = findreplace( ); /查找应予置换的页面 blockposition.pagenum = curpage; display( ); n+; blockposition.accessed-; /置换页面所在的物理块中访问标记设为-1 else/若存在该页for(int i=0; isize; i+) if(blocki.pagenum != -1) /物理块不空printf( %02d ,blocki.pagenum);cout指令已经存在! 其物理块地址为:&blockexistendl;for(int j=0; jsize; j+)blockj.accessed+; cout缺页次数:nendl; cout缺页率:(n/320.0)*100%endl;void main( )int select; cout请输入第一条指令号(1320): ; random( ); cout*对应的调用页面队列*endl; pagestring( ); docout*endl; cout* 1:opt 2:lru 3:fifo 4:退出 *endl; cout*endl; coutselect; cout*endl; init( ); switch(select) case 1:cout最佳置换算法opt:endl; cout*endl; opt( ); break; case 2:cout最近最久未使用置换算法lru:endl; cout*endl; lru( ); break; case 3:cout先进先出置换算法fifo:endl;cout*re.shcd $directorycpio i $1 /dev/fd()d0)exit 0;es