16第5章虚拟存储器管理.ppt

最多使用（Most Frequently Used)置换算法 较少的引用数,则刚调入并将使用,择引用次数大的置换 改进型Clock置换算法 请求分段的硬件支持 请求分段系统中的缺段中断处理过程 段的共享 程序的结构：(页面大小=128字)初始int a[128][128]为0 for (i=0;i128;i++) for (j=0;j128;j++) a[i,j]=0 ; for (j=0;j128;j++) for (i=0;i128;i++) a[i,j]=0 ; a[0][0]，a[0][1]，a[0][2] , ……a[0][127] a[1][0]，a[1][1]，a[1][2] ,……a[1][127] ………….. a[127][0]， …………. a[127][127] 编制程序对缺页率的影响 数组内存中是按行排列的 (即每行占一个页面)(如分配一块给数组) 128-1次缺页 128*128 -1=214 -1=16K-1次缺页 方式A 方式B 页面大小对系统性能的影响 小页面 大页面 3)恢复进程时间 + 2)读页面时间 + 1)缺页中断服务时间 寻道时间15ms+磁盘延迟时间8 ms+ 传输时间1ms=24ms 缺页处理时间 1)缺页中断服务时间+3)恢复进程时间=1ms ,内存存取=100ns 如果页面大，则系统从磁盘上读入页面到内存的次数少，有利于提高I/O的效率。 小页面 小页面 磁盘驱动器 (DMA方式) 磁盘驱动器 （DMA方式） 系统区 进程页面 进程请求I/O 释放CPU 全局置换时淘汰该页 数据传输 1）增加系统存储区 2）对页面进行加锁 解决方法 系统防止解锁失效，使该块作废 I/O互锁 页面2 页面1 页面0 块I 块J 块K 页面2 页面1 页面0 写时复制(FORK) 页面2 页面1 页面0 块I 块J 块K 页面2 页面1 页面0 写时复制后 块M 增补位 修改字段M 存取方式 段长 外存地址 存在位P 访问字段R 段的基址 段名 段在内存? 段是否被修改？ E、R、R/W 记录该段被访问的频繁程度 能否动态增长? 段在外存的存放地址 1)段表机制 2)缺段中断 3)地址变换机构 4)(内/外存) 5.5 请求分段存储管理方式 5.3.2 最近最久未使用（LRU）页面置换算法 最近最久未使用(Least Recently Used，LRU)页面置换算法 FIFO置换算法 最佳置换算法 淘汰在内存留驻时间最长的页面 淘汰将来最长时间不被使用的页面 如果用最近的过去代替最近的将来，即选择最近过去最长时间已经不被使用的页面首先淘汰，同样也能获得好的性能。 Pt …… Pn …… P2 P1 产生缺页 最久未使用的页 最近点 赋予每个内存页面一个访问字段，用来记录页面自上次被访问以来所经历的时间T，当淘汰一页面时，选择现有页面中其T最大的。 LRU算法的基本思想是：利用局部性原理，根据一个作业在执行过程中过去的页面访问踪迹，来推测未来的行为，认为过去一段时间里不曾被访问的页面，在最近的将来可能也不会再被访问。这种算法的实质是；当需要置换一页时，选择在最近一段时间内，最久不用的页面予以淘汰 Pt …… Pn …… P2 P1 产生缺页 T …… …… T2 T1 实现方法 表示上次访问的时间，则T-Ti=最大 2 0 4 2 3 0 4 4 0 3 0 2 3 0 1 0 2 2 1 0 7 1 0 7 0 7 7 1 0 7 1 0 2 1 2 3 0 3 2 0 1 2 3 1 2 3 0 2 3 4 7 0 1 访问次数=20次，M=3, 置换次数=9 ，缺页次数=9+3=12 由于LRU算法能够合理地预测程序运行状态，可以针对不同的引用串进行，具有很好的置换性能，一直被公认为一种性能好且可以实现的页面置换算法。 计数器 堆栈 LRU算法的实现 如何确定已经访问过的最近最久页面？ 寄存器 使用时间域 ……………. 块号 进程页表项目增加一项表示时间 CPU的逻辑时钟或计数器 1．计数器方式 1)时间域的更新 2)页面置换时的查找 3)时钟溢出的问题 系统的开销 栈底 …… …… 栈的大小=分配的块数 压栈指针 a 初态 访问a a b 访问b a b c 访问c 访问d b c a 访问a b c a d 访问e c a d e 栈底:LRU页面 栈顶:最近使用过的页页 2．堆栈方式 当一个页面被使用时，它被压入堆栈顶部 b被换出 1 0 0 0 0 1