第八章 虚拟存储器.ppt

1、第八章 虚拟存储器管理,基本概念 请求分页的存储器系统 页面置换算法 请求分段的存储器系统,8.1 基本概念,1.虚拟存储器的引入 （1）局部性原理 时间的局部性 空间的局部性 （2）定义 把作业的一部分装入内存就可运行的存储器系统是虚拟存储器系统。 虚拟存储器系统是指能从逻辑上对内存容量进行扩充，并具有请求调入和置换功能的一种存储器系统。,2. 虚拟存储器的实现方法 请求分页的存储器管理系统 请求分段的存储器管理系统 段页式的虚存管理系统 3.虚拟存储器的特征 离散性 多次性：作业被分成多次装入内存。 对换性 虚拟性：从逻辑上扩充内存容量。,5.1 基本概念,注：虚拟性是以多次性和对换性为基

2、础。,4.虚拟地址与实地址 虚拟地址：在虚存管理系统中，通常把运行进程访问的指令和数据的逻辑地址（目标程序中的相对地址）称为虚拟地址。虚拟地址的集合称为虚拟地址空间。 实地址：是指CPU能直接访问的存放指令和数据的主存地址。主存也称为实地址空间。,5.1 基本概念,8.2 请求分页的存储器系统,在基本分页系统的基础上，增加了请求调页和页面置 换功能的页式虚拟存储器系统。 1.请求分页的硬件支持 （1）页表、快表和反向页表,其中：有效位：表示该页是否在内存； 修改位：表示该页调入内存后是否被修改过； 保护权限：可读/可读写,活动页表：由页表寄存器指出的进程页表称为活动页表。 在单处理机系统中，通

3、常有两个活动页表：当前活动进程的活动页表和内核活动页表。,8.2 请求分页的存储器系统,快表 快表由硬件实现，一般有64256个表目。每个快表表目包含若干个项，如： 虚页号 物理块号 保护权限 进程号 有些系统中有两个分离的快表（如IBM RS/6000）： 数据快表（128个表目） 指令快表（32个表目）,8.2 请求分页的存储器系统,实际上，快表的查找与页表的查找是同时进行的，快表 查找成功，就自动停止对页表的查找。,反向页表 反向页表中的每一个表目对应主存中的一个物理块号（反向页表的索引号）。每个表目包括： 其映射的虚页号 指向哈希链的下一指针 有效位、引用位、修改位 保护和加锁信息 使

4、用反向表的系统采用哈希技术完成逻辑地址到物理地址的转换。（参见教材P170图9.3）,8.2 请求分页的存储器系统,（2）缺页中断机构 产生和处理缺页中断的机构。 缺页中断与一般中断的区别： 在指令执行期间产生和处理中断信号 一条指令执行期间可能产生多次缺页中断,B：,A：,COPY A TO B,1,2,3,4,5,6,8.2 请求分页的存储器系统,地址变换 在基本分页系统的地址变换机构的基础上增加了 产生和处理缺页中断的功能。 过程如图所示：,8.2 请求分页的存储器系统,开始,页号页表长?,是,越界中断,该页在快表 中？,该页在内存否？,修改A和M,修改快表,形成物理地址,保存CPU现场

5、,从外存中找到缺页,内存满否？,换页处理,该页被修改否？,将该页写回外存,读缺页,换缺页入内存,修改页表,是,是,是,是,否,否,否,否,访问页表,结束,（3）MMU MMU是内核主存管理子系统依赖的低层硬件，主要任务完成虚地址到物理地址的转换，包括： 管理硬件的页表基址寄存器 将虚地址分为虚页号和页内位移 页面失效处理 设置页表中相应的访问位、修改位、检查有效位和保护权限,8.2 请求分页的存储器系统,2.页面分配的有关策略 （1）最小物理块数的确定 最小物理块数是指能保证进程正常运行所需要的最 少物理块数。 相关因素：机器指令的格式、功能 和寻址方式。 （2）页面分配和置换策略 固定分配局

6、部置换 可变分配全局置换 可变分配局部置换,8.2 请求分页的存储器系统,（3）页面分配方法 平均分配：每个进程分配的物理块数相同 按比例分配：按进程页面数的多少进行分配,注：m为系统可用物理块数 si为每个进程的页面数 bi为每个进程分配的物理块数,考虑优先权分配,8.2 请求分页的存储器系统,3.页面调入策略 （1）调入页面的时机 预调页策略：执行前先调入若干不久将被访问的页面 请求调页策略：缺页时请求调入页面，每次只调入一页。 （2）从何处调入页面 系统有足够的对换区空间：所有页面从对换区调入。 系统的对换区空间不足：不会被修改的页面从文件区调入。 Unix方式：未运行过的页面从文件区调

