1. 存储器管理的基本概念

1.1 存储器的层次结构

现代计算机系统常采用多层结构，使得存储器系统不仅具有能与处理机速度相匹配的速度，而且还拥有非常大的容量以及便宜的价格。

一般的通用计算机至少将存储器分为 CPU 寄存器、主存和辅存三个层次，而在较高档的计算机中，还将存储器进一步细分为寄存器、高速缓存、主存储器、固定磁盘、可移动存储介质等多个层次。

1.2 程序的装入

在编辑源程序时，用户通常使用符号名来访问指令和数据，符号名的集合被称作名字空间。

源程序必须经过编译、链接，并装入内存后，才能运行。内存由一系列存储信息的物理单元（字或字节）组成，每个单元都有自己的地址，我们将每个内存单元的这种实际地址称作物理地址或绝对地址，而将内存单元的集合称作存储空间或绝对地址空间。

1.2.1 绝对装入方式（单道程序环境）

如果在编译时，事先能够知道程序将驻留在内存的什么位置，则编译程序可直接将程序的符号地址转换成绝对地址，产生使用绝对地址的目标模块，进而链接成使用绝对地址的转入模块，这样，装入程序便可以按照装入模块中的地址将程序和数据装入内存，而不需要对模块中的地址部分进行修改。

1.2.2 可重定位装入方式与静态重定位

在多道程序的环境下，编译程序不直接将符号地址翻译成绝对地址，而是产生从 0 开始编址的目标模块，并由链接程序将多个模块及它们所要调用的库函数一起链接成一个从 0 开始编址的、完整的装入模块。可见，此时装入模块中指令和数据的地址是相对于装入模块的首字节而编址的，因此，被称作相对地址或逻辑地址，相对地址的集合被叫作相对地址空间，或者逻辑地址空间。
将装入模块中指令和数据的相对地址调整成相应内存单元的绝对地址的过程称为重定位。
如果重定位是在装入时，由重定位装入程序一次性完成的，则被称作静态重定位，而相应的装入方式则称为可重定位装入方式。不允许程序运行时在内存中移动位置。

1.2.3 动态运行时装入方式

在程序真正执行时进行的重定位。通过增设一个重定位寄存器，将正在执行作业在内存中的起始地址，每次访问指令和数据时，由硬件自动将相对地址与重定位寄存器中的起始地址相加，形成实际的物理地址。

1.3 程序的链接

链接是将编译后得到的各个目标模块以及所需的库函数连接在一起，形成一个完整的装入模块。其必须将各目标模块中的相对地址和外部调用符号转换成装入模块中的相对地址。
根据链接时间不同，分为：

1.3.1 静态链接方式（适应于连续内存分配方式）

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

1.3.2 装入时动态链接（使用于离散分配）

装入一个模块时，若发生一个外部模块调用事件，则由装入程序找出相应的外部模块，将它装入内存，并把它链接到调用者模块上去。
优点是便于对程序模块进行修改和更新，并且可以对外存中的目标模块实现共享。

1.3.3 运行时动态链接（使用于虚拟存储器）

装入模块时，若发现一个被调用模块尚未装入内存，便立即由OS找出该模块，将它装入内存，并把它链接到调用者模块上。
优点：除了便于实现目标模块的修改、更新和共享外，还会加快程序的装入过程，由于它不会将本次执行过程中调用不到的模块装入内存，因此能提高内存的利用率。

2. 连续分配方式

2.1 单一连续分配（单用户、单任务）

将内存分为系统区和用户区，系统区仅供OS使用，通常位于内存的低端；而用户区则供用户使用，其中仅能存放一道作业。

2.2 固定分区分配

在系统启动时，将内存的用户空间划分成若干区域，这些分区的大小和边界在系统运行期间不再变化，并且允许在每个分区中装入一道作业。

系统中需要建立固定分区说明表，其中给出每个分区的起始地址、大小以及该分区是否已分配出去的状态信息。若未找到合适的分区，则拒绝为该用户程序分配内存。当一用户要释放内存时，只需将相应表项的状态改为“未分配”即可。
固定分区分配方式可以是多道程序共存于内存中，但内存中程序的导数仍将受到分区个数的限制，会存在内部碎片。

2.3 动态分区分配

每次装入作业时，动态地为作业从可用内存中划分出一个分区，其大小刚好能满足作业的实际需要。因此，内存中分区的个数和每个分区的大小将随着系统中允许的作业情况而变化。
动态分区分配方式常采用空闲分区表或空闲分区链表来管理可用内存，其中每个表项或结点对应于内存的一个空闲分区，记录有该分区的大小和起始地址等信息。

常用的分配算法：

