Microsoft PowerPoint - Chapter4_Memory.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - Chapter4_Memory.pptx"

旭芒友
5 years ago
Views:

LRU-the hardware array Associate counter with each page. At each reference increment counter. Evict page with lowest counter Keep n x n array for n pages.

1 LRU-the hardware array Associate counter with each page. At each reference increment counter. Evict page with lowest counter Keep n x n array for n pages.upon reference page k, put 1 s in row k and 0 s in column k. Row with smallest binary value corresponds to LRU page. Evict k! Easy hardware implementation Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved LRU-hardware LRU using a matrix when pages are referenced in the order 0, 1, 2, 3, 2, 1, 0, 3, 2, 3. Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved

Prentice-Hall, Inc. All rights reserved.

2 LRU-software Hardware uses space=> software implementation Make use of software counters Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved LRU in Software Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved

3 LRU-software aging algorithm Keep a string of values of the R bits for each clock tick (up to some limit) After tick, shift bits right and add new R values on the left On page fault, evict page with lowest counter Size of the counter determines the history Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved 最不频繁使用算法 (LFU, Least Frequently Used) 选择到当前时间为止被访问次数最少的页面被置换 ; 每页设置访问计数器, 每当页面被访问时, 该页面的访问计数器加 1; 发生缺页中断时, 淘汰计数值最小的页面, 并将所有计数清零 ; 也称为 NFU, Not Frequently Used 3

4 页面缓冲算法 (page buffering) 它是对 FIFO 算法的发展, 通过被置换页面的缓冲, 有机会找回刚被置换的页面 ; 被置换页面的选择和处理 : 用 FIFO 算法选择被置换页, 把被置换的页面放入两个链表之一即 : 如果页面未被修改, 就将其归入到空闲页面链表的末尾, 否则将其归入到已修改页面链表工作集模型 Demand paging-bring a process into memory by trying to execute first instruction and getting page fault. Continue until all pages that process needs to run are in memory (the working set) Try to make sure that working set is in memory before letting process run (pre-paging) Thrashing-memory is too small to contain working set, so page fault all of the time Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved

5 Behavior of working set as a function of k W(k,t) is number of pages at time t used by k most recent memory references Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved How to implement working set model When fault occurs can evict page not in working set (if there is such a page) Need to pick k Could keep track of pages in memory at every memory reference. Each k references results in a working set. Shift register implementation. Insert page number at each reference. Expensive Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved

6 工作集策略 (working set strategy) 引入工作集的目的是依据进程在过去的一段时间内访问的页面来调整常驻集大小定义 : 工作集是一个进程执行过程中所访问页面的集合, 可用一个二元函数 W(t, ) 表示, 其中 :t 是执行时刻 ; 是窗口尺寸 (window size); 工作集是在 [t -, t] 时间段内所访问的页面的集合, W(t, ) 指工作集大小即页面数目 ; 工作集大小的变化 : 进程开始执行后, 随着访问新页面逐步建立较稳定的工作集当内存访问的局部性区域的位置大致稳定时, 工作集大小也大致稳定 ; 局部性区域的位置改变时, 工作集快速扩张和收缩过渡到下一个稳定值 6

7 困难 : 工作集的过去变化未必能够预示工作集的将来大小或组成页面的变化 ; 记录工作集变化要求开销太大 ; 对工作集窗口大小的取值难以优化, 而且通常该值是不断变化的 ; 几种常见页面置换算法的比较现代操作系统 P121 7

8 分配和置换策略固定分配, 局部置换可变分配, 全局置换可变分配, 局部置换教材 P188 初始页面配置局部页面置换全局页面置换 8

