「系统」01-存储管理

Chapter1 - 存储管理

存储管理是对内存硬件的抽象，本章要求掌握计算机的存储体系、存储管理的主要功能、各种不同的存储管理方案和虚拟存储管理。

0x00 存储体系

1. 基础知识

• *ELF(Executable and Linkable Format) 可执行文件

• ELF头的定义：
  • e_ident： 这一部分是文件的标志，用于表明该文件是一个ELF文件。ELF文件的头四个字节为magic number。
  • e_type： 用于标明该文件的类型，如可执行文件、动态连接库、可重定位文件等。
  • e_machine： 表明体系结构，如x86，x86_64，MIPS，PowerPC等等。
  • e_version： 文件版本
  • e_entry： 程序入口的虚拟地址
  • e_phoff： 程序头表在该ELF文件中的位置(具体地说是偏移)。ELF文件可以没有程序头表
  • e_shoff： 节头表的位置。
  • e_eflags： 针对具体处理器的标志。
  • e_ehsize： ELF 头的大小。
  • e_phentsize： 程序头表每项的大小。
  • e_phnum： 程序头表项的个数。
  • e_shentsize： 节头表每项的大小。
  • e_shnum： 节头表项的个数。
  • e_shstrndx： 与节名字符串表相关的节头表

typedef struct {
    unsigned char e_ident[16]; 		/* 标志本文件为目标文件，提供机器无关的数据，可实现对文件内容的译码与解释*/
    unsigned char e_type[2]; 		/* 标识目标文件类型 */
    unsigned char e_machine[2]; 	/* 指定必需的体系结构 */
    unsigned char e_version[4]; 	/* 标识目标文件版本 */
    unsigned char e_entry[4]; 		/* 指向起始虚地址的指针 */
    unsigned char e_phoff[4]; 		/* 程序头表的文件偏移量 */
    unsigned char e_shoff[4]; 		/* 节头表的文件偏移量 */
    unsigned char e_flags[4]; 		/* 针对具体处理器的标志 */
    unsigned char e_ehsize[2]; 		/* ELF 头的大小 */
    unsigned char e_phentsize[2]; 	/* 程序头表每项的大小 */
    unsigned char e_phnum[2]; 		/* 程序头表项的个数 */
    unsigned char e_shentsize[2]; 	/* 节头表每项的大小 */
    unsigned char e_shnum[2]; 		/* 节头表项的个数 */
    unsigned char e_shstrndx[2]; 	/* 与节名字符串表相关的节头表项的索引 */
} Elf32_Ehdr;

• 一个程序本质上都是由 bss段、data段、text段三个组成的。

  • bss段：（bss segment）
    • 用来存放程序中未初始化的全局变量的一块内存区域。bss是英文Block Started by Symbol的简称。
    • bss段属于静态内存分配。
  • data段：数据段（data segment）
    • 用来存放程序中已初始化的全局变量的一块内存区域。
    • 数据段属于静态内存分配。
  • text段：代码段（code segment/text segment）
    • 用来存放程序执行代码的一块内存区域。
    • 这部分区域的大小在程序运行前就已经确定，并且内存区域通常属于只读(某些架构也允许代码段为可写)。
    • 在代码段中，也有可能包含一些只读的常数变量，例如字符串常量等。

• text和data段都在可执行文件中，由系统从可执行文件中加载，而bss段不在可执行文件中，由系统初始化。

• 一个装入内存的可执行程序，除了bss、data和text段外，还需构建一个栈（stack）和一个堆（heap）。
  • 栈(stack)：存放、交换临时数据的内存区
    • 用户存放程序局部变量的内存区域，（但不包括static声明的变量，static意味着在数据段中存放变量）。
    • 保存/恢复调用现场。在函数被调用时，其参数也会被压入发起调用的进程栈中，并且待到调用结束后，函数的返回值也会被存放回栈中。
  • 堆（heap）：存放进程运行中动态分配的内存段
    • 当进程调用malloc等函数分配内存时，新分配的内存就被动态添加到堆上（堆被扩张）；当利用free等函数释放内存时，被释放的内存从堆中被剔除（堆被缩减）。
    • 它的大小并不固定，可动态扩张或缩减。

2. 生成可执行文件的过程

1. 编译：.c -> .o

   • 编译C程序的时候，是以.c文件作为编译单元的;
   • C语言代码经过编译以后，并没有生成最终的可执行文件（.exe 文件），而是生成了一种叫做目标文件（Object File）的中间文件（或者说临时文件）。目标文件和可执行文件的格式是相同的，都是二进制文件。
     • 对于 Visual C++，目标文件的后缀是.obj；对于 GCC，目标文件的后缀是.o。

   C语言的编译器有很多种，不同的平台下有不同的编译器，例如：

   • Windows 下常用的是微软开发的 Visual C++，它被集成在 Visual Studio 中，一般不单独使用；
   • Linux 下常用的是 GUN 组织开发的 GCC，很多 Linux 发行版都自带 GCC；
   • Mac 下常用的是 LLVM/Clang，它被集成在 Xcode 中（Xcode 以前集成的是 GCC，后来由于 GCC 的不配合才改为 LLVM/Clang，LLVM/Clang 的性能比 GCC 更加强大）。

2. 链接：.o -> exe

   • 编译只是将我们自己写的代码变成了二进制形式，它还需要和系统组件（比如标准库、动态链接库等）结合起来，这些组件都是程序运行所必须的。于是需要将这些.o文件链接到一起，形成最终的可执行文件。
   • 在链接时，链接器会扫描各个目标文件，将之前未填写的地址填写上，从而生成一个真正可执行的文件。

3. 重定位：Relocation

   • 将之前未填写的地址填写的过程。

链接过程举例

• 一个C语言程序

---------------------------main.c-----------------------------
int buf[2] = {1,2}; //全局变量
void swap();

int main(){
    swap();
    return 0;
}
-------------------------------------------------------------

--------------------------swap.c----------------------------
extern int buf[];

int *bufp0 = &buf[0]; //全局变量
static int *bufp1; //静态变量

void swap() //buf数组的0索引和1索引的值互换
{
    int temp; //局部变量
    bufp1 = &buf[1];
    temp = *bufp0;
    *bufp0 = *bufp1;
    *bufp1 = temp;
}
-------------------------------------------------------------

• gcc调用包含的几个工具
  • cc1：预处理器和编译器
  • as：汇编器
  • collect2：链接器

链接过程的本质

可执行文件的内存映像

3. 程序的装载和运行

• 装载前的工作：
  • shell调用 fork() 系统调用，创建出一个子进程。
• 装载工作：
  • 子进程调用 execve() 加载program(即要执行的程序)
  • 加载器在加载程序的时候只需要看ELF文件中和segment相关的信息即可。

• 细节
  • 一个segment在文件中的大小是小于等于其在内存中的大小。
  • 如果segment在文件中的大小小于在内存中的大小，那么在载入内存时通过补零使其达到其在内存中应有的大小

程序的装载流程

1. 读取ELF头部的魔数(Magic Number)，以确认该文件确实是ELF文件。
   • ELF文件的头四个字节依次为’0x7f’、’E’、‘L’、‘F’。
   • 加载器会首先对比这四个字节，若不一致，则报错。
2. 找到段表项。
   • ELF头部会给出的段表起始位置在文件中的偏移，段表项的大小，以及段表包含了多少项。
   • 根据这些信息可以找到每一个段表项。
3. 对于每个段表项解析出各个段应当被加载的虚地址，在文件中的偏移，以及在内存中的大小和在文件中的大小。（段在文件中的大小小于等于内存中的大小）
4. 对于每一个段，根据其在内存中的大小，为其分配足够的物理页，并映射到指定的虚地址上。再将文件中的内容拷贝到内存中。
5. 若ELF中记录的段在内存中的大小大于在文件中的大小，则多出来的部分用0进行填充。
6. 设置进程控制块中的PC为ELF文件中记载的入口地址。
7. 控制权交给进程开始执行。

0x01 存储管理的功能

• 存储器由内存和外存组成。
• 所谓内存空间，是由存储单元（字节或字）组成的一堆连续的地址空间。
  • 用来存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的，亦即程序计数器所指的存储器。

1. 内存的分配和回收

一个有效的存储分配机制，应对用户提出的需求予以快速响应，为之分配响应的存储空间；当用户不在需要它时及时回收，以供其他用户使用。因此，存储管理应具有以下功能：

• 记住每个存储区域的状态。使用相应的表格记录内存空间使用状态，内存空间是已分配的，或者是空闲的。
  • 位图表示法、链表表示法
• 完成分配。当用户提出申请时，按需要进行分配，并修改相应的分配表格。
• 回收。收回用户释放的区域，并修改相应的分配表格。

2. 存储保护

在多道程序系统中，内存中既有操作系统，又有许多用户程序。为使系统正常运行，避免内存中各程序相互干扰，必须对内存中的程序和数据进行保护。存储保护通常需要有硬件支持，并由软件配合实现，常用的存储保护方法有：

• 地址越界保护。每个进程都具有其相对独立的地址空间，如果进程在运行时所产生的的地址超出器地址空间，则发生地址越界。因此，对进程所产生的地址必须加以检查。
  • 界限寄存器方法
