内存管理

存储器的抽象—地址空间

物理地址直接暴露给进程带来几个严重的问题

1. 假如用户程序可以寻址内存的每一个字节，它们就可以很容易的破坏操作系统
2. 并行多个程序成为困难，程序访问相同的地址会造成彼此数据的破坏

地址空间

地址空间是一个进程可用于寻址内存的一套地址集合，每一个进程都有一个自己的地址空间，并且这个地址空间独立于其他进程的地址空间。

基址寄存器和界限寄存器

基址寄存器和界限寄存器是操作系统给每个CPU配置的两个特殊硬件寄存器，基址寄存器保存进程的起始物理地址，界限寄存器保存进程可用的进程长度。

动态重定位: 使用基址寄存器和界限寄存器将每个进程的地址空间映射到物理内存的不同部分

比如一个16K的程序被装载到内存，基址寄存器会记录程序的起始地址0, 界限寄存器记录内存边界16384. 那么第二个16KB的程序就会被装载到16384 -> 32768，当第二个程序要执行JMP 28时，内存地址会跳转到16412（加上基址地址）

地址交换技术

一个进程需要的内存空间不可控，把所有进程都保存内存中，可能导致内存超载（容量不够），因此可以通过两种方式解决，一种是交换，另一种是虚拟内存，这里简单介绍交换的策略。

地址交换技术，即把一个进程完整调入内存，是该进程运行一段时间，然后把它存回磁盘，释放内存地址，供其他进程使用。若该进程被唤醒，则重新分配所需内存，此时可能不是之前的内存地址，可以通过基址寄存器和界限寄存器，在程序执行中进行必要的转换

空闲内存管理

1. 使用位图的存储管理
   • 内存被划分为多个分配单元。每个分配单元小到几个字节，大到几千字节
   • 位图使用0表示一个空闲的分配单元，1表示占用，在内存分配时，可以根据实际需要内存大小，在位图中寻找连续k个0的分配单元进行分配，其中k表示所需内存大小/分配单元
2. 使用链表的存储管理

虚拟内存

虚拟内存的基本思想是：每一个程序拥有自己的地址空间，这个空间被分成多个块，每个块被称作页或页面。每个页有连续的地址范围。这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序引用到的一部分在物理内存中的地址空间时，由硬件立即执行必要的映射，当程序引用到的一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。

分页

使用虚拟内存前: 程序产生的地址（如 MOV REG, 1000, 地址将由基址寄存器值 + 偏移量1000)，产生的地址直接送到内存总线，读写操作该地址的物理内存，即为物理地址

使用虚拟内存后: 上述产生的地址（此时称为虚拟地址)将被送到内存管理单元MMU，由MMU把虚拟地址映射为物理地址。

MMU对虚拟地址的映射

内存管理单元MMU: 用于记录虚拟地址页到物理地址页框的映射。页和页框的大小是相同的。这里我们以页和页框大小均为4KB为例(linux一般为4KB)，假设系统物理内存只有32KB，但程序所需内存为64KB。因此：

1. 虚拟页面个数为 64 / 4 = 16个
2. 物理页框个数为 32 / 4 = 8个

那这个64KB(16个页面)的程序，如何映射到32KB(8个页框)的物理内存中呢？首先需明确这64KB的数据都在磁盘上，之后页面的加载和替换都是物理内存和磁盘的数据交互

MMU管理虚拟页面序号和物理页框序号之间的映射

1. 如果需要操作的虚拟内存地址所在的页号为4，如果页号4存在物理地址的映射，则MMU会将虚拟内存地址，直接转换成物理内存地址，并访问数据
2. 如果页号4没有映射，则使CPU陷入操作系统(叫做缺页中断)
3. 操作系统找到一个最少使用的页框并把它的内容写入磁盘，随后将要访问的页(刚刚说的4)的数据读到刚才回收的页框中，修改MMU映射关系，然后重新启动引起缺页中断的指令

关于页的补充

1. 虚拟地址的组成，虚拟地址由x。如单页大小4KB(12位)，页数16（需要4位），因此，虚拟地址可以是16位，即前4位表示页号，后12位表示偏移量。

页表

页表是虚拟页和物理页框的映射，每一个映射关系（即每条映射记录），以页号作为索引，加上一些控制位（下面讨论），再加上页框号。

页表的结构

一个常用的32位的页表

