BUAA-OS-Theory-Chapter3-2

第三章 内存管理 - Part2

分页式存储管理

通过分页式存储管理可以把一个逻辑地址连续的程序装入到若干不连续的物理地址中，这可充分利用存储空间、减少移动带来的开销

主要针对的问题：

• 动态内存分配
• 碎片、紧凑问题

定义：

• 页：每个作业的地址空间分成的大小相同的片
• 存储块/页框：主存的存储空间也被分为与页相同大小的片

分页地址结构

页号 | 偏移量

分页式结构下，地址由两部分组成，页号可以是物理块号也可以是逻辑页号，两者可以转换

• 逻辑地址、物理地址在同一系统内的页/块内偏移位数（大小）一致

• 给定一个逻辑地址空间中的地址为 A ，页面的大小为 L ，则页号 P 和页内地址 d（从0 开始编号）为

  • $P=INT[\frac A L],d=[A]modL$

• 页面大小是由硬件决定的，通常选用$2^n$作为页大小，最常用的页面大小为4KB

  • 若采用小页面：页内碎片、内存碎片减少，提高内存利用率；页面数多，页表占用内存大；换进换出速度降低，但效率高；若采用大页面则特点相反
  • 分页开销为$\frac{se}p+\frac p 2$（页面大小$p=\sqrt{2se}$，进程平均字节s，页表项e）

• 逻辑上相邻的页，在物理地址上不一定相邻

页表数据结构

• 进程页表：每个进程具有一个页表，描述该进程逻辑页与物理块的映射关系
• 物理页面表：整个系统只拥有一个物理页面表，描述物理空间的分配情况
• 请求表：整个系统有一个请求表，描述系统内各进程页表的大小额位置，用于地址转换

页表的作用：

• 记录进程的内存分配情况
• 实现进程运行时的动态重定位
• 访问内存数据需要访问内存两次（页表+内存地址）

多级页表

当逻辑地址较大时会导致页表增大，可以采用多级页表或动态调入页表的方式解决

• 动态调入页表：只把部分页表项调入内存，待需要其他页面时再调入

两级页表

• 逻辑地址划分：二级页表|一级页表|页内地址
• 将一级页表再进行分页，将页表分散地存放在物理块中，再使用外部页表记录这些页
• 正在运行的进程必须调入二级页表，但是一级页表可以按需调入内存
• 对多级页表来说，各级页表存放的都是物理块号，他们指向内存中的下级页表或真正的被访问页

地址变换过程

逻辑地址转换为物理地址：

• 根据页号在页表中查询对应的项（页表始址+页号*页表项长度）
• 读出页表项对应的物理块号
• 使用块号+页内地址合成出物理地址

纯分页系统

若系统不支持内存主存的页面对换功能，就必须把程序的页一次性地装入内存；若当前内存不足则必须等待空闲

优点

• 没有外碎片，每个内碎片小于页大小（毕竟按页分块）
• 程序不必连续在内存中存放，系统可以轻易完成该进程新数据的装载

缺点：

• 程序需要一次性全部装入内存，占用开销大

MMU（Memory Management Unit）

CPU为了提高地址转换效率，添加了一个硬件单元MMU，其主要包括：

• 快表TLB：存放于虚拟地址相关的物理地址
• TLB控制单元：TLB内容的填充覆盖、越界检查
• 页表查找单元：当TLB未命中时查找页表并输送给TLB单元

• MMU的工作流程：
  • 先在TLB中查询，成功匹配则分段查询（如果有多级页表）页表并得到物理地址；若未匹配则到外部页表中查询并置换进TLB中
  • 根据TLB项判断是否符合访问规范
  • 符合规范后再分段查询页表，返回物理地址

TLB

TLB，即Translation Lookaside Buffer，是专门针对页表项的高速缓存Cache，其内容是页表中的一部分或全部内容

