1.内存管理概念

1.1.内存的基础知识

1.内存用于缓和CPU和硬盘（外存）之间的速度矛盾（CPU速度快，而外存速度慢），因此，程序执行前要先存放到内存中CPU才能处理

2.通过给内存的存储单元编址的方式区分不同程序在内存中的地方

①内存地址从0开始，每个地址对应一个存储单元

②按字节编址，每个存储单元的大小为1B，即8bit

③按字编址，若字长为16位，则每个存储单元的大小为2B，即16bit

3.程序中指令的地址是逻辑地址 4.内存的装入模块（.exe执行文件）在装入内存时，有三种方式：

①绝对装入：在提前知道程序执行后将会存放在内存哪个位置的前提下，指令中的相对地址经过编译器的处理后可以变为绝对地址

②静态重定位（可重定位装入）：编译器根据装入内存中的起始物理地址（加上指令中的相对地址）得到最终的地址

特点：（1）装入内存时，就必须分配其要求的全部内存空间（提前分配好，且要求地址连续）

（2）在运行期间不能移动（指令中已经写死指令的地址空间）

③动态重定位（动态运行时装入）：装入内存时的指令地址仍然是逻辑地址，但是需要重定位寄存器的支持（重定位寄存器存放的是装入模块存放的起始地址，CPU通过重定位寄存器中存放的起始地址+指令中存放的逻辑地址得到最终的地址）

特点：（1）允许程序在内存中发生移动（通过修改重定位寄存器中存放的起始地址的值实现）

（2）可以将程序分配到不连续的存储区

（3）运行前可以只装入部分代码，在执行期间动态申请分配内存

（4）便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间

5.从写程序到程序运行经历的步骤：编译→链接→装入

（1）程序员写出源代码文件（例如.c文件，若干个.c文件中存放main函数、a函数和b函数）

（2）源代码文件经过编译形成目标模块文件（一一对应，例如.c文件对应.o文件），目标模块文件中包含代码所对应的指令，指令的编址都是逻辑地址，即相对地址从0开始：编译的实质就是将高级语言翻译成与之等价的机器语言

（3）将若干个目标模块文件和这些目标模块文件所调用的库函数（例如printf）通过链接（组装起来）形成完整的装入模块（.exe文件），此时装入模块具有完整的逻辑地址

即将目标文件和库函数通过链接形成装入模块

（4）程序运行就是将装入模块装入内存，并且此时逻辑地址就能转换成物理地址

6.链接的三种方式：

①静态链接：装入前就将所有目标模块和所需的库函数链接成一个完整的装入模块

②装入时动态链接：运行前边装入边链接

③运行时动态链接：需要该目标模块才对它进行链接

1.2.内存管理的概念

1.操作系统负责内存空间的分配和回收（例如记录内存中哪些地方空闲、哪些地方已分配；进程运行结束后回收其所占用的内存空间；新的进程应该存放在内存中的哪个位置等等）

2.操作系统需要从逻辑上对内存空间进行扩充（把物理上很小的内存拓展为逻辑上很大的内存）

3.操作系统提供地址转换功能（负责程序逻辑地址和物理地址的转换，使得程序员在编程时可以不用考虑底层地址转换的实现细节）

4.操作系统提供内存保护功能（保证各进程在各自存储空间内运行，即进程只能访问自己的内存空间，不能访问别的进程的内存空间）

①设置上、下限寄存器（分别存放该进程上、下限地址）：进程的指令每次访问某个地址时，CPU通过对比该地址和上、下限寄存器的内容判断是否越界

②通过重定位寄存器（即基址寄存器，存放进程的起始物理地址）和界地址寄存器（即限长寄存器，存放进程的最大逻辑地址）进行越界检查：CPU首先对比指令中的逻辑地址和界地址寄存器中存放的最大逻辑地址，若逻辑地址更大，则发生越界；若逻辑地址更小，则该逻辑地址加上重定位寄存器中的地址得到物理地址

1.3.覆盖与交换

1.3.1.覆盖

1.覆盖技术的思想：将程序分多个段；常用的常驻内存（调入后不再取出），不常用的使用时调入内存，不使用时调出内存

2.设A(main函数)为常用函数，B函数和C函数不同时调用，D函数只有在调用B函数时才可能调用，E函数和F函数只有在调用函数C时才可能调用，且E函数和F函数不可同时调用

此时，就能将A函数占用的8K内存空间设定为固定区，B函数和C函数的内存空间取最大值设置为覆盖区，D函数、E函数和F函数的内存空间取最大值设置为覆盖区（分区依据：不能同时被访问的程序段共享一个覆盖区，覆盖区的大小取这些程序段占用空间的最大值）

3. 必须由程序员声明覆盖结构，即对用户不透明：程序员在变成时必须指明调用结构，例如哪些函数可以调用哪些函数

1.3.2.交换技术

1.交换技术的思想：当内存紧张时，系统将内存中某些进程暂时换出外存（进程的PCB将会保留在内存中，并且加入挂起队列），内存空间不紧张时，再将这些进程换入内存

进程PCB保留在内存的原因：PCB中保存有该进程在外存中的地址

中级调度（内存调度）：决定将哪个挂起状态的进程重新调入内存

2.被换出的进程应该保留在外存的对换区：

外存分为①对换区和②文件区：对换区I/O速度大于文件区