1. 页号，页表的索引，表示虚拟页面序号
2. 页框号，记录该虚拟页面的物理内存页框号
3. 在/不在位，指出当前页表映射是否生效。
4. 保护位指出一个页允许什么类型的访问。
5. 修改位指出该页是否被修改。在发生缺页中断是，通过修改位判断是否需要将物理页框中的内容刷新到磁盘。如果已修改则需要写入磁盘，未修改可以直接丢弃
6. 访问位指出该页被访问的时机。(不一定是时间，但是可以通过访问位的值判断在缺页中断时需要被淘汰的页面)

MMU使用页表进行映射

MMU拿到虚拟地址后，通过前四位获取了页号，之后:

1. 假如页表中此页号对应记录的在/不在位为1，即已存在，那么MMU会取出这条页表记录中的页框号（因为预设的内存只有32KB，因此页框号只用3个比特位表示即可），此页框号作为高3位，加上虚拟地址中低12位，组成一个15位的物理地址，即是真实内存的物理地址，随及提交内存总线，进行内存数据读写
2. 假如页表中此页号对应记录的在/不在位为0，表示暂时无映射关系，此时，发起缺页中断，加载新页（如上所述），进行虚拟地址到物理地址的转换

加速分页过程

两个主要问题：

• 虚拟地址到物理地址的映射要非常快
• 虚拟地址的空间很大，页表也会很大
  • 假设一个需要4GB内存的进程，页大小为4KB，需要的页表项数为 4GB/4KB = 1M，约100万页

两个极端的方法：

• 一个极端：将页表完全映射到寄存器。即进程启动时，将页表数据载入寄存器中，那么CPU每次访问页表数据直接在寄存器获取，速度极快，但是需要大量的寄存器空间
• 另一个极端：页面仍然在内存中，寄存器存储页表在内存中的地址，那么可以节约寄存器大小，但是每次地址映射都需要从内存中读取页表数据，这个速度相对就很慢

转换检测缓冲区（TLB）

TLB是计算机设置的一个小型硬件设备，将虚拟地址（部分）直接映射到物理地址，而不必再访问页表，也称相联存储器或者快表

（个人理解它就是在CPU和内存页表之间再加一层缓存，对于常用的页表项，可以直接从TLB中快速查到，而不用再次访问内存。这也是TLB建立的假设基础: 只有很少的页表项会被反复读取，而其他页表项很少被访问）

1. TLB的原理
   • 在MMU中设置TLB，包含少量的表项（通常不会高于256）
   • 当虚拟地址进入MMU后，硬件首先将虚拟页号和TLB中所有表项进行匹配
     • 如果找到匹配，则直接返回页框号，不再访问内存页表
     • 如果未找到匹配，则需要进入内存查找页表，并在TLB中淘汰一个表项，更新为刚刚读取的表项

TLB 解决上述问题1

多级页表和倒序排表

1. 多级页表

   • 避免把全部页都加载进内存（因为可能很多一部分页是访问不到的）

2. 倒排分表

关于页表的补充

1. 页表在进程间是隔离的。每个进程都需要自己的页面，因为进程拥有自己的虚拟空间

页面置换算法

1. 最优页面置换算法
   • 理论上的最优算法，现实无法实现。记录每一个页面将在多少条指令后被再次调用（预测未来，无法实现的原因），数值越大（表示越往后才能被用到）越先被淘汰。
2. 最近未使用页面置换算法(NRU)
   • 通过两个状态位(R，读写位；M，修改位)记录当前页的使用状态，R和M在初始化时均是0，R位被定期（比如每次时钟中断）置0，当发生缺页中断时可以根据这两个状态位的优先级进行置换
3. 先进先出页面置换算法
   • 操作系统维护当前内存中页面的链表，最新进入放在表尾，最早进入放在表头，发生缺页中断时淘汰表头
4. 第二次机会页面置换算法
   • 优化FIFO，如果发现表头的R位为1，表示最近的时钟周期被使用，则先不淘汰它，将其R位置零，放到表尾，在查看下一个表头页面，以此类推
5. 时钟页面置换算法
   • 将上述链表改成时钟链表（首尾相接循环），并记录一个表指针表示最老页面，使用第二次机会算法的方式进行淘汰，可以避免在链表中移动页面
6. 最近最少使用页面置换算法(LRU）
   • 置换未使用时间最长的页面

其他问题

栈内存和堆内存

1. 栈内存: 由系统自动申请和释放，用于存放函数参数、局部变量等，操作方式类似数据结构栈
   • 操作系统负责申请和释放
   • 空间较小
   • 存放函数参数、局部变量、寄存器内容等
2. 堆内存: 由程序员分配和释放，数据结构是链表，
   • 必须由开发人员申请和释放
   • 空间较大
   • 存放程序员控制的内容