华东石油大学计算机考研操作系统第四章3.ppt

2. 虚拟存储器 采用软硬件技术将外存当作内存的扩充，用户作业运行时把必不可少的指令或数据装入内存，其余放在外存。当访问的信息不在内存时，由系统自动完成内外存信息交换。这样对用户来说，好象系统拥有一个容量很大的内存，这个扩充了的内存称作虚拟存储器。 虚拟存储器两方面含义  1）一级存储器概念2）作业地址空间概念 对系统：借助于各种表格机构，体现虚拟实间。 对用户：指令地址部分所限定的比实存大得多的地址实间。 3.依据 问题：作业信息不全部装入主存的情况下能否保证作业的正确运行？ 分析 第一、程序往往包含若干个循环，在一段时间里这些程序部分被多次调用(如计数循环、转子程序、堆栈)。 第二，程序在一段时间运行中，往往集中访问某一存储区域中的数据或附近位置的数据(如动态数组、顺序代码)。 第三，程序中有些部分是彼此互斥的，不是每次运行时都用到的，例如出错处理程序，仅当在数据和计算中出现错误时才会用到,正常情况下, 出错处理程序不放在主存,不影响整个程序的运行。 程序局部性原理 （ P.Denning ，1968） 在一段时间内一个程序的执行往往呈现出高度的局部性，它对内存的访问是很不均匀的。 局部性表现为：时间局部性和空间局部性 时间局部性 一条指令被执行了，则在不久的将来它可能再被执行 空间局部性 若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用 4、实现虚存的两个关键问题 1）如何决定当前应该是哪些信息在内存2）当要访问的信息不在内存时如何处理 5、实现虚存所需的物质基础（条件） 1）有足够大的辅存2）一定容量的主存3）自动的地址变换机构 7. 虚拟存储器的容量 一个虚拟存储器的最大容量是由计算机的地址结构确定的。如：若CPU的有效地址长度为32位，则程序可以寻址范围是0～(2^32)-1 ，即虚存容量为 4GB。 虚拟存储器的容量与主存的实际大小没有直接的关系，而是由主存与辅存的容量之和所确定。 1.需要解决的问题 系统需要解决下面问题： 系统如何获知进程当前所需页面不在主存。 当发现缺页时，如何把所缺页面调入主存。 当主存中没有空闲的页框时，为了要接受一个新页，需要把老的一页淘汰出去，根据什么策略选择欲淘汰的页面。 2. 页描述子的扩充 页号、驻留位、内存块号、外存地址、访问位、修改位、（存取控制、辅存地址） 中断位：表示该页是在内存还是在外存 访问位：表示该页最近被访问过，根据访问位来决定淘汰哪页 修改位：查看此页是否在内存中被修改过  3.地址变换与缺页中断 查页表时，当存在位指示该页不在主存时，则引起一个缺页中断发生，相应的中断处理程序把控制转向缺页中断子程序。执行此子程序，即把所缺页面装入主存。然后处理机重新执行缺页时打断的指令。这时，就将顺利形成物理地址。如下图所示。  4.请求分页存储管理地址变换流程 二.页面置换算法 当要放一页面到全满的主存块时，系统需淘汰一页。用来选取淘汰哪一页的规则，叫置换算法。 “抖动”或“颠簸”： 频频的页面置换。 “抖动”现象的出现会使系统效率急剧下降，甚至导致系统的崩溃。 最佳置换算法 (OPT) 先进先出置换算法 (FIFO) 最近最久未用置换算法 (LRU) 近似的LRU算法（NRU算法） 1.最佳置换算法 思想：当发生缺页中断时，此算法把在将来最长时间不用的页面置换出内存 。 最佳置换算法是由Belady于1966年提出的一种理论上的算法。 采用最佳置换算法，通常可保证获得最低的缺页率。 前提：为便于讨论页面置换算法的优劣，我们一般在固定主存页面数及在作业的某页面走向的前提下，讨论使用置换算法调度之后缺页的次数。即假设分配给每个作业的主存空间固定为某一确定的主存块数且把对作业某地址的访问转换为对应页面的访问来讨论缺页数，并以此来衡量算法的优劣，这样有助于问题的简化。 例：假设分配给作业的内存块数为3，某一作业的页面走向分别为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。 2. 先进先出(FIFO)页面置换算法 分析1 此算法是最简单的页面置换算法。此算法容易实现，可以通过设置循环队列这一数据结构来记录作业在内存中页面的页号，队列头指针用于指出最先进入内存的页面。当发生缺页中断时，指针指向的页面被换出，然后指针循环后移一项。 例如：系统中设置一张具有m个元素的页号表，它是由Ｍ个数： P[0], P[1], …, P[m-1]所组成的一个数组， 其中每个P[i] (i =0,1,…m-1) 存储一个在主存中的页面的页号。 假设用指针k指示当前调入新页时应淘