内存管理概念

内存基础

内存的定义和作用

其实我们在前面学习进程时已经经常提到了内存的部分知识，我们知道一个进程在上cpu之前需要现在内存中处于就绪态，上cpu后进程实体的PCB,数据段，代码段大部分都处于内存中方便随时和cpu进行信息交换。所以内存可存放数据，程序执行前需要先放到内存中才能被cpu处理----所以cpu的功能是缓和cpu与硬盘之间的速度矛盾。

思考：内存如何区分多个程序的数据存储地？

我们知道在多道程序环境下，系统中会有多个程序并发执行，也就是说会有多个程序的数据需要同时放在内存中，那么如何区分每一个数据段是属于哪个程序的呢？实际上内存会分为许多部分，有一个一个小房间，每一个小房间就是一个“存储单元”，内存地址从0开始，每个地址对应一个存储单元。

1. 如果计算机“按字节编址”，则每个存储单元为1字节（1Byte)，即1B，即8个二进制位。
2. 如果字长为16位的计算机“按字编址”，则每个存储单元为1个字，每个字的大小为16个二进制位，所以一个字=两个字节。

补充：常用的数量单位与换算

$$1KB(1K)=2^{10}Byte$$

$$1MB(1M)=2^{20}Byte$$

$$1GB(1G)=2^{30}Byte$$

所以我们知道换算进制为2^10也就是1024Btye,所以1K实际上已经非常大了。

思考：4GB内存是什么意思？

一台手机/电脑的内存为4GB，是什么意思。我们按照上面的公式计算，4GB=4*2^30Byte,如果内存是按照字节编址的，那么也就是会有2^2*2^30=2^32个房间，又因为是从0开始编号，所以房间编号为0~2^32-1。所以需要2^32个地址一一标识这些房间，所以需要32个二进制位来表示。

指令的工作原理

我们思考现在要对x=x+1指令语句进行执行，具体过程如下图：

首先高级指令x=x+1翻译成处理机可以看懂的二进制指令串（可能一个高级指令会对应多条二进制指令），然后cpu执行这个二进制指令串。

我们从上面可以看到cpu根据二进制指令找到010011111处的数据进行取出到寄存器中，然后+1操作，在返还该值到地址处，这样就完成了一个读写操作将x+1。可见，我们写的代码要翻译成CPU能识别的指令，这些指令会告诉CPU应该去内存中的那个地址读/写数据，这个数据应该做什么样的处理。在这个例子中，我们默认这个进程的相关内容从地址#0开始连续存放，指令中的地址参数直接给出了变量x的实际存放地址（物理地址）。

思考：如果进程不是从地址#0开始存放的会影响正常执行吗？

比如如下面这个案例，我们现在将79处的存储单元写入10然后再将79处的数据读入到寄存器3中，如果进程是从#0开始存放数据的，那么确实可以正常执行：

从上面的图中我们也可以看出程序经过编译，链接后生成的指令中指明的是逻辑地址即相对地址，即相对于进程其实地址而言的地址，如上图中实际上指令中的地址为79处并不是指的物理地址79处，而是相对于进程起始处79处的地址，只不过是刚好此时进程是从地址为#0开始存储的，所以逻辑地址处的79就是映射的物理地址的79处。所以可以正常运行。（为了简化理解，本次我们都默认操作系统为进程分配的是一片连续的内存空间）。

但是实际上情况不可能总是如此的理想。如下图：

我们如果默认逻辑地址就是物理地址的话，此时上面的过程就会出现重大错误。因为此时指令0和1值的还是逻辑地址处的79，但是此时这个进程并不是放到内存中的#0地址开始毕竟内存中会存入许多进程（并发性导致许多进城会在内存中存储随时准备就绪上cpu)，所以此时指令0和1处的所说的的逻辑地址79处实际上是相对于此时起始地址#100开始后面的79个存储单元即绝对地址179处的数据，但是如果我们仅仅是按照逻辑地址==绝对地址执行的话，那么此时就会映射到其他进程的数据段（物理地址79处）这明显是不对的，所以我们在装入模块（可执行文件）进入内存时（这是高级调度/作业调度）需要对地址进行转换以达到在执行指令时读/写数据的地址正确，此时我们需要某些策略来使得指令中的逻辑地址转换为正确的物理地址。

思考：如何将指令中的逻辑地址转换为物理地址？

1. 策略1：绝对装入
2. 策略2：可重定位装入（静态重定位）
3. 策略3：动态运行时装入（动态重定位）

模块装入的三种方式

绝对装入

在编译时，如果知道程序将放到内存中的那个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存。比如上面那道题我们在装入模块到内存之前知道将要在内存地址为100的地方开始存放。