• 权限保护。对于允许多个进程共享的公共区域，每个进程都有自己的访问权限。因此，必须对公共区域的访问加以限制和检查。
  • 存储键保护法

3. 地址转换

• 一些相关概念
  • 名字空间：在汇编语言或高级语言编写的程序中，是通过符号名来访问子程序和数据的，我们把程序中符号名的集合叫做“名字空间”。
  • 地址空间：源程序经过编译后得到的目标程序，存在于它所限定的地址范围内，这个范围称为地址空间。目标程序中的地址称为相对地址（或逻辑地址），把相对地址的集合叫做“相对地址空间”或简单地叫做“地址空间”。
  • 存储空间：存储空间是指主存中一系列存储信息的物理单元的集合，这些单元的编号称为物理地址或绝对地址。简言之，存储空间是物理地址的集合。

• 把逻辑地址转换成绝对地址的工作称为“地址重定位”或“地址映射“，又称”地址转换“。

• 按照重定位的时机，可分为静态重定位和动态重定位。

4. 静态重定位

静态重定位是在程序执行之前进行重定位，它根据装配模块将要装入的内存起始位置直接修改装配模块中的有关使用地址的指令。程序中涉及直接地址的每条指令都要进行相应的修改。

• 需要修改的位置称为重定位项；
• 实际装入模块起始地址称为重定位因子。

为了支持静态重定位，连接程序在生成统一地址空间和装配模块时，还应产生一个重定位表。操作系统的装入程序要把装配模块和重定位表一起装入内存。由装配模块的实际装入起始地址得到重定位因子，然后实施如下两步：

1. 取重定位项，加上重定位因子而得到欲修改位置的实际地址
2. 对实际地址中的内容再做加重定位因子的修改，从而完成指令代码的修改。

静态重定位无需硬件支持，但存在着如下缺点：

• 程序重定位之后就不能再在内存中移动；
• 要求程序的存储空间是连续的，不能把程序放在若干个不连续的区域内。

5. 动态重定位

动态重定位是指：在程序执行过程中进行地址重定位，而不是在程序执行之前进行。更确切地说，是在每次访问内存单元前才进行地址转换。

动态重定位可使装配模块不加任何修改而装入内存，但其需要硬件支持：定位寄存器和加法器。

• 实际上就是，静态重定位要手动修改指令中的直接地址；而动态重定位可以在硬件加持下由定位寄存器和加法器自主完成修改。

动态重定位的优势：

• 目标模块装入内存时无需任何修改，因而装入之后再搬迁也不会影响其正确执行。这对于存储器紧凑、解决碎片问题是极其有利的。
• 一个程序由若干个相对独立的目标模块组成时，每个目标模块装入的存储区域之间不必顺序相邻，只需要各个模块有各自对应的定位寄存器。

6. 存储共享

存储共享不仅能使多道程序动态地共享内存，提高内存利用率，还能共享内存中某个区域的信息，包括：代码共享和数据共享。

7. “扩充”内存容量

存储扩充是指利用存储管理软件为进程提供一个比实际内存更大的逻辑存储空间，即虚拟存储管理技术。

0x02 分区存储管理

单道程序的内存管理

• 条件：

  • 在单道程序环境下，整个内存里只有两个程序：一个用户程序和操作系统。
  • 操作系统所占的空间是固定的。
  • 因此可以将用户程序永远加载到同一个地址，即用户程序永远从同一个地方开始运行。

• 结论：

  • 用户程序的地址在运行之前可以计算

• 方法：

  • 静态地址翻译：即在程序运行之前就计算出所有物理地址。
  • 静态翻译工作可以由加载器实现。

• 分析：

  • 地址独立？YES. 因为用户无需知道物理内存的相关知识。
  • 地址保护？YES. 因为没有其它用户程序

• 优点：

  • 执行过程中无需任何地址翻译工作，程序运行速度快。

• 缺点：

  • 比物理内存大的程序无法加载，因而无法运行。
  • 造成资源浪费（小程序会造成空间浪费；I/O时间长会造成计算资源浪费）。

• 思考：

  • 程序可加载到内存中，就一定可以正常运行吗？
  • 用户程序运行会影响操作系统吗

多道程序的内存管理

• 空间的分配：分区式分配

  • 把内存分为一些大小相等或不等的**分区(partition)**，每个应用程序占用一个或几个分区。操作系统占用其中一个分区。
  • 适用于多道程序系统和分时系统，支持多个程序并发执行，但难以进行内存分区的共享。

• 方法：

  • 固定（静态）式分区分配，程序适应分区。
  • 可变（动态）式分区分配，分区适应程序

1. 固定式分区

1）基本思想

固定分区是指系统先把内存划分为若干个固定大小的连续分区。一旦划分好，在系统运行期间便不再重新划分。

• 分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。
• 分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区

采用的数据结构：

• 分区表，记录分区的大小和使用情况

固定式分区的管理

• 优点：易于实现，开销小。
• 缺点：内碎片造成浪费；分区总数固定，限制了并发执行的程序数目。

2）内存分配表与分区的分配、回收

• 单一队列的分配方式
  • 当需要加载程序时，选择一个当前闲置且容量足够大的分区进行加载，可采用共享队列的固定分区（多个用户程序排在一个共同的队列里面等待分区）分配。

• 多队列分配方式
  • 由于程序大小和分区大小不一定匹配，有可能形成一个小程序占用一个大分区的情况，从而造成内存里虽然有小分区闲置但无法加载大程序的情况。
  • 这时，可以采用多个队列，给每个分区一个队列，程序按照大小排在相应的队列里。

2. 可变式分区

1）基本思想

可变分区是指系统不预先划分固定分区，而是在装入程序时划分内存分区，使为程序分配的分区的大小正好等于该程序的需求量，且分区的个数是可变的。

可变式分区的管理：分区的边界可以移动，即分区的大小可变。

• 优点：没有内碎片。
• 缺点：有外碎片。

2）闲置空间管理

为实现可变分区管理，必须解决内存占用情况的记录方式和分配与回收算法两个问题。这就必须跟踪内存的使用，跟踪的办法有两种：位图表示法（分区表）和链表表示法（分区链表）。

位图表示法

给每个分配单元赋予一个字位，用来记录该分配单元是否闲置。例如，字位取值为0表示单元闲置，取值为1则表示已被占用，这种表示方法就是位图表示法。

链表表示法

将分配单元按照是否闲置链接起来，这种方法称为链表表示法。如上图所示的的位图所表示的内存分配状态，使用链表来表示的话则会如下图所示

两种方法的特点

• 位图表示法：

  • 空间成本固定：不依赖于内存中的程序数量。
  • 时间成本低：操作简单，直接修改其位图值即可。
  • 没有容错能力：如果一个分配单元为1，不能肯定应该为1还是因错误变成1。

• 链表表示法：

  • 空间成本：取决于程序的数量。
  • 时间成本高：链表扫描通常速度较慢，还要进行链表项的插入、删除和修改。
  • 有一定容错能力：因为链表有被占空间和闲置空间的表项，可以相互验证

3）分区分配操作

记录内存分配情况，一般采用两张表：P表（已分配分区表）和F表（未分配分区表）。

• 每张表的表项为存储控制块MCB（Memory Control Block），包括AMCB（Allocated MCB）和FMCB（Free MCB）

• 空闲分区控制块按某种次序构成FMCB链表结构。当分区被分配出去以后，前、后向指针无意义

分配内存

• 事先规定 size 是不再切割的剩余分区的大小。

• 设请求的分区大小为 u.size，空闲分区的大小为 m.size。

• 若 m.size - u.size ≤ size，将整个分区分配给请求者。

  • 即如果当前分区分配给该作业后，余下的大小非常小（不足以再分配出去了），也即内碎片。

• 否则，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区表/链中。

回收内存

• 回收分区上邻接一个空闲分区，合并后首地址为空闲分区的首地址，大小为二者之和。
• 回收分区下邻接一个空闲分区，合并后首地址为回收分区的首地址，大小为二者之和。
• 回收分区上下邻接空闲分区，合并后首地址为上空闲分区的首地址，大小为三者之和。
• 回收分区不邻接空闲分区，这时在空闲分区表中新建一表项，并填写分区大小等信息。

4）可变分区分配和释放算法

基于顺序搜索的分配算法

1. 首次适应算法（First Fit）：每个空白区按其在存储空间中地址递增的顺序连在一起，在为作业分配存储区域时，从这个空白区域链的始端开始查找，选择第一个足以满足请求的空白块。

2. 下次适应算法（Next Fit）：把存储空间中空白区构成一个循环链，每次为存储请求查找合适的分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就将它划分后分配出去。

3. 最佳适应算法（Best Fit）：为一个作业选择分区时，总是寻找其大小最接近于作业所要求的存储区域。

4. 最坏适应算法（Worst Fit）：为作业选择存储区域时，总是寻找最大的空白区。

