引言
花了一段时间才把之前的笔记整理了一部分，平时太忙也没啥时间。今天开始整理内存管理部分的，内存管理部分大致分为三部分笔记，第一部分就是本篇内存管理基础，第二部分是虚拟内存，第三部分高速缓存。
一个程序在运行前，只是一个存储在磁盘上的可执行的二进制文件，包括可执行指令和数据。当程序运行时，这个二进制文件会被加载到内存中，指令和数据在执行时会被cpu从内存中加载到寄存器中，然后执行，可能会把执行结果再次存入内存中。数据以何种形式存在内存，如果为进程分配内存，进程退出如何回收，这个过程叫内存管理，接下来就详细介绍这个过程
早期无存储器抽象
无存储器抽象内存访问
用户程序直接操作物理内存的地址，比如将位置为1000的物理内存中的内容复制到REGISTER1
1 | MOV REGISTER1,1000 |
物理内存模型
a模型早期的主机和微机，很少使用
b模型多用于嵌入式系统
c模型早期用于个人计算机
a、c模型有一个bug，用户程序可能擦除操作系统内存，如果是这种无抽象的物理内存，同一时间只能运行一个进程。
多个程序运行-物理分块内存
原理：内存被分块例如2kb一个块，在CPU内部有特殊寄存器来记录内存块的保护key，当程序运行时，会有一个PSW与寄存器中的对应，当不属于该内存块的程序访问时，PSW和寄存器中存的key将不一致，避免了程序访问别的程序的内存。简要示意图如下
存在问题
因为程序还是利用绝对路径访问内存，所以存在不同应用程序访问同一个内存块的问题，导致程序崩溃，下图的a和b加载到内存后内存结构为c，但是a的第一句跳转到24是没问题，但是b第一句跳转到28，但是内存地址28是程序a的。
IBM解决方案：静态重定位
当加载b程序到16384时，所有访问地址都加上16384，比如JMP 28变成了JMP 16412，但是该方法不是一个通用的解决办法。此外，还需要程序提供额外的信息来标识哪些是地址。
存储抽象-地址空间
前边已经知道了无存储抽象，也就是直接使用物理内存的两个缺点
- 哪怕只有一个应用程序运行，操作系统内存也可能会被偶然或恶意破坏
- 多应用程序并发运行困难
地址空间概念
概念：地址空间并不局限于存储，它是一个抽象的概念，电话号码是一个地址空间，ip也是，域名也是
基地址和界限寄存器（动态重定位）
使用基地址和界限寄存器时内存中进程的内存结构
cpu访问内存时，硬件会利用要访问的地址+base，然后判断是否大于base+limit的地址，如果大于那么访问就是越界的，产生错误并终止访问。
Swapping
如果内存足够大到可以容纳所有进程的代码和数据，那么地址空间加上硬件提供的动态重定位的方案或许已经可行，但是通常所有进程需要的内存超过存储可以提供的范围。
标准Swapping
原理：标准Swapping是通过换进程来重复利用内存空间，如下图首先内存只有A进程，接着B、C进程被创建或者换入内存，紧接着D进程需要运行，A被换出；当A再次被调度时，将B换出给A腾空间，A再次进入内存。
但是A再次进入内存的时候，地址空间已经发生变化。所以，Swapping换入之后需要重新重定位，有两种方式：
- 通过软件在载入的时候重定位
- 通过硬件在运行的时候重定位（比较常用），基地址和界限寄存器就适用这种情况
内存压缩
内存因为进程的换入换出会产生一些内存空洞，这些内存空洞会导致内存浪费，因为这些空洞连续内存空间大小不足以容纳一个进程所需的空间。因此通过将所有进程占用的空间全部向下移动，就有可能将小的空洞连成一大块空闲内存。这种技术就叫内存压缩
进程内存大小分配问题
- 固定大小，如果进程大小是固定不会改变，操作系统只需简单分配进程需要的大小
- 数据段可能增长，此时有四种解决方法
- 如果进程邻近有空闲内存，分配给进程
- 如果进程邻近是其他进程，那么寻找一块更大的空闲内存，将进程迁移过去
- 如果没有更大的空闲内存，那么尝试将邻近的进程交换出去
- 如果进程无法增长内存并且交换区已经满了，那就挂起该进程直到有空闲内存（或者kill该进程）
为了提高内存分配的效率，满足大部分进程内存都会增长的场景。(a)系统在分配内存时为进程预留增长所需的空间；(b)如果进程有连个可增长的段，比如数据段和栈段，可以数据段从下往上分配，栈从上往下分配，如果内存不足时再增长内存。
页面Swapping
针对虚拟内存的，在下一部分详细介绍
空闲内存管理
Bitmaps
原理：将内存分块成小的分配单元(可以是小到几个字或者大到几kb)，然后用一个bitmap来记录哪些块已被使用，1代表使用，0代表空闲
关键：内存单元大小的选择很关键，太小，bitmap太大，太大，会浪费有些空间
缺点：当需要为进程分配内存时，内存管理系统需要遍历bitmap找出一段连续的空间，这个操作是很费时的
空闲链表
原理：用链表将以使用和未使用的内存连接起来，每个节点说明该节点是空闲的(H)还是已经使用(P)，以及内存的起始位置和长度。
例子，X代表要释放的进程，阴影部分代表空闲
- a中x释放后，空闲链表P替换为H，该空间空闲
- b和c的X释放后，两个相邻的空闲区域合并成一个区域，链表变短
- d中X释放后三个链表节点合并成一个
连续内存分配算法
截止目前我们讨论的内存都是将内存作为连续内存为基础的，连续内存指的是我们分配给进程的内存在空间上是连续的，在下一部分中会介绍虚拟内存，将会看到，进程是可以被分配不连续的内存。拿上边图中的空闲链表做例子
首次适配算法(first fit)
内存管理器沿着链表搜索，直到找到一块足够大的空闲内存，假设现在要分配的内存为2，该算法将扫描链表，然后选择编号2的空闲块
下次适配算法(next fit)
和首次适配算法类似，只是搜索起始位置不同，首次适配算法是从头开始，而下次适配算法是从上一次分配的位置开始
最佳适配算法(best fit)
最佳适配算法从头开始搜索到结尾，找出最小的能容纳进程的空闲块，比首次适配算法慢。假设分配内存为2，则扫描全表发现编号5的空闲块最适合
最差适配算法
每次搜索最大的空闲内存块，来减少内存碎片，扫描全表，发现编号2的空闲块最大
快速适配算法
为常用分配内存大小建立不同的项，分项存储。和所有按空闲内存大小排序的算法一样，当进程内存释放或者换出时，查找相邻块判断是否可以合并是非常耗时的。
总结
上述总结了通过无存储器抽象到利用地址空间的抽象一步步解决从单进程到多进程问题、从进程需要小内存到内存无法容纳进程的问题。虽然现代计算机有更高级的虚拟内存技术，学习一个技术很好的方式是了解其发展历史，了解了历史，对理解一个技术的诞生有很好的帮助，因为可以知道为什么需要这个技术以及它解决的问题。在下一篇中将介绍虚拟内存技术。