**

页式存储管理

**

一、页式存储管理的基本原理

【页式存储管理的基本原理】

• 分页存储器将主存划分成多个大小相同的页架
• 受页架尺寸限制，程序的逻辑地址也自然分页
• 不同的页可以放在不同页架中，不需要连续
• 页表用于维系进程的主存完整性
  

【页式存储管理中的地址】

• 页式存储管理的逻辑地址由两部分组成：页号和单元号，逻辑地址形式：
  
• 页式存储管理的物理地址也有两部分组成：页架号和单元号，物理地址形式：
  
• 地址转换（直接把页号变为页架号）可以通过查页表完成

【页式存储管理的地址转换思路】

【页式存储管理的内存分配/去配】

• 可用一张位示图来记录主存分配情况
• 建立进程页表维护主存逻辑完整性
  

【页的共享】

• 页式存储管理能够实现多个进程共享程序和数据
• 数据共享：不同进程可以使用不同页号共享数据页
• 程序共享：不同进程必须使用相同页号共享代码页
  #共享代码中的（JMP<页内地址>）指令，使用不同页号时做不到

二、页式存储管理的地址转换

【页式存储管理的地址转换代价】

• 页表放在主存：每次地址转换必须访问两次主存
  1.按页号读出页表中的相应页架号
  2.按计算出来的绝对地址进行读写
• 存在问题：降低了存取速度
• 解决方法：利用Cache存放部分页表

【页式存储管理的快表】

• 为提高地址转换速度，设置一个专用的高速存储器，用来存放页表的一部分
• 快表：存放在高速存储器中的页表部分
• 快表表项：页号，页架号
• 这种高速存储器是联想存储器，即按照内容寻址，而非按照地址访问

【引入快表后的地址转换代价】

• 采用快表后，可以加快地址转换速度
• 假定主存访问时间为200毫微秒，快表访问时间为40毫微秒，查快表的命中率是90%。平均地址转换代价为：（200+40）*90%+（200+200）*10%=256毫微秒
• 比两次访问主存的时间（400毫微秒）下降了36%

【基于快表的地址转换流程】

• 按逻辑地址中的页号查快表
• 若该页已在快表中，则由页架号和单元号形成绝对地址
• 若该页不在快表中，则再查主存页表形成绝对地址，同时将该页登记到快表中
• 当快表填满后，又要登记新页时，则需在快表中按一定策略淘汰一个旧登记项

【多道程序环境下的进程表】

• 进程表中登记了每个进程的页表
• 进程占有处理器运行时，其页表起始地址和长度送入页表控制寄存器
  

【多道程序环境下的地址转换】

三、页式虚拟存储管理

【页式虚拟存储管理的基本思想】

• 把进程全部页面装入虚拟存储器，执行时先把部分页面装入实际内存，然后，根据执行行为，动态调入不在主存的页，同时进行必要的页面调出
• 现代OS的主流存储管理技术
• 首次只把进程第一页信息装入主存，称为请求页式存储管理

【页式虚拟存储管理的页表】

• 需要扩充页表项，指出
  #每页的虚拟地址、实际地址
  #主存驻留标志、写回标志、保护标志、引用标志、可移动标志
  

【页式虚拟管理的实现】

• CPU处理地址
  #若页驻留，则获得块号形成绝对地址
  #若页不在内存，则CPU发出缺页中断
• OS处理缺页中断
  #若有空闲页架，则根据辅存地址调入页，更新页表与快表等
  #若无空闲页架，则决定淘汰页，调出已修改页，调入页，更新页表与快表

【页式虚拟存储管理的地址转换】

【缺页中断的处理流程】

四、页面调度

【页面调度】

• 当主存空间已满又需要装入新页时，页式虚拟存储管理必须按照一定的算法把已在主存的一些页调出去
• 选择淘汰页的工作称为页面调度
• 选择淘汰页的算法称为页面调度算法
• 页面调度算法如果设计不当，会出现（刚被淘汰的页面立即又要调入，并如此反复）这种现象称为抖动或颠簸

【缺页中断率】

• 假定进程P共n页，系统分配页架数m个
• P运行中成功访问次数为S，不成功访问次数为F，总访问次数A=S+F
• 缺页中断率定义为：f=F/A
• 缺页中断率是衡量存储管理性能和用户编程水平的重要依据

【影响缺页中断率的因素】

• 分配给进程的页架数：可用页架数越多，则缺页中断率就越低
• 页面的大小：页面尺寸越大，则缺页中断率就越低
• 用户的程序编制方法：在大数据量情况下，对缺页中断率也有很大影响

【用户编程的例子】

• 程序将数组置为“0”，假定仅分得一个主存页架，页面尺寸为128个字，数组元素按行存放，开始时第一页在主存
  

【OPT页面调度算法】

• 理想的调度算法是：当要调入新页面时，首先淘汰以后不再访问的页，然后选择距现在最长时间后再访问的页
• 该算法由Belady提出，称Belady算法，又称最佳算法（OPT）
• OPT只可模拟，不可实现

【先进先出FIFO页面调度算法】

• 总是淘汰最先调入主存的那一页，或者说主存驻留时间最长的那一页（常驻的除外）
• 模拟的是程序执行的顺序性，有一定合理性

【最近最少用LRU页面调度算法】

