第4章虚拟存储器(3).ppt

1、4.6 虚拟存储器的基本概念,4.6.1 问题的提出 程序大于总内存 多个程序要运行内存只能容纳部分作业 虚拟存储器的基本思想是: 程序、数据、堆栈的大小可以超过内存的大小, 操作系统把程序当前使用的部分保留在内存, 而把 其它部分存在磁盘上, 需要时在内存和磁盘之间动态对换。 虚拟存储器支持多道程序设计技术。,2. 程序局部性原理 在一段时间内一个程序的执行往往呈现出高度的局部性, 顺序执行的多, 过程调用, 循环结构, 对数组操作等等。表现为: 时间局部性： 一条指令被执行了，则在不久的将来它可能再被执行。 空间局部性： 若某一存储单元被使用，则在一定时间内, 与该存储单元附近的单元可能被

2、使用。,3. 虚拟存储技术,以CPU时间和外存空间换取昂贵内存空间, 这是操作系统中的资源转换技术。 虚存: 把内存与外存有机的结合起来使用, 从而得到一个容量很大的“虚内存”。 实现思想: 当进程运行时, 先将一部分程序装入内存, 另一部分暂时留在外存, 当要执行的指令不在内存时, 由系统自动将它们从外存调换到内存。即具有请求调入和置换功能。,4.6.2 虚拟存储器的实现方式,请求分页方式 分段请求方式 硬件支持： 请求分页(段)的页(段)表机构 缺页(段)中断机构 请求分页(段)的地址变换机构,4.6.3 虚拟存储器的特征,离散性: 是实现虚拟存储器的基础 多次性: 多次将部分调入内存,

3、运行时再调入 交换性: 暂时不执行换出, 需要时再换入 虚拟性: 逻辑(虚)上扩充了内存物理(实)容量,CPU,MMU,内存,磁盘 控制器,总线,CPU把虚地址送给MMU,MMU把物理地址送给存储器,页 号 P 页 内 位 移 量 W,31 11 0,4. 虚拟地址结构,页的大小=？ 页的多少=？ 虚存的大小=？,4.7 请求分页式存储管理,在进程开始运行之前, 不是装入全部页面,而是装入一个或零个页面, 之后根据进程运行的需要, 动态装入其它页面; 当内存空间已满, 而又需要装入新的页面时, 则根据某种算法淘汰某个页面, 以便装入新的页面。 4.7.1 硬件支持及工作过程 1、页表机制 状态

4、位P：表示该页是在内存还是在外存 访问位：记录该页在一段时间内被访问的次数 修改位：查看此页是否在内存中被修改过,2、缺页中断机构 在地址映射过程中, 在页表中发现所要访问的页不在内存, 则产生缺页中断。操作系统接到此中断信号后, 就调出缺页中断处理程序,根据页表中给出的外存地址, 将该页调入内存,使进程继续运行下去。 如果内存中有空闲块, 则分配一页将新调入页装入内存, 并修改页表中相应页表项目的驻留位及相应的内存块号。若此时内存中没有空闲块, 则要淘汰某页, 若该页在内存期间被修改过, 则要将其写回外存。,4.地址变换,影响缺页次数的因素,(1) 分配给进程的物理页面数 (2) 页面本身的

5、大小 (3) 程序的编制方法 (4) 页面淘汰算法,4.7.2 页面分配与置换,请求调页中操作系统提供的支持 请求调页时, 把所需的页从外存调入内存 置换时, 将内存的某些页调至外存 问题： 进程正常运行所需的最少物理块是多少？ 每个进程分配的物理块数是固定的吗？ 每个进程分配的物理块数依据是什么？,1. 策略最小物理块数 最小物理块数与硬件结构、指令格式、寻址方式有关。 直接寻址方式最少块数为2 间接寻址方式最少块数为3 功能较强的机器最少块数为6 2. 页面分配和置换策略(固定分配、可变分配) 1) 固定分配局部置换 系统中驻留的进程数与分配给进程的页数是什么关系？（正比？反比？） 块数太

