第3章 内存管理

覆盖和交换技术是在多道程序环境下用来扩充内存的两种方法。

连续分配方式指为一个用户程序分配一个连续的内存空间。连续分配方式主要包括单一连续分配、固定区分配和动态区分配。

• 3.1.1 内存管理的基本原理和要求
  • 内存管理概念
    • 内存管理：操作系统对内存的划分和动态分配。
    • 为什么要进行内存管理：
    • 方便用户使用存储器
    • 提高内存利用率
    • 通过虚拟技术从逻辑上扩充存储器
    • 内存管理的功能：
    • 内存空间的分配和回收。由操作系统完成对主存储器空间的分配和管理，使程序员摆脱存储分配的麻烦，提高编程效率。
    • 地址转换。把逻辑地址转换成相应的物理地址。
    • 内存空间的扩充。利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存。
    • 存储保护。保证各道作业在各自的存储空间内运行，互不干扰。
  • 进程运行的基本原理和要求 在进行具体的内存管理之前，需要了解进程运行的基本原理和要求。

    

    

     

    重定位寄存器含最小的物理地址值。界地址寄存器含逻辑地址的最大值。每个逻辑地址值必须小于地址寄存器。​

    • 1. 程序装入和链接
    • 将用户程序变为可在内存中执行的程序的步骤：
    • 编译。由编译程序将用户源代码编译成若干目标模块。
    • 链接。由链接程序将编译后形成的一组目标模块及所需的库函数链接在一起，形成一个完整的装入模块。
    • 装入。由装入程序将装入模块装入内存运行。
    • 程序的链接有以下三种方式：
    • 静态链接。
    • 装入时动态链接。
    • 运行时动态链接。
    • 内存的装入模块在装入内存时也有三种方式：
    • （1）绝对装入。
    • （2）可重定位装入（静态重定位）。
    • （3）动态运行时装入（动态重定位）。
    • 2. 逻辑地址空间和物理地址空间
    • 相对地址（逻辑地址）：编译后，每个目标模块都是从0号单元开始编址，这称为目标模块的相对地址。
    • 逻辑地址空间：当链接程序把各个目标模块链接成一个完整的可执行目标程序时，链接程序顺序依次按各个模块相对地址构成统一的从0号单元开始编址的逻辑地址空间。 用户程序和程序员只需知道逻辑地址，只有系统编程人员才涉及内存管理的具体机制。不同进程可以由相同的逻辑地址，因为会映射到主存的不同位置。​
    • 物理地址空间：是指内存中物理单元的集合，它是地址转换的最终地址。
    • 地址重定位：当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换成物理地址，这个过程就叫地址重定位。
    • 3. 内存保护
    • 内存保护是什么：在内存分配前，需要保护操作系统不受用户进程的影响，同事保护用户进程不受其他用户进程的影响。
    • 内存保护可采用的两种方法：
    • （1）在CPU中设置一对上、下限寄存器，存放用户作业在主存中的下限和上限地址，每当CPU要访问一个地址时，分别和两个寄存器的值相比，判断有无越界。
    • （2）采用重定位寄存器（或基址寄存器）和界地址寄存器（又称限长寄存器）来实习这种保护。内存管理结构动态地将逻辑地址与界地址寄存器进行比较，若未发生地址越界，则加上重定位寄存器的值后映射成物理地址，再送交给内存单元。
    • 注意重定位寄存器和界地址寄存器的区别：
    • 重定位寄存器是用来“加”的，逻辑地址加上重定位寄存器中的值就能得到物理地址；
    • 界地址寄存器是用来“比”的，通过比较界地址寄存器中的值与逻辑地址的值判断是否越界。
