《操作系统》内存管理

内存管理概念

常考点

覆盖交换技术相关
- 使用交换技术时，一个进程正在I/O操作，则不能交换出主存；开辟一个缓冲I/O区后，可以交换出主存
- 覆盖和交换的提出是为了解决主存空间不足的问题，不是从物理上解决，而是将暂时不用的部分换出主存以节省空间，从而在逻辑上扩充主存
- 单一连续存储管理可采用覆盖技术
程序运行过程
- 形成逻辑地址的阶段：链接
- 形成物理地址的阶段：装入或程序运行时
重定位相关
- 动态重定位是在作业的执行过程中进行的
- 静态重定位是在装入的时候进行的
- 固定分区可以采用静态重定位（装入后位置不再改变）
- 在整个系统设置一个重定位寄存器，用来存放程序在内存中的始址
其他
- 内存保护需要由OS和硬件机构合作完成，以保证进程空间不被非法访问

基本概述

内存管理
- 内存管理时操作系统对内存的划分和动态分配
内存管理目的
- 为了更好地支持多道程序并发执行
- 方便用户
- 提高内存利用率
内存管理功能
- 内存空间的分配与回收：由OS完成主存储器空间的分配和管理
- 地址转换：存储管理将逻辑地址转换为物理地址
- 内存空间的扩充：利用虚拟存储技术/自动覆盖技术，从逻辑上扩充内存
- 内存共享：允许多个进程访问内存的同一部分
- 存储保护：保证多道作业在各自的存储空间运行，互不干扰
内存管理分配
- 连续分配：$单一连续分配\rightarrow（单道发展到多道OS）\rightarrow固定分区分配\rightarrow（为了适应大小不同的程序）\rightarrow动态分区分配$
- 不连续分配：$分段存储管理\rightarrow分页存储管理\rightarrow段页存储管理$

将程序变成可在内存中执行的程序过程【即程序的链接与接入过程】

过程图

编译
- 由编译程序将用户源代码编译程若干目标模块
链接
- 由链接程序将目标模块和库函数链接，形成完整的装入模块
- 链接类别
  - 静态链接
  - 动态链接
  - 运行时动态链接
装入
- 由装入程序将装入模块装入内存运行
- 装入类别
  - 静态装入：在编译时计算好物理地址
  - 可重定位装入：装入时把逻辑地址转换为物理地址，但装入后不能改变
  - 动态重定位装入：执行时再决定装入的地址并装入，装入后有可能会换出

逻辑地址与物理地址

逻辑地址
- 定义
  - 每个目标模块都从0号单元开始编址的地址
- 特点
  - 不同进程可以有系统的逻辑地址，这些逻辑地址可以映射到主存的不同位置
  - 进程运行时，看到和使用的地址都是逻辑地址
  - 将逻辑地址转换为物理地址的过程叫做地址重地位
物理地址
- 物理地址空间是指内存中物理单元的集合
特点
- 物理地址是地址转换的最终地址

进程的内存映像

内存映像
- 定义
  - 当一个进程调入内存运行时，就构成了进程的内存映像
- 组成要素
  - 代码段：代码段是只读的，可以被多个进程共享
  - 数据段：程序运行时加工处理的对象，包括全局变量和静态变量
  - 进程控制块PCB：存放在系统区，OS通过PCB控制和管理进程
  - 堆：用来存放动态分配的变量【动态的】
  - 栈：用来实现函数调用的【动态的】

内存保护

目的
- 确保每个进程都有一个单独的内存空间
方法
- 方法1：在CPU中设置一对上下限存储器，判断CPU访问的地址是否越界
- 方法2：使用重定位寄存器和界地址寄存器（只有OS内存才可以使用这两个寄存器）
  - 界地址寄存器/基地址寄存器含最小的物理地址值【用于加】
  - 界地址寄存器含逻辑机制的最大值【用于比】
  - 逻辑地址+重定位寄存器的值 = 物理地址

内存共享

概念
- 只有只读区域的进程空间可用共享
- 纯代码/可重入代码 = 不能修改的代码，不属于临界资源
- 可重入程序通过减少交换数量来改善系统性能
实现方式
- 段的共享
- 基于共享内存的进程通信（第二章的同步互斥）
- 内存映射文件

内存管理方法

常考点

