操作系统原理（九）之并发编程同步互斥
操作系统原理
同步互斥是操作系统当中协调进程之间动作和相互关系的一种机制。
进程类型
独立进程
- 不和其他进程共享资源或状态
- 确定性–输入状态决定结果
- 可重现–能够重现起始条件
并行进程
当系统有一个以上CPU时,则线程的操作有可能非并发。当一个CPU执行一个线程时，另一个CPU可以执行另一个线程，两个线程互不抢占CPU资源，可以同时进行，这种方式我们称之为并行(Parallel)
并发进程
当有多个线程在操作时,如果系统只有一个CPU,则它根本不可能真正同时进行一个以上的线程，它只能把CPU运行时间划分成若干个时间段,再将时间 段分配给各个线程执行，在一个时间段的线程代码运行时，其它线程处于挂起状。.这种方式我们称之为并发(Concurrent)
- 在多个进程间共享资源
- 不确定性
不可重现
调度顺序不重要
并发进程的正确性
- 执行进程是不确定性和不可重现的
- 程序错误可能是间歇性发生的
并发进程的优势
- 共享资源
进程需要与计算机中的其他进程和设备进行协作
- 加速
I/O操作和CPU计算可以重叠（并行）
- 模块化
程序可划分成多个模块放在多个处理器上并行执行
将大程序分解成小程序
使系统易于复用和扩展
并发编程的实现
- 并发编程的实现方式一种是多进程的并发，一种是多线程的并发。
- 从操作系统的角度来看，进程是资源分配的基本单位，线程是任务调度的基本单位，线程是轻量级的进程但它不能脱离进程存在，也就是说线程使用的资源都是从宿主进程获得的。
- Python中可能就会取决于IO密集型还是CPU密集型在两种并发方式之间进行权衡
并发进程的创建
- 调用函数fork()来创建一个新的进程
操作系统需要分配一个新的并且唯一的进程ID标识
在内核中，这个系统调用会运行 new_pid = next_pid++
翻译成机器指令
- 两个进程并发执行时的预期结果（假定是 next_pid = 100）
一个进程得到的ID应该是100
另一个进程的ID应该是101
next_pid应该增加到102
- 新进程标识中的可能错误
两个不同的新进程分配了一样的new_pid，且next_pid只增加了1
进程的交互关系
| 相互感知的程度 |
交互关系 |
进程间的影响 |
| 相互不感知（完全不了解其他进程的存在） |
独立 |
一个进程的操作催其他进程的结果无影响 |
| 间接感知（双方都与第三方交互，如共享资源） |
通过共享进行协作 |
一个进程的结果依赖于共享资源的状态 |
| 直接感知（双方直接交互，如通信） |
通过通信进行协作 |
一个进程的结果依赖于从其他进程获得的信息 |
四种进程或线程同步互斥的控制方法
1、临界区:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。
2、互斥量:为协调共同对一个共享资源的单独访问而设计的。
3、信号量:为控制一个具有有限数量用户资源而设计。
4、事 件:用来通知线程有一些事件已发生，从而启动后继任务的开始。
基本概念
- 临界区（critical section）
进程访问临界资源的一段需要互斥执行的代码
- 进入区（entry section）
检查可否进入临界区的一段代码
如可进入，设置相应“正在访问临界区”标志
- 退出区（exit section）
清除“正在访问临界区”状态
- 剩余区（remainder section）
代码中的其余部分
临界区
临界区访问规则
- 空闲则入
没有进程在临界区时，任何进程可进入
- 忙则等待
有进程在临界区时，其他进程均不能进入临界区
- 有限等待
等待进入临界区的进程不能无限等待
- 让权等待（可选）
不能进入临界区的进程应释放CPU（如转换到阻塞状态）
临界区的实现方法
禁用中断 软件方法 更高级的抽象方法
详见 实现临界区互斥的基本方法
禁用中断
进程互斥锁Lock 高级抽象方法
- 锁是一个抽象的数据结构
一个二进制变量（锁定/解锁）
Lock :: Acquire()
锁被释放前一直等待，然后得到锁
Lock :: Release()
释放锁，唤醒任何等待的进程
使用锁来控制临界区访问
- 使用TS指令实现自旋锁（spinlock）
如果锁被释放，那么TS指令读取0并将值设置1
锁被设置为忙并且需要等待完成
如果锁处于忙状态，那么TS指令读取1并将值设置为1
不改变锁的状态并且需要循环
- 特点：
线程在等待的时候消耗CPU时间
无忙等待锁 （忙等待、无忙等待）
原子操作指令锁
优点
- 运用于单处理器或者共享主存的多处理器中任意数量的进程同步
- 中断禁用只适用于单处理机
- 简单并且容易证明
- 支持多临界区
缺点
- 忙等待消耗处理器时间
- 可能导致饥饿
进程离开临界区时有多个等待进程的情况
并没有做到按先来后到的顺序来使用资源，因为在锁的请求操作当中，放到就绪队列之后会再去检查。若在检查的时候资源出于空闲状态，那就申请到了。回来的时候，实际上各个线程把就绪队列排定的顺序并不见得是申请锁的顺序
- 拥有临界区的低优先级进程
- 请求访问临界区的高优先级进程获得处理器并等待临界区
- 低优先级等待CPU，高优先级等待临界区资源