• 算法特点
  • 首次适应算法：
    • 优先利用内存低地址部分的空闲分区。
    • 但由于低地址部分不断被划分，留下许多难以利用的很小的空闲分区（碎片或零头） ，而每次查找又都是从低地址部分开始，增加了查找可用空闲分区的开销。
  • 下次适应算法：
    • 使存储空间的利用更加均衡，不致使小的空闲区集中在存储区的一端，但这会导致缺乏大的空闲分区。
  • 最佳适应算法：
    • 若存在与作业大小一致的空闲分区,则它必然被选中；
    • 若不存在与作业大小一致的空闲分区，则只划分比作业稍大的空闲分区，从而保留了大的空闲分区。
    • 但最佳适应算法往往使剩下的空闲区非常小，从而在存储器中留下许多难以利用的小空闲区（碎片） 。
  • 最坏适应算法：
    • 总是挑选满足作业要求的最大的分区分配给作业。这样使分给作业后剩下的空闲分区也较大，可装下其它作业。
    • 但由于最大的空闲分区总是因首先分配而划分，当有大作业到来时，其存储空间的申请往往会得不到满足。

基于索引搜索的分配算法

基于顺序搜索的动态分区分配算法一般只是适合于较小的系统，如果系统的分区很多，空闲分区表（链）可能很大（很长） ，检索速度会比较慢。为了提高搜索空闲分区的速度，大中型系统采用了基于索引搜索的动态分区分配算法。

• 快速适应算法，又称为分类搜索法

  • 把空闲分区按容量大小进行分类，经常用到长度的空闲区设立单独的空闲区链表。
  • 系统为多个空闲链表设立一张管理索引表。

• 优点：

  • 查找效率高，仅需要根据程序的长度，寻找到能容纳它的最小空闲区链表，取下第一块进行分配即可。
  • 该算法在分配时，不会对任何分区产生分割，所以能保留大的分区，也不会产生内存碎片。

• 缺点：

  • 在分区归还主存时算法复杂，系统开销较大。
  • 在分配空闲分区时是以进程为单位，一个分区只属于一个进程，存在一定的浪费，即空间换时间。

5）移动技术

• 系统初启时，内存中除常驻的操作系统外，其余的是一个完整的大空闲区。
• 随后，对调入的若干作业接连划分几个大小不等的分区分配给它们。
• 在运行一段时间后，随着作业的完成以及相应分区的释放，原来的一整块存储区会形成空闲分区和已分配分区相间的局面，即外碎片，如下图：

解决碎片问题的办法是：

• 紧凑技术（Compaction），即移动技术：在适当时刻，通过移动作业从把多个分散的小分区拼接成一个大分区的方法称为紧凑（拼接或紧缩） 。

  

• 目标：消除外部碎片，使本来分散的多个小空闲分区连成一个大的空闲区。

• 紧凑时机：找不到足够大的空闲分区且总空闲分区容量可以满足作业要求时

• 实现支撑：动态重定位——作业在内存中的位置发生了变化，这就必须对其地址加以修改或变换

  

• 采用移动技术要注意以下问题：

  • 移动技术会增加系统的开销。采用移动技术，需要在内存中进行数据块移动的操作，还要修改内存分配表和进程控制块，增大了系统运行时间。
  • 移动是有条件的。不是任何在内存中的作业都能随时移动。例如，若某个进程正在与外部设备交换信息，那么与该进程有关的数据块就不能移动，必须等到其结束之后。

6）分区的保护

存储保护是为了防止一个作业有意或无意地破坏操作系统或其它作业。常用的存储保护方法有：

• 界限寄存器方法：
  • 上下界寄存器方法
  • 基址、限长寄存器 (BR,LR) 方法

• 存储保护键方法：
  • 给每个存储块分配一个单独的保护键，它相当于一把锁。进入系统的每个作业也赋予一个保护键，它相当于一把钥匙。
  • 当作业运行时，检查钥匙和锁是否匹配，如果不匹配，则系统发出保护性中断信号，停止作业运行

3. 伙伴系统

• 固定分区方式不够灵活，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。
• 动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。
• 伙伴系统 (buddy system)是介于固定分区与可变分区之间的动态分区技术。
  • 伙伴：在分配存储块时将一个大的存储块分裂成两个大小相等的小块，这两个小块就称为“伙伴”

似乎不是重点，略…

4. 分区管理方案的优缺点

分区管理是实现多道程序设计的一种简单易行的存储管理技术。

• 优势：
  • 提高系统的吞吐量并缩短了周转时间；
  • 实现容易，内存额外开销少；
  • 存储保护措施也很简单。
• 缺点：
  • 存在着较为严重的碎片问题，虽然可以通过紧凑技术解决，但浪费了处理及时间；
  • 此外，分区管理不能为用户提供“虚存”，即不能实现对内存的“扩充”。
  • 分区管理要求运行程序一次全部装入内存之后，才能开始运行。这样，内存中可能包含一些实际不适用的信息。

0x03 页式存储管理

程序、进程和作业

• 程序是静止的，是存放在磁盘上的可执行文件

• 进程是动态的。

  • 进程包括程序和程序处理对象（数据集），是一个程序对某个数据集的执行过程，是分配资源的基本单位。
  • 通常把进程分为系统进程和用户进程两大类：
    • 完成操作系统功能的进程称为系统进程；
    • 完成用户功能的进程则称为用户进程。

• 作业是用户需要计算机完成的某项任务，是要求计算机所做工作的集合

进程与程序的区别

进程	程序
进程是程序在处理机上一次执行的过程，是动态的概念。	程序是静态的概念；
进程有生存周期，有诞生有消亡，是短暂的	程序是相对长久的
一个进程也可以运行多个程序	一个程序可以作为多个进程的运行程序
进程具有创建其他进程的功能；	程序没有
进程是竞争计算机系统有限资源的基本单位；进程更能真实地描述并发	程序不能

作业与进程的区别

作业	进程
一个作业的完成要经过作业提交、作业收容、作业执行和作业完成4个阶段。	而进程是对已提交完毕的程序所执行过程的描述，是资源分配的基本单位。
作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业后，系统将它放入外存中的作业等待队列中等待执行。	而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。任一进程，只要它被创建，总有相应的部分存在于内存中。
一个作业可由多个进程组成，且必须至少由一个进程组成	反过来则不成立。
作业的概念主要用在批处理系统中，像UNIX这样的分时系统中就没有作业的概念。	进程的概念则用在几乎所有的多道程序系统中

程序、进程和作业之间的联系

• 一个作业通常包括程序、数据和操作说明书三个部分。
• 每一个进程由进程控制块PCB、程序和数据集合组成。这说明程序是进程的一部分，是进程的实体。
• 因此，一个作业可划分为若干个进程来完成，而每一个进程有其实体——程序和数据集合

1. 基本思想

• 如果可以把一个逻辑地址连续的程序分散存放到若干不连续的内存区域内，并保证程序的正确执行，则既可充分利用内存空间，又可减少移动带来的开销。这就是页式管理的基本思想。

• 页式管理首先由英国Manchester大学提出并使用。支持页式管理的硬件部件通常称为MMU（Memory Management Unit）。

页、页表、页框

• 页：

  • 在分页存储管理系统中，把每个作业的地址空间分成一些大小相等的片，称之为页面（Page）或页；
  • 各页从0开始编号。

• 存储块：

  • 在分页存储管理系统中，把主存的存储空间也分成与页面相同大小的片，这些片称为存储块，或称为页框（Frame）；
  • 同样从0开始编号。

• 页表：

  • 为了便于在内存找到进程的每个页面所对应块，分页系统中为每个进程配置一张页表；
  • 进程逻辑地址空间中的每一页，在页表中都对应有一个页表项

• 页面的大小：

  • 页大小（与块大小一样）是由硬件来决定的,通常为2的幂。选择页的大小为2的幂可以方便的将逻辑地址转换为页号和页偏移。
    • 如果逻辑地址空间为 2^m^，且页大小为 2^n^ 单元，那么逻辑地址的高 m-n 位表示页号（页表的索引），而低n位表示页偏移。每页大小从512B到16MB不等。
    • 现代操作系统中，最常用的页面大小为4KB。
  • 若页面较小
    • 减少页内碎片和总的内存碎片，有利于提高内存利用率。
    • 每个进程页面数增多，使页表长度增加，占用内存较大。
    • 页面换进换出速度将降低。
  • 若页面较大
    • 每个进程页面数减少，页表长度减少，占用内存较小。
    • 页面换进换出速度将提高。
    • 增加页内碎片，不利于提高内存利用率。

• 数据结构

  • 进程页表：
    • 每个进程有一个页表，描述该进程占用的物理页面及逻辑排列顺序；
    • 逻辑页号（本进程的地址空间）-> 物理页面号（实际内存空间）；
  • 物理页面表：
    • 整个系统有一个物理页面表，描述物理内存空间的分配使用状况。
    • 数据结构：位示图，空闲页面链表；
  • 请求表：
    • 整个系统有一个请求表，描述系统内各个进程页表的位置和大小，用于地址转换，也可以结合到各进程的PCB里。

• 关于页表

  • 页表存放在内存中，属于进程的现场信息。

  • 用途：

    1. 记录进程的内存分配情况

    2. 实现进程运行时的动态重定位。

  • 访问一个数据需访问内存 2 次 (页表一次，内存一次)。

  • 页表的基址及长度由页表寄存器给出。

纯分页系统（Pure Paging System）

