第九章 同步

B站 陈渝老师 清华大学
https://www.bilibili.com/video/av6538245?from=search&seid=436175425155932048

9.1 背景

• 到目前为止
  多道程序设计(multi- programming) :现代操作系统的重要特性
  并行很有用(为什么? )提示:多个并发实体: CPU(s)，I/O， … 用户,…
  进程/线程:操作系统抽象出来用于支持多道程序设计
  CPU调度:实现多道程序设计的机制
  调度算法–不同的策略

(1)计算机内有多个线程，有独立的线程，互相不影响，也有可能相互之间需要合作的线程。

• 独立的线程:

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

• 合作线程:

-在多个线程*享状态
-不确定性
-不可重现
-不确定性和不可重现意味着bug可能是间歇性发生的

(2)为什么需要线程合作？

• 进程/线程， 计算机/设备需要合作
• 优点1:共享资源

-一台电脑，多个用户
-一个银行存款余额，多台ATM机
-嵌入式系统(机器人控制:手臂和手的协调)

• 优点2:加速

-1/0操作和计算可以重叠
-多处理器-将程序分成多个部分井行执行

• 优点3:模块化

-将大程序分解成小程序
以编译为例，gcc会调用cpp, cc1, cc2, as, ld
-使系统易于扩展

(3)线程并发引起的可能出现一个不确定性。举个例子

• 程序可以调用函数fork ()来创建一个新的进程

操作系统需要分配一个新的并且唯一的进程ID
因此在内核中，这个系统调用会运行

1. new_pid=next_pid++ ; //共享的全局变量 原子操作?

• 翻译成机器指令

1. LOAD next_pid Reg1
2. STORE Reg1 new_pid
3. INC Reg1
4. STORE Reg1 next_ pid

◆假设两个进程并发执行

如果next_pid等于100， 那么其中一个进程得到的ID应该是100,另一个进程 的ID应该是101，next_pid应该增加到102

9.2-9.4一些概念

(1)竞态条件 Race Condition
上述例子的现象称为竞态条件。
◆系统缺陷:结果依赖于并发执行或者事件的顺序/时间
➢不确定性
➢不可重现
◆怎样避免竞态?可以引入原子操作。
(2)原子操作 Atomic Operation

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

-该执行成功结束
-或者根本没有执行
-并且不应该发现任何部分执行的状态

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

-有些看上去是原子操作，实际上不是
-连x++这样的简单语句,实际上是由3条指令构成的
-有时候甚至连单条机器指令都不是原子的 Pipeline, super- scalar, out- of- order, page fault

第二个例子，假设内存读取和存储是原子的，但是加1和减1操作不是原子的。 因为线程共享数据段资源，可能会出现线程A：i++，接着调度B：i–，没有人赢。

(3)临界区、互斥、死锁、饥饿

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

(4)锁、解锁、死锁
例如，在冰箱上设置一个锁和钥匙( lock&key )
第三个例子，买太多面包问题：

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

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

9.5临界区(Critical section)

• 临界区的进去和退出必须满足下面：

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

• 使用下面的三种方法更好的实现对临界区代码的帮助：

1.禁止硬件中断
2.基于软件的解决方案
3.更高级的抽象，基于硬件的原子操作指令

9.6 方法1:禁用硬件中断

中断有使操作系统强制打断进程执行、完成进程切换的能力，可以在进入临界区前把中断屏蔽了，等线程出临界区再重新使能中断。

-没有中断，没有上下文切换，因此没有并发
-硬件将中断处理延迟到中断被启用之后
-大多数现代计算机体系结构都提供指令来完成

• 进入临界区

禁用中断

• 离开临界区

开启中断

缺点

1. 一旦中断被禁用，线程就无法被停止
   整个系统都会为你停下来，一些时钟信号、网络包、磁盘读写事件没法得到及时的响应。
   可能导致其他线程处于饥饿状态
2. 要是临界区可以任意长怎么办
   无法限制响应中断所需的时间(可能存在硬件影响)
   只有在临界区很小的时候才可以使用，要小心使用。
3. 因为中断屏蔽只在当前CPU而对其他的CPU并没有屏蔽。所以多cpu并行执行的情况下，不适用。

9.7 方法2:基于软件的解决方法

在分布式系统中

线程i线程j

缺点：只能交替进行，才能保证另一个进程进去临界区

改进->用flag[]数组来


正确的解法：Peterson算法


除此之外还有两种算法。Dekker、Bakery。
Dekker进出入临界区相比于Peterson算法更复杂。感兴趣的同学课后再去了解。

• 软件实现算法分析：
  ◆Dekker算法 (1965) :第-个针对双线程例子的正确解决方案
  ◆Bakery算法 ( Lamport 1979 ) :针对n线程的临界区问题解决方案
  ◆复杂
  –需要两个进程间的共享数据项
  –需要忙等待
  –浪费CPU时间
  ◆没有硬件保证的情况下无真正的软件解决方案
  –Peterson算法需要原子的L0AD和STORE指令

9.8 方法3:更高级的抽象

软件来做的不足：开销、时间复杂性比较大
改进：基于硬件原子操作的高级抽象实现

• 硬件提供了一些原语

-像中断禁用，原子操作指令等
-大多数现代体系结构都这样

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

-例如:锁，信号量
-从硬件原语中构建

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

-一个二进制状态(锁定/解锁)，两种方法
-Lock::Acquire() -锁被释放前一直等待，然后得到锁
-Lock::Release() -释放锁，唤醒任何等待的进程

• 锁抽象怎么来实现：
  -两个特殊的操作可以帮助互斥：Test-and-Set 或 交换。

• 大多数现代体系结构都提供特殊的原子操作指令
  -通过特殊的内存访问电路
  -针对单处理器和多处理器

• Test- and -Set测试和置位
  -从内存中读取值
  -测试该值是否为1 (然后返回真或假)
  -内存值设置为1

• 交换
  -交换内存中的两个值

用上述两个操作来实现锁：

• Test- and -Set测试和置位

缺点：使用忙等待的锁
->就像上面使用test-and-set实现的锁一样
->线程在等待的时候消耗cpu周期
改进：等待的时候加入等待序列，进入睡眠

• 基于交换来实现进入临界区

• 基于原子操作的优缺点：

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

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

总结

• 锁是更高等级的编程抽象

-互斥可以使用锁来实现
-通常需要一定等级的硬件支持

• 常用的三种实现方法

-禁用中断(仅限于单处理器)
-软件方法(复杂)
-原子操作指令(单处理器或多处理器均可)

• 可选的实现内容:

-有忙等待
-无忙等待

目前，原子操作指令来完成这个的比较多。

参考资料：操作系统_清华大学(向勇、陈渝)
https://www.bilibili.com/video/BV1js411b7vg?from=search&seid=15059545862768601253

本文地址：https://blog.csdn.net/qq_38229259/article/details/107446437