• TLB的工作流程
  • 接收CPU产生的逻辑地址并将其分解为虚拟页码和页内地址
  • 根据页码号在TLB中寻找有无对应的条目：成功匹配则返回物理块；若未命中则前往完整页表中寻找，并将页表项复制进TLB中
  • 最终合成出物理块+页内地址形式的物理地址
• 通常TLB的条目数在$64\textasciitilde1024$之间，并且有些条目有可能不能被替换出TLB（比如内核代码）
• ASID：其可以用来唯一地标识进程，只有当申请访问的程序和页表项对应的进程一致（ASID相同）才允许访问，否则即说明页表项失效
  • （说明不同的程序正在访问相同的虚拟页码，因不同程序的映射规则不同，对应的物理块也不会一致，此时存放的物理块号是错误的）
  • 如果允许TLB同时包含多个进程的页表项时，每次选择页表TLB都必须被flushed或删除，以确保下一个进程不会使用不匹配的映射

反置页表

一般意义上的页表构造了一个虚拟页$\to$物理块的映射，当虚拟页数量大时会消耗大量内存；而反置页表则是构建了一个物理块$\to$虚拟页的映射，其为每个物理块都说明了对应的虚拟页

• 反置页表项：进程ID|逻辑页号
• 反置页表中，每一个物理块$i$都对应着反置页表的第$i$项，而第$i$项的信息则提示了这个物理块属于哪个进程、对应了哪个逻辑页
• 通过构造反向的映射，反置页表的大小只与物理内存的大小相关
• 反置页表的工作流程：
  • 利用进程ID和虚拟页号在反置页表中遍历所有项（相当于查询所有物理块）
  • 如第$i$项产生匹配，则该虚拟页对应的**物理块号就为$i$**；如未发生匹配，则说明此虚拟页未存放在内存中，申请从主存中调页
  • 
• 可以借助哈希表，将反置页表改造成反置链表：通过虚拟页码指向对应链表的头，进而仅查询该链表中的表项，从而减少遍历带来的时间消耗
  • 
  • （只查询图中Page Table中的Chain内容即可）
• 采用反置页表的系统难共享内存：每个物理块只对应一个虚拟页条目

页共享与保护

• 页的共享：对于多个程序需要共享同一个物理块的数据/程序时，应让它们包含该块的虚拟地址全部指向相同的物理块
• 共享带来的问题：
  • 若共享、不共享数据被划分在同一块内，将泄露数据；可以采用分段存储管理的方式专门对公开数据进行共享
• 页的保护：
  • 地址越界保护
  • 在页表中设置保护位：定义访问时的操作权限（有可能不同进程对相同的共享数据拥有不同的权限）

分段式存储管理

对于一个程序的各组成部分来说，他们对内存的需求并不相同

• 编程用户
  • 用户一般按照逻辑关系对作业分段，并根据名字访问程序段和数据段
• 信息共享
  • 共享是以信息的逻辑单位——段，为基础的；而存储却是以物理单位——页，进行的
  • 共享段的难度要比共享页的难度高
• 信息保护
  • 一个页中可能存放了多个程序的内容，简单的页分享可能会导致数据的错误泄露
  • 可以对信息采取段为单位进行分享和保护
• 动态增长
  • 在进程运行的过程中，某些数据段可能会不断增长，存储管理方法存在困难
• 动态链接
  • 在程序运行时才把目标程序和主程序进行链接

分段地址空间

将段作为地址的分割依据，使得地址空间由各个分段组成，这些段可以不相连，但一个段的内部地址一定连续

• 逻辑地址结构：段号|位移量
  • 分区：按照磁盘的物理地址对内存进行划分
  • 分页：按照固定大小的页对内存进行划分
  • 分段：按照程序段长度对内存进行划分（分段长度自由，前两者都已固定）

段表

• 段表记录了段号与内存物理地址的对应关系，并存放于内存当中
• 基址与长度由段表寄存器给出
• 优点：
  • 易于实现段的共享与保护