• 3.1.2 覆盖与交换
• 1. 覆盖
• 2. 交换
• 3.1.3 连续分配管理方式
• 1. 单一连续分配
• 2. 固定区分配

  

  

   

  

  • 固定分区分配在划分分区时有两种不同的方法：
  • 分区大小相等。用于利用一台计算机去控制多个相同对象的场合，缺乏灵活性。
  • 分区大小不等。划分多个较小的分区、适量的中等分区和少量大分区。
  • 分区说明表：
  • 引入目的：为了便于内存分配，通常将分区按大小排队，并为之建立一张分区说明表。
  • 表项：包括每个分区的始址、大小及状态（是否已分配）。
  • 应用：当有用户程序要装入时，便检索该表，以找到合适的分区给予分配并将其状态置为“已分配”；未找到合适分区时，则拒绝为该程序分配内存。
  • 这种分区方式存在的两个问题：
  • 一是程序可能太大不能放入任何一个分区，用户不得不采用覆盖技术来使用内存空间；
  • 二是主存利用率低，当程序小于固定分区大小时，用不完一个完整的内存分区空间，这样造成的分区内部空间浪费，也就是内部碎片。
• 3. 动态分区分配

  

  • 动态分区的分配策略算法：
  • 各算法比较：
  • 在内存空间利用上：首次适应算法 > 最佳适应算法 > 最大适应算法。
  • 算法实现上：最佳适应算法和最大适应算法都需要对可用块进行排序或遍历查找，而首次适应算法和邻近适应算法只需要简单查找。
  • 在回收上：当回收的块与原来的空闲块相邻时需要进行合并。
