第5章 内存管理

单选题6题 多选题2题

5.1 内存管理的基本任务

1. 内存管理的任务

   • 内存空间
     • 系统区——用以存放操作系统常驻内存部分，用户不能占用这部分空间
     • 用户区——分配给用户使用，用于装入并存放用户程序和数据
     • 存储管理实质上就是管理供用户使用的那部分空间
   • 内存管理问题
     • 内存管理方法
     • 内存的分配和释放算法
     • 虚拟存储器的管理
     • 控制内存和外存之间的数据流动方法
     • 地址变换技术
     • 内存数据保护与共享技术

   存储管理的主要任务

   (1) 内存的分配与回收

   • 功能
     • 记住每个存储区域的状态
     • 实施分配（静态分配与动态分配）
     • 回收
   • 组织方式
     • 位示图表示法：用一位(Bit)表示一个空闲页面（0表示空闲，1表示占用）
     • 空闲页面表：包括首页面号和空闲页面个数，连续若干页面作为一组登记在表中
     • 空闲块表：空闲块首址和空闲块长度，没有记录的区域即为进程所占用
   • 内存分配方式
     • 静态分配
       • 在程序运行过程中不允许再申请或在内存中“搬家”
       • 分配工作是在程序运行前一次性完成
     • 动态分配
       • 在程序运行过程中，允许申请附加的内存空间或在内存中“搬家”
       • 分配工作可以在程序运行前及运行过程中逐步完成

   (2) 存储共享

   • 定义
     • 两个或多个进程共用内存中的相同区域
     • 好处：动态地共享内存，提高内存利用率
   • 内容
     • 代码共享：必须是纯代码
     • 数据共享
   • 目的
     • 通过代码共享节省内存空间，提高内存利用率
     • 通过数据共享实现进程通信

   (3) 存储保护

   • 存储保护的目的：为多个程序共享内存提供保障
   • 需要有硬件支持，并由软件配合实现
   • 内容包括：保护系统程序区不被用户有意或无意的侵犯；不允许用户程序读写不属于自己地址空间的数据
   • 地址越界保护：对进程所产生的地址必须加以检查
   • 权限保护：必须对公共区域的访问加以限制和检查

   (4) “扩充”内存容量

2. 地址转换

   (1) 地址重定位

   • 存储器以字节（每个字节为8个二进制位）为编址单位，每个字节都有一个地址与其对应，这些地址称为内存的“绝对地址”，与绝对地址对应的内存空间称为“物理地址空间”。
   • 用户程序中使用的地址称为“逻辑地址”，与逻辑地址对应的存储空间称为“逻辑地址空间”。
   • 把逻辑地址转换成绝对地址的工作称为 “地址重定位”或“地址转换”，又称“地址映射” 。
   • 重定位的方式有 “静态重定位”和“动态重定位” 两种。

   (2) 静态重定位

   • 静态重定位的地址转换工作是在程序开始执行前集中完成的，在程序执行过程中就不再进行地址转换工作。

   (3) 动态重定位

   • 动态重定位：在装入程序时，不进行地址转换，而是直接把程序装入到分配的内存区域中。在程序执行过 程中，每当执行一条指令时都由硬件的地址转换机构将指令中的逻辑地址转换成绝对地址。
   • 硬件 + 软件
     • 硬件要有一个地址转换机构，可由一个基址寄存器和一个地址转换线路组成。
   • 采用动态重定位时，装入内存的程序保持原来的逻辑地址，可改变程序在内存中的存放区域。
   • 程序在内存中被移动位置后，只要把新区域的起始地址代替原来在基址寄存器中的值，程序仍可正确执行。
   • 采用动态重定位的系统支持“程序浮动”

5.2 分区储存管理方案

1. 概念

   • 分区存储管理是能满足多道程序运行的最简单的存储管理方案。
   • 基本思想：把内存划分成若干个连续区域（分区），每个分区装入一个运行程序。
   • 分区的方式
     • 固定分区
     • 可变分区

2. 固定分区

   (1) 基本思想

   • 固定分区是指系统先把内存划分成若干个大小固定的分区，在系统运行期间不再重新划分。
   • 各分区的大小可以不同，可以满足不同程序的存储要求。
   • 每一分区的大小是固定的，可容纳程序的大小有所限制，必须提供对内存资源的最大申请量。

   (2) 内存分配表与分区的分配、回收

   • 用于固定分区管理的内存分配表是一张分区说明表
   • 区号—大小—起始地址—状态
   • 工作流程
     • 运行的程序
     • 查找空闲的、大小合适的分区
     • 修改分区的状态
     • 系统回收
     • 修改分区的状态（改为空闲）
   • 缺点
     • 不能充分利用内存
     • 分区方案灵活性差
     • 可接纳程序的大小受分区大小的严格限制