①对换区：追求对换速度（提升系统整体速度）→连续存储

②文件区：追求空间利用率→离散存储

1.4.连续分配管理方式

1.内部碎片：分配给某进程的内存空间中，有些部分没有用上

2.外部碎片：内存中某些空闲分区因为太小而难以使用（可以通过紧凑技术解决）

1.4.1.单一连续分配

一个程序独占整个用户区

1.4.2.固定分区分配

将用户空间划分为若干个分区，每个分区只装入一道作业

1.分区大小相等：缺乏灵活性（可能出现很小的程序区占用很大的分区/程序过大无法装入分区），但适用多个相同对象的场合

2.分区大小不等：灵活性更强（大程序分配大的分区，小程序分配小分区）

3.操作系统需要建立分区说明表对分区进行管理（表明分区的各个状态）

4.优点：无外部碎片

5.缺点：①程序过大无法装入（可以通过覆盖技术解决）

②产生内部碎片（若程序只有6M，而分区最小只有10M，但程序分区，因此有4M浪费）

1.4.3.动态分区分配

1.不预先划分内存分区（单一连续分配和固定分区分配都是提前划分分区），在进程装入时根据进程的大小动态的建立分区（分区大小正好满足进程需要）

2.系统通过①空闲分区表或②空闲分区链记录内存的现存空闲分区

3.系统根据动态分区算法从空闲分区中选中一个分区分给装入内存的新作业

4.分区的分配：

①当空闲分区大小＞当前将要分配的空间时，修改该空闲分区大小和起始地址：

在大小为4MB的进程5装入分区1后，分区号1的分区大小更改为20 - 4 = 16MB；起始地址更改为8 + 4 = 12MB

②当空闲分区大小 = 当前将要分配的空间时，删除该空闲分区的表项

在大小为4MB的进程5装入分区3后，因为分区号3的大小和进程5相等，因此空闲表中删除分区3

5.进程的回收：

①回收的进程后有相邻的空闲分区，两个相邻分区合并为一个：

将进程4回收后，分区号1的分区大小更改为14MB，起始地址更改为进程4的起始地址即28M

②回收的进程前有相邻的空闲分区，两个相邻分区合并为一个：

将进程3回收后，分区号2的分区大小更改为28MB，起始地址不变

③回收的进程前、后各有一个相邻的空闲分区，三个相邻分区合并为一个：

将进程3回收后，分区号1的分区大小更改为34MB（20 + 10 + 4），起始地址更改为8M（进程1的起始地址）（将分区块号1、分区块号和进程4合并为分区块号1，并且分区块号3变为分区块号2）

④回收的进程前、后都没有相邻空闲分区，回收进程单独成立一块新的空闲分区：

进程2回收后，新增分区块号2，分区大小为进程2的大小14MB，起始地址为进程2的起始地址28M

5.动态分区没有内部碎片，但是有外部碎片（可以通过紧凑技术解决外部碎片，即内存挪位）

图中进程1大小为20MB，而内存中空闲分区的总大小也为20MB，但是分成了三个部分（6 + 10 + 4）MB，可以通过紧凑技术使得这三个部分称为一个部分，就能满足进程1的需求（连续分配管理中，进程要求内存中一段连续的存储空间）

1.5.动态分区分配算法

1.5.1.首次适应算法（First Fit）：地址递增排列

1.算法思想：每次从低地址开始找，找到第一个满足大小的空闲分区

2.实现：空闲分区以地址递增的顺序排列，每次分配内存时顺序查找空闲分区表，找到第一个满足大小的空闲分区，将其分配给该进程，并更新空闲分区表（但无需重新排列）

1.5.2.最佳适应算法（Best Fit）：容量递增排列

1.算法思想：尽可能留下更多的大片空间，即优先使用小的内存空间

2.实现：空闲分区以容量递增的顺序排列，每次分配内存时顺序查找空闲分区表，找到第一个满足大小的空闲分区（该分区一定是能够满足其要求，但又最小的空闲分区）

3.缺点：

①将会产生很多的外部碎片（每次都选最小的分区分配，但是最小的内存可能和该程序仍仍然有小部分差距

②算法开销大：回收分区后，可能会导致分区的重新排列（由回收分区的合并引起）

1.5.3.最坏适应算法（Worst Fit）：容量递减排列

1.算法思想：为了解决最佳适应算法问题（留下很多的外部碎片），优先使用更大的内存空间（与最佳适应算法相反）

2.实现：空闲分区按容量递减的顺序排列，每次分配内存时顺序查找空闲分区表，找到第一个满足大小的空闲分区（该方法中第一个空闲分区一般都能满足要求，若该分区满足不了要求，其余分区则都满足不了要求） （可能会导致重新排列：）

3.缺点：

①每次都都使用最大的分区装入进程，则可能出现大进程来时，最大的分区满足不了要求的情况（即没有大进程可用）

②算法开销大：回收分区后，可能会导致分区的重新排列（由回收分区的合并引起）

1.5.4.临近适应算法（Next Fit）：地址递增排列

1.算法思想：从上次查找结束的位置开始检索（首次算法的改进，能够有效减少检索带来的开销）

2.实现：空闲分区按地址递增的顺序排列，每次分配内存时从上次查找结束的位置开始查找，找到第一个满足大小的空闲分区

3.缺点：可能会增加大地址被小程序使用的可能性，进而导致当大程序到来时，无大地址可用