那么此时在对文件进行编译，链接后指令中不在使用逻辑地址，而是直接转换为物理地址如上图，此时在将装入模块（可执行文件）放入内存中，当处理机执行到指令0和指令1时就会到正确的存储单元（物理地址为179）读/写数据。如下图：

虽然没有什么大问题，但是绝对装入只适用于单道程序环境。程序中使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。通常情况下都是编译或汇编时在转换为绝对地址。

思考：为什么只使用于单道程序环境？

很简单，因为在装入模块进入内存后指令一直是不变的物理地址，但是我们知道在多道程序环境中进程是并发异步执行的，不可能一直存储于内存的一个固定地方，但是一旦装入模块变换了存储地址那么初始地址就也改变了，那么此时很显然此时装入模块中的地址就又出现指向错误了，而且如果绝对装入只能适用于单道环境程序，显然也不满足进程并发执行和内存建立的初衷，所以这种方法缺陷较大，有待改进。

可重定位装入（静态重定位）

静态重定位（可重定位装入），顾名思义肯定是能够弥补上面绝对装入的缺陷，具体做法是编译，链接后的装入模块的地址还是从0开始的，但是指令中使用的地址，数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块放入内存的适当位置。装入时进行重定位，将逻辑地址变换为物理地址（地址变换是在装入时一次完成）。

我们从上图可以看到，他是在装入时对于逻辑地址进行了+100的处理，这样当再次进入内存分配到内存的其他地方时也可以随时更新为正确的地址，不像绝对装入那样直接改变为绝对地址当再次进入内存就有可能出现错误。

思考：还有没有什么可以改进的地方？

我们对比一下绝对装入和静态可重定位装入两者的区别。

但是我们发现静态重定位的特点是一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，作业就不能装入该内存并且最大缺陷是作业一旦进入内存后，在运行期间就不能在移动，也不能再申请内存空间。所以我们好需要解决在内存运行期间移动的问题。

动态运行时装入（动态重定位）

动态重定位：编译，链接的装入模块的地址还是从0开始的，装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方法需要一个重定位寄存器的支持。

装入时：

执行时：

我们看出动态重定位满足所有要求是最好的策略。动态重定位在满足程序在内存中移动的同时，还可以将程序分配到不连续的存储区，所以他区别于静态重定位不需要一次性申请所有连续的地址空间并且每次都只需要取出部分代码执行，如果需要映射地址则通过重定位寄存器可以随时指向正确的存储单元（都不需要连续存储了），简直是太棒了。并且由于是重定位寄存器更改映射地址所以可以向用户提供一个比存储空间大得多的地址空间（虚拟性）。

思考：总结三种策略的异同点？

我们从以下几个角度区分这三个策略：

1. 装入模块起始地址：绝对装入策略装入模块中的起始地址未必是0，但是静态重定位和动态重定位一定是0
2. 逻辑地址->物理地址转换时期：绝对装入策略中是在编译，链接后即将逻辑地址转换为物理地址，静态重定位是在装入内存时，而动态重定位是在执行时借助重定位寄存器转换。总的来说，只有动态重定位是在内存中还保存逻辑地址。
3. 借助外界手段：只有动态重定位需要一个辅助的重定位寄存器，静态重定位不需要。
4. 装入的地址要求：绝对装入和静态重定位都需要一次性申请一片连续的容量够大的地址空间，而动态重定位可以离散装入。

思考：链接编译到底是什么？

我们知道在一个程序从写到运行一次需要经过以下几个过程：

编译就是将用户源代码编译成若干个目标模块（编译就是把高级语言翻译为机器语言），而链接程序将编译后形成的一组目标模块，以及所需要的的库函数链接在一起，形成一个完整的装入模块，装入是由装入程序将装入模块装入内存运行。所以链接很重要，他是形成一个模块的关键步骤，这里面有3中链接方式。

链接的三种方式

静态链接

静态链接就是在程序运行之前先将各目标模块及它们所需要的库函数连接成一个完整的可执行文件（装入模块），之后不再拆开。如下图：

没啥大问题，但是这样就必须一次性申请一片连续的存储地址貌似难以实现因为内存中会造成许多内存碎片。而且准备工作时间很长，没有链接成一个完整的模块之前不能进入内存执行。

装入时动态链接

将各目标模块装入内存时，边装入边链接的一种链接方式，如下图：

这样即使还没有完成全部链接，但是前面的部分模块已经可以进入内存，准备工作时间明显缩短。

运行时动态链接

在程序执行中需要该目标模块时，才对他进行链接。如下图：

不但占用内存空间小，准备时间短，而且便于修改和更新，便于实现对目标模块的共享。

思考：怎么就便于实现目标模块的共享了？

我们思考有两个程序现在都有一个调用打印机I/O设备的代码段，那么对于运行时动态链接的好处是不需要写两份了，谁需要谁就链接这部分模块，加大了模块的可重复利用率，这也是组件化思想的体现。

