OS_第四章内存管理

OS OS

Created At : 2024-02-27 21:58

Count:7k Views 👀 :

Comment:

第四章-内存管理

第四章-内存管理

内存管理概述
- 存储器的层次结构
- 程序的装入与链接
  - 程度的链接
    - 静态链接方式：在 程序运行之前 ， 将各目标模块及它们所需的库函数链接成一个完整的装配模块，以后不再拆开 ，需进行（1） 相对地址修改 （2） 变换外部调用模块 ，如上图中 jmp(L)、jmp(L+M)等
    - 装入时动态链接：在 装入内存时 ，采用 边装入边链接的链接方式 ，即在装入一个目标模块时， 若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块 。
    - 运行时动态链接：将 对某些模块的链接推迟到程序执行时才进行 ，在执行过程中，若发现一个被调用模块尚未装入内存时，立即由OS去找到该模块，并将其装入内存，，将其链接到调用者模块上。
    - 三种链接方式比较
      - 静态链接方式：调用模块必须含有其目标模块的拷贝， 可执行文件、难以实现“内存” 模块共享
      - 装入时动态链接方式： 便于软件版本的修改和更新；便于实现目标模块为多个应用程序共享
      - 运行时动态链接方式： 装入时动态链接方式的改进 ，将某些目标模块的链接推迟到执行时根据是否需要再完成， 更加有利于内存的有效利用
  - 程序的装入：由装入程序将装入模块载入内存
    - 绝对装入方式（ 单道程序环境 ）：程序被加载到内存的固定地址上，采用绝对地址
    - 静态可重定位装入方式（ 多道程序环境 ）
      - 重定位：程序装入或执行时对装入模块或目标程序中的 指令及数据地址 的修改过程， 静态可重定位 指的是将 装入模块装入内存时一次性完成重定位 ， 需要连续存储空间，装入后不能移动。
    - 动态运行 时装入方式（ 运行中移动位置 ）：需要 特殊硬件支持 （地址变换机构），以保证地址转换不会影响指令的执行速度， 便于动态链接和代码共享
连续分配存储管理方式
- 单一连续分配方式：内存划分为系统区和用户区，单用户单任务
  - 内存划分为 系统区和用户区
  - 整个 用户区为一个用户独占，仅驻留一道程序
  - 静态链接 和 动态重定位技术 、存储器保护措施
  - 仅适用于 单用户、单任务操作系统 中
- 固定分区分配方式：用户区进一步划分为 多个固定区域 ，开始支持多道程序
  - 用户区分为 若干固定区域
  - 每个分区可装入一道作业
  - 分区划分方法( 等分/不等分)
  - 分区说明表 与 内存分配算法
  - 可用于 多道程序存储管理
- 动态分区分配方式：用户区进一步地 动态地对内存空间分配
  - 分配用数据结构
    - 空闲分区表
    - 空闲分区链
  - 分区分配算法（ 基于顺序搜索，适用于不太大的系统 ）
    - 首次适应算法（First Fit FF ）
    - 循环首次适应算法(Next Fit NF )
    - 最佳适应算法(Best Fit BF )
    - 最坏适应算法（Worst Fit WF ）
  - 分区分配算法（ 基于索引搜索，适用于中/大型系统，有效提高空闲分区检索速度 ）
    - 快速适应算法/分类搜索算法（quick fit）：
      - 将 空闲分区根据其容量大小分类 ，对于 每一类具有相同容量 （2KB、4KB、8KB等）的所有空闲分区， 单独设立一个空闲分区链表 ， 系统中存在多个空闲分区链表
      - 同时，在内存中 设立一张管理索引表 ，每一个 索引表项对应了一种空闲分区类型 ，并记 录了该类型空闲分区链表表头的指针 。
      - 搜索可分配的空闲分区：
        
        第一步：根据进程的长度，从索引表中寻找能容纳它的最小空闲区链表
        
        第二部：从链表中取下第一块进行分配，需要注意的是：该算法在进行空闲分区分配时， 不会对任何分区进行切割 ，所以 能保留大的分区 ， 满足对大空间的需求，也不会产生内存碎片
      - 优缺点： 优点：查找效率高；缺点：一个分区只分给一个进程，以空间换时间，存在空间的浪费
    - 伙伴系统
      - 无论是 已分配或空闲区 ，大小均为 2的k次幂
      - 系统 初始态 ，整个内存区是一个大小为 2的m次的空闲区
      - 系统运行过程， 不断二分 ，直到找到一个不大不小的分区
      - 对于 相同大小的所有空闲分区 ， 单独设立一个空闲分区双向链表
    - 哈希算法：相对于前两者， 不需要建立管理索引表 ，而是 根据空闲分区在可利用空闲区表中的分布规律 ，建立 hash函数，构造一张以空闲分区大小为关键字的哈希表 ，该表的每一个 表项记录了一个对应的空闲分区链表表头指针
  - 分区分配与回收操作
    - 分区分配操作
    - 分区回收操作：回收的三种情况：
