《模拟请求页式管理（5.28）.pptx》由会员分享，可在线阅读，更多相关《模拟请求页式管理（5.28）.pptx（17页珍藏版）》请在金锄头文库上搜索。
1、书山有路 目录 1 书山有路 1 模拟请求页式管理一 设计目的通过模拟实现请求页式存储管理的几种基本页面置换算法 了解虚拟存储技术的特点 通过对页面 页表 地址转换和页面置换过程的模拟 加深对请求调页系统的原理和是实验过程的理解 掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程 并比较它们的效率 二 设计内容通过随机数产生一个指令序列 共320条指令 指令的地址按下述原则生成 50 的指令是顺序执行的 25 的指令是均匀分布在前地址部分 25 的指令是均匀分布在后地址部分 具体的实施方法是 在 0 319 的指令地址之间随机选取一起点m 顺序执行一条指令 在前地址 0 m
2、 1 中随机选取一条指令并执行 该指令的地址为m 顺序执行一条指令 其地址为m 1 在后地址 m 2 319 中随机选取一条指令并执行 重复上述步骤 直到执行320次指令 将指令序列变换成为页地址流 书山有路设 页面大小为1K 用户内存容量为4页到32页 用户虚存容量为32K 在用户虚存中 按每K存放10条指令排列虚存地址 即320条指令在虚存中的存放方式为 第0条 第9条指令为第0页 对应虚存地址为 0 9 第10条 第19条指令为第1页 对应虚存地址为 10 19 第310条 第319条指令为第31页 对应虚存地址为 310 319 按以上方式 用户指令可组成32页 计算并输出下述各种算法
3、在不同内存容量下的命中率 先进先出的算法 FIFO 最近最久未使用算法 LRU 最佳访问算法 OPT 三 设计原理 FIFO页面置换算法 原理简述 在分配内存页面数 AP 小于进程页面数 PP 时 当然是最先运行的AP个页面放入内存 这时有需要处理新的页面 则将原来内存中的AP个页面最先进入的调出 是以称为FIFO 然后将新页面放入 以后如果再有新页面需要调入 则都按 的规则进行 算法特点 所使用的内存页面构成一个队列 2 书山有路LRU页面置换算法 原理算述 当分配内存页面数 AP 小于进程页面数 PP 时 当然是把最先执行的AP个页面放入内存 当需要调页面进入内存 而当前分配的内存页面全部
4、不空闲时 选择将其中最长时间没有用到的那个页面调出 以空出内存来放置新调入的页面 称为LRU 算法特点 每个页面都有属性来表示有多长时间未被CPU使用的信息 LRU算法的硬件支持把LRU算法作为页面置换算法是比较好的 它对于各种类型的程序都能适用 但实现起来有相当大的难度 因为它要求系统具有较多的支持硬件 所要解决的问题有 一个进程在内存中的各个页面各有多久时间未被进程访问 如何快速地知道哪一页最近最久未使用的页面 为此 须利用以下两类支持硬件 1 寄存器用于记录某进程在内存中各页的使用情况 3 书山有路 2 栈可利用一个特殊的栈来保存当前使用的各个页面的页面号 每当进程访问某页面时 便将该页
5、面的页面号从栈中移出 将它压入栈顶 4 四 算法实现命中率 1 页面失效次数 页地址流长度本实验中 页地址流长度为320 页面失效次数为每次访问相应指令时 该指令所对应的页不在内存的次数 关于随机数产生方法 采用TC系统提供函数RAND 和RANDOMIZE 来产生 constintMaxNum 320 指令数constintM 5 内存容量intPageOrder MaxNum 页面请求intSimulate MaxNum M 页面访问过程intPageCount M LackNum PageCount用来记录LRU算法中最久未使用时间 LackNum记录缺页数floatPageRate 命
6、中率 PageRate 1 float LackNum float MaxNum 计算命中率intn rand 320 随机数产生320次页面请求PageOrder k n 10 根据指令产生320次页面请求 书山有路五 流程图 开始生成地址流 1 S 4 形成地址页号 用户内存空间msize 2 Msize 32 FIFO LRU OPT Msize加1 是否用其他算法继续 结束 N YS 1 2 3 Y 输入算法号SN提示出错 重新输入 5 书山有路六 源程序 include includeusingnamespacestd constintMaxNum 320 指令数constintM
7、5 内存容量intPageOrder MaxNum 页面请求intSimulate MaxNum M 页面访问过程intPageCount M LackNum PageCount用来记录LRU算法中最久未使用时间 LackNum记录缺页数intPageCountOPT M PageCountOPT用来记录OPT算法中最久未使用时间floatPageRate 命中率intPageCount1 32 boolIsExit inti FIFO算法中判断新的页面请求是否在内存中 boolf false for intj 0 j M j if Simulate i 1 j PageOrder i 在前一
8、次页面请求过程中寻找是否存在新的页面请求 f true returnf intIsExitLRU inti LRU算法中判断新的页面请求是否在内存中 intf 1 for intj 0 j M j if Simulate i 1 j PageOrder i f j returnf intCompare LRU算法找出内存中需要置换出来的页面 intp q p PageCount 0 6 书山有路q 0 for inti 1 i M i if p PageCount i p PageCount i q i returnq intCompareOPT inti OPT算法找出内存中需要置换出来的页
9、面 inttemp 5 for inta 0 a 5 a temp a 0 for intj 0 j M j for intii i 1 ii MaxNum ii if Simulate i 1 j PageOrder ii temp j else break intmax temp 0 intmaxIndex 0 for inti1 1 i1 M i1 if max temp i1 max temp i1 maxIndex i1 7 书山有路 returnmaxIndex voidInit 初始化页框 for intk 0 k MaxNum k intn rand 320 随机数产生320次
10、页面请求PageOrder k n 10 根据指令产生320次页面请求 for inti 0 i MaxNum i 初始化页面访问过程 for intj 0 j M j Simulate i j 1 for intq 0 q M q 初始化最久未使用数组 PageCount q 0 PageCountOPT q 0 voidAllNum intj cout 页面访问序列 endl for j 0 j MaxNum j cout PageOrder j voidOutPut 输出 inti j cout endl cout 页面访问过程 只显示前十个 endl for i 0 i 10 i fo
11、r j 0 j M j 8 书山有路 if Simulate i j 1 cout elsecout Simulate i j cout endl cout 缺页率 LackNum endl cout 命中率 PageRate endl cout endl voidFIFO FIFO算法 intj x 0 y 0 LackNum 0 Init 初始化for j 0 j M j 将前五个页面请求直接放入内存中 for intk 0 k j k if j k Simulate j k PageOrder j elseSimulate j k Simulate j 1 k LackNum for x
12、 M x MaxNum x for intt 1 t M t Simulate x t Simulate x 1 t if IsExit x 根据新访问页面是否存在内存中来更新页面访问过程 LackNum Simulate x y M PageOrder x y PageRate 1 float LackNum float MaxNum 算出命中率 9 书山有路 AllNum OutPut voidLRU LRU算法 intj x 0 y 0 LackNum 0 Init for j 0 j M j 将前五个页面请求直接放入内存中 for intk 0 k j k PageCount k if
13、 j k Simulate j k PageOrder j elseSimulate j k Simulate j 1 k LackNum for x M x MaxNum x for intt 0 t M t 先将前一次页面访问过程赋值给新的页面访问过程 Simulate x t Simulate x 1 t intp IsExitLRU x if p 1 根据返回的p值来更新页面访问过程 intk k Compare for intw 0 w M w if w k PageCount w elsePageCount k 1 Simulate x k PageOrder x LackNum
14、else 10 书山有路for intw 0 w M w if w p PageCount w elsePageCount p 1 PageRate 1 float LackNum float MaxNum 算出命中率AllNum OutPut voidOPT 最佳访问算法Optimal intj x 0 y 0 LackNum 0 Init for j 0 j M j 将前五个页面请求直接放入内存中 for intk 0 k j k PageCountOPT k if j k Simulate j k PageOrder j elseSimulate j k Simulate j 1 k L
15、ackNum AllNum for x M x MaxNum x for intt 0 t M t 先将前一次页面访问过程赋值给新的页面访问过程 Simulate x t Simulate x 1 t intp IsExitLRU x OPT算法中判断新的页面请求是否在内存中if p 1 根据返回的p值来更新页面访问过程 11 书山有路 intk k CompareOPT x OPT算法找出内存中需要置换出来的页面for intw 0 w M w if w k PageCountOPT w elsePageCountOPT k 1 Simulate x k PageOrder x LackNu
16、m else for intw 0 w M w if w p PageCountOPT w elsePageCountOPT p 1 PageRate 1 float LackNum float MaxNum 算出命中率OutPut voidYourChoice intchoice switch choice case1 cout endl cout FIFO算法结果如下 endl FIFO break case2 cout endl cout LRU算法结果如下 endl LRU break 12 书山有路case3 cout choice YourChoice choice voidmain intchoice i 1 while i cout choice if choice 1 choice 2 choice 3 choice 4 YourChoice choice 13 书山有路七 运行示例及结果分析 14 书山有路 15 书山有路八 心得体会本次课程设计目的是通过请求页式管理中页面置换算法模拟设计 了解虚拟存储技术的特点 掌握请求页式存储管理的页面置换算法 做了这么多次课程