7、入,8.2 请求分页的存储器系统,4.页面的调入过程,该页在内存？,有空闲物理块？,保留CPU现场,调入所需页,选择一页换出,该页修改否？,写回外存,恢复CPU现场,继续执行,变换地址并执行,否,否,是,是,是,产生缺页中断,1.页面访问失效的原因 边界错误：如页号超过页表的长度。 有效性错误：要访问的页面不在内存，即有效位为零。 保护错误：不允许的访问权限。,8.3 页面置换算法,最佳置换算法（OPT） 最近未使用置换算法（NRU） 先进先出置换算法（FIFO） 二次机会置换算法 时钟页面置换算法（CLOCK） 最近最久未使用置换算法（LRU） 改进型Clock（近似LRU）算法,2. 页面

8、置换算法,2. 页面置换算法,（1）最佳置换算法（OPT） 该算法是Belady在1966年提出的一种理论上的算法。为保证缺页率最低，选择永久不使用，或在最长时间内将不再被访问的页面淘汰。 这种算法在实际中一般很难实现。 例：假设分配给某进程的页架数为3，采用请求调页方式，采用最佳置换算法，求下列页面执行序列的缺页率。 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,1,7,0,1,（2）最近未使用置换算法（NRU） 淘汰最近未使用的页面，而且最好是未被修改的页面。即淘汰的页面最好是访问位和修改位同时为零的页面。 为了避免系统中所有的页面的访问位和修改位可能都为“1”的情况

9、，系统周期性地将主存中页面的访问位清“0”。,2. 页面置换算法,（3）先进先出置换算法（FIFO） 淘汰页面时，选择最先进入的页面。 缺点：该算法只是在按线性顺序访问地址空间时才具有较高的效率，否则可能出现抖动现象。 例：假设分配给某进程的页架数为3，采用请求调页方式，页面置换算法用FIFO，求下列页面执行序列的缺页率。 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,1,7,0,1,2. 页面置换算法,（4）二次机会置换算法 该算法是 FIFO算法的一种改进。淘汰时，首先检查FIFO链首页面的访问位，如果为“0”，则立即淘汰，如果为“1”，则将其移到当前FIFO链的链尾

10、，再检查新的链首页面，直到找到一个访问为“0”的链首页面。,2. 页面置换算法,（5）时钟页面置换算法 将二次机会置换算法中的FIFO链组织成一个环状队列，设一指针指向当前最老的页面。当产生缺页中断时，如果指针所指向的页面的访问位为“0”，则淘汰，将新调入的页面插入到指针指向的位置，指针前移； 如果访问位为“1”，则将其清“0”， 指针前移，直到找到一个访问位 为“0”的页面。,2. 页面置换算法,（6）最近最久未使用（LRU）算法 原理 根据页面在内存中的使用情况，选择最近最久未使用 的页面予以淘汰。即以“最近的过去”预测“最近的将来”。 硬件LRU法 1）寄存器 需为内存中的每一页配置一移

11、位寄存器，用来记录各页 在内存中的使用情况。假设N位寄存器的表示形式为： R= Rn-1Rn-2Rn-3R2R1R0,2. 页面置换算法,实现原理：当进程访问某物理块时，就将相应寄存器的Rn-1位置1，各寄存器根据系统时钟，每隔一定时间右移一位，各寄存器所中表示值最小的那个页面将是下一个被淘汰的页面。,2. 页面置换算法,访问页1后右移一位：,页1,页2,页1,页2,淘汰页2,访问页1,1,1,2）栈实现的LRU法 存放当前使用的各页面的页号。 实现原理：当进程访问某页时，就将该页的页号从栈底移出压入栈顶，或将新访问的页号压入栈顶。处于栈底的就是最近最久未使用的页面号。 例：假设某进程的页面引

12、用顺序为：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。假设系统分配给该进程的物理块为3，并采用请求调页策略，则栈的变化情况如下图所示：,2. 页面置换算法,0,2,1,0,7,3,0,4,2,3,0,2,3,1,2,0,7,0,1,缺页率=13/20=65%,2. 页面置换算法,缺页率：缺页次数与进程页面总数的比值。,3）矩阵实现的LRU算法（参考教材P185186）,LRU算法虽然能够实现，但需要增加成本和开销。,（7）改进型Clock（近似LRU）算法 原理 为内存中所有的页面设置一访问位和一修改位，置初值为0，并将这些页通过指针链接成循环队列。在选择淘

