1 内存管理概念

1.1 基本原理和要求

内存管理：

操作系统对内存的划分和动态分配

内存管理的功能有：

程序的装入和链接：

源程序 -> 可执行程序：

• 编译。由编译程序将用户源代码编译成若干目标模块。
• 链接。由链接程序将编译后形成的一组目标模块及所需的库函数链接在一起，形成一个完整的装入模块。
• 装入。由装入程序将装入模块装入内存运行。

链接方式：

• 
  静态链接
  
  。

  在程序运行之前，先将各目标模块及它们所需的库涵数链接成一个完整的可执行程序，以后不再拆开。

• 
  装入时动态链接
  
  。

  将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的方式。

• 
  运行时动态链接
  
  。

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

装入方式：

1. 绝对装入。

   在编译时，若知道程序将骁留在内存的某个位置，则编译程序将产生绝对地址的目标代码。绝对装入程序按照装入模块中的地址，将程序和数据装入内存。由于程序中的逻辑地址与实际内存地址完全相同，因此不需对程序和数据的地址进行修改。绝对装入方式只适用于单道程序环境。

   另外，程序中所用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。而通常情况下在程序中采用的是符号地址，编译或汇编时再转换为绝对地址。

2. 可重定位装入。

   在多道程序环境下．多个目标模块的起始地址（简称始址）通常都从0开始，程序中的其他地址都是相对于始址的，此时应采用可重定位装入方式。根据内存的当前情况，将装入模块装入内存的适当位置。装入时对目标程序中指令和数据的修改过程称为重定位，地址变换通常是在装入时一次完成的，所以又称静态重定位。

   静态重定位的特点是，一个作业装入内存时，必须给它分配要求的全部内存空间，若没有足够的内存，则不能装入该作业。

   此外，作业一旦进入内存，整个运行期间就不能在内存中移动，也不能再屮请内存空间。

3. 动态运行时装入，也称动态重定位。

   程序在内存中若发生移动，则需要采用动态的装入方式。装入程序把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址均为相对地址。这种方式需要一个重定位寄存器的支持。

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

逻辑地址空间和物理地址空间：

编译后，每个目标模块都从0号单元开始编址，这称为该目标模块的相对地址（或逻辑地址）。当链接程序将各个模块链接成一个完整的可执行目标程序时，链接程序顺序依次按各个模块的相对地址构成统一的从0号单元开始编址的逻辑地垃空问。

用户程序和程序员只需知道逻辑地址，而内存管理的具体机制则是完全透明的，只有系统编程人员才会涉及内存管理的具体机制。不同进程可以有相同的逻辑地址，因为这些相同的逻辑地址可以映射到主存的不同位置。

物理地址空间是指内存中物理单元的集合，它是地址转换的最终地址，进程在运行时执行指令和访问数据，最后都要通过物理地址从主存中存取。

当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换成物理地址，这个过程称为地址重定位；

内存保护：

两种方法：

1. 在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界。

2. 采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址

1.2 覆盖与交换

覆盖技术：

引入了覆盖技术，用来解决 “

程序大小超过物理内存总和

” 的问题‘

覆盖技术的思想

：将程序分为多个段（多个模块）。常用的段常驻内存，不常用的段在需要时调入内存。内存中分为一个“固定区”和若干个“覆盖区”。需要常驻内存的段放在“固定区”中，调入后就不再调出（除非运行结束）不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存必须由程序员声明覆盖结构，操作系统完成自动覆盖。

缺点

：对用户不透明，增加了用户编程负担。覆盖技术只用于早期的操作系统中，现在已成为历史。

交换技术：

交换（对换）技术的设计思想

：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）

中级调度（内存调度），就是要决定将哪个处于挂起状态的进程重新调入内存。

暂时换出外存等待的进程状态为挂起状态（挂起态，suspend）

挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态

何时换：

1. 具有对换功能的操作系统中，通常把磁盘空间分为
   
   文件区
   
   和
   
   对换区
   
   两部分。

   文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式；

   对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式（学过文件管理章节后即可理解）。

   总之，对换区的I/O速度比文件区的更快。

2. 交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。

   例如：在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程； 如果缺页率明显下降，就可以暂停换出。

3. 可优先换出阻塞进程；可换出优先级低的进程；为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间…

（注意：PCB会常驻内存，不会被换出外存）

