十七.同步互斥

17.1 背景

并发进程的正确性

独立进程

• 不和其他进程共享资源或状态
• 确定性->输入状态决定结果
• 可重现->能够重现起始条件
• 调度顺序并不重要

并发进程

• 在多个进程间有资源共享
• 不确定性
• 不可重现

并发进程的正确性

• 执行过程是不确定和不可重现的
• 程序错误可能是间歇性发生的

进程并发执行的好处

进程需要与计算机中的其他进程和设备进行协作

• 好处1：共享资源
  • 多个用户使用同一台计算机
  • 银行账 存款余额在多台ATM机操作
  • 机器人上的嵌入式协调手臂和手的动作
• 好处2：加速
  • I/O操作和CPU计算可以重叠（并行）
  • 程序可划分成多个模块放在多个处理器上并发执行
• 好处3：模块化
  • 将大程序分解成小程序：以编译为例，gcc会调用cpp，cc1，cc2，as，ld
  • 使系统易于复用和扩展

并发创建新进程时的标识分配

• 程序可以调用函数fork()来创建一个新的进程
  • 操作系统需要分配一个新的并且唯一的进程ID
  • 在内核中，这个系统调用会运行

3. 翻译成机器指令

• 两个进程并发执行时的预期结果（假定next_pid = 100）
  • 一个进程得到的ID应该是100
  • 另一个进程的ID应该是101
  • next_pid应该增加到102

新进程分配标识中的可能错误

方案五

利用两个原子操作实现一个锁

• Lock.Acquire()
  • 在锁被释放前一直等待，直到获得锁
  • 如果两个线程都在等待同一个锁，并且同时发现锁被释放了，那么只有一个能获得锁
• Lock.Release()：解锁并唤醒任何等待中的进程

基于原子锁的解决方案

进程的相互关系：相互感知程度

• 互斥（mutual exclusion）：一个进程占用资源，其它进程不能使用
• 死锁（deadlock）：多个进程各占用部分资源，形成循环等待
• 饥饿（starvation）：其它进程可能轮流占用资源，一个进程一直得不到资源

17.3 临界区和禁用硬件中断同步方法

临界区（Critical Section）

• 临界区（critical section）：进程中访问临界资源的一段需要互斥执行的代码
• 进入区（entry section）：
  • 检查可否进入临界区的一段代码
  • 如可进入，设置相应“正在访问临界区”标志
• 退出区（exit section）：清除“正在访问临界区”标志
• 剩余区（remainder section）：代码中的其余部分

临界区的访问规则

• 空闲则入：没有进程在临界区时，任何进程可进入
• 忙则等待：有进程在临界区时，其它进程均不能进入临界区
• 有限等待：等待进入临界区的进程不能无限期等待
• 让权等待（可选）：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）

临界区的实现方法

• 禁用硬件中断
• 软件方法
• 更高级的抽象方法

不同的临界区实现机制的比较：性能、并发级别

方法1：禁用硬件中断

• 没有中断，没有上下文，因此没有并发
  • 硬件将中断处理延迟到中断被启用之后
  • 现代计算机体系结构都提供指令来实现禁用中断

• 进入临界区：禁止所有中断，并保存标志
• 离开临界区：使能所有中断，并恢复标志

方法1：缺点

• 禁用中断后，进程无法被停止
  • 整个系统都会为此停下来
  • 可能导致其它进程处于饥饿状态
• 临界区可能很长：无法确定响应中断所需的时间（可能存在硬件影响）
• 要小心使用

17.4 基于软件的同步方法

两个线程，T0和T1，线程Ti的代码如下：

线程可通过共享一些共有变量来互斥它们的行为

Peterson算法

• 满足线程Ti和Tj之间互斥的经典的基于软件的解决方法（1981年）
• 共享变量

• 线程Ti的代码

Dekkers算法

• 可扩展到多进程
• 共享变量

• 线程Ti的代码

N线程的软件方法（Eisenberg和McGuire）

• 优点
  • 适用于单处理器或者共享主存的多处理器中任意数量的进程同步
  • 简单并且容易验证正确性
  • 支持多临界区，每个临界区对应一个锁
• 缺点
  • 忙等待锁消耗处理器时间
  • 可能导致饥饿：进程离开临界区时有多个等待进程的情况，则进程进入等待队列的顺序不一定是申请锁的顺序
  • 忙等待锁可能导致死锁：拥有临界区的低优先级进程在请求处理器，而请求访问临界区的高优先级进程已获得处理器但在等待临界区，各不相让，就构成死锁了

同步方法总结

• 锁是一种高级的同步抽象方法
  • 互斥可以使用锁来实现
  • 需要硬件支持
• 常用的三种同步实现方法
  • 禁用中断（仅限于单处理器）
  • 软件方法（复杂）
  • 原子操作指令（单处理器或多处理器均可，使用最广泛）

文章知识点与官方知识档案匹配，可进一步学习相关知识CS入门技能树Linux入门初识Linux24975 人正在系统学习中