内存管理

内存管理是操作系统对内存空间的分配、组织、管理、回收，以及物理/虚拟内存地址映射的一整套庞大的管理系统。

内存的分配

内存的分配包括连续分配方式与离散分配方式，其中连续分配方式是将

连续内存分配方式

连续分配管理方式直接向用户进程分配物理内存的连续内存空间。因为其物理空间是完整连续的，它的地址转换通常只需通过硬件的基址寄存器进行简单的加法计算即可完成，而不需要像非连续分配（分页/分段机制）那样，依赖页表或段表来进行复杂的离散内存寻址与映射。

连续分配方式分为单一连续分配、固定分区分配与动态分区分配

单一分区分配

将内存分为系统区与用户区，用户区单次只允许一条进程访问。单一分区分配不会产生外部碎片，但是其对于内存的利用率过低，在现代操作系统中被淘汰。

固定分区分配

单一分区分配只支持单进程访问内存，多进程并发的场景受限。固定分区将物理内存空间分为固定大小的分区，每一个分块只能容纳一道进程作业。

固定分区可以分为相同内存大小的分区与不同内存大小的分区。

分区大小相等 -- 缺乏灵活性，分区过小限制大，分区过大会产生内部碎片，造成空间浪费。
分区大小不等 -- 需要维护一个内存分配的分区使用表，按照分区大小排列，包括内存大小、初始地址与是否被分配。

动态分区分配

按照进程的动态需求分配连续内存空间。动态分区分配方式在进程释放后会出现内存碎片，这样的内存碎片存在于给进程分配的内存块外，因此称为外部碎片，即一小段的连续内存空间。假如之后的进程需求内存小于内存碎片，则可以直接从内存碎片分配内存空间，但是代价是再次释放进程后会将内存碎片分为更小的内存碎片，直到内存碎片无法支持任何进程。

对于外部碎片，可以通过紧凑技术合并外部碎片。操作系统周期性地移动进程内存地址，将进程的首址与进程的终址拼接，从而将碎片合并。

紧凑技术需要进行动态重定位以实现，性能开销较大。

通常通过链表维护空闲分区，以起址排序。内存块回收时，内存空闲区的合并大致可以分为四类

内存块回收时，与前一空闲区相邻 -- 合并并更新前一空闲区的大小，空闲区的个数不改变
内存块回收时，与后一空闲区相邻 -- 合并并更新后一空闲区的大小，空闲区的个数不改变
内存块回收时，不与任何空闲区相邻 -- 创建新的空闲表项并插入空闲区链表，空闲区个数+1
内存块回收时，前后均与空闲区相邻 -- 合并并更新前一空闲区大小(前+当前块+后)，删除后一空闲块的链表项

空闲内存块分配方式

动态分区中有很多的内存块，如何将空闲的、具有足够大小的内存块分配给进程作业呢？

根据分区索引方式分为顺序分配与索引分配。

空闲内存块的顺序分配

由于空闲分区内存块的链表是根据空闲地址升序排列的，**首次分配算法(First Fit)**使用最简单的顺序查找，找到第一个满足内存条件的空闲分区就分配给进程。

首次分配算法下，通常高地址的内存块是没有被使用过的完整分块，因此有利于大内存开销的进程使用。但是低地址区域容易积累小的外部碎片。每次查找需要从表头开始，查找的开销也较大。

基于首次分配算法的查找逻辑，**邻近适应算法(Next Fit)**的每一轮搜索起点为上次搜索的结束位置。但是首次分配算法的大内存块保留的优势因为搜索起点变化而被破坏，整体性能不如首次分配算法

最佳适应算法(Best Fit) 将空闲内存块根据容量的升序排列，根据内存大小进行最优分配。最佳适应算法目的是追求单次分配的最大内存利用率，但是会产生相当多的微小外部碎片，实际内存利用率与性能不佳。

最坏适应算法(Worth Fit) 将空闲分区按容量递减排列，主动将最大的内存块分割为小块，每次分块总是内存利用率最小的，从而避免生成小碎片。但是难以有足够的大内存块满足大作业的内存需求。

空闲内存块的索引搜索分配

通过索引表查找的方式分配空闲内存块。常见的方式有三种: 快速适应算法(Quick Fit)、伙伴系统(Buddy System)、哈希算法

快速适应算法是根据常用进程占据的空间进行预分块，分为固定大小的内存块。但是回收时进行合并操作的逻辑较为复杂，因为合并后的块大小不一定是常用进程的分块大小，不可避免产生内部碎片。

伙伴系统是将内存空间进行空间二分，形成一个内存块二叉树。如果内存块不足以分配给进程，就向上合并为更大的块以匹配需求。通常不会适应类似于红黑树/B树等更加复杂的数据结构进行内存的管理，更加复杂的数据结构意味着更加复杂的硬件逻辑与性能问题。

