存储器管理的主要模式

逻辑地址

  • 逻辑地址：又称相对地址，即用户编程所使用的地址空间
  • 逻辑地址从0开始编号，有两种形式：
    • 一维逻辑地址（地址）
    • 二维逻辑地址（段号:段内地址）

段式程序设计

  • 把一个程序设计成多个段
    • 代码段、数据段、堆栈段、等等
  • 用户可以自己应用段覆盖技术扩充内存空间使用量
    • 这一技术是程序设计技术，不是OS存储管理的功能

物理地址

  • 物理地址：又称绝对地址，即程序执行所使用的地址空间
  • 处理器执行指令时按照物理地址进行

主存储器的复用

  • 多道程序设计需要复用主存
  • 按照分区复用：
    • 主存划分为多个固定/可变尺寸的分区
    • 一个程序/程序段占用一个分区
  • 按照页架复用：
    • 主存划分成多个固定大小的页框
    • 一个程序/程序段占用多个页框

存储管理的基本模式

  • 单连续存储管理：一维逻辑地址空间的程序占用一个主存固定分区或可变分区
  • 段式存储管理：段式二维逻辑地址空间的程序占用多个主存可变分区
  • 页式存储管理：一维逻辑地址空间的程序占用多个主存页框区
  • 段页式存储管理：段式二维逻辑地址空间的程序占用多个主存页框区

存储管理模式示意图

存储管理的功能

地址转换

  • 地址转换：又称重定位，即把逻辑地址转换成绝对地址
  • 静态重定位：在程序装入内存时进行地址转换
    • 由装入程序执行，早期小型OS使用
  • 动态重定位：在CPU执行程序时进行地址转换
    • 从效率出发，依赖硬件地址转换机构

主存储器空间的分配与去配

  • 分配：进程装入主存时，存储管理软件进行具体的主存分配操作，并设置一个表格记录主存空间的分配情况
  • 去配：当某个进程撤离或主动归还主存资源时，存储管理软件要收回它所占用的全部或者部分存储空间，调整主存分配表信息

主存储器空间的共享

  • 多个进程共享主存储器资源：多道程序设计技术使若干个程序同时进入主存储器，各自占用一定数量的存储空间，共同使用一个主存储器
  • 多个进程共享主存储器的某些区域：若干个协作进程有共同的主存程序块或者主存数据块

存储保护

  • 为避免主存中的多个进程相互干扰，必须对主存中的程序和数据进行保护
    • 私有主存区中的信息：可读可写
    • 公共区中的共享信息：根据授权
    • 非本进程信息：不可读写
  • 这一功能需要软硬件协同完成
    • CPU检查是否允许访问，不允许则产生地址保护异常，由OS进行相应处理

主存储器空间的扩充

  • 存储扩充：把磁盘作为主存扩充，只把部分进程或进程的部分内容装入内存
    1. 对换技术：把部分不运行的进程调出
    2. 虚拟技术：只调入进程的部分内容
  • 这一工作需要软硬件协作完成
    1. 对换进程决定对换，硬件机构调入
    2. CPU处理到不在主存的地址，发出虚拟地址异常，OS将其调入，重执指令

虚拟存储器的概念

虚拟存储器思想的提出

  • 主存容量限制带来诸多不便
    • 用户编写程序必须考虑主存容量限制
    • 多道程序设计的道数受到限制
  • 用户编程行为分析
    • 全面考虑各种情况，执行时有互斥性
    • 顺序性和循环性等空间局部性行为
    • 某一阶段执行的时间局部性行为
  • 因此可以考虑部分调入进程内容

虚拟存储器的基本思想

  • 存储管理把进程全部信息放在辅存中，执行时先将其中一部分装入主存，以 后根据执行行为随用随调入
  • 如主存中没有足够的空闲空间，存储管理需要根据执行行为把主存中暂时不用的信息调出到辅存上去

虚拟存储器的实现思路

  • 需要建立与自动管理两个地址空间
    • (辅存)虚拟地址空间：容纳进程装入
    • (主存)实际地址空间：承载进程执行
  • 对于用户，计算机系统具有一个容量大得多的主存空间，即虚拟存储器
  • 虚拟存储器是一种地址空间扩展技术，通常意义上对用户编程是透明的，除非用户需要进行高性能的程序设计

虚拟存储器示意

存储管理的硬件支撑

存储器的组织层次

存储管理涉及的存储对象

  • 存储管理是OS管理主存储器的软件部分
  • 为获得更好的处理性能，部分主存程序与数据（特别是关键性能数据）被调入Cache，存储管理需要对其进行管理，甚至包括对联想存储器的管理
  • 为获得更大的虚拟地址空间，存储管理需要对存放在硬盘、固态硬盘、甚至网络硬盘上的虚拟存储器文件进行管理

高速缓存存储器（Cache）

  • Cache是介于CPU和主存储器间的高速小容量存储器，由静态存储芯片SRAM 组成，容量较小但比主存DRAM技术更加昂贵而快速，接近于CPU的速度
  • CPU往往需要重复读取同样的数据块，Cache的引入与缓存容量的增大，可以大幅提升CPU内部读取数据的命中率，从而提高系统性能