共享相关
- 段的共享是通过两个作业的段表中相应表项指向被共享的段的统一物理副本实现的
存储器相关
- 对主存储器的访问以字节或字为单位
- 对主存储器的分配以块或段为单位
其他
- 确定一个地址需要几个参数，作业地址空间就是几维的

分页、分段和段页

分段
- 地址映射表
  - 每个进程由多个不等的段组成
- 地址结构
  - 段号+段内偏移
- 地址结构维度
  - 二维
- 供谁感知
  - 供用户感知
- 划分单位
  - 以段为单位分配
  - 每段是一个连续存储区
  - 每段不一定等长
  - 段与段之间可连续，也可不连续
- 长度
  - 段长不固定
- 访问主存次数
  - 2次
- 碎片情况
  - 只产生外部碎片
分页
- 地址映射表
  - 每个进程一张页表，且进程的页表驻留在内存中
- 地址结构
  - 页号+页内偏移
- 地址结构维度
  - 一维
- 供谁感知
  - 供操作系统感知
- 划分单位
  - 逻辑地址分配按页分配
  - 物理地址分配按内存块分配
- 长度
  - 页长固定
- 访问主存次数
  - 2次
- 碎片情况
  - 产生内部碎片
段页式
- 地址映射表
  - 每个进程一张段表，每个段一张页表
- 地址结构
  - 段号+段内页号+页内偏移量
- 地址结构维度
  - 二维
- 供谁感知
  - 无
- 划分单位
  - 分段方法来分配管理用户地址空间
  - 分页方法来管理物理存储空间
- 长度
  - 段长不固定，页长固定
- 访问主存次数
  - 3次
- 碎片情况
  - 产生内部碎片

连续分配

定义
- 连续分配管理是为一个用户程序分配一个连续的内存空间
特点
- 用户程序在主存中都是连续存放的
- 非连续分配的方式的存储密度<连续分配方式
碎片
- 内部碎片：当程序小于固定分区大小时，也要占用一个完整的内存分区，导致分区内部存在空间浪费
- 外部碎片：内存中产生的小内存块
分类
- 单一连续分配
  - 定义
    - 此方法下，内存分为两个区
      - 系统区：供OS用，在地址区
      - 用户区，内存用户空间由一道程序独占
  - 优点
    - 简单，无外部碎片
    - 无需内存保护（内存中永远只有一道程序）
  - 缺点
    - 只能用于单用户单任务的OS
    - 有内部碎片，存储器利用率极低
- 固定分区分配
  - 定义
    - 用户内存空间划分为固定大小（分区大小相等或不等）的区域
    - 每个区装一道作业
  - 优点
    - 简单
  - 缺点
    - 程序太大可能放不下任何一个分区，有内部碎片
    - 不能实现多进程共享一个主存区，存储空间利用率低
- 动态分区分配
  - 进程转入内存时，根据内存实际需要，动态低分配内存且动态分区在作业装入是动态建立的
  - 动态分配算法
    - 首次适应算法
      - 次序
        
        按地址递增的次序
      - 特点
        
        最简单，效果最好，速度最快
    - 邻近适应算法
      - 特点
        
        比首次适应算法差
    - 最佳适应算法
      - 次序
        
        按容量递增的次序
      - 特点
        
        性能很差，会产生最多的外部碎片
    - 最坏适应算法
      - 次序
        
        按容量递减的次序
      - 特点
        
        可能导致没有可用的大内存块，性能差

分段

概念
- 分段 = 程序由若干个逻辑分段组成，不同的段有不同的属性，用分段的方式把程序分离
- 段表 = 一张逻辑空间与内存空间映射的表
段的共享与保护
- 段的共享：通过两个作业的段表中相应表项指向被共享的段的同一物理副本
- 段的保护
  - 存储控制保护
  - 地址越界保护
优缺点
- 优点
  - 能产生连续的内存空间
  - 分段存储管理能反映程序的逻辑结构并有利于段的共享和保护
  - 段的动态链接与逻辑结构有关，分段存储管理有利于程序的动态链接
- 缺点
  - 会产生外部碎片
  - 内存交换的效率低
- 特点
  - 满足程序员/用户
  - 方便编程，分段共享
  - 分段保护，动态链接，增长
  - 分段管理地址空间是二维的
  - 每段的长短不同
地址变换
- 物理地址 = 段基址 + 偏移量