9 改善时间性能的途径降低缺页率 : 缺页率越低, 虚拟存储器的平均访问时间延长得越小 ; 提高外存的访问速度 : 外存和内存的访问时间比值越大, 则达到同样的时间延长比例, 所要求的缺页率就越低 ; 高速缓存命中率抖动问题 (thrashing) 随着驻留内存的进程数目增加, 或者说进程并发水平 (multiprogramming level) 的上升, 处理器利用率先是上升, 然后下降这里处理器利用率下降的原因通常称为虚拟存储器发生抖动, 也就是 : 每个进程的常驻集不断减小, 缺页率不断上升, 频繁调页使得调页开销增大 OS 要选择一个适当的进程数目, 以在并发水平和缺页率之间达到一个平衡 9

10 抖动的预防 : 降低并发程度局部置换策略工作集算法预留部分页面挂起若干进程缺页频度法工作集与缺页率 Working set Page fault rate transition stable

11 请求分段式在简单段式存储管理的基础上, 增加请求调段和段置换功能地址变换和缺段中断 : 指令和操作数必定不会跨越在段边界上保护界限保护 ( 上下界界限地址寄存器 ): 所有访问地址必须在上下界之间 ; 用户态与内核态存取控制检查环保护 : 处理器状态分为多个环 (ring), 分别具有不同的存储访问特权级别 (privilege), 通常是级别高的在内环, 编号小 ( 如 0 环 ) 级别最高 ; 可访问同环或更低级别环的数据 ; 可调用同环或更高级别环的服务 11

12 Unix 中的存储管理由于 UNIX 可在多种平台上运行, 其存储管理差异十分大这里我们介绍 Solaris 2.x 的存储管理系统 Solaris 的存储管理系统分成两部分 : 对换系统 (paging system) 和内核存储分配器 (kernel memory allocator) 对换系统 : 为进程和磁盘缓存提供页式虚拟存储管理 ; 内核存储分配器 : 为内核提供内存分配服务 ; 12

13 对换系统对换系统的数据结构页表 (page table): 每个进程有一个页表, 进程逻辑空间的每页对应页表中的一个表项 ; 硬盘块描述表 (disk block descriptor): 该表表项与页表表项一一对应, 描述该页在磁盘上的副本 ; 页面表 (page frame date table): 按物理页面号排序, 描述每个物理页面 ; 对换表 (swap-use table): 每个磁盘对换区有一个对换表, 该对换区上的每个页副本对应一个表项 ; 双指针轮转置换算法 (Two-Handed Clock Page-Replacement Algorithm) 利用页面表上的几个指针维护一个空闲页面表当空闲页面数少于一定阈值时, 该算法置换一些页面加入空闲页面表 Fronthand 清空 R 位 Backhand 置换 R=0 的页面 End of Page List Fronthand Backhand Beginning of Page List Fronthand 和 Backhand 之间的夹角有什么影响? 扫描的速度有什么影响? 13

14 内核存储分配特征内核存储分配器内核需要分配和释放小内存块, 用于内核的数据结构和缓冲区 ; 这些内存块通常比物理页面要小许多 ; 这些内存块的分配和释放要求快速进行 ; 分配和释放的内存块的大小变化是缓慢的惰性动态分区算法 (lazy buddy system) 惰性动态分区算法 : 该算法是一种动态分区算法分配的分区大小可变, 但只能为 2 K 释放的分区并不马上合并, 而是维持一定数目的各种大小的空闲分区 ; 当空闲分区超过一定数目时, 才合并 14

