多线程程序的状态机模型
[!hint]
- 并发
- 逻辑上的"同时执行"
- 通过操作系统或者运行库(java)模拟的"轮流执行"
- 并行
- 真正意义上的"同时执行"
- 共享内存的多个处理器
不同时读写，导致数据覆盖
虚拟化给了进程Determinism：
为了更快的读取速度性能
数据先写入CPU的cache，再同步给其他处理器
允许读取到旧值
现代处理器的“乱序执行”
对于解决并发1+1 -> 阻止同时的sum++ 互斥
| 特征 | 乐观锁 | 悲观锁 |
|---|---|---|
| 冲突假设 | 假设冲突很少 | 假设冲突频繁 |
| 加锁时机 | ==操作前不加锁，提交时检查冲突== | ==操作前立即加锁，阻塞其他线程== |
| 性能 | 无锁操作，冲突少时性能高 | 有锁操作，冲突多时性能稳定 |
| 实现复杂度 | 需要版本号、CAS 等机制 | 依赖操作系统或数据库的锁机制 |
| 典型场景 | 高并发、低冲突（如数据库更新） | 低并发、高冲突（如银行账户操作） |
永远不要用不要用共享内存做互斥 数据有传播延迟，CPU核心有自己的内存（Cache），核心之间的内存共享做懒处理 编译器会优化
电脑是人造的，BYD我是土皇帝
把锁的层级提升到硬件，Atomos原子指令 通过Atomos，在硬件层面上实现一个类似下面锁代码：
cvoid lock() {
retry:
if (can_go == ![✅]) {
can_go = ![❌]; // then function returns
} else {
goto retry;
}
}
void unlock() {
can_go = ![✅];
}
==而对于那些使用原子指令实现的并发层序，都是硬件基于上面实现的锁==
[!example] 各个CPU架构上的Atomos
- 一个 “不被打断” 的 load + 计算 + store
- x86: Bus Lock (locked instruction)
- RISC-V: LR/SC & A 扩展
- 来自 MIPS: Load-Linked/Store-Conditional >(LL/SC)
- arm: ldxr/stxr, stadd (store add) 指令
对于每一个临界变量都有自己的一把锁，自旋锁
硬件提供机制解决问题，操作系统再实现程序提高性能
SYSCALL_acquire(&lk)
SYSCALL_release(&lk)
pthread_mutex_t lock最通用且性能平衡互斥实现了原子性，保证了A->B OR B ->A 但是由于线程的先后顺序不确定，A->B的稳定性还没有保障
[!tip] 理解并发的方法
- 线程 ->我们自己
- 共享内存 ->物理空间
对于互斥来说，只能做到分开
理解同步：什么是事件（代码的执行）、什么是顺序
老方法，古法同步（
性能优化
任何同步问题都需要锁🔒 ==条件变量总是和一个互斥锁联合使用==
mutex_lock(🔒); while (!cond) { // cond 可以是任意的计算 cond_wait(&cv, 🔒); } assert(cond); // 此时 cond 成立且持有锁 lk mutex_unlock(🔒);
// 注意锁的使用 mutex_lock(🔒); cond = true; cond_broadcast(&cv); // 唤醒所有可能继续的线程 mutex_unlock(🔒);
万能的同步方法：条件变量
而使用条件变量，只需要回答一个问题： ”什么时候执行方法？“
节点想要执行，所有的依赖节点已经完成（可以用一把大锁同步一轮）
实现一个任务的调度器Scheduler
实现同步->Happens-Before->条件变量 实现互斥->互斥锁
[!question] 互斥锁实现同步？ 我们通过mutex互斥锁，实现线程之间的互斥运行 实际上在这些互斥的线程中，也存在一种Happens-Before的关系（A to B / B to A）
而同步的实现是基于各个线程Happens-Before关系 因此，我们是否能借助Mutex来实现一个更高效的同步呢——信号量
对上面的想法进行抽象，本质上是Release-Acquire实现了Happens-Before
信号🚨在这里可以视为一种资源许可
Faker！信号量 VS 条件变量，你们知道吗？
count不总是能很好地代表同步条件更复杂的同步问题——复杂的条件变量？
[!example] 哲♂学家吃饭 ![[file-20250513195719748.png]] 哲♂学家们一起吃饭，他们有时会思考有时会吃饭。 吃饭的时候需要举起他们左右手的叉子，只有举起左右手的叉子后，他们才会开始吃饭。
- 问题：吃了很久很久后，于是乎在某一个时刻，所有哲学家同时都举起左手的叉子，大家就都等待右手的叉子
并非完美，信号量不总是优雅
数值型资源不能总是很好地表达同步条件
引入调度者，统一管理全部资源（叉子）
并发编程困难的本质
Data Race 数据竞争 不同的线程==同时==访问同一内存，且至少有一个是写
Atomicity Violation 原子性违反 一个操作序列（多个相关操作） 在执行过程中被其他线程中断，导致部分操作完成而另一部分未完成，破坏整体逻辑一致性
Order Violation 顺序违反 事情未按预定的顺序发生![[file-20250516185226498.png]]
Deadlock 死锁 -> 数据竞争
[!PDF|yellow] [[操作系统导论 ( etc.) (Z-Library).pdf#page=294&selection=10,0,24,20&color=yellow|操作系统导论 ( etc.) (Z-Library), p.294]]
- 互斥：线程对于需要的资源进行互斥的访问（例如一个线程抢到锁）。 - 持有并等待：线程持有了资源（例如已将持有的锁），同时又在等待其他资源（例如，需要获得的锁）。 - 非抢占：线程获得的资源（例如锁），不能被抢占。 - 循环等待：线程之间存在一个环路，环路上每个线程都额外持有一个资源，而这个资源又是下一个线程要申请的。如果这 4 个条件的任何一个没有满足，死锁就不会产生
非死锁问题 -> 原子性/顺序违反
Lock Ordering
原子操作
[!check] 用好现代的程序工具 开发者社区已经为这些MillionDollorsMistake尽可能地提供解决方案
然而，在计算图的实现上，原子性、信号量和条件变量虽然提供了基础的同步条件功能，但这并不是计算图优雅的实现方式（好比用汇编代码做开发......）
在实现这些同步条件的时候，我们代码中往往会充斥许多的干扰代码，而往往我们会在这里犯错（比如上错锁，或者忘记上锁）![[assets/并发编程/file-20250527131756842.png]]
然而，在长期的编程实践中，程序员们总结出了一定的规律，能为我们提供一些封装的方法功能实现计算图
Embarrassingly parallel（易并行）的计算（物理计算）
通常计算图容易静态切分
Web2.0的到来，带来了并发的需求
event-based concurrency（动态计算图）
Callback Hell
Promise
“框架” 是驱动技术发展的原动力
我们需要好的抽象来表达人类世界中的需求
不同于高性能计算，以海量分布式数据（存储）为中心
实时的 “小数据处理”
离线的 “大数据处理”
数据中心里的并发问题
Challenge: 高可靠、低延迟的多副本分布式存储和计算
和线程概念相同
小孩子才做选择，多处理器并行和轻量级并发我全都要！
Goroutine 实现
什么是CPU？ 无情的执行指令的机器（并非）
CPU其实一直在并行编程 指令的执行也是一种计算图，对于没有数据依赖多条指令，CPU可以从PipeLine上预读多条指令，然后构建一个并行的计算图执行
每个 CPU 核心都是一个编译器
这意味着什么？——用数字电路实现一个编译器
[!example] Dark Silicon “暗硅时代”
- P=C⋅V2⋅f
- “功耗墙”：纵使有更大的电路，热功耗限制了性能上限
[!summary] 向量指令 向量指令（Vector Instruction）是一种单指令多数据（Single Instruction, Multiple Data, SIMD）的指令形式，它通过一条指令同时对多个数据元素进行相同的操作，从而显著提升数据处理效率。这种指令集设计主要用于并行计算场景，尤其适合需要处理大规模数据的高性能计算、多媒体处理和机器学习等领域。
[!info] 图形渲染原理——GPU的由来 计算屏幕上每个像素点要展示的RGB Value（光照的变化等......） ![[assets/并发编程/file-20250530163954871.png]] 而对于屏幕上的每个像素点（也就是Shader函数）都是可以并行的，我们就需要大量的线程实现并行（2,073,600个线程）
SIMT（Single instruction, multiple threads） ——GPU上的并行 单指令多线程：多个Cores共享一个PC，实现所有线程同步执行相同指令
线程发散
[!summary] 线程发散 线程发散（Thread Divergence） 是指同一线程束（Warp/Wavefront）中的线程因条件分支（如
if-else）进入不同的执行路径，导致GPU无法并行执行所有线程，从而降低效率的现象
- CPU为了执行业务逻辑，要执行、加载很多离散的代码。 因此CPU更擅长处理线程发散，而对于要同时执行大量的相同指令，优化是很差的
- 而线程发散对于GPU执行指令的损耗是很大的，但是多线程重复指令GPU很擅长
因此，当你的程序对内存的访问，符合正确的模式时，GPU才能发挥最大的带宽