利用段表实现物理内存区映射

分段系统的地址变换过程

分页

概念
- 分页：把整个虚拟和物理内存空间切成一段段固定尺寸的大小，在linux中，每页的大小为4KB
页/页面
- 页面就是进程中的块
- 页面大
  - 页内碎片增多，降低内存的利用率
- 页面小
  - 进程的页面数大，页表过长，占用大量内存，增加硬件地址转换的开销，降低页面换入/换出的效率
- 地址结构
  - 地址结构 = 页号P + 页内偏移量W
  - 地址结构决定了虚拟内存的寻址空间有多大
  - 完成地址转换工作的是硬件的地址转换机构，而不是地址转换程序
- 页表
  - 页表就是记录页面在内存中对应的物理块号
  - 页表的起始地址放在页表基址寄存器PTBR中
  - 页表是存储在内存里的，内存管理单元（MMU）就做将虚拟内存地址转换成物理地址的工作
- 相关计算1
  - 设有2GB内存，页大小为4KB，页表大小为4B
    - 共有$\frac{2GB}{4KB} = 512K 个块/页$，即每个页表有512K项
    - 页表大小 = 512 X 4B = 2MB
    - 即只要2MB就可以表示512K个页
- 相关计算2
  - 一个由32位二进制组成的地址空间，页面长度为4KB，每个页表项占用4B，请问地址字结构
    - 因页面长度为4KB，所以页面偏移占 12 位
    - 余下20位对应页号，所以进程的页面总数可达 1M 个
    - 整个页表占用 4 MB，这4MB又划分为 1K 个页面
- 优缺点
  - 优点
    - 能有效地提高内存利用率
  - 缺点
    - 会产生内部碎片
  - 特点
    - 逻辑地址分配按页分配
    - 物理地址分配按内存块分配
    - 划分的页面大小都相同
    - 所有进程都有一张页表
    - 页表存在内存中
    - 分页是面向计算机的
    - 整个系统设置一个页表寄存器用于存放页表在内存中起始地址和长度

分页的地址变换

基本地址变换
- 把虚拟内存地址，切分成页号和偏移量
- 根据页号，从页表里面，查询对应的物理页号
- 直接拿物理页号，加上前面的偏移量就能够得到物理内存地址
- 缺点
  - 分页产生的页表过大，使用多级页表来解决空间上的问题

两级页表地址变换
- 一级页表覆盖到全部虚拟地址空间，二级页表在需要时创建
- 建立多级页表的目的在于建立索引，以便不用浪费主存空间存储无用的页表项，也不用盲目地顺序式查找页表项
- 页表寄存器存放的是一级页表起始物理地址
- 多层参与，时间上开销大，加入TLB，提高地址的转换速度

具有快表的地址变换
- 快表是相联存储器（TLB）
- 快表也叫页表缓存，转址旁路缓存
- 快表专门存放程序最常访问的页表项的Cache
- 快表位于CPU芯片中，用于加速地址变换的过程
- CPU芯片中，封装了MMU（内存管理单元）
- MMU用来完成地址转换和TBL的访问与交互

段页

实现方法
- 将程序划分为多个有逻辑意义的段【分段】
- 对分段划分出来的连续空间，再划分固定大小的页【分页】
地址变换
- 作业的逻辑地址划分为：段号，段内页号，页内偏移量
- 对内存的管理以存储块为单位，地址空间是二维的
- 演示图例

得到物理地址的3次内存访问
- 访问段表，得到页表起始地址
- 访问页表，得到物理页号
- 将物理页号与页内偏移组合，得到物理地址

虚拟内存的实现

常考点

虚拟存储概念相关
- 虚拟存储器的最大容量是由计算机的地址结构决定的，与主存容量和外存容量没有关系
- 虚拟存储技术基于程序的局部性原理，局部性越好，虚拟存储系统越能更好地发挥作用
- 虚拟存储技术只能基于非连续分配技术
- 使用覆盖、交换方法可以实现虚拟存储
页面置换算法
- 无论采用什么页面置换算法，每种页面第一次访问时不可能在内存中，必然发生缺页，所以缺页次数$\geq$不同的页号数量
缺页中断
- 请求分页存储器中，页面尺寸增大，存放程序需要的页帧数减少，缺页中断次数也会减少
- 影响缺页中断的时间有：缺页率，磁盘读写时间，内存访问时间
- 缺页中断可能执行的操作：置换页面，分配内存（不会进行越界出错处理）
- 缺页处理过程中可能执行的操作：修改页表，分配页框，磁盘I/O（内存没有页面，需要从外存读入）
其他
- 系统调用是由用户进程发起，请求OS的服务
- 创建新进程可以通过系统调用完成
- 可以加快虚实地址转换的操作：增大快表TLB的容量，让页表常驻内存
- 当磁盘利用率很高，但是CPU利用率不高时，改进CPU利用率的操作：增大内存的容量，减少多道程序的度数