• 在分页存储管理方式中，如果不具备页面对换功能，不支持虚拟存储器功能，这种存储管理方式称为纯分页或基本分页存储管理方式。
• 在调度一个作业时，必须把它的所有页一次装到主存的页框内；如果当时页框数不足，则该作业必须等待，系统再调度另外作业。
• 优点：
  • 没有外碎片，每个内碎片不超过页大小；
  • 一个程序不必连续存放；
  • 便于改变程序占用空间的大小。
• 缺点：
  • 程序全部装入内存

2. 地址转换

为了实现页式存储管理，系统要提供一对硬件的页表控制寄存器，即页表始址寄存器和页表长度寄存器，另外还需要高速缓冲存储器的支持。

• 页表始址存储器：用于保存正在运行进程的页表在内存的首地址。
• 页表长度寄存器：用于保存正在运行进程的页表的长度。
• 当进程被调度程序选中并投入运行时，系统将其页表首地址和页表长度从PCB中取出并送入这两个寄存器中。

1）一级页表

1. 逻辑地址：地址变换机构把相对地址分为页号和页内地址两部分
2. 页表定位：页表寄存器：页表始址 + 页号 × 页表项长度
   • 如果页号大于或等于页表长度，则表示本次所访问的地址已超越进程的地址空间，产生地址越界中断。
3. 查询页表：读出物理块号
4. 物理地址：块号 + 块内地址。 （块内地址 = 页内地址

• 一级页表的问题
  • 若逻辑地址空间很大 (2^32^ 2^64^ ) ，则划分的页比较多，页表就很大，占用的存储空间大（要求连续） ，实现较困难。
    • 例如，对于 32 位逻辑地址空间的分页系统，如果规定页面大小为 4 KB 即 2^12^ B，则在每个进程页表就由高达 2^20^ 页组成。
    • 设每个页表项占用4个字节，每个进程仅仅页表就要占用 4 MB 的内存空间。
  • 解决问题的方法
    • 动态调入页表：只将当前需用的部分页表项调入内存，其余的需用时再调入。
    • 多级页表

2）多级页表

• 多级页表结构中，指令所给出的地址除偏移地址之外的各部分全是各级页表的页表号或页号，而各级页表中记录的全是物理页号，指向下级页表或真正的被访问页

3）具有快表的地址变换机构

• 快表又称联想存储器 (Associative Memory) 、TLB (Translation Lookaside Buffer) 转换表查找缓冲区。
• 快表是一种特殊的高速缓冲存储器（Cache） ，内容是页表中的一部分或全部内容。
  • CPU 产生逻辑地址的页号，首先在快表中寻找，若命中就找出其对应的物理块；
  • 若未命中，再到页表中找其对应的物理块，并将之复制到快表。
  • 若快表中内容满，则按某种算法淘汰某些页
• 通常，TLB中的条目数并不多，在64~1024之间。

• TLB的性质和使用方法与Cache相同：

  • TLB只包括也表中的一小部分条目。当CPU产生逻辑地址后，其页号提交给TLB。如果页码不在TLB中（称为TLB失效），那么就需要访问页表，并将页号和帧号增加到TLB中。
  • 如果TLB中的条目已满，那么系统会选择一个来替换。替换策略有很多，从最近最少使用替换（LRU）到随机替换等。
  • 另外，有的TLB允许有些条目固定下来。通常内核代码的条目是固定下来的。

• TLB的其它特性

  • 有的TLB在每个TLB条目中还保存地址空间标识码（address-space identifier，ASID）。ASID可用来唯一标识进程，并为进程提供地址空间保护。当TLB试图解析虚拟页号时，它确保当前运行进程的ASID与虚拟页相关的ASID相匹配。如果不匹配，那么就作为TLB失效。
  • 除了提供地址空间保护外，ASID允许TLB同时包含多个进程的条目。如果TLB不支持独立的ASID，每次选择一个页表时（例如，上下文切换时），TLB就必须被冲刷（flushed）或删除，以确保下一个进程不会使用错误的地址转换。

4）哈希页表（hashed page table）

• 处理超过32位地址空间的常用方法是使用哈希页表（hashed page table），并以虚拟页码作为哈希值。

• 哈希页表的每一条目都包括一个链表的元素，这些元素哈希成同一位置（要处理碰撞）。每个元素有3个域：

  1. 虚拟页码
  2. 所映射的帧号
  3. 指向链表中下一个元素的指针。

• 该算法按照如下方式工作：

  • 虚拟地址中的虚拟页号转换为哈希表号，用虚拟页号与链表中的每一个元素的第一个域相比较。
  • 如果匹配，那么相应的帧号（第二个域）就用来形成物理地址，如果不匹配，那么就对链表中的下一个节点进行比较，以寻找一个匹配的页号。

5）反置页表（Inverted page table）

• 问题

  • 一般意义上，每个进程都有一个相关页表。该进程所使用的每个页都在页表中有一项。这种页的表示方式比较自然，这是因为进程是通过页的虚拟地址来引用页的。操作系统必须将这种引用转换成物理内存地址。
  • 这种方法的缺点之一是每个页表可能有很多项。这些表可能消耗大量物理内存，却仅用来跟踪物理内存是如何使用的。如每个使用32位逻辑地址的进程其页表长度均为4MB。

• 反置页表

  • 反置页表不是依据进程的逻辑页号来组织，而是依据该进程在内存中的物理页面号来组织（即：按物理页面号排列）
    • 其表项的内容是逻辑页号 P 及隶属进程标志符 pid 。
  • 反置页表的大小只与物理内存的大小相关，与逻辑空间大小和进程数无关。
    • 如：64M主存,若页面大小为 4K，则反向页表只需 64KB。
  • 如64位的PowerPC, UltraSparc等处理器

• 利用反置页表进行地址变换

  • 用进程标志符和页号去检索反置页表。
  • 如果检索完整个页表未找到与之匹配的页表项，表明此页此时尚未调入内存，对于具有请求调页功能的存储器系统产生请求调页中断，若无此功能则表示地址出错。
  • 如果检索到与之匹配的表项，则表项的序号 i 便是该页的物理块号，将该块号与页内地址一起构成物理地址

• 反向页表按照物理地址排序，而查找依据虚拟地址，所以可能需要查找整个表来寻找匹配。
• 可以使用 哈希页表 限制页表条目或加入 TLB 来改善。
• 通过哈希表(hash table)**查找可由逻辑页号得到物理页面号**。
  • 虚拟地址中的逻辑页号通过哈希表指向反置页表中的表项链头（因为哈希表可能指向多个表项），得到物理页面号。
• 采用反向页表的系统很难共享内存，因为每个物理帧只对应一个虚拟页条目。

3. 页共享与页保护

• 页共享：各进程把需要共享的数据/程序的相应页指向相同物理块。

• 页保护：页式存储管理系统提供了两种方式来进行页保护：

  • 地址越界保护
  • 在页表中设置保护位（定义操作权限：只读，读写，执行等）

• 页共享带来的问题

  • 若共享数据与不共享数据划在同一块中，则有些不共享的数据也被共享，不易保密。
  • 实现数据共享的最好方法：分段存储管理。

0x04 段式存储管理

1）基本思想

分段地址空间

一个段可定义为一组逻辑信息，每个作业的地址空间是由一些分段构成的（由用户根据逻辑信息的相对完整来划分），每段都有自己的名字（通常是段号），且都是一段连续的地址空间，首地址为0。

特点

• 方便编程：

  • 通常一个作业是由多个程序段和数据段组成的，用户一般按逻辑关系对作业分段，并能根据名字来访问程序段和数据段。

• 信息共享：

  • 共享是以信息的逻辑单位为基础的。页是存储信息的物理单位，段却是信息的逻辑单位。
  • 页式管理中地址空间是一维的，主程序，子程序都顺序排列，共享公用子程序比较困难，一个共享过程可能需要几十个页面

• 信息保护：

  • 页式管理中，一个页面中可能装有 2 个不同的子程序段的指令代码，不能通过页面共享实现共享一个逻辑上完整的子程序或数据块。
  • 段式管理中，可以以信息的逻辑单位进行保护。

• 动态增长：

  • 实际应用中，某些段（数据段）会不断增长，前面的存储管理方法均难以实现。

• 动态链接：

  • 动态链接在程序运行时才把主程序和要用到的目标程序（程序段）链接起来

分段管理的优缺点

• 优点：

  • 分段系统易于实现段的共享，对段的保护也十分简单。

• 缺点：

  • 处理机要为地址变换花费时间，要为表格提供附加的存储空间。
  • 为满足分段的动态增长和减少外零头，要采用拼接手段。
  • 在辅存中管理不定长度的分段困难较多。
  • 分段的最大尺寸受到主存可用空间的限制

2）段式地址结构及变换过程

• 段表

  • 段表记录了段与内存位置的对应关系。

  • 段表保存在内存中。

  • 段表的基址及长度由段表寄存器给出

    

  • 访问一个字节的数据/指令需访问内存两次 (段表一次，内存一次)。

  • 逻辑地址由段和段内地址组成

    

• 地址变换过程

  1. 系统将逻辑地址中的段号 S 与段表长度 TL 进行比较。

     • 若 S>TL，表示段号太大，是访问越界，于是产生越界中断信号。
     • 若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存的始址。

  2. 再检查段内地址 d，是否超过该段的段长 SL。

     • 若超过，即 d >SL，同样发出越界中断信号。

     • 若未越界，则将该段的基址与段内地址 d 相加。

       即可得到要访问的内存物理地址。