1. 首次适应算法。将空闲分区按起始地址递增的次序排列，每次分配均从空闲分区表或空闲分区链首开始顺序查找，并从第一个能满足要求的空闲分区中划分出作业所要求的空间分配出去。该算法优先使用内存低地址部分的空闲分区，在高地址部分保留较大的空闲分区，但会在低端留下很多难以利用的小空闲分区，而每次分配时，对空闲分区的查找都必须经过这些分区，增加查找开销。
2. 循环首次适应算法。将空闲分区按起始地址递增的顺序排成循环链表，每次分配均从上次分配的位置之后开始查找。使内存空闲分区分布更加均匀，从而减少查找空闲分区的开销，但会使存储器中缺乏大的空闲分区。
3. 最佳适应算法。将空闲分区按大小递增的次序排列，将能满足要求的最小空闲分区分配出去。内存中留下大量难以利用的小空闲分区。
4. 最坏适应算法。将空闲分区按大小递减的次序排列。该算法产生碎片的几率最小，但会使内存区缺乏大的空闲分区。

为了减少大量难以利用的小空闲分区造成的查找开销，在进行内存分配时，可事先设定一定阈值，当找到的分区中剩余空间小于阈值时，将不再进行分区的分隔，而是把整个分区分配给请求者。
当作也运行完毕时，需要进行内存的回收，系统将检查是否有空闲分区与回收区相邻，如果有，则修改空闲分区表或空闲分区链将它们进行合并。

2.4 伙伴系统

在伙伴系统中，内存块的大小为$2^S$2S字节，$L\leq S \leq U$L≤S≤U其中，$2^L$2L为可分配的最小块的尺寸，而$2^U$2U为可分配的最大块的尺寸，通常$2^U$2U是可供分配的整个内存空间的大小。

开始时，可用于分配的空间大小为$2^U$2U字节，当有一个进程申请K字节时，如果$2^{U-1}<K \leq 2^U$2U−1<K≤2U，则分配整个分区给该进程，否则，将分区划分为两个大小相等（均为$2^{U-1}$2U−1字节）的伙伴。如果$2^{U-2}<K \leq 2^{U-1}$2U−2<K≤2U−1，那么将两个伙伴中的一个分配给该进程；否则，其中的一个伙伴又被分成大小相等的两块。继续这个过程，知道产生可供分配的合适块为止。

2.5 可重定位分区分配

解决问题：可能用户程序因找不到足够大的空闲分区而难以装入，但所有空闲分区容量的总和却足以满足该程序的要求。
将内存中所有作业进行移动，从而将原来分散的多个空闲分区移到同一端拼接成一个大的空闲分区，以装入用户的作业。可重定位分区分配方式就是在动态分区分配方式的基础上增加紧凑功能，需要得到动态重定位技术的支持。

2.6 分区的保护

为了防止一个用户作业破坏操作系统或其他用户作业，常采用界限寄存器和保护键的方法来进行分区的保护。

1. 界限寄存器。一对上、下限寄存器，用来存放正在执行的作业在内存的结束地址和起始地址。
2. 保护键。它为每个分区分配一个单独的保护键，相当于一把锁，同时为每个进程分配一个相应的保护键，相当于一把钥匙。每当进行内存访问时，都要检查钥匙和被访问单元的锁是否匹配，若不匹配，则发生保护性中断。

2.7 对换

所谓对换，是指把内存中暂时不能运行的进程或暂时不用的程序或数据，调到外存上，以便腾出足够的内存空间，再把具备运行条件的进程或进程所需要的程序和数据调入内存。
如果对换是以整个进程为单位，便称之为“整体对换”或“进程对换”，这种对换广泛应用于分时系统中，如果对换是以“页”或“段”为单位，则分别称之为“页面兑换”或“分段对换”，它们实现虚拟存储器的基础，这部分内容将在虚拟存储器中介绍。
为了实现进程对换，系统能实现下面三方面的功能：

1. 兑换空间的管理，对对换空间管理的主要目标时提高进程换入、换出的速度，因此通常将对换空间设置在高速的磁盘中，并采取简单的连续分配方式。
2. 进程的换入。系统应定时地查看所有进程的状态，从中找出“就绪”但已换出的进程，将它们按某种次序依次换入，直至无可换入的进程为止。
3. 进程的换出。当有就绪进程要换入，但已无足够的内存空间时，系统便要进行换出。选择换出进程时，首先将选择处于阻塞状态且优先级最低的进程，若找不到这样的进程，则要根据换入进程的优先权、在外存的驻留时间等因素，考虑是否将某个低优先权的就绪进程换出。

3. 基本分页存储管理方式

动态分区分配方式会形成许多外部碎片，虽然它们可以通过“紧凑”技术加以解决，但需为之付出巨大的时间开销。因此，OS 中引入了分页存储管理方式，它将一个作业离散地存放到内存中，从而使系统无须紧凑，便能很好地解决碎片问题。

3.1 分页存储管理的基本方法

系统将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页，相应地，将内存空间分成若干与页面同样大小地块，称为物理块或页框。内存的分配以块为单位，并允许将一个进程的若干页分别装入到多个可以不相邻接的物理块中。
为了地址映射方便，页面的大小通常设置成2的幂，如果页面的大小为$2^k$2k字节，逻辑地址的长度为n位，可将线性的逻辑地址分成两部分：右边的k位为业内位移量W，左边n-k位为页号P。

在进程运行时，为了能在内存中找到每个页面对应的物理块，系统为每个进程建立了一张页面映射表，简称页表。进程的每个页占页表的一个表项，其中记录了相应页对应的内存块的块号，以及用于分页保护的存取控制信息。

