1、第七章 虚拟存储器管理?基本概念?请求分页的存储器系统?页面置换算法?请求分段的存储器系统 7.1 基本概念基本概念 1.虚拟存储器的引入（1）局部性原理?时间的局部性?空间的局部性 （2）定义 把作业的一部分装入内存就可运行的存储器系统。虚拟存储器系统能从逻辑上对内存容量进行扩充，并具有请求调入和置换功能的一种存储器系统。2.虚拟存储器的实现方法?请求分页的存储器管理系统?请求分段的存储器管理系统?段页式虚存管理系统 7.1 基本概念 注：虚拟性是以多次性和对换性为基础。3.虚拟存储器的特征?离散性?多次性：作业被分成多次装入内存。?对换性?虚拟性：能从逻辑上扩充主存容量。4.虚拟地址与实地
2、址 7.1 基本概念基本概念?虚拟地址：在虚存管理系统中，通常把运行进程访问的指令和数据的逻辑地址（目标程序中的相对地址）称为虚拟地址。虚拟地址的集合称为虚拟地址空间。?实地址：是指CPU能直接访问的存放指令和数据的主存地址(CPU外部地址总线上访问物理主存的地址)。主存也称为实地址空间。7.2 请求分页的存储器系统 在基本分页系统的基础上，增加了请求调页和页面置 换功能的页式虚拟存储器系统。1.请求分页的硬件支持 （1）页表、快表和反向页表 页架号 访问位 有效位P 保护权限 修改位M 外存地址 页表项 内容：其中：有效位：表示该页是否在内存 修改位：表示该页调入内存后是否被修改过 保护权限
3、：可读/可读写 活动页表：由页表寄存器指出的进程页表称为活动页表。在单处理机系统中，通常有两个活动页表：当前活动进程的活动页表和内核活动页表。7.2 请求分页的存储器系统?快表 快表由硬件实现，一般有64256 个表目。每个快表表目包含若干个项，如：?虚页号?物理块号?保护权限?进程号 有些系统中有两个分离的快表（如IBM RS/6000）：?数据快表（127 个表目）?指令快表（32个表目）7.2 请求分页的存储器系统?反向页表 反向页表中的每一个表目对应主存中的一个物理块号（反向页表的索引号）。每个表目包括：?其映射的虚页号?指向哈希链的下一指针?有效位、引用位、修改位?保护和加锁信息 使
4、用反向表的系统采用哈希技术完成逻辑地址到物理地址的转换。目的是为了解决页表大小随逻辑地址空间递增和避免使用多级页表的问题 7.2 请求分页的存储器系统 页号 P 页内偏移 d 页号 表目体 链指针 P 页架号 3 反向页表 哈希表 哈希函数 页架号 d 物理地址 基于反向页表的地址转换过程：反向页表的索引号就是 主存的页架号。溢 出 链（2）缺页中断机构 产生和处理缺页中断的机构。缺页中断与一般中断的区别：?在指令执行期间产生和处理中断信号?一条指令执行期间可能产生多次缺页中断 B：A：COPY A TO B 1 2 3 4 5 6 7.2 请求分页的存储器系统 地址变换 在基本分页系统的地址
5、变换机构的基础上增加了 产生和处理缺页中断的功能。过程如图所示：7.2 请求分页的存储器系统请求分页的存储器系统 开始 页号页表长?是 越界中断 该页在快表 中？该页在内存否？修改A和M 修改快表 形成物理地址 保存CPU 现场 从外存中找到缺页 内存满否？换页处理 该页被修改否？将该页写回外存 读缺页 换缺页入内存 修改页表 是 是 是 是 否 否 否 否 否 访问页表 结束（3）MMU MMU 是内核主存管理子系统依赖的 低层硬件，主要完成虚地址到物理地址的转换，包括：?管理硬件的页表基址寄存器?将虚地址分为虚页号和页内位移?页面失效处理（边界错误、缺页、保护错误）?设置页表中相应的访问位
6、、修改位、检查有效位和保护权限 7.2 请求分页的存储器系统 2.页面分配的有关策略 （1）最小物理块数的确定 最小物理块数是指能保证进程正常运行所需要的最 少物理块数。相关因素：机器指令的格式、功能 和寻址方式。（2）页面分配和置换策略?固定分配局部置换?可变分配全局置换：系统维护一个空闲物理块队列?可变分配局部置换：根据缺页率来动态增加或减少每个进程分配的物理块数 7.2 请求分页的存储器系统 （3）页面分配方法?平均分配：每个进程分配相同数量的物理块?按比例分配：按进程所拥有页面数的多少进行分配 mssibisisni*1?注：m为系统可用物理块数 si为每个进程的页面数 bi为每个进程
7、分配的物理块数?考虑优先权分配 7.2 请求分页的存储器系统 3.页面调入策略（1）调入页面的时机?预调页策略：执行前先调入若干不久将被访问的页面?请求调页策略：缺页时请求调入页面，每次只调入一页。7.2 请求分页的存储器系统 （2）从何处调入页面?系统有足够的对换区空间：所有页面从对换区调入。?系统的对换区空间不足：不会被修改的页面从文件区调入。?Unix 方式：未运行过的页面从文件区调入 4.页面调入过程 该页在内存？有空闲物理块？保留CPU 现场 调入所需页 选择一页换出 该页修改否？写回外存 恢复CPU 现场 继续执行 变换地址并执行 否 否 否 是 是 是 产生缺页中断 1.页面访问
8、失效的原因?边界错误：如页号超过页表的长度。?有效性错误：要访问的页面不在内存，即有效位为零。?保护错误：不允许的访问权限。7.3 页面置换算法?页淘汰可以发生在申请页帧时，而现代OS一般都定时进行页淘汰。?如何选取被淘汰的页是由页面替换策略决定的，若已决定淘汰页P，则淘汰一页的主要工作有：2.页面置换（页面淘汰）算法?查P页表项的修改位，若未修改，则有效位清0，将页帧送回空闲页帧队列。?若已修改，则看是否要写回交换区，若回写swap区页，则申请一块swap区空间，将P的外存块号置上。?调用I/0子系统将页帧上的数据写到外存块号所指的外存空间。有效位清0，并将页帧送回空闲页帧队列。?最佳置换算
9、法（OPT）?最近未使用置换算法（NRU）?先进先出置换算法（FIFO）?二次机会置换算法?时钟页面置换算法（CLOCK）?最近最久未使用置换算法（LRU）?改进型Clock（近似LRU）算法 2.页面置换算法 2.页面置换算法（1）最佳置换算法（OPT）该算法是Belady 在1966 年提出的一种理论上的算法。为保证缺页率最低，选择永久不使用，或将在最长时间内不再被访问的页面淘汰。9/21=43%例：假设分配给某进程的页架数为3，采用请求调页方式，采用最佳置换算法，求下列页面执行序列（访问串）的缺页率。7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,1,7,0,1 由于
10、需要预先得知整个访问串的序，故不能用于实践。仅作为一种标准，用以测量其他可行策略的性能。（2）最近未使用置换算法（NRU）淘汰最近未使用的页面，而且最好是未被修改的页面。即淘汰的页面最好是访问位和修改位同时为零的页面。2.页面置换算法页面置换算法 为了避免系统中所有的页面的访问位和修改位可能都为“1”的情况，系统周期性地将主存中页面的访问位清“0”。（3）先进先出置换算法（FIFO）淘汰页面时，选择最先进入的页面。实现方便。不需要额外硬件。2.页面置换算法 14/21=66.7%例：假设分配给某进程的页架数为3，采用请求调页方式，页面置换算法用FIFO，求下列页面执行序列的缺页率。7,0,1,
11、2,0,3,0,4,2,3,0,3,2,1,2,0,1,1,7,0,1 缺点：该算法只是在按线性顺序访问地址空间时才具有较高的效率，否则可能出现抖动现象。Belady奇异：指替换策略不满足随着驻留集的增大，页故障数一定减少的规律。（驻留集(工作集)：进程的合法页集合。）（4）二次机会置换算法）二次机会置换算法 该算法是 FIFO 算法的一种改进算法。淘汰时，首先检查FIFO 链首页面的访问位，如果为“0”，则立即淘汰，如果为“1”，则将其移到当前FIFO 链的链尾，并将其访问位置“0”，再检查新的链首页面，直到找到一个访问为“0”的链首页面。2.页面置换算法页面置换算法（5）时钟（Clock）
12、页面置换算法 将二次机会置换算法中的 FIFO 链组织成一个环状队列，设一指针指向当前最 老的页面。当产生缺页中断时，如果指针所指向的页面的访问位为“0”，则淘汰，将新调入的页面插入到指针指向的位置，指针前移；如果访问位为“1”，则将其清“0”，指针前移，直到找到一个访问位 为“0”的页面。2.页面置换算法页面置换算法（6）最近最久未使用（LRU）算法 原理 根据页面在内存中的使用情况，选择最近最久未使用 的页面予以淘汰。即以“最近的过去”预测“最近的将来”，即淘汰上次使用距当前最远的页。2.页面置换算法 硬件LRU 法?寄存器：需为内存中的每一页配置一移位寄存器，用来记录各页在内存中的使用情
13、况。假设N位寄存器的表示形式为：R=Rn-1Rn-2Rn-3R2R1R0 实现原理：当进程访问某物理块时，将相应寄存器的Rn-1位置1，各寄存器根据系统时钟，每隔一定时间右移一位，各寄存器所中表示值 最小的那个页面将是下一个被淘汰的页面。2.页面置换算法 Rn-1 Rn-2 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 访问页1后右移一位：页1 页2 页1 页2 淘汰页2 访问页1 1 1?栈实现的LRU 法 存放当前使用的各页面的页号。实现原理：当进程访问某页时，就将该页的页号从栈底移出压入栈顶，或将新
14、访问的页号压入栈顶。处于栈底的就是最近最久未使用的页面号。2.页面置换算法页面置换算法 例：设某进程的页面引用顺序为：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1，统分配给该进程的物理块为3，并采用请求调页策略，则栈的变化情况如下图所示：0 2 1 0 7 3 0 4 2 3 0 2 3 1 2 0 7 0 7 0 7 1 0 7 2 1 0 0 2 1 3 0 2 0 3 2 4 0 3 2 4 0 3 2 4 0 3 2 3 0 2 2 3 0 1 2 3 2 1 3 0 2 1 7 0 2 0 7 2 1 7 0 1 缺页率=13/20=65%2.页面置
15、换算法 缺页率：缺页次数与进程页面总数的比值。3）矩阵实现的LRU 算法（参考教材P175176）LRU 算法虽然能够实现，但需要增加成本和开销，无Belady奇异。7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1（7）改进型Clock（近似LRU）算法 原理：为内存中所有的页面设置一访问位和一修改位，置初值为0，并将这些页通过指针链接成循环队列。在选择淘汰页时，尽量选择那些访问位和修改位都0的页面，如果没有这样的页面，再考虑访问位为0，而修改为1的页面做为淘汰页。由访问位A和修改位M组成的页面类型有：2.页面置换算法页面置换算法 第一类页面：A=0，M=0；第二
16、类页面：A=0，M=1；第三类页面：A=1，M=0；第四类页面：A=1，M=1。页面淘汰过程页面淘汰过程 开始 第一次扫描循环队列 有A=0，M=0 的页面？第二轮扫描循环队列 置A=0 有A=0，M=1 的页面？扫描完否？扫描完否？淘汰该页 调入新页结束 有 有 无 否 完 无 否 完 扫描下一个页 扫描下一个页 页面置换算法实现目标：不发生抖动现象，缺页页面置换算法实现目标：不发生抖动现象，缺页率正常。（1）概念 一个运行进程在t-到t时间间隔内所访问的页面集合称为该进程在时间t上的工作集，记为w(t,)。其中，为“工作集的窗口尺寸”，工作集中所包含的页面数称为“工作集尺寸”，记为 。工作
17、集是 t和的函数：?不同t的工作集所包含的页面数不同?不同t的工作集中所包含的页面可能也不同 3.工作集 w(t,)3.工作集（2）例子 在某虚拟页式管理系统中，采用工作集模型来决定分给进程的物理块数，有如下的页面访问序列：1633779162 3434344434 43 窗口尺寸为=9，试求t1,t2 时刻的工作集。t1 t2 1 633779162 3 434344434 43 一个进程在t时刻的工作集：w(t,)=t-时刻到t时刻之间的页面集合 t1 时刻的工作集w(t1,)=1,2,3,6,7,7,9 t2时刻的工作集w(t2,)=3，4 3.工作集工作集 4.空闲页面链表空闲页面链表
18、 原理：在系统中维持一个空闲页面链表，当运行进程需要空闲页架时直接从该链表中分配页架给当前请求的进程，并不断地按照某种页面置换算法向空闲页面链表中加入可用页面。空闲页面链表中空闲页面的一般 排序是：终止进程的数据和堆栈页面排在链的最前面，其后是置换出来的可用页面。4.空闲页面链表 特点：?空闲页面链表的规模应适当保持（最大、最小页架数）?空闲链表中的页面并非真正“空闲”，空闲是指可分配的含义?在进行页面置换时不需移动主存中页面的内容，只是把页表目从页表移入页面链表，或相反。?通常由一个专用的进程来负责页面的替换工作 空闲页面链表也称为页缓冲技术。空闲页面链表的作用：提高缺页时的系统处理效率，提
19、高进程的执行速度。5.交换区交换区?在请求分页的存储器管理系统中，从内存淘汰出来的页面存放在外存的交换区。?当交换区中的页面再次被访问时，内核页面失效处理函数将其从交换区中读出。?为了记录所有被换出页面在交换区中的位置，需要设置一交换区映射表。（交换区映射表驻留内核主存区）?交换区中一般存放淘汰的数据页面和堆栈页面，进程的正文页面可以通过文件系统，从执行文件中得到。5.4 请求分段式存储器管理请求分段式存储器管理 1.基本思想 只将作业的若干个段装入内存便可启动运行，并以分 段为单位进行换进和换出。2.请求分段中的硬件支持（1）段表 （2）缺段中断机构 段名 段长 段的基址 存取方式 访问字段
20、 修改字段 有效位 增补位 外存始址 缺段中断的处理过程如下图：请求调入新段X 内存中有X段长 的空闲区吗？内存中所有空闲 区之和X段长吗？紧凑空闲区，形成一 个满足要求的空闲区 分配空闲区并 从外存调入新段X 修改段表和有 关数据结构 结束返回 淘汰相关的段形成 一个合适的空闲分区 有 是 否 没有 3.地址变换 在分段管理存储管理系统的地址变换的基础上增加了缺段中断的请求和处理机制。地址变换的示意图如下：5.4 请求分段式存储器管理请求分段式存储器管理 访问SW S段表长 W段长？存取合法吗？段在内存？修改相应的访问字段 形成物理地址 结束返回 越界中断 处理 分段保护 中断处理 缺段中断
21、 处理 段号 段内位移 否 否 否 是 是 是 5.4 请求分段式存储器管理请求分段式存储器管理 4.分段的共享与保护 （1）分段共享 共享段表：系统中配置一张共享段表，每个共享段在共享段表中占一表项，每个表项的内容如下：共享段的分配与回收 段名 段长 内存地址 状态 外存始址 共享进程计数count 进程名 进程号 状态 段号 存取控制 4.分段的共享与保护 （2）分段保护?越界检查：每个进程只能运行在自己的地址空间。?存取控制检查：只读、只执行、读/写?环保护机构：不同的环具有不同的访问权限。原则是：?一个程序可以访问驻留在相同环或较低环中的数据?一个程序可以调用驻留在相同环或较高环中的服
22、务 5.4 请求分段式存储器管理请求分段式存储器管理 2009 考研考研 46.（8）请求 答案答案 2010考研 46.（8分）设某计算机的逻辑地址空间和物理地址空间均为64KB.按字节编址。若某进程最多需要6页（Page）数据存储空间，页的大小为1KB.操作系统采用固定分配局部置换策略为此进程分配4个页框（Page Fame）.页号 页根号 装入时刻 访问位 0 7 130 1 1 4 230 1 2 2 200 1 3 9 160 1 当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据，请问答下列问题：（1）该逻辑地址对应的页号是多少？（2）若采用先进先出（FIFO）置换算法，
23、该逻辑地址对应的物理地址是多少？要求给出计算过程。（3）若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。（设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，示意图如下。）答案答案 解答：17CAH=(0001 0111 1100 1010)2（1）页大小为1K，所以页内偏移地址为10位，于是前6位是页号，所以第一间的解为：5（2）FIFO，则被置换的页面所在页框为7，所以对应的物理地址为（0001 1111 1100 1010）2=1FCAH（3）CLOCK,则被置换的页面所在页框为2，所以对应的物理地址为（0000 1011 1100 1010）2=
24、OBCAH 作业7：1.何谓虚拟存储器系统？虚拟存储器系统的容量由哪些因素决定？2.请比较在分页、分段虚拟存储技术中的存储保护与碎片问题。3.在某个采用基本页式存储管理系统中，有J1，J2和J3三个作业同驻主存。其中J2有4个页面，分别装入到主存的第3、4、6、7四个物理块中。假定页面和存储块的大小为1024B，主存容量为10KB。问题：（1）画出J2的页面映像表；（2）当J2在CPU 上运行是，执行到其地址空间第500 号处遇到一条传送指令：MOV 2100，3100。请用地址变换图计算MOV 指令中两个操作数的物理地址。4.在一个请求分页系统中，一个进程的页面走向:1,3,2,1,1,3,5,1,3,2,1,5，现假定系统采用请求调页策略，系统分配给该进程的页架数为3，试分别求出采用LRU 和FIFO 进行页面置换时的缺页率。
