虚拟化

什么是虚拟化¶

共享 CPU¶

通过虚拟化 CPU、内存等硬件，让一个进程只运行一个时间片（分时共享），然后切换到其他进程， 操作系统提供了一个假象，使得较多的进程可以运行在有限的资源上
进程的组成（机器状态）：
- 内存（地址空间）：指令+数据
- 寄存器：程序计数器，栈指针等

共享内存¶

地址空间：运行的程序看到的系统中的内存
操作系统通过虚拟内存，使得程序认为它被加载到特定地址的内存中，并且具有非常大的地址空间
虚拟内存系统的目标：
- 透明：操作系统实现虚拟内存的方式，应该让运行的程序看不见。（不应感知到内存被虚拟化）
- 效率：时间&空间（不会更慢，不需要太多额外存储）
- 保护：确保进程收到保护（不会受到其他进程的映像），操作系统本身更不应该受到进程的影响

操作系统的进程管理¶

操作系统初始化阶段加载了第一个进程
操作系统是状态机的管理者
fork-exevce-exit 构成了 unix 中的进程世界

进程的概念¶

进程由三部分组成：程序代码段、数据段、PCB（进程控制块）
PCB：
- 系统通过 PCB 了解进程的信息，在进程执行结束时回收 PCB
- 主要包含了：进程描述信息（进程标识符、用户标识符等）、进程控制和管理信息（描述进程运行状态，作为 CPU 调度的依据）、资源分配信息、处理机相关信息（CPU 寄存器等上下文信息）
进程的状态：
- 运行态：正在 CPU 上运行
- 就绪态：获得了除了 CPU 以外的全部资源，得到 CPU 就可以开始运行了（这个时间通常很短）
- 阻塞态：正在等待某一个事件而暂停（如 IO, 等待除了 CPU 之外的资源）
- 创建态：正在被创建（步骤：创建 PCB，分配资源，转入就绪）
- 终止态：正在消失，如运行结束，还需要进行资源释放回收等操作
进程的状态转换：
进程的管理方式
- 连接方式：将相同状态的 PCB 连接成一个队列
- 索引方式：将同一状态的进程组织在一个索引表

进程的基本操作¶

进程的创建 -fork¶

pid_t fork(void); 创建当前线程的完整克隆
- 是对当前进程（状态机）的完整复制（内存、寄存器现场等）
- 父进程会收到返回值为子进程的进程号
- 子进程收到返回值 0
- 返回值（RAX）就是两个线程的唯一区别
具体过程
- 分配进程标识号，申请空白 PCB
- 分配其他资源，如内存，IO 设备等
- 初始化 PCB，信息
- 插入就绪队列等待调度

pid_t x = fork();
pid_t y = fork();
printf("%d %d\n", x, y);

-

执行可执行文件-execve¶

int execve(const char *filename,char * const argv[], char * const envp[]);
- “重置“状态机，将当前进程重置为一个可执行文件描述的状态机的初始状态（一个可执行文件实际就描述了一个状态机的初始状态）
- 即改为执行另一个程序，不会再返回，即 execve 后面的内容不会再被执行
将 fork 和 execve 分离使得可以在其之间执行一些操作，比如修改文件描述符进行输入输出重定位
将一个程序转化为进程，首先要将代码和静态数据从磁盘加载到内存中
- 通常惰性执行，再程序执行期间根据需求动态加载
操作系统还需要做其他初始化操作，如为程序栈、堆初始化并分配空间以及执行 IO 设置相关的工作
最后操作系统启动执行程序，转到入口处开始执行，将控制权转交给新创建的线程

应用程序的执行环境 env

PATH: 可执行文件搜索路径
PWD: 当前路径
HOME: home 目录
DISPLAY: 图形输出

PS1: shell 的提示符

int main() {
    char *const argv[] = {
        "/bin/bash",
        "-c",
        "env",
        NULL,
    };

    char *const envp[] = {
        "HELLO=WORLD",
        NULL,
    };

    // Reset the state machine to "/bin/bash"
    execve(argv[0], argv, envp);

    // We are here only on error.
    printf("Hello, World!\n");
}

fork+execve

执行新程序的常见使用方式

fork 创建子进程，使用 execve 将子进程初始化为目标可执行文件对应的状态机

int pid = fork();
if (pid == -1) {
    perror("fork"); goto fail;
} else if (pid == 0) {
    // Child
    execve(...);
    perror("execve"); goto fail;
} else {
    // Parent
    ...
}

终止进程-_exit¶

主动销毁进程
void _exit(int status);
- 立即摧毁状态机，允许有一个返回值 (子进程会通知父进程)
- 会终止进程中的所有线程
C 语言提供的退出方式
- return main 函数
- exit (num)
- 这两种否会调用 atexit，可以做一些退出之前的处理
操作系统提供的退出方式
- _exit(num)
- syscall(SYS_exit,0)
- 会直接终止进程，不会调用 atexit

具体过程：

根据标识符检索 PCB
终止进程执行（如果在运行态）
释放资源（归还给父进程或操作系统）

将 PCB 从所在链表移除

void func() {
    printf("Goodbye, Cruel OS World!\n");
}

int main(int argc, char *argv[]) {
    // This is a convenient mechanism for 
    atexit(func);
    //c语言提供的方式
    if (argc < 2) {
        return EXIT_FAILURE;
    }
    if (strcmp(argv[1], "exit") == 0) {
        exit(0);
    }
    //操作系统提供的方式
    if (strcmp(argv[1], "_exit") == 0) {
        _exit(0);
    }
    if (strcmp(argv[1], "__exit") == 0) {
        syscall(SYS_exit, 0);
    }
}

