Operating System

孤立程序

1. C程序视角

• 状态机描述

• 状态 = 堆H + 栈S

  • 栈帧列表(含PC) + 全局变量

  • 开辟一段栈空间，存在栈指针寄存器(栈指针esp)、基址寄存器(帧指针ebp)

  • 栈帧（从高地址往下生长）保存：函数的返回地址和参数，临时变量，函数调用上下文

• 初始状态 = main第一条语句

  • 全局变量初始化

• 状态转换 = 指针移动到下一条语句，并执行该语句

  • 函数调用：push 函数入口的PC到栈帧里
  • 函数返回：pop 栈帧

• 应用：

  • 递归程序使用了系统栈，所以手动模拟系统栈，就能将递归程序转为非递归

2. 汇编代码视角

• 状态机描述
• 状态 = 内存M + 寄存器R
  • 栈帧中保存的其实就是寄存器R的状态
  • 硬件先保存一部分，交付软件后，软件再保存所有
• 初始状态 = Label为_start的汇编中的第一条指令
• 状态转换 = 执行一条指令

操作系统中的程序

• 与程序的状态机几乎一致，稍微有点不同

• 孤立程序只能执行计算指令

• 而操作系统程序存在==系统调用syscall==。

  • 系统调用syscall：准备好程序的当前状态(M,R)，传递状态给软件，将本身完全交由操作系统
  • 操作系统程序 = 计算 + syscall
  • 使用strace查看程序运行时调用的syscall
  • 操作系统提供API给上层，它们都需要相应权限
  • 操作系统中程序状态机的初始状态略有不同
  • 不在main，也不在_start中
  • 是==程序的动态链接器==中的第一条指令，负责链接程序运行时所需的动态库
  • 例如linux-x86：/lib64/ld-linux-x86-64.so.s
  • 技巧：使用__attribute__((constructor))或__attribute__((destructor))

编译器

1. C程序视角 -> 汇编代码视角

• 编译的实质是状态机转换
• 如何保证编译正确性？
• 可观测行为一致：但实际上我们目前只是实现了单核编译器的正确性
  • 最终内存一致性 Eventual memory consistency
  • 写回
• 逻辑层面完全一致：解释执行/基于语义的直接翻译，低效

2. 宽松内存模型下的编译优化

• 宽松内存模型：只保证可观测行为一致，给这样一个稍宽松的前提实现代码rewriting
• 比如：Inline assembly，Call to external CU = write back visible memory

并发

1. 线程

• 实质是单个共享内存中的多个执行流
• 拥有独立的状态(M,R)或者叫(H,S)
• 共享全部的内存：指针可以互相引用，它也能用来实现线程同步
• 单个共享内存是由谁来管控呢？
• 单个进程管理一个内存空间，其中有多个执行流

2. 简化的线程操作

• create：创建一个入口函数为fn(int tid)的新线程，并立即执行

• tid为线程号

• 语义：新增一个stack frame列表，并初始化为fn(tid)

• join：等待所有运行线程的fn返回

• 运行main的线程也会自动join，即等待所有线程结束

• 语义：在其他线程未执行完时，进入==死循环==；否则返回

3. 现代并发中出现的问题

• 并行与并发的关系

• 并行是同时间点发生，范围较严格；并发是同时间段发生，范围较宽松。并发包含了并行。

• 单核处理器只能并发：一个时间段内，线程执行时可能会被中断，并切换到另一个线程执行

• 而多核处理器除并发外，还可以并行：一个时间点，多个核心的线程同时执行

• 并发导致了==原子性的丧失==：一段代码/指令的执行不可能独占整个计算机

• 内存中读后写指令(load+store)默认不是一条原子指令，可能会被打断或干扰

• 解决：实现互斥（保证临界区==如共享内存==中指令的串行化），保证原子性

• 编译器优化导致了==同步性与顺序一致性的丧失==：编译器会以单线程的思路对多线程的程序进行优化

• 编译器会进行：顺序指令的重排序、保证最终内存一致性

• 而并发程序中共享内存可以保证线程同步、指令也不是顺序进行的
• 这样的优化会让线程同步失效、数据相关指令的顺序被重排

• 解决：

  • 提供volatile，保证变量所在内存的读写操作，不被优化
  • 利用volatile实现memory barrier，防止指令重排
  • 利用mfence或者其他原子指令

