操作系统 | 学习笔记 | 王道 | 3.1 内存管理概念

3 内存管理

3.1 内存管理概念

3.1.1 内存管理的基本原理和要求

内存可以存放数据，程序执行前需要先放到内存中才能被CPU处理—缓和cpu和磁盘之间的速度矛盾

1. 内存管理的概念

   虽然计算机技术飞速发展，内存容量也在不断扩大，但仍然不可能将所有用户进程和系统所需的全部程序与数据放入内存，因此操作系统对内存空间进行合理的划分和有效的动态分配。操作系统对内存的划分和动态分配，就是内存管理的概念。

   内存空间的主要功能有：

   • ① 内存空间的分配与回收：OS 要怎么记录哪些内存区域已经被分配出去了，哪些又还空闲；当进程运行结束之后，如何将进程占用的内存空间回收。
   • ② 内存空间的扩充：OS 利用虚拟内存技术或自动覆盖技术使得系统运行很大的程序，从逻辑上扩充内存。
   • ③ 地址转换：为了使编程更方便，程序员写程序时应该只需要关注指令、数据的逻辑地址。而 逻辑地址到物理地址的转换（这个过程称为地址重定位）应该由操作系统负责，其中地址重定位有三种方式。
   • ④ 内存保护：保证各进程在各自存储空间内运行，互不干扰。

2. 程序执行过程

   创建进程首先要将程序和数据装入内存。将用户源程序变为可在内存中执行的程序，通常需要以下几个步骤：

   • 编译：由编译程序将用户源代码编译成若干目标模块，编译就是把高级语言翻译为机器语言。
   • 链接：由链接程序将编译后形成的一组目标模块及它们所需的库函数链接在一起，形成一个完整的装入模块。
   • 装入：由装入程序将装入模块装入内存运行。

   

   编译后，每个目标模块都是从 0 号单元开始编址，这称为该目标模块的 逻辑地址 (或相对地址)。当链接程序将各个模块连接成一个完整的可执行目标程序时，链接程序顺序依次按各个模块的相对地址构成统一的从 0 号单元开始编制的 逻辑地址空间。用户程序和程序员只需知道逻辑地址，而内存管理的具体机制则是完全透明的，只有系统编程人员才会涉及内存管理的具体机制。不同进程可以有相同的逻辑地址，因为这些相同的逻辑地址可以映射到内存的不同位置。
     物理地址空间 是指内存中物理单元的集合，它是地址转换的最终地址。进程在运行时执行指令和访问数据，最后都要通过物理地址从主存中存取。当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换成物理地址(动态重定位是地址转换推迟到程序真正要执行时才进行)，这个过程称为 地址重定位。

3. 程序的链接

   • 静态链接

     在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件(装入模块)，之后不再拆开。

     

   • 装入时动态链接

     将各 目标模块装入内存时，边装入边链接的链接方式。

     

   • 运行时动态链接

     在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享。

     

4. 程序的装入

   • 绝对装入

     在编译与链接后，得到的装入模块指定 直接使用了绝对地址。

     

   • 可重定位装入

     

   • 动态运行时装入

     装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址(装入时依然保持使用逻辑地址)，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持。

     

     动态重定位特点： 可以将程序分配到不连续的存储区中；在程序运行前只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存；便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间；采用动态重定位时允许程序在内存中发生移动。

   注：链接的作用是形成了完整的装入模块与逻辑地址，但逻辑地址到物理地址的转换过程是重定位，而不是装入。

   注：重定位寄存器也称基址寄存器、界地址寄存器也称为限长寄存器。