- 动态可重定位分区分配方式：基本与动态分区分配方式相同， 差别仅在于：增加了紧凑的功能，对碎片进行了处理
  - 紧凑技术：将内存中的 作业进行移动 ，将众多 碎片拼接成一个大的分区 ，每次 紧凑后 ，必须对 作业进行重定位 ，为了 不影响系统的效率 ，通过 动态重定位 进行支持
  - 动态重定位
  - 动态重定位分区分配流程
- 对换技术与覆盖技术
  - 对换技术（ 对换分区采取的连续分配方式 ）
    - 对换的概念： 多道程序环境下 ，将 内存中暂时不能运行的进程 或暂时不用的 程序和数据换出到外存 上， 提高内存空间利用率
    - 对换的类型
      - 整体对换（ 处理机的中级调度 ）：以 整个进程为单位
        
        进程的换出
        
        选择被换出的进程（进程状态（ 阻塞/睡眠 ）+优先级（最低）+内存驻留时间）
        
        进程换出的过程（换出 非共享或不再共享 的程序及数据段 -> 申请对换空间 -> 换出 -> 内存释放 -> 修改内存分配数据结构及PCB）
        
        进程的换入
        
        选择被换入的进程（进程状态（ 就绪状态、已换出 ）+换出时间（最久）
      - 页面（分段）对换：以 进程的一个页面或分段为单位 进行对换，其目的是 为了支持虚拟存储系统
    - 对换（磁盘）空间的管理
      - 磁盘空间 分为 文件区 和 对换区 ， 对换区只占用磁盘空间的小部分
      - 对换区使用情况数据结构：空闲盘区表/链（盘块组为基本单位）
      - 对换区分配与回收操作： 对换分区采取的是连续分配方式 ，故 与动态分区分配/回收方式雷同
  - 覆盖技术
  - 对换技术与覆盖技术的区别
    - 对换主要是在 不同进程、作业 之间进行
    - 覆盖是在 同一进程、作业 中进行
