8虚拟存储器.ppt

Chapter 8: Virtual Memory 基本概念 局部性原理 定义 请求分页存储管理方式 MMU支持 页面分配 调入策略 页面置换算法 性能分析 抖动 Chapter 8: Virtual Memory 请求分段存储管理 Intel 80386存储管理方式 Background 局部性原理 在某个时间间隔内,程序的执行时访问的地址空间局限在某个范围 定义 把作业的一部分装入内存便可运行的存储器系统 具请求调入功能和置换功能,能在逻辑上对内存容量进行扩充的存储器系统 Background 虚拟存储器实现方式 请求分页 请求分段 虚拟存储器特征 离散性 多次性 对换性 虚拟性 Demand Paging Bring a page into memory only when it is needed. Less I/O needed Less memory needed Faster response More users Demand Paging 硬件支持(MMU) 页表支持 页号 物理块号 状态位 访问字段 修改位 外存地址 缺页中断机构 地址变换机构 地址变换过程 硬件操作 软件操作 页面分配 最小物理块数 页面分配和置换策略 固定分配局部置换 可变分配全局置换 可变分配局部置换 分配算法 平均分配 按比例分配 考虑优先权的分配算法 页面调入策略 何时调入页面 预调页策略 请求调页策略 从何处调入页面 交换区 文件区 混合 页面置换算法 最佳置换算法 先进先出置换算法 LRU置换算法 Clock置换算法 最少使用置换算法 页面缓冲算法 Replacement Algorithms Want lowest fault rate. Evaluate algorithm by running it on a particular string of memory references (reference string) and computing the number of page faults on that string. In all our examples, the reference string is 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. First-In-First-Out (FIFO) Algorithm Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 3 frames (3 pages can be in memory at a time per process) 4 frames FIFO Replacement – Belady’s Anomaly more frames ? less page faults Optimal Algorithm Replace page that will not be used for longest period of time. 4 frames example Optimal Algorithm 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 How do you know this? Used for measuring how well your algorithm performs. Least Recently Used (LRU) Algorithm Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 Least Recently Used (LRU) Algorithm Counter implementation Every page entry has a counter; every time page is referenced through this entry, copy the clock into the counter. When a page needs to be changed, look at the counters to determine which are to change. LRU Algorithm (Cont.) Stack implementation – keep a stack of page numbers in a double link form: Page referenced: move it to the top requires 6 pointers to be changed No search for replacement LRU Approxima