内存管理

冯诺依曼体系中的存储：
主存：只有CPU可以直接访问的大型存储介质
二级存储：主存的扩展，提供大的非易失的存储容量，比如磁盘

存储结构：
存储系统通常根据其速度、成本和波动性进行分层组织
存储层次结构之间的移动可以是显式的，也可以是隐式的

背景

1. 内存由一个很大的字节数组组成，每个字节都有自己的地址。
   （1）CPU根据程序计数器的值从内存中获取指令。
   （2）这些指令可能导致额外的加载和存储（存储到特定的内存地址）。
2. 程序运行必须先加载到内存中（程序被放置在进程中）。
3. 输入队列：磁盘上等待被放入内存运行程序的进程的集合。
4. 每个进程都有分离的内存空间，其实现需要基地址寄存器（Base register）和界限地址寄存器（Limit register）
5. CPU访问一个地址，需要判断是否大于基地址，是否小于基地址+界限地址。

地址绑定

1. 通常，地址绑定可以发生在编译阶段、加载阶段和运行阶段。
   （1）编译阶段：如果在编译时就已知道进程将在内存中的驻留地址，那么就可以生成绝对地址。（适用于单道程序环境）
   （2）加载阶段：如果在编译时并不知道进程将驻留在何处，那么编译器就应生成可重定位地址，对这种情况，最后绑定会延迟到加载时才进行，
   （3）执行阶段：如果进程在执行时可以从一个内存段移到另一个内存段，那么绑定应延迟到执行时才进行。（最优）

逻辑地址和物理地址

1. 逻辑地址：由CPU生成，也可以称为虚拟地址。
2. 物理地址：内存单元中的实际地址。
3. 编译时和加载时的地址绑定方法生成相同的逻辑地址和物理地址，执行时的地址绑定方案生成不同的逻辑地址和物理地址。

内存管理单元（MMU）

1. 是一个硬件设备，将虚拟地址转换为物理地址。
2. 在MMU方案中，重定位寄存器（又称基地址寄存器）中的值在被发送到内存时被添加到用户进程产生的每个地址中，即用户进程所生成的地址在送交内存之前，都将加上重定位寄存器的值。

动态加载

1. 进程的大小受物理内存大小的限制，为了获得更好的内存空间利用率，使用动态加载。
2. 采用动态加载时，一个程序只有在调用时才会加载，所有程序都以可重定位加载格式保存在磁盘上。
3. 动态加载的优点是，只有一个程序被需要时，它才会被加载，当大多数代码用来处理异常情况时，这种方法很有用。
4. 动态加载不需要操作系统提供特别支持。

动态链接

1. 存根：是一小段代码，用来指出如何定位适当的内存驻留库程序，或者在程序不在内存时应如何加载库。
2. 动态链接需要操作系统的支持，需要操作系统检查所需程序是否在某个进程的内存空间内。

覆盖

1. 在内存中只保存那些在给定的时间需要的指令和数据。
   

交换（Swapping）

1. 可以将进程暂时从内存中交换到后备存储器，然后将其带回内存继续执行。
2. 交换策略被用于基于优先级的调度算法，如果高优先级的进程到达并需要服务，内存管理器可以换出低优先级的进程，以加载和执行高优先级的进程。

连续分配(Contiguous Allocation)

主存被分为两部分，操作系统与中断向量保存在低内存中，用户进程保存在高内存中。

1. 在连续内存分配中，每个进程都被包含在一个单独的连续内存中。

内存保护

1. 如何保护操作系统免受用户进程的影响，以及保护用户进程不受其他用户进程的影响
   （1）使用重定位寄存器，包含最小物理地址的值
   （2）使用界限地址寄存器，包含逻辑地址范围
   （3）每个逻辑地址必须小于界限地址寄存器
   （4）内存管理单元MMU通过在重定位寄存器添加值来动态映射逻辑地址（逻辑地址+基地址）
2. CPU产生逻辑地址，需先与界限地址寄存器进行比较，若小于界限地址寄存器则加上重定位寄存器中的基地址，来获得物理地址。