离散分配存储管理方式：解决连续存储管理方式的 碎片问题以及紧凑开销
- 基于分页存储管理方式：将 用户程序的地址空间分为若干个页面 ；相应地，将 内存空间分为若干个物理块或页框（frame） ， 页与块的大小相同 ，这样便可将用户的任一页放入任一物理块中
  - 分页地址中的地址结构
    - 页号+偏移量
    - 逻辑地址与分页地址之间的地址转换
  - 地址变换结构
    - 基本的地址变换结构
      - 首先， 逻辑地址 被 自动划分 为 页号和页内地址 两部分，以页号为索引去检索页表
      - 执行检索之前， 先将页号与页表长度作比较 ，若 页号大于页表长度，发生越界中断
      - 若 未发现越界错误 ，则将 页表始址 与（ 页号和页表项长度的乘积 ）相加，得到在页表中的位置
      - 最后 映射得到的物理块号与页内偏移地址相加 得到最终的 物理地址
    - 具有快表的地址变换结构（ 提高数据检索的速度 ）
      - 为了 提高地址变换速度 ，在 地址变换结构中增设 一个 具有并行查询能力 的 特殊高速缓冲寄存器 ，称为“ 联想寄存器”/“快表 ”
      - 在CPU给出有效地址后，首先 将页号送入高速缓冲寄存器中 ，并 将此页号与高速缓存中的所有页号进行比较 ， 若匹配到，表示所要访问的页表项在快表中
      - 若没有匹配到 ，则 执行基本地址变换机构的操作 ， 最后要将检索到的页表项存入快表中
    - 两级和多级页表
      - 引入的原因 ：现代计算机系统支持非常大的逻辑地址空间(2^32~2^64)，页表变得庞大。例如，对于具有 32位逻辑地址空间的分页系统 ，规定 页面大小为4KB即2^12B ，则每个 进程页表的页面可达1M 个；若同时 设定页表项大小为4B ，则每个 进程仅页表便需占用4MB 内存空间 ，且要求是 连续的
      - 基本思想 ： 对页表按内存物理块大小进行分页 ，对它们进行编号并 离散地存放于不同的物理块 中；同时 为离散分配的页表分页再建立一张页表 ，称之为 外层页表 ，以记录各页表分页对应的物理块号
      - 两级页表结构示意图
        
        解决了页表占用连续大内存的问题，解决离散存储问题，不减少页表的大小
        
        多层页表的设置增加了访问内存的次数，两级页表结构需要访问三次内存才能取到数据
      - 两级页表地址变换结构
      - 多级页表结构（例题）
    - 反置页表
      - 概要： 反置页表为每个物理块设置一个页表项 ，并 将页表项按照物理块的号码排序 ， 页表项的内容 包括该 物理块号对应的页号 以及 隶属进程标识符 ，利用 反置页表进行地址变换 时，使用 进程标识符 以及页号去 检索反置页表 ，若 找到对应的表项 ，则 以该表项序号即该页所在物理块 号与 页内偏址构成物理地址
      - 反置页表地址变换
      - 例题：对于一个具有 64MB 的机器，如果 页面大小为4KB ，那么 反置页表占用64KB内存 ， 物理块个数 ：64MB/4KB = 16K 一个物理块可以放的页表项个数 ：4KB/4B = 1K 反置页表需要的物理块数 ：16K/1k =16; ANS : 16*4KB = 64KB
- 基于分段存储管理方式
  - 分段存储管理方式的引入
    - 方便编程： 满足用户在编程和使用上的多方面要求
    - 信息共享：以段是信息的逻辑单位为基础 ，因此可以为共享过程建立一个独立的段，简化了共享的实现
    - 信息保护： 以段是信息的逻辑单位为基础 ，以一个过程、函数或文件为基本单位进行保护
    - 动态链接：以段是信息的逻辑单位为基础 ，在程序运行过程中，当调用某个目标程序时，才将该段调入内存并进行链接
    - 动态增长：例如数据段的动态增长
  - 分段系统的基本原理
    - 分段：
      - 作业地址空间被划分成若干段 ，若 主程序MAIN、子程序段X、数据段D以及栈段S ， 各个段都有自己的段号（名字） ；
      - 每个段都从0开始编址，并采用一段连续的地址空间（缺点） ，段的长度可以不相等；
      - 整个作业的地址空间是二维的，逻辑地址由段号和段内地址组成
    - 段表：
      - 用于 实现作业地址空间与在内存中物理地址的映射
    - 地址变换结构
      - 首先， 将逻辑地址中的段号 与 段表寄存器中的段表长度比较 ，若 大于段表长度，则越界中断
      - 然后，根据 段表始址＋段号 检索段表 ，得到在 内存中的物理地址基址
      - 再 将段内地址与段长比较 ， 若大于段长，则越界中断；若未越界，将段内地址＋物理地址基址则为最终的物理地址
    - 分段与分页系统的主要区别
      - 相似之处 ：两者都采用 离散分配方式 ，且都是 通过地址映射机构实现地址变换
      - 目的不同 ： 分页是系统管理上的需要 ， 页面是信息的物理单位；分段主要是用户的需要，分段是信息的逻辑单位。
      - 分页/分段长度不同 ： 分页的大小 由系统决定，是 固定的 ； 分段的长度 取决于用户，是 不固定 的
      - 分页/分段作业地址空间维度不同 ： 分页的用户程序地址空间是一维的 ，属于单一的 线性地址空间 ； 分段的程序地址空间是二维的 ，用户需要 同时给出段名和段内地址 。
  - 分段系统信息共享 分页系统也可以实现信息共享，分段系统相对更容易实现
    - 可重入代码的概念：（ 代码区共享，数据区私有 ）
      - 一种 允许多个进程同时访问的代码；
      - 为使各个进程所执行的代码完全相同，绝对不允许可重入代码在执行中有任何改变，所以它是一种不允许任何进程对其进行修改的代码。
      - 但事实上，大多数代码在执行时都有可能发生改变，例如其中用于控制程序执行次数的变量及指针、信号量及数组等。为此， 在每个进程中都必须配备局部数据区，并把在执行中可能改变的部分都拷贝到该数据区。 这样， 在程序执行时，只修改属于特定进程私有的数据区中的内容，而不去改变共享的代码，这时的可共享代码即成为可重入代码
    - 信息共享比较举例说明： 某多用户系统，可同时接纳40个用户 ，假设均在 执行Editor编辑文本 。若该 文本编辑程序含有160KB的代码区和40KB的数据区 ，则 总共需要8000KB的内存空间来支持40个用户 ； 如果该文本编辑程序代码是可重入的， 则无论分页系统还是分段系统该程序代码都能被共享，即内存中只需保留一份文本编辑程序的副本， 因而所需内存空间仅为40×40+160=1760KB
      - 分页系统实现的信息共享
      - 分段系统实现的信息共享
