实验二 存储管理 1 实验目的 存储管理的主要功能之一是合理地分配 bb.doc

实验二 存储管理1. 实验目的 存储管理的主要功能之一是合理地分配空间。请求页史管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。实验是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。2. 实验内容1) 通过随机数产生一个指令序列，共320条指令，指令的地址按下述原则生成：j 50%的指令是顺序执行的；k 25%的指令是均匀分布在前地址部分。l 25%的指令是均匀分布在后地址部分。具体的实施办法是：j 在0，319的指令地址之间随机选取一点m；k 顺序执行一条指令，即执行地址为m+1的指令；l 在前地址0，m+1中随机选取一条指令并执行，该指令的地址为m；m 顺序执行一条指令，其地址为m+1；n 在后地址m+2，319中随机选取一条指令并执行；o 重复上述步骤jn，直到执行320次指令。2) 将指令序列变换成页地址流设：j 页面大小为1K；k 用户内存容量为4页到32页；l 用户虚存容量为32K； 在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为： 第0条-9条指令为第0页（对应虚存地址为0，9）； 第10条-第19条指令为第一页（对应虚存地址为10，19）； 第310条-第319条指令为第31页（对应虚存地址为310，319）； 按以上方式，用户指令可组成32页。3) 计算并输出下述各种算法在不同内存容量下的命中率。j 先进先出的算法（FIFO）；k 最近最少使用算法（LRU）；l 最佳淘汰算法（OPT）； 命中率=1-页面失效次数/页地址流长度在本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。4） 实验提示关于随机数产生办法，用TC系统提供函数RAND（）产生随机数。3设计内容与步骤分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。1、调页策略1)何时调入页面2)请求调页策略2、从何处调入页面 (1)系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。 (2)系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出时，以后需要时，再从对换区调入。（3）UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都从文件区调入。而对于曾经运行过但又被换出的页面，由于被放在对换区，因此在下次时，应从对换区调入。由于UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。3、页面调入过程j 页面大小为1K；k 用户内存容量为4页到32页；l 用户虚存容量为32K； 在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为： 第0条-9条指令为第0页（对应虚存地址为0，9）； 第10条-第19条指令为第一页（对应虚存地址为10，19）； 第310条-第319条指令为第31页（对应虚存地址为310，319）； 按以上方式，用户指令可组成32页。4. 概要设计（1）页面置换算法：1、先进先出(FIFO)页面置换算法的描述：这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。2、 最近最少使用算法（LRU）页面置换算法的描述：算法的基本思想：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问3、 最佳淘汰算法（OPT）页面置换算法的描述：算法的基本思想：当要调入一页而必须淘汰一页旧页时，所淘汰的页应该是以后不再访问的页或距现在最长时间后再访问的页。这样的调度算法使缺页中断率为最低。然而这样的算法是无法实现的因为在程序运行中无法对以后要使用的页面作出精确的断言。不过，这个理论上的算法可以用来作为衡量各种具体算法的标准。这个算法是由Belady提出来的，所以叫做Belady算法，又叫做最佳算法(OPT)4、程序执行是稳定的，高效的。在LRU算法中，要找出最近最久未使用的页面的话，就必须设置有关的访问记录项，且每一次访问这些记录项，页面都必须更新这些记录项。如此显然要花费较大的系统开销(包括时间和空间上的)，这也是实际系统中不直接采用LRU算法作为页面置换算法的直接原因，但由于其在页面置换的优越性，实际系统常使用LRU的近似算法。（2）数据结构1、函数定义 (1) void main()：主函数 (2) voidFIFO()：计算使用FIFO算法时的命中率。（3）voidLRU():计算使用LRU算法时的命中率. (4) voidOPT():计算使用OPT算法时的命中率.2、其他定义（1）#define total_page_address 320 /*作业的地址流数*/（2）#define total_page 32 /*作业的页面数*/（3）int pagetotal_page_address;/变量定义，:每条指令所属页号。(4) int page_message100,i,ptr=0,j; (5) int invalid=0,exist;3、主要程序算法 #include #define total_page_address 640 /*作业的地址流数*/#define total_page 32 /*作业的页面数*/int pagetotal_page_address;void FIFO(int mem_frame);void LRU(int mem_frame);void OPT(int mem_frame);main()int i,p,fl;srand(getpid();/*设置随机种子*/*产生页地址流,假设有50%的指令是顺序执行的*/for (i=0;itotal_page_address;i+)pagei=-1;for (i=0;itotal_page_address;i+=2) fl=0;while (fl=0)p=rand()%total_page_address;if (pagep=-1)fl=1;pagep=rand()%total_page; p=0;for (i=0;itotal_page_address;i+)if (pagei=-1) pagei=p;else p=pagei;for (i=4;i=32;i+) /*用户内存工作区从4 个页面到32 个页面*/printf(%2d page frames ,i);FIFO(i);LRU(i);OPT(i);printf(n);void FIFO(int mem_frame)int page_message100,i,ptr=0,j; int invalid=0,exist;/*page_message 存放页面信息,ptr指向最早进入的页面*/for (i=0;i100;i+) page_messagei=-1; /*-1表示无页面*/for (i=0;itotal_page_address;i+)/查找该页是否在内存exist=0;for (j=0;jmem_frame;j+)if (page_messagej=pagei)exist=1; /该页在内存中if (exist=0) /该页不在内存中，失败invalid+;for (j=0;j=mem_frame)page_messageptr=pagei; /淘汰最早进入的页面ptr=(ptr+1) % mem_frame;printf(FIFO: %6.4f ,1-(float)invalid/total_page_address);void LRU(int mem_frame)int page_message100,i,ptr=0,j,m,n; int invalid=0,exist,sit1,sit2;/*page_message 存放页面信息,ptr指向最早进入的页面*/for (i=0;i100;i+) page_messagei=-1; /*-1表示无页面*/for (i=0;itotal_page_address;i+)/查找该页是否在内存exist=0;for (j=0;jmem_frame;j+)if (page_messagej=pagei)exist=1; /该页在内存中if (exist=0) /该页不在内存中，失败invalid+;for (j=0;j=mem_frame)/查找最久未用页面进行淘汰 exist=3333;for (m=0;m=0;n-)if(page_messagem=pagen) sit1=n;break;if (existsit1) exist=sit1;sit2=m;page_messagesit2=pagei;printf(LRU: %6.4f ,1-(float)invalid/total_page_address);void OPT(int mem_frame)int page_message100,i,ptr=0,j,m,n; int invalid=0,exist,sit1,sit2;/*page_message 存放页面信息,ptr指向最早进入的页面*/for (i=0;i100;i+) page_messagei=-1; /*-1表示无页面*/for (i=0;itotal_page_address;i+)/查找该页是否在内存exist=0;for (j=0;jmem_frame;j+)if (page_messagej=pagei)exist=1; /该页在内存中if (exist=0) /该页不在内存中，失败invalid+;for (j=0;j=mem_frame)/查找最久未用页面进行淘汰 exist=-1;for (m=0;mmem_frame;m+)for(n=i+1;n=total_page_address)sit2=m;elseif (existsit1) exist=sit1;sit2=m;page_messagesit2=pagei;printf(LRU: %6.4f ,1-(float)invalid/total_page_address);5. 结果与分析实验结果： 4 page frames FIFO: 0.5563 LRU: 0.5563 OPT: 0.6344 5 page frames FIFO: 0.5672 LRU: 0.5703 OPT: 0.6813 6 page frames FIFO: 0.5906 LRU: 0.5828 OPT: 0.6969 7 page frames FIFO: 0.6188 LRU: 0.6125 OPT: 0.7172 8 page frames FIFO: 0.6344 LRU: 0.6312 OPT: 0.7547 9 page frames FIFO: 0.6469 LRU: 0.6422 OPT: 0.7625 10 page frames FIFO: 0.6547 LRU: 0.6641 OPT: 0.7891 11 page frames FIFO: 0.6781 LRU: 0.6781 OPT: 0.7937 12 page frames FIFO: 0.6797 LRU: 0.6937 OPT: 0.8109 13 page frames FIFO: 0.6937 LRU: 0.7063 OPT: 0.8172 14 page frames FIFO: 0.7188 LRU: 0.7266 OPT: 0.8484 15 page frames FIFO: 0.7359 LRU: 0.7344 OPT: 0.8594 16 page frames FIFO: 0.7500 LRU: 0.7531 OPT: 0.8672 17 page frames FIFO: 0.7562 LRU: 0.7656 OPT: 0.8750 18 page frames FIFO: 0.7797 LRU: 0.7812 OPT: 0.8797 19 page frames FIFO: 0.7891 LRU: 0.7859 OPT: 0.8906 20 page frames FIFO: 0.7969 LRU: 0.7984 OPT: 0.8953 21 page frames FIFO: 0.8297 LRU: 0.8125 OPT: 0.9016 22 page frames FIFO: 0.8562 LRU: 0.8234 OPT: 0.9078 23 page frames FIFO: 0.8672 LRU: 0.8422 OPT: 0.9141 24 page frames FIFO: 0.8703 LRU: 0.8672 OPT: 0.9203 25 page frames FIFO: 0.8797 LRU: 0.8812 OPT: 0.9266 26 page frames FIFO: 0.8844 LRU: 0.8891 OPT: 0.9281 27 page frames FIFO: 0.8859 LRU: 0.9031 OPT: 0.9359 28 page frames FIFO: 0.8922 LRU: 0.9109 OPT: 0.9375 29 page frames FIFO: 0.9203 LRU: 0.9250 OPT: 0.9406 30 page frames FIFO: 0.9297 LRU: 0.9328