3. 可变分区

   (1) 基本思想

   • 可变分区是指系统不预先划分固定分区，而是在装入程序时划分内存分区，使为程序分配的分区的大小正好等于该程序的需求量，且分区的个数是可变的。
   • 工作流程
     • 系统初启——空间为一个完整的大空闲区
     • 有程序要求装入内存运行——该空闲区中划分出一块与程序大小相同的区域进行分配
     • 当系统运行一段时间后——会一系列的内存分配和回收
     • 注意：若有上下相邻的两块空闲区，系统应将它们合并成为一块连续的大空闲区

   (2) 移动技术

   • 为什么提出移动技术？
     • 在可变分区管理方案中，随着分配和回收次数的增加，必然导致碎片的出现。
   • 解决碎片问题的方法
     • 在适当时刻进行碎片整理，把所有空闲碎片合并成一个连续的大空闲区且放在内存的一端。
   • 过程称为“移动技术”或“紧凑技术”或“紧缩技术”
   • 移动技术可以集中分散的空闲区，提高内存的利用率，便于作业动态扩充内存。
   • 移动技术产生的问题
     • 会增加系统的开销
     • 移动有条件：若某个进程正在与外部设备交换信息，与该进程有关的数据块就不能移动
   • 在采用移动技术时应该尽可能减少需要移动的作业数和信息量。

   (3) 可变分区的实现

   • 采用可变分区方式管理时，要有硬件的地址转换机构作支持。
   • 硬件设置两个专用的控制寄存器：基址寄存器和限长寄存器。
     • 基址寄存器用来存放程序所占分区的起始地址
     • 限长寄存器用来存放程序所占分区的长度。
   • 为了实现可变分区的管理，必须设置某种数据结构用以记录内存分配的情况，确定某种分配策略并且实施 内存的分配与回收。
     • 已分配区表：记录已装入的程序在内存中占用分区的起始地址和长度，用标志位指出占用分区的程序名
     • 空闲区表：记录内存中可供分配的空闲区的起始地址和长度，用标志位指出该分区是未分配的空区。

   (4) 空闲分区的分配策略

   • 最先适应算法——顺序查找分区说明表，找到第一个满足申请长度的空闲区，将其分割并分配

   • 最优适应算法——找到第一个能满足申请长度的最小空闲区，将其分割并分配

   • 最坏适应算法——查找分区说明表，找到能满足申请要求的最大的空闲区

   • 下次适应算法——从上一次分配的位置开始扫描内存，选择下一个大小足够的可用块

   (5) 分区的回收

   • 回收分区的上邻分区是空闲的，需要将两个空闲区合并成一个更大的空闲区，然后修改空闲区表。
   • 包收分区的下邻分区是空闲的，需要将两个空闲区合并成一个更大的空闲区，然后修改空闲区表。
   • 回收分区的上邻分区和下邻分区都是空闲的，需要将三个空闲区合并成个更大的空闲区，然后修改空闲区表。
   • 回收分区的上邻分区和下邻分区都不是空闲的，则直接将空闲分区记录在空闲区表中。

4. 分区管理方案的优缺点

   • 优点
     • 让内存真正成了共享资源，有效地利用了处理机和I/O设备
     • 提高了系统的吞吐量和缩短了周转时间
   • 缺点
     • 内存使用仍不充分，并且存在着较为严重的碎片问题。
     • 不能为用户提供“虚存”， 每一个用户程序的存储要求仍然受到物理存储器实际存储容量的限制。

5.3 页式存储管理方案

1. 基本思想

   • 页式存储管理是对分区方式管理内存的补充，可以解决分区管理的缺点（当内存中无足够大的连续空间时, 程序就无法装入）。
   • 页式存储管理可以把一个逻辑地址连续的程序分散存放到几个不连续的内存区域中，并且保证程序的正确 执行，可充分利用内存空间，减少移动所花费的开销。
   • 内存分块（每块大小相等），块是进行主存空间分配的物理单位
   • 程序的逻辑地址分页，页的大小与块的大小一致，可把程序信息按页存放到块中
   • 页式存储器提供编程使用的逻辑地址由两部分组成：页号和页内地址
     • 假定地址（逻辑地址）用m个二进制表示，其中页内地址部分占用n个二进制位，那么，每一页的长度就是2ⁿ个字节，也就是每一个内存块有2"个字节。 这时，页号部分占用了m-n位，所以，最大的程序可允许有2^(m-n)个页面。