哈希算法通过哈希函数得到空闲块的头指针以快速获取空闲分块链。

离散内存分配方式

即分页方式和分段方式，通过页表和段表的映射方式管理内存块

基本分页存储管理

分页管理模式将物理内存分为若干大小相等的物理内存单元，称为页框(物理块/页帧)；将逻辑空间分为与物理空间相等大小的区域称为页。系统以页框为单位分配进程的内存资源。

页与页框的映射方式

逻辑地址中的页有一个唯一的编号称为页号，同时物理地址的页框也有唯一编号称为页框号。

页号到页框号的映射通过页表记录。页表包含每一个页的对应物理页框号、以及相应的状态信息(有效位、访问位等)

逻辑地址的构成由页号+页内偏移量构成。页号用于确定逻辑地址所在的页面，页内偏移量用于确定相对于页面首址的偏移量。这两个地址共同刻画了单一逻辑地址对象。

逻辑地址与物理地址的转换需要地址变换机构，通过页表将逻辑地址映射到物理空间。通过**页表寄存器(PTR)**加快地址变换的速度, 用以存放页表始址与长度。

设逻辑侧的页大小/物理侧的页框大小为 $L$ , 逻辑地址为 $A$ , 物理地址 $E$ , 页表长度 $M$

地址变换的逻辑为:

根据逻辑地址进行页号与偏移量的计算: 页号 $P = \lfloor \frac{A}{L} \rfloor$ (填满了多少块), 页内偏移 $W = A\% L$ (偏移)
越界判断: $P\geq M$ 说明当前逻辑地址所在页超过页表范围，触发越界中断
根据页号 $P$ 在页表中查找页框号 $T$ , 并计算该页框的始址 $b$
逻辑地址对应的物理地址为对应页框相等页内偏移的地址

A = PL+W // 逻辑侧
T = σ(P) // 页表映射
E = TL+W // 物理侧

如果地址转换速度慢或者页表过大，可能导致内存系统的性能下降。诸如快表、多级页表等技术解决了这样的问题

基于快表的地址变换机构

虚拟存储器中提到 快表(TLB) 是基于Cache实现的、能快速并行查找的存储器。

快表中的存储形式和内存页表一致，都是页号+页内偏移量的形式。但是遵循局部性原理存入更高频使用的页表项，能提高地址变换的整体性能。

在有快表的地址变换机构中，CP优先向快表中的页号进行比较，如果快表页号命中就直接读取快表中存储的物理块号；否则就访问内存页表。

两级页表结构

两级页表结构将底层页表也做了一层页表离散映射，相当于将页表作为一个地址
。同时，系统只将活跃的页表调入内存，其余页表置于内存当中。

假设单个页框内能容纳的页表项数量为 $K$

P_1 = ⌊P_0/K⌋ // 一级页表索引
P_2 = P_0 % k // 二级页表索引
A = P_0L+W    // 逻辑侧 -- P_0 为总逻辑页号
T = σ(P)      // 页表映射
E = TL+W      // 物理侧

两级页表结构本质是对页进行分组，满足

$P_0 = P_1K+P_2$

因此逻辑地址由三个部分组成

|一级页表索引|二级页表索引|页内偏移量|

硬件系统通常设置一个外层页表寄存器用于存放一级页表的起始地址

基本分段存储管理

分页管理方式是硬件上的内存管理方式，分段管理方式是面向用户的内存管理方式。

分段系统将用户进程的逻辑空间分为不同大小的段，包含如主程序段、子程序段、栈段与数据段等不同内存段，每一个段从0地址开始兵分配连续的段内空间。通过段号+段内偏移量确定逻辑地址

分段结构中的逻辑地址结构

|段号 S|段内偏移量 W|

段表结构

|段表|段长|本段在主存中的初始地址|

用于确定段在物理地址中的区域，段地址变换机构也能通过段表进行逻辑地址与物理地址的映射

段与共享

系统能维护一个共享段表以支持多个共享段访问共享段表。不可修改的代码支持多个进程的并发执行，系统会将这样的纯代码放入只读段中。同时每一个进程都有私有的局部数据区，避免共享访问私有数据。

段的保护

越界保护段号不能超过段表长度
存取控制保护通过访问权限位防止非法访问

段页式存储管理

先根据用户逻辑讲进程地址分段，再将每一个段内存块根据页逻辑存储。进程的逻辑地址由三个部分构成

|段号 S|页号 P|页内偏移量 W|

段页寻址中段寻址部分需要通过段表实现，这和单段表的逻辑是一样的。