1.3 连续分配管理方式

单一连续分配：

在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。

内存中只能有一道用户程序，用户程序独占整个用户区空间。

优点

：实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护（eg：早期的PC操作系统MS-DOS）。

缺点

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

固定分区分配：

整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，

划分方式

：

1. 
   分区大小相等
   
   ：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合

   （比如：钢铁厂有n个相同的炼钢炉，就可把内存分为n个大小相等的区域存放n个炼钢炉控制程序）

2. 
   分区大小不等
   
   ：增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分

   （比如：划分多个小分区、适量中等分区、少量大分区）

操作系统需要建立一个数据结构——

分区说明表

，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）。

优点

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

缺点

：

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

动态分区分配：

动态分区分配又称为可变分区分配。

这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。

因此系统分区的大小和数目是可变的。

（eg：假设某计算机内存大小为64MB，系统区8MB，用户区共56MB…）

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

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

   算法	算法思想	分区排列顺序	优点	缺点
   首次适应	从头到尾找适合的分区	空闲分区以地址递增次序排列	综合看性能最好。算法开销小，回收分区后一般不需要对空闲分区队列重新排序
   最佳适应	优先使用更小的分区，以保留更多大分区	空闲分区以容量递增次序排列	会有更多的大分区被保留下来，更能满足大进程需求	会产生很多太小的、难以利用的碎片；算法开销大，回收分区后可能需要对空闲分区队列重新排序
   最坏适应	优先使用更大的分区，以防止产生太小的不可用的碎片	空闲分区以容量递减次序排列	可以减少难以利用的小碎片	大分区容易被用完，不利于大进程； 算法开销大（原因同上）
   邻近适应	由首次适应演变而来，每次从上次查找结束位置开始查找	空闲分区以地址递增次序排列（可排列成循环链表）	不用每次都从低地址的小分区开始检索。算法开销小（原因同首次适应算法）	会使高地址的大分区也被用完

3. 如何进行分区的分配与回收操作？假设系统采用的数据结构是“空闲分区表”…如何分配？

   有相邻就合并分区表，无就创建一个表项。

1.4 非连续分配方式

分页存储：

（页框=页帧=内存块=物理块=物理页面）。（页框号=页帧号=内存块号=物理块号=物理页号）

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，可以放到不相邻的各个页框中。

（注：进程的最后一个页面可能没有一个页框那么大。也就是说，分页存储有可能产生内部碎片，因此页框不能太大，否则可能产生过大的内部碎片造成浪费）

逻辑地址结构：

页表：

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。

注：页表通常存在PCB（进程控制块）中

1. 一个进程对应一张页表
2. 进程的每个页面对应一个页表项
3. 每个页表项由“页号”和“块号”组成
4. 页表记录进程页面和实际存放的内存块之间的映射关系
5. 每个页表项的长度是相同的

Eg：

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

内存块大小 = 页面大小 = 4KB = 2

¹²

B

4GB 的内存总共会被分为 2

³²

/ 2

¹²

= 2

²⁰

个内存块

内存块号的范围应该是 0 ~ (2

²⁰

-1)

内存块号至少要用 20bit 来表示

至少要用 3B 来表示块号（3*8=24bit）

由于页号是隐含的，因此每个页表项占3B，存储整个页表至少需要3*(n+1)B

注意：页表记录的只是内存块号，而不是内存块的起始地址！J 号内存块的起始地址 = J * 内存块大小

如何地址转换：

在系统中通常设置一个页表寄存器 (PTR)，存放页表在内存的起始地址 F 和页表长度 M.

进程未执行时，页表的始址和长度存放在进程控制块中，当进程执行时，才将页表始址和长度存入页表寄存器。

设页面大小为L，逻辑地址A到物理地址E的变换过程如下（逻辑地址、页号、每页的长度都是十进制数）：

1. 计算页号P（P = A/L）和页内偏移量W（W = A%L）。
2. 比较页号P和页表长度M，若P>=M，则产生越界中断，否则继续执行。
3. 页表中页号P对应的页表项地址=页表始地址F + 页号P * 页表项长度，取出该页表項内容b，即为物理块号。

要注意区分页表长度和页表项长度。页表长度的值是指一共有多少页，页表项长度是指页地址占多大的存储空间。

计算E = b * L + W，得到的物理地址E去访问内存。

以上整个地址变换过程均是由硬件自动完成的。