2. 存储空间的分配与回收

   • 页式存储管理方式内存空间
     • 以物理页面（块）为单位——物理页面的大小是固定的
     • 三种不同的标识
       • 哪些块已经分配
       • 哪些块尚未分配
       • 当前剩余的空闲块数
   • 简单的内存分配表可以用一张 “位示图”构成。位示图中的每一位与一个内存块对应，每一位的值可以是0或1，0表示对应的内存块为空闲，1表示已占用。同时增加一个字节记录空闲块数。
     • 在进行内存分配时，先查看空闲块数是否能满足程序要求
     • 若不能满足则不进行分配，程序就不能装入内存
     • 若能满足，则进行分配，程序就能装入内存
   • 分配过程
     • 当找到一个为0的位后，根据它所在的字号、位号，按如下公式就可计算出对应的块号
     • 块号 = 字号 * 字长 + 位号
     • 把程序装入到这些内存块中，并为该程序建立页表。
     • 假定归还块的块号为i，则在位示图中对应的位置为：字号 = [i/字长]，位号 = i mod 字长

3. 地址转换与快表

   (1) 页式存储管理的地址转换

   • 页式存储管理
     • 页表控制寄存器
       • 页表起始地址寄存器——保存运行进程的页表的首地址
       • 页表长度寄存器——保存运行进程的页表的长度
     • 高速缓冲存储器
   • 页表指出该程序逻辑地址中的页号与所占用的内存块号之间的对应关系，又是硬件进行地址转换的依据。
   • 页表的长度由程序拥有的页面数而定，每个程序的页表长度可能是不同的。
   • 物理地址的计算公式为：物理地址 = 内存块号 * 块长 + 页内地址
   • 把内存块号作为绝对地址的高位地址，而页内地址作为它的低地址部分。
   • 页表的长度由程序拥有的页面数而定，且需要连续存放。

   (2) 页表

   • 多级页表（以32bit地址空间来说明：有分页系统，地址空间32位，页面大小为4KB，设每个页表项需要4B）
     • 一级页表
       • 页号占20bit，即2²⁰个页号，需要2²⁰个页表项
       • 要求2²⁰ * 4B= 4MB 空间连续存放页表
     • 二级页表
       • 每页可存放4KB/4B= 1K = 2¹⁰个页表项
       • 页表的业内地址为10bit，每个页表的页号有2¹⁰，也为10bit
       • 页目录也有2¹⁰，页目录10bit
   • 散列页表
     • 虚拟页号——(a)虚拟页表、(b)所映射的页框号、(c)指向链表中下一个元素的指针
     • 基本思想：由虚拟页号得到散列值来查找散列页表，并将此页号与链表中的第一个元素的字段(a)进行比较。
     • 如果匹配，则相应的页框号[字段(b)]就可用于形成物理地址。
     • 如果不匹配，则沿链表依次寻找相匹配的表项。
   • 反置页表
     • 在反置页表中，每个物理页框对应一个表项，每个表项包含与该页框相对应的虚拟页面地址以及拥有该页面进程的信息。
     • 整个系统中只存在一个页表，并且每个页框对应其中一个表项。
     • 在反置页表中存放地址空间标志符保证了一个特定进程的逻辑页面可以映射到相应的物理页框上。
     • 反置页表是按照物理地址排序的，在使用时却是按照虚拟地址查找。
     • 反置页表的实例：64位的UltraSPARC和PowerPC

   (3) 快表(TLB)

   • 提高存取速度
     • 在地址映射机制中增加一组高速寄存器保存页表
     • 在地址映射机制中增加一个小容量的联想寄存器（由高速缓冲存储器组成）
       • 利用高速缓冲存储器存放当前访问最频繁的少数活动页面的页号
       • 快表中登记了页表中的一部分页号与内存块号的对应关系。
   • 快表
     • 只存放当前进程最活跃的少数几页
     • 进程的推进会导致快表的内容动态更新。
       • 当用户程序需要存取数据时，根据该逻辑页号在快表中找出对应的内存块号，然后拼接页内地址，以形成物理地址
       • 在快表中没有相应的逻辑页号， 则地址映射通过内存中的页表进行
       • 在得到内存块号后需将该块号填到快表的空闲单元中
       • 若快表中没有空闲单元，则根据置换算法置换某一行，再填入新得到的页号和块号
     • 优点：采用快表后，地址转换的时间大幅下降

5.4 虚拟页式存储管理方案