• 现代处理器导致了==可见性的丧失==：CPU也是特殊意义上的编译器(汇编$OP$->$\mu OP$)，它里面也有类似的优化

• CPU会进行：指令乱序发射，按序提交，尽可能多执行$\mu OP$

• 也就是说，就算汇编指令确定了正确顺序，CPU中issue后的execute顺序也不一定是这个顺序

实现互斥

1. Peterson算法与Dekker算法

背景：

• 那时没有原子指令，load和store是两条指令，因此实现锁的lock和unlock时会线程冲突，所以提出了Peterson协议

我称Peterson算法为谦让算法，还有一个类似的算法是Dekker算法

这个算法实际上是一个protocol，目的是防止线程A因为速度太快，在线程B提出访问请求前，直接提出请求并访问了

• 不阻止就形成不了线程的竞争关系，自然就不能实现互斥

内容：

• A提出访问请求（举旗），B提出访问请求（举旗）
• A覆盖占用标识（申请让B先用）

• B覆盖占用标识（申请让A先用）

• 此时的A先用标识覆盖了之前的B先用标识

• 情况：

• 如果除了自己没人举旗子，则进入；

• 如果自己举了旗子，且标识为自己先用，则进入；
• 否则等待
• 举旗的目的：
• 让进程知道现在是不是需要处理互斥
• 谦让的目的：
  • 不让自己投票后立刻进去。当然，如果对方不举旗就没有这个担忧了。

2. 验证正确性

• 手画状态机
• 使用Model Checker，用BFS等+优化绘制一个图的所有状态空间
• 模拟线程：使用Python Generator，即yield关键字

3. lock前缀————硬件实现原子性

• 由于内存中读后写指令(load+store)默认不是一条原子指令，我们除了使用Peterson算法等软件机制，我们还能用硬件机制————实现一条load后立即store的原子指令

• 最简单的一个：lock xchg原子指令

• 更多的原子指令在stdstomic.h中间接调用

• 需要硬件保证：store一定写入内存、lock指令之间一定有确定的顺序而不是乱序

4. 实现互斥1：用原子指令实现Spin Lock

• 设置一个共享变量isLock = Key

• 当需要load+store时，且isLock == Key，则用xchg将isLock原子置换为NoKey。执行完load+store后，将isLock置换回Key

• 当需要load+store时，且isLock != Key，则==循环查看isLock==，直到符合置换条件

• 自旋锁：当变量被自旋锁锁上时，申请线程需要循环查看锁状态，直到解锁

• 由于OS具有中断机制，上述的自旋锁不够完整：

• 给资源上锁后，OS触发外部中断，但是中断程序内部也需要使用该资源，因此中断程序会由于==无法得到资源==而被挂起，发生死锁。

• 理想的fix：lock-unlock期间强制关闭中断，或者保持lock-unlock期间中断状态不变
  • 实现中断状态不变：保存中断状态I并禁止中途中断，中断全局/每CPU/每线程设置一个中断计数器，初值为0，lock就+1，unlock就-1，当值为0时就恢复中断为I

• 但是关闭中断或者保持中断的代价太大了

• 优化：Read-Copy-Update（牺牲部分CPU的读写一致性）

• 给资源设置一个指针，指向当前版本

• 上锁时，不改写原版本，而是创建一个一致的副本并修改为新版本

• 新版本创建完后，将指针指向新版本

• 等所有CPU都切换过一次版本了，就将旧版本删除

• 自旋锁的劣势：

• 由于等待线程循环查看isLock，使得线程过多反而性能越低

• 自旋锁实现互斥需要保持中断状态，代价太大
• 因此自旋锁只适合短临界区

5. 实现互斥2：Mutex Lock

• 与自旋锁的实现一致，只是由OS来间接上锁/解锁
• 线程使用Syscall提交一个上锁请求，OS查看资源是否已经有锁
• 若无，则获得资源
• 若有，OS调度CPU切换线程，将请求线程放入等待队列，直到资源解锁再唤醒
• 线程使用Syscall提交一个解锁请求
• 与Spin Lock的区别：
• 自旋一次失败时：线程直接进入等待，而不是循环查看isLock，即它只会执行一次spin，效率比Spin Lock快。
• 自旋一次成功时：线程需要进入OS一次才能开始使用资源，效率比Spin Lock慢。