- 段页式存储管理方式： 分页与分段相结合，广泛采用
  - 优越性： 分页系统能有效地提高内存利用率 ， 很好地解决内存的外部碎片问题以及为各个分段离散地分配内存等问题 ； 分段系统则能很好地满足用户需要 ， 便于实现、分段可共享、易于保护、可动态链接等一系列优点。
  - 基本原理：
    - 先对作业进行分段，再对每个分段进行分页
    - 作业地址空间和地址结构
    - 段页存储管理的地址映射
  - 地址变换过程
虚拟存储器概念及其关键技术
- 虚拟存储器的概念 ：所谓 虚拟存储器，是指仅把作业的一部分装入内存便可运行作业的存储器系统 。具体地说，所谓 虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上扩充内存容量的一种存储器系统。 实际上， 用户看到的大容量只是一种感觉，是虚的 ，故而得名虚拟存储器， 其逻辑容量由内存和外存容量之和决定 ，其 运行速度接近于内存速度，而每位的成本却又接近于外存 。
- 局部性原理 ：程序在执行时将呈现局部性规律，即在一较短时间内，程序的执行仅限于某个部分；相应地，它所访问的内存空间也仅局限于某个区域；局部性表现形式：时间局部性（指令执行与数据结构访问）空间局部性（存储单元临近访问）
- 虚拟存储器的特征
  - 离散性 ：离散分配方式
  - 多次性 ：作业被分成多次调入内存和运行
  - 对换性 ：程序和数据在作业运行过程中的换进/出
  - 虚拟性 ：内存容量的逻辑扩充
请求分页存储管理方式
- 硬件支持
  - 请求页表机制：
    - 基本作用：将用户地址空间中的逻辑地址映射为内存空间中的物理地址
  - 缺页中断机构：
    - 基本特征
      - 保护CPU现场
      - 分析中断原因
      - 转入缺页中断处理程序
      - 恢复CPU现场
    - 缺页中断的特殊性
      - 在 指令执行期间产生和处理 中断信号
      - 一条指令执行期间，可能产生多次缺页中断 ，如图产生6次缺页中断
  - 地址变换机构：
    - 在分页系统的地址变换机构的基础上， 增加缺页中断的产生和处理，以及页面置换功能 ；