1. 虚拟存储技术

   (1) 基本思想

   • 利用大容量的外存来扩充内存，产生一个比实际内存空间大得多的、逻辑的虚拟内存空间（虚存）
   • 由操作系统在硬件支持下把两级存储器（内存+外存）统一管理，达到“扩充”内存的目的
   • 实现虚拟存储器的硬件支持
     • 系统有容量足够大的外存
     • 系统有一定容量的内存
     • 最主要的是：硬件提供实现虚-实地址映射的机制

   (2) 工作原理

   • 当进程开始运行时，先将一部分程序装入内存，另一部分暂时留在外存
   • 当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存的工作
   • 当没有足够的内存空间时，系统自动选择部分内存空间，将其中原有的内容交换到磁盘上，并释放这些内存空间供其他进程使用
   • 程序的运行不受内存容量约束的、虛拟的、能够满足自己需求的存储器。

   (3) 交换技术

   • 定义：指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。
   • 分类
     • 整体交换（进程交换）：以整个进程为单位的。
     • 页面（分段）交换：以进程的一个页面（或分段）为单位进行换入换出，统称为部分交换。
   • 交换技术是实现请求分页和分段式存储管理的基础，其目的是为了支持虚拟系统。
   • 具有对换功能的OS中，把磁盘空间分为文件区和对换区
     • 文件区
       • 存放各类文件，访问频率低，占磁盘大部分空间
       • 采用离散分配方式管理，提高空间利用率
     • 对换区
       • 存放内存换出的数据，对换频率极高，占磁盘少部分空间
       • 采用连续分配方式管理，提高换入和换出的速度