CPU 调度¶

UNIX-NICE 机制
- 分数从-20 到 19，分数越小“越坏“，优先级越高
LINUX-CFS 机制
- 让系统进程尽可能公平的共享处理器
- 为每个进程记录精确的运行时间
- 中断异常发生之后切换到运行时间最少的进程执行
- 通过为时间计时加一个权数（时间流失速度不一样）实现优先级管理
进程调度面临的问题
- 互斥锁
- 多处理器，cache、内存等局部性
- 大小核异构
- 核心距离（共享内存密集型程序）
- 多用户公平性（更多线程抢占更多资源）
- 使用三级调度：
- 高级调度（作业调度）：从外存处于后备队列的作业中选一个来载入内存、创建相关的进程
- 中级调度（内存调度）：将暂时不能运行的进程调入外存（挂起）具备运行条件并且内存空闲时再调回。主要是为了提高内存的利用率
- 低级调度（进程调度）：从就绪队列中选取进程，分配 CPU，进程调度的进行频率很高，最基本的调度
- 排队器：将系统中所有就绪进程按照一定策略排成一个或多个队列
- 分配器：根据调度程序所选的进程，从队列中取出，并为其分配进程
- 上下文切换器：保存就上下文、恢复新上下文
进程的调度方式
- 非抢占式调度：只有一个进程运行完成或者进入阻塞态，才能将 CPU 分配给其他进程
- 抢占式调度：更重要的进程需要使用 CPU 则允许调度程序暂停正在执行的进程，分配给紧急进程
两种线程调度
- 用户级线程调度：内核只是选择一个进程执行，用户进程中的调度程序决定要调用的线程
- 内核级线程调度：内核选择特定额线程执行
调度的目标
- \(CPU 利用率=\frac{{CPU有效工作时间}}{CPU有效工作时间+CPU空闲等待时间}\)
- 系统吞吐量：单位时间 CPU 完成的作业数量
- 周转时间：作业提交到作业完成所经历的时间
  - \(作业周转时间=作业完成时间-作业提交时间\)
  - \(带权周转时间=\frac{{作业周转时间}}{作业实际运行时间}\)
- 等待时间：进程处于等待 CPU 的时间之和
- 响应时间：用户提交请求到首次产生响应的时间

典型调度算法¶

先来先服务 FCFS
- 即 FIFO
- 长作业会占用太长时间，不适用于分时系统和实时系统，通常结合使用
短作业优先 SJF
- 一般是非抢占式的，每次优先从队列中选择短作业执行
- 对长作业不公平，可能被长期抢占（饥饿问题）
- 实际上这种算法不太现实，因为操作系统通常无法准确预估任务的执行时长
- 抢占式 SJF 称为最短完成时间优先（STCF），STFC 在周转时间指标上可以达到最优，但是在响应时间等方面的表现不是很好
高响应比优先调度算法
- 主要用于作业调度，考虑作业的等待时间和运行时间
- \(响应比=\frac{{等待时间+要求服务时间}}{要求服务时间}\)
- 等待时间相同时短作业的响应比更大优先调度，等待时间较长时长作业也有机会（克服了饥饿问题）
优先级调度
- 根据优先级进行调度
- 非抢占式：高优先级也要等当前进程执行完成
- 抢占式：优先级更高的进入队列，则暂停当前正在执行的任务 (实时系统通常使用)
- 静态优先级：预先设置（可能导致低优先级进程长期不能被执行）
- 动态优先级：会随着等待时间而变化，如增加
- 一般来说有：系统进程>用户进程；交互型进程>非交互型进程；IO 进程>计算进程
时间片轮转调度 RR
- 主要用于分时系统，高响应性。周转时间指标表现很差
- 执行完一个时间片后将当前进程移到末尾，重新取进程继续执行
多队列调度算法
- 设置不同就绪队列，对进程分类，使用不同的调度算法
多级反馈队列调度算法
- 希望同时具有良好的周转时间和响应时间
- 不需要对工作的运行方式有先验知识，而是通过观察工作的运行来给出对应的优先级。
- 如果一个工作不断放弃 CPU 去等待键盘输入（交互型进程），MLFQ 因此会让它保持高优先级。如果一个工作长时间地占用 CPU（计算密集型），MLFQ 会降低其优先级。通过这种方式，MLFQ 在进程运行过程中学习其行为，从而利用工作的历史来预测它未来的行为
- 设置多个队列，优先级递减
  - 如果 A 的优先级 > B 的优先级，运行 A
  - 如果 A 的优先级 = B 的优先级，轮转运行 A 和 B（同一优先级队列内）