- 内存分配策略和算法
  - 最少物理块数的确定： 最少物理块： 保证进程正常运行所需的最少物理块数， 若系统为某进程分配的物理块数少于此值，进程将无法正常运行
  - 内存物理块分配与置换策略
    - 固定分配局部置换： 固定分配 ：为 每个进程分配一组固定数目的物理块 ， 在进程运行期间不再改变 ； 局部置换 ：若进程运行过程中 发生缺页中断 ，只能从分配给进程的n个页面中选择一页换出， 保证分配给进程的内存空间不变
    - 可变分配全局置换： 可变分配 ：先为每个进程分配一定数目的物理块，在 进程运行期间，可根据具体情况做适当的增减 ； 全局置换 ：进程在运行过程中发生缺页中断， 首先将OS所保留的空闲物理块中取出一块分给该进程 ； 若没有剩余，从全部进程的物理块中选择一块换出，然后分配给缺页的进程 。总的来说， 全局置换可以使缺页进程的内存空间增加，若是从别的进程抢来的，则是此消彼长。
    - 可变分配局部置换：当 进程发生缺页中断 后，从 该进程中选择一页换出 ，若该进程 频繁发生缺页中断 ，则 根据缺页率酌情为其增/减物理块
  - 物理块分配算法
    - 平均分配算法：将系统可供分配的 物理块平均分配
    - 按比例分配算法：根据 进程的大小按比例分配物理块
    - 考虑优先权的分配算法： 照顾重要或紧迫的进程 能尽快完成，为它分配较多的内存空间
- 调页策略
  - 何时调入页面
    - 预调页策略：将那些 预计在不久之后便会被访问的程序 或数据所在的页面， 预先调入内存 ， 以预测为基础，主要用于进程首次调入
    - 请求调页策略：当进程在运行中需要访问某部分程序和数据时， 若发现其所在的页面不在内存，应立即提出请求 ，由系统将其所需页面调入内存； 易于实现但系统开销大
  - 何处调入页面（针对外存而言， 外存分为文件区和对换区 ， 文件区离散分配，对换区连续分配 ）
    - 对换区空间充分： 进程运行前 ，便须将与该进程有关的文件， 从文件区拷贝到对换区
    - 对换区空间不足： 对于不会被修改的文件 ，都直接 从文件区调入 ； 对于可能修改的文件 ， 换出时将其调到对换区 ， 调入时从对换区调入
    - UNIX方式： 凡未运行过的页面都应从文件区调入 ，而对于 曾运行过又被换出到对换区的页面则从对换区调入
  - 页面调入过程
    - 缺页中断发生
    - 根据页表项给定外村地址调入所缺页面
    - 内存不足置换