5. 内存映像

   不同于存放在硬盘上的可执行程序文件，当一个程序调入内存运行时，就构成了进程的内存映像。一个进程的内存映像一般有几个要素：

   • 代码段：即程序的二进制代码，代码段是只读的，可以被多个进程共享。
   • 数据段：即程序运行时加工处理的对象，包括全局变量和静态变量。
   • 进程控制块（PCB）：存放在系统区。操作系统通过PCB来控制和管理进程。
   • 堆：用来存放动态分配的变量。通过调用malloc 函数动态地向高地址分配空间。
   • 栈：用来实现函数调用。从用户空间的最大地址往低地址方向增长。

   代码段和数据段在程序调入内存时就指定了大小，而堆和栈不一样。

   当调用像malloc和free这样的C标准库函数时，堆可以在运行时动态地扩展和收缩。

   用户栈在程序运行期间也可以动态地扩展和收缩，每次调用一个函数，栈就会增长；从一个函数返回时，栈就会收缩。

   

   上图是一个进程在内存中的映像。

   • 其中，共享库用来存放进程用到的共享函数库代码，如printf函数等。
   • 在只读代码段中，.iit是程序初始化时调用的_init函数；.text是用户程序的机器代码；.rodata是只读数据。
   • 在读/写数据段中，.data是已初始化的全局变量和静态变量；.bss是未初始化及所有初始化为0的全局变量和静态变量。

6. 内存保护

   确保每个进程都有一个单独的内存空间。内存分配前，需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响。内存保护可采取两种方法：

   • 在CPU中设置一对上、下限寄存器，存放用户作业在主存中的下限和上限地址，每当CPU要访问一个地址时，分别和两个寄存器的值相比，判断有无越界。

   • 采用重定位寄存器（又称基地址寄存器）和界地址寄存器（又称限长寄存器）来实现这种保护。

     重定位寄存器含最小的物理地址值，界地址寄存器含逻辑地址的最大值。内存管理机构动态地将逻辑地址与界地址寄存器进行比较，若未发生地址越界，则加上重定位寄存器的值后映射成物理地址，再送交内存单元，如下图所示。

     

     重定位寄存器是用来“加”的，逻辑地址加上重定位寄存器中的值就能得到物理地址；

     界地址寄存器是用来“比”的，通过比较界地址寄存器中的值与逻辑地址的值来判断是否越界。

     加载重定位寄存器和界地址寄存器时必须使用特权指令，只有操作系统内核才可以加载这
     两个存储器。这种方案允许操作系统内核修改这两个寄存器的值，而不允许用户程序修改。

7. 内存共享

   并不是所有的进程内存空间都适合共享，只有那些只读的区域才可以共享。

   可重入代码又称纯代码，是一种允许多个进程同时访问但不允许被任何进程修改的代码。

   在实际运行时，每个进程有自己的私有数据段，可以更改自己私有的数据区数据，不可改变共享的代码。

   例：考虑一个可以同时容纳40个用户的多用户系统，他们同时执行一个文本编辑程序，若该程序有160KB代码区和40KB数据区，则共需8000KB的内存空间来支持40个用户。如果160KB代码是可分享的纯代码，则不论是在分页系统中还是在分段系统中，整个系统只需保留一份副本即可，此时所需的内存空间仅为40KB×40+160KB=1760KB。

   对于分页系统，假设页面大小为4KB，则代码区占用40个页面、数据区占用10个页面。为实现代码共享，应在每个进程的页表中都建立40个页表项，它们都指向共享代码区的物理页号。此外，每个进程还要为自己的数据区建立10个页表项，指向私有数据区的物理页号。

   对于分段系统，由于是以段为分配单位的，不管该段有多大，都只需为该段设置一个段表项（指向共享代码段始址，以及段长160KB）。由此可见，段的共享非常简单易行。

8. 内存分配与回收

   在操作系统由单道向多道发展时，存储管理方式便由单一连续分配发展为固定分区分配。为了能更好地适应不同大小的程序要求，又从固定分区分配发展到动态分区分配。

   为了更好地提高内存的利用率，进而从连续分配方式发展到离散分配方式一一页式存储管理。

   引入分段存储管理的目的，主要是为了满足用户在编程和使用方面的要求，其中某些要求是其他几种存储管理方式难以满足的。

