【操作系统】Operation System-第9章-同步 & 互斥

操作系统—同步 & 互斥

• 独立的线程

  ? 不和其他线程共享资源或状态

  ? 确定性 => 输入状态决定结果

  ? 可重现 => 能够重现起始条件，I/O

  ? 调度顺序不重要

• 合作线程

  ? 在多个线程中共享状态

  ? 不确定性

  ? 不可重现

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

进程 / 线程，计算机 / 设备需要合作。

合作优点

1. 共享资源

   ? 一台电脑，多个用户

   ? 一个银行存款余额，多台ATM机

   ? 嵌入式系统（机器人控制：手臂和手的协调）

2. 加速

   ? I/O操作和计算可以重叠

   ? 多处理器：将程序分成多个部分并行执行

3. 模块化

   ? 将大程序分解成小程序

   ? √ 以编译为例，gcc会调用cpp，cc1，cc2，as，ld

   ? 使系统易于扩展

最主要的问题在于：整个操作的四条机器指令执行过程中，产生了一次上下文切换，使得整个的结果和我们预期不一致了。

调度的时机点可以在四条语句的任何一个位置产生切换，会得到很多不一样的结果，这种交叉切换性会有很多种情况，也就意味着最终的结果具有不确定性 和 不可重复性。

• 无论多个线程的指令序列怎样交替执行，程序都必须正常工作

  ? 多线程程序具有不确定性和不可重现的特点

  ? 不经过专门设计，调试难度很高

• 不确定性要求并行程序的正确性

  ? 先思考清楚问题，把程序的行为设计清楚

  ? 切忌给予着手编写代码，碰到问题再调试

我们必须要有一些新的机制来保证能够达到最终确定的结果，后面会引入同步互斥机制 解决这种不确定性的问题。

一些概念

Race Condition（竞态条件）

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

  ? 不确定性

  ? 不可重现

• 怎么样避免竞态/p>

Atomic Operator（原子操作）

• 原子操作是指一次不存在任何终端或者失败的执行

  ? 该执行成功结束

  ? 或者根本没有执行

  ? 并且不应发生任何部分执行的状态

• 实际上操作往往不是原子的

  ? 有些看上去是原子操作，实际上不是

  ? 连这样的简单语句，实际上是由三条指令构成的

  ? 有时候甚至连单条假期指令都不是原子的

  ? √ Pipeline，super-scalar，out-of-order，pape fault

• 临界区（critical section）

  ? 进程中访问临界资源的一段需要互斥执行的代码

• 进入区（entry setcion）

  ? 检查是否进入临界区的一段代码

  ? 如可进入，设置相应 “正在访问临界区” 标志

• 退出区（exit section）

  ? 清除 “正在访问临界区” 标志

• 剩余区（remainder section）

  ? 代码中的其余部分

临界区的访问规则

• 空闲则入（Progess）

  ? 没有进程在临界区时，任何进程可以进入

• 忙则等待（互斥）

  ? 有进程在临界区时，其他进程均不能进入临界区

• 有限等待

  ? 等待进入临界区的进程不能无限期的等待

• 让权等待（可选）

  ? 不能进入临界区的进程，应释放CPU（如转换到阻塞状态）

方法1：禁用硬件中断

• 没有中断，没有上下文切换，因此没有并发

  ? 硬件将中断处理延迟到中断被启用之后

  ? 大多数现代计算机体系结构都提供指令来完成

• 进入临界区

  ? 禁用中断

• 离开临界区

  ? 开启中断

用这种方法确实可以解决这个问题，但它还有一些缺点：

• 一旦中断被禁用，线程就无法被停止

  ? 整个系统都会为你停下来

  ? 可能导致其他线程处于饥饿状态

• 要是临界区可以任意长怎么办/p>

  ? 无法限制响应中断所需的时间（可能存在硬件影响）

• 要小心使用

  ? 适用于临界区很小的情况

在多CPU的情况下存在一定局限性，无法解决互斥问题。

方法2：基于软件的解决方案

• 满足 “忙则等待”，但有时不满足 “空闲则入”
  • $T_i$ 不在临界区，$T_j$ 想要继续运行，但是必须等待 $T_i$ 进入过临界区后

第二次尝试

• 满足 “忙则等待”，但是不满足 “空闲则入”。

Peterson算法

• 满足进程 $T_i$ 和 $T_j$ 之间互斥的经典的基于软件的解决方法（1981年）

• Use two shared data items（使用两个共享数据项）

  ? // 指示该谁进入临界区

  ? // 指示进程是否准备好进入临界区

• Code for ENTER_CRITICAL_SECTION（进入临界区）

• Code for EXIT_CRITICAL_SECTION（退出临界区）

• 进程 $P_i$ 的算法

上述算法能够满足互斥、前进、有限等待三种特性；可用反证法来证明。

Dekker算法

进程 $P_i$ 的算法

Eisenberg and McGuire算法

N个线程的软件方法

Bakery算法

N个进程的临界区

• 进入临界区之前，进程接收一个数字
• 得到的数字最小的进入临界区
• 如果进程 $P_i$ 和 $P_j$ 收到相同的数字，那么如果 $ij$
• 编 方案总是按照枚举的增加顺序生成数字

总结

• Dekker算法（1965）：第一个针对双线程例子的正确解决方案

• Bakery算法（Lamport 1979）：针对n线程的临界区问题解决方案

• 复杂

  ? 需要两个进程的共享数据项

• 需要忙等待

  ? 浪费CPU时间

• 没有硬件保证的情况下无真正的软件解决方案

  ? Peterson算法需要原子的LOAD和STORE指令

方法3：更高级的抽象

• 硬件提供了一些原语

  ? 像中断禁用，原子操作指令等

  ? 大多数现代体系结构都这样

• 操作系统提供更高级的编程抽象来简化并行编程

  ? 例如：锁，信 量

  ? 从硬件原语中构建

• 锁（lock） 是一个抽象的数据结构

  ? 一个二进制状态（锁定，解锁），两种方法

  ? ：锁被释放前一直等待，然后得到锁

  ? ：锁释放，唤醒任何等待的进程

• 使用锁来编写临界区

  ? 前面的例子变得简单起来：

• 大多数现代体系结构都提供特殊的原子操作指令

  ? 通过特殊的内存访问电路

  ? 针对单处理器和多处理器

• Test-and-Set测试和置位指令

  ? 从内存中读取值

  ? 测试该值是否为1（然后返回真或假）

  ? 内存值设置为1

• 交换指令（exchange）

  ? 交换内存中的两个值

  声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！