基本概念

传统存储管理方式特征
- 一次性：作业必须一次性全部装入内存，才能开始运行
- 驻留性：作业被装入内存后，就一直驻留在内存中，直到作业结束
- 运行中的进程会因等待I/O而被阻塞，可能处于长期等待状态
局部性原理
- 时间局部性：程序中的某条指令一但执行，不久后该指令可能再次运行，出现的原因是程序中存在大量的循环结构
- 空间局部性：程序在一段时间内所访问的地址，可能集中在一定的范围内
虚拟存储器
- 定义
  - 系统为用户提供的一个比实际内存容量大得多的存储器
- 特征
  - 多次性：只需将当前运行的那部分程序和数据装入内存即可开始运行【最重要特征】
  - 对换性：作业无需一直常驻内存，要用时换入，不要时换出
  - 虚拟性：从逻辑上扩充内存的容量【最重要的目标】
- 虚拟内存的实现
  - 方式（离散分配）
    - 请求分页存储管理
    - 请求分段存储管理
    - 请求段页式存储管理
  - 需要的东西
    - 一定的硬件支持，一定容量的内存和外存
    - 页表/段表机制作为主要的数据结构
    - 中断机制，当程序要访问的部分还未调入内存时，产生中断
    - 地址变换结构

请求分页管理方式

特点
- 只要求将当前一部分页面装入内存，即可启动作业运行，不需要一次全部装入
- 在作业执行的过程中，当访问的页面不存在时，再通过调页功能将其调入
相比基本分页管理增加的功能
- 请求调页功能：将要用的页面调入内存【调入】
- 页面置换功能：将不用的页面换出到外存【调出】
页表的构成
- 页号
- 页框号
- 状态位P
- 访问字段A
- 修改位M
- 外存地址L
页面机制新增字段
- 状态位/合法位P
  - 标记该页是否已被调入内存中
  - 供程序访问时参考，用于判断是否触发缺页异常
- 访问字段A
  - 记录本页在一段时间内被访问的次数
  - 供置换算法换出页面时参考
- 修改位M
  - 标识该页在调入内存后是否被修改过
  - 当页面被淘汰时，若页面数据没有修改，则不用写回外存
- 外存地址L
  - 用于指出该页在外存上的地址，通常为物理块号
  - 供写回外存和从外存中调入此页时参考
缺页中断
- 定义
  - 缺页是在CPU执行某条指令过程中，进行取指令或读写数据时发生的一种故障，是内中断或叫做异常
- 产生时间
  - 每当要访问的页面不在内存中时，便产生一个缺页中断，请求OS将所缺的页调入内存
  - 缺页中断是访存指令引起的，说明所要访问的页面不在内存中
  - 进行缺页中断处理并调入所要访问的页后，访存指令应该重新执行
- 特点
  - 在指令执行期间而非一条指令执行完后产生和处理中断信号
  - 一条指令在执行期间，可能产生多次缺页中断
地址变换机构新增功能
- 产生和处理中断信号
- 从内存中换出一页
地址变换过程

页框分配（进程准备执行时，由OS决定给特定进程分配几个页框）

驻留集
- 给一个进程分配的物理页框（物理块）的集合
驻留集大小
- 分配给进程的页框越少，驻留在内存的进程就越多，CPU的利用率就越高
- 进程在主存中的页面过少，缺页率相对较高
- 分配的页框过多，对进程的缺页率没有大的影响
分配策略
- 固定分配局部置换：物理块固定，缺页时先换出一个线程再调入所缺页
- 可变分配全局置换：物理块可变，缺页时增加物理块再调入所缺页
- 可变分配局部置换：物理块可变，若不频繁缺页则用局部置换，频繁换页再用全局置换
- 对各进程进行固定分配时页面数不变，不可能出现全局置换
物理块调入算法
- 平均分配算法
- 按比例分配算法
- 优先权分配算法
调入页面的时机
- 预调页策略 = 运行前的调入
  - 主要用于进程的首次调入，由程序员指出应先调入哪些页