• 缺点：
  • 处理地址花费时间，也要考虑段表的占用内存
  • 为满足分段的动态增长、减少外碎片，要采用拼接内存的手段
  • 在辅存中难管理不定长度的分段
  • 分段尺寸受到内存大小的限制，不能超出内存空间

地址变换过程

• 查询申请访问的段号是否在段表内，如果超界则产生中断
• 检查段内位移量是否超出段的长度，如果超界则产生中断
• 若均为越界，则返回对应段号所在的物理地址基址，与段内位移量相加则得到物理地址

段共享

若对于某一个程序/程序段，会被众多用户/程序调用，那么就可以共享这个段，声明其为可重入的，这样只需要保留一份只读代码在内存当中即可

分页式与分段式的比较

• 分页式地址空间是一维线性的；分段式则是二维地址空间
• 页是信息的物理单位，其大小固定；段是信息的逻辑单位，其大小不定（但总具有完整的意义）
• 分页用户不可见，系统直接操作内存；分段用户可见

分页有效解决了碎片问题，同时使得程序可以不连续存放

分段实现了数据高效共享与保护，可便捷所需空间动态增长的程序，也利于动态链接

段页式内存管理

段页式内存管理是分段、分页原理的结合：系统先将程序分为若干段，再把每段按照固定大小进行分页

• 逻辑地址结构：段号|段内页号|页内地址
• 访问时先访问内存的段表，找到对应页表的起始地址；再查该段的页表，找到段内页号对应的物理块号，最后根据物理块和页内地址访问物理内存
• 在逻辑上，程序被分成了长度不同的段，段内连续；在空间上，程序的段被分为了长度相同的页，段内不连续

x86的段页式实现（待补）

覆盖与交换

覆盖，就是一个相对独立的程序单位。一个大的程序可以划分为一系列的覆盖

• 覆盖段：程序执行时并不要求同时装入主存的一组覆盖；这个覆盖段被分到同一个存储区域（覆盖区）
• 使用覆盖则必须在编程时提前确定模块间的覆盖关系，时间换空间

交换，把暂时不用的数据/程序从内存转移到辅存中，再把使用的数据转入主存

• 交换可以增加并发的程序数目；提供适当的响应时间
• 交换会增加处理机开销；没有考虑执行过程中地址访问的统计特性

因为在同一个覆盖段内的两个覆盖不会同时使用，所以可以对两个覆盖进行交换

局部性原理

局部性原理指在执行过程中的一个较短的时间内执行的指令和其操作数的地址都在都某区域内并受到约束

• 时间局部性：一条指令、一段数据的前后两次访问集中在某时间内
• 空间局部性：邻近的几条指令，访问的数据集中在某区域内
• 当程序出现对某数据结构的多次操作，通常局限在较小的范围内

快排的局部性比堆排好：堆排使得数据在整个数组内做大范围的跳动，而快排的数据访问间隔比较小，显然快排的空间局部性更好

虚拟存储

虚拟存储为每个进程提供了一个连续完整的地址空间，利用了主存和磁盘的特点（类似于Cache和主存的关系，下沉了一层，但两者有一定区别）

虚拟内存把地址空间定义为连续的虚拟内存地址，欺骗程序在使用一大段连续地址

• 每个进程都认为自己正在独占系统的所有内存；但并不是所有内容都直接放置在内存中，操作系统遵循覆盖的规则保留一部分内容
• 虚存保护了每个进程的地址访问操作，防止出现冲突
• 虚拟存储在主存和硬盘存储间交换，利用了主存的快速、硬盘的大空间特点

虚拟存储的基本原理

• 按需装载：只需要将当前需要的分页/分段读入内存，后续需要的页/程序段在使用时再读入
• 缺页调入：在执行过程中发生缺页/缺段时从磁盘调入内存
• 不用调出：操作系统将内存不常用的页/段归还磁盘外存，调出后的空间供新的页/段调入使用