3）信息共享

例：一个多用户系统，可同时接纳 40 个用户，都执行一个文本编辑程序 (Text Editor)。假设该文本编辑程序有 160KB 的代码和另外 40 KB 的数据区。

• 如果不共享，则总共需有 8 MB 的内存空间来支持 40 个用户。

• 如果 160 KB 的代码是可重入的，则无论是在分页系统还是在分段系统中，该代码都能被共享。 因此在内存中只需保留一份文本编辑程序的副本，此时所需的内存空间仅为1760 KB(40×40+160)，而不是(160+40)×40= 8000 KB 。

  • 可重入代码(Reentrant Code) 又称为“纯代码”(Pure Code)，是一种允许多个进程同时访问的代码。
  • 为使各个进程所执行的代码完全相同，绝对不允许可重入代码在执行中有任何改变。因此，可重入代码是一种不允许任何进程对它进行修改的代码。

分页与分段共享比较

• 在上面例子中，
  • 若采用分页共享，每个进程要使用40个页表项（每个页表项4Byte）共享160K的editor；
  • 在分段系统中，实现共享容易得多，只需在每个进程的段表中为文本编辑程序设置一个段表项

4）分页与分段的比较

• 分页的作业的地址空间是单一的线性地址空间，分段作业的地址空间是二维的。
• “页”是信息的“物理”单位，大小固定。“段”是信息的逻辑单位，即它是一组有意义的信息，其长度不定。
• 分页活动对用户是透明的，而是系统对于主存的管理。分段是用户可见的（分段可以在用户编程时确定，也可以在编译程序对源程序编译时根据信息的性质来划分）

	页式存储管理	段式存储管理
目的	实现非连续分配，解决碎片问题	更好地满足用户需要
信息单位	页（物理单位）	段（逻辑单位）
大小	固定（由系统管理，对用户透明）	不定（由用户程序定，对用户可见）
内存分配单位	页	段
作业地址空间	一维	二维
优点	有效解决了碎片问题（没有外碎片，每个内碎片不超过页大小）； 有效提高内存的利用率，程序不必连续存放。	更好地实现数据共享与保护； 段长可动态增长； 便于动态链接。

0x05 段页式存储管理

1）基本思想

用分段方法来分配和管理虚拟存储器，而用分页方法来分配和管理实存储器。

实现原理

• • 段页式存储管理是分段和分页原理的结合，即先将用户程序分成若干个段（段式） ，并为每一个段赋一个段名，再把每个段分成若干个页（页式） 。

  • 其逻辑地址结构由段号、段内页号、及页内位移三部分所组成。

    

  • 系统中设段表和页表，均存放于内存中。读一字节的指令或数据须访问内存三次，为提高执行速度可增设高速缓冲寄存器。

  • 每个进程一张段表，每个段一张页表。

  • 段表含段号、页表始址和页表长度；页表含页号和块号

2）地址转换

1. PCB 中取出段表始址和段表长度，装入段表寄存器。

   • 将段号与段表长度进行比较，若段号大于或等于段表长度，产生越界中断。

2. 利用段表始址与段号得到该段表项在段表中的位置。

   • 取出该段的页表始址和页表长度。将页号与页表长度进行比较，若页号大于或等于页表长度，产生越界中断。

3. 利用页表始址与页号得到该页表项在页表中的位置。

4. 取出该页的物理块号，与页内地址拼接得到实际的物理地址。

3）实例：X86的段页式地址映射

X86的地址映射机制分为两个部分：

• 段映射机制，将逻辑地址映射到线性地址；
• 页映射机制，将线性地址映射到物理地址

第一阶段：段式地址映射

1. 根据指令的性质来确定应该使用哪一个段寄存器（Segment Selector），例如转移指令中的地址在代码段，而取数据指令中的地址在数据段；
   • CS寄存器：程序指令段起始地址；
   • DS寄存器：程序数据段起始地址；
   • SS寄存器：栈起始地址；
   • ES, FS, GS寄存器：额外段寄存器
2. 根据段存器的内容，找到相应的“地址段描述结构“（Segment Descriptor），段描述结构都放在一个表（Descriptor Table）中（GDT或LDT等），而表的起始地址保存在GDTR、LDTR等寄存器中。
   • GDT（Globle Descriptor Table)：全局描述符表，是全局性的，为所有的任务服务，不管是内核程序还是用户程序，我们都是把段描述符放在GDT中。
   • LDT（Local Descriptor Table）：局部描述符表，为了有效实施任务间的隔离，处理器建议每个任务都应该有自己的描述符表，并且把专属于这个任务的那些段描述符放到LDT中。
3. 从地址段描述结构中找到基地址（Base Address）；
4. 将指令发出的地址作为位移，与段描述结构中规定的段长度相比，看看是否越界；
5. 根据指令的性质和段描述符中的访问权限来确定是否越权；
6. 将指令中发出的地址作为位移，与基地址相加而得出线性地址（Linear Address）

第二阶段：页式地址映射

1. 从CR3寄存器中获取页面目录表（PageDirectory）的基地址；

2. 以线性地址的Directory位段为下标，在目录（Page Directory）中取得相应页面表（Page Table）的基地址；

3. 以线性地址中的Table位段为下标，在所得到的页面表中获得相应的页面描述项；

4. 将页面描述项中给出的页面基地址与线性地址中的offset位段相加得到物理地址。

X86的控制寄存器

控制寄存器（CR0～CR3）用于控制和确定处理器的操作模式以及当前执行任务的特性：

• CR0中含有控制处理器操作模式和状态的系统控制标志；

• CR1保留不用；

• CR2含有导致页错误的线性地址；

• CR3中含有页目录表物理内存基地址，因此该寄存器也被称为页目录基地址寄存器PDBR（Page-Directory Base address Register）。

0x06 覆盖与交换技术

• 例如，一开始内存中只有OS，这时候进程A来了，于是分出一片与进程A大小一样的内存空间；随后，进程B来了，于是在进程A之上分出一片给进程B；然后进程C来了，就在进程B上面再分出一片给C

• 问题

  • 每个程序像叠罗汉一样累计，如果程序B在成型过程中需要更多空间怎么办？（例如在实际程序中，很多递归嵌套函数调用的时候会造成栈空间的增长。
  • 预留一定的空间？OS怎么知道应该分配多少空间给一个程序呢？分配多了，就是浪费；而分配少了，则可能造成程序无法继续执行。
  • 必须解决大作业在小内存中运行的问题

• 解决方法

  • 覆盖与交换技术是在多道程序环境下用来扩充内存和提高内存利用率的两种方法，可以解决在小的内存空间运行大作业的问题。
  • 覆盖技术主要用在早期的 OS 中，交换技术则用在现代OS 中

1. 覆盖技术（Overlay）

• 覆盖：把一个程序划分为一系列功能相对独立的程序段，让执行时不要求同时装入内存的程序段组成一组（称为覆盖段） ，共享主存的同一个区域，这种内存扩充技术就是覆盖。
• 程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，覆盖前面的程序段（内存“扩大”了） 。
• 一般要求作业各模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后由操作系统完成自动覆盖。
• 缺点：对程序员不透明，增加了程序员的负担。

2. 交换技术（Swapping）

• 交换：广义的说，所谓交换就是把暂时不用的某个（或某些）程序及其数据的部分或全部从主存移到辅存中去，以便腾出必要的存储空间；接着把指定程序或数据从辅存读到相应的主存中，并将控制转给它，让其在系统上运行。

• 优点：

  • 增加并发运行的程序数目，并且给用户提供适当的响应时间；
  • 编写程序时不影响程序结构

• 缺点：

  • 对换入和换出的控制增加处理机开销；
  • 程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性

• 交换技术的几个问题

  • 选择原则，即将哪个进程换出/内存？
    • 等待I/O的进程
  • 交换时机的确定，何时需发生交换？
    • 只要不用就换出（很少再用）；
    • 只在内存空间不够或有不够的危险时换出
  • 交换时需要做哪些工作？
  • 换入回内存时位置的确定

3. 覆盖与交换技术的区别

覆盖技术	交换技术
覆盖可减少一个程序运行所需的空间。	交换可让整个程序暂存于外存中，让出内存空间。
覆盖是由程序员实现的，操作系统根据程序员提供的覆盖结构来完成程序段之间的覆盖。	交换技术不要求程序员给出程序段之间的覆盖结构。
覆盖技术主要对同一个作业或程序进行。	交换换主要在作业或程序间之间进行。

0x07 虚拟存储管理

1. 局部性原理

• 问题

  • 程序在执行时，大部分是顺序执行的指令，少部分是转移和过程调用指令。
  • 过程调用的嵌套深度一般不超过5，因此执行的范围不超过这组嵌套的过程。
  • 程序中存在相当多的循环结构，它们由少量指令组成，而被多次执行。
  • 程序中存在相当多对一定数据结构的操作，如数组操作，往往局限在较小范围内

• 局部性原理的概念

  • 指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。还可以表现为：
    • 时间局部性，即一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；
    • 空间局部性，即当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内

2. 虚拟页式存储管理

1）基本思想

基本原理

• 在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。

• 在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页或段入到内存，然后继续执行程序。

