操作系统（九） – 同步

目录

1. 背景

2. 一些概念

2.1 竞态条件

2.2 原子操作

2.3 产生竞争的示例

2.4 冰箱例子进行类比

2.4.1 使用便签

2.4.2 使用便签（二）- 将便签放在第一位 

2.4.4 更复杂的两种便签 

2.4.5 临界区

3. 临界区

3.1 临界区的属性 

4. 对临界区代码保护的方法1： 禁用硬件中断

5. 方法2： 基于软件的解决方法

5.1 假设的模型 

5.2 使用turn来实现

5.3 改进，使用flag[]

5.4 调整顺序后的flag []

5.5 正确的解法

5.5.1 代码 

5.5.2 代码2(更为复杂，了解）

5.6 n个进程的算法

5.6.1  Bakery算法 

6. 方法3： 更高级的抽象

6.1 基于硬件的解决方法

6.2 假定是一个lock编程抽象

6.3 实现lock

6.4 示例（看起来有很多行代码，但是硬件上实现了，在执行时是一个整体，不允许被打断）

6.5 代码设计，支持n个进程

6.6 可以进一步改进，解决忙等

6.6.1 把等待的进程放在等待队列，进行睡眠

6.7 优点

6.8 缺点 

6.9 总结

---

 

1. 背景

• 独立的线程:
  • 不和其他线程共享资源或状态
  • 确定性→输入状态决定结果
  • 可重现建→能够重现起始条件，I/0
  • 调度顺序不重要
• 合作线程:
  • 在多个线程中共享状态
  • 不确定性
  • 不可重现

不确定性和不可重现意味着bug可能是间歇性发生的

 既然有风险，为什么需要合作

• 进程/线程，计算机/设备需要合作
• 优点1: 共享资源
  • 一台电脑，多个用户
  • 一个银行存款余额，多台ATM机
  • 嵌入式系统(机器人控制:手臂和手的协调)
• 优点2:加速
  • I/0操作和计算可以重叠
  • 多处理器-将程序分成多个部分并行执行
• 优点3:模块化
  • 将大程序分解成小程序
    • 以编译为例，gcc会调用cpp, ccl, cc2, as, ld
  • 使系统易于扩展

原子性问题 

我们希望程序具有的特性 

• 无论多个线程的指令序列怎样交替执行，程序都必须正常工作
  • 多线程程序具有不确定性和不可重现的特点
  • 不经过专门设计，调试难度很高
• 不确定性要求并行程序的正确性
  • 先思考清楚问题，把程序的行为设计清楚
  • 切忌急于着手编写代码，碰到问题再调试

2. 一些概念

2.1 竞态条件

 系统缺陷:结果依赖于并发执行或者事件的顺序/时间

• 不确定性
• 不可重现

怎样避免竞态/p>

让指令不被打断

2.2 原子操作

• 原子操作是指一次不存在任何中断或者失败的执行
  • 该执行成功结束
  • 或者根本没有执行
  • 并且不应该发现任何部分执行的状态
• 实际上操作往往不是原子的
  • 有些看，上去是原子操作，实际上不是
  • 连x++这样的简单语句，实际上是由3条指令构成的
  • 有时候甚至连单条机器指令都不是院子的
    • Pipeline， super- scalar, out-of-order， page fault

2.3 产生竞争的示例

•  Critical section (临界区)
  • 临界区是指进程中的一段需要访问共享资源，并且当另一个进程处于相应代码区域时便不会被执行的代码区域
• Mutual exclusion (互斥)
  • 当一个进程处于临界区并访问共享资源时，没有其他进程会处于临界区并且访问任何相同的共享资源
  • 不允许临界区有其它的进程
• Dead lock (死锁)
  • 两个或以上的进程，在相互等待完成特定任务，而最终没法将自身任务进行下去
• Starvation (饥饿)
  • 一个可执行的进程，被调度器持续忽略，以至于虽然处于可执行状态却不被执行

2.4 冰箱例子进行类比

问题：可能出现重复购买面包的情况。 

解决重复购买面包的本质

1.  最多有一个人去买面包
2. 如果需要，有人回去买面包

解决的方法： 例如，在冰箱.上设置-个锁和钥匙( lock&key )

1. 去买面包之前锁住冰箱并且拿走钥匙
2. 修复了“太多”的问题:要是有人想要果汁怎么办/li>
3. 可以改变“锁(lock) ”的含义
4. “锁(lock)”包含“等待(waiting) ”

锁、死锁、解锁 

• .Lock (锁):在门、抽屉等物体，上加上保护性装置，使得外人无法访问物体内的东西，只能等待解锁后才能访问。
• Unlock (解锁) :打开保护性装置,使得可以访问之前被锁保护的物体类的东西。
• .Deadlock (死锁) : A拿到锁1, B拿到锁2, A想继续拿到锁2后再继续执行，B想继续拿到锁1后再继续执行。导致A和B谁也无法继续执行。

2.4.1 使用便签

2.4.2 使用便签（二）- 将便签放在第一位 

 2.4.3 使用便签（三）- 区别不同的便签

 

2.4.4 更复杂的两种便签 

 

2.4.5 临界区

 

 

 

3. 临界区

3.1 临界区的属性 

• 互斥:同一时间临界区中最多存在-一个线程
• Progress:如果-个线程想要进入临界区，那么它最终会成功
• 有限等待:如果一个线程处于入口区，那么在i的请求被接受之前其他线程进入临界区的时间是有限制的
• 无忙等待(可选):如果一个进程在等待进入临界区,那么在它可以进入之前会被挂起

4. 对临界区代码保护的方法1： 禁用硬件中断

概述 

禁用中断，不允许它进行切换 

缺点

 

 

5. 方法2： 基于软件的解决方法

5.1 假设的模型 

5.2 使用turn来实现

5.3 改进，使用flag[]

5.4 调整顺序后的flag []

5.5 正确的解法

5.5.1 代码 

5.5.2 代码2(更为复杂，了解）

5.6 n个进程的算法

循环的等待、执行。 

5.6.1  Bakery算法 

银行排队，按 执行。

如果收到相同的 ，就按照进程 来执行。 

 

6. 方法3： 更高级的抽象

6.1 基于硬件的解决方法

•  硬件提供了一些原语
  • 像中断禁用，原子操作指令等
  • 大多数现代体系结构都这样
• 操作系统提供更高级的编程抽象来简化并行编程
  • 例如:锁，信 量
  • 从硬件原语中构建

6.2 假定是一个lock编程抽象

6.3 实现lock

•  大多数现代体系结构都提供特殊的原子操作指令
  • 通过特殊的内存访问电路
  • 针对单处理器和多处理器
• Test- and -Set测试和置位
  • 从内存中读取值
  • 测试该值是否为1 (然后返回真或假)
  • 内存值设置为1
• 交换.
  • 交换内存中的两个值

6.4 示例（看起来有很多行代码，但是硬件上实现了，在执行时是一个整体，不允许被打断）

6.5 代码设计，支持n个进程

存在忙等的情况。 

6.6 可以进一步改进，解决忙等

6.6.1 把等待的进程放在等待队列，进行睡眠

6.7 优点

•  优点
  • 适用于单处理器或者共享主存的多处理器中任意数量的进程
  • 简单并且容易证明
  • 可以用于支持多临界区

6.8 缺点 

•  缺点
  • 忙等待消耗处理器时间
  • 当进程离开临界区并且多个进程在等待的时候可能导致饥饿
  • 死锁
    • 如果一个低优先级的进程拥有临界区并且一个高优先级进程也需求，那么高优先级迸程会获得处理器并等待临界区

 

6.9 总结

•  锁是更高等级的编程抽象
  • 互斥可以使用锁来实现
  • 通常需要一定等级的硬件支持
• 常用的三种实现方法
  • 禁用中断(仅限于单处理器)
  • 软件方法(复杂)
  • 原子操作指令(单处理器或多处理器均可)
• 可选的实现内容:
  • 有忙等待
  • 无忙等待