07 同步 | 《操作系统》笔记

这一系列是操作系统 (清华大学向勇、陈渝)视频课的课堂笔记，主要是课堂 PPT 和部分讲授内容的文字版，仅供参考。

一些概念

• Race Condition(竞态条件)
  • 系统缺陷：结果依赖于并发执行或者事件的顺序/时间
    • 不确定性
    • 不可重现
  • 如何避免竞态
    • 让指令不被打断
• Atomic Operation(原子操作)
  • 原子操作是指一次不存在任何中断或者失败的执行
    • 该执行成功结束
    • 或者根本没有执行
    • 并且不应该发现任何部分执行的状态
  • 实际上操作往往不是原子的
    • 有些看上去是原子操作，实际上不是
    • 连 x++ 这样的简单语句，实际上是由 3 条指令构成的
    • 有时候甚至连单条机器指令都不是原子的
      • pipeline, super-scalar, out-of-order, page fault
• Critical section(临界区)
  • 临界区是指进程中的一段需要访问共享资源井且当另一个进程处于相应代码区域时便不会被执行的代码区域
• Mutual exclusion(互斥)
  • 当一个进程处于临界区并访问共享资源时，没有其他进程会处于临界区并且访问任何相同的共享资源
• Mutex(互斥量)
  • 互斥量的使用流程：线程占用互斥量，然后访问共享资源，最后释放互斥量
  • 标准库互斥量 std::mutex 的几个成员函数
    • lock()：调用线程将锁住该互斥量。线程调用该函数会发生下面 3 种情况：
      • 如果该互斥量当前没有被锁住，则调用线程将该互斥量锁住，直到调用 unlock之前，该线程一直拥有该锁
      • 如果当前互斥量被其他线程锁住，则当前的调用线程被阻塞住
      • 如果当前互斥量被当前调用线程锁住，则会产生死锁
    • unlock()：解锁，释放对互斥量的所有权
    • try_lock()：尝试锁住互斥量，如果互斥量被其他线程占有，则当前线程也不会被阻塞。线程调用该函数也会出现下面 3 种情况：
      • 如果当前互斥量没有被其他线程占有，则该线程锁住互斥量，直到该线程调用 unlock 释放互斥量
      • 如果当前互斥量被其他线程锁住，则当前调用线程返回 false，而并不会被阻塞掉
      • 如果当前互斥量被当前调用线程锁住，则会产生死锁
• Dead lock(死锁)
  • 两个或以上的进程，在相互等待完成特定任务，而最终没法将自身任务进行下去
• Starvation(饥饿)
  • 一个可执行的进程，被调度器持续忽略，以至于虽然处于可执行状态却不被执行
• 关于锁的概念
  • lock(锁)
    • 在门、抽屉等物体上加上保护性装置，使得外人无法访问物体內的东西，只能等待解锁后才能访问
  • unlock(解锁)
    • 打开保护性装置，使得可以访问之前被锁保护的物体类的东西
  • deadlock(死锁)
    • A拿到锁1，B拿到锁2，A想继续拿到锁2后再继续执行，B想继续拿到锁1后再继续执行，导致A和B谁也无法继续执行

      临界区

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

方法一：禁用硬件中断

• 使用方法
  • 进入临界区
    • 禁用中断
  • 离开临界区
    • 开启中断
• 方法的局限性
  • 一旦中断被禁用，线程就无法被停止，无法限制响应系统中断，影响系统效率
    • 整个系统都会为你停下来
    • 可能导致其他线程处于饥饿状态
  • 仅适用于临界区较短的情况
    • ？
  • 不适用于多 CPU
    • 只能限制本 CPU 其他进程访问临界区，无法限制其他 CPU

方法二：基于软件的解决方法

• 尝试一（两个线程）
  • 
  • turn = i 表示轮到进程 i 进入临界区，所以不是 i 的进程就要在 while 循环中等待；进程 i 退出临界区并将 turn 设置为 j，这时候进程 j 才可以进入临界区
• 尝试二（两个线程）
  • 
  • 如果进程 flag[j] == 1，表示进程 j 在临界区中，所有其他进程就要在 while 循环中等待；进程 j 退出临界区时会将 flag[j] 设为 0，表示其退出临界区，其他进程可以进来了
• 尝试三（两个线程）
  • 
• Peterson 算法（两个线程）
  • 
  • 
• Dekker 算法（两个线程）
  • 
• Eisenberg and mcGuire’s 算法（n 个线程）
  • 
• Bakery 算法（n 个线程）
  • 

方法三：更高级的抽象

• 硬件提供了一些原语
  • 像中断禁用，原子操作指令等
  • 大多数现代体系结构都这样
• 操作系统提供更高级的编程抽象来简化并行编程
  • 例如：锁、信号量
  • 从硬件原语中构建
• 大多数现代体系结构都提供特殊的原子操作指令
  • 通过特殊的内存访问电路
  • 针对单处理器和多处理器
  • 测试和置位 (Test-and-Set)
    • 从内存中读取值
    • 测试该值是否为 1（然后返回真或假）
    • 内存值设置为 1
  • 交换 (Exchange)
    • 交换内存中的两个值
• 
• 优点
  • 适用于单处理器或者共享主存的多处理器中任意数量的进程
  • 简单并且容易证明
  • 可以用于支持多临界区
• 缺点
  • 忙等待消耗处理器时间
  • 当进程离开临界区并且多个进程在等待的时候可能导致饥饿
  • 死锁
    • 令如果一个低优先级的进程拥有临界区并且一个高优先级进程也需求，那么高优先级进程会获得处理器并等待临界区
• 总结
  • 锁是更高等级的编程抽象
    • 互斥可以使用锁来实现
    • 通常需要一定等级的硬件支持
  • 常用的三种实现方法
    • 禁用中断（仅限于单处理器）
    • 软件方法（复杂）
    • 原子操作指令（单处理器或多处理器均可）
  • 可选的实现内容
    • 有忙等待
    • 无忙等待