• 另一方面，操作系统将内存中暂时不使用的页或段调出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的页或段——即具有请求调入和置换功能，只需程序的一部分在内存就可执行。

• 优点：

  • 可在较小的可用内存中执行较大的用户程序；
  • 可在内存中容纳更多程序并发执行；
  • 不必影响编程时的程序结构（与覆盖技术比较）
  • 提供给用户可用的虚拟内存空间通常大于物理内存(real memory）

虚拟存储技术的特征

• 离散性：

  • 物理内存分配的不连续，虚拟地址空间使用的不连续（数据段和栈段之间的空闲空间，共享段和动态链接库占用的空间）

• 多次性：

  • 作业被分成多次调入内存运行。正是由于多次性，虚拟存储器才具备了逻辑上扩大内存的功能。
  • 多次性是虚拟存储器最重要的特征，其它任何存储器不具备这个特征。

• 对换性：

  • 允许在作业运行过程中进行换进、换出。
  • 换进、换出可提高内存利用率

• 虚拟性：

  • 虚拟存储器机制允许程序从逻辑的角度访问存储器，而不考虑物理内存上可用的空间数量。
  • 范围大，但占用容量不超过物理内存和外存交换区容量之和。
  • 占用容量包括：进程地址空间中的各个段，操作系统代码

• 虚拟性以多次性和对换性为基础，多次性和对换性必须以离散分配为基础

与Cache-主存机制的异同

• 透明性不同：
  • cache的管理完全由硬件完成，对系统程序员和应用程序员均透明；而虚存管理由软件（OS）和硬件共同完成，由于软件的介入，虚存对实现存储管理的系统程序员不透明，而只对应用程序员透明（段式和段页式管理对应用程序员“半透明”）。
• 未命中时的损失不同：
  • 由于主存的存取时间是cache的存取时间的5～10倍，而主存的存取速度通常比辅存的存取速度快上千倍，故主存未命中时系统的性能损失要远大于cache未命中时的损失

人类活动与生活的借鉴

关于虚拟内存

• 虚拟内存不只是“用磁盘空间来扩展物理内存”的意思——这只是扩充内存级别以使其包含硬盘驱动器而已。
• 把内存扩展到磁盘只是使用虚拟内存技术的一个结果，它的作用也可以通过覆盖或者把处于不活动状态的程序以及它们的数据全部交换到磁盘上等方式来实现。
• 对虚拟内存的定义是基于对地址空间的重定义的，即把地址空间定义为“连续的虚拟内存地址”，以借此“欺骗”程序，使它们以为自己正在使用一大块的“连续”地址。

2）请求式分页管理系统

一些基本概念

进程的逻辑空间（虚拟空间）

• 一个进程的逻辑空间的建立是通过链接器（Linker），将构成进程所需要的所有程序及运行所需环境，按照某种规则装配链接而形成的一种规范格式(布局)，这种格式按字节从0开始编址所形成的空间也称为该进程的逻辑地址空间。
• 其中OS所使用的空间称为系统空间，其它部分称为用户空间。系统空间对用户空间不可见。后面只讨论用户可见部分。
• 由于该逻辑空间并不是真实存在的，所以也称为进程的虚拟（地址）空间。
• 如：Hello Word进程包含Hello Word可执行程序、printf函数（所在的）共享库程序以及OS相关程序

虚拟地址空间和虚拟存储空间

• 进程的虚拟地址空间即为进程在内存中存放的逻辑视图。因此，一个进程的虚拟地址空间的大小与该进程的虚拟存储空间的大小相同，且都从0开始编址。有些书中也将虚拟存储空间称虚拟内存空间。
• 含有空白的虚拟地址空间称为稀疏（sparse）地址空间

交换分区（交换文件）

• 是一段连续的磁盘空间（按页划分的），并且对用户不可见。

• 它的功能就是在物理内存不够的情况下，操作系统先把内存中暂时不用的数据，存到硬盘的交换空间，腾出物理内存来让别的程序运行。

• 在Linux系统中，交换分区为Swap；在Windows系统中则以文件的形式存在（pagefile.sys)。

