NJU OS Notes

01 绪论 - 操作系统概述

为什么要学操作系统

• 为什么要学 X：
• 重走从无到有的发现历程，了解领域内的基本动机，基本方法，里程碑，走过的弯路。
• 最终目的：应用，创新，革命

• 为什么要学操作系统：
• 操作系统的历史就是计算机软硬件发展的历史
• 基本动机：更快更好地服务上层应用。
• 基本方法：构建抽象（Building Abstractions）
• 里程碑：Unix, Linux …

什么是操作系统

Operating System: A body of software, in fact, that is responsible for making it easy to run programs (even allowing you to seemingly run many at the same time), allowing programs to share memory, enabling programs to interact with devices, and other fun stuff like that.(OSTEP)

• 简单总结：管理软硬件资源，为程序提供服务的程序。

• 操作系统发展历史的三大线索：硬件（计算机），软件（程序），操作系统（管理硬件和软件的软件）

• 操作系统发展历史：
• 1940s：程序都非常简单，没有操作系统
• 1950s - 1960s: 高级编程语言出现，OS 此时以库函数 + 调度代码的形式存在
• 1970s：分时操作系统，支持多道程序设计

怎么学操作系统

Take away Message From JYY:

操作系统是软件和硬件之间的桥梁；因此我们 “找到” 一些合适的软件、一些相对简单的硬件，理解操作系统就会变得容易。现在，学习操作系统已经变得前所未有地简单，大家只要怀揣梦想、学会提问就可以了！

02 绪论 - 应用视角的操作系统

Everything（二进制程序）都是状态机

• 任何程序（二进制程序）都由计算 + syscall 组成，总是从被操作系统加载并设置初始状态开始，经历指令执行，最后退出。

• 应用程序 = 计算 + 操作系统 API

• 因此在应用程序视角，OS 最重要的职责是提供令应用程序舒适的抽象（对象 + API）

Everything（C 程序）都是状态机

• 首先把 C 程序改写为 Simple C

• 状态 = 所有 stack frame(包括局部变量和 PC) + 全局变量

• 初始状态：仅有一个 StackFrame(main, argc, argv, PC=0)，全局变量初始化为初始值。

• 状态迁移 = 执行 frames[-1].PC 处的简单语句

编译器与编译优化

• 编译器的输入：C 程序（= 状态机）

• 编译器的输出：汇编代码（= 状态机）

• 编译器：状态机之间的翻译器

编译优化：C 语言编译器在进行代码优化时，遵循的基本准则是在不改变程序的语义 (即程序的行为和输出结果) 的前提下，提高程序的执行效率和/或减少程序的资源消耗。

给两个程序 A, B，编译器到底允许不允许把 A 编译成 B？这个问题也就是在问 A 和 B 的语义是否等价，然而对于任意 A，B 程序，通过静态分析判断两个程序是否等价是一个不可判定问题。

• 从状态机的视角考虑：系统调用是使程序计算结果可见的唯一方法
• 不改变语义 = 不改变可见结果
• 满足C/汇编状态机生成的所有 syscall 序列完全一致，任何优化都是允许的

• 由此，不可优化的部分有：
• External function calls (链接时才能确定到底是什么代码，有可能包含系统调用)
• 编译器提供的 “不可优化” 标注 （volatile）

总结

03 绪论 - 硬件视角的操作系统

Everything（计算机系统）都是状态机

• CPU 是一个数字电路组成的系统，包括时序逻辑和组合逻辑

• 状态 = 时序逻辑元件的值（内存和寄存器的值）

• 初始状态：由设计者确定的 reset 值

• 状态迁移：组合逻辑（指令执行）

• 补充：还有外部世界的状态（外部设备等）

• 如果有多个处理器，那么状态迁移就是选择一个执行一步

Everything 都是状态机

• 截至目前，我们可以说：C 程序，二进制程序，计算机系统都是状态机。

固件：接管计算机系统的第一个程序

• 程序员如何和计算机系统交互：
• 仅靠 RESET 是不够的
• 计算机系统和 system programmers 之间确立的约定（如果你把代码放在某个位置，它就会被执行）

• 固件：厂商固定在计算机系统中的代码
• 运行程序前配置计算机系统
• 不严格地说，加载 OS

• Firmware 会扫描磁盘的前 512 字节，符合一定条件加载到 0x7c00