总结

基本上全是重点和易错点

内存管理

回顾前面所讲的知识，我们主要着重于对装入模块装入内存前和装入内存时的问题如正确的地址转换，链接方式等，那么接下里来我们在讨论一下对于内存中运行时对于各进程的管理。

内存空间的分配与回收

操作系统作为系统资源的管理者，当然也需要对内存进行管理，要管些什么？首先对于内存空间的分配和回收的任务必不可少。如下：

这些问题都会涉及到许多后续问题所以有不同的算法策略，后面我们将详细讲到。

内存空间的扩展

我们前面也讲过操作系统的虚拟性，实际上就是用过逻辑地址和物理地址的映射以及内外存切换装入等方式实现的，从而能够在有限大小的内存空间中虚拟出远大于物理空间大小的内存空间。所以操作系统需要提供某种技术从逻辑上对内存空间进行扩展。

地址转换

为了使变成更方便，程序猿写程序时应该只需要关注指令、数据的逻辑地址，而逻辑地址到物理地址的转换（这个过程称为地址重定位就是之前讲的三种装入策略）应该由操作系统负责，这样就保证了程序猿写程序时不需要关注物理内存的实际情况。类似的还有刚学写管程概念，也是为了更加方便于程序猿只集中于程序的编写而提出的。所以对于三种装入方式，我们可以看出只有动态重定位是现代操作系统才拥有的，毕竟其他两种方式还需要程序猿关注地址转换为体以防止出错。

内存保护

同时操作系统还需要提供内存保护功能，保证各进程在各自存储空间内运行，互不干扰。这里有两种策略：

策略1:

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

所以可以看出上、下限寄存器存储的是物理地址。

策略2

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

所以管理判断是否越界的是界地址寄存器，并且策略2是根据逻辑地址进行越界检查的，而策略1是根据物理地址进行越界检查的。

总结

覆盖与交换

这里我们讲的覆盖与交换技术不用想肯定是内存空间扩充的技术来实现操作系统的虚拟性，扩大内存空间大小。

覆盖技术

在早期的计算机内存很小，也没有操作系统所以无虚拟性的概念，即就是逻辑地址==物理地址的情况，那么比如IBM推出的第一台PC机最大只支持1MB大小的内存，那么就真的只是1MB了，所以会经常出现内存大小不够的情况出现（比如一个文件为20MB，那么放都放不进去更谈何运行）。所以后来提出了覆盖技术来解决程序大小超过物理内存总和的问题。

覆盖技术的思想是将程序分为多个段（多个模块）。常用的段常驻内存，不常用的段在需要时再调入内存（很容易想到）。所以内存中相应的有一个“固定区”和多个“覆盖区”。需要常驻内存的段放在“固定区”，调入后就不再调出（除非运行结束），不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存。如下：

main函数部分在固定区，而BCDEF在覆盖区，这种覆盖技术确实解决了问题，但是必须由程序猿声明覆盖结构，操作系统完成自动覆盖。所以缺点是对用户不透明，增加了用户编程负担。覆盖技术只用于早期的操作系统，现在已经成为历史。并且我们发现还有一个小细节操作系统还可以做到让不能同时被访问的程序段共享同一个覆盖区，这样也做到了一定的减少占用内存空间的作用。

交换技术

交换技术（对换技术）的设计思路是当内存空间紧张时，系统将内存中某些进程暂时换出内存，把外存中某些亿具备运行条件的进程换入内存（进程在内存与磁盘间动态调度，这也是绝对装入方式易出错的地方）。

这里面的进程挂起和就绪运行的状态切换涉及的是中级调度（内存调度），就是决定将那个处于挂起状态的进程重新调入内存。

所以暂时被换出到外存等待的进程为挂起状态（suspend),挂起态又可细分为就绪挂起和阻塞挂起两种状态，这就不得不再提一下状态经典三角切换模型。

思考：交换技术应该将挂起的进程放在外存（磁盘）的什么位置？

具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式（空间碎片少）。

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

思考：什么时候应该交换？

交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如：在发现许多进程运行时经常发生缺页（后面会讲）就说明内存紧张，此时就可以换出一些进程，如果缺页率明显下降了，那么就可以暂停换出了。

思考：换出时应该换出那些进程？

可优先换出阻塞进程（毕竟在哪都是等😉），可优先换出优先级低的进程，为了防止优先级低的进程在被调入内存后很快又被换出，有的系统会考虑进程在内存的驻留时间来决定换出哪个进程。但是一定要注意PCB是一定不会被换出的，他是常驻内存的。

总结

一定要注意覆盖技术和交换技术的区别在于角度不同，覆盖技术着眼于一个程序或进程，而交换技术是着眼于全局多个进程之间的关系，所以覆盖技术与交换技术互相配合最大限度的对内存空间进行扩展。