分页系统中内存分配实例

3.2 地址变换机构

3.2.1 基本的地址变换机构

页式存储管理系统中，逻辑地址到物理地址的转换是在进程执行的过程中，由硬件地址变换机构借助页表自动进行的。

通常，将作业的页表放在内存中，而在系统中只设置一个页表寄存器。当一进程因 CPU 调度而转入执行状态时，其页表的内存始址和长度将从该进程的 PCB 中装入页表寄存器。当进程要访问某个逻辑地址中的指令或数据时，地址变换机构自动地将逻辑地址分为页号和页内地址两部分，并将页号与页表寄存器中地页表长度进行比较，若页号不小于页表长度，便产生越界中断，否则便以页号为索引去检索页表，从中得到该页地物理块号，送入物理地址寄存器与业内地址拼接，形成对应地物理地址。

分页系统地址变换机构（https://blog.****.net/dongyanxia1000/article/details/51711780）。

3.2.2 具有快表地地址变换机构

由于页表是存放在内存中的，CPU 每存取一条指令或一个数据，都要两次访问内存：第一次访问内存中的页表，以得到指令或数据所在页对应的内存块号；第二次才根据物理地址存取指令或数据。为了提高存取效率，可在地址变换机构中，增设一个具有并行查找能力的高速缓冲寄存器，用以存放当前被频繁访问的页面的页号和对应的页表项。

由于成本关系，快表通常做得较小，一般只能存放16~512个页表项。如果快表的命中率是 α，访问一次内存的时间是 t，访问快表的时间为 β，则通过逻辑地址访问内存中的一个数据的有效访问时间可表示为：αxβ+(t+β)(1-α)+t。

3.3 多级页表

对于较大逻辑地址空间，可将页表进行分页，并将各个页表离散地存放到内存块中，必须为离散分配的页表再建立一张页表，称为外层页表。在使用两级页表的分页系统中，每次访问一个数据需要访问三次内存，故同样需要增设快表来有效地提高访问速度。利用多级页表，虽然无需再为页表分配大段连续的内存空间，但是页表所占用的内存空间非常大，可以用虚拟技术解决，仅将当前所需的页表页调入内存。

两级页表结构（https://max.book118.com/html/2018/0215/153241902.shtm）。

4. 分段式存储管理方式

用户通常喜欢将自己的作业按逻辑关系划分为若干段，然后通过段名和段内地址来访问相应的程序或数据，同时，还希望能以段为单位对程序和数据进行共享和保护，并要求分段能动态增长——分段式存储管理方式诞生了。

4.1 分段系统的基本原理

分段系统中，作业地址空间中的用户程序被划分成若干段，每个段定义了一组逻辑信息，有自己的段名和段长，并都采用首地址为0的一段连续地址空间；而内存空间的管理则与动态分区相似，只不过将分配对象由整个程序变为段，即为每个段分配一个连续的内存区，而且，在逻辑上连续的多个段在内存中可以不必连续存放。

段表实现地址映射（https://max.book118.com/html/2018/0215/153241902.shtm）。

用户通过段名、段内地址来访问指令和数据，因此，分段系统的作业地址空间是二维的，系统为每个进程建立了一张段映射表，进程的每个段在段表中占一个表项，其中记录了该段在内存中的起始地址和段的长度以及对分段进行保护的存取控制信息。像分页系统一样，由于段表存放在内存中，每访问一个数据也需要访问两次内存。

分段系统的地址变换过程（https://max.book118.com/html/2018/0215/153241902.shtm）。

4.2 分页与分段比较

1. 页是信息的物理单位，分页是为了提高内存的利用率。段则是信息的逻辑单位，它含有一组其意义相对完整的信息，分段是为了能更好地满足用户的需要。
2. 页的大小固定由系统决定。段的长度不固定，且由用户锁编写的程序决定。
3. 分页的地址空间是一维的，程序员只需要一个记忆符，便可表示一个地址。分段的地址空间是二维的，程序员在标识一个地址时，既需要给出段名，又需给出段内地址。

4.3 段页式存储管理方式

是分页式和分段管理的结合，它先将地址空间中的用户程序分成若干个段，再将每个段分成若干页。而内存空间则被分成与页同样大小的块，并以块为单位来进行内存的分配。

段页式系统的地址空间是二维的，每个逻辑地址包括段号和段内地址两部分，段内地址又被地址变换机构根据页面大小自动分成段内页号和页内地址。为了实现地址变换，系统必须为每个进程建立一张段表，并为每个分段建立一张页表，段表项给出了每个分段所对应的页表的内存始址和长度，页表项则给出了页所对应的内存块号。在进行地址变换时，首先根据段表寄存器中的段表始址和逻辑地址中的段号找到对应的段表项，从中获得该段的页表地址；然后再利用页表始址和逻辑地址中的段内页号来获得对应的页表项，从中获得该页的内存块号；由内存块号与业内地址拼接形成物理地址。

由于段表和页表都放在内存中，每存取一条指令或一个数据都需要三次访问内存。