- 页面淘汰算法
  - 抖动与缺页率的概念
    - 抖动：若所用置换算法不当，刚被换出的页面很快又被访问，需重新调入，为此，又需再选一页换出， 频繁地更换页面
    - 缺页率： 缺页率 = 缺页中断次数/页面访问次数
  - 最佳淘汰算法（ 向后看 ）
    - 基本思想： 选择永不使用或是在最长时间内不再被访问 （即距现在最长时间才会被访问）的页面淘汰出内存
    - 理想化算法，具有最好性能 （对于固定分配页面方式，本法可保证获得最低的缺页率），但 无法实现 ，故主要 用于算法评价参照
    - 举例说明：
  - 先进先出淘汰算法
    - 基本思想： 选择最先进入内存 即在内存驻留时间最久的页面换出到外存
    - 简单直观 ，但 不符合进程实际运行规律 ， 性能较差 ，故实际 应用极少
    - 举例说明：
  - 最长时间未使用（最近最久未使用）淘汰算法（ LRU （Least Recently Used） ）
    - 硬件支持 ：
      - 移位寄存器
        
        当 进程访问某物理块时 ，将 最高位置为1
        
        定时信号 每隔一定时间 将寄存器右移一位
        
        具有最小数值 的寄存器对应的页面就是 最近最久未使用 的页面
      - 栈
        
        用栈保留 当前使用的页面号
        
        当进程访问某页面，将该页面 从栈中移出，压入栈顶
        
        栈底为最近最久未使用的页面
    - 基本思想： FIFO 算法是 向前看 ， LRU ，则是 向最近的前面看 ，（ 两算法看的方向一致，但是FIFO有点极端，LRU则是最近的前面 ）选择 最近最久未使用的页面淘汰
    - 适用于各种类型的程序， 性能较好 ，但 需要较多的硬件支持
    - 举例说明：
  - 最少使用淘汰算法（ LFU Least Frequently Used ）
    - 硬件支持： 移位寄存器 ，与LRU算法的硬件支持需求一致
    - 基本思想：为内存各个页面设置一个移位寄存器，当访问该页面，将最高位置为1， 选择在一个时钟周期（通常是ns级）次数最少的页面淘汰
    - 鉴于仅用移位寄存器有限各位来记录页面使用会导致（时钟中断间隔内） 访问一次与访问多次的等效性，本算法并不能真实全面地反映页面使用情况
  - 时钟式淘汰算法（ LRU近似算法，又称为NRU （Not Recently Used） ）
    - 为每个页面 设置一位访问位 ，当访问该页面时，将访问位置为1
    - 改进型时钟式淘汰算法（为每个页面 设置两位标志位：访问位（A）修改位（M） ）
      - 页面四种状态：
        
        （A=0，M=0） ：表示该页最近即未访问，又未修改， 最佳淘汰页面
        
        （A=0，M=1） ：表示该页最近未访问，但是已被修改， 并不是很好的淘汰页，但是可以选择淘汰
        
        （A=1，M=0） ：表示该页最近被访问，未修改， 该页有可能再被访问
        
        （A=1，M=1） ：表示该页最近即访问又修改， 该页可能再被访问
      - 算法流程：
        
        首先扫描循环队列， 选择（A=0，M=0）的第一个页面淘汰 ， 若没有找到，下一步
        
        开始第二轮扫描 ， 选择（A=0，M=1）的第一个页面淘汰 ， 同时将所有页面的A置为0 ， 若没有找到，转第一步
      - 评价：与简单时钟式淘汰算法相比， 可减少磁盘的I/O操作次数 ， 但淘汰页的选择可能经历多次扫描，故实现算法自身的开销增大
  - 页面缓冲算法
    - 基本思想：设置空闲页面链表和已修改页面链表
      - 空闲页面链表 ：将系统中的空闲物理块（用于分配给频繁缺页的进程）链接成一个链表， 进程中被换出的物理块（未修改），将其挂在空闲页面链表尾；此外，当进程频繁缺页，可将空闲页面链表中的空闲物理块分配给该进程
      - 已修改页面链表 ： 若进程需要把一个（已修改）的页面换出 ， 将该页面挂在已修改页面链表表尾，并不换到外存上； 当已修改链表达到一定长度，一起将所有已修改页面写回磁盘
    - 显著降低了页面换进换出的频率，使磁盘IO次数大大减少
请求分段存储管理方式
- 硬件支持
  - 段表项的扩充
  - 地址变换机构
  - 缺段中断机构
    - 缺段中断机构同样需要在一条 指令的执行期间产生和处理
    - 在一条指令执行期间可能产生多次缺段中断 。 但由于分段是信息的逻辑单位 ，因而 不可能出现一条指令被分割在两个分段中和一组信息被分割在两个分段中的情况
    - 由于段不是定长的，因此缺段中断的处理要比缺页中断的处理复杂
- 分段共享
  - 共享段表
  - 共享段的分配与回收：对于 第一个请求使用某共享段的进程 ，由 系统为该共享段进行内存区的分配和装入 ，同时把共享段信息填入对应进程段表中，并在共享段表中为之增加一个表项和填写相关内容； 对于以后其它进程提出共享该段要求，则仅需对对应的进程段表表项及共享段表表项修正即可
- 分段保护
  - 越界检查： 由地址变换机构完成
  - 存取控制检查： 存取控制检查以段为基本单位进行 ，访问方式有 只读、只执行，读写 ；共享段的存取控制应 对不同进程赋予不同权限，既要保证信息安全，又要满足运行需要
  - 环保护机构（ 功能较完善的保护机制 ）
    - 小编号具有高优先权 （小编号，大能量）
    - 调用高级服务，访问低级数据

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2542608082@qq.com