预备知识：链接与装载
gcc调用包含的几个工具
- cc1: 预处理和编译器
- as: 汇编器
- collect2: 链接器
ELF(Executable and Linkable Format)——可执行文件格式
几个重要节头：
- .bss: 存储未初始化的全局变量和静态变量。此节类型是SHT_NOBITS,因此不占⽂件空间
- .data: 存储已初始化的全局变量和静态变量。
- .text: 存放正文，也称程序的执行指令
.bss、.data节是数据段的组成部分
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： 与节名字符串表相关的节头表。
节头表更关注于文件内部各个节的属性信息，而程序（段）头表则关注于程序执行时的段信息。
段是由多个节组成的，多个节经过重定位后形成一个段。段主要用于描述程序在内存中的布局和加载方式。例如，在创建两个汇编文件时，每个文件都有自己的数据节（.data）。当这两个文件链接在一起时，它们的数据节会组合在一起形成一个数据段。同样，代码节也会组合形成代码段。
链接
将.o文件链接到一起，形成最终的可执行文件
- E重定位目标文件
- U未解析符号
- D已定义符号
程序入口点：_start函数
三种链接方式
- 静态链接：装入前连接成一个完整装入模块
- 装入时动态链接：运行前边装入边链接
- 运行时动态链接：运行时需要目标模块才装入并链接
三种装入方式
- 绝对装入：编译时产生绝对地址（单道程序阶段，无操作系统）
- 可重定位装入：装入时将逻辑地址转换为物理地址（早期多道批处理阶段）
- 动态运行时装入：运行时将逻辑地址转换为物理地址，需设置重定位寄存器（现代操作系统）
装载和运行
- shell调用fork()系统调用，创建出一个子进程（装载前的工作）
- 子进程调用execve()加载program（开始装载）
- 读取ELF头部的魔数(Magic Number)，以确认该文件确实是ELF文件
- 找到段表项
- 对于每个段表项解析出各个段应当被加载的虚地址，在文件中的偏移。以及在内存中的大小和在文件中的大小。（段在文件中的大小 <= 内存中的大小）
- 对于每一个段，根据其在内存中的大小，为其分配足够的物理页，并映射到指定的虚地址上。再将文件中的内容拷贝到内存中
- 若ELF中记录的段在内存中的大小大于在文件中的大小，则多出来的部分用0进行填充。
- 设置进程控制块中的PC为ELF文件中记载的入口地址
- 控制权交给进程开始执行！
存储管理基础
存储保护
保证各进程在自己的内存空间内运行，不会越界访问
两种方法：
界限寄存器方法
两种方式：
- 设置上下限寄存器
- 利用重定位寄存器（基址寄存器）、界地址寄存器（限长寄存器）进行判断
存储保护键方法
给每个存储块分配一个单独的保护键，它相当于一把锁。进入系统的每个作业也赋予一个保护键，它相当于一把钥匙。当作业运行时，检查钥匙和锁是否匹配，如果不匹配，则系统发出保护性中断信号，停止作业运行
覆盖与交换：解决分区管理问题
覆盖技术（主要用于早期的OS）
- 一个固定区：存放最活跃的程序段，固定区中的程序段在运行中不会调入调出
- 若干个覆盖区：不可能同时被访问程序段可共享一个覆盖区，覆盖区中的程序段在运行过程中会根据需要调入调出
必须由程序员声明覆盖结构，操作系统完成自动覆盖
缺点：对用户不透明，增加了用户编程负担
补充：计算机领域“透明”的含义
在计算机术语中，”透明”通常指的是一种操作或过程对用户或其他系统的影响被隐藏或减轻到最小程度，以使其表现为无缝、不可察觉或无需用户干预。这种透明性的目标是使系统更易于使用、更具可靠性，并减少对终端用户或其他系统组件的干扰。
通俗来讲：看不见，不用管它（系统管理员或者开发者无需显式干预和管理）。那么“不透明”就是指开发人员要考虑怎么用它。
交换技术
内存紧张时，换出某些进程以腾出内存空间，再换入某些进程。
磁盘分为文件区和对换区，换出的进程放在对换区。
覆盖与交换的区别
- 覆盖：同一个程序或进程中的
- 交换：不同进程（或作业）之间的
连续分配管理
单一连续分配：只支持单道程序，内存分为系统区和用户区，用户程序放在用户区。
无外部碎片，有内部碎片
固定分区分配：支持多道程序，内存用户空间分为若干个固定大小的分区，每个分区只能装一道作业
无外部碎片，有内部碎片
两种分区方式
- 分区大小相同
- 分区大小不同
两种分配方式
- 单一队列的分配方式：当需要加载程序时，选择一个当前闲置且容量足够大的分区进行加载，可采用共享队列的固定分区（多个用户程序排在一个共同的队列里面等待分区）分配
- 多队列分配方式：给每个分区一个队列，程序按照所需内存的大小排在相应的队列里。避免小程序占用大分区，导致大程序无法加载。
可变式分区（动态分区分配）：支持多道程序，在进程装入内存时，根据进程动态地建立分区
无内部碎片，有外部碎片。外部碎片可用紧凑技术解决
闲置空间管理
在管理内存时，OS需要知道内存空间有多少空闲。这就必须跟踪内存的使用，跟踪的办法有两种：
位图表示法（分区表）
空间开销固定：不依赖于内存中的程序数量。
时间开销低：操作简单，直接修改其位图值即可。
没有容错能力：如果一个分配单元对应的标志位为1，不能确定是否因错误变成1。
链表表示法（分区链表）
空间开销：取决于程序的数量。
时间开销：链表扫描速度较慢，还要进行链表项的插入、删除和修改
有一定容错能力：因为链表有被占空间和闲置空间的表项，可相互验证
分配内存
若m.size（空闲分区的大小）- u.size（请求的分区大小）≤size （规定当剩余空闲分区≤ size时，不再进一步分割），将整个分区分配给请求者。否则，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区表/链中
回收内存
- 待回收分区与前一个空闲分区邻接：合并后首地址为空闲分区的首地址，大小为二者之和。
- 待回收分区与后一个空闲分区邻接：合并后首地址为回收分区的首地址，大小为二者之和。
- 待回收分区与前后两个空闲分区邻接：合并后首地址为前一个空闲分区的首地址，大小为三者之和。
- 待回收分区不与空闲分区邻接：在空闲分区表中新建
分配算法
基于顺序搜索的分配算法：适合于较小的系统
首次适应：每个空闲区按其在存储空间中地址递增的顺序连在一起。为作业分配存储空间时，从这个空闲区域链始端开始查找，选择第一个满足的空白块
缺点：留下碎片，查找时间开销大
下次适应：把空闲区构建成一个循环链表。每次从上次查找结束的地方开始，只要找到能装的就分配出去
优点：存储空间利用更均衡
缺点：缺乏大的空闲分区
最佳适应：找大小与作业所需存储区域最接近的
缺点：留下碎片
最坏适应：每次都找最大空闲区
优点：分给一个作业后剩下的空闲分区也较大，可以装下其他作业
缺点：大作业的空间申请难以满足
基于索引搜索的分配算法：大中型系统，提高搜索空闲分区的速度
快速适应算法（/分类搜索法）：把空闲分区按容量大小进行分类，常用大小的空闲区设立单独的空闲区链表。系统为多个空闲链表设立一张管理索引表
优点：查找效率高；保留大分区，不会产生内存碎片
缺点：分区回收算法复杂
伙伴系统（Linux系统采用）：在分配存储块时将一个大的存储块分裂成两个大小相等的小块，这两个小块就称为“伙伴”。介于固定分区与可变分区之间的动态分区技术
紧凑技术
实现支撑：动态重定位（作业在内存中的位置发生了变化，这就必须对其地址加以修改或变换。）
可重定位分区分配
结合紧凑技术的动态分区技术
多重分区分配
为了支持结构化程序设计，操作系统往往把一道作业分成若干片段（如子程序、主程序、数据组等）。这样，片段之间就不需要连续了。只要增加一些重定位寄存器，就可以有效地控制一道作业片段之间的调用
页式内存管理
基本思想：把一个逻辑地址连续的程序分散存放到若干个不连续的内存区域，并保证程序的正确执行。
纯分页/基本分页存储管理方式：在调度一个作业时，必须把它的所有页一次装到主存的页框内；如果当时页框数不足，则该作业必须等待，系统再调度另外作业。不具备页面对换功能，不支持虚拟存储器功能。
补充知识：作业、进程和程序
作业通常包括程序、数据和操作说明书三部分。
每一个进程由进程控制块PCB、程序和数据集合组成。这说明程序是进程的一部分，是进程的实体。
基本概念
- 页面/页：逻辑地址空间
- 页框/存储块：物理内存的存储空间，与页面相同大小的片
- 页表项：每个页面到页框的映射
- 页表：分页系统为每个进程配置的一张表，页表项的集合。存放在内存中
页面大小
- 小：页内碎片少，利于提高内存利用率；页表占用内存较大；页面换进换出速度降低
- 大：与小相反
地址变换机构
- 内存系统区的PCB（进程控制块）将页表信息传给页表寄存器（存储页表起始地址+页表长度信息）
- 根据逻辑地址计算页号、页内偏移量
- 判断是否越界：页号 <= 页表长度 ？
- 查询页表，找到页号对应的页表项，确定页号对应的页框号
- 用页框号+页内偏移量计算出物理地址
- 访问目标内存单元
二级页表
目录-页表-偏移量
多级页表为什么省空间
因为多级页表允许操作系统根据进程实际使用的内存量来动态分配页表空间（想想实验课的MOS）
多级页表的设计允许操作系统在创建进程时只需为每个进程分配一个一级页表，然后根据进程申请的内存空间，再为进程分配二级页表。这种按需分配的方式避免了单级页表在进程创建时为可能用到的所有页表项分配空间，从而减少了不必要的内存占用。
快表/TLB（转换表查找缓冲区）/联想存储器
为了解决页表机制带来的内存访问效率严重下降问题
快表一种特殊的cache，内容是页表中的一部分或全部内容
结构：Valid + Virtual page + Modified + Protection + Page frame
哈希页表：处理超过32位地址空间的一种常用方法
将虚拟页号转换为哈希值，据此访问哈希表的表项（链表）。用虚拟页号与链表中的元素的第一个域相比较。如果匹配，那么相应的页框号（第二个域）就用来形成物理地址；如果不匹配，那么就进一步比较链表的下一个节点，以找到匹配
反置页表
页表按页框号排序，页表项内容是逻辑页号+隶属进程标识符
优点：页表占用的内存空间小
页共享与保护
保护：
- 地址越界保护
- 在页表中设置保护位（定义操作权限：只读，读写，执行等）
共享：分段存储管理（解决共享数据和不共享数据出现在同一个页框的问题）
段式内存管理（类比页式）
将地址空间按照程序自身的逻辑关系划分为若干个段（类比页式的”分成若干页面“）。
段表项：段号（隐含在地址下标）、段长+基址（区别于页式，段的长度不固定，页的大小固定）
地址变换（类比页式的地址变换，需增加一步：根据段表内的段长检查段内地址/偏移是否越界）
分段和分页对比
| 分段 | 分页 | |
|---|---|---|
| 对用户 | 可见 | 不可见 |
| 地址空间 | 二维 | 一维 |
| 信息共享和保护实现难易程度 | 更容易实现 | 更难实现 |
| 长度 | 不固定 | 固定 |
| 都需要两次访存，都可引入快表机构 |
段页式内存管理
段里再分页
逻辑地址结构：段号+页号+页内偏移量
段表项：段号（隐含在地址下标）、页表长度（一个段里有几页）+页表存放块号（页表起始地址）
页表项：页号（隐含在地址下标）、页框号
地址变换机构：段式和页式的结合，三次访存，可引入快表机构（段号+页号）
虚拟内存管理
局部性原理
时间局部性：程序中存在大量循环
空间局部性：很多数据在内存中是连续存放的
基于局部性原理产生了高速缓存技术
虚拟内存的定义和特征
定义：程序不需全部装入即可运行，运行时根据需要动态调入数据，若内存不够，还需换出一些数据
| 特征比较 | 虚拟内存 | 传统存储管理方式 |
|---|---|---|
| 多次性 | 一次性 | |
| 对换性 | 驻留性 | |
| 虚拟性 | ||
| 离散性 |
虚拟内存的实现
- 请求分页式存储
- 请求分段式存储
- 请求段页式存储
操作系统要提供请求调页（调段）功能，页面置换（段置换）功能
请求分页管理方式
一些基本概念
进程的逻辑空间：一个进程的逻辑空间的建立是通过链接器（Linker），将构成进程所需要的所有程序及运行所需环境，按照某种规则装配链接而形成的一种规范格式(布局)，这种格式按字节从0开始编址所形成的空间也称为该进程的逻辑地址空间
虚拟地址空间和虚拟存储空间：进程的虚拟地址空间即为进程在内存中存放的逻辑视图。因此，一个进程的虚拟地址空间的大小与该进程的虚拟存储空间的大小相同，都从0开始编址。
交换分区（交换文件）：一段连续的磁盘空间（按页划分的），并且对用户不可见。
功能：在物理内存不够的情况下，OS先把内存中暂时不用的数据，存到磁盘的交换空间，腾出物理内存来让别的程序运行。
在Linux系统中，交换分区为swap；在Windows系统中则以文件的形式存在（pagefile.sys)。
交换分区的大小：应当与系统物理内存（M）的大小保持线性比例关系(Linux中）：
If (M < 2GB) swap = 2*M
else swap = M + 2GB
请求式分页管理的页表项
- 逻辑页号（隐含）
- 访问位（用于页面置换算法）
- 修改位（表明此页在内存中是否被修改过）
- 保护位（只读、可写、可执行）
- 驻留位（1：该页位于内存中；2：该页还在外存中）
- 物理页帧号
页面调入策略
按需调页/请求式调页：当且仅当需要某页时才将其调入内存的技术
预调页：同时将所需要的所有页一起调入内存
优缺点：与按需调页相比，阻止了大量的页错误（也叫缺页异常）；但若程序执行的局部性较差，则预先装入的很多页面不会很快被引用，并会占用大量的内存空间，反而降低系统的效率。
实际应用中，可以为每个进程维护一个当前工作集（进程运行正在使用的页面集合）中的页的列表，如果进程在暂停之后需要重启时，根据这个列表使用预调页将所有工作集合中的页一次性调入内存
页面置换策略
| 算法 | 算法规则 | 优缺点 |
|---|---|---|
| 最优置换（OPT） | 从主存中移出永远不再需要的页面，如这样的页面不存在，则应选择最长时间不需要访问的页面。 | 所有页置换算法中页错误率最低 但它需要引用串（即页面访问序列）的先验知识，因此无法实现。但通常用于比较性研究，衡量其他页置换算法的效果 |
| 先进先出（FIFO） | 优先淘汰最先进入的页面 | 性能较差，较早调入的页往往是经常被访问的页，导致它们被反复调入调出，可能出现belady异常（在使用FIFO算法作为缺页置换算法时，随着分配的页框增多，缺页率反而提高） |
| Second Chance（改进的FIFO算法） | ||
| Clock（改进的FIFO算法&Second Chance） | 通过一个环形队列，避免将数据在FIFO队列中移动 | |
| 最近最少使用（LRU） | 选择最近一段时间最久不用的页面去置换 | 是局部性原理的合理近似，性能接近OPT算法 但需记录页面使用的先后关系，实现开销大 |
| *老化算法（AGING，LRU近似） | 为每个页面设置一个移位寄存器，每隔一段时间（clocktick），所有寄存器右移1位，并将访问位R值从左移入。淘汰寄存器中数值最小的页面 | |
| *工作集算法 | 给定一个进程，记录其工作集，当需要进行页面替换时，选择不在工作集中的页面进行替 | |
| WSClock工作集时钟页面置换算法 | 和时钟算法很像，将页框组成一个循环表，每个表项包含来自基本工作集算法的上次使用时间 |
前面是从一个进程的角度讨论虚存管理的相关问题，下面是从系统管理者（OS）的角度讨论多个进程情况下虚存管理的问题
概念：工作集和驻留集
- 进程的工作集（working set）：当前正在使用的页面的集合。
- 进程的驻留集（resident set ）：虚拟存储系统中，每个进程驻留在内存的页面集合，或进程分到的物理页框集合。
多进程页面分配策略
- 固定：每个进程分配固定数量的页框
- 可变
多进程页面置换策略
- 局部：系统在进程自身的驻留集中判断当前是否存在空闲页框，并在其中进行置换
- 全局
分配与置换的搭配
graph LR; |
抖动问题（thrashing）
随着驻留内存的进程数目增加，即进程并发程度的提高，处理器利用率先上升，然后下降。因为每个进程的驻留集不断减小，当驻留集小于工作集后，缺页率急剧上升，频繁调页使得调页开销增大。
抖动的消除与预防
局部置换策略：使抖动局限在一个小的范围内，但是并未消除抖动的方式。
引入工作集算法
预留部分页面
挂起若干进程
负载控制
主要解决系统应当保持多少个活动进程驻留在内存的问题，即控制多道程序系统的度。当内存中的活动进程数太少时，负载控制将增加新进程或激活一些挂起进程进入内存；反之，当内存中的进程数太多时，负载控制将暂时挂起一些进程，减少内存中的活动进程数。
页面缓冲算法
对FIFO算法的发展
被置换页面的选择和处理：用FIFO算法选择被置换页，把被置换的页面放入两个链表之一。即：如果页面未被修改，就将其归入到空闲页面链表的末尾，否则将其归入到已修改页面链表。
写时复制技术
两个进程共享同一块物理内存，每个页面都被标志成了写时复制。共享的物理内存中每个页面都是只读的。如果某个进程想改变某个页面时，就会与只读标记冲突，而系统在检测出页面是写时复制的，则会在内存中复制一个页框，然后进行写操作。新复制的页框对执行写操作的进程是私有的，对其他共享写时复制页面的进程是不可见的。
优点：
传统的fork()系统调用直接把所有的资源复制给新创建的进程。这种实现过于简单而效率低下，因为它拷贝的数据也许并不共享，如果新进程打算立即执行一个新的映像，那么所有的拷贝都将前功尽弃。
Linux的fork()使用写时复制实现，它可以推迟甚至免除拷贝数据的技术。内核此时并不复制整个进程地址空间，而是让父进程和子进程共享同一个拷贝。只有在需要写入的时候，数据才会复制，从而使各个进程都拥有各自的拷贝。也就是说，资源的复制只有在需要写入的时候才进行。
页目录自映射
以二级页表为例：设页表基址$ PT_{base} $（4MB对齐，即低22位为0，非必须，这是为了让页目录表在一个单独页表内，也可以简化计算），则页目录表基址$ PD_{base}=PT_{base} | (PT_{base} >> 10) $，自映射目录表项$ PDE_{self-mapping}=PT_{base} | (PT_{base} >> 10) | (PT_{base} >> 20) $。可推广到多级页表。
自映射的数学意义：手持北京地图在北京，必有地图上一点与其表示的地理位置与该点的实际地理位置重合。(压缩映像)
