《页面置换算法实验(内含完整代码)》由会员分享，可在线阅读，更多相关《页面置换算法实验(内含完整代码)（10页珍藏版）》请在金锄头文库上搜索。
1、实验二 存储管理 一、 实验目的 通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的 特 点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程， 并比较它们的效率。 二、 实验内容 基于一个虚拟存储区和内存工作区，设计下述算法并计算访问命中率。 1、最佳淘汰算法（OPT） 2、先进先出的算法（FIFO） 3、最近最久未使用算法（LRU） 4、简单时钟(钟表)算法（CLOCK） 命中率页面失效次数页地址流(序列)长度 三、 实验原理简述 UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收 均以页为单位进行；一个进程只需将其一部
2、分（段或页）调入内存便可运行；还支持请求 调页的存储管理方式。 当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提 出请求（向CPU发出缺中断） ，由系统将其所需页面调入内存。这种页面调入方式叫请求调 页。 为实现请求调页，核心配置了四种数据结构：页表、页帧（框）号、访问位、修改位、有 效位、保护位等。 当 CPU 接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转 入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果 此时内存未满，能容纳新页，则启动磁盘 I/O 将所缺之页调入内存，然后修改页表。 如果内存已满，则须按某种置换算法从内存中
3、选出一页准备换出，是否重新写盘由 页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要 访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。 四、 算法描述 本实验的程序设计基本上按照实验内容进行。即使用srand( )和rand( )函数 定 义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算 法计算出相应的命中率。 （1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： A：50%的指令是顺序执行的 B：25%的指令是均匀分布在前地址部分 C：25%的指令是均匀分布在后地址部分 具体的实施方法是： A：在0，3
4、19的指令地址之间随机选取一起点m B：顺序执行一条指令，即执行地址为m+1的指令 C：在前地址0,m+1中随机选取一条指令并执行，该指令的地址为m D：顺序执行一条指令，其地址为m+1 E：在后地址m+2，319中随机选取一条指令并执行 F：重复步骤A-E，直到320次指令 （2）将指令序列变换为页地址流 设：页面大小为1K； 用户内存（页帧）容量为4页32页； 用户虚存容量为32K。 在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的 存放方式为： 第 0 条-第 9 条指令为第0页（对应虚存地址为0，9）第10条-第19条指令为第1页（对应虚存地址为10，19） 第
5、310条-第319条指令为第31页（对应虚存地址为310，319） 按以上方式，用户指令可组成32页。 五、 算法实现与分析 1.常量及变量 #define total_instruction 320 /指令流长 #define total_vp 32 /虚页长 #define clear_period 50 /清周期 pfc_type pfctotal_vp, /主存区页面控制结构数组 pfc_type *freepf_head, /主存区页面控制结构的空闲页面头指针 pfc_type *busypf_head, /主存区页面控制结构的忙页面头指针 pfc_type *busypf_tail
6、; /主存区页面控制结构的忙页面尾指针 int diseffect; /页错误计数器，初次把页面载入主存时也当做页错误 pl_type pltotal_vp; /页面结构数组 2.数据结构 typedef struct /页面结构 int pn, /页面序号 pfn, /页面所在内存区的帧号 counter, /单位时间内访问次数 time; /上次访问的时间 pl_type; struct pfc_struct /页面控制结构，模拟内存中的页集int pn, /页面号pfn; /内存区页面的帧号struct pfc_struct *next; /页面指针，用于维护内存缓冲区的链式结构 ;3.
7、函数定义 int initialize(int); /初始化页面结构数组和页面控制结构数组 int FIFO(int); /先进先出算法 int LRU(int); /最近最久未使用算法 int OPT(int); /最佳置换算法 int CLOCK(int); /简单时钟(钟表)算法 六、 实验结果分析 实验数据结果： -随机产生指令流-257 258 37 38226 227 109 110184 185 164 165166 167 59 60310 311 135 136148 149 105 106240 241 121 122124 125 50 51315 316 308 309
8、312 313 299 300315 316 284 285284 285 272 273318 319 216 217310 311 266 267318 319 127 128129 130 52 5353 54 48 49130 131 62 63159 160 107 108206 207 130 131167 168 123 124272 273 23 24123 124 32 33303 304 163 164206 207 134 135269 270 123 124177 178 124 125244 245 54 5568 69 5 6165 166 144 145270 2
9、71 75 7688 89 65 6669 70 31 32 56 57 40 41189 190 73 7492 93 50 5192 93 77 7888 89 62 63125 126 71 72255 256 125 126289 290 97 98235 236 163 164240 241 29 30158 159 80 81280 281 263 264312 313 58 59226 227 78 79121 122 108 109202 203 32 3342 43 18 19153 154 67 68292 293 63 64264 265 54 55269 270 40
10、41296 297 295 296318 319 269 270278 279 214 215222 223 186 187220 221 30 31268 269 33 34226 227 117 118211 212 170 171313 314 77 78248 249 34 35232 233 25 2682 83 59 6061 62 23 24168 169 24 25259 260 239 240318 319 275 276283 284 74 75244 245 144 145244 245 86 87120 121 115 116238 239 209 210275 276
11、 215 216284 285 214 215 285 286 186 187208 209 162 163238 239 41 42 - -不同页面工作区各种替换策略的命中率表- Page FIFO LRU OPT CLOCK4 0.550 0.559 0.669 0.5505 0.566 0.572 0.700 0.5726 0.578 0.594 0.722 0.5787 0.591 0.603 0.741 0.5978 0.631 0.628 0.756 0.6379 0.637 0.656 0.772 0.65010 0.641 0.669 0.787 0.65311 0.656 0
12、.678 0.800 0.66612 0.688 0.684 0.813 0.67213 0.703 0.697 0.822 0.69714 0.713 0.713 0.831 0.71915 0.722 0.728 0.841 0.72216 0.731 0.747 0.850 0.74117 0.744 0.772 0.856 0.74718 0.769 0.778 0.863 0.76919 0.778 0.787 0.869 0.77820 0.781 0.797 0.875 0.79421 0.787 0.800 0.881 0.80622 0.816 0.809 0.887 0.80923 0.822 0.822 0.891 0.82224 0.838 0.831 0.894 0.83825 0.844 0.847 0.897 0.84126 0.847 0.856 0.900 0.85627 0.847 0.869 0.900 0.85928 0.856 0.878 0.900 0.87229 0.859 0.884 0.900 0.87830 0.881 0.891 0.900 0.89131 0.897 0.897 0.900 0.89732 0.900 0.900 0.9