2. 虚拟页式存储管理

   (1) 基本思想

   • 在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之 后根据进程运行的需要，动态装入其他页面
   • 当内存空间已满，而又需要装人新的页面时，则根据某种算法置换出某个页面，以便装入新的页面。
   • 虚拟页式存储管理需增加表项
     • 页号：页面的编号
     • 有效位：又称驻留位、存在位或中断位，表示该页是在内存还是在外存。
     • 页框号：页面在内存中时所对应的内存块号
     • 访问位：又称引用位或参考位，表示该页在内存期间是否被访问过
     • 修改位：表示该页在内存中是否被修改过
     • 禁止缓存位：采用内存映射I/O的机器中需要的位

   (2) 缺页中断

   • 若在页表中发现所要访问的页面不在内存，则产生缺页中断。
   • 当发生缺页中断时，操作系统必须在内存中选择一个页面将其移出内存，以便为即将调入的页面让出空间。

   (3) 页面调度策略

   • 调入策略（确定什么时候调入）
     • 只在缺页时调入，也只调入发生缺页时所需的页面，实现简单，产生较多的缺页中断，造成对外存I/O次数多，时间开销过大，容易产生抖动现象
   • 置页策略（确定调度页面放在何处）
     • 当线程产生缺页中断时，内存管理器还必须确定将调入的虚拟页放在物理内存的何处
   • 置换策略（确定哪些页面被调出）
     • 分配策略：固定分配策略、可变分配策略
     • 置换策略：全局置换、局部置换
     • 固定分配局部置换：为每一进程分配固定的页数的内存空间，在整个运行期间都不再改变。
     • 可变分配全局置换：先为系统中的每一进程分配一定数量的物理块，操作系统本身也保持个空闲物理块队列。
     • 可变分配局部置换：为每一进程分配一定数目的内存空间。

   (4) 页面置换算法

   • 先进先出页面置换算法(FIFO)
     • 思想：总是选择最先装入内存的一页调出，或者说是把驻留在内存中时间最长的一页调出。
     • 实现：把装入页面的页号按进入的先后次序排好队列，每次总是调出队首的页，当装入一个新页后，把新页的页号排入队尾。
   • 最近最少使用页面置换算法(LRU)
     • 基本思想：选择距离现在最长时间内没有被访问过的页面先调出。
     • 置换原理：已经很久没有使用的页面很有可能在未来较长的一段时间内不会被用到（指的是使用的时间）
     • 在页表中为每一页增加一个“计时”标志，每被访问一次都应从“0”开始重新测时
     • 当要装入新页时，检查页表中各页的计时标志，从中选出计时值最大的那一页调出，并且把各页的计时标志全置成“0”，重新计时
   • 最近最不常用页面置换算法(LFU)
     • 基本思想：根据在一段时间里页面被访问次数少的页面调出。
     • 每一页设置一个计数器，每当访问一页时，就把该页对应的计数器加1
     • 选择计数值最小的那页调出，同时把所有的计数器清“0”
   • 理想页面置换算法(OPT)
     • 基本思想：置换以后不再需要的或者在最长时间以后才会用到的页面。
     • 一般不可能实现，可以作为衡量其他页面置换算法优劣的一个标准。
   • 最近未使用页面置换算法(NRU)
     • 基本思想：随机地从类编号最小的非空类中挑选一个页面淘汰之。
     • 置换的方法：当访问页面（读或写）时设置R位；当写入页面（即修改页面）时设置M位。
     • 当发生缺页中断时，操作系统检查所有的页面并根据它们当前的R位和M位的值，把它们分为如下4类：
       • 第0类：没有被访问，没有被修改（R=0,M=0，编号00) 第1类：没有被访问，已被修改（R=0,M=1，编号01 ) 第2类：巳被访问，没有被修改（R=1,M=0，编号10) 第3类：已被访问，已被修改（R=1,M=1，编号11)
   • 第二次机会置换算法
     • 基本思想：寻找一个最近的时钟间隔以来没有被访问过的页面。
     • 实现：页面设置读位R，缺页时检查进入内存时间最久页面的R位，如果R为0，那么这个页面既老又没有被使用，立即置换掉；如果R为1，就将R位清0，并把该页面放到链表的尾端，修改其进入时间，然后继续搜索。
   • 时钟页面置换算法(Clock)
     • 基本思想：把所有的页面都保存在一个类似时钟面的环形链表中，一个表针指向最老的页面。
     • 置换的方法：当发生缺页中断时，算法首先检查表针指向的页面，如果它的R位是0就置换该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找到一个R位为0的页面为止。

   (5) 缺页中断率

   • 假定一个程序共有n页，系统分配给它的内存块是m块（m、n均为正整数，且1≤m≤n）。因此，该程序最多有m页可同时被装入内存。如果程序执行中访问页面的总次数为A，其中有F次访问的页面尚未装入内存，故产生了F次缺页中断。 缺页中断率：f=F/A (总次数/缺页中断次数)
   • 影响缺页中断率的因素有：
     • 分配给程序的内存块——分配给程序的内存块数多，则同时装人内存的页面数就多，故减少了缺页中断的次数，也就降低了缺页中断率。
     • 页面的大小——页面的大小取决于内存分块的大下，块大则页面也大每个页面大了则程序的页面数就少。装入程序时是按页存放在内存中的，装入一页的信息量就大，就减少了缺页中断的次数，降低了缺页中断率。
     • 程序编制方法——程序编制的方法不同，对缺页中断的次数有很大影响。
     • 页面置换算法——页面置换算法对缺页中断率的影响也很大，调度不好就会出现“抖动”。理想的调度算法(OPT)能使缺页中断率最低。采用FIFO置换算法产生的缺页中断率约为最佳算法的三倍。

   (6) 虚拟存储管理的性能问题

   • 在虚存中，页面可能在内存与外存之间频繁地调度，有可能出现抖动或颠簸。
   • 系统用于调度页面所需要的时间比进程实际运行所占用的时间还多，系统效率会大幅下降。
   • 抖动或颠簸产生的原因
     • 进程在一段时间内集中访问一些页面（活动页面），分配给个进程的内存物理页面数太少，使得该进程所需要的“活动”页面不能全部装入内存，则进程在运行过程中可能会频繁地发生缺页中断，从而产生颠簸。
   • 采用工作集模型，可以解决颠簸问题。
   • 对于给定的进程访页序列，从时刻(t-Δ)到时刻t之间所访问页面的集合，称为该进程的工作集，Δ称为工作集窗口。
   • 工作集是随时间而变化的，工作集大小与窗口尺寸密切相关。
   • 工作集窗口可动态调整

3. 段式与段页式存储管理方案

   段式存储

   • 基本思想
     • 系统将内存空间动态划分为若千个长度不同的区域，物理段在内存中的起始地址，称作段首址。将物理段中的所有单元从0开始依次编址，称为段内地址
     • 用户程序则按逻辑上有完整意义的段来划分，称为逻辑段（简称段） ，所有逻辑段从0开始编号，称为段号，逻辑段中的所有单元从0开始编址，称为段内地址，用户程序的逻辑地址由段号和段内地址两部分组成。
   • 实现
     • 内存分配时，系统以段为单位进行内存分配，为每一个逻辑段分配一个连续的内存区
     • 当把程序装入内存后，系统为每个用户程序建立一张段表，用于记录用户程序的逻辑段与内存物理段之间的对应关系
     • 段表包括逻辑段号、物理段起始地址（段首址）和物理段长度
     • 物理段的段内地址与逻辑段的段内地址相同