总结

• 处理器是无情的执行指令的机器。

• 处理器会规定好 Reset 后的行为。

• Reset 后 Firmware 开始运行，再加载操作系统。

• 厂商逐渐形成了达成共识的 Firmware Specification (IBM PC “兼容机”、UEFI、……)。

04 绪论 - 数学视角的操作系统

程序正确性

• 程序是一个状态机，也就是说它是一个数学严格的对象。

• 可以通过对程序建模在数学上证明其正确性（手工 or 通过计算机穷举）

为操作系统建模

• 应用视角：OS = 对象 + API

• 硬件视角：OS = 程序

• 操作系统 = 状态机的管理者（同时它自己也是状态机）

• 建模：自己定义状态机并模拟状态机的执行

数学视角的 OS

• 状态：多个应用程序“状态机”

• 初始状态：仅有一个 “main” 状态机，且处于初始状态

• 状态迁移：选择一个状态机执行一步

• 由此我们得到了状态图，要证明正确性，只需要在状态图上遍历，证明不存在从初始状态可达的“坏状态”

总结

• 我们可以用更 “简单” 的方式 (例如 Python) 描述状态机、建模操作系统上的应用，并且实现操作系统的可执行模型。

• 一旦把操作系统、应用程序当做 “数学对象” 处理，那么我们图论、数理逻辑中的工具就能被应用于处理程序——例如，可以用图遍历 “暴力枚举” 的方法证明程序的正确性。

05 并发 - 多处理器编程

多线程编程模型

• 多个共享内存的状态机
• C 语言状态机的多个线程
• 共享全局变量
• 每个线程有独立的栈帧
• 汇编语言状态机的多个线程
• 共享地址空间
• 独立的寄存器（比如 sp 指向各自的栈帧）

• 状态迁移：选择任意一个线程执行一步

放弃（1）：状态迁移原子性的假设

• 在单线程编程模型中，我们做了一个隐含的假设，即只有一个状态机，没有外部因素能干涉它的执行，多次状态迁移可以合并为原子性的一步。

• 但是在多线程编程模型中这个隐含的假设不再成立，由于共享内存，我们每次 load 的一个值都可能是被别的线程修改过的。

• 多线程程序正确性：通过证明（比如模型检查）来确保多线程程序的正确性，这也是数学视角的价值。

证明：∀ 线程调度方法，程序满足 XXX 性质。

放弃（2）：程序顺序执行的假设

• （recap）我们对状态机模型的隐含假设：
• 只有一个状态机，没有人干涉它的执行
• 如果不含系统调用，可以把若干状态迁移合并为原子性的一次状态迁移

• (even worse) 编译器在编译优化时也做了相同的假设：编译器会试图优化状态迁移，改变执行流

• 共享内存模型推翻的编译器的假设，但编译器依然会按照顺序执行优化代码，否则任何涉及共享内存的代码都变得不可优化。

• 在并发模型 + 编译优化的双重因素下，并发程序变得更难以理解。

• 一个经典的编译优化 + 并发带来的 bug:

• 所以在编译优化的存在下如何控制程序执行流：
• 插入不可优化的代码
• 标记变量 load 或 store 不可优化（volatile）
• 一把大🔓保平安（本课程中的推荐方法，先从这里开始再慢慢优化）

放弃（3）：存在全局指令执行顺序的假设

• （re-recap）我们对状态机模型的隐含假设：每次选择一个状态机（线程），执行一条指令。即程序的执行具有顺序一致性（sequential consistency）。

The result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

• 单处理器多线程符合 “顺序一致性” 的假设，但是现代多处理器计算机并不保证，可能会一次性取多条指令，不相干的指令可以乱序执行（处理器也是编译器，这可以看作某种编译优化）。

• 在现代多处理器计算机系统中，我们原来的简单的共享内存模型不再准确。

• 为了保证效率，实际上每个线程访问的是自己的对于共享内存的副本，这些副本之间会以复杂的关系相互同步，最终达到一致。

• CPU 设计者的难题：内存模型的易理解性 v.s. 性能的权衡。

即便我们能控制编译器生成的指令，处理器内部还隐藏了一个动态编译器——它和缓存共同作用，最终使并发程序的行为变得更难理解：并发程序执行的结果，甚至可以不是所有执行过指令的某个排列顺序运行的结果！

总结