南京大学蒋炎岩操作系统笔记（p4-p7）

P4理解并发程序执行Model Checker通用检查器负责通用任务枚举所有可达状态生成并探索状态转移搜索错误状态输出状态图Python Generator生成器是后面实现Model Checker的一个关键技术Generator 可以让一个函数暂停下次再从暂停的位置继续执行。yield会保存整个函数的执行现场包括局部变量、程序执行位置等。下一次next()时会从上一次yield的下一条语句继续执行而不是重新进入函数。利用 GeneratorModel Checker 可以控制不同线程每次只执行一步从而模拟不同的线程调度顺序。P5并发控制互斥自旋锁、互斥锁和futexlock保证一条指令原子执行不会被其他 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/SCLoad-Reserved / Store-ConditionalLRLoad Reserved 作用 ① 读取内存数据 ② 对该内存建立 reservation预约/保留SCStore 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。缺点每次加锁、解锁都可能进入内核系统调用开销较大。FutexFast Userspace Mutex自旋锁睡眠锁核心思想 先在用户态尝试获取锁只有竞争时才进入内核。工作流程 ① 获取锁成功用户态完成无系统调用Fast Path。 ② 获取锁失败调用 futex()进入内核睡眠等待Slow Path。 ③ 解锁若有等待线程调用 futex_wake() 唤醒否则直接释放锁。优点 无竞争时无需系统调用速度快。 有竞争时线程睡眠不会一直自旋浪费 CPU。Fast Path 用户态完成加锁/解锁无系统调用。Slow Path 锁竞争时进入内核睡眠和唤醒线程。注意 Futex 实现复杂容易出现竞争、死锁、丢失唤醒等问题因此常借助 Model Checker 验证其正确性。P6并发控制同步条件变量、信号量在多处理器上协同多个线程完成任务。线程同步在某个时间点共同达到互相已知的状态因为并发程序的步调很难保持一致所以需要先到的先等)经典线程同步问题生产者-消费者模型生产者生成数据并放入共享缓冲区。消费者从共享缓冲区取出数据并处理。缓冲区两者共享的有限空间。也就是不断重复尝试属于忙等待会浪费 CPU。更合理的方式是使用条件变量或信号量让缓冲区满或空时线程阻塞睡眠。1、条件变量万能同步方法条件变量通常用于在某个线程等待特定条件的满足时将其挂起并在其他线程满足条件时唤醒它。条件变量提供了一种有效的方式来实现线程之间的通信以及在某个条件成立时阻塞和唤醒线程。2、信号量(Semaphore)信号量是一种基于计数器的同步机制用于控制多个线程对有限资源的访问也可实现线程同步。线程通过Pwait和Vsignal操作申请和释放资源。Pwait信号量减 1若结果小于 0或资源不足线程阻塞等待。Vsignal信号量加 1若有等待线程则唤醒其中一个线程。特点内部维护一个计数器。可实现互斥初值为 1称二值信号量。可实现资源管理初值大于 1表示可同时访问的资源数量。常用于生产者—消费者问题、读者—写者问题等同步场景。P7真实时间的并发编程高性能计算/数据中心/人机交互中的并发编程数据中心特点低延迟、有备份、能同步线程Thread特点由操作系统调度。多个线程共享同一进程地址空间。可以真正利用多核 CPU并行执行。获取共享资源时需要使用Mutex、信号量、条件变量等同步机制。优点能充分利用多核 CPU。适合计算密集型任务。缺点线程切换开销较大。容易出现竞争、死锁等并发问题。协程Coroutine特点由程序自身调度。在用户态完成切换。遇到yield或await时主动让出执行权。一个线程中可以运行多个协程。优点切换速度快。开销小。编程简单不容易产生线程竞争。缺点通常不能充分利用多核 CPU。CPU 密集型任务性能不如多线程。Go语言能像线程一样利用多核也能像协程一样轻量。