jyy os 并发
lec5 多处理器编程：
理解程序：状态机模型，我们把一个程序看成一个状态机，程序的状态是{寄存器，内存}，而每次取出一条指令、再执行的过程的就是状态迁移到过程。
由这个状态机模型，我们可以有非常多的 trick，例如 debug 单步执行，例如模拟器，例如如果某些指令是“可逆”的，就可以在 debug 的时候反向执行，“时间倒流”（gdb 也提供了这一模式）……
对于并发程序，多处理器模型，我们的直觉告诉我们，可以把这个程序看成是多个状态机，并发的过程就是每次取出一个状态机，执行一步，而所有的状态机有共享的内存（线程模型）…… 这样的模型已经足够复杂，状态数是指数增长的，解决需要考虑所有状态的问题是 NP 完全的。
但更重量级的是，这样的模型是错的！
并发编程的问题：
- load/store 的非原子性
- 编译器的优化
编译器本身也是采用“单处理器假设”，否则几乎无法完成任何涉及到共享内存的优化。求和问题的结果：O0 优化是一个[N，2N]之间的值,O1 优化是 N,O2 优化是 2N：查看汇编发现 O1 是 load－循环－store, O2 只有一个 add。解决方法要么是通过内联汇编和 volatile 等控制编译器行为，要么是加锁。还有一个有意思的例子是 while(!flag)；，如果 flag 不是 volatile 的，开编译优化会只读一次 flag，失去并发控制的效果。
- 底层硬件也是“编译器”
info
超标量，多指令重排。t1 线程 load(x), y++，print t2 线程 load(y), x++,print 在 x,y 初始为 0 的情况下可以出现 00,01,10,11 四种情况——load(a)和 b++因为不是相同的地址是可能被重排的（某种意义上的“相对论效应”，不同线程看到两个不互为因果的事件执行顺序不同）！**实际的状态机不是一步一步走的，而是一次取若干步，进行组合排序之后再执行。**这个问题的核心在于 load(x), y++这两条指令之中，如果 load(x)发生了 cache miss，要不要等待 cache hit 之后再执行 y++? 如果你允许这样的重排，那就放弃了人类友好的假设，如果不允许这样的重排，性能就大大下降。
- 内存模 型的问题, 我们认为的内存模型是每个线程都会操作一个共享内存，然而实际的存储模型是，在寄存器和内存之间还有缓存，而缓存是每个 cpu 独有的——缓存和内存又如何同步呢？
info
x86 是市面上最强一致性的模型，它几乎和我们想象之中的无缓存模型相同，各个 cpu 的缓存和全局的内存之间通过一个写缓冲同步，写指令按顺序进入写缓冲，并且会在写缓冲和内存各自读取，从而保证了顺序，并且只有一个全局内存。而 ARM 等其他模型，如果采用了其他缓存和内存同步方法，想要通过允许暂时的不同步来得到更高的性能，顺序一致性就被打破了，并发的程序在某个瞬时实际上各自有各自的内存视图，人类编写代码就更不友好。也因为这个底层硬件的处理不同，在 ARM 上模拟 x86 是一个世界性的难题。
** 对于并发，讲概念是不够的：事实可能不是我们理解的那样。讲代码都是不够的：需要精巧的 workload 才能出现某个 corner case。**
证明才是解决问题的方法！
lec6, 7 并发控制（互斥）
并发的可行性？
我们前面说明了并发问题的根本解决方 法是退化成串行——互斥执行，那并发的意义何在？
悲观角度看，如果有 1/k 的程序是没法并发的，那至少执行 1/k 的时间
乐观角度看，由于实际的物质界是“并发”的——每一个操作对周围的影响是需要时间传递的，如果我们考虑的区域足够大，宏观上每个区域就可以在一定时间段内近似看成是不影响的——图并发，物理模拟等等；并且计算任务多是可以并发的。
历史顺序：
开始阶段——软件互斥
Peterson 算法（协议）
后续阶段——硬件互斥
证明的意义：快速回答更多的问题，如果改变条件，还正确吗？公平性？死锁可能？（两人都无法进入临界区）…都转换成图（状态空间）上的遍历问题了
Perterson 算法的问题：
-
只能两个线程
-
对于现代多处理器无效
尝试实现互斥的操作
- 开关中断
问题：一，权限，OS 可以用户态不行 二，现代多处理器每个 cpu 都有自己的中断，失败
题外话：不可屏蔽中断 NMI（non-maskable interrupt），例如，当 OS 出 bug 死循环时候重启——OS 定时设置某个寄存器，如果 OS 死循环，该 NMI 检测到该寄存器未被设置，触发代码重启电脑
哪些 barrier 是必不可少的？godbolt.org
并发编程对思维方式的启示：树形广思考——如果有一个能从 1 到无穷的电脑程序（例如前面的 model checker），人只需要想足够多的 0－1 即可
- 软件不够，硬件来凑——原子指令的产生
由原子指令实现自旋锁——一个问题：如何处理中断？
T1 拿锁，中断，后续 T2,T3,…均自旋等待 T1，实质上退化成了全局中断——中断是频繁的（例如网卡） ，不可接受
实际的 OS 内部结构的自旋锁会关中断（需要保存中断状态，xv6 是使用了一个类似栈结构，上锁前 push 当前中断，解锁后 pop 当前中断）（注意始终是当前 cpu 的中断）
system 人的哲学——如果一个算法需要用几张纸才能讲清楚，那就不喜欢——prefer 简单做法的组合
自旋锁最大的问题 Scalability 太差——核数变多，反而性能下降！
只适用于几乎从不拥堵，立即完成的对象——例如链表里面插入一个元素
对于长程控制，需要用其他结构
- read-mostly 结构的优化
观察到，内核里面很多结构都是 read-mostly 的（例如路由表，用户组……）
一个非常聪明的想法：Read-copy-Update RCU 读时完全不加锁，写时拿锁吗，copy 一个新的副本，将版本控制的指针指向新的副本
其核心在于，允许在读写交错的时候，一些程序读到 v1, 一些程序读到 v2，牺牲读写的一致性换取读的强并发
甚至可以更好，实际上不一定需要复制整个对象，例如链表的插入，只需要插入时最后修改头节点的 next 指针，并且不急着删掉原先的头节点的 next 就行。下一个问题就是何时回收旧版本
- Linux 内核 trick
上面是内核态的自旋锁，那在用户态怎么得到互斥呢？如果还是用原子指令来自旋，scalability+中断问题，用户态没有关中断的权限（拿锁后中断会导致其他线程长时间空等），并且无法保证锁是短程的 ——我们想要让用户态“告诉”OS，我可以让出这个 cpu 不要空转
解决方案，将锁变成一种 syscall，陷入内核里面后再加自旋锁，关中断，如果不能获取，则等待，并且可以调度 cpu。一是解决了中断的死锁问题，二是获取了调度 cpu 的能力，也就是 ostep 的 yield()，三是有 yield 之后将一个任意长时间的互斥变成了一个短时的自旋。解锁的时候，如果有在等待的线程，就唤醒——syscall 也使得监控锁结构更方便，不需要管用户态是怎么锁的，只需要考虑内核的锁就行
更进一步，pthread，futex（fast userspace mutex）：two path
fast path: 如果直接拿到，不进 syscall
slow path: 如果没拿到，syscall 让 OS 帮我“自旋”（yield）
难的地方，T1 fast path, T2 slow path, T1 realease（一个原子指令）前面一点 T2 syscall，T1 如何唤醒 T2?
库的锁性能已经足够好——除非是极端情况，例如锁里面只是一个 sum++之类非常简单的东西
lec9、10 并发控制：同步
同步：多个线程之间相对关系的保持
状态机视角，从一个简单状态发散开之后又收回一个简单状态
第一个同步：“先来先等待”
第二个同步：生产者－消费者问题——99%的实际问题可以用这个解决
剩下 1%——条件变量解决 100%的问题 （同步：等到某一个条件的时候，做某件事）
实现一个条件变量
拿锁－如果条件（谓词）不满足 －放锁－retry（或者更好的 yield）
所以 condition_variable 就是这样的抽象，一个条件+一把锁的（优化）自旋，总是在唤醒之后再次检查条件（底层机制上 notify_one 是自然的，交给系统调度）
notify_all 的可能实现：维护一个等待条件变量的任务的链表/队列
计算任务 → 有向无环图，某些计算节点依赖于先前计算的节点
唯一的一个生产者负责遍历计算图，放入任务队列，多个消费者负责取出任务，计算执行，条件变量的条件就是依赖的计算图节点都计算完毕（例如，一个计数器）
（每一条边对应一个互斥 🔒，每一个计算节点对应一个线程。线程可以开始计算的条件是所有入边计算完毕）
只要生产者（调度器）分配效率足够高，也就是分配的时间相较任务时间小，就可以并行
例如一个不怎么好并行的，dijstra
算法核心是，从 pq 之中取出一个节点，该节点所有边 relax，如果确实更短，更新 pq
计算图为 pq→ 取出节点 →N 条边 →pq,有多条边的部分就是节点 →N 条边和 N 条边 →relax pq
中间 N 条路径可以看成任务，并行，考虑到时间问题，也可以做一个线程池，例如线程 1 对应 1－100 条边，线程 2 对应 101－200 条边，etc，最后更新 pq
并发 kmp 可行吗？计算图上每一个节点依赖前面所有节点(pi[j]相关)，不太好做
并发 kruskal? 取出全局最小这个计算任务可以变成维护几个局部最小的堆，可以并行
……
这个角度能发现一些意外可以并行的，例如动态规划
最长公共子序列为例， dp[i,j]依赖于 dp[i,j-1], dp[i-1,j]和 dp[i-1,j-1]
也就是二维图上，右下角依赖于上左左上
那对这样的图进行拓扑排序，每一层都是右上－左下的一条对角线！并行度不断增加！
（当然实际上这个问题 cache 也占很大一部分）
万能同步方法：状态机之中“历史”的部分
例如，有一堆线程 a 打印 H，另一堆线程 b 打印 O，另一堆线程 c 打印空格，要求总是打印出来为
空格 HHO 或者 空格 HOH
状态机为
空格->H->H->O回空格
->O->H回空格
H：前面是 H，后面是 O；前面是 O，后面是空格；前面是空格，后面 H 或 O
O：前面第 二个是 H，后面是空格；否则是 H
空：后面 H
三组线程等待条件变量“可以打印 H，O，空格”，而维护一个值代表前面两个是什么，逐一匹配各条规则，唤醒条件变量上等待的线程
计算图的方法是实际可用的
每一条边分配一个信号量，初始为 0
每个计算任务对应一个点，对所有入边 P
从初始点开始，计算，完成后 V 所有出边，到算完所有点结束（没有出边）
信号量的核心：
1.允许在一个线程里面获得锁，另一个线程里面释放锁
2.允许 N≥1 个线程进入（能计数的互斥锁）
信号量的典型应用：
- A→V(s)→P(s)→B 一次性 happen-before
- mutex 的 N 个准入拓展
信号量优雅实现生产消费者