3.1.2 覆盖与交换

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

1. 覆盖

   • 基本思想：由于程序运行时并非任何时候都要访问程序及数据的各个部分（尤其是大程序），因此可把用户空间分成一个固定区和若干覆盖区

     • 将经常活跃的部分放在固定区，其余部分按调用关系分段。
     • 首先将那些即将要访问的段放入覆盖区，其他段放在外存中，在需要调用前，系统再将其调入覆盖区，替换覆盖区中原有的段。

   • 特点：

     • 打破了必须将一个进程的全部信息装入主存后才能运行的限制，但当同时运行程序的代码量大于主存时仍不能运行；
     • 内存中能够更新的地方只有覆盖区的段，不在覆盖区中的段会常驻内存；
     • 覆盖技术对用户和程序员不透明。

2. 交换

   • 基本思想：把处于等待状态（或在CPU调度原则下被剥夺运行权利）的程序从内存移到辅存，把内存空间腾出来，这一过程又称换出；把准备好竞争CPU运行的程序从辅存移到内存，这一过程又称换入。
   • 交换过程：例如，有一个CPU采用时间片轮转调度算法的多道程序环境。时间片到，内存管理器将刚刚执行过的进程换出，将另一进程换入刚刚释放的内存空间。同时，CPU调度器可以将时间片分配给其他已在内存中的进程。每个进程用完时间片都与另一进程交换。在理想情况下，内存管理器的交换过程速度足够快，总有进程在内存中可以执行。
   • 问题：
     • 交换需要备份存储，通常是磁盘。它必须足够大，并提供对这些内存映像的直接访问。
     • 为了有效使用CPU，需要使每个进程的执行时间比交换时间长。
     • 若换出进程，则必须确保该进程完全处于空闲状态。
     • 交换空间通常作为磁盘的一整块，且独立于文件系统，因此使用起来可能很快。
     • 交换通常在有许多进程运行且内存空间吃紧时开始启动，而在系统负荷降低时就暂停。
     • 普通的交换使用不多，但交换策略的某些变体在许多系统（如UNX）中仍发挥作用。

3. 区别

   交换技术主要在不同进程（或作业）之间进行，而覆盖则用于同一个程序或进程中。对于主存无法存放用户程序的矛盾，现代操作系统是通过虚拟内存技术来解决的，覆盖技术则已成为历史；而交换技术在现代操作系统中仍具有较强的生命力。

3.1.3 连续分配管理方式

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

1. 单一连续分配

   在单一连续分配方式中，内存被分为 系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间。

   

   优点： 实现简单；无外部碎片；可以采用覆盖技术扩充内存；无需采取内存保护，因为内存中永远只有一道程序。

   **缺点：**只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低。

   内部碎片：分配给某进程的内存区域中，如果有些部分没有用上。

   外部碎片：是指内存中的某些空闲分区由于太小而难以利用。

2. 固定分区分配

   固定分区分配是最简单的一种多道程序存储管理方式，它将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业。当有空闲分区时，便可从外存的后备作业队列中选择适当大小的作业装入该分区，如此循环。划分分区有两种方法：

   • 分区大小相等。程序太小会造成浪费，程序太大又无法装入，缺乏灵活性。
   • 分区大小不等。划分为多个较小的分区、适量的中等分区和少量大分区，增加了灵活性。

   

   为了便于分配，建立一张分区使用表，通常按分区大小排队，各表项包括每个分区的起始地址、大小及状态（是否已分配），如下图所示。

   

   分配内存时，便检索该表，以找到一个能满足要求且尚未分配的分区分配给装入程序，并将对应表项的状态置为“已分配”；若找不到这样的分区，则拒绝分配。

   回收内存时，只需将对应表项的状态置为“未分配”即可。

   优点： 实现简单，无外部碎片。

   缺点： 当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能；会产生内部碎片，内存利用率低。

