进程间通信、同步原语
# 进程间通信、同步原语
本文为《现代操作系统:原理与实现》(陈海波著)的阅读笔记,第七章、第八章的内容概要与笔记。
# 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)
解决优先级的方法主要有三种:
- **不可抢占临界区协议:**即临界区的线程不能被抢占,所带来的问题就是一些没有竞争关系的高优先级线程也会被阻塞。
- 优先级继承协议【现代操作系统常用】:当高优先级等待锁时,会使锁的持有者继承其优先级。
- **优先级置顶协议:**将锁的持有者线程优先级置为其竞争者中最高的优先级。