15 该算法维护的参数 : N i 表示大小为 2 i 的分区数目 ; A i 表示大小为 2 i 的已分配分区数目 ; G i 表示大小为 2 i 的适合合并空闲 (globally free) 分区数目 ; L i 表示大小为 2 i 的不适合合并空闲 (locally free) 分区数目 ; 我们有如下关系 : N i = A i + G i + L i ; 合并的判断条件 : 要求 Li Ai; 依据它们的差来决定是否合并 : 差为 0 或 1 时进行合并, 大于 1 时不合并 Windows NT 中的存储管理 FFFFFFF 用户存储区专用进程地址空间 : 用户代码数据和堆栈 ; 线程环境块 (TEB): 用户态代码可修改的线程控制信息 ; 进程环境块 (PEB): 用户态代码可修改的进程控制信息 ; 共享用户数据页 : 系统存储区映像, 为用户态可访问的系统空间, 目的在于避免用户态与核心态的频繁切换 ; 如 : 系统时间 BFFFFFFF C FFFFFFFF 直接映射区页交换区固定页面区固定页面区 : 永不被换出内存的页面 ; 如 : HAL 特定的数据结构 ; 页交换区 : 非常驻内存的系统代码和数据 ; 如 : 进程页表和页目录 ; 直接映射区 : 常驻内存且寻址由硬件直接变换的页面, 访问速度最快 ; 用于存放内核中频繁使用且要求快速响应的代码 15

16 地址转换 NT 使用 2 级页表结构转换虚拟地址, 第一级称为页目录 ( 每个进程一个页目录 ), 第二级称为页表每个页目录或页表有 1024(2 10 ) 个表项, 每个表项为 4 字节由于每个页面为 4KB, 每个进程的地址空间可为 4GB(2 10 *2 10 *2 12 ) 页面调度策略页面调度策略包括取页策略置页策略和淘汰策略取页策略 :NT 采用按进程需要进行的请求取页和按集群方法进行的提前取页集群方法是指在发生缺页时, 不仅装入所需的页, 而且装入该页附近的一些页置页策略 : 在线性存储结构中, 简单地把装入的页放在未分配的物理页面即可淘汰策略 : 采用局部 FIFO 置换算法在本进程范围内进行局部置换, 利用 FIFO 算法把驻留时间最长的页面淘汰出去 16

17 工作集策略 NT 根据内存负荷和进程缺页情况自动调整工作集进程创建时, 指定一个最小工作集 ( 可用 SetProcessWorkingSetSize 函数指定 ); 当内存负荷不太大时, 允许进程拥有尽可能多的页面 ; 系统通过自动调整保证内存中有一定的空闲页面存在 ; 页面状态 NT 的页面有 6 种状态 : 有效状态 : 某进程正在使用该页面 ; 清零状态 : 空闲且已被清零 ; 空闲状态 : 空闲但尚未被清零 ; 备用状态 : 已标记为无效, 但可快速回到有效状态 ; 修改状态 : 已标记为无效, 但对该页面内容的修改尚未写入外存, 可快速回到有效状态 ; 坏页状态 : 该页面产生硬件错, 不能再用. 17

18 小结存储组织 ( 层次 ), 存储管理功能重定位和装入静态链接和动态链接存储管理方式 : 单一连续区管理, 分区管理 ( 静态和动态分区 ) 覆盖, 交换页式和段式存储管理 : 原理, 优缺点, 数据结构, 地址变换, 分段的意义, 两者比较虚拟存储器局部性原理, 虚拟存储器的原理种类 ( 虚拟页式段式段页式 ), 缺页异常存储保护和共享调入策略分配策略和清除策略置换策略工作集策略 18

19 问题? 19

<4D F736F F F696E74202D DB5DAB6FECAAEB6FEBDB22DCEA2D0CDBCC6CBE3BBFACFC8BDF8BCBCCAF5CAB5C0FDA3A8D2BBA3A92E >

<4D F736F F F696E74202D DB5DAB6FECAAEB6FEBDB22DCEA2D0CDBCC6CBE3BBFACFC8BDF8BCBCCAF5CAB5C0FDA3A8D2BBA3A92E > 第二十二讲授课教师 : 陆俊林王箫音 2012 年春季学期主要内容一实模式回顾二虚拟存储机制三保护模式四 64 位模式五多线程技术教材相关章节 : 微型计算机基本原理与应用 ( 第二版 ) 第 15 章 80x86/Pentium 保护模式原理与结构 1 主要内容一实模式回顾二虚拟存储机制三保护模式四 64 位模式五多线程技术 2 回顾 : 三种工作模式之间的转换