存储器管理的主要模式

逻辑地址

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

段式程序设计

• 把一个程序设计成多个段：代码段（code segment）、数据段（data segment）、堆栈段（stack segment）等等
• 用户可以自己应用段覆盖技术扩充内存空间使用量

这一技术是程序设计技术，不是 OS 存储管理的功能

物理地址

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

主存储器的复用

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

存储管理的基本模式

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

存储管理的功能

地址转换

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

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

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

主存储器空间的共享

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

存储保护

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

主存储器空间的扩充

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

虚拟存储器的概念

虚拟存储器思想的提出

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

虚拟存储器的基本思想

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

虚拟存储器的实现思路

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

存储管理的硬件支撑

存储管理涉及的存储对象

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

高速缓冲存储器（Cache）

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

高速缓冲存储器的构成

高速缓冲存储器通常由高速存储器、联想存储器、地址转换部件、替换逻辑等组成

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

高速缓冲存储器的组织

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

高速缓冲存储器的分级

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

存储管理与硬件支撑

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

单连续分区存储管理

每个进程占用一个物理上完全连续的存储空间（区域）

• 单用户连续存储管理
• 固定分区存储管理
• 可变分区存储管理

单用户连续分区存储管理

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

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

可变分区存储管理概述

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

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

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

可变分区存储管理

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

可变分区方式的内存分配

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

可变分区方式的内存零头

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

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

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

页式存储管理的基本原理

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

页式存储管理中的地址

• 页式存储管理的逻辑地址由两部分组成：页号+单元号（offset）。
• 页式存储管理的物理地址由两部分组成：页架号+单元号（offset）
• 页架的 offset 和页的 offset 应该是相同的
• 地址转换可以通过查页表完成

页的共享

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

页式存储管理的地址转换

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

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

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

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

基于快表的地址转换流程

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

多道程序环境下的进程表

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

用户作业名	页表始址	页表长度
AB	0010	4
CD	0014	3
EF	0017	7
…	…	…

页式虚拟存储管理

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

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

页式虚拟存储管理的页表

虚拟存储需要扩充页表项，页表项中需要指出：

1. 每页的虚拟地址、实际地址
2. 主存驻留标志、写回标志、保护标志、引用标志、可移动标志

标志位	主存块号	辅助存储器地址

页式虚拟存储管理的实现

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

页面调度

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

缺页中断率

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

影响缺页中断率的因素

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

页秒调度算法

OPT 页面调度算法

• 理想的调度算法是：当要调入新页面时，首先淘汰以后不再访问的页，然后选择距现在最长时间后再访问的页。
• 该算法由Belady提出，称Belady算法，又称最佳算法（OPT）
• OPT只可模拟，不可实现（实际中无法预测未来，不知道未来哪个页不再被访问也不知道未来哪个页什么时候会再被访问）。

先进先出 FIFO 页面调度算法

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

最近最少使用 LRU 页面调度算法

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

LRU 算法的模拟实现

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

最不常用 LFU 页面调度算法

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

时钟 CLOCK 页面调度算法

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

CLOCK 算法的工作流程

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

Reference

1. 南京大学软件学院本科三年级课程《计算机与操作系统》