• 3.1.4 非连续分配管理方式 非连续分配方式是指允许一个程序分散地装入不相邻的内存分区中。

  

  非连续分配方式根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。在分页存储管理方式中，根据允许作业时是否要把作业的所有页面都调入内存才能运行分为基本分页存储管理方式和请求分页存储管理方式。​​

  • 0. 分类
  • 1. 基本分页存储管理方式

    

    

    

    配置页表后，进程执行时，通过查找该表，即可找到每页在内存中的物理块号。

     系统中设置的页表寄存器（PTR），存放页表在内存的起始地址F和页表长度M。进程未执行时页表的始址和长度存放在进程控制块（PCB）中；进程执行时，才放入页表寄存器（PTR）中。整个地址变换过程由硬件自动完成。​​页式管理中地址空间是一维的。

    

    • （0）前言
    • 引入分页的目的：为了尽量避免碎片的产生。（固定分区会产生内部碎片、动态分区会产生外部碎片） 采用分页管理后不会产生外部碎片，每个进程平均只产生半个块大小的内部碎片（也称业内碎片）。
    • 分页的思想：把内存空间划分为大小相等且固定的块，块相对较小，作为内存的基本单位。每个进程也以块为单位进行划分，进程在执行时，也以块为单位申请内存中的块空间。
    • （1）分页存储的几个基本概念
    • ①页面和页面大小
    • 页（Page）：进程中的块称为页。
    • 页框（Page Frame）：内存中的块称为页框。 进程执行时申请内存空间，即页面分配可用页框，页和页框一一对应。
    • 块（Block）：外存也以同样的单位划分，直接称为块。
    • 页面大小：为了方便地址转换，页面大小应是2的整数幂。页面大小要适中。
    • 页面太小：造成进程的页面数过多，这样页表就会过长，占用大量内存；而且会增加硬件地址转换的开销，降低页面换入/换出的效率。
    • 页面过大：使业内碎片增多，降低内存的利用率。
    • ②地址结构 注意：地址结构决定了虚拟内存的寻址空间有多大。
    • 分页存储管理的逻辑地址结构
    • ③页表
    • 页表的组成：页表项。页表项的组成如下：
    • 页表项的作用：找到该页在内存中的位置。
    • 页表项与地址结构的区别：
    • 都由两部分组成；
    • 第一部分都是页号；
    • 页表项的第二部分是物理内存中的块号，地址结构中的第二部分是业内偏移；
    • 页表项的第二部分与地址的第二部分共同组成物理地址。
    • 页表的作用：实现从页号到物理块号的地址映射，页表一般存放在内存中。
    • （2）基本地址变换机构
    • 地址变换机构的作用：将逻辑地址转换为内存中的物理地址。地址变换借助于页表实现。
    • 设页面大小为L，逻辑地址A到物理地址E的变换过程如下（逻辑地址、叶红、每页的长度都是十进制数）：
    • ①计算页号P（P=A/L，如5/2=2）和页内偏移量W（W=A%L，如5%2=1）。
    • ②比较页号P和页表长度M，若P>=M，则产生越界中断，否则继续执行。
    • ③页表中页号P对应的页表项地址 = 页表始址F + 页号P x 页表项长度，取出该页表项内容b，即为物理块号。 区分页表长度和页表项长度：页表长度指一共有多少页；页表项长度指页地址占多大的存储空间。
    • ④计算逻辑地址E = b x L + W，用得到的物理地址E去访问内存。
    • ⑤例题：若页面大小L为1KB，页号2对应的物理块为b=8，计算逻辑地址A=2500的物理地址E的过程如下： 页号P=A/L=2500/1KB=2500/1024=2；页内偏移量W=A%L=2500%1KB=2500%1024=452；逻辑地址E=b x L + W=8*1KB+452=8*1024+452=8644。​​
    • 分页管理方式存在的两个主要问题：
    • ①每次访存操作都需要进行逻辑地址到物理地址的转换，地址转换过程必须足够快，否则访存速度会降低。
    • ②每个进程引入页表，用于存储映射机制，页表不能太大，否则内存的利用率会降低。
    • （3）具有快表的地址变换机构
    • 单纯的地址变换机构存在的问题：若页表全部放在内存中，则存取一个数据或一条指令需要至少两次访问内存，第一次是访问页表确定所取数据或指令的物理地址，第二次是根据该地址存取数据或指令。这种方法比通常执行指令速度慢了一半。解决方法是引入快表。
    • 快表（又称相联存储器(TLB)）：一个具有并行查找能力的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，主存中的页表称为慢表。 快表的有效性基于著名的局部性原理。
    • 具有快表的地址变换结构，地址的变换过程如下：先去快表找，若找到则取出对应页号同业内偏移量拼接形成物理地址，这样存取数据近一次访存就能实现；若未找到则访问主存中的页表，在读出页表后，同时将其存入快表以便以后可能的再次访问。若快表已满，按一定算法对旧的页表项进行替换。
    • （4）两级页表
    • 两次页表逻辑地址空间的格式
    • 二级页表结构示意图
    • 建立多级页表的目的：在于建立索引，以便不用浪费主存空间去存储无用的页表项，也不能盲目地顺序式查找页表项。
  • 2. 基本分段存储管理方式

    

    页式系统中，逻辑地址的页号和页内偏移量对用户是透明的。段式系统中，逻辑地址的段号和段内偏移量必须由用户显式提供，在高级程序设计语言中，这个工作由编译程序完成。​

    

    每个进程都有一张段表，其中每个段表项对应进程的一段，段表项记录该段在内存中的始址和长度。

    • （0）前言
    • 分页管理方式的目的：提供内存的利用率，提升计算机的性能，分页通过硬件机制实现，对用户完全透明。
    • 分段管理方式的目的：考虑了用户和程序员，以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要。
    • （1）分段
    • 分段：按照用户进程中的自然段划分逻辑空间。 例如，用户进程由主程序、两个子程序、栈和一段数据组成，则可用划分为5段，每段从0开始编址，并分配一段连续的地址空间。（要求段内连续，段间不要求连续，整个作业空间是二维的）
    • 分段系统中的逻辑地址结构
    • （2）段表
    • 段表的组成：段表项。段表的内容如下：
    • 段表的作用：用于实现从逻辑段到物理内存区的映射。
    • （3）地址变换机构
    • 地址变换机构的作用：实现进程从逻辑地址到物理地址的变换功能。 系统中设置的段表寄存器，用于存放段表始址F和段表长度M。
    • 从逻辑地址A到物理地址E之间的地址变换过程如下：
    • ①从逻辑地址A中取出前几位为段号S，后几位为段内偏移量W。 注意，段式存储管理的题目中，逻辑地址以二进制给出；页式存储管理的题目中，逻辑地址以十进制给出。但具体问题具体分析。
    • ②比较段号S和段表长度M，若S>=M，则产生越界中断，否则继续执行。
    • ③段表中段号S对应的段表项地址=段表始址F + 段号S x 段表项长度。取出该段表项的前几位得到段长C。若段内偏移量>=C，则产生越界中断，否则继续执行。 段表项实际只有两部分，前几位是段长，后几位是始址。
    • ④取出段表项中该段的始址b，计算物理地址E=b+W，用得到的物理地址E去访问内存。
    • （4）段的共享与保护
    • 段的共享：在段式系统中，通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的。 注意：当一个作业正在从共享段读取数据时，必须防止另一个作业修改此共享段中的数据。不能修改的代码称为纯代码或可重入代码（它不属于临界资源），这样的代码和不能修改的数据可以共享，可修改的代码和数据不能共享。
    • 段的保护： 注意：页式管理可以根据给出的一个整数确定对应的物理地址，但段式管理不能，因为段的长度不固定，页面大小是固定的，所以必须给出段号和段内偏移，因此段式管理的地址空间是二维的。
    • 一种是存取控制保护；
    • 另一种是地址越界保护。 地址越界保护将段表寄存器中的段表长度与逻辑地址中的段号进行比较，若段号大于段表长度，则产生越界中断；再将段表项的段长和逻辑地址中的段内偏移进行比较，若段内偏移大于段长，页号产生越界中断。注意：分页管理中的地址越界保护只需要判断页号是否越界，页内偏移是不可能越界的。​
  • 3. 段页式管理方式

    段页式管理的地址空间是二维的。

    

    进行一次访问需要三次访问主存，可以使用快表技术加快查找速度，其关键字由段号、页号组成，值是对应的块号和保护码。

    • 引入：页式存储管理提供了内存利用率，段式存储管理反映程序的逻辑结构有利于段的共享，将这两种存储管理方法结合起来就是段页式存储管理方式。
    • 段页式管理：在段页式系统中，作业的地址空间被分成若干逻辑段，然后将每个段分成若干固定大小的页。对内存空间的管理仍然和页式管理一样。
    • 段页式系统的逻辑地址结构：
    • 段表与页表：为了实现地址变换，系统为每个进程建立一张段表，每个分段建立一张页表。（注意：在一个进程中，段表只有一个，而页表可能有多个） 段表寄存器和页表寄存器的作用都有两个：一个是在段表或页表寻址；而是判断是否越界。
    • 地址变换机构：进行地址变换时，首先通过段表查到页表始址，然后通过页表找到块号，最后形成物理地址。