例如

若页面大小为 1KB,页号 2 对应的物理块为 b = 8，计算逻辑地址 A = 2500 的物理地址 E 的过程如下：

P = 2500 / 1K = 2，

W = 2500 % 1K = 452，

查找得到页号 2 对应的物理块的块号为 8，E = 8 × 1024 + 452 = 8644。

1.5 快表

快表，又称联想寄存器（TLB，translation lookaside buffer），是一种访问速度比内存快很多的高速缓存（TLB不是内存！），用来存放最近访问的页表项的副本，可以加速地址变换的速度。一般集成在CPU内部.

与此对应，内存中的页表常称为慢表。

如何转换：

1. CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。

2. 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量 拼接形成物理地址，最后，访问该物理地址对应的内存单元。

   因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。

3. 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。

   因此，若快表未命中，则访问某个逻辑地址需要两次访存

（注意：在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。

但若快表已满，则必须按照一定的算法对旧的页表项进行替换）

TLB 和普通 Cache 的区别——TLB 中只有页表项的副本，而普通 Cache 中可能会有其他各种数据的副本

时间局部性

：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。（因为程序中存在大量的循环）

空间局部性

：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。（因为很多数据在内存中都是连续存放的）

1.6 二级页表

把页表再分页并离散存储，然后再建立一张页表记录页表各个部分的存放位置，称为页目录表，或称外层页表，或称顶层页表结构：

如何转换：

1. 按照地址结构将逻辑地址拆分成三部分
2. 从PCB中读出页目录表始址，再根据一级页号查页目录表，找到下一级页表在内存中的存放位置
3. 根据二级页号查二级页表，找到最终想访问的内存块号
4. 结合页内偏移量得到物理地址

注意几个细节：

1. 若分为两级页表后，页表依然很长，则可以采用更多级页表，一般来说各级页表的大小不能超过一个页面

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

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

   页号 = 40-12 = 28 位, 页表项大小= 4B 页面大小= 2
   
   ¹²
   
   B，则每个页面可存放2
   
   ¹²
   
   / 4= 2
   
   ¹⁰
   
   个页表项

   因此各级页表最多包含 2
   
   ¹⁰
   
   个页表项，需要10位二进制位才能映射到 2
   
   ¹⁰
   
   个页表项，因此每一级的页表对应页号应为10位。总共28位的页号至少要分为三级

2. 两级页表的访存次数分析（假设没有快表机构）

   第一次访存：访问内存中的页目录表

   第二次访存：访问内存中的二级页表

   第三次访存：访问目标内存单元

1.7 基本分段存储管理方式

分段：

进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从0开始编址

内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。

由于是按逻辑功能模块划分，用户编程更方便，程序的可读性更高

逻辑地址结构：

段表：

地址变换：

对比分页：

1. 页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。

2. 段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。

3. 分段对用户是可见的，用户编程时需要显式地给出段名。

4. 页的大小固定且由系统决定。

5. 段的长度却不固定，决定于用户编写的程序。

6. 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。

7. 分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。

分段比分页更容易实现信息的共享和保护。

1. 不能被修改的代码称为纯代码或可重入代码（不属于临界资源），这样的代码是可以共享的。
2. 可修改的代码是不能共享的（比如，有一个代码段中有很多变量，各进程并发地同时访问可能造成数据不一致）

1.8 段页式管理

分页、分段的优缺点分析：

段页式管理：

将进程按逻辑模块分段，再将各段分页（如每个页面4KB）

再将内存空间分为大小相同的内存块/页框/页帧/物理块

进程前将各页面分别装入各内存块中

逻辑结构：

如何转换：

1.9 总结

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

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

2. 页式管理中每个页表项大小的下限如何决定？

   页表项的作用是找到该页在内存中的位置。以32位逻辑地址空间、字节编址单位、一页 4KB 为例，地址空间内共含有2
   
   ³²
   
   B/4KB=1M页，20位才能保证表示范围能容纳所有页面，又因为以字节作为编址单位，即页表项的大小>=[20/8]=3B.所以在这个条件下，为了保证页表项能够指向所有页面，页表項的大小应该大于3B：当然，也可选择更大的页表项大小，让一个页面能够正好容下整数个页表项，以方便存储（例如取成4B，一页正好可以装下1K个页表项）,或增加一些其他信息。

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

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