虚拟存储的特征

• 离散性：物理内存分配上的不连续性、虚拟地址使用上的不连续性
• 多次性：（分时复用）分多次调用程序进入内存，使得虚拟存储具有了在逻辑上扩大内存的功能；这时虚拟存储最重要的特征
• 对换性：内存、外存可进行交换，提高内存利用率
• 虚拟性：虚拟存储允许程序从逻辑的角度上访问存储器，而不需考虑实际的物理空间

虚拟性以多次性和对换性为基础

多次性、对换性以离散性为基础

优点：

• 程序调用的内存限制扩大，通常大于物理内存
• 可容纳更多的程序并发执行
• 不影响编程时的程序结构（与覆盖技术相比）

缺点：

• 时间换空间，以CPU工作时间和内外存交互的长时间为代价

限制：

• 虚拟内存的最大容量由计算机的地址结构决定

虚拟内存与Cache

相同点：

• 都为分层存储体系：充分利用高速存储器的速度和低速存储器的容量
• 原理相同：利用程序的局部性原理，进行信息的部分调用

不同点：

• Cache侧重访问低速存储器的速度问题，虚存侧重高速存储器的容量问题（+内存管理、保护等）
• CPU可直接访问内存；但不能直接访问外存，仍需要调取至内存才能访问
• 透明性不同：Cache作为硬件对程序员透明；虚存采用软件管理，受操作系统控制（对实现存储管理的系统程序员不透明，对应用管理员透明）
• 损失不同：主存未命中的损失远大于Cache未命中的损失

虚拟内存名词解释

进程的逻辑空间（虚拟空间）

使用虚存技术后对单个程序可见的空间，从0开始编址。这段空间逻辑上连续，但并不实际存在于内存/外存中

虚拟地址空间与虚拟存储（内存）空间

进程的虚拟地址空间是进程在内存中存放的逻辑视图

一个程序的虚拟地址空间与虚拟存储空间大小相同

交换分区

一段按页划分的磁盘空间，对用户不可见

在物理内存不足时存放内存数据，为其他进程解放物理内存

虚拟内存需要解决的问题

• 地址映射问题：进程的逻辑空间到实际内存的映射问题
• 调入问题：调入机制、调入块的选择
• 替换问题：调出相关问题
• 更新问题：内存、外存数据的同步
• 其他问题：存储保护、程序重定位等

虚存的地址映射

• 内核在进程创建时没有把程序与数据交换进物理内存中（此时仅建立虚存-磁盘的映射），等到需要使用时才会通过缺页机制交换数据
• 用户可执行文件和共享库都以文件的形式存储在磁盘中，在页表中类型为file backed
• heap和stack在磁盘上没有对应的文件，类型为anonymous，地址为空
• 未分配部分没有对应的页表项，只有当malloc申请内存时才建立页表项

虚存的调用机制

调入主存的数据有两类：

• OS的核心程序与数据
• 正在运行的用户进程相关的程序与数据

借助缺页错误处理机制进行调用

• 调用时间：

  • OS在系统启动时调入
  • 用户数据调入有不同策略：预调页、按需调页

• 预调页：同时将所有页都调入内存中，阻止大量开始运行时产生的页错误

• 按需调页：只有当缺页时才进行调用，类似使用交换的分页系统

• 缺页错误处理机制过程：

  • 现场保护：发现异常进入内核态，保存现场信息
  • 页面定位：查找异常的虚拟页面
  • 权限检查：检查虚拟地址有效性、安全保护位，出错则kill
  • 新页面调入1：通过页面置换找到一个需要换出的物理页
  • 旧页面写回：把这个物理页写回外存（需要置为忙状态，以防被其他进程抢占）
  • 新页面调入2：将虚存所需的页面从外存调入内存
  • 更新页表：项操作系统发出中断，更新内存的页表项
  • 恢复现场