- 请求调页策略 = 运行时的调入
  - 调入的页一定会被访问，策略易于实现
  - 每次仅调入一页，增加了磁盘I/O开销
请求分页系统外存组成
- 存放文件的文件区【采用离散分配方式】
- 存放对换页面的对换区【采用连续分配方式】
- 兑换区的磁盘I/O速度更快
从何处调入页面
- 系统拥有足够的对换区空间
- 系统缺少足够的对换区空间
- UNIX方式
如何调入页面
- 所访问的页面不在内存时
  - 缺页中断
  - 无空闲物理块
  - 决定淘汰页
  - 调出页面
  - 调入所缺页面
- 所访问的页面不在内存时
  - 缺页中断
  - 有空闲物理块
  - 调入所缺页面

页面置换算法

最佳置换算法OPT（Optimal replacement）
- 被淘汰的页面
  - 以后永不使用
- 特点
  - 基于队列实现的
  - 该算法无法实现
  - 只能用于评价其他算法
先进先出置换算法FIFO(First In First Out)
- 被淘汰页面
  - 在内存中驻留时间最久的页面
- 特点
  - 会出现Belady异常（分配的物理块数增大但页故障数不减反增）
  - 性能差，但实现简单
最近最久未使用置换算法LRU（Least Recently Use）
- 最淘汰的页面
  - 最近最长时间未访问过的页面
- 特点
  - 性能好，但实现复杂
  - 需要寄存器和栈道硬件支持
  - 堆栈类算法
  - 耗费高因为要对所有页排序
时钟置换算法CLOCK
- 被淘汰的页面
  - 最近未使用的页面
- 特点
  - FIFO和LRU的结合

其余零散知识点

抖动/颠簸
- 定义
  - 在页面置换时，出现频繁的页面调度行为
  - 所有页面置换策略都有可能造成抖动
- 产生原因
  - 系统中同时运行的进程太多$\rightarrow$分配给每个进程的物理块太少$\rightarrow$进程在运行时频繁出现缺页$\rightarrow$频繁的调动页面
  - 主要原因是因为页面置换算法不合理
- 解决方法
  - 撤销部分进程
  - 增加磁盘交换区大小和提高用户进程优先级都与抖动无关
工作集
- 定义
  - 在某段时间间隔内，进程要访问的页面集合
- 如何确定
  - 基于局部性原理，用最近访问过的页面来确认
- 作用
  - 工作集反映了进程在接下来一段时间内可能频繁访问的页面集合
  - 为了防止抖动现象，要使分配给进程的物理块数>工作集大小
内存映射文件
- 定义
  - 与虚拟内存相似，将磁盘文件的全部或部分内容与进程虚拟地址空间的某区域建立映射关系
- 作用
  - 可以直接访问被映射文件，不必执行文件I/O操作，无需对文件内容进行缓存处理
- 优点
  - 适合用来管理大尺寸文件
虚拟存储器性能影响因素
- 页面较大$\rightarrow$缺页率较低$\rightarrow$可以减少页表长度，但使得页内碎片增大
- 页面较小$\rightarrow$缺页率较高
  - $\rightarrow$可减少内存碎片，提高内存利用率
  - $\rightarrow$使页表过长，占用大量内存
- 分配给进程的物理块越多，缺页率就越低
- 分配给进程的物理块数超过某个值时，对缺页率的改善并不明显
- 好的页面置换算法可以使进程在运行过程中具有较低的缺页率
- LRU，CLOCK将未来可能要用到的进程保存在内存中，可以提高页面的访问速度
- 编写程序的局部化程度越高，执行时的缺页率越低
- 存储和访问尽量使用系统的访问方式
地址翻译
- CPU中的控制寄存器和页表基址寄存器（PTBR）指向当前页表
- CPU传来的n位虚拟地址分为两个部分
  - 虚拟页号：作业到页表中的索引，与PTBR结合可得具体PTE
  - 虚拟页面偏移：将PTE中存储的物理页号与虚拟地址中的虚拟页面偏移结合起来，可得相应物理地址

使用页表的地址翻译