• 3.2.1 虚拟内存的基本概念
  • 1. 传统存储管理方式的特征：一次性和驻留性。 由于作业一次性全部装入并且一直驻留在内存中不被换出，浪费了内存资源。
  • 2. 局部性原理
    • 应用：如快表、页高速缓存及虚拟内存技术（都属于高速缓存技术，这个技术依赖于局部性原理）。
    • 局部性原理表现的两个方面：
    • （1）时间局部性。某条指令或数据执行访问过，不久又会被再次执行访问。 时间局部性产生的原因是存在着大量循环操作。
    • （2）空间局部性。程序访问了某存储单元，那么不久后，其周围附件的也将被访问。
  • 3. 虚拟存储器的定义和特征
    • 虚拟存储器原理：在程序装入时，只将一部分装入内存，其他部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时用不到的内容换出到外存上，从而腾出空间放将要调入内存的信息。 简而言之：程序不一次性全调入内存，在需要的时候再调入内存，并且将暂时用不到的内容换出到外存。
    • 虚拟存储器的特点
    • （1）多次性。指作业无须一次性全部装入内存，而是在需要时多次调入。
    • （2）对换性。指作业无须一直驻留在内存，允许在作业的运行过程中换进和换出。
    • （3）虚拟性。实际上并没有增加内存容量，只是从逻辑上扩充内存容量。
  • 4. 虚拟内存技术的实现 虚拟内存的实现如果采用连续分配的方式，会造成内存资源的浪费，也无法从逻辑上扩大内存容量。虚拟内存的实现需要采用离散分配的内存管理方式。​
    • 虚拟内存实现的三种方式：
    • 请求分页存储管理
    • 请求分段存储管理
    • 请求段页式存储管理
    • 无论哪种方式，都需要一定硬件支持，一般需要以下支持：
    • 一定容量的内存和外存。
    • 页表机制（或段表机制），作为主要的数据结构。
    • 中断机构，当缺页（即程序要访问的部分不在内存时），则产生中断。
    • 地址变换机构，逻辑地址变换为物理地址。