高速缓存存储器的构成

  • 高速缓冲存储器通常由高速存储器、联想存储器、地址转换部件、替换逻辑等组成
  • 联想存储器：根据内容进行寻址的存储器
  • 地址转换部件：通过联想存储器建立目录表以实现快速地址转换。命中时直接访问Cache；未命中时从内存读取放入Cache
  • 替换部件：在缓存已满时按一定策略进行数据块替换，并修改地址转换部件

高速缓存存储器的组织

  • 由于CPU芯片面积和成本，Cache很小
  • 根据成本控制，划分为L1、L2、L3三级

高速缓存存储器的分级

  • L1 Cache：分为数据缓存和指令缓存；内置；其成本最高，对CPU的性能影响最大；通常在32KB-256KB之间
  • L2 Cache：分内置和外置两种，后者性能低一些；通常在512KB-8MB之间
  • L3 Cache：多为外置，在游戏和服务器领域有效；但对很多应用来说，总线改善比设置L3更加有利于提升系统性能

地址转换/存储保护的硬件支撑

存储管理与硬件支撑

  • 鉴于程序执行与数据访问的局部性原理，存储管理软件使用Cache可以大幅度提升程序执行效率
  • 动态重定位、存储保护等，若无硬件支撑在效率上是无意义的，即无实现价值
  • 无虚拟地址中断，虚拟存储器无法实现
  • 无页面替换等硬件支撑机制，虚拟存储器在效率上是无意义的

单连续分区存储管理

单连续分区存储管理

  • 每个进程占用一个物理上完全连续的存储空间(区域)
  • 单用户连续存储管理
  • 固定分区存储管理
  • 可变分区存储管理

单用户连续分区存储管理

  • 主存区域划分为系统区与用户区
  • 设置一个栅栏寄存器界分两个区域，硬件用它在执行时进行存储保护
  • 一般采用静态重定位进行地址转换
  • 硬件实现代价低
  • 适用于单用户单任务操作系统，如DOS

单用户连续分区存储管理示意

  • 静态重定位：在装入一个作业时，把该作业中程序的指令地址和数据地址全部转换成绝对地址

固定分区存储管理

固定分区存储管理的基本思想

  • 支持多个分区
  • 分区数量固定
  • 分区大小固定
  • 可用静态重定位
  • 硬件实现代价低
  • 早期OS采用

固定分区方式的主存分配

  • 主存分配表
  • 主存分配与去配

固定分区方式的地址转换

  • 硬件实现机制与动态重定位

可变分区存储管理

可变分区存储管理概述

  • 固定分区存储管理不够灵活，既不适应大尺寸程序，又存在内存内零头， 有浪费
  • 能否按照进程实际内存需求动态划分分区，并允许分区个数可变
  • 这就是可变分区存储管理

可变分区存储管理

  • 按进程的内存需求来动态划分分区
  • 创建一个进程时，根据进程所需主存量查看主存中是否有足够的空闲空间
    • 若有，则按需要量分割一个分区
    • 若无，则令该进程等待主存资源
  • 由于分区大小按照进程实际需要量来确定，因此分区个数是随机变化的

可变分区方式的内存分配示例

可变分区的主存分配表

  • 已分配区表与未分配区表，采用链表

可变分区方式的内存分配

  • 最先适应分配算法
  • 邻近适应分配算法
  • 最优适应分配算法
  • 最坏适应分配算法

可变分区的内存回收

地址转换与存储保护

  • 硬件实现机制与动态重定位

可变分区方式的内存零头

  • 固定分区方式会产生内存内零头
  • 可变分区方式也会随着进程的内存分配产生一些小的不可用的内存分区，称为 内存外零头
  • 最优适配算法最容易产生外零头
  • 任何适配算法都不能避免产生外零头

移动技术（程序浮动技术）

  • 移动分区以解决内存外零头
  • 需要动态重定位支撑

工作流程

页式存储管理

页式存储管理的基本原理

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

页式存储管理中的地址

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

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

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

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

页的共享

  • 页式存储管理能够实现多个进程共享程序和数据
  • 数据共享：不同进程可以使用不同页号共享数据页
  • 程序共享：不同进程必须使用相同页号共享代码页
  • 共享代码页中的(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遍历哈希链找到所需进程的虚页号， 该项的索引就是页架号，通过拼接位移便可生成物理地址
  • 若遍历整个反置页表中未能找到匹配页表项，说明该页不在内存，产生缺页中 断，请求操作系统调入

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

段式存储管理

段式程序设计

  • 每个程序可由若干段组成，每一段都可以从“0”开始编址，段内的地址是连续的
  • 分段存储器的逻辑地址由两部分组成
    • 段号：单元号

程序的分段结构

段式存储管理的基本思想

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

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

段的共享

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

段式虚拟存储管理

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

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

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

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

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

段页式存储管理

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

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

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

段页式存储管理的地址转换

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