3. 动态分区分配

   动态分区分配 又称为 可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此，系统分区的大小和数目是可变的。

   没有内部碎片，有外部碎片

   例：如图所示，系统有64MB内存空间，其中低8MB固定分配给操作系统，其余为用户可用内存。

   开始时装入前三个进程，它们分别分配到所需的空间后，内存仅剩4MB，进程4无法装入。

   在某个时刻，内存中没有一个就绪进程，CPU出现空闲，操作系统就换出进程2，换入进程4。由于进程4比进程2小，这样在主存中就产生了一个6MB的内存块。

   之后CPU又出现空闲，需要换入进程2，而主存无法容纳进程2，操作系统就换出进程1，换入进程2。

   

   紧凑技术：动态分区在开始时是很好的，但随着时间的推移，内存中会产生越来越多的外部碎片。需要通过紧凑技术来解决，即操作系统不时地对进程进行移动和整理。但这需要动态重定位寄存器的支持，且相对费时。

   1. 系统要用什么样的数据结构记录内存的使用情况？

      

   2. 当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？

      

   3. 如何进行分区的分配与回收操作？

      将相邻的空闲空间合并。

   在进程装入或换入主存时，若内存中有多个足够大的空闲块，则操作系统必须确定分配哪个内存块给进程使用，这就是动态分区的分配策略。考虑以下几种算法：

   • 首次适应（FirstFit）算法

     • 算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
     • 如何实现：空闲分区以地址递增的次序链接。分配内存时，从链首开始顺序查找，找到大小能满足要求的第一个空闲分区分配给作业。
     • 算法简单，最好最快，回收分区后一般不需要对空闲分区队列重新排序

   • 最佳适应（BestFit）算法

     • **算法思想：**优先使用更小的分区，以保留更多大分区。
     • **如何实现：**空闲分区按容量递增的次序形成空闲分区链，找到第一个能满足要求且最小的空闲分区分配给作业，避免“大材小用”。
     • **缺点：**产生大量小的、难以利用的外部碎片

   • 最坏适应（WorstFit）算法

     （最大适应算法）

     • **算法思想：**优先使用更大的分区，以防止产生太小的不可用的碎片。
     • **如何实现：**空闲分区以容量递减的次序链接，找到第一个能满足要求的，即最大的分区，从中分割一部分存储空间给作业。
     • **缺点：**如果之后有“大进程”到达，无足够大连续内存空间分配。

   • 邻近适应（NextFit）算法

     （循环首次适应算法）

     • **算法思想：**由首次适应演变而来，每次从上次查找结束位置开始查找。
     • **如何实现：**空闲分区以地址递增的顺序排列（可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
     • **缺点：**导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用，划分为小分区，最后导致无大分区可用。

   算法	算法思想	分区排列顺序	优点	缺点
   首次适应	从头到尾找适合的分区	空闲分区以地址递增次序排列	性能最好 算法开销小
   最佳适应	优先使用更小的分区	空闲分区以容量递增次序排列	保留更大分区	产生大量碎小的外部碎片；算法开销大
   最坏适应	优先使用更大的分区	空闲分区以容量递减次序排列	减少难以利用的碎片	大分区容易被用完；算法开销大
   邻近适应	每次从上次查找结束位置开始查找	空闲分区以地址递增次序排列（可排列成循环链表)	空闲分区有相同概率被使用，算法开销小	使高地址大分区也被用完

   注：动态分区分配没有内部碎片，但是有外部碎片。

4. 分区的分配与回收

   回收内存分区时，有可能遇到四种情况：

   • ① 回收区的后面有一个相邻的空闲分区。
   • ② 回收区的前面有一个相邻的空闲分区。
   • ③ 回收区的前、后各有一个相邻的空闲分区。
   • ④ 回收区的前、后都没有相邻的空闲分区。

   无论那种情况，都要遵循相邻的空闲分区要合并的原则。