• 3.2.2 请求分页管理方式
  • 0. 请求分析管理方式：在请求分页系统中，只要求将当前需要的一部分页面装入内存，便快要启动作业。在作业执行过程中，当所要访问的页面不在内存中时，通过调页功能调入，同时考可以通过置换功能将暂时不用的页面换出到外存上。 为了实现请求分页，需要硬件支持：一定容量的内存及外存的计算机系统、页表机制、缺页中断机构和地址变换机构。
  • 1. 页表机制

    

    • 请求分页系统中的页表项及参数说明：
    • 页号：页表项的号。
    • 物理块号：物理内存中的块号。
    • 状态位P：用于指示该页是否已调入内存，供程序访问时参考。
    • 访问字段A：用于记录本页在一段时间内被访问的次数或记录本页有多长时间未被访问，供置换算法换出页面时参考。
    • 修改位M：标识该页在调入内存后是否被修改过。
    • 外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入参考。
  • 2. 缺页中断机构
    • 每当所要访问的页面不在内存中时，便产生一个缺页中断。
    • 缺页中断与一般中断的相比，有两个明显区别：
    • （1）在指令执行期间产生和处理中断信号，属于内部中断。
    • （2）一条指令执行期间，可能产生多次缺页中断。
  • 3. 地址变换机构
    • 在进行地址变换时，先检索快表：
    • 若找到要访问的页，则修改页表项中的访问位（写指令还需要重置修改位，表示该页被修改过），然后利用页表项中给出的物理块号和业内地址形成物理地址。
    • 若未找到该页的页表项，则应到内存中去查找页表项，再对比页表项中的状态位P，看是否已经调入内存，未调入则产生缺页中断，请求从外存把该页调入内存。
• 3.2.3 页面置换算法（决定应该换入哪页、换出哪页）
  • 0. 前言
    • 为什么需要页面置换算法：进程运行时，若其访问的页面不在内存中需要将其调入，但内存无空闲空间，那么需要考虑从内存中调出一页数据或程序，然后腾出空间来调入需要的页。
    • 页面置换算法的定义：选择调出页面的算法就叫页面置换算法。
    • 页面置换算法的目标：将以后不会再访问或以后较长时间内不会再访问的页面先调出。
  • 1. 最佳（OPT）置换算法

    

    • 图表演示及注释说明
    • ①内存中不存在页号为7的页面，因此缺页，直接调入。
    • ②内存中不存在页号为0的页面，因此缺页，直接调入。
    • ③内存中不存在页号为1的页面，因此缺页，直接调入。此时三个物理块填满，接下来就可能进行页面置换了。
    • ④内存中不存在页号为2的页面，因此缺页，不能直接调入，因为三个物理块已满，需要进行置换，OPT置换算法是置换最长时间内不再被访问的页面，从此处往后数，发现页号为7最长时间内不会被访问，因此将物理块1中的7换出，然后调入2。
    • ⑤内存中存在页号为0的页面，不缺页，不需要调入也不需要置换。
    • ⑥内存中不存在页号为3的页面，因此缺页，不能直接调入，因为三个物理块已满，需要进行置换，OPT置换算法是置换最长时间内不再被访问的页面，从此处往后数，发现页号为1最长时间内不会被访问，因此将物理块3中的1换出，然后调入3。
    • ⑦内存中存在页号为0的页面，不缺页，不需要调入也不需要置换。
  • 2. 先进先出（FIFO）页面置换算法

    

    • 图表演示及注释说明
    • ①中有四个数分别为7、0、1、2，其中前三个为物理块中填满的，而红色的2是进行置换的，那么根据FIFO算法置换最先进入的，观察四个数，最先进入的是7，那么把物理块1中的7换成2。后面也是这样来的，通过上面的队列方便观察该置换哪个数出去。
    • ②中有四个数分别为0、1、2、3，其中有个空格是表示物理块中已有此页，而红色的3是进行置换的，那么根据FIFO算法，观察四个数，最先进入的是0，因为7已经被置换掉了，所以是0，将0换成3。注意所有的都是4个数，这是由物理块的个数加一个待置换的页决定的。
  • 3. 最近最久未使用（LRU）置换算法

    

    • 图表演示及注释说明
  • 4. 时钟（CLOCK）置换算法 暂无处理
    • CLOCK算法和改进型CLOCK算法
    • 在使用位（访问位）上再添加一个修改位，得到改进型CLOCK置换算法，使每页都处于以下四种情况：
    • （1）最近未被访问，也未被修改（u=0,m=0）。
    • （2）最近被访问，但未被修改（u=1,m=0）。
    • （3）最近未被访问，但被修改（u=0,m=1）。
    • （4）最近被访问，被修改（u=1,m=1）。
    • 改进型CLOCK算法优于简单CLOCK算法的地方在于替换时首选没有变化的页。
    • CLOCK算法只考虑到是否被访问过，因此被访问过的当然尽可能留下，未使用过的就淘汰；而改进型CLOCK算法对使用过的页面又做了细分，分为使用过但未修改过和使用过且修改过，对于有未使用过的页面，则当然首先把它换出，若全面页面都使用过，则当然优先把未修改过的页面换出。
  • 5. 几种页面置换算法的比较

    

    • 图表比较