6、多会出现什么问题？ 块数太少会出现什么问题？,2) 可变分配全局置换 空闲物理块由谁管理？(OS?进程？） 缺页中断时从何处获得空闲页？ 调入调出什么时候发生（空闲页用完还是给进程分配的页用完？） 3) 可变分配局部置换 为每个进程所分配的物理块数相对固定 从每个进程所分配的页面中进行换入换出。 从全局的角度动态调整每个进程所分配的页面,3. 分配算法(固定分配策略） 平均分配算法 驻留内存的进程平均分配, 貌似公平, 实际不公平, 长进程缺页率高 按比例分配算法 按驻留内存的进程的大小比例分配, 较公平 考虑优先权的分配算法 整个内存分为两部分, 一部分按比例分配, 另一部分按优先权分配,

7、照顾到重要紧迫的进程尽快完成,4.7.3 页面调入,什么时候调入？从何处调入？怎么调入？ 1.什么时候调入 预调入策略: 一次调入若干相邻页(预计即将运行的页)比单页调入效率高, 命中率约50%。 请求调页策略: 缺页时提出请求, OS将所需一页调入内存, 易于实现, I/O启动频率高系统开销大。 2. 从何处调入页面 系统有足够的对换区时, 运行前全部从文件区调入对换区, 运行中全部从对换区调入所需页。 系统缺少足够的对换区时, 不会被修改的页从文件区调入, 会被修改的页从对换区调入换出。,4.8.1 页面置换算法 好的页面置换算法应具有低的页面更换频率 最佳置换算法 先进先出算法 最近最久

8、未使用LRU 算法 CLOCK算法,4.8 页面置换算法,最佳置换算法 淘汰永不使用或最长时间内不再被访问的页 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 2 7 0 0 0 0 4 0 0 0 1 1 3 3 3 1 1 无法实现, 只能用它做评价标准。 2.先进先出置换算法 简单易行 没有考虑访问频度的差别, 不能保证经常访问的页不被淘汰。,3. 最近最久未使用LRU 算法,淘汰在最近最久未使用的页面。 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 4 4 4 0 1 1

9、1 0 0 0 0 0 0 3 3 3 0 0 1 1 3 3 2 2 2 2 2 7 4. Linux 的LRU算法 最初分配某个页时, 页的寿命为3, 每次页被访问, 其寿命增加3, 直到20为至。当内核的交换进程运行时(kswapd周期运行), 在内存的所有页面寿命减1。如果某个页的寿命为0，则该页作为交换候选页。,5. 简单的CLOCK置换算法,每页设置一访问位A, 当某页被访问时, 其访问位A被置为1。将内存中所有页面都通过链接指针链接成一个循环队列, 进行循环检查。 如果页的访问位A=0, 则淘汰该页; 若A=1, 则重新将A置为0, 暂不换出而给该页第二次驻留内存的机会。继续向后

10、循环检查直到某页访问位A=0, 则淘汰之。,6. 改进的CLOCK算法 页面换出时,如果该页已被修改, 必须将它重新写到磁盘上; 但如果该页未被修改, 则不必写回磁盘。改进的CLOCK算法增加置换代价这一因素, 用修改位M表示, 优先考虑M=0 (未被修改)的页, 淘汰顺序为: A=0, M=0 A=0, M=1 A=1, M=0 A=1, M=1 其执行过程分为三步： (1) 寻找A=0且M=0, 找到则淘汰该页, 此遍不修改A。 (2) 第一步失败, 则进行第二轮扫描, 寻找A=0且M=1, 找到则淘汰该页。此遍将所有经过的页面A置0； (3) 第二步也失败, 则此时所有页的A=0。重复第

11、一步, 如果仍失败, 再重复第二步, 一定能找到被淘汰的页。,7. 页面缓冲算法 采用前面介绍过的可变分配局部置换方式, 内存中一部分作为页面缓冲区, 将缓冲区的物理快链接为两个链表,空闲链表,页修改页面的链表,页面缓冲算法,页面缓冲采用FIFO置换算法。当需要读入一个页面时, 利用空闲链表的第一个物理快装入该页。 如果被淘汰的页面未被修改, 就将它直接链接到空闲链表表尾, 否则, 则将其链接到已修改的链表表尾。该页面仍留在内存中, 并未进行实际的换出。 当进程再次访问这些页面时, 只需花费较小的开销，使该页面又返回该进程的驻留集。 当被修改页面达到一定数量时，再将它们一起写回磁盘。显著地减少

12、了磁盘I/O的次数。,4.8 请求分段存储管理方式 4.8.1 硬件支持及工作过程,1、段表内容 增加：特征位(在/不在内存, 是否可共享), 存取权限位(只执行,只读, 可读写), 修改位(是否修改过, 能否移动), 增补位(是否动态增长过) 2、越界中断处理 进程在执行过程中, 有时需要扩大分段, 如数据段; 由于要访问的地址超出原有的段长, 发出越界中断; 操作系统处理中断时, 首先判断该段的扩充位,如可扩充, 则增加段的长度; 否则按出错处理。,3、缺段中断处理 检查内存中是否有足够的空闲空间 a. 若有, 则装入该段, 修改有关数据结构, 中断返回 b. 若没有, 检查内存中空闲区的

13、总和是否满足要求,是则应采用紧缩技术, 转a; 否则, 淘汰一些段, 转a 4、地址变换 请求分段系统的地址变换机构, 是在分段系统的地址变换机构基础上, 增加缺段中断的请求和处理等功能,当发现要访问的段不再内存时, 必须将该段调入内存并修改段表, 然后才能用段表进行地址变换。,分段存储管理方式便于实现分段的共享与保护, 只需在每个进程的段表中用相应的表项指向共享段在内存的起始地址。为了管理好共享段, 系统配置相应的数据结构作为共享段表。 共享段表 共享段的分配和回收 分段保护,4.8.2 分段的共享与保护,1. 共享段表 系统为所有共享段配置一张共享段表, 每个共享段在该表中占一个表项, 其

14、中记录了段号、段长、内存始址、存在位等信息, 同时还记录了共享进程计数和共享此分段的每个进程的情况。,共享段表,共享段表项,2. 共享段的分配和回收 共享段的分配 对第一个请求使用该共享段的进程, 系统为该共享段分配一物理区并把共享段调入该区, 同时把该区的始址填入该进程的段表中, 还需在共享段表中增加一表项, 填写有关信息, 把count置为1。 当又有其它进程要访问该共享段时, 只需在访问进程的段表中增加一表项, 填入该共享段的物理地址; 并在共享段表的对应表项中, 填写调用进程名和存取控制等, 再执行count:= count+1 操作。 共享段的回收 取消该进程的段表中共享段所对应的表项,并执行count:= count-1, 结果为0则回收共享段的内存并取消该进程在共享段表中对应的表项; 否则仅取消该进程在共享段表中对应的纪录。,3. 分级保护 各分段在逻辑上是独立的, 容易实现信息保护 越界检查 在分段系统的地址变换