3.1.4 基本分页存储管理

固定分区会产生内部碎片，动态分区会产生外部碎片，这两种技术对内存的利用率都比较低。为了避免碎片的产出，引出了分页的思想。
​ 分页的思想：把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。

分页管理与固定分区类似，不会产生外部碎片；进程运行按块申请主存空间，只会在最后一块有内部碎片，每个进程平均只有半个块的内部碎片（页内碎片）。

1. 基本概念

   • 页面和页面大小

     • 进程中的块称为页或页面（Page)，
     • 内存中的块称为页框或页帧（Page Frame)
     • 外存也以同样的单位进行划分，直接称为块或盘块（Block)。

     进程在执行时需要为每个页面分配主存中的可用页框，这就产生了页和页框的一一对应。

     

     • 将内存空间分为一个个大小相等的分区，每个分区就是一个页框 。每个页框有一个编号，即 页框号，页框号 从 0 开始。
     • 将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个 页或页面。每个页面也有一个编号，即 页号，页号也是 从 0 开始。

     页框=页帧=内存块=物理块=物理页面

     为方便地址转换，页面大小应是2的整数幂。同时页面大小应该适中，

     • 页面太小会使进程的页面数过多，这样页表就会过长，占用大量内存，而且也会增加硬件地址转换的开销，降低页面换入/换出的效率；
     • 页面过大又会使页内碎片增多，降低内存的利用率。

   • 地址结构

     地址结构决定了虚拟内存的寻址空间有多大。

     分页存储管理的 逻辑地址结构 如下所示：

     

     地址结构包含两个部分：前一部分为页号，后一部分为页内偏移量 W。

     在上图所示的例子中，地址长度为 32 位，其中 0 ~ 11位 为页内偏移量(或称页内地址)，即每页大小为 4KB；12~31 位为页号，进程地址空间最多允许 220 页。

   • 页表

     为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张 页表。页表通常存在 PCB (进程控制块，在操作系统的内核地址空间)中。页表记录进程 页面 和实际存放的 内存块 之间的 映射关系。

     

     • ①一个进程对应一张页表。
     • ②进程的每个页面对应一个页表项。
     • ③每个页表项由页号和块号组成。
     • ④每个页表项的长度是相同的。

     例：假设某系统物理内存大小为 4 GB，页面大小为 4 KB，则每个页表项至少应该为多少字节？

     • 内存块大小=页面大小=4KB=212B
     • 4GB的内存总共会被分为232／212=220个内存块
     • 内存块号的范围应该是0～220-1
     • 内存块号至少要用20 bit来表示
     • 至少要用3B来表示块号（3＊8=24 bit＞20bit）

     页表项在内存中是连续存放，因此页号是可以隐藏的，不占内存空间，页表项占 3 个字节。

     注：如果未特别强调，默认计算机按字节编址。

     注：页号是隐藏的

   • 地址转换

     分页存储特点： 虽然进程的各个页面是离散存放的，但是页面内部是连续存放的。

     

     页号 = 逻辑地址 / 页面长度
     页内偏移量 = 逻辑地址 % 页面长度

     如果要访问逻辑地址 A 的物理块，则

     • ① 确定逻辑地址 A 对应的页号 P
     • ② 找到 P 号页面在内存中的起始地址（需要查页表）
     • ③ 确定逻辑地址 A 的页内偏移量 W

   

2.基本地址变换机构

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。变换机构如下图所示。

通常会在系统中设置一个 页表寄存器(PTR)，存放 页表在内存中的起始地址 F 和页表长度 M。
进程未执行时，页表的始址 和 页表长度 放在进程控制块(PCB)中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