- 策略：工作进入系统时，放在最高优先级；如果工作用完整个时间片，降低其优先级；如果工作在其时间片以内主动释放 CPU，则优先级不变（问题：饥饿问题、欺骗问题）
- 改进：经过一段时间 S，就将系统中所有工作重新加入最高优先级队列，保证长工作至少定期有一些进展，解决饥饿问题
- 完善 CPU 计时方式（准确判断是否真的是交互式任务）：调度程序应该记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时，一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次 CPU），就降低其优先级，解决欺骗问题。
- 高优先级更多是交互工作，使用较短的时间片；低优先级队列更多使用 CPU 密集型工作，配置更长时间的时间片。
比例份额调度（彩票调度）
- 目标：确保每个工作获得一定比例的 CPU 时间，而不是专注优化周转时间和响应时间
- 一个进程拥有彩票占总数的比例就是其占有资源的份额
- 有当工作执行非常多的时间片时，彩票调度算法能得到期望的结果。
- 调度程序不断抽取中奖号码，对应的进程被调度运行、
- 多任务进程可以自行决定如何将彩票分配，由操作系统对象；一个进程还可以将自己持有的彩票转让给其他进程（如客户端吧彩票交给服务端）；如果一个进程知道它需要更多 CPU 时间，就可以增加自己的彩票，从而将自己的需求告知操作系统（这可能存在欺诈问题）
- 步长调度就是对每个进程分别计数，为最小的进程调度并加上一个值（彩票越多值越小）
- 随机调度的优点是简单迅速不需要全局信息
多处理器调度
- 问题：
  - 缓存失效、一致性问题
  - 锁、线程安全数据结构的较大开销，可能出现 CPU 越多越慢
  - 缓存亲合度问题，更换 CPU 需要重新缓存，速度变慢
- 单队列调度 SQMS：将所有需要调度的工作放入一个单独的队列中，需要对队列加锁效率较低（用统一的一个队列为所有 CPU 分配任务）
  - 保持一些工作的亲和度的同时，可能需要牺牲其他工作的亲和度来实现负载均衡
- 多队列调度 MQMS：包含多个调度队列，每个队列可以使用不同的调度规则
  - 当一个工作进入系统后，系统会依照一些启发性规则将其放入某个调度队列。每个 CPU 调度之间相互独立，就避免了单队列的方式中由于数据共享及同步带来的问题。
  - 存在负载不均的问题（每个 CPU 分别设置队列导致）因此还需要根据 CPU 空闲状态迁移工作

进程地址空间¶

一个进程的地址空间包含运行的程序的所有内存状态，如代码、栈、堆等
虚拟内存机制的目标：
- 透明：程序不应该感知到内存被虚拟化的事实，程序的行为就好像它拥有自己的私有物理内存
- 效率：时间和空间上尽可能高效，不会消耗太多的额外资源
- 保护：一个进程不应该以任何形式访问或影响其他进程或操作系统本身的内存内容，即每个进程都在自己的独立环境中运行，避免其他出错或恶意进程的影响
查看进程的地址空间及权限 `/proc/[pid]/maps
- 地址范围|权限|偏移量|设备|innode（对应文件）|路径名或标记
或者使用 pmap 命令查看管局进程的内存使用信息

*vdso¶

一段运行在用户空间的代码，允许一些特定的系统调用（如获取时间）避免进行上下文切换到内核态，可以调高执行的效率（尤其是调用频繁的系统调用）
vDSO 通过将一小段代码映射到用户进程的地址空间来工作。这段代码实现了一些系统调用的功能。当应用程序需要执行某些系统调用时，它可以直接调用这些已映射到用户空间的函数，而无需执行完整的系统调用过程。

管理进程的地址空间¶

增加、删除、修改可访问的内存，进行内存申请等工作
mmap 系统调用用于将设备或文件映射到内存中，从而创建一块可以直接通过指针访问的内存区域。
- void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
- addr: 希望映射区域的首选起始地址。通常设为 NULL，由系统选择映射区域的地址。
- length: 映射区域的长度。
- prot: 映射区域的保护权限。可以是以下几个值的组合：
  - PROT_READ: 可读。
  - PROT_WRITE: 可写。
  - PROT_EXEC: 可执行。
  - PROT_NONE: 不可访问。
- flags: 控制映射的行为。常见的标志包括：
  - MAP_FIXED: 使用指定的addr精确地址；如果地址已被使用，会替换原有的映射。
  - MAP_SHARED: 对映射的修改会反映到底层文件上，并且对其他所有映射同一文件的进程可见。
  - MAP_PRIVATE: 对映射区域的写入不会写回到原文件，而是创建一个写时复制的私有副本。
- fd: 要映射的文件的文件描述符。若是创建匿名映射，则设为-1。
- offset: 文件中的偏移，映射从文件的这个偏移开始。
```
volatile uint8_t *p = mmap(
        NULL,
        8 GiB,//宏定义的
        PROT_READ | PROT_WRITE,
        MAP_ANONYMOUS | MAP_PRIVATE,
        -1, 0
    );
