《操作系统》实验三 存储管理.doc

实验三 存贮器管理 一、实验目的 本课题实习的目的用高级语言编写一个程序，模拟实现分页式虚拟存储管理，并对几种常用的页面调度算法（、LRU、FIFO OPT等）进行分析比较，评测其性能优劣，从而加深对虚拟存储管理以及各种调度算法的了解。 二、实验要求 采用一些常用的存贮器分配算法,设计一个存贮器管理模拟系统并调试运行。模拟环境应尽量接近真实。 三、实验内容 问题描述 ⑴通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： ①一半的指令是顺序执行的； ②四分之一的指令是均匀分布在前地址部分； ③四分之一的指令是均匀分布在后地址部分。 具体的实施办法是： ①在[0，319]之间选一起点m； ②顺序执行一条指令，即m+1条； ③向前地址[0，m—1]中执行一条指令m′； ④顺序执行一条指令，即m′+1条； ⑤向后地址（m′+2，319）执行一条指令m’’ ⑵将指令序列变换成为页地址流。 假设： ①页面大小为1KB； ②用户实存容量为4页到32页； ③用户虚存容量为32KB。 用户虚存容量32KB，每1KB中放10条指令，共320条指令（0∽319）。其中0∽9为0页，10∽19为1页…310∽319为31页。 ⑶使用不同的页面调度算法处理缺页中断，并计算不同实存容量下（4∽32KB）的命中率。 ①先进先出算法（FIFO）； ②最近最少使用算法（LRU）； ③最佳淘汰算法（OPT）；先淘汰最不常用的页地址； ④最少访问页面算法（LFU）。 命中率的算法为： 命中率=缺页中断次数/页地址流长度 2、数据结构 int vmsize /*虚存容量，为32k*/ int pagesize /*页面尺寸，大小为1k到32k*/ int pageassigned /*实存容量，大小从4页到32页*/ 3、思路 关于随机数的产生办法。首先要初始化设置随机数，产生序列的开始点，例如，通过下列语句实现： rand(400) ⑴计算随机数，产生320条指令序列 m=160 for(i=0;i80;i++) { j=i*4; a[j]=m; a[j+1]=m+1; a[j+2]=a[j]*1.0*rand( )/32767; a[j+3]=a[j+2]+1; m=a[j+3]+(319-a[j+3]*1.0*rand( )/32767; } ⑵将指令序列变换成为页地址流 for (k=0;k320;k++) {pt=a[k]/10; … } ⑶计算不同算法的命中率 rate=1—1.0*U/320; 其中U为缺页中断次数，320是页地址流长度。 ⑷输出格式 k fifo lru 4 0.23 0.25 … … … 32 1.0 1.0 4、算法及框图 （1）先进先出算法（FIFO） 先进先出算法的出发点是先进内存者先被淘汰，即选择在内存中驻留时间最长的一页淘汰之。理由是，最早调入的页在近期不再被使用的可能性要大于最近调入的页。实现这种算法的基本方法是，为调入的每一页以递增方式标明调入次序，淘汰时选择次序值最小的那一页，或者建立一个先进先出队列，总是淘汰队首的那一页。 (2)最近最久未使用淘汰算法（Least Recently Used） 这是一种经常使用的有效算法，淘汰最近一段对间内最久未被访问的页面。它是根据程序执行时所具有局部属性（时间局部性属性）来考虑的，其思想是刚被访问过的页面，常常马上又要被访问，而那些在较长时间里未被使用的页面，一般来说可能不会马上被访问。 这种算法实现起来较困难,实际应用中往往采用LRU近似算法。如采用不断调整页表链的方法,即总是淘汰页表链链首的页，而把新访问的页插入链尾。若当前调用页已在页表内,则把它再次调整到链尾。这样就能保证最近使用的页总是靠近链尾部分,而不常使用的页就移到链尾，逐个被淘汰,页表较大时，调整页表链的代价也是不小的。 （3）算法总体框图（见后图3.1） 图3.2 FIFO与LRU算法框图 图3.2 FIFO与LRU算法框图 （4）FIFO算法与LRU算法框图 四、存储管理示例 1.问题描述 该模拟系统的外部特性与真实系统基本一样。存贮分配算法采用首次适应法。用拼接和搬家技术来处理存贮器碎片。 2.数据结构 (1)自由链与区头。内存空区采用自由链结构。链首由指针freep指向,链中各空区按地址递增次序排列。初启时整个用户内存区为一个大空区。在每个空区首部设置一个区头(freearea)结构。区头信息包括: size 空区大小(以字节计),包括区头所占空间 next 前向链指针,指向下一个空区 back 反向链指针,指向上一个空区 address 本空区首地址。 (2)内存分配表MAT。 系统设置一个MAT,每个运行作业都在MAT中