• 交换器的大小：交换分区的大小应当与系统物理内存（M）的大小保持线性比例关系(Linux中）：

  If (M < 2G) Swap = 2\*M
  else 		Swap = M+2

  • 原因在于，系统中的物理内存越大， 对于内存的负荷可能也越大

实存管理与虚存管理

• 实存管理：

  • 分区（Partitioning） （连续分配方式） （包括固定分区、可变分区）
  • 分页（Paging）
  • 分段（Segmentation）
  • 段页式（Segmentation with paging）

• 虚存管理：

  • 请求分页（Demand paging）– 主流技术
  • 请求分段（Demand segmentation）
  • 请求段页式（Demand SWP

请求式分页系统

• 在运行作业之前，只要求把当前需要的一部分页面装入主存。当需要其它的页时，可自动的选择一些页交换到辅存去，同时把所需的页调入主存。

• 虚拟存储系统：控制自动页面交换而用户作业意识不到的那个机构，称为虚拟存储系统

请求式分页管理的页表

在使用虚拟页式存储管理时需要在页表中增加以下表项：

• 页号：页面的编号。

• 驻留位：1表示该页位于内存当中，0，表示该页当前还在外存当中。

• 内存块号：页面在内存中时，所对应的内存块号。

• 外存地址：页面在外存中时，所在的外存地址。

• 保护位：只读、可写、可执行。

• 修改位：表明此页在内存中是否被修改过。

• 访问（统计）位：用于页面置换算法。

请求分页与请求分段系统的比较

	请求分页系统	请求分段系统
基本单位	页	段
长度	固定	可变
分配方式	固定分配	可变分配
复杂度	较简单	较复杂

2）缺页中断（重要）

在实际系统中，用户作业当前用到的页面放在主存中，其他的页面则放在磁盘上。当进程执行过程中需访问的页面不在物理存储器中时，会引发发生缺页中断，进行所需页面调入，步骤如下：

1. 陷入内核态，保存必要的信息（OS及用户进程状态相关的信息）。（现场保护）

2. 查找出来发生页面中断的虚拟页面（进程地址空间中的页面）。这个虚拟页面的信息通常会保存在一个硬件寄存器中，如果没有的话，操作系统必须检索程序计数器，取出这条指令，用软件分析该指令，通过分析找出发生页面中断的虚拟页面。（页面定位）

3. 检查虚拟地址的有效性及安全保护位。如果发生保护错误，则杀死该进程。（权限检查）

4. 查找一个空闲的页框(物理内存中的页面)**，如果没有空闲页框则需要通过页面置换算法找到一个需要换出的页框。（新页面调入（1））**

5. 如果找的页框中的内容被修改了，则需要将修改的内容保存到磁盘上¹。（注：此时需要将页框置为忙状态，以防页框被其它进程抢占掉）（旧页面页面写回）

6. 页框“干净”后，操作系统将保持在磁盘上的页面内容复制到该页框中²。（新页面调入（2））此时会引起一个写磁盘调用，发生上下文切换（在等待磁盘写的过程中让其它进程运行）

7. 当磁盘中的页面内容全部装入页框后，向操作系统发送一个中断。操作系统更新内存中的页表项，将虚拟页面映射的页框号更新为写入的页框，并将页框标记为正常状态。（更新页表）

8. 恢复缺页中断发生前的状态，将程序指针重新指向引起缺页中断的指令。（恢复现场）

9. 程序重新执行引发缺页中断的指令，进行存储访问。（继续执行）

缺页处理过程涉及了用户态和内核态之间的切换，虚拟地址和物理地址之间的转换（这个转换过程需要使用MMU和TLB），

3）页面调度策略

0. 调度问题

1. 调入什么？（什么程序和数据调入主存）

   • OS的核心部分的程序和数据；
   • 正在运行的用户进程相关的程序及数据。

2. 何时调入？

   • OS在系统启动时调入。
   • 用户程序的调入取决于调入策略。

3. 如何调入？

   • 缺页错误处理机制，置页策略和置换策略。

虚拟存储器系统通常定义三种策略来规定如何（或何时）进行页面调度：调入策略、置页策略和置换策略。

I. 调入策略

调入策略决定什么时候将一个页由外存调入内存之中，有两种常用调入策略：

• 请求调页（demand paging）：也称按需调页，只调入发生缺页时所需的页面。
  • 这种调入策略实现简单，但容易产生较多的缺页中断，造成对外存I/O次数多，时间开销大，容易产生抖动现象。
• 预调页（prepaging）：即实现调入页面的策略，在发生缺页需要调入某页时，一次调入该页以及相邻的几个页。
  • 这种策略提高了调页的I/O效率，减少了I/O次数。但由于这是一种基于局部性原理的预测。若调入后的页在以后很少被访问，则造成浪费。
  • 这种方式常在程序装入时使用。

II. 置页策略

当线程产生缺页中断时，内存管理器还必须确定将调入的虚拟页放在物理内存的何处。用于确定最佳位置的一组规则称为“置页策略”。选择页框时应考虑使CPU内存高速环从不必要的震荡最小。

III. 置换策略

如果缺页中断发生时物理内存已满，“置换策略”被用于确定哪个虚页面必须从内存中移出，为新的页面腾出空位。

• 在页式系统中，可采用两种分配策略：即固定和可变分配策略。
• 在进行置换时，也可以采用两种策略：即全局置换和局部置换。

将它们结合起来，有如下三种策略：

• 固定分配局部置换（fixed allocation, local replacement）：
  • 为每一进程分配固定页数的内存空间，在整个运行期间都不再改变。
  • 如果进程在运行中出现缺页，则只能从该进程的N个页面中选出一个换出，然后再调入一页，以保证分配给该进程的内存空间不变。
• 可变分配全局置换（variable allocation, global replacement）：
  • 先为每一进程分配一定数量的物理块，操作系统本身也保持一个空闲物理块队列。
  • 如果进程在运行中出现缺页，由系统的空闲物理块队列中取出一物理块分配给该进程；当队列中的物理块用完时，操作系统才从内存中选择一块调出。该块可能是系统中任意一个进程的页。
  • 全局置换算法存在的一个问题是，程序无法控制自己的缺页率。
    • 一个进程在内存中的一组页面不仅取决于该进程的页面走向，而且也取决于其他进程的页面走向。因此，相同程序由于外界环境不同会造成执行上的很大差别。
    • 使用局部置换算法就不会出现这种情况，一个进程在内存中的页面仅受本进程页面走向的影响。
• 可变分配局部置换（variable allocation, local replacement）：
  • 为每一进程分配一定数目的内存空间。
  • 当进程的页框全部用完，出现缺页，需要装入一个新的页面时，系统将在该进程的当前驻留集中（即只允许从该进程的页面中选出一页换出）选择一个页面换出内存。
  • 如果进程在运行中频繁地发生缺页中断，则系统再为该进程分配若干物理块，直到进程的缺页率降低到适当程度为止。

4）页面置换算法

（1）先进先出（First-in, First-out，FIFO）

• 基本思想：最简单的页置换算法，操作系统记录每个页被调入内存的时间，当必需置换掉某页时，选择最旧的页（即驻留时间最长的一页）换出。
• 实现方法：
  • 新访问的页面插入FIFO队列尾部，页面在FIFO队列中顺序移动；
  • 淘汰FIFO队列头部的页面；

• 特点
  • 性能较差。较早调入的页往往是经常被访问的页，这些页在FIFO算法下被反复调入和调出，并且有Belady现象。
  • 这种算法仅在按线性顺序访问地址空间时才是最理想的。

Belady现象

• 在使用FIFO算法作为缺页置换算法时，分配的缺页增多，但缺页率反而提高，这样的异常现象称为belady Anomaly。
• 虽然这种现象说明的场景是缺页置换，但在运用FIFO算法作为缓存算法时，同样也是会遇到，增加缓存容量，但缓存命中率也会下降的情况。

改进的FIFO算法——Second Chance

• 基本思想：如果被淘汰的数据之前被访问过，则给其第二次机会（Second Chance）。

• 实现方法：

  • 每个页面会增加一个访问标志位，用于标识此数据放入缓存队列后是否被再次访问过。
  • A是FIFO队列中最旧的页面，且其放入队列后没有被再次访问，则A被立刻淘汰；否则如果放入队列后被访问过，则将A移到FIFO队列头，并且将访问标志位清除。
  • 如果所有的页面都被访问过，则经过一次循环后就会按照FIFO的原则淘汰

改进的FIFO算法— Clock

• 基本思想：Clock是Second Chance的改进版，也称**最近未使用算法(NRU, Not Recently Used)**。通过一个环形队列，避免将数据在FIFO队列中移动。
• 实现方法：
  • 如果没有缺页错误，将相应的页面访问位置1，指针不动
  • 产生缺页错误时，当前指针指向C：
    • 如果C被访问过，则清除C的访问标志，并将指针指向D；
    • 如果C没有被访问过，则将新页面放入到C的位置，置访问标志位为1，并将指针指向D。

FIFO类算法对比

对比点	对比
命中率	Clock = Second Chance > FIFO
复杂度	Second Chance > Clock > FIFO
代价	Second Chance > Clock > FIFO

由于FIFO类算法命中率相比其他算法要低不少，因此实际应用中很少使用此类算法。

（2）最近最久未使用（Least Recently Used Replacement，LRU）

• 基本思想：

  • LRU算法根据数据的历史访问记录来进行淘汰数据，当需要置换一页面时，选择在最近一段时间内最久不用的页面予以淘汰。
  • 其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”（局部性原理）

• 实现方法一：

  • 每一页可设计一个标志位，每当访问某一页时，将该页的标志位的值从0变成1。
  • 周期性地检查每一页的标志位，看看哪些页被访问过

• 实现方法二：

  • 设置一个特殊的栈，保存当前使用的各个页面的页面号。
  • 每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。
  • 栈底始终是最近最久未使用页面的页面号

*老化算法（AGING）

LRU算法开销很大，硬件很难实现，老化算法是LRU的简化，但性能接近LRU。

• 为每个页面设置一个移位寄存器，并设置一位访问位R，每隔一段时间，所有寄存器右移1位，并将R值从左移入。

（3）最不频繁使用（LFU）

• 基本思想：把最不常用的页面先淘汰。

• 实现方法：每一页可设计一个计数器，每访问一次后，将该页的计数器加1，然后淘汰计数值最小的页。

（4）最优置换策略（Optimal，OPT）

• 基本思想：从主存中移出永远不再需要的页面，如无这样的页面存在，则应选择最长时间不需要访问的页面

（5）补救措施

上面淘汰算法的目的在于减少页面交换次数，节约处理机时间。除此之外还可以采取一些补救措施来减少页面交换次数：

• 作业进入执行状态之前，输入并保存作业的全部信息，根据作业的执行情况，“分期分批”进入内存。

• 为了避免发生缺页中断而临时进行页面交换，可采用所谓预淘汰方式，其思想是：

  • 在内存中保持有少量空页，当发生缺页中断时，直接从外存调入所需的页面，而不利己淘汰暂不需要的页面。
  • 而未发生缺页中断时，根据淘汰算法再淘汰某些页面
  • 有点类似cache的思想。

• 优化访问磁盘次序（文件系统中的磁盘调度问题）。

5）缺页中断率

假定一个程序共有n页，系统分配给它的内存块是m块（m <= n）。因此该程序最多有m页可同时被装入内存。如果程序执行中访问页面的总次数为A，其中产生了F次缺页中断，则 $f = \frac{F}{A}$ 称为“缺页中断率”。

影响缺页中断率的因素

• 分配给程序的内存块数
• 页面的大小
• 程序编制方法
• 页面调度算法

6）页式存储管理的保护措施

• 界限保护（上下界界限地址寄存器）
• 存取控制检查
• 用户态与内核态
• 环保护：
  • 处理器状态分为多个环(ring)，分别具有不同的存储访问特权级别(privilege)，通常是级别高的在内环，编号小（如0环）级别最高；
  • 可访问同环或更低级别环的数据；可调用同环或更高级别环的服务

7）页共享

写时复制技术

两个进程共享同一块物理内存，每个页面都被标志成了写时复制。

• 共享的物理内存中每个页面都是只读的。如果某个进程想改变某个页面时，就会与只读标记冲突，而系统在检测出页面是写时复制的，则会在内存中复制一个页面，然后进行写操作。新复制的页面对执行写操作的进程是私有的，对其他共享写时复制页面的进程是不可见的。

写时复制的优点

• 传统的fork()系统调用直接把所有的资源复制给新创建的进程。这种实现过于简单而效率低下，因为它拷贝的数据也许并不共享，如果新进程打算立即执行一个新的映像，那么所有的拷贝都将前功尽弃。Linux的fork()使用写时拷贝(copy-on-write)实现，它可以推迟甚至免除拷贝数据的技术。内核此时并不复制整个进程地址空间，而是让父进程和子进程共享同一个拷贝。只有在需要写入的时候，数据才会复制，从而使各个进程都拥有各自的拷贝。也就是说，资源的复制只有在需要写入的时候才进行

内存映射文件(Mem-Mapped File)

• 基本思想：进程通过一个系统调用（mmap）将一个文件（或部分）映射到其虚拟地址空间的一部分，访问这个文件就像访问内存中的一个大数组，而不是对文件进行读写。
• 在多数实现中，在映射共享的页面时不会实际读入页面的内容，而是在访问页面时，页面才会被每次一页的读入，磁盘文件则被当作后备存储。
• 当进程退出或显式地解除文件映射时，所有被修改页面会写回文件。
• 采用内存映射方式，可方便地让多个进程共享一个文件

7）抖动问题

前面我们从一个进程的角度，讨论了虚存管理中的相关问题，下面我们将从系统管理者的角度（OS的视角）讨论多个进程同时存在，虚存管理中的问题。

• 进程的工作集（working set）：当前正在使用的页面的集合。
• 进程的驻留集（Resident Set ）：虚拟存储系统中，每个进程驻留在内存的页面集合，或进程分到的物理页框集合。

工作集

工作集是指进程运行时被频繁访问的页面集合。引入工作集的目的是依据进程在过去的一段时间内访问的页面来调整驻留集大小。

• 工作集大小的变化：

  • 进程开始执行后，随着访问新页面逐步建立较稳定的工作集。
  • 当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定；
  • 局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值。

• 获得精确工作集的困难：

  • 工作集的过去变化未必能够预示工作集的将来大小或组成页面的变化；
  • 记录工作集变化要求开销太大；
  • 对工作集窗口大小的取值难以优化，而且通常该值是不断变化的

驻留集

进程驻留集管理主要解决的问题是，系统应当为每个活跃进程分配多少个页框。

• 影响页框分配的主要因素：
  • 分配给每个活跃进程的页框数越少，同时驻留内存的活跃进程数就越多，进程调度程序能调度就绪进程的概率就越大。
  • 然而，这将导致进程发生缺页中断的概率较大；为进程分配过多的页框，并不能显著地降低其缺页中断率

抖动问题(thrashing)

• 随着驻留内存的进程数目增加，或者说进程并发水平(multiprogramming level)的上升，处理器利用率先是上升，然后下降。
• 这里处理器利用率下降的原因通常称为虚拟存储器发生“抖动”，也就是：每个进程的驻留集不断减小，当驻留集小于工作集后，缺页率急剧上升频繁调页使得调页开销增大。
• OS要选择一个适当的进程数目，以在并发水平和缺页率之间达到一个平衡

抖动的消除与预防

• 局部置换策略：如果一个进程出现抖动，它不能从另外的进程那里夺取内存块，从而不会引发其他进程出现抖动，使抖动局限于一个小的范围内。 然而这种方法并未消除抖动的发生。（微观层面）
• 引入工作集算法（微观）
• 预留部分页面（微观或宏观）
• 挂起若干进程：当出现CPU利用率、而磁盘I/O非常频繁的情况时，就可能因为多道程序度太高而造成抖动。为此，可挂起一个或几个进程，以便腾出内存空间供抖动进程使用，从而消除抖动现象。（宏观）

问题：如何从宏观层面预防抖动？

负载控制（宏观）

• 多道程序系统允许多个进程同时驻留内存，以提高系统吞吐量和资源利用率。然而，如果同时驻留的进程数量太多，每个进程都竞争各自需要的资源，反而会降低系统效率。

  • 如果内存中进程太多，将导致每个进程的驻留集太小，发生缺页中断的概率很大，系统发生抖动的可能性就会很大。
  • 如果在内存中保持太少的活动进程，那么所有活动进程同时处于阻塞状态的可能性就会很大，从而降低处理机的利用率。

• 负载控制主要解决系统应当保持多少个活动进程驻留在内存的问题，即控制多道程序系统的度。当内存中的活动进程数太少时，负载控制将增加新进程或激活一些挂起进程进入内存；反之，当内存中的进程数太多时，负载控制将暂时挂起一些进程，减少内存中的活动进程数

• 系统负载的判断

  • L=S准则
    • 通过调整多道程序的度，使发生两次缺页之间的平均时间（L）等于处理一次缺页所需要的平均时间（S）。即平均地，一次缺页处理完毕，再发生下一次缺页。此时，处理机的利用率将达到最大。
  • 50%准则
    • 当分页单元的利用率保持在50%左右时，处理机的利用率将达到最大。如果系统使用基于CLOCK置换算法的全局置换策略，可通过监视扫描指针的移动速率来调整系统负载。如果移动速率低于某个给定的阀值，则意味着近期页面失败的次数较少，此时可以增加驻留内存的活动进程数。如果超出阀值，则近期页面失败的次数较多，此时，系统应当减少驻留内存的活动进程数

可挂起的进程

• 优先级最低的进程；
• 缺页进程：因为发生缺页中断的进程处于阻塞状态，暂时不需要竞争处理机的使用权。而且，挂起一个缺页进程时，挂起和激活操作需要的数据交换将消除页替换的开销；
• 最后一个被激活的进程 ：因为为此类进程装入的页面较少。将其挂起的开销较小；
• 驻留集最小的进程：将该类进程挂起以后，激活所需的开销较小；
• 最大的进程：挂起最大的进程将获得最多的内存空间，可以满足内存中的进程申请空闲页框的需要，使它们能尽快执行完成

0x08 存储管理实例

略

考点积累

1. 常考知识点

• 覆盖技术是早期在单一连续区存储管理中使用的扩大存储容量的一种技术。

• 页式存储管理的特点是不要求作业装入到内存的连续区域，而页式虚拟管理的特点是不要求作业同时全部装入到内存的连续区域。

• 采用分段式存储管理没有内碎片

  • 在分段式存储管理系统中，为每个段分配一个连续的分区，分区大小等于分段大小，分区内没有内部碎片。

• 分段存储管理有利于程序的动态链接。

  • 动态链接机制是为了各个进程共享动态链接库中的函数，提高了内存利用率。

  • 分段虚拟存储管理中的每个段式按照程序逻辑意义上划分的，如一个函数为一个端，动态链接库中的函数可以作为一个段来管理。相比分页虚拟存储管理，分段机制可节省短标占用的空间。

  • 目前流行的通用操作系统如Windows、Linux操作系统都是使用分页虚拟存储管理方法，当然也使用动态链接技术。

• 虚拟存储器的最大容量由CPU的地址长度决定。

  • 虽然从实际使用来说，虚拟存储器使得进程可使用内存扩大到内外存容量之和；但是进程的内存寻址还是由计算机的地址结构决定，这就决定了虚拟存储器理论上的最大容量。
  • 比如，64位系统环境下，虚拟内存技术使得进程可用内存空间达264B，但外存显然是达不到这个大小的。

• 在实现段共享时，共享程序段必须是可重入代码或是“纯代码”。它是一种允许多个进程同时访问的代码，是一种不允许任何进程在执行的过程中对齐进行修改的代码。

• 程序加载时并不一次性将所有程序调入内存，而仅将程序的一部分装入内存，这体现了局部性原理。

• 根据存储管理中内、外碎片的定义。

  • 固定分区管理、页式存储管理、段页式管理有内碎片，没有外碎片。
  • 动态分区管理和段式存储管理有外碎片，没有内碎片。

• 请求分页系统的页面大小是相同的。

• 段表长度在分段式存储管理中用作存储保护。

• 在进行地址变换时，系统将逻辑地址截成段号和段内地址两部分，将段号与段表长度进行比较，如果段号大于等于段表寄存器中的段表长度，则访问越界，产生越界中断。

• 最优（最佳）置换算法产生缺页率最小，但不是实用的页面淘汰算法

• 在采用请求分页式存储管理的系统中，地址变换过程可能会因为缺页、地址长度越界和越权访问等原因而产生的中断。

• 分区存储管理不能实现虚拟的原因是分区管理要求运行程序一次性全部装入主存，因而作业地址空间不能超过存储空间。

• 虚拟存储器通常由主存和辅存两级存储系统组成。

• 静态重定位是由专门设计的重定位装配程序完成的，而动态重定位是靠硬件地址变换机构（即定位寄存器和加法器）来实现的。

• 在段式存储管理中，段的保护措施通常有越界保护和存取控制两种方式。

• 在可变分区存储管理中，分区的保护通常由界限寄存器和存储保护键两种方式。

• 在存储管理方案中，可用上、下限地址寄存器存储保护的是分区分配。

• 交换技术获得的好处是以牺牲CPU时间为代价的，是一种时间换空间的技术。

• 在请求分页系统中，页面置换算法常用的是FIFO和LRU。

• 段表表目的主要内容包括：段号、段长、段在内存中的起始地址。

• 页表表目的主要内容包括：页号、块号。

• 在段式虚拟存储管理系统中，程序所使用的的最大段数以及端的最大长度是由逻辑地址结构决定的。

• 动态页式系统中的页表项比静态页式系统中页表项增加了存在（中断位）、修改位和外存地址，决定淘汰页是否协会外村的页表项中的依据是修改位。

2. 错题积累

• CPU利用率20%，说明系统运行进程的时间比例不高。
• 对换空间的磁盘利用率已达97.7%，说明交换操作非常频繁。
• 由此断定物理内存严重短缺，可以通过增加内存条来增加物理空间容量。

• 联想存储器用以存放当前访问的那些页表项，每个页表项包括页号和相应的块号，用于地址变换。

• 根据程序的局部性理论，Denning提出了工作集理论。工作集是指进程运行时被频繁访问的页面集合。虽然程序只需少量的几页内存就可以运行，但为了使程序更有效地运行，必须使程序的工作集全部在内存(主存储器)当中，否则会使进程在运行中频繁出现缺页中断，从而出现频繁的页面调入/调出现象，造成系统性能急剧下降，严重时会出现“抖动”现象。
• 若页面在内存中，不会产生缺页中断，也即不会出现页面的调入/调出。

• 段式管理时用户使用的逻辑地址是不连续的
• 地址映射一定要有硬件地址转换机制作支持
• 页表由系统确定
• 采用静态充电位不能实现程序浮动。

（2017北航真题）假设只考虑页内碎片和页表引起的额外内存开销。如进程本身占用内存的平均大小是1MB，每个页表项的大小是8B，为减小额外的内存开销，页面大小应设置为 3KB 。

• 设页面大小为 x KB。
• 平均每个进程需要占 1MB /x KB = 2^10^ / x个页框
• 页表中有 x KB / 8B = 2^7^x 个页表项
• 由于每个进程对应一个页表，一个页表项对应一页，因此每个进程所占页框不能超过页表中的页表项，即 2^10^/x < 2^7^x ，x^2^ > 8 ，x = 3。