Storage Management Part Ⅰ
存储器的层次结构
存储器层次结构概述
为能更多的存放并更快地处理用户信息，目前许多计算机把存储器分为三级。
- 高速缓存 Cache：K 字节、高速、昂贵、易变的
- 内存 RAM： M 或 G 字节、中速、中等价格、易变的
- 磁盘：G 或 T 字节、低速、价廉、不易变的
寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储的信息不再存在。
磁盘和可移动存储介质属于设备管理的管辖范畴，它们存储的信息将被长期保存。
主存储器与寄存器
主存储器（内存，主存，可执行存储器）
用于保存进程运行时的程序和数据。CPU 的控制部件只能从主存中取得指令和数据到 CPU 寄存器，同样，CPU 寄存器中的数据可存入主存。
CPU 与外设交换数据必须依托于主存。寄存器
寄存器访问速度最快，与 CPU 协调工作。
高速缓存与磁盘缓存
CPU 对高速缓存的访问，其速度比访问主存快，比访问寄存器慢。
根据程序执行的局部性原理，将主存中一些经常访问的数据存放在高速缓存中，减少访问主存的次数，提高程序的执行速度。
有些计算机系统设置了两级高速缓存，即，一级高速缓存与二级高速缓存。局部性原理（Locality Principle）指在程序执行过程中，数据和指令的访问存在一定的空间和时间上的局部性特点。其中，时间局部性是指一个数据项或指令在一段时间内被反复使用的特点，空间局部性是指一个数据项或指令在一段时间内与其相邻的数据项或指令被反复使用的特点。
在分页机制中，页表的作用是将虚拟地址转换为物理地址，从而完成内存访问。在这个过程中，局部性原理的作用体现在两个方面：
时间局部性：由于程序中存在一定的循环或者重复操作，因此会反复访问同一个页或一些特定的页，这就体现了时间局部性的特点。为了利用时间局部性，分页机制中通常采用缓存机制来提高页面的命中率，即将最近访问过的一些页放入缓存中，如果下一次访问的页已经在缓存中，就不需要再次访问内存，而是直接从缓存中读取。
空间局部性：由于程序中数据和指令的访问通常是具有一定的空间连续性的，因此当访问某个页时，往往会顺带访问其相邻的一些页。为了利用空间局部性，分页机制中通常采用预取技术来预先将相邻的一些页读入内存缓存中，以便在未来访问时能够直接使用，从而提高访问速度。总之，局部性原理是计算机体系结构设计的重要原则之一，也是许多优化算法的基础。在分页机制中，利用时间局部性和空间局部性，采用缓存和预取技术，可以提高页面的命中率，从而提高内存访问效率
高速缓存与磁盘缓存
- 高速缓存
CPU 对高速缓存的访问，其速度比访问主存快，比访问寄存器慢。
根据程序执行的局部性原理，将主存中一些经常访问的数据存放在高速缓存中，减少访问主存的次数，提高程序的执行速度。
有些计算机系统设置了两级高速缓存，即，一级高速缓存与二级高速缓存。 - 磁盘缓存
内存中一块存储区，对应于某固定磁盘，临时存储磁盘数据（如，数据预取）
存储器管理的目的和功能
操作系统负责协调这些存储器的使用
三级存储器，从缓存到内存到外存，其容量愈来愈大，而访问数据的速度则愈来愈慢，价格也愈来愈便宜。
用户的程序在运行时应存放在主存中，以便处理机访问。
为尽可能利用 CPU，要求直接存取内存的速度尽量快到与 CPU 取指速度相匹配，容量大到能装下当前运行的程序与数据
由于主存容量和速度有限。所以把那些不马上使用的程序、数据放在外部存储器(又称辅存)中。当用到时再把它们读入主存。
- 主存储器的分配和管理：按用户要求把适当的存储空间分配给相应的作业。一个有效的存储分配机制，应在用户请求时能作出快速的响应，分配相应的存储空间；在用户不再使用它时，应立即回收，以供其他用户使用。为此，这个存储分配机制应具有如下功能：
- 记住每个存储区域的状态：哪些是已分配的，哪些是可以用作分配的。
- 实施分配：在系统程序或用户提出申请时，按所需的量给予分配；修改相应的分配记录表。
- 接受系统或用户释放的存储区域：并相应地修改分配记录表。
- 提高主存储器的利用率：使多道程序能动态地共享主存，最好能共享主存中的信息
- “扩充”主存容量：这是借助于提供虚拟存储器或其它自动覆盖技术来达到的。即为用户提供比主存的存储空间还大的地址空间
- 存储保护：确保各道用户作业都在所分配的存储区内操作，互不干扰。即要防止一道作业由于发生错误而损害其它作业，特别需要防止破坏其中的系统程序。这个问题不能用特权指令来加以解决，而必须由硬件提供保护功能，并由软件配合实现
存储分配的三种方式
存储分配，解决多道作业之间共享主存的问题。确定什么时候，以什么方式，把一个作业的全部信息或作业运行时首先需要的信息分配到主存中，并使这些问题对用户来说尽可能是透明的。
“对用户透明”（User Transparency）是一种计算术语，它指的是用户在使用系统或服务时，不需要关心或理解其背后的复杂实现细节。换句话说，系统或服务的复杂性对用户是”透明”的。
解决存储分配问题的三种方式：
目前，绝大多数计算机系统都采用静态或动态存储分配方式
- 直接指定方式
程序员在编程序时，或编译程序(汇编程序)对源程序进行编译(汇编)时，使用实际存储地址。- 在多道程序环境下，应保证各作业所用的地址互不重叠。在多道程序发展的初期，通常把存储空间划分成若干个固定的不同大小分区，并对不同的作业指定相应的分区。因此，对编程人员或对编译程序而言，存储器的可用空间是可知的
- 采用直接指定方式分配的前提是：存储器的可用容量(空间)已经给定或者可以指定，这对单用户计算机系统是不成问题的
- 这种分配方式的实质是：由编程人员在编写程序时，或由编译程序编译源程序时，对一个作业的所有信息确定在主存存储空间中的位置。因此，这种直接指定方式的存储分配方案，不仅用户感到不便，而且存储空间的利用也不那么有效
- 静态分配方式（Static Allocation）
用户在编程时，或由编译程序产生的目的程序，均可从其地址空间的零地址开始；当装配程序对其进行连接装入时才确定它们在主存中的相应位置，从而生成可执行程序。也就是说，存储分配是在装入时实现的。静态分配策略的存储管理很简单，但在多道程序系统中不能有效地共享存储器资源
这种静态存储分配方式的特点是：- 在一个作业装入时必须分配其要求的全部存储量；
- 如果没有足够的存储空间，就不能装入该作业；
- 一旦一个作业进入内存后，在其退出系统之前，它一直占用着分配给它的全部存储空间；
- 作业在整个运行过程中不能在内存中“搬家”、也不能再申请存储量。
- 动态分配方式（Dynamic Allocation）
动态分配是一种更加有效的使用主存储器的方法。这种动态存储分配方式的特点是：- 作业在存储空间中的位置，也是在其装入时确定的；
- 在其执行过程中可根据需要申请附加的存储空间；
- 一个作业已占用的部分存储区域不再需要时，可以要求归还给系统。即：这种存储分配机制能接受不可预测的分配和释放存储区域的请求，实现个别存储区域的分配和回收；
- 存储区域的大小是可变的；
- 允许作业在内存中“搬家”。
基本概念
逻辑地址（相对地址，虚地址） Logical Address
用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为 0，其余指令中的地址都相对于首地址而编址。不能用逻辑地址在内存中读取信息
物理地址（绝对地址，实地址）Physical Address
内存中存储单元的地址，可直接寻址
命名空间 namespace
是一种封装或组织代码的方式，它可以将一组标识符（如变量、函数、类、模块等）包含在一个名为命名空间的范围内
地址空间 Address Space
程序用来访问信息所用地址单元的集合，是逻辑（相对）地址的集合，由编译程序生成。
存储空间 Storage Space
主存中物理单元的集合。这些单元的编号称物理地址或绝对地址。存储空间的大小是由主存的实际容量决定的。
地址空间是逻辑地址的集合；存储空间是物理地址的集合。一个是“虚”的概念，一个是“实”的物体。
一个编译好的目标程序存在于它自己的地址空间中，当要它在计算机上运行时，才把它装入存储空间。
一个作业在编译、装入前后存在于不同的空间。
程序的装入和链接
将一个用户源程序变为一个可在内存中执行的程序，通常要经过下列几步：
- 预处理（Preprocessing）：这是编译过程的第一步，主要处理源代码中的预处理器指令。例如，C 和 C++语言中的
#include和#define等。预处理器将处理这些指令，如扩展包含文件，替换宏定义等，生成一个预处理后的源代码文件。 - 编译（Compilation）：在这个阶段，编译器将预处理后的源代码转换为汇编语言。编译器在这个过程中会进行词法分析、语法分析、语义分析和优化等操作。编译器还会检查源代码中的错误，并生成对应的错误和警告信息。
- 汇编（Assembly）：汇编阶段将编译阶段生成的汇编代码转换为机器语言代码，也就是目标代码。这个过程是由汇编器完成的。每一条汇编语言指令通常会被转换为一条机器语言指令。
- 链接（Linking）：链接阶段是将所有的目标代码和必要的库函数链接在一起，生成一个可执行文件。链接器会处理源代码中的外部符号引用，将它们与正确的地址或者符号绑定在一起。
- 装入（Loading）：当程序运行时，加载器（Loader）的任务是将可执行文件从硬盘加载到内存中，然后开始执行。加载器还负责解析程序对动态库的依赖，并将这些库加载到内存中。
程序的装入
根据存储空间的分配方式，将一个装入模块装入内存时，可采用三种方式：
- 绝对装入方式 Absolute Loading Mode：
在编译时，如果知道程序将驻留在内存的具体位置，那么编译程序将产生实际存储地址（绝对地址）的目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存。- 装入模块被装入内存后，由于程序中的逻辑地址与实际内存地址完全相同，故不需对程序和数据的地址进行修改。
- 通常在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。
- 静态重定位装入方式 Static Relocation Loading Mode：
地址变换是在装入内存时一次完成的，且以后不能移动。
一般情况下,物理地址=相对地址+内存中的起始地址
适用于多道程序环境，可以将装入模块装入到内存中任何允许的位置。- 优点：不需硬件支持，可以装入有限多道程序。
- 缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动，不易实现共享。
- 动态重定位装入方式/动态运行时装入方式 Dynamic Run-time Loading
装入程序将装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把地址转换推迟到程序执行时进行。在硬件地址变换机构的支持下，随着对每条指令或数据的访问自动进行地址变换，故称为动态重定位
最简单的办法是利用一个重定位寄存器(RR)。该寄存器的值是由进程调度程序根据作业分配到的存储空间起始地址来设定的。
在具有这种地址变换机构的计算机系统中，当执行作业时，不是根据 CPU 给出的有效地址去访问主存，而是将有效地址与重定位寄存器中的内容相加后得到的地址作为访问主存的地址
采用动态重定位技术后，程序中所有指令和数据的实际地址是在运行过程中最后访问的时刻确定的。也就是说，在作业运行过程中临时申请分配附加的存储区域或释放已占用的部分存储空间是允许的。- 主要优点
① 主存的使用更加灵活有效。这里，一个用户的作业不一定要分配在一个连续的存储区，因而可以使用较小的分配单位。而且，在作业开始之前也不一定把它的地址空间全部装入主存，而可以在作业执行期间响应请求动态地进行分配。
② 几个作业共享一程序段的单个副本比较容易。
③ 有可能向用户提供一个比主存的存储空间大得多的地址空间。因而无需用户来考虑覆盖结构，而由系统来负责全部的存储管理。 - 主要缺点
① 需要附加硬件支持；
② 实现存储器管理的软件比较复杂。
- 主要优点
程序的链接
链接程序的功能，是将经过编译后所得到的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块。
连接程序按各个模块的相对地址依次构成统一的从 0 号单元开始编址的逻辑地址空间
根据链接时间的不同，可把链接分成如下三种：
静态链接 Static Linking
在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块（又称执行模块），以后不再拆开。
将几个目标链接装配成一个装入模块时，需解决以下两个问题：- 将相对地址进行修改。即将除第一个模块外的相对地址修改成装入模块中的相应的相对地址
- 变换外部调用符号。即将每个模块中所用的外部调用符号，都变换为相对地址。
这种先进行链接所形成的一个完整的装入模块，又称为可执行文件
Pros：适用范围广，不必担心用户机器缺少某个库函数
Cons：修改或更新某个目标模块时，需要重新打开装入模块，效率低且很多时候不可行；静态链接的每个模块都要有目标模块的副本，无法实现共享，浪费空间装入时动态链接 Load-Time Dynamic Linking
用户源程序经编译后所得到的目标模块，是在装入内存时，边装入边链接的。即在装入一个目标模块时，若发生一个外部模块调用，将引起装入程序去找出相应的外部目标模块，并将其装入内存。
Pros：便于软件版本的修改和更新,只需修改各个目标模块，不必将装入模块拆开，非常方便;便于实现目标模块共享。即可以将一个目标模块链接到几个应用模块中，从而实现多个应用程序对该模块的共享。运行时动态链接 Run-Time Dynamic Linking
目前最常使用的链接方式,采用装入时动态链接方式，虽然可将一个装入模块装入到内存的任何地方，但装入模块的结构是静态的，表现在：- 进程（程序）在整个执行期间，装入模块是不改变的；
- 每次运行时的装入模块是相同的。并且事先无法知道本次要运行哪些模块，只能将所有可能要运行的模块在装入时全部链接在一起，而实际上往往有些目标模块根本不会运行。
采用运行时动态链接可将某些目标模块的链接推迟到执行时才进行，即在执行过程中，若发现一个被调用模块尚未装入内存时，由 OS 去找到该模块，将它装入内存，并链接到调用模块上。运行时动态链接的工作原理如下：
- 加载阶段：当程序启动时，动态链接器（在 Unix-like 系统中通常是 ld.so 或 ld-linux.so，在 Windows 系统中是 kernel32.dll）会加载程序需要的动态链接库（DLL）或共享对象（SO）文件。这些库文件包含程序需要的函数和数据。
- 链接阶段：在程序运行时，当程序第一次调用某个库函数时，动态链接器会查找这个函数在内存中的实际地址，并将这个地址写入程序的全局偏移表（GOT）或程序查找表（PLT）。这个过程被称为“解析”。
- 运行阶段：一旦函数地址被解析，程序就可以直接调用这个函数，而不需要再次通过动态链接器。如果程序再次调用这个函数，它会直接从 GOT 或 PLT 中获取函数的地址。
运行时动态链接的优点包括：
- 主要优点:凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。
- 节省内存：因为多个程序可以共享同一个库的单个副本。
- 模块化：程序可以在运行时加载和卸载模块，这使得程序更加灵活和可扩展。
- 版本控制：可以在不重新编译程序的情况下更新库。
运行时动态链接的缺点包括：
- 性能开销：动态链接和解析需要时间，尤其是在程序第一次调用库函数时。
- 兼容性问题：如果库的新版本和旧版本不兼容，那么使用这个库的程序可能会出错。
连续分配存储管理方式
连续分配指为用户程序分配一个连续的内存空间。
程序空间本来就是连续的,用连续的内存装入连续的程序，减少管理工作的难度
连续分配有三种方式：
- 单一连续分配方式
单用户系统在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低。内存分为两个区域，一个供操作系统使用，一个供用户使用. - 分区式分配方式
系统把内存用户区划分为若干分区，分区大小可以相等，也可以不等。一个进程占据一个分区。这是早期用于多道程序的一种较简单的存储管理方式。它又可以分为：- 固定分区
- 动态（可变）分区
- 可重定位分区分配(汤子瀛)
单一连续分配
内存中仅驻留一道用户程序，整个用户区为一个用户独占。
内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。
最简单，适用于单用户、单任务的 OS。
- 优点：易于管理。
- 缺点：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占用内存。
例如：DOS 2.0 以下的 DOS 操作系统采用单一连续区域主存管理方法。
🌟 内存碎片
内部碎片 Internal Fragment：分配给用户但用户没有使用的空间，即多分配的空间。分配给进程的内存空间比进程所需的内存空间大，但未使用的部分不能再分配给其他进程，造成内部碎片。
外部碎片 External Fragment：没有分配但无法分配的空间，即太小而无法分配的空间。相邻已分配内存空间的空闲区域太小，不能分配给需要的进程，造成外部碎片。
固定分区分配
固定分区分配思想：将内存用户空间划分为若干个固定大小的区域，每个区域称为一个分区（region），在每个分区中只装入一道作业 ，从而支持多道程序并发设计。
由于这些存储区域是在系统启动时划定的，在用户作业装入及运行过程中，其区域的大小和边界是不能改变的。
固定式分区的划分方法有两种：
(1)分区大小相等
(2)分区大小不等
为了实现这种固定分区的分配，系统需要建立一张分区说明表。这个分区说明表指出可用于分配的分区数以及每个区的大小、起始地址及状态(是否已被分配)
内存分配过程
当有作业要装入内存时，内存分配程序检索分区说明表，从中找出一个尚未使用的满足大小要求的分区分配给该作业，然后修改分区的状态；如果找不到合适的分区就拒绝为该作业分配内存。
内存中已分配给用户但未被利用的区域称为 “内零头”（内部碎片，内碎片）;固定分区分配有内零头产生
- 优点：易于实现，开销小
- 缺点：内碎片造成浪费；分区总数固定，限制了并发执行的程序数目；存储空间的利用率太低。现在的操作系统几乎不用它了。
动态分区分配
动态分区分配是指根据进程的实际需要，动态地为之分配连续的内存空间。即分区的边界可以移动，分区的大小是可变的。
动态分区又有两种不同选择，一种是分区的数目固定大小可变，而另一种则允许分区的数目和大小都可变。 为了说明它们之间的重要差异，我们考虑一个具有 256K 字节存储器的系统。
第一种方案(分区数目固定)：假定系统初始化时规定把存储空间划分为 8 个分区;在下图(a)中用问号(?)来表示它们。在系统运行一段时间后，已有 192K 存储空间分配给 7 个作业，剩下 64K 还未分配，如下图(b)所示。
现在，又有两个作业 P 和 Q 准备调入，它们每个需要 32K 存储空间。显然，我们有足够的存储空间。却没有足够数的存储区域(目前只有一个可用)。因此，只能允许一个作业(如 P)被调入，如下图(c)所示。
第二种方案(分区数目可变)：最初，没有建立任何分区，整个可用的存储空间用一个问号来表示；之后，发生上述所说在系统运行一段时间后，已有 192K 存储空间分配给 7 个作业，剩下 64K 还未分配的情况，如图(b)；
现在，我们在剩下的 64K 存储空间中，可以创建两个分区，分别装入作业 P 和 Q，如图(c)。显然，此方案比第一个方案更灵活，内存利用率更高。
动态分区分配算法
实现动态分区分配，通常有两种数据结构：空闲分区表和空闲分区链。
算法
系统运行一段时间后，在整个存储空间内将出现许多大小不等的区域，有的仍被作业进程占用，有的则因作业已退出系统而成为可用于再分配的区域。现在假设有一个新的作业需调入主存，如何为其选择一个合适的区域？
- 基于顺序搜索
- 最佳适应算法(Best Fit)
- 最坏适应算法(Worst Fit)
- 首次适应算法(First Fit)
- 循环首次适应算法(Next Fit)
- 基于索引搜索
- 快速适应算法(Quick Fit)
- 伙伴系统
最佳适应算法 Best fit: BF
就是为一作业选择分区时总是寻找其大小最接近作业所要求的存储区域。即：把作业放入这样的分区后剩下的内部碎片最小。为了加快查找速度，应将存储空间中所有的空白区按其大小递增的顺序链接起来，组成一空白区链(Free List)。
优点：
- 如果存储空间中具有正好是所要求大小的存储空白区，则必然被选中；
- 如果不存在这样的空白区，也只对比要求稍大的空白区进行划分，而绝不会去划分一个更大的空白区。因此，其后遇到大作业到来时，作业要求的存储区域就比较容易得到满足。
缺点：
- 采用最佳适应算法，在每次分配时，总是产生最小的空白区。因此，经过一段时期后，存储空间中可能留许多这样的空白区，由于其太小而无法使用。为了改善这种情况，在该算法中设置一参数 G，用它来确定最小分区的大小。当选择一个分区时，如果选中的空白区与要求的大小之差小于 G，则不再对它划分，而把整个这个空白区分配给申请的作业。
- 在回收一个分区时，为了把它插入到空白区链中合适的位置上也颇为费时。所以，这种算法乍看起来是最佳的，其实则不然。
最坏适应算法 Worst fit: WF
与最佳适应算法相反，它在为作业选择存储区域时，总是寻找最大的空白区。在划分后剩下的空白区也是最大的，因而对以后的分配很可能仍然是有用的，这是该算法的一个优点。但是，由于最大的空白块总是首先被分配而进行划分，当有大的作业时，其存储空间的申请往往得不到满足，这是该算法的一个缺点。
为了支持这个算法的实现，空白块应以大小递减的顺序链接起来。
首次适应算法 First fit: FF
BF 和 WF 各有其利弊。首次适应算法是对它们进行折衷考虑后设计出来的。
每个空白区按其在存储空间中地址递增的顺序链在一起，即每个后继空白区的起始地址总是比前者的大。在为作业分配存储区域时，从这个空白区链的始端开始查找，选择第一个足以满足请求的空白块，而不管它究竟有多大。
和上述算法一样，这个选择的空白区被分成两部分。一部分与请求的大小相等，分配给作业；剩下的部分留在空白区链中。显然，这个算法倾向于优先利用存储空间中低址部分的空白区。
主要优点
算法简单，查找速度快；留在高址部分的大的空白区被划分的机会较少，因而在大作业到来时也比较容易得到满足。
主要缺点：
这种算法常常利用一个大的空白区适应小作业的请求，从而留下一些较小的无法用的空白区(外部碎片)，存储空间利用率不高；而且，由于所有的请求都是从空白区链的始端开始查找，因而这些小而无用的空白区集中在这个链的前端，相应地，一些较大空白区在链的尾端才能发现，这种情况将使找到合适空白区的速度降低。
下次(循环首次)适应算法 Next fit: NF
为了克服上述缺点，又设计了一种称为“下次”适应的算法，它实际上是首次适应算法的一种变形，故也被称为带旋转指针的首次适应算法(Next Fit with Roving Pointer)
为此，我们把存储空间中空白区构成一个循环链。每次为存储请求查找合适的分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就将它划分后分配出去。显然，采用这一策略后，存储空间的利用更加均衡，而不至于使小的空白区集中于存储器的一端。但是，在存储器的另一端也不可能保留大的空白块，因此，当需要获得相当大的空白区时，能满足的可能性减少了。
快速适应算法 Quik fit:QF
将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。
这样，系统中存在多个空闲分区链表；
同时，在内存中设立一张管理分区类型，并记录了该类型空闲分区链表表头的索引表，该表的每一个表项记录了对应类型空闲分区链表表头的指针。
分配过程：根据进程的长度，寻找到能容纳它的最小空闲分区链表，并取下第一块进行分配即可
优点
- 查找效率高。
- 该算法在进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。
缺点
- 在分区归还主存时算法复杂，系统开销较大。
- 该算法在分配空闲分区时是以进程为单位，一个分区只属于一个进程，因此在为进程所分配的一个分区中，或多或少地存在一定的浪费。空闲分区划分越细，浪费则越严重，
隋唐小练
分区分配操作
涉及动态分区的主要操作有分配内存和回收内存。这些操作是在程序接口中通过系统调用发出的。
分配内存：
向操作系统提出一特定存储量的请求。通常，它并不要求这个分配的存储区域限于特定的位置，但是，这个区域必须是连续的。OS 利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。- 请求的分区大小为 u.size
- 表中每个空闲分区的大小为 m.size
- size 是事先规定的不再切割的剩余分区的大小
回收内存
进程用于归还一个不再需用的存储区域。- 当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点。
- 在回收一个分区时，一个回收的分区与空白区邻接的情况有四种，对这四种情况分别作如下处理：
- 回收区与插入点的前一个空闲分区 F1 相邻接。此时应将回收区与插入点的前一分区合并(通过修改其前一分区 F1 的大小，不必为回收区分配新表现)
- 回收区仅与下面的空白区邻接，合并后仍为空白区 F2，但其起始地址和大小均需改变。用回收区的首址作为新空闲区的首址，大小为两者之和
- 回收区与上、下面的空白区邻接此时将三个分区合并，使用 F1 的表项和 F1 的首址，取消 F2 的表项，大小为三者之和。
- 回收区与上、下面的空白区均不邻接，在这种情况下，应为回收区单独建立一新表项，填写回收区的首址和大小，并根据首地址插入到空闲链中的适当位置。
伙伴系统 Buddy System
固定分区和动态分区都存在内部碎片和外部碎片的问题。伙伴系统是一种解决内部碎片问题的方法。
在伙伴系统中，可用内存块的大小为$2^k (1\le k\le m)$
其中$2^1$表示分配的最小块尺寸，$2^m$表示分配的最大块尺寸，通常是可供分配的整个内存空间大小。
对空闲区按照大小分类，相同大小的分区链接为一个双向空闲链表；最多可形成 k 个链表。
进程请求大小为 n 的存储空间：
- 找到 i，使得$2^{i-1} < n < 2^i$
- 在空闲分区大小为$2^i$的链表中查找，若找到，则分配；
- 如果没找到，从$2^{i+1}$的链表中查找，找到后，将其分裂为两个大小相等的伙伴，其中一个分配给进程，另一个插入到$2^i$相应的链表中。
- 如果仍然没找到，则继续查找更大的链表，直到找到或者查找完所有链表。
> 分割及回收合并分区需要时间开销，多用于多处理机系统中。哈希算法
利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张哈希表，以空闲分区大小为关键字，每一个表项记录了一个对应的空闲分区链表表头指针。
当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。
可重定位分区分配
紧凑 Compaction
可变式分区分配策略是在装入作业时根据其要求量为其划定相应的区域。这种分配策略，消除了固定式分区分配造成的“内零头”，但不可避免地在存储空间中造成“外零头”，为了进一步提高存储器的利用率，必须设法减少由于外零头造成的浪费。
一个最简单而直观的解决零头问题的办法是，定时地或者在内存紧张时，把存储空间中的空白区合并为一个大的连续区。
实现方法将内存中的所有作业进行移动，使它们全都相邻接，这样，可把原来分散的多个小分区合成一个大分区。这种技术称为存储器的紧凑Compaction。
把一个作业从一个存储区域移动到另一个存储区域，需要对作业中的某些地址部分和地址常数等进行调整。一个较实用且可行的办法是采用动态重定位技术。一个作业在主存中移动后，只要改变重定位寄存器中的内容即可。
动态重定位 Dynamic Relocation
在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。
程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。
Ref
Storage Management Part Ⅰ