南京大学蒋炎岩操作系统笔记（p4-p7）
P4：理解并发程序执行
Model Checker（通用检查器）负责通用任务
枚举所有可达状态
生成并探索状态转移
搜索错误状态
输出状态图
Python Generator（生成器）是后面实现Model Checker的一个关键技术
Generator 可以让一个函数"暂停"，下次再从暂停的位置继续执行。
yield会保存整个函数的执行现场（包括局部变量、程序执行位置等）。下一次next()时，会从上一次yield的下一条语句继续执行，而不是重新进入函数。
利用 Generator，Model Checker 可以控制不同线程每次只执行一步，从而模拟不同的线程调度顺序。
P5：并发控制：互斥（自旋锁、互斥锁和futex）
lock：保证一条指令原子执行，不会被其他 CPU 或线程打断。xchg：一种原子交换指令，能够一次性完成“读旧值 + 写新值”，常用于实现自旋锁等同步机制。实际开发通常使用
stdatomic.h提供的原子操作接口，而不是直接编写这些汇编指令。
利用xchg原子交换指令实现自旋锁（如果锁被别人占用，就一直在CPU上循环等待，直到锁释放）的代码：
int table = YES; void lock() { retry: int got = xchg(&table, NOPE); if (got == NOPE) goto retry; assert(got == YES); } void unlock() { xchg(&table, YES); }
其中YES表示锁是空闲的，NOPE表示锁已经被别人占用
RISC-V原子操作（LR/SC（Load-Reserved / Store-Conditional））
- LR（Load Reserved） 作用： ① 读取内存数据 ② 对该内存建立 reservation（预约/保留）
- SC（Store Conditional） 作用： 只有 reservation 未失效时才允许写入。
- 返回值： 0：写入成功 非0：写入失败（reservation 已失效）
- reservation 失效条件： 1、其他 CPU/线程修改该内存 2、中断（多数实现会取消 reservation）
- 实现流程： LR → 本地计算 → SC 成功则完成原子操作； 失败则重新执行 LR/SC，直到成功。
RISC-V 不像 x86 提供 lock add、lock xchg 等专用原子指令
RISC-V 通过
LR（预约读取）+ SC（条件写回）实现原子操作，若期间数据被其他处理器修改，则 SC 失败，需要重新尝试。
自旋锁的缺陷：
① 缓存同步开销 - 多个 CPU 不断访问同一个锁变量。 - 会触发缓存一致性（Cache Coherence），增加通信延迟，降低性能。
② CPU空转- 获得锁的线程执行临界区。 - 其他线程一直 while 循环等待（自旋），占用 CPU 但不做有效工作。 - 竞争线程越多，CPU 利用率越低。
③ 持锁线程被切换 - 持有锁的线程可能被操作系统切换出去。 - 其他线程持续自旋等待，无法进入临界区。 - 造成 CPU 100% 占用但没有有效工作，资源严重浪费
自旋锁的使用场景：操作系统内核的并发数据结构（短临界区）
实现长临界区的互斥：长临界区不适合一直自旋，而是采用“阻塞 + 唤醒”机制。
流程： ① 获得锁的线程进入临界区。 ② 后来的线程加入等待队列，并调用 yield() 主动让出 CPU。 ③ 持锁线程释放锁后，唤醒等待队列中的一个线程；若无人等待，则释放锁。
自旋锁（Spin Lock）
优点：
- 获取锁很快
- 不需要系统调用
缺点：
- 获取不到锁就一直自旋，浪费 CPU。
睡眠锁（Mutex）
优点：
- 获取不到锁就睡眠，不浪费 CPU。
缺点：
- 每次加锁、解锁都可能进入内核（系统调用），开销较大。
Futex（Fast Userspace Mutex）=自旋锁+睡眠锁
核心思想： 先在用户态尝试获取锁，只有竞争时才进入内核。
工作流程： ① 获取锁成功：用户态完成，无系统调用（Fast Path）。 ② 获取锁失败：调用 futex()，进入内核睡眠等待（Slow Path）。 ③ 解锁：若有等待线程，调用 futex_wake() 唤醒；否则直接释放锁。
优点： 无竞争时无需系统调用，速度快。 有竞争时线程睡眠，不会一直自旋浪费 CPU。
Fast Path： 用户态完成加锁/解锁，无系统调用。
Slow Path： 锁竞争时进入内核，睡眠和唤醒线程。
注意： Futex 实现复杂，容易出现竞争、死锁、丢失唤醒等问题，因此常借助 Model Checker 验证其正确性。
P6：并发控制：同步（条件变量、信号量）
在多处理器上协同多个线程完成任务。
线程同步：在某个时间点共同达到互相已知的状态（因为并发程序的步调很难保持一致，所以需要先到的先等)
经典线程同步问题：生产者-消费者模型
- 生产者：生成数据，并放入共享缓冲区。
- 消费者：从共享缓冲区取出数据并处理。
- 缓冲区：两者共享的有限空间。
也就是不断重复尝试，属于忙等待，会浪费 CPU。更合理的方式是使用条件变量或信号量，让缓冲区满或空时线程阻塞睡眠。
1、条件变量（万能同步方法）
条件变量通常用于在某个线程等待特定条件的满足时，将其挂起，并在其他线程满足条件时唤醒它。条件变量提供了一种有效的方式来实现线程之间的通信，以及在某个条件成立时阻塞和唤醒线程。
2、信号量(Semaphore)
信号量是一种基于计数器的同步机制，用于控制多个线程对有限资源的访问，也可实现线程同步。线程通过P（wait）和V（signal）操作申请和释放资源。
- P（wait）：信号量减 1；若结果小于 0（或资源不足），线程阻塞等待。
- V（signal）：信号量加 1；若有等待线程，则唤醒其中一个线程。
特点：
- 内部维护一个计数器。
- 可实现互斥（初值为 1，称二值信号量）。
- 可实现资源管理（初值大于 1，表示可同时访问的资源数量）。
- 常用于生产者—消费者问题、读者—写者问题等同步场景。
P7：真实时间的并发编程（高性能计算/数据中心/人机交互中的并发编程）
数据中心特点：低延迟、有备份、能同步
线程（Thread）
特点：
- 由操作系统调度。
- 多个线程共享同一进程地址空间。
- 可以真正利用多核 CPU并行执行。
- 获取共享资源时需要使用Mutex、信号量、条件变量等同步机制。
优点：
- 能充分利用多核 CPU。
- 适合计算密集型任务。
缺点：
- 线程切换开销较大。
- 容易出现竞争、死锁等并发问题。
协程（Coroutine）
特点：
- 由程序自身调度。
- 在用户态完成切换。
- 遇到
yield或await时主动让出执行权。 - 一个线程中可以运行多个协程。
优点：
- 切换速度快。
- 开销小。
- 编程简单，不容易产生线程竞争。
缺点：
- 通常不能充分利用多核 CPU。
- CPU 密集型任务性能不如多线程。
Go语言能像线程一样利用多核，也能像协程一样轻量。