下面是程序锅在寒假期间根据《现代操作系统原理和实现》做的一个思维导图，完整、详细、清晰的文字版本后头会出，因为自己也想出整一套出来。
以下内容是由 XMind 根据上述思维导图的内容自动转换而来。
进程间通信
同步
-
同步原语
-
互斥锁
-
临界区问题
-
什么是临界区
- 互斥访问是指任意时刻只允许至多一个线程访问共享资源的方式，而需要被保证互斥访问共享资源的代码区域被成为临界区（个人理解就是这段代码涉及到对共享资源的访问，需要互斥访问）。
-
什么是临界区问题
- 如何通过设计协议来保证互斥访问临界区的问题
-
解决临界区问题的三个条件
- 互斥访问
- 有限等待
- 空闲让进
-
-
解决临界区问题的方法
-
硬件实现：关闭中断
- 缺点：在多核环境下，关闭中断的方法不再适用。
-
软件实现：皮特森算法
- 一个全局数组 flag，有两个布尔成员变量（flag[0]、flag[1]），分别代表两个线程能否进入临界区；一个全局变量 turn，决定最终能进入临界区的线程编号。
- 经典的皮特森算法只能应对两个线程的情况，1990 Micha Hofri 扩展了算法，使其可以被使用于任意数量的线程。
- 缺点：皮特森算法需要访存操作严格按照程序顺序执行。然而现代 CPU 为了达到更好的性能，往往允许访存操作乱序执行（编译器有时候也会使得生成的二进制中存在访存操作的乱序），因此皮特森算法无法直接在这些 CPU 上正确工作。
-
软硬结合：使用原子操作实现互斥锁
-
硬件层面
- Intel 使用带 lock 前缀的指令来保证操作的原子性（也就是一条指令前面指定了 lock 前缀之后，那么这条指令就是原子性的了）。
- ARM 使用 Load-Link/Store-Conditional（LL/SC）的指令组合。LL 的时候会使用一个专门的监控器记录当前访问的地址，而在 SC 的时候，当且仅当监视的地址没有被其他核修改，才执行存储操作，否则返回存储失败。
-
原子操作（是指不可被打断的一个或一系列操作，要么这一系列执行都执行完成，要么这一系列指令一条都不执行），使用硬件提供的指令来实现原子操作
-
CAS（Compare And Swap，比较与置换）
-
FAA（Fetch And And，拿取并累加）
-
-
互斥锁（使用硬件保证的原子操作来实现互斥锁）
-
自旋锁（使用 CAS 来实现）
-
排号自旋锁（FAA）
-
-
-
-
使用互斥锁实现生产者消费者
-
-
条件变量
-
Motivation：在单独的互斥锁环境中，会陷入循环等待，而这些循环等待是毫无意义的，不仅浪费了 CPU 资源还增加了系统的能耗。
-
VS 互斥锁
- 互斥锁和条件变量解决的不是同一个问题。互斥锁用于解决临界区问题，保证互斥访问共享资源。而条件变量通过提供挂起/唤醒机制来避免循环等待，节省 CPU 资源。条件变量需要和互斥锁搭配使用。
-
实现
-
使用条件变量实现生产者消费者
-
-
信号量（PV 原语）
-
信号是用来辅助控制多个线程访问有限数量的共享资源的（相当于互斥锁的扩展版，也可以当成互斥锁+条件变量+计数器的整合版）
-
VS 条件变量
- 条件变量和信号量都提高了类似的操作接口（wait 和 signal），但是信号量是由条件变量、计数器、互斥锁实现的（计数器是核心）。可以将信号量当成利用条件变量实现了更高级的抽象。
-
VS 互斥锁
- 二元信号量（信号量的值只能在 0 和 1 之间变化）-互斥锁有拥有着这一概念，而二元信号量没有。
- 计数信号量（非二元信号量的其他信号量）-计数信号量允许多个线程通过，互斥锁同一时刻只允许一个线程获取。
-
实现
- 基本思想
-
使用信号量实现生产者消费者
-
-
读写锁
-
Motivation：有些对共享资源的操作并不需要互斥，比如读写者问题中，读者只需要读取共享数据即可，那么读者与读者之间就不需要互斥（读者和写者之间还是需要互斥的），这个时候读者之间假如还是使用互斥锁，虽然不会导致正确问题，但是会削减读者之间的并行度，造成一定的性能损失。
-
实现
-
使用示例
-
偏向读者的读写锁
- 写者和读者同时申请进入临界区时，先允许读者进入。
-
偏向写者的读写锁
- 写者和读者同时申请进入临界区时，先允许写者进入。
-
-
-
RCU
-
简介：RCU（Read Copy Update）是一种在内核中广泛使用的同步原语，同样允许多个读者进入读临界区，但是 RCU 还可以做到写者不会阻塞读者，且读者不需要使用额外的同步原语来保护读临界区，从而有效减少在关键路径上的性能开销。
-
Motivation：虽然读写锁允许多个读者同时进入读临界区，但是写者会阻塞读者，且读者仍然需要在关键路径上添加读者锁，会造成一定的性能开销。
-
基本思想：RCU 实现使用了原子操作的技术（原子操作只是基础，相当于机制），写者在更新时是原子操作，这样读者要么读到旧的值，要么读到新的值，不会观察到任何中间结果。
-
订阅/发布机制
- 主流的现代 CPU 均提供对地址对齐的单一读写操作的原子性保证，其支持的位宽往往与 CPU 的位宽一致。比如，64 位的 CPU 往往能保证对地址对齐的 64 位数据的读写操作的原子性，也就是读写数据是原子性的。
-
-
-
考虑到写者更新的数据往往超过 64 位的限制，RCU 引入了订阅/发布机制，来利用对 64 位指针（32位机器上就是32位指针）的读写原子性。举例来说，有 A->B 这样单链表，假如想要在 A B 之间插入 C 这个节点，那么写者先将 C 这个节点生成好，同时 C 指向 B，这样只需要使用原子操作来更新 A 的 next 指针指向 C 即可。这样，读者要么读到旧值，要么读到新值。
- 宽限期
- （主要讨论何时能收回资源，RCU 引入了宽限期）
- VS 读写锁
- 读写锁和 RCU 都可以用于应对读多写少的场景，通过增加读者的并行度来提高应用程序的性能。但是，RCU 中的读者不会被写者阻塞且无须使用耗时的同步操作，因此 RCU 中的读者的开销更小。但，读写锁的接口较为方便，可以轻松用于不同的场景。
- 管程
- 线程安全
- 某个函数、函数库在多线程环境中被调用时，能够正确地使用同步原语保护多线程对共享变量的访问和修改。
- 管程概念
- 管程主要是解决开发者在实际应用程序中直接使用同步原语的负担较重的问题。
管程包含两部分：一是共享的数据，一部分是操作共享数据的函数。管程可以保证在同一个时刻最多只有一个操作者进入管程的保护区域访问共享数据。这样，开发者只需要调用管程提供的函数即可，无须使用额外的同步原语，从而减轻了开发者的负担。
相比其他同步原语：管程是一种更高级的抽象，利用其他同步原语实现了一套更加干净的接口。开发者无须考虑底层同步的实现，就能保证应用程序的正确性。
- 实例
- Java 使用 synchronized 关键字及其对应的管程来实现不同线程间的同步。Java 的管程可以保证，对其保护对象的所有代码区域，最多只有一个 Java 线程能够进入这些区域并处理数据。
// 定义 synchronized 代码块
synchronized(object)
// 定义 synchronized 方法
synchronized public void method_name(void)
-
同步带来的问题
-
死锁
-
产生的原因
-
互斥访问
-
持有并等待
-
资源非抢占
-
循环等待
-
其他
- 中断处理过程中使用了互斥锁，在获取锁后，释放锁前又发生了中断，那么也会导致死锁。
-
-
-
可以使用可重入锁来解决。可重入锁会判断锁的持有者是否为线程自己，如果是自己则不会阻塞和等待，而是通过一个计数器来记录加锁次数。这个计数器会在放锁的时候减少，当为 0 时才真正放锁。
也可以使用关中断的方式来解决，在加锁时关中断，放锁时开中断。
- 检测与恢复
- 检测
- 通过资源分配表和线程等待表来构建图，如果构建出来的图有环，那么就发生了死锁。
- 恢复
- 找到环中的任一个线程中止它并释放其占有的资源。假如释放之后还存在环，那么继续选择下一个线程进行释放，直至打破循环。
- 让环上的所有线程回退到之前某一个状态，然后再次运行。由于死锁往往是由于特定的调度和触发时机而导致的，再次运行很大概率不会发生死锁。
- 什么时候做死锁检测
- 定时监测
- 超时等待检测（如等待在某资源上超过一个限定的时间就检测一次）
- 死锁预防
- 死锁预防是指通过设计合理的资源分配算法，从源头上预防死锁。
- 基本思想：保证产生死锁的四个必要条件不被同时满足即可。
- 避免互斥访问
- 可以采用一个代理线程，多个线程假如想要访问共享资源，都向代理线程发出请求，代理线程再进行操作。这样存在的问题是大部分应用程序不容易修改此模式，对于每一个共享资源都需要一个代理线程的话，那么将会带来很大的负担。
- 不允许持有并等待
- 要求线程在真正开始操作之前一次性申请所有的资源，一旦需要获取的资源中任一资源不可用，则该线程不能成功申请这一系列资源，且该线程需要释放已经占有的资源。这样存在的问题是在资源的竞争程度较高时，一个线程很可能不能一次性拿到所有共享资源的使用权，因此会进入申请-释放的循环，造成资源利用率低，甚至出现饥饿的情况。（这种方式也会带来活锁现象）
- 允许资源被抢占
- 允许一个线程抢占其他线程已经占有的资源，这种情况下需要保证被抢占的线程能正确地恢复，然而回滚和恢复的操作十分困难，因此这种方式适合于易于保存和恢复的场景。
- 避免循环等待
- 要求线程按照一定顺序来获取资源。
- 死锁避免
- 死锁避免是通过在系统运行时跟踪资源分配过程来避免出现死锁。
- 基本思想：在系统运行时，任意线程需要新的资源都必须向系统提出申请。系统根据其所处状态，判断是否能将资源分配给线程。如果将资源分配给线程之后，系统处于安全状态，那么则将资源分配给它，如果处于非安全状态，那么则不分配资源给线程。
- 安全/非安全状态
- 安全状态是指系统中存在至少一个安全序列，如果系统按照这个序列调度线程执行，将会避免资源不足的情况发生。假如系统中不存在这样一个安全序列，那么则是非安全状态。
- 银行家算法---保证系统一直处于安全状态
- 活锁
- 活锁并没有发生阻塞，而是线程不断重复着“尝试-失败-尝试-失败”的过程（不允许持有并等待的方式），导致在一段时间内没有线程能够成功达成条件并运行下去。
没有一种统一的方法来避免活锁，需要结合具体问题来分析和提出避免方案。
- 优先级反转
- 由于同步导致线程执行顺序违反预设优先级。在实时操作系统中，优先级反转造成的后果十分严重。高优先级任务对实时性要求高，而反转会导致高优先级任务被低优先级任务阻塞，甚至错过其预定的截止时间。
- 解决方法
- 不可抢占临界区协议（Non-preemptive Critical section Protocol，NCP）
- 优先级继承协议（Priority Inheritance Protocol，PIP）
- 优先级置顶协议（Priority Ceiling Protocol，PCP）（思路是尽可能让临界区内的线程尽快执行完成）
- 即时优先级置顶协议（Immediate Priority Ceiling Protocol，IPCP）
- 原生优先级置顶协议（Original Priority Ceiling Protocol，OPCP）
- [[Linux futex]]
宏内核进程间的通信
-
管道（使用内存作为数据的一个缓冲区）
-
匿名管道
- 通过 pipe 系统调用创建，进程会拿到读写的端口（两个文件描述符）。通常结合 fork 的使用，来建立父子进程间的连接。由于，fork 会将文件描述符也复制一份，所以假如想要父子进程之间的正确通信，这个时候需要父子进程关闭多余的端口。
-
命名管道
- 使用 mkfifo 创建，需要指定一个全局的文件名，由这个文件名来指定一个具体的管道。
-
-
共享内存
-
基本思想
- 共享内存允许一个或多个进程在其所在的虚拟地址空间中映射相同的物理内存页
-
优点
- 性能好，消息队列、信号量、管道这些由于完善的抽象，虽然方便了使用，但是涉及到的数据拷贝、控制流转移等影响了抽象的性能。
-
-
消息队列
-
信号量
-
信号
-
socket
微内核进程间的通信
- Mach
- L4
