内存管理
程序中物理地址和逻辑地址之间的关系确定
一个程序从编辑完成到运行这个过程中，经过了编译、链接、装入这几个过程
编译：由编译程序将用户源代码编译成若干个目标模块
链接：由链接程序将编译后形成的一组目标模块、以及需要的函数库链接在一起，形成一个完整的装入模块
装入(装载)：由装入程序将装入模块装入内存运行
在装入过程中，一共由三种装入方式
装入
绝对装入
在编译时，如果知道程序将会放置到内存中的哪一个位置，编译程序将产生具有物理地址的目标代码，装入程序按照装入模块的地址，将程序和数据装入内存。
这种装入方式只适用于单道程序环境
静态重定位
编译后的程序中，使用的是逻辑地址，在装入时对地址进行“重定位”，将逻辑地址变换为物理地址。
静态重定位的特点是在装入一个程序时，必须分配其所需要的全部内存空间，如果没有足够内存，就无法装入作业，而且，在作业装入到内存之后，运行期间无法移动，也不能申请内存空间
这种方式用于早期的多道批处理操作系统
动态重定位
装入之前的步骤和静态重定位一样，区别就是在装入内存时，并不会立刻把逻辑地址转换成物理地址，而是把地址转换推迟到程序真正执行的时候才进行，因此装入内存后，所有的地址仍然是逻辑地址。这种方式需要一个重定位寄存器的支持
采用动态重定位时允许程序在内存中移动，并且还能将程序分配到不连续的存储空间中；在程序运行过程中只需要装入部分代码即可运行，然后在程序运行期间，根据需要动态申请分配内存；便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间
这种方式应用于现代操作系统
链接
静态链接
在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件，之后不再拆开
装入时动态链接
将各目标装入内存时，边装入边链接的链接方式
运行时动态链接
在程序执行中需要该目标模块时，才对它进行链接，其优点是便于修改和更新，便于实现对目标模块的共享。
内存空间的分配和回收
下面讲到的连续分配和非连续分配指的是进程分配到的内存空间是否连续
连续分配管理方式
单一连续分配
系统被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据。用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间
优点：实现简单，无外部碎片。
缺点：只能用于单用户、单任务的操作系统中。由内部碎片，存储器利用率低
固定分区分配
操作系统需要建立分区说明表，来实现各个分区的分配与回收
/固定分区分配.png)
分区大小相等
缺点：缺乏灵活性
分区大小不相等
优点：增加灵活性，可以满足不同大小的进程需求
注：固定分区分配都会产生内部碎片。
动态分区分配
动态分区分配根据进程需要的内存大小进行动态的分配。
要实现该技术必须解决以下几个问题：
1、操作系统该使用什么数据结构来记录内存的使用情况？
2、当有多个分区满足需求时，应该选择哪个分区进行分配
3、如何进行分区的分配与回收操作？
解决：
1、一般采用空闲分区表或者空闲分区链
空闲分区表和上面固定分配方法中的分区说明表类似，以数组的方式存放每个分区的大小、起始地址和使用情况等信息
空闲分区链是以双向链表的形式，把每个空闲的内存块给连接起来
2、当有多个分区满足需求时，这里就引出了下面四种动态分区分配算法
1、首次适应算法：每次从低地址开始查找，找到第一个能满足大小的空闲分区
2、最佳适应算法：将空闲分区表中的内存大小按照从小到大进行排序，从小到大查找，找到第一个符合要求的空闲分区，这个算法会优先把符合要求的最小内存块使用掉，尽可能剩下大的内存空间。缺点就是会产生许多外碎片
3、最坏适应算法：该算法的思想和最佳适应算法的思想截然相反，从最大的可用内存块开始进行分配。缺点就是如果遇到需要大内存空间的进程，没有足够的内存可以分配。
4、邻近适应算法：这个算法就是在首次适应方法上做了一点小小的修改，每次查找时，不是从低地址开始查找起，而是从上一次使用的内存位置开始查找。
/四种动态内存分配算法比较.png)
3、当根据分配算法分配好内存之后，只需要修改下分区表或者分区链中的内存块信息即可，回收时同理，更新下数据即可，当合并时发生分区连续的情况，将分区进行合并。
动态分区分配不会出现内碎片，但是会出现外碎片
内部碎片：分配给进程的内存有部分没有用上
外部碎片：内存中有部分区域由于太小而难以分配给进程使用
结合上面的装入过程，使用动态重定位的方法以及中级调度，可以把内存中进程移动到一块，可以解决外碎片的问题。
非连续分配管理方式
从上面的连续分配管理方式来看，都存在着各自的问题，固定内存分配方法会导致产生内部碎片，内存利用率低，动态分区分配会导致产生外部碎片，虽然可以通过移动内存块的方式来解决，但是移动内存块的开销也不小。
非连续分配管理中，为用户进程分配的内存是一些离散的内存空间，而不是连续的内存空间
基本分页存储管理
其思想就是把内存分成一个个相等的小分区，再按照分区大小把进程分割成一个个小部分
将空间分割成一个个的小块，每个小块就是一个“页帧”，也成为“内存块”，“物理块”，每个页帧有自己的编号，叫做块号，从0开始递增。
将用户进程的地址空间也分割成一个个与页帧大小相等的区域，称为“页”，每个页也有自己的页号，页号页式从0开始。
将页和页帧一个个对应起来，实现该技术最大的难点就是在于如何实现逻辑地址和物理地址的转换
逻辑地址和物理地址之间的转化需要经过下面几个计算步骤：
假设现在每个页面大小是4KB(2\^12B)，内存大小为4GB(2\^32B)，每个地址需要使用32个二进制位进行表示
给定逻辑地址为2，那么其二进制表示为0000…0000010，前面20位是页号，后面12位是页内偏移量
因此如果能够知道前20位(在这里是00000…000)这个逻辑页的起始物理地址，那么就能够知道逻辑地址2的物理地址(逻辑页的起始物理地址+页内偏移量)。
操作系统会为每个进程建立一张页表，页表会将页号和块号一一对应起来，操作系统知道页面的大小，因此可以根据逻辑地址，迅速判断出逻辑页号，查询页表后找到对应的块号，因此也能够知道该块号的起始地址(块号*块大小)，从而也就得到逻辑地址相对应的物理地址。
页表的结构类似与数组，下标是逻辑块号，其对应的值是物理块号。
上面的例子中，页号是20位，因此页表中每个值也是20位，在存放时每个值占据三个字节
所以，逻辑地址转换成物理地址的过程如下：
根据逻辑地址的块号是M，该进程页表在内存中的起始地址是X，则该逻辑块所对应的物理块在页表中的位置是X+3*M(这里的3是页表项每个值所占据的字节数)，找到该位置后，获取到逻辑块所对应的物理块号，即可算出其物理地址。
在计算机中，有专门的硬件负责处理逻辑地址到物理地址的转换，这个硬件是基本地址变换机构
通常会在系统中设置一个页表寄存器，存放页表在内存中的起始地址F和页表长度M，进程未执行时，页表的起始地址和页表长度放在PCB中，当进程被调用时，操作系统内核会把它们放置到页表寄存器中
从上面地址转换的过程中可以看到，每次要访问一个逻辑地址对应的单元，需要查询两次内存，第一次是去查询页表，第二次才查询到对应的物理地址的存储单元。能否仅通过一次内存查询就获取到对应的值呢，下面就有具有快表的地址变换机构。
快表(TLB)是一种访问速度比内存快很多的高速缓冲存储器，根据程序的局部性原理，把经常访问到的页面的物理地址保存起来，避免去内存中取。因此每次查询时，先会去查询快表，如果命中了，直接可以得到物理地址，如果没有命中，就只能先去访问内存，获取到对应的物理块号，保存至快表中，然后再去查询物理地址对应的值
单级页表存在的问题
还是以上面这个例子为例，4GB内存，页面大小为4KB，页表中一共需要2\^20项，每一项需要占据四个字节(本来是三个字节，为了方便计算这里以四个字节来算)，为了能迅速在页表中找到对应的块号，一般页表所存放的空间是连续的，这里一个进程就需要4MB的的连续内存空间，即1024个连续页块，此外，由程序局部性原理可以得知，进程在一段时间内只需访问几个页面即可，无需让整个页表常驻内存。
如何解决上面这两个问题：
1、连续内存空间的分配，可以仿照上面进程连续分配管理方式的方法，将页表进行分组，每一项为4B，每一个页块大小为4KB，因此可以每1K个页表项作为一组。再为页表建立一张目录表，称为页目录表。
2、第二个问题可以通过在页目录表中新增加一个字段，用于检测该页面是否加载至内存中，如果未加载，在查询到该内存位置时，产生一个内中断，把相应的块给调入到内存
基本分段存储管理
和分页式的思路基本一致，区别就是内存的大小不是固定的，还有，段表(对应于分页存储中的页表)保存的是段长和基址
/段式地址转换过程.png)
段页式存储管理
先分析下分段和分页方式的优缺点
| 优点 | 缺点 | |
|---|---|---|
| 分页管理 | 内存空间利用率高，不会产生外部碎片，只会有少量的内部碎片 | 不方便按照逻辑模块实现信息的共享和保护 |
| 分段管理 | 方便按照逻辑模块实现信息的共享和保护 | 如果段长过长，为其分配的连续空间会很不方便。另外，分段管理会产生外部碎片 |
段页式存储结合了两者的优点，先通过分段，然后每个分段内再进行分页，具体地址的转换过程如下。
/段页式地址转换过程.png)
内存空间的扩展
覆盖技术
将程序分为多个段(多个模块)，常用的段常驻内存，不常用的段在需要时调入内存。
内存中分为一个“固定区”和若干个“覆盖区”。常驻内存的段放在“固定区”，且在程序结束之前，不再把该区域调出内存。不常用的段放在“覆盖区”，需要时调入内存，用不到时调出内存。
/覆盖技术.png)
上图中，A模块会调用B或者C模块，B会调用D模块，C会调用E或者F模块，这里，可以把A段放置在固定区，由于B和C不会被同时调用，因此可以选择设置一个较大的覆盖区，D、E和F也不会被同时调用，因此再设置一个覆盖区。这样做的话，原本需要52K的内存空间，现在只需要30K就行了。
这种方式必须由程序员声明覆盖结构，操作系统完成自动覆盖，缺点是对用户不透明，增加了用户的编程负担。这种技术只用于早期的操作系统，现在不用了。
交换技术
当内存空间紧张时，把内存中的一些进程暂时换到外存中，把外存中某些已经具备运行条件的进程换入到内存。前面的处理机调度的中级调度就是使用到了交换技术。
交换技术的实现：
具有交换功能的操作系统中，通常会把磁盘分为文件区和对换区两部分，文件区用于存放文件，主要追求存储空间的利用率，因此对文件区的管理采用离散分配的方式；对换区只占用磁盘的一小部分，被换出的进程数据就存放在对换区，由于对换的速度直接影响系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式。总之，对换区的IO速度比文件区的更快
什么时候进行交换呢？
交换通常在许多进程运行且内存吃紧时进行。例如在运行时发现许多进程在运行时经常发生缺页，就说明此时的内存比较紧张，此时就可以换出一些进程。
注：这里换出换入时，进程的PCB仍然是会常驻内存的，不会被换出
虚拟内存技术
传统的内存管理方式，包括连续分配和非连续分配都存在如下问题，
一次性：作业必须一次性装入内存中才能开始运行，这会造成两个问题
- 如果作业很大时，不能全部装入内存，导致大作业无法运行;
- 当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能够运行，导致系统并发度下降。
驻留性：一旦作业被装入内存，就一直驻留在内存中，知道作业运行结束。而实际上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费内存空间
根据程序的局部性原理，在程序装入时，将程序中很快用到的部分装入内存，暂时用不到的放在外存，当运行时发现要访问的信息不在内存中，则操作系统把需要的信息调入到内存，然后继续执行程序。当内存不够时，由操作系统负责把内存中暂时用不到的信息换到外存。
根据上面这种方法，在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存。
虚拟内存有三个主要特征：
多次性：无需在作业运行时一次性装入内存，而是允许分成多次调入内存
对换性：在作业运行时无需常驻内存，允许在运行时调入调出
虚拟性:从逻辑上扩充了内存容量，使用户看到的内存容量，远大于实际容量
如何实现虚拟内存技术？
虚拟内存技术，因为允许作业多次调入调出，如果采用连续分配管理方式，很不方便实现，因此虚拟内存技术的实现建立在非连续分配管理方式之上(分页、分段、段页式)
根据这三个非连续分配管理方式，加上虚拟内存技术之后，衍生出了请求分页存储管理、请求分段存储管理、请求段页式存储管理，需要增加的功能就是请求调页功能(将缺失页调入到内存)和页面置换功能(将暂时用不到的信息换到外存)
请求分页存储管理
/基本分页存储页表和请求分页存储页表对比.png)
除了页表结构的变化，还需引入缺页中断机构
缺页中断机构负责内存块的调入调出。
当内存不足时，应该将哪个页面调到外存？这里就有以下五种页面置换算法
最佳置换算法(OPT)：每次选择淘汰的页面将是以后都不会用到的页面，或者是在最长时间内不再被访问的页面。但实际上，只有在进程执行过程中才能知道接下来会访问什么页面，操作系统无法做到预先判断页面访问序列。因此最佳置换算法是无法实现的。
先进先出置换算法(FIFO)：每次淘汰的页面是最先进入内存的页面。
最近最久未使用置换算法(LRU)：每次淘汰的页面是最近最久未使用的页面。可以通过在页表中新增加一个访问字段，记录自上次被访问以来的时间。该算法的实现需要硬件的支持，虽然算法性能好，但是开销大。
时钟置换算法(CLOCK)
为页表中的每一项新增一项访问位，并以链表的形式把所有的表项连接在一起形成循环链表。如果该页面访问过了，则把访问位设置为1，每次淘汰时，从链表头开始查找，如果访问位位1，则置为0，并继续往下查找，如果找到访问位位0的页面，将该页面当作淘汰位淘汰掉，如果全是1，则在全部置为0后，再从头再次查找。因此该算法每次选择淘汰时最多扫描两次。
改进的时钟置换算法
普通的时钟置换算法只考虑了页面是否被访问过。但是一个被淘汰的页面没有被修改过，那么该页面就无需写入到外存中。只有被修改且被淘汰的页面才需要写回外存
根据上面这个特点，可以选择优先淘汰没有被修改过的页面，通过在表项中新增一个修改位，修改位为0，则代表未修改过，修改位为1，则代表修改过。因此改进的时钟置换算法的淘汰过程如下：
1、页表项仍然是以循环链表的形式进行连接，查找(访问位,修改位)为(0,0)的页表项进行淘汰，这轮查找不修改访问位和修改位(淘汰最近没被访问且没被修改过的页面)
2、查找第一项(0,1)的页表项进行淘汰，并依次把访问位设置为0(淘汰最近没被访问过但是被修改过的页面)
3、查找第一项为(0,0)的页表项进行淘汰，这轮查找不修改访问位和修改位(淘汰最近被访问过但是没被修改过的页面)
4、查找第一项为(0,1)的页表项进行淘汰。(淘汰最近被访问且被修改过的页面)
/页面置换算法的对比.png)
请求分段存储管理
请求段页式存储管理
地址转换(地址重定位)
这里的地址转换的实现是通过上面的装入过程实现的
内存保护
方法一：在CPU中设置一对上、下限寄存器，用于存放进程的上下限地址，进程的指令要访问某个地址时，CPU检查是否越界
方法二：采用重定位寄存器(又称为基址寄存器)和界地址寄存器(又称限长寄存器)进行越界检查。重定位寄存器存放进程的起始物理地址，界地址寄存器中存放的时进程最大的逻辑地址。访问某个内存空间时，首先使用界地址寄存器判断是否访问空间是否越界，如果没有越界，将该地址加上重定位寄存器中的起始地址，得到其物理地址。