```
munmap 函数用于取消映射的内存区域，释放这部分区域。
- int munmap(void *addr, size_t length);
- addr: 映射区域的起始地址。
- length: 映射区域的长度。
mprotect 函数用于修改现有内存区域的保护权限。
- int mprotect(void *addr, size_t length, int prot);
- addr: 需要修改权限的内存区域的起始地址。
- length: 需要修改权限的内存区域的长度。
- prot: 新的保护权限，同 mmap 中的保护权限。

入侵进程的地址空间¶

一个进程对其他进程的地址进行访问，就可以任意改变另一个程序的行为
如何查找变量的存储空间（金山游侠）
- 让目标变量发生变化，查找发生了相同变化的内存，直至能唯一确定
- 之后直接对内存的数据进行修改
给进程发送虚假信号（按键精灵）
- 如发送 gui 事件（鼠标键盘）
改变进程对时间的感知（变速齿轮）
- 通过修改系统调用表或使用动态链接库实现拦截系统调用（）
- syscall：gettimeofday，sleep（用于等待时间）
- 创建一个 C 文件，定义拦截的系统调用函数，与原函数同名。
- 我们定义了一个与原始 gettimeofday 函数同名的函数，以便覆盖标准库中的实现。
- 在自定义的 gettimeofday 函数中，我们首先通过 dlsym 获取原始函数地址。
- 调用原始函数获取当前时间。
- 根据加速因子修改时间值，然后返回修改后的时间。
- 应用：软件动态更新

内存管理¶

内存管理的主要内容：
- 内存空间分配与回收
- 地址转换
- 内存地址的扩充
- 内存共享
- 存储保护
操作系统可以分配大段的内存（甚至超过物理上限）；由程序自己负责更细致的分配小段内存，如使用 malloc()free()，在操作系统提供的 [L,R) 范围内维护互不相交的区间集合
多级内存管理：第一级由操作系统分配，操作系统将内存交给进程，在进程结束时进行回收；第二级在进程中，由进程在内部进行管理。
在实际系统中，我们通常不考虑“最坏情况“（现实中的应用是 “正常” 的，不是 “恶意” 的），应该结合实际的 workload 来进行设计和优化
实际的情况
- 小对象：字符串、临时对象等；生存周期可长可短
- 中对象：容器、复杂的对象；更长的生存周期
- 大对象：巨大的容器、分配器；很长的生存周期
因此管理的重点是小对象，小对象分配/回收的 scalability 是主要瓶颈（多 CPU 上同时进行）
思想：设置两套系统
- first path：性能极好、并行度极高、覆盖大部分情况，但有小概率会失败
- slow path：不在乎那么快，但把困难的事情做好
具体到 malloc
- first path：给所有线程事先分配“领地”, 线程默认从自己的领地分配（线程本地完成），如果自己的领地不足再从全局借用：为了实现更好的性能浪费一点是可以接受的（比如内存对齐）
  - 针对不同大小的空间需求，使用不同的特定分配器（不同细粒度，像棋盘一样直接分配一个格子）
- slow path：pgalloc ()

内存分配¶

单一连续分配：
- 将内存分为系统区和用户区
- 分配方式很简单，不需要内存保护（内存中也只有一道程序），只适用于单用户单任务操作系统，有内部碎片存储器利用率较低
固定分区分配：
- 最简单的多道程序存储管理方法，将用户内存空间划分为若干固定大小的分区，每个分区只装入一道作业
- 有分区空闲时从外存的后备作业队列中选择适当大小的作业状图分区
- 如果分区大小相等会造成较多浪费，通常划分为：多个较小区间、适量的中等分区和少量大分区
- 使用分区表来进行分配和回收：表中记录分区号、大小和起始地址以及分配状态，分配内存时就对表进行检索并选择内存进行分配
- 问题：分区大小固定不够灵活，利用可能不充分
以上两种为静态重定位不需要硬件地址变换机构，由装入程序或操作系统完成地址转换
动态分区分配：
- 可变分区分配，根据实际需要动态的进行分配。通常在分配的头块中存储一些额外的信息，比如 free 时就不需要再指出大小
- 问题：随着时间推移，会产生大量的外部内存碎片，需要整理程序
动态分区分配内存的内存回收算法
- 设置一个分区链表（空闲列表），分配内存时通过遍历节点寻找分区，较大时还可以对节点进行分割
- 回收时在链中找到相应的位置插入，此外如果插入后发现与前后节点的空间连续，还可以对内存做合并操作
基于顺序搜索的分配算法（性能都不太好）
- 首次适应算法：空闲地址递增，分配时顺序查找第一个能满足大小的内存分区，使低地址出现了较多碎片（性能相对较好）
- 邻近适应算法：分配内存时从上次查找的结束位置开始
- 最佳适应算法：空闲分区按容递增分配，顺序查找第一个能满足大小的空间，性能较差产生了很多小碎片（产生最多的碎片）
- 最坏适应算法：容量递减排序，每次选择最大空闲分区分割空间
- 当系统较大时，顺序遍历很慢
基于索引搜索的分配算法 : 根据大小对碎片空间进行分类，分为不同的链
- 快速适应算法：根据进程常用大小进行划分，首先在索引表中找到最小能容纳的分区链表，然后从链表中取出第一块进行分配（会进行切割），但是也需要在回收时进行分区合并
- 伙伴系统：所有分区的大小均为 \(2^k\)，对于需要 \(2^{i-1}<n<2^i\) 空间时从大小为 \(2^i\) 的链表中进行寻找，如果没有则分裂 \(2^{i+1}\) 的空闲分区。合并时也要对伙伴分区进行合并（从同一个块分裂来的）
- 哈希算法：根据空闲分区链表的分布规律建立哈希函数，构建以空闲分区大小为关键字的哈希表，表项为对应的头指针，每次通过哈希计算得到头指针从中得到空闲的分区链表
注意：固定分区产生的是内部碎片（分配的区域没有被完全利用）；动态分区产生的是外部碎片（切割产生的）

虚拟内存的诞生历程¶

目标：高效、控制
使用基于硬件的地址转化，硬件对每次内存访问进行处理，将虚拟地址转化为物理地址
基于纯软件的静态重定位：由加载程序的软件负责地址的转化（直接对指令进行重写）
- 问题：不能很好的提供访问保护；重定位完成后难以将内存空间移动到其他位置
基于硬件的动态重定位：硬件负责将虚拟地址加上基址寄存器中的内容得到物理地址，再分发给内存系统
- 基址寄存器负责地址的转化、界限寄存器负责确保访问地址在地址空间范围之内提供访问保护
- CPU 中负责地址转化的部分就称为 MMU
- 对硬件的要求：特权模式/用户模式转化、基址和界限寄存器、能转化虚拟地址并检测越界、修改基址和界限器的特权指令、能触发异常并有注册异常处理程序的特权指令
直接将整个程序放入内存造成太大浪费（堆栈的大部分都是空的），并产生大量内存碎片。由此引入分段机制，如分为代码、堆、栈，并设置三套基址/界限寄存器此外分段还方便了代码共享（进程之间共享代码段）

虚拟内存管理¶

虚拟存储器就是系统好像为用户提供一个比实际内存大的多的存储器，称为虚拟存储器。
- 特点：多次性（分次装入）；对换性（内存外存换出换入）；虚拟性（从逻辑上扩容了内存的容量）
页表的数据结构（最广泛方案，使用在 x 86、risc 5 等）：多叉树（多级页表），根节点存储在 CR3，进一步由于空间局域性可以使用 TLB 缓存加速
- MIPS 实现：TLB Miss 以后产生异常，操作系统使用 tlbwi/tlbwr (indexed/random) 重填，可以为不同的进程使用不同的数据结构！
- 哈希表实现：将虚拟页号和 pid 共同作为键，整个系统只需要一个哈希表，miss 时比较慢
分页主要的目的是提高内存利用率及计算机性能，通过操作系统和硬件机制实现，对用户完全透明
- 分页长度固定，会产生内部碎片
分段管理考虑了用户和程序员：实现方便编程、信息保护和共享、动态增长和动态链接
- 长度根据需要分配，会产生外部碎片
段页式存储中：每个进程有一个段表，每一个段对应一个（多级）页表
- 即每个进程一个段表但是可能有多个页表
请求分页管理方式：以基本分页系统为基础（换入），还提供了请求调页和页面置换功能（换出）
- 为了实现换入换出，添加字段：状态位（是否已经调入内存）；访问字段（被访问次数，用于置换）；修改位（是否被修改过）；
- 缺页的处理：缺页中断（内部异常），由操作系统处理
抖动：同一个页面被反复换入换出
- 根本原因：分配的物理块太少
工作集：某段时间间隔内进程要访问的页面结合

页框管理与页面置换（交换空间）¶

利用大而慢的设备（硬盘），透明地提供巨大虚拟地址空间的假象
在硬盘上开辟一部分空间（交换空间）专门用于物理页的移入移出
有一个存在位表示内容是否在物理内存中，如果不在内存中，则发生缺页，需要从磁盘进行加载
为了保证有少量的空闲内存，大多数操作系统会设置高水位线和低水位线，来帮助决定何时从内存中清除页。当操作系统发现有少于 LW 个页可用时，后台负责释放内存的线程会开始运行，直到有 HW 个可用的物理页。（即不是等到满了在做清理）
驻留集：给一个进程分配的页框的集合
- 越小：单个进程占用的资源就越少，但是缺页率相对较高
- 越大：存在边际效应，浪费内存空间
内存分配策略
- 固定分配局部置换：为每个进程分配固定数目的物理块，运行中发生缺页则只能从分配的内存中选择换出换入
  - 可以使用：平均分配；按进程大小比例分配；优先权分配
- 可变分配全局置换：先分配一定数目，但是在运行中根据运行工情况动态调整，发生缺页时从空闲队列分配，更加灵活。可能导致动态增加太多，进程占用太大。
- 可变分配局部置换：发生缺页时，只允许从进程自己的内存中换出，根据缺页率动态调整分配的块的数目
调入页面的时机：
- 预调页策略：根据局部性原理一次调入若干相邻页面
- 请求调页策略：需要用时（不存在）才调入，调入的页面都一定会被使用

页面置换算法 - 最佳置换 OPT - 换出以后永不使用的页面或最长时间内不再使用的，只向前看 - 无法为通用操作系统实现最优策略，但是可以用于作为评价置换算法的基准 - 先进先出 FIFO - 淘汰最早进入内存的页面 - 分配更多物理块可能反而导致缺页增加（belady 现象） - 最近最久未使用 LRU - 淘汰最近最长时间没有使用的页面，只向后看 - 时钟置换 CLOCK（最近未用 NRU） - 当一个页面被装入或被访问时，其访问为置为 1，算法将内存中的页面连接成一个循环队列，有一个替换指针，选择淘汰一页时，如果值为 1，则修改为 0（给一次机会先不换出）；如果为 0 则换出，然后指向下一个页面。 - image.png|500 - 改进的 CLOCK 算法 - 修改过的页面换出时需要写回（也就是说会有更大的代价，因此综合考虑访问位 A 和修改位 M） - \(A=0,M=0\) 最佳淘汰页 - \(A=0,M=1\) 次佳淘汰页 - \(A=1,M=0\) 可能再被访问 - \(A=1,M=1\) 可能再被访问 - 先寻找最佳淘汰页（这遍不修改访问位）；第二轮扫描寻找次佳淘汰页，这次访问位置 0，直到找到为止 - 改进版减少了磁盘 IO 操作

当工作负载不存在局部性时，使用什么策略区别不大。当内存足够大时，所有算法都有近似 100%的命中率
当内存空间不足时，FIFO 了 LRU 的表现很差
当页面很多时，严格的 LRU 可能较慢（顺序扫描最小值），引入近似 LRU：CLOCK 算法

快表 TLB¶

对于 TLB 未命中的情况，一些传统的如 CISC 的 x 86 由硬件来处理，在一些更现代化的如 RISC 中硬件系统只负责抛出一个异常，将由异常处理程序负责解决。
发生上下文切换可能会改变页表，原先的 TLB 会失效
- 可以通过上下文切换时简单的清空 TLB 来解决
- 为了减少开销实现上下文切换的 TLB 共享，添加一个 ASID 作为进程标识符，用来区分不同进程的 TLB 表项

多级页表¶

解决页表太大的问题（如 32 位的页表有 4 mb，而且每个进程有自己的页表，会占用大量的空间）
- 一个解决方法：结合分段，按照段的界限设置页表，防止为不需要的部分分配页表造成空间上的浪费
多级页表中有页目录表，如果一级页表整页无效，则不分配该页的页表。页目录可以告诉页表的页在哪里，或者页表的整个页不包含有效页
- 多级页表支持稀疏的地址空间，不需要为页表分配连续空间，操作系统可以在需要分配或增长页表时简单地获取下一个空闲页。
反向页表：为物理页建立，存储每个物理页对应哪些虚拟页，通过散列表进行查找

其他优化¶

分页的 copy-on-write
- 比如 fork 后通常要 execve，而这就导致 fork 中白拷贝内存页了，为了避免拷贝，可以共享内存页（物理页），只读情况下可以共享，等到要写时再拷贝
页聚集：将大批量的页从全局脏列表中分组到一起，并将它们一举写入磁盘。执行更少和更大的写入，从而提高性能。
按需置零（惰性）：当页添加到地址空间时在页表中放入一个标记页不可访问的条目。如果进程读取或写入页，则会向操作系统发送陷阱。在处理陷阱时，操作系统会完成寻找物理页的必要工作，将它置零，并映射到进程的地址空间。如果该进程从不访问该页，则所有这些工作都可以避免。

链接与加载¶

可执行文件和加载¶

绝对装入：只适用于单道程序环境，使用绝对地址（程序中的逻辑地址与存储的实际地址相同）
可重定位状装入（静态重定位）：在装入时一次性完成（必须直接分配足够的内存），运行中不能在内存中移动也不能申请内存空间
动态运行时装入（动态重定位）：装入程序将装入模块装入到内存之后，地址转化推迟到程序真正执行时进行，可以将程序分配到不连续的存储器，运行时通过重定位寄存器和地址变换机构计算得到地址
可执行文件是一个描述了状态机初始状态的数据结构
- 即 execve 执行之后的地址空间中应该有什么
常见 Binutils（二进制文件工具）解释并打印一些二进制信息
- cc、ld、readelf、objdump、size、addr 2 line、nm
目标文件是一些 section 的集合（. test .data .rodata 等）
- section 三要素：代码、符号、重定位（暂时不能确定的数值）
生成目标文件时要合并所有的 sections，分别合并不同节的代码，并解析重定位进而确定所有符号的位置，最终得到一个可执行文件
加载时将多段字节序列复制到地址空间中，并分别赋予可读、可写、可执行的权限，最后跳转到入口开始执行

动态链接和加载¶

位置无关程序 PIC：编译后的程序可以在内存的任何位置运行，而不需要在运行时重新调整代码中的地址，主要用于共享库和动态加载可执行文件
- 使用相对地址替代绝对地址，如使用相对跳转指令
- GOT 是一个在运行时由动态链接器填充的表格，用于保存全局变量和函数的地址。代码访问全局变量和函数时，通过查找 GOT 中的条目来获得实际地址。
- PLT 是一种用于延迟绑定的机制，在程序第一次调用某个外部函数时，动态链接器会解析函数地址并更新 PLT 条目，后续调用该函数时直接通过 PLT 跳转到目标地址。
动态链接用于实现应用之间的库共享，使得不需要每个程序都包含重复的库（如 libc）
优点：
- 减少空间占用
- 当库被修改时，不需要重新链接所有的应用
加载时重定位：\(libc.o\)
- libc 的所有代码和数据在编译时就被链接到每一个可执行文件中（即 libc. o 会被复制多份加入到不同的可执行文件）
- 省了磁盘空间，但是不能节省内存
- 解析很多不需要使用的符号，导致链接速度较慢
运行时重定位：\(libc.so\)
- 编译器生成位置无关的代码
- 共享库可以被加载的内存的任何位置
- 维护一个额外的表，函数调用时先查表，表项中获取共享库汇总对应方法的位置（即多了一次查表的过程）
- 内存中也只需要有一个副本
如果每次函数调用都查表会造成较大的性能开销，并且用立即数直接填入偏移量则无法处理较大范围的移动
运行时重定位的具体实现：
- 由于立即数的移动范围有限，先跳转到 PLT（到不了 GOT ），再 ljmp 到目标地址
- 第一次调用时通过查表得到偏移量（当程序或共享库第一次加载时，PLT 表会被初始化，使得每个表项指向一个代码段，这个代码段会调用动态链接器来解析符号。当程序第一次调用外部函数时，会通过 PLT 表跳转到动态链接器。动态链接器解析符号并将函数的实际地址填入 GOT 表和 PLT 表。），并填回到 PLT 加速之后的跳转
动态链接和加载解决的问题
- 在加载时确定位置
- PLT 解决的是立即数跳转距离的限制

中断与上下文切换¶

系统调用¶

系统调用就是对操作系统的函数调用，“跳转并获得无限的权利”
存在一个陷阱表（在操作系统初始化时设置，是特权操作），其中描述了可以进行的系统调用操作、
通过系统调用，操作系统在为程序提供必要的服务的同时也维持了安全和控制

执行 syscall 的具体过程

syscall = “jal”:  // sysret: 逆操作
    mov %rip, %rcx
    mov %rflags, %r11
    set SS = kernel, SS = kernel, CPL = 0
    jmp IA32_LSTAR  // System Target Address Register

首先保存返回地址，将当前指令指针 rip 保存到寄存器 rcx
保存标志位寄存器 rflags 到 r 11
然后切换到内核堆栈（修改段寄存器），并修改权限级别 CPL
最后跳转到系统调用处理程序

中断机制¶

如果没有中断，一个不使用系统调用的程序（如死循环）无法被终止
虚拟机快照机制的实现原理：保存虚拟机在特定时间点的完整状态，包括内存、CPU 寄存器、磁盘和设备状态的过程。实现快照时，首先暂停虚拟机，然后将内存和 CPU 状态复制到快照文件中，使用写时复制技术保存磁盘数据，并记录所有设备的状态。恢复快照时，重新加载这些保存的数据，使虚拟机恢复到保存时的状态。
中断信号到来时，如果处理器中断打开，操作系统会进行处理
risc 中的具体过程与系统调用类似：保存-调度-恢复。一种"被动的 syscall"

上下文切换¶

系统调用指令是一种特殊的 “长跳转”——而跳转的目标是由操作系统配置好、应用程序不能决定的。类似地，处理器中断也会被动调用长跳转到操作系统内核。操作系统内核代码会 “封存” 进程的状态机：
- 对于内存中的页面，保持原封不动；
- 使用精心构造的代码，小心地将所有寄存器保存到内存中（避免覆盖未保存的信息）。
- 恢复时刚好相反，从内存中取出保存的数据放回到寄存器
计算机系统就处于所有程序都被封存、操作系统代码正在执行的状态。操作系统会选择性地调度下一个寄存器现场到 CPU 上，实现上下文切换。
有两种类型的寄存器保存/恢复。第一种是发生时钟中断的时候，运行进程的用户寄存器由硬件隐式保存，使用该进程的内核栈。第二种是当操作系统决定从 A 切换到 B。在这种情况下，内核寄存器被软件（即 OS）明确地保存，但这次被存储在该进程的进程结构的内存中。后一个操作让系统从好像刚刚由 A 陷入内核，变成好像刚刚由 B 陷入内核。

核心

Context *on_interrupt(Event ev, Context *ctx) {
    // 保存当前任务的上下文
    current->context = *ctx;

    // 调用调度函数，选择下一个任务
    current = schedule();

    // 返回新任务的上下文
    return &current->context;
}

扩展¶

内存映射文件：操作系统提供的一个系统调用，将磁盘文件与虚拟地址空间之间建立映射关系，以访问内存的形式来访问文件
- 共享内存通常就是这么实现的（物理内存中的一个内存映射文件被映射到两个不同的虚拟地址空间）
- 可以像访问内存（数组）那样访问，不需要使用 IO 操作，更为便捷

系统调用和 UNIX Shell¶

操作系统对象¶

everything is a file
操作系统中的对象要么是一个文件要么是一个字节流，通过指针访问一切（对象的访问都需要指针）
- 定义（重要）：文件描述符是指向操作系统对象的指针

管道与匿名管道¶

一种进程间同步机制 IPC

管道：特殊文件流

由读者和写者共享
命名管道是一种特殊类型的文件（FIFO），它存在于文件系统中，可以被系统中任何知道其名字的进程访问。

读口支持 read；写口支持 write

#define PIPE_NAME "/tmp/my_pipe"
void pipe_read() {
    int fd = open(PIPE_NAME, O_RDONLY);
    char buffer[1024];
    if (fd == -1) {
        perror("open");
        exit(1);
    }
    // Read from the pipe
    int num_read = read(fd, buffer, sizeof(buffer));
    if (num_read > 0) {
        printf("Received: %s\n", buffer);
    } else {
        printf("No data received.\n");
    }
    close(fd);
}
void pipe_write(const char *content) {
    // Open the pipe for writing
    int fd = open(PIPE_NAME, O_WRONLY);
    if (fd == -1) {
        perror("open");
        exit(1);
    }
    // Write the message to the pipe
    write(fd, content, strlen(content) + 1);
    close(fd);
}
int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "Usage: %s read|write [message]\n", argv[0]);
        return 1;
    }
    // Create the named pipe if it does not exist
    if (mkfifo(PIPE_NAME, 0666) == -1) {
        if (errno != EEXIST) {
            perror("mkfifo");
            return 1;
        }
    }
    if (strcmp(argv[1], "read") == 0) {
        pipe_read();
    } else if (strcmp(argv[1], "write") == 0) {
        pipe_write(argv[2]);
    } else {
        fprintf(stderr, "Invalid command. Use 'read' or 'write'.\n");
        return 1;
    }
    return 0;
}

匿名管道 int pipe (int pipefd[2]);
- pipe 返回两个文件描述符
- 适用于父子进程通信（如 fork 的），根据 fork 的返回值决定使用哪一个口
- 匿名管道通常是单向的，意味着数据只能在一个方向上流动（可以创建两个匿名管道实现双向通信）。
- 匿名管道由于不在文件系统中出现，不易被其他不相关的进程访问。

void do_parent(int fd) {
    const char *msg = "Hello, world!";
    printf("[%d] Write: '%s'\n", getpid(), msg);
    write(fd, msg, strlen(msg) + 1);
    close(fd);
    // Wait for the child to finish
    wait(NULL);
    printf("[%d] Done.\n", getpid());
}

void do_child(int fd) {
    static char buf[1024];
    ssize_t num_read = read(fd, buf, sizeof(buf));
    if (num_read == -1) {
        perror("read");
        exit(EXIT_FAILURE);
    }
    printf("[%d] Got: '%s'\n", getpid(), buf);
    // Close the read end of the pipe
    close(fd);
}

int main() {
    int pipefd[2];
    // Create a pipe
    if (pipe(pipefd) == -1) {
        perror("pipe");
        exit(EXIT_FAILURE);
    }
    // Fork the current process
    pid_t pid = fork();
    if (pid == -1) {
        perror("fork");
        exit(EXIT_FAILURE);
    }
    if (pid == 0) {
        // Child
        close(pipefd[1]); // Close unused write end
        do_child(pipefd[0]);
    } else {
        // Parent
        close(pipefd[0]); // Close unused read end
        do_parent(pipefd[1]);
    }
    return 0;
}

- 匿名管道通常用于父子进程或具有明确亲缘关系的进程之间的快速通信，如一个进程需要对另一个进程进行直接控制或频繁地传输数据。 - 命名管道更适用于需要跨多个不相关进程进行长时间或复杂交互的场景，如不同组件或程序间需要交换信息但又不方便直接使用更复杂的通信机制（如套接字）的情况。

pipe 用于连接两个应用程序：
- pipe read 在没有数据时会等待
- pipe write 在有读者打开时，写入缓冲区并返回
管道异常
- 如果写者还在运行，但是读者被关闭，就会出现 SIGPIPE 信号
- 如 python3 -c 'while True: print(1)' | head -n 1

Unix Shell¶

特殊的应用程序
- 直接和用户进行交互
- 配置操作系统，启动、管理其他应用程序
- 负责把用户指令翻译成系统调用
高效简洁精确的自然语言
- "自然编程语言"
- 一行命令，即可协同多个程序执行
Shell 执行一个命令时总是会创建新的子进程
- 如输入 ls shell 就睡 fork 一个子进程用于执行命令，父进程等待子进程执行完成之后再做进一步的处理

| 管道命令的实现原理

Shell 通过创建管道、fork 子进程和重定向标准输入输出来实现功能
对于 command1 | command2 Shell 首先创建一个管道，fork 出两个子进程分别用于执行两条命令，其中第一个子进程重定向输出到管道写口，第二个子进程重定向输入到管道读口

管道两侧的命令本质上是并行执行的两个进程，通过管道进行数据传递

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>

int main() {
    int pipefd[2];
    pid_t pid1, pid2;

    // 创建管道
    if (pipe(pipefd) == -1) {
        perror("pipe");
        exit(EXIT_FAILURE);
    }

    // 创建第一个子进程，执行 command1
    pid1 = fork();
    if (pid1 == -1) {
        perror("fork");
        exit(EXIT_FAILURE);
    }

    if (pid1 == 0) {
        // 子进程 1
        close(pipefd[0]);  // 关闭读端
        dup2(pipefd[1], STDOUT_FILENO);  // 将标准输出重定向到写端
        close(pipefd[1]);  // 关闭写端
        execlp("ls", "ls", "-l", (char *)NULL);  // 执行 command1
        perror("execlp");
        exit(EXIT_FAILURE);
    }

    // 创建第二个子进程，执行 command2
    pid2 = fork();
    if (pid2 == -1) {
        perror("fork");
        exit(EXIT_FAILURE);
    }

    if (pid2 == 0) {
        // 子进程 2
        close(pipefd[1]);  // 关闭写端
        dup2(pipefd[0], STDIN_FILENO);  // 将标准输入重定向到读端
        close(pipefd[0]);  // 关闭读端
        execlp("grep", "grep", ".c", (char *)NULL);  // 执行 command2
        perror("execlp");
        exit(EXIT_FAILURE);
    }

    // 父进程
    close(pipefd[0]);  // 关闭管道读端
    close(pipefd[1]);  // 关闭管道写端

    // 等待子进程结束
    waitpid(pid1, NULL, 0);
    waitpid(pid2, NULL, 0);

    return 0;
}

C 语言标准库的实现 libc¶

C 是一种 “高级汇编语言”，是系统调用的一层 “浅封装”
语言机制上的运行库大部分可以用 C 语言本身实现，少部分需要一些 “底层支持”（使用内联汇编）
musl 更适合阅读学习的 libc
一个 c 程序的完整执行过程
- 加载 ELF 文件到内存
- 加载器将 ELF 文件头中的 e_entry 值（入口点地址）加载到程序计数器（PC）寄存器，初始化（如设置堆栈、寄存器等）后控制权移交给程序的启动代码开始执行
- 首先在 \(\_start\) 有汇编设置一些寄存器
- \(\_start\_c\) 获取参数指针，划分为 argc、argv 等调用 \(\_\_libc\_start\_main\)，进一步得到 env 等（还有多级初始化）再调用 \(main\)（此时已经准保好了 argv、argc、envp）
- 执行 \(main\)
- 之后在 \(exit\) 内再进行一些清理，最后通过 syscall 调用 exit

计算封装¶

不依赖于系统， Freestanding 环境下也可以使用的定义
如 string.h 以及 stdlib.h 等等都封装了很多使用方法
实现这部分库函数 = C 语言课程习题

系统调用与环境抽象¶

如 printf 等操作，封装简化了系统调用的使用

linux 操作系统¶

linux 的层次结构