• 设页面大小为 L ，逻辑地址 A 到物理地址 E 的变换过程如下：

  

  

  • ①计算页号P和页内偏移量W

    如果用十进制数手算，则$P=A/L，W=A$；但是在计算机实际运行时，逻辑地址结构是固定不变的，因此计算机硬件可以更快地得到二进制表示的页号、页内偏移量

  • ②判断页号是否越界

    比较页号P和页表长度M，若P≥M，则产生越界中断，否则继续执行。

    注意：页号是从0开始的，而页表长度至少是1，因此P=M时也会越界

  • ③查页表，找页号对应的页表项，确定内存块号
    $$页表中页号P对应的页表项地址=页表起始地址F+页号P\ast 页表项长度$$
    取出该页表项内容b，即为内存块号。

    注意区分页表项长度、页表长度、页面大小的区别。

    页表长度指的是这个页表中总共有几个页表项，即总共有几个页；

    页表项长度指的是每个页表项占多大的存储空间；

    页面大小指的是一个页面占多大的存储空间

  • ④用内存块号和偏移量得到物理地址

    计算$E=b\ast L+W$，用得到的物理地址E去访存。

    如果内存块号、页面偏移量是用二进制表示的，那么把二者拼接起来就是最终的物理地址了

  • ⑤访问目标内存单元

在分页存储管理（页式管理）的系统中，页是信息的物理单位，分页完全是系统行为，因此 页的大小由系统决定，逻辑地址在计算机的视角很好确定。所以，页式管理中地址是一维的。即，只要给出一个逻辑地址，系统就可以自动地算出页号、页内偏移量 两个部分，并不需要显式地告诉系统这个逻辑地址中，页内偏移量占多少位。

3.具有快表的地址变换机构

快表，又称联想寄存器(TLB)，是一种 访问速度比内存快很多的高速缓存器，用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。

注：TLB 不是内存；快表与 Cache(高速缓冲器) 的区别在于，块表中只有页表项的副本，而普通 Cache 中可能有其他各种数据的副本，可以把快表理解为一种特殊的 Cache。

• 设某进程执行过程中要访问 (0,4) 这个逻辑地址，访问过程如下：

  

  

注：在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定算法对旧的页表项进行替换（局部性原理）。

4.两级页表

两级页表的分配管理方式属于基本分页存储管理范畴，其用于解决页表项占据连续页框的问题。

• 单级页表存在的问题

  问题一：页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。

  解决：可建立两级页表，一级页表为页目录表，二级页表离散存储。

  问题二：没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。

  解决：可以在需要访问页面时才把页面调入内存（虚拟存储技术）。可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存

• 两级页表的原理、地址结构

  二级页表实际上是在原有页表结构上再加上一层页表，如下图所示。

  

  建立多级页表的目的在于建立索引，以便不用浪费主存空间去存储无用的页表项，也不用盲目地顺序式查找页表项。

  

  例：某系统按字节寻址，支持 30 位的逻辑地址，采用分页存储管理，页面大小为 4KB，页表项长度为 4B，试问逻辑地址的结构。

  页面大小为4KB=212B，则页内偏移量要用12位表示。

  30-12=18，则顷号用18位表示，即进程最多有218个页面，一共需要218个页表项来记录这些页面与物理块的映射关系，且页号范围是：0~218-1。

  页表项长度是4B，一个内存块（页框）最多存储4K/4=212/4=210个页表项。

  218个页表项则需要218/210=28个内存块才能存储。

  即需要专门给进程分配28=256个连续的物理块（页框）来存放它的页表。

  为避免连续占用内存块问题，可以设置28=256个二级页表，并用一级页表来记录这些二级页表，因此一级页号占8位。

