进程间通信、同步原语
# 进程间通信、同步原语
本文为《现代操作系统：原理与实现》（陈海波著）的阅读笔记，第七章、第八章的内容概要与笔记。
# 1. 进程间通信
进程间通信（Inter-Process Communication, IPC）是操作系统最重要的内容之一。
# 1.1 基础概念
IPC常被用于服务调用，因此参与IPC的两方又被称为调用者和被调用者，或者客户端和服务端
消息传递的接口：
- Send
- Recv
- RPC(req_message, resp_message) 远程过程调用
- Reply
两种消息传递方式：
- 共享内存
- 操作系统辅助
单向与双向，同步与异步
同步IPC往往是双向IPC，即发送者需要等待返回结果（但并不绝对）。
# 1.2 宏内核进程间通信
这部分讲宏内核，下部分讲微内核。但实际上主要的通信方式就是宏内核这几种。后面微内核主要倾向于性能的讲解。因此微内核暂时忽略，主要学习宏内核的部分
一共有六种重要的通信方式：
- 管道
- 消息队列
- 信号量
- 共享内存
- 信号
- 套接字
# 管道
单向IPC，只能两个进程参与
# 消息队列
唯一一个以消息作为抽象的通信方式
可单向可双向。参与数可以为多进程。
# 信号量
就是一个共享计数器。
可单向可双向。参与数可以为多进程。
PV操作：P为减1，V为加1。信号量取值为0-1，小于0和大于1都会触发特定操作。通常来说，用作同步时，小于0会阻塞进程。
# 共享内存
顾名思义，就是维护共享的物理内存。
可单向可双向。参与数可以为多进程。
# 信号
单向IPC，但是可以多进程。
底层是个队列。
只发送一个编号（信号编号），会触发特定的处理函数。
有点类似硬件的中断，但是它是由软件发出的。
# 套接字
就是网络编程中的套接字，不过用在了本地。
只能用于两个进程，不过方向可以单可以双。
# 1.3 微内核进程间通信
# 2. 同步原语
# 2.1 互斥锁
有一些名词需要注意一下
竞争冒险：指程序的正确性依赖于执行的顺序这一现象。
互斥访问：任意时刻，只允许一个线程的访问方式。
临界区：保证互斥访问共享资源的代码区。
临界区问题：如何设计协议保证互斥访问的问题。
要解决临界区问题需要做到三点：
- 互斥访问
- 有限等待
- 空闲让进
解决临界区问题有三个大方向：
- 利用硬件：关闭中断
- 利用软件：皮特森算法
- 软硬件结合：互斥锁
# 利用硬件
当一方访问时，关闭中断。
可以满足三点条件，但是多核环境不适用。
# 利用软件
利用全局的flag[2]和true来保证两个程序互相控制。
当一个程序要运行时，只能让对方去运行，自己首先陷入等待。
注意CPU必须顺序执行。
# 软硬件结合：互斥锁
终于引出了小结的标题。
互斥锁是指利用硬件保证的原子操作，配合软件的抽象实现的一种解决临界区问题的方式。
原子操作有两种：
- CAS: Compare And Swap
- FAA: Fatch And Add
这些原子操作是硬件保证的，它们中间不能被打断，一旦开始必会被执行完。
由于有两种原子操作，因此抽象出两种互斥锁：
- 利用CAS操作，抽象出了自旋锁
- 利用FAA操作，抽象出了排号自旋锁
本部分详见P216，简要摘录一些重点：
- 大部分64位CPU对于地址对其的64位单一写操作都是原子的。
- 自旋锁并不能保证有限等待，不具有公平性
- 比如Arm移动端处理器大小核的设计，由于小核频率低于大核，有可能永远无法获得锁。
- 排号自旋锁由于每个进程领一个号码，保证了执行顺序，进而实现了有点等待。
# 2.2 条件变量
条件变量解决的问题是 循环等待的问题，使用条件变量可以挂起程序，避免其陷入“是否还有空位”这种问题上。
线程挂起时，需要保证当前已经获取了互斥锁。
# 2.3 信号量
就是前面进程间通信中的信号量。
由于其PV操作，又被称为PV原语。
PV操作的对应关系：
- P - 减1 - wait
- V - 加1 - signal
信号量的作用是：辅助控制多个线程访问有限数量的共享资源。
具体思想是：把信号量的初值设置成资源数量，如果消耗，则调用wait；如果释放，则调用signal。
# 2.4 读写锁
读写锁解决的问题是：读并不需要互斥访问。写与读，写与写之间才需要。
这部分详见P229
# 2.5 RCU，2.6 管程
略
# 2.7 同步带来的问题
# 死锁
一组线程都在互相等待对方释放资源，并且手中都持有一定资源。
死锁的条件（产生原因）：
- 互斥访问
- 持有并等待
- 资源非抢占
- 循环等待
检测死锁的方式：针对循环等待。
利用资源分配表记录不同资源被占有的情况，加上线程等待表等待资源的情况，寻找环。
死锁预防（就是针对原因的四点）：
- 避免互斥访问
- 不允许持有并等待
- 允许资源被抢占
- 避免循环等待
银行家算法
大概就是，每次有线程申请资源时，操作系统先预演一遍，判断会不会死锁，如果会就让其等待，下次再行分配。
具体看P243
# 活锁
当不允许持有资源等待时，可能会发生活锁。
具体情况是，两个进程互相申请对方所持有对的资源 - 失败 - 互相放弃自己的资源 - 再申请 - 成功 - 申请 - 失败 - 。。。。。
这样循环下去，虽然没有持有资源并等待，但是仍然无法正常进行任务。
# 优先级反转
优先级反转的例子见P247，高优先级的T1因为等待低优先级的T3，被中等优先级的T2阻塞。
优先级反转可能会导致严重的问题，例如高优先级的任务因为被阻塞而超过其截止时间（deadline)
解决优先级的方法主要有三种：
- **不可抢占临界区协议：**即临界区的线程不能被抢占，所带来的问题就是一些没有竞争关系的高优先级线程也会被阻塞。
- 优先级继承协议【现代操作系统常用】：当高优先级等待锁时，会使锁的持有者继承其优先级。
- **优先级置顶协议：**将锁的持有者线程优先级置为其竞争者中最高的优先级。