实存管理与虚存管理

实存管理方法：分区、分页、分段、段页式

虚存管理方法：（向外存）请求分页、请求分段、请求段页式

请求分页/段式系统

与原本的分页/段式类似，只不过内存中只存放了部分的程序和数据，待其启动后再按需从外存中以页/段为单位进行调用即可

• 硬件支持：页表/段表机制、缺页/缺段时的中断机构和地址变换机构
• 软件支持：请求调页/段、请求页/段置换的功能
• 页表项：
  • 驻留位：1-在内存；0-在外存
  • 保护位：只读、可写、可执行
  • 修改位：此页在内存中有无修改操作
  • 访问位：用于页面置换算法

虚存页面置换策略

最优置换策略

把所有页中未来最久不会被使用的页替换出去

• 具有最低的页错误率，然而这种方法不可能被实现

先进先出策略

当需要替换页时，把最先进入的页替换出去

• 借助一个队列，新访问的页面插入队尾，替换的页从队首出队
• 性能较差：较早调入的页访问通常较多
• Belady现象：分配的页面数增多，但缺页率却增高的现象

FIFO的置换特征，与进程访问内存的动态特征是矛盾的

Second Chance策略、Clock（最近未使用算法）策略

Second Chance是改进后的FIFO法，给每一个页面一个标记位，记录此页面是否被访问过

• 如果将要被换出的页面曾被访问过，就清除标记位，放至队尾重新入队；否则直接出队
• 当所有页面都被访问过时，也直接出队

Clock在Second Chance的基础上变更为了环形队列；在注意指针移动的基础上，其余操作保持一致

• FIFO类算法对比：
  • 命中率：Clock = Second > FIFO
  • 复杂度：Second > Clock > FIFO
  • 代价：Second > Clock > FIFO

LRU（最近最少使用）策略

根据页面的历史访问记录进行替换：最近使用过的数据将来的访问几率更高

这种算法是局部性原理的合理近似，但硬件开销较大

• 设置一个栈，保存当前的所有页面号
• 当某个页面被访问时，取出栈中的页面号，重新压栈
• 当需要替换时，退出栈底的元素

AGING（老化算法）策略（*待补）

AGING是LRU的一种简化，性能上接近LRU，但减少了硬件开销

• 为每个页面设置一个移位寄存器，并设置一位访问位R，每隔一段时间，所有寄存器右移1位，并将R值从左移入。

虚存同步更新问题

当一个页面被换出时，为了保持内存外存信息的一致性，必要时需要进行信息的更新

• 换出页面为file backed类，并未被修改：直接discard，因外存含有副本
• 换出页面为file backed类，但有修改：写回原有位置，因外存副本过期
• 换出页面为anonymous类，若第一次换出+未修改：写入Swap区；否则discard
• 换出页面为anonymous类，且有修改：写入Swap区

工作集与驻留集管理

• 工作集：过去一段时间内进程访问的页面集合
• 驻留集：进程被分配的物理页集合

工作集策略

引入工作集是为了调整驻留集的大小

当进程开始执行后，工作集随着页面加载逐渐稳定；当进程的局部性区域变化时，工作集进行一次快速扩张和收缩，再到达一个稳定的值

页表与自映射

假设页式内存管理中，一页大小为 a Byte，一个页表项的大小为 b Byte，且页表起始地址为 x（保证页对齐），求页目录（自映射）的地址？

在实验课中我们很容易就能回答，答案是 x + x >> 10，但是怎么来的还是要有自己的理解。

首先可知，页表在所有页面的第 x / a 页上，那么页目录就应该从页表的起始地址向后数和页面数同样多的页表项数，这样取到的页表项就恰好对应页表的起始地址，也就是向后数 (x / a) * b Byte

最后再加上起始的页表基地址，结果为 x + (x / a) * b

在这里代入 MOS 的数据，就是 x + (x / 4096) * 4 = x + x >> 10了