• 3.2.4 页面分配策略
  • 1. 驻留集大小

    

    • 驻留集：给一个进程分配的物理页框的集合就是这个进程的驻留集。 操作系统必须绝对读多少页（不可能把一个进程的所有页都读入注册），即决定给特定的进程分配几个页框。
    • 采用三种策略：
    • （1）固定分配局部置换。
    • （2）可变分配全局置换。
    • （3）可变分配局部置换。
    • 三种策略的总结比较
  • 2. 调入页面的时机

    

    • 为确定系统将进程运行时所缺的页面调入内存的时机，有以下两种调页策略：
    • （1）预调页策略。
    • （2）请求调页策略。
    • 两种调页策略的比较
  • 3. 从何处调入页面
    • 请求分页系统中的外存分为两部分：
    • 用于存放文件的文件区，采用离散分配方式。
    • 用于存放对换页面的对换区，采用连续分配方式，磁盘I/O速度比文件区快。
    • 从何处调入页面存在三种情况：
    • 1)系统拥有足够的对换区空间。可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前，需将与该进程有关的文件从文件区复制到对换区。
    • 2)系统缺少足够的对换区空间。凡不会被修改的文件都直接从文件区调入:而当换出这些页面时，由于它们未被修改而不必再将它们换出。但对于那些可能被修改的部分，在将它们换出时须调到对换区，以后需要时再从对换区调入(因为读的速度比写的速度快)。
    • 3) UNIX方式。与进程有关的文件都放在文件区，因此未运行过的页面都应从文件区调入。曾经运行过但又被换出的页面，由于放在对换区，因此下次调入时应从对换区调入。进程请求的共享页面若被其他进程调入内存，则无须再从对换区调入。
• 3.2.5 抖动
  • 抖动（颠簸）：即在页面置换过程中，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上又要换出主存，这种频繁的调度行为称为抖动。
  • 频繁发生抖动的原因：某个进程频繁访问的页面数目高于可用的物理页帧数。
• 3.2.6 工作集

  

  注意：去掉重复项。

  • 工作集：指某段时间间隔内，进程要访问的页面集合。
  • 计算工作集
  • 工作集的特点
    • 基于局部性原理，可用用最近访问过的页面来确定工作集。
    • 工作集可由时间t和工作集窗口大小来确定。
    • 工作集反映了进程在接下来一段时间内可能会频繁访问的页面集合。
    • 若分配的物理块小于工作集大小，进程就可能频繁缺页。
    • 为了防止抖动现象，一般来说分配给进程的物理块数（即驻留集大小）要大于工作集大小。
• 3.2.7 地址翻译 暂无处理
  • TLB——页表（TLB不命中）——cache——主存（cache不命中）——外存（缺页）。