2022年实验请求页式存储管理页面置换算法.docx
精品学习资源操作系统试验报告班级:计科 0801 班 姓名：韩伟伟 学号： 08407106时间： 2021-5-25试验五 恳求页式储备治理的页面置换算法一试验目的通过恳求页式储备治理中页面置换算法模拟程序，明白虚拟储备技术的特点，把握恳求页式储备治理的页面置换算法；二试验属性设计三试验内容1. 通过随机数产生一个指令序列，共320 条指令，指令的地址按下述原就生产：50的指令是次序执行的；25的指令是匀称分布在前地址部分；25的指令是匀称分布在后地址部分；2. 将指令序列变换成为页地址流设页面大小为1K ；用户内存容量为4 页到 32 页；用户虚存容量为32K；在用户虚存中，按每K 存放 10 条指令排列虚存地址，即320 条指令在虚存中的存放方式为：第 0 条至第 9 条指令为第0 页；第 10 条至 19 条指令为第1 页；第 310 条至 319 条指令为第 31 页；3. 运算并输出下述各种算法在不同内存容量下的命中率；1> 先进先出算法 <FIFO ）2> 最近最少使用算法<LRU ）3> 正确使用算 <OPT）命中率页面失效次数页地址流长度本试验中，页地址流长度为320，页面失效次数为每次拜访相应指令时，该指令所对应的页不在内存的次数；四思路关于随机数的产生方法；第一要初始化设置随机数，产生序列的开头点，例如，通过以下语句实现：srand 400 > ；1>运算随机数，产生320 条指令序列m160；for i 0； i 80； i+ j i 4； aj m；aj+1 m+1 ；aj+2 aj 1.0 rand >/32767 ； aj+3 aj+2+1m aj+3+319-aj+3> 1.0 rand >/32767；2>将指令序列变换成为页地址流欢迎下载精品学习资源for k 0； k 320； k+> pt ak/10 ； pd= ak%10 ；3>运算不同算法的命中率rate 1-1.0 U/320 ；其中 U 为缺页中断次数， 320 是页地址流长度；4>输出格式kfifo1ru4 0.230.25欢迎下载精品学习资源五试验报告32 1.01.0欢迎下载精品学习资源1. 写出你编写的 C 语言程序；#include<conio.h> #include<stdio.h> #include<stdlib.h> #include<string.h>#define Myprintf printf"|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|n"> /*表格掌握 */ #define bsize 4/物理块大小#define psize 16/进程大小typedef struct pageint num； /*记录页面号 */int time； /*记录调入内存时间*/Page；/*页面规律结构，结构为便利算法实现设计*/ Page bbsize；/*内存单元数 */int cbsizepsize； /*暂储存内存当前的状态：缓冲区*/ int queue100；/*记录调入队列 */int K；/*调入队列计数变量 */ int phbbsize=0； /物理块标号int propsize=0； /进程序列号int flagbsize = 0； /进程等待次数 存放最久未被使用的进程标志> int i = 0, j = 0,k = 0； /i表示进程序列号 ,j表示物理块号int m = -1, n = -1；/物理块闲暇和进程是否相同判定标志int max = -1,maxflag = 0； /标记替换物理块进程下标int count = 0；/统计页面缺页次数/*/*/随 机 产 生序列号函数/*欢迎下载精品学习资源int* build>printf"随机产生一个进程序列号为：n"> ；int i = 0；fori=0； i<psize； i+>proi = 10*rand>/RAND_MAX+1>+1；printf"%d ",proi>；printf"n">；returnpro>；/*/查 找 空 闲物理块/*int searchpb>forj=0； j<bsize； j+>ifphbj = 0>m = j；return m；break；return -1；/*/查 找 相 同进程/* int searchpro>forj = 0； j < bsize； j+>ifphbj = proi>n = j；return j；return -1；/*/初 始 化 内欢迎下载精品学习资源存/* void empty>fori=0；i<bsize；i+>phbi=0；count=0；/计数器置零/*/先 进 先 出页面置换算法/* void FIFO>fori = 0； i<psize； i+>m=searchpb>；n=searchpro>；/ 找 flag值最大的forj = 0； j < bsize；j+>ifflagj>maxflag>maxflag = flagj；max = j；ifn = -1>/不存在相同进程ifm .= -1>/存在闲暇物理块phbm = proi； /进程号填入该闲暇物理块count+；flagm = 0；forj = 0； j <= m ； j+>flagj+；m = -1；else/不存在闲暇物理块phbmax = proi；flagmax = 0；forj = 0；j < bsize； j+>欢迎下载精品学习资源flagj+；max = -1；maxflag = 0；count+；else/存在相同的进程phbn = proi；forj = 0；j < bsize； j+>flagj+；n = -1；forj = 0； j < bsize； j+>printf"%d ",phbj>；printf"n">；printf"缺页次数为： %dn",count>；printf"n">；/*/*/* 初始化内存单元、缓冲区*/ void InitPage *b,int cbsizepsize>int i,j；fori=0；i<psize；i+>bi.num=-1；bi.time=psize-i-1；fori=0；i<bsize；i+>forj=0；j<psize；j+> cij=-1；/* 取得在内存中停留最久的页面, 默认状态下为最早调入的页面*/ int GetMaxPage *b>欢迎下载精品学习资源int i；int max=-1；int tag=0；fori=0；i<bsize；i+>ifbi.time>max>max=bi.time；tag=i；return tag；/* 判定页面是否已在内存中*/ intEquationint fold,Page *b>int i；fori=0；i<bsize；i+>if fold=bi.num>return i；return -1；/*LRU 核心部分 */void Lruuint fold,Page *b>int i；int val；val=Equationfold,b>；if val>=0>欢迎下载精品学习资源elsebval.time=0；fori=0；i<bsize；i+> if i.=val>bi.time+；queue+K=fold；/* 记录调入页面 */ val=GetMaxb>；bval.num=fold；bval.time=0；fori=0；i<bsize；i+>欢迎下载精品学习资源if i.=val>bi.time+；void LRU>int i,j；K=-1；Initb, c>；fori=0；i<psize；i+>Lruuproi,b>；c0i=proi；/*记录当前的内存单元中的页面*/ forj=0；j<bsize；j+>cji=bj.num；/*结果输出 */printf"内存状态为： n"> ；Myprintf；forj=0；j<psize；j+> printf"|%2d ",proj>；printf"|n">；Myprintf；fori=0；i<bsize；i+>forj=0；j<psize；j+>ifcij=-1>printf"|%2c ",32>；elseprintf"|%2d ",cij>；printf"|n">；Myprintf；printf"n调入队列为 :"> ；fori=0；i<K+1 ；i+> printf"%3d",queuei>；printf"n缺页次数为：%6dn缺页率： %16.6f",K+1,float>K+1>/psize>；/*/主函数欢迎下载精品学习资源/* void main>int sel；doprintf"ttt-ttt">；printf"ttt - 欢迎进入操作系统界面- ttt">；printf"ttt-tttn">；printf"tttttt">；printf"ttt虚拟内存 ttt">；printf"ttt -ttt">；printf"ttt1、产生随机序列 ttt">；printf"ttt -ttt">；printf"ttt2、最久未使用 LRU> ttt">；printf"ttt -ttt">；printf"ttt3、先进先出 FIFO> ttt">；printf"ttt -ttt">；printf"ttt4、正确置换算法 OPT> ttt">；printf"ttt - ttt"> ；printf"ttt 5 、三种算法的比较 > ttt"> ；printf"ttt - ttt"> ；printf"ttt0、退出 Exit> ttt">；printf"ttttttn">；printf"请挑选所要执行的操作 0/1/2/3/4/5>:">；scanf"%d",&sel>；switchsel>欢迎下载精品学习资源break ；break ；break ；case0:printf"ttt-再见！ - tttn">；system"pause">；case 1:build>；break ；case 2:printf"最久未使用算 n"> ；LRU>；empty> ；printf"n">；case 3:printf"先进先出算 n"> ；FIFO> ；empty> ；printf"n">；case 5:printf"先进先出算法 n"> ； FIFO> ；empty> ；欢迎下载精品学习资源printf"最久未使用算法 n"> ；LRU>；empty> ；break ；default: printf"请输入正确的选项号！"> ；printf"nn">；break ；whilesel.=0>；产生的随机序列：最近最少使用算法执行结果如下：欢迎下载精品学习资源先进先出 FIFO 算法执行结果：2. 总结体会恳求页式储备治理的实现原理；恳求页式治理的基本原理是将规律地址空间分成大小相同的页，将储备地址空间分块，页和块的大小相等，通过页表进行治理；页式系统的规律地址分为页号和页内位移 量；页表包括页号和块号数据项，它们一一对应；依据规律空间的页号，查找页表对应项找到对应的块号，块号乘以块长，加上位移量就行成储备空间的物理地址；每个作业的规律地址空间是连续的，重定位到内存空间后就不肯定连续了；3. 写出这三种页面置换算法的实现思想；FIFO 算法总是剔除最先调入主存的页面，即剔除在主存中驻留时间最长的页面，认为驻留时间最长的页不再使用的可能性较大；LRU 算法剔除的页面是最近一段时间内最久未被拜访的那一页，它是基于程序局部性原理来考虑的，认为那些刚被使用过的页面可能仍要立刻被使用，而那些在较长时间内未被使用的页面可能不会立刻使用；OPT 算法，当要调入一页而必需剔除旧页时，应当剔除以后不再拜访的页，或距现在最长时间后要拜访的页面；4. 对不同算法的性能进行评判；FIFO 算法较易实现，对具有线性次序特点的程序比较适用，而对具有其他特点的程序就效率不高，此算法仍可能显现抖动现象<Belady ）反常； LRU算法基于程序的局部性原 理，所以适用用大多数程序，此算实现必需保护一个特别的队列页面剔除队列；OPT 算法虽然产生的缺页数最少，然而，却需要猜测程序的页面引用串，这是无法预知的，不可能对程序的运行过程做出精确的断言，不过此理论算法可用做衡量各种详细算法的标准；欢迎下载精品学习资源欢迎下载