• 地址变换

  例： 将逻辑地址 (00000000,0000000001,111111111111) 转换为物理地址（用十进制表示）。

  

  首先，按照地址结构将逻辑地址拆分成三部分

  • ① 从 PCB 中读出页目录表始址，再根据一级页号查页目录表，找到下一级页表在内存中的存放位置。
  • ② 根据二级页号查二级页表，找到最终想访问的内存块号。
  • ③ 结合页内偏移量得到物理地址。

  最终要访问的内存块号为 4，该内存块的起始地址为 4*4096 = 16384 页内偏移量为 4095。

  最终的物理地址为：16384 + 4095= 20479。

  两次页表，若采用“快表”，需要3次访存。

  • 第一次：访问页目录表。
  • 第二次：访问内存中的二级页表。
  • 第三次：访问目标内存单元。

• 多级页表

  若分为两级页表后，页表依然很长，则可以采用更多级页表。并且，若采用多级页表机制，则各级页表的大小不能超过一个页面。

  例：某系统按字节编址，采用 40 位逻辑地址，页面大小为 4KB，页表项大小为 4B，假设采用纯页式存储，则要采用 (   ) 级页表，页内偏移量为 (   ) 位？

  

  页面大小=4KB=212B，按字节编址，因此页内偏移量为12位。

  页号=40-12=28位

  页面大小=212B，页表项大小=4B，则每个页面可存放212/4=210个页表项。

  因此，各级页表最多包含210个页表项，需要10位二进制位才能映射到210个页表项。

  因此每一级的页表对应页号应为10位。总共28位的页号至少要分为3级。

  此外，若未用“快表”，N 级页表机制，需要 N+1 次访问内存。

3.1.5 基本分段式存储管理

分页管理方式是从计算机的角度考虑设计的，目的是提高内存的利用率，提升计算机的性能。分页通过硬件机制实现，对用户完全透明。

分段管理方式的提出则考虑了用户和程序员，以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要。

1. 分段

   段式管理方式按照用户进程中的自然段划分逻辑空间。

   

   例如，用户进程由主程序段、两个子程序段、栈段和数据段组成，于是可以把这个用户进程划分为5段，每段从0开始编址，并分配一段连续的地址空间。

   段内要求连续，段间不要求连续，因此整个作业的地址空间是二维的。

   

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

2. 段表

   程序分多个段，各段离散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张段映射表，简称段表。

   

   段表用于实现从逻辑段到物理内存区的映射。

   特点：

   • ① 每个段对应一个段表项，其中 记录了该段在内存中的起始位置（又称“基址”）和段的长度。
   • ② 各个段表项的长度是相同的。
   • ③ 由于段表项长度相同，在内存中是连续存放，因此段号可以是隐含的，不占存储空间。
   • ④ 段内要求连续，段间不要求连续，因此整个作业的地址空间是二维的。

3. 地址变换机构

   分段系统的地址变换过程如图所示。为了实现进程从逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表始址F和段表长度M。从逻辑地址A到物理地址E之间的地址变换过程如下：

   

   • ① 根据逻辑地址得到段号，段内地址

     从逻辑地址A中取出前几位为段号S，后几位为段内偏移量W。

   • ② 判断段号是否越界

     比较段号S和段表长度M，若 $段号S\ge 段表长度M$ ，则产生越界中断，否则继续执行。

   • ③ 查询段表，找到对应段表项

     段表中段号S对应的 $段表项地址=段表始址F+段号S\times 段表项长度$ 。

   • ④ 检查段内地址是否超过段长

     取出该段表项的前几位得到段长C。若$段内偏移量W\ge 段长C$，则产生越界中断，否则继续执行。

   • ⑤ 计算得到物理地址

     取出段表项中该段的始址b，计算 $物理地址E=段基址b+偏移量W$ ，得到物理地址E。

   • ⑥ 访问目标内存单元

     用得到的物理地址E去访问内存。

4. 段的共享与保护

   • 共享

     在分段系统中，段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的。

     不能修改的代码称为纯代码或可重入代码（它不属于临界资源），这样的代码和不能修改的数据可以共享，而可修改的代码和数据不能共享。

   • 保护

     分段管理的保护方法主要有两种：一种是存取控制保护，另一种是地址越界保护。

     • 存取控制保护：指在段表的每个表项中，设置“存取控制”字段，规定对该段的访问方式。
     • 地址越界保护：指在进行存储访问时，要检查逻辑地址是否超出了进程的地址空间。

