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：没有分配但无法分配的空间，即太小而无法分配的空间。相邻已分配内存空间的空闲区域太小，不能分配给需要的进程，造成外部碎片。