内存分配

1. 可变分区分配
   （1）孔：可用的内存快，不同大小的孔分散在整个内存中
   （2）当一个进程需要被分配内存空间时，从一个足够大的孔中分配内存来容纳这个进程
   （3）操作系统维护已分配的分区信息和空闲分区信息
2. 动态分配问题——如何从一组空闲的孔中满足一个大小为N的请求
   （1）首次适应：分配第一个足够大的孔
   （2）最佳适应：分配最小的足够大的孔
   （3）最差适应：分配最大的孔
   （4）在速度和存储利用率方面，首次适应和最佳适应优于最差适应
3. 碎片
   （1）外部碎片：进程外部无法分配给进程的空间
   （2）内部碎片：已经分配给进程，但是进程不能使用（进程所分配的内存可能比所需的要大）
   （3）通过紧缩（compaction）来减少外部碎片：将所有空闲内存放在一个大块中。（只有重定位是动态地，并且在运行时进行的，才可以采用紧缩）

分页（Paging）

分页允许进程的物理地址空间是非连续的

1. 将物理内存分为固定大小的块，称为帧
2. 将逻辑内存分为固定大小的块，称为页

地址转换方案

1. CPU产生的地址被分为页码和页偏移
2. 页码作为页表的索引（页表包含每页所在的物理内存的基地址，可以通过页码查物理内存基地址，基地址与页偏移的组合形成了物理内存地址）
   
3. 如果逻辑地址空间为2^m，且页大小为2ⁿ，则逻辑地址的高m-n位表示页码，低n位表示页偏移

碎片问题

1. 使用分页方案，没有外部碎片，但可能有内部碎片

页大小

1. 页大小通常在4KB到8KB之间，也有系统支持更大的页
2. 通常，对于32位的CPU，每个页表条目是4字节长的，可以指向2³²个物理帧，但是这个大小也有可能改变

分页特征

分页的一个重要方面是，程序员视图的内存和实际的物理内存清楚分离

页表的实现

1. 页表小，保存在寄存器中
2. 页表大，被保存在主存中，此时页表基寄存器(PTBR)指向页表，页表长度寄存器(PTLR)表示页表的大小，在这种方案中，每次数据/指令访问都需要两次内存访问，一个用于页表，一个用于数据或指令
3. TLB（转换表缓冲区）：可以加入新的硬件TLB，关联内存，TLB只包含少量的页表条目，当CPU产生一个逻辑地址后，它的页码发送到TLB，如果找到可用于访问内存，如果没找到就需访问页表，再将页码和帧码添加到TLB
   
4. 有效访问时间（注意，需要加入访问数据/指令所需的时间，即不管如何都加上一次访问内存的时间）

内存保护

1. 附在页表中每个条目上的有效-无效位
2. 当该位为有效时，该值表示相关的页在进程的逻辑地址空间内，在内存中
3. 当该位为无效时，该值表示相关的页不在进程的逻辑地址空间内，可能在磁盘中

页表结构

1. 分层页表：页表、页表的页表……
   
2. 哈希页表（虚拟页码被散列到一个页表中）
   
3. 反向页表（进程是通过虚拟地址来引用页，操作系统可以将这种引用转换成物理内存的地址）
   

共享页

1. 共享代码：进程间共享只读代码的一个副本
2. 私有代码和数据：
   （1）每个进程都保留一份寄存器和数据的单独副本。
   （2）私有代码和数据的页面可以出现在逻辑地址空间的任何地方。
   

分段（Segmentation）

1. 进程的地址空间：按照程序自身逻辑关系划分为若干个段，每个段都有一个段名，每段从0开始编址。
2. 内存的分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。
3. 分段系统的逻辑地址结构由段号（段名）和段内地址（段内偏移量）所组成。
4. 段号的位数决定每个进程最多可以分几个段，段内地址位数决定每个段的最大长度是多少。
5. 段表：将二维的逻辑地址映射为一维的物理地址。包括段在内存中的起始物理地址和段的长度。
   

分页式分段（Segmentation with Paging）