5. 分段、分页管理的对比

   	存储信息	地址空间	信息保护	访存次数
   分页管理	页是信息的物理单位 对用户透明 系统行为	一维 记忆符()	不易	分页(单级页表)需两次访问 页表+目标内存单元
   分段管理	段是信息的逻辑单位 对用户可见 用户需求	二维 段名+段内地址([D]|)	容易 纯代码	分段需两次访问 段表+目标内存单元

3.1.6 段页式管理

1. 段页式管理结构

   分页存储管理能有效地提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享和保护。将这两种存储管理方法结合起来，便形成了段页式存储管理方式。

   段页式存储管理方式，将作业的地址空间首先被分成若干逻辑段，每段都有自己的段号，然后将每个段分成若干大小固定的页，内存空间分为大小一个个大小相等的分区。如下图所示。

   

   在段页式系统中，作业的逻辑地址分为三部分：段号、页号和页内偏移量。如下图所示。

   

   段号的位数决定了每个进程最多可以分几个段，页号位数决定了每个段最大有多少页，页内偏移量决定了页面大小、内存块大小是多少。

   在一个进程中，段表只有一个，而页表可能有多个。

   例：如下图所示的段页式格式，

   

   • 段号16位，因此进程中最多有216=64K个段。
   • 页号4位，因此每个段最多有24=16页。
   • 页内偏移量有12位，因此每个内存块大小为212=2KB

   分段对用户是可见的，程序员编程时需要显式地给出段号、段内地址。而将各段分页对用户是不可见的。系统会根据段内地址自动划分页号和页内偏移量。因此，段页式管理的地址结构是二维的。

2. 地址转换

   在进行地址变换时，首先通过段表查到页表始址，然后通过页表找到页号，最后形成物理地址。

   

   如下图所示，进行一次访问实际需要三次访问主存，这里同样可以使用快表来加快查找速度，其关键字由段号、页号组成，值是对应的页帧号和保护码。

   

   • ① 根据逻辑地址得到段号、页号、页内偏移量
   • ② 判断段号是否越界若S≥M，则产生越界中断，否则继续执行
   • ③ 查询段表找到对应的段表项，段表项的存放地址为$F+S\times 段表顶长度$
   • ④ 检查页号是香越界，若页号≥页表长度，则发生越界中断，否则继续执行
   • ⑤ 根据页表存放块号、页号查询页表找到对应页表项
   • ⑥ 根据内存块号页内偏移量得到最终的物理地址
   • ⑦ 访问目标内存单元

引入段式存储管理方式，主要是为了更好地满足用户的一系列要求。

方便编程
共享和保护
动态链接和增长

3.1.6 本节小结

1）为什么要进行内存管理？

​ 在单道批系统阶段，一个系统在一个时间段内只执行一个程序，内存的分配极其简单，即仅分配给当前运行的进程。引入多道批程序后，进程之间共享的不仅仅是处理机，还有主存储器。然而，共享主存会形成一些特殊的挑战。若不对内存进行管理，则容易导致内存数据的混乱，以至于影响进程的并发执行。因此，为了更好地支持多道程序并发执行，必须进行内存管理。

2）多级页表解决了什么问题？又会带来什么问题？

多级页表解决了当逻辑地址空间过大时，页表的长度会大大增加的问题。而采用多级页表时，一次访盘需要多次访问内存甚至磁盘，会大大增加一次访存的时间。

无论是段式管理、页式管理还是段页式管理，读者都只需要掌握下面三个关键问题：

1.逻辑地址结构
2.页（段）表项结构
3.寻址过程。
搞清楚这三个问题，就相当于搞清楚了上面几种存储管理方式。再次提醒读者区分逻辑地址结构和表项结构。