13、汰页时，尽量选择那些访问位和修改位都0的页面，如果没有这样的页面，再考虑访问位为0，而修改为1的页面做为淘汰页。 由访问位A和修改位M组成的页面类型有： 第一类页面：A=0，M=0； 第二类页面：A=0，M=1； 第三类页面：A=1，M=0； 第四类页面：A=1，M=1。,2. 页面置换算法,页面淘汰过程,开始,第一次扫描循环队列,有A=0，M=0的页面？,第二轮扫描循环队列,置A=0,有A=0，M=1的页面？,扫描完否？,扫描完否？,淘汰该页,调入新页结束,有,有,无,否,完,无,否,完,扫描下一个页,扫描下一个页,页面置换算法实现目标：不发生抖动现象，缺页率正常。,（1）概念 一个运行进程

14、在t- 到t时间间隔内所访问的页面集合称为该进程在时间t的工作集，记为w(t, )。 其中， 为“工作集的窗口尺寸”，工作集中所包含的页面数称为“工作集尺寸”， 记为 。 工作集是 t和的函数： 不同t的工作集所包含的页面数不同 不同t的工作集中所包含的页面可能也不同,3. 工作集,3. 工作集,（2）例子 在某虚拟页式管理系统中，采用工作集模型来决定分给进程的物理块数，有如下的页面访问序列： 1633789162 3434344434 43 窗口尺寸为 =9，试求t1,t2时刻的工作集。,t1,t2,1 633789162 3 434344434 43,一个进程在t时刻的工作集： w(t,

15、)=t- 时刻到t时刻之间的页面集合,t1时刻的工作集w(t1, ) =1,2,3,6,7,8,9,t2时刻的工作集w(t2, ) =3，4,3. 工作集,4.空闲页面链表,原理： 在系统中维持一个空闲页面链表，当运行进程需要空闲页架时直接从该链表中分配空闲页架给当前请求的进程，并不断地按照某种页面置换算法向空闲页面链表中加入可用页面。 空闲页面链表中空闲页面的一般排序是：终止进程的数据和堆栈页面排在链的最前面，其后是置换出来的可用页面。,4.空闲页面链表,特点： 空闲页面链表的规模应适当保持（最大、最小页架数） 空闲链表中的页面并非真正“空闲”，空闲是指可分配的含义 在进行页面置换时不需移动

16、主存中的页面的内容，只是把页表目从页表移入页面链表，或相反。 通常由一个专用的进程来负责页面的替换工作 空闲页面链表的作用： 提高缺页时的系统处理效率，提高进程的执行速度。,空闲页面链表也称为页缓冲技术。,5.交换区,在请求分页的存储器管理系统中，从内存淘汰出来的页面存放在外存的交换区。 当交换区中的页面再次被访问时，内核页面失效处理函数从交换区中读出。 为了记录所有被换出页面在交换区中的位置，需要设置一交换区映射表。（交换区映射表驻留内核主存区） 交换区中一般存放淘汰的数据页面和堆栈页面，进程的正文页面可以通过文件系统，从执行文件中得到。,5.4 请求分段式存储器管理,1.基本思想 只将作业

17、的若干个段装入内存便可启动运行，并以分 段为单位进行换进和换出。 2.请求分段中的硬件支持 （1）段表 （2）缺段中断机构,缺段中断的处理过程如下图：,请求调入新段X,内存中有X段长 的空闲区吗？,内存中所有空闲 区之和X段长吗？,紧凑空闲区，形成一 个满足要求的空闲区,分配空闲区并 从外存调入新段X,修改段表和有 关数据结构,结束返回,淘汰相关的段形成 一个合适的空闲分区,有,是,否,没有,3.地址变换在分段管理存储管理系统的地址变换的基础上增加了缺段中断的请求和处理机制。地址变换的示意图如下：,5.4 请求分段式存储器管理,访问SW,S段表长 W段长？,存取合法吗？,段在内存？,修改相应的

18、访问字段,形成物理地址,结束返回,越界中断 处理,分段保护 中断处理,缺段中断 处理,段号,段内位移,否,否,否,是,是,是,4.分段管理的共享和保护,（1）段的共享 对于那些被多个程序共享的段，在内存中只保留一个副本。副本采用可重入代码。 可重入代码：又称“纯代码”，是一种允许多个进程同时访问的代码。可重入代码在被访问过程中不允许任何进程对其进行修改。,自学部分：,SRV4和Solaries采用的是哪种存储管理技术？ SRV4采用哪些数据结构来帮助实现分页技术？ 如何解决请求分页系统中的主存共享和快表的一致性问题？ 了解内核主存管理中的伙伴系统（阅读教材P163） 了解intel pentium的段页式实现机制,作业8 ： 1.P199：9.2、9.5、9.25 2.在某个采用基本页式存储管理