• 淘汰最近一段时间较久未被访问的那一页，即那些刚被使用过的页面，可能马上还要被使用到
• 模拟了程序执行的局部属性，既考虑了循环性又兼顾了顺序性
• 严格实现的代价大（需要维持特殊队列）

【LRU算法的模拟实现】

• 每页建一个引用标志，供硬件使用
• 设置一个时间间隔中断：中断时页引用标志置0
• 地址转换时，页引用标志置1
• 淘汰页面时，从页引用标志为0的页中随机选择
• 时间间隔多长是个难点

【最不常用LFU页面调度算法】

• 淘汰最近一段时间内访问次数较少的页面，对OPT的模拟性比LRU更好
• 基于时间间隔中断，并给每一页设置一个计数器
• 时间间隔中断发生后，所有计数器清0
• 每访问页1次就给计数器加1
• 选择计数值最小的页面淘汰

【时钟CLOCK页面调度算法】

• 采用循环队列机制构造页面队列，形成了一个类似于钟表面的环形表
• 队列指针则相当于钟表面上的表针，指向可能要淘汰的页面
• 使用页面引用标志位

【CLOCK算法的工作流程】

• 页面调入主存时，其引用标志位置1
• 访问主存页面时，其引用标志位置1
• 淘汰页面时，从指针当前指向的页面开始扫面循环队列
  #把所遇到的引用标志位是1的页面的引用标志位清0，并跳过
  #把所遇到的引用标志位是0的页面淘汰，指针推进一步

五、反置页表

【反置页表的提出】

• 页表及相关硬件机制在地址转换、存储保护、虚拟地址访问中发挥了关键作用
• 为页式存储管理设置专门硬件机构
• 内存管理单元MMU：CPU管理虚拟/物理存储器的控制线路，把虚拟地址映射为物理地址，并提供存储保护，必要时确定淘汰页面
• 反置页表IPT：MMU用的数据结构

【反置页表的基本设计思想】

• 针对内存中的每个页架建立一个页表，按照块号排序
• 表项包含：正在访问该页架的进程标识、页号及特征位，和哈希链指针等
• 用来完成内存页架到访问进程页号的对应，即物理地址到逻辑地址的转换

【反置页表的页表项】

• 页号：虚拟地址页号
• 进程标志符：使用该页的进程号（页号和进程标志符结合起来标志一个特定进程的虚拟地址空间的一页）
• 标志位：有效、引用、修改、保护和锁定等标志信息
• 链指针：哈希链

【基于反置页表的地址转换过程】

• MMU通过哈希表把进程标识和虚页号转换成一个哈希值，指向IPT（反置页表）的一个表目
• MMU遍历哈希链找到所需进程的虚页号，该项的索引就是页架号，通过拼接移位便可生成物理地址
• 若遍历整个反置页表中未能找到匹配表项，说明该页不在内存，产生缺页中断，请求操作系统调入

【反置页表下的地址转换示意】

• 未显示选择淘汰页面，同样由MMU完成

**

段式存储管理

**

一、段式存储管理

【段式程序设计】

• 每个程序可由若干段组成，每一段都可以从“0”开始编址，段内的地址是连续的
• 分段存储器的逻辑地址由两部分组成
  #段号：单元号
  #和页式存储管理（段号：单元号）有本质区别。“段号：单元号”是用户程序设计自己设定的。而“页号：单元号”是系统自动切割的，用户并不知道。所以分页存储器是用户编程原则上不可见的，除了性能优化。而分段存储器是用户可控制的

【程序的分段结构】

【段式存储管理的基本思想】

• 段式存储管理基于可变分区存储管理实现，一个进程要占用多个分区
• 硬件需要增加一组用户可见的段地址寄存器（代码段、数据段、堆栈段、附加段），供地址转换使用
• 存储管理需要增加设置一个段表，每个段占用一个段表项，包括：段始址、段限长，以及存储保护、可移动、可扩充等标志位

【段式存储管理的地址转换流程】

【段的共享】

• 通过不通进程段表中的项指向同一个段基址来实现
• 对共享段的信息必须进行保护，如规定只能读出不能写入，不满足保护条件则产生保护中断

二、段式虚拟存储管理

【段式虚拟存储管理的基本思想】

• 把进程的所有分段都存放在辅存中，进程运行时先把当前需要的一段或几段装入主存，在执行过程中访问到不在主存的段时再把他们动态装入
• 段式虚拟存储管理中断的调进调出是由OS自动实现的，对用户透明
• 与段覆盖基数不同，它是用户控制的主存扩充技术，OS不感知

【段式虚拟存储管理的段表扩充】

• 段表的扩充
  #特征位：00（不在内存）01（在内存）11（共享段）
  #存取权限：00（可执行）01（可读）11（可写）
  #扩充位：0（固定长）1（可扩充）
  #标志位：00（未修改）01（已修改）11（不可移动）
  

【段式虚拟存储管理的地址转换】

三、段页式存储管理

【段页式存储管理的基本思想】

• 段式程序设计可以基于页式存储管理实现
• 每一段不必占据连续的存储空间，可存放在不连续的主存页架中
• 能够扩充位段页式虚拟存储管理
• 装入部分段，或者装入段中部分页面

【段页式存储管理的段表和页表】

【段页式存储管的地址转换】

【段页式虚拟存储管理的地址转换】