【操作系统学习】（二）同步互斥

临界区

描述

• 临界区
  
  • 指进程中访问临界资源的一段需要互斥访问的代码
• 进入区
  
  • 检查可否进入临界区的一段代码
  • 如可进入，设置相应“正在访问临界区”的标志
• 退出区
  
  • 清除“正在访问临界区”的标志
• 剩余区
  
  • 代码中的剩余代码

访问规则

• 空闲则入
  
  • 没有进程在临界区时，任何进程可进入
• 忙则等待
  
  • 如果有进程在临界区时，任何进程都不可进入临界区
• 有限等待
  
  • 等待进入临界区的进程不能无限的被动等待
• 让权等待（可选）
  
  • 不能进入临界区的进程，应该放弃CPU的使用

同步实现方法

1、禁用硬件中断

• 没有中断，也没有上下文的切换，没有并发执行
  
  • 硬件将中断处理延迟到中断被启用之后
  • 使用计算机体系结构的指令集提供的方法实现

缺点

• 禁用中断之后，进程无法被停止
  
  • 可能导致饥饿
  • 整个系统都会为此停下来
• 临界区可能很长
  
  • 无法确定响应中断所需的时间

2、软件方法

共享变量

• 线程之间可以通过一些共有的变量去同步它们的行为

PS:以下为代码描述

//第一种做法

缺点

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

//第二种做法

缺点

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

//第三种做法

缺点

• 满足“忙则等待”,但不满足“空闲可入”

//Peterson算法

//Dekkers算法

3、基于软件的解决方法的分析

• 复杂
  
  • 需要两个进程间的共享数据项
  • 需要程序编写者极高的素养
• 需要忙等待
  
  • 浪费CPU时间

更高级的抽象方法

描述

• 硬件提供了一些同步原语
  
  • 中断禁用，原子操作指令等
• 操作系统提供了更高级的编程抽象来简化进程同步
  
  • 例如：锁、信 量
  • 用硬件原语来构建

锁（lock）

• 锁是一种抽象的数据结构
  
  • 一个二进制变量（锁定/解锁）
  • Lock::Acquire
    
    • 锁被释放前一直等待，然后得到锁
  • Lock::Release
    
    • 释放锁，唤醒任何等待的线程
• 在进入区得到锁，在退出区释放锁

原子操作指令

• 现代CPU体系都提供一些特殊的原子操作指令，保证在原子操作时不会被中断
• 测试和置位操作TS（Test-and-Set）（三个操作为一整个不会被中断的原子操作）
  
  • 从内存中读取值
  • 测试该值是否为1
  • 内存单元值设置为1
• 交换指令
  
  • 交换内存中的两个值

使用TS指令实现自旋锁（spinlock）

• 缺点： 线程在等待的时候也会消耗CPU资源

无忙等待锁(基于上面的自旋锁的忙等待进行优化)

• 在无法进入临界区的时候，将自己的CPU使用权交出

• 优点
  
  • 适用于单处理器或者共享主存的多处理器中任意数量的进程同步
  • 简单且容易证明
  • 支持多临界区
• 缺点
  
  • 忙等待锁会占用CPU时间
  • 可能导致饥饿
    
    • 进程离开临界区的时候有多个进程等待的情况
  • 可能会出现死锁
    
    • 如下为一种情况：
      
      • 拥有临界区的低优先级进程没有获得CPU资源（没法执行完自己的工作）
      • 请求访问临界区的高优先级进程获得处理器资源并等待临界区（如果是执行忙等待）
      • 导致两者都没法执行自己的任务，造成死锁

同步方法总结

• 锁是一种高级的同步抽象方法

  • 互斥可以使用锁来支持
  • 需要硬件的支持才能使用

• 常用的三种同步实现方法

  • 禁用中断（仅限于单处理器）
  • 软件方法（复杂）
  • 原子指令操作（单处理器、多处理器均可实现）

信 量

简介

• 信 量是操作系统提供的一种协调
  
  • 软件同步是平等线程中的一种同步协商机制
  • OS是管理者，地位高于进程
  • 由操作系统来规定谁使用临界区资源
  • 用信 量表示资源的数量
• 有Dijkstra在60年代提出
• 早期操作系统的主要同步机制

描述

• 信 量是一种抽象的数据类型
  
  • 由一个整型变量（sem）和两个原子操作组成
  • P（Prolaag（荷兰语：尝试减少））
    
    • sem减一
    • 如果sem
  • V（Verhoog（荷兰语：增加））
    
    • sem加一
    • 如果sem
• 信 量是被保护的整型变量
  
  • 初始化完成后，只能通过P()和V()操作修改
  • 由操作系统保证，PV操作是原子操作
• P()可能被阻塞，V()不会被阻塞
• 通常假定信 量是“公平的”
  
  • 线程不会无限期的被阻塞在P（）操作
  • 假定信 量等待是按照先进先出排队（自旋锁无法实现先进先出）

信 量的实现

信 量的分类

• 可分为两种信 量
  
  • 二进制信 量：资源数量为0或1
  • 资源信 量：资源可为任何非负数
  • 两者等价
    
    • 基于一个可以实现另一个
• 信 量的使用
  
  • 互斥访问
    
    • 临界区的互斥访问控制
  • 条件同步
    
    • 线程间的事件等待

用信 量实现临界区的互斥访问

• 必须成对使用P()和V()
  
  • P()保证互斥访问临界资源
  • V()保证在使用后释放临界资源

PV 解决生产者消费者问题

生产者 –> 缓冲区 –> 消费者

• 问题分析
  
  • 任何时刻只能有一个线程操作缓冲区(互斥访问)
  • 缓存区空时，消费者必须等待生产者（条件同步）
  • 缓冲区满时，生产者必须等待消费者（条件同步）
• 用信 量描述每个约束
  
  • 二进制信 量 mutex
  • 资源信 量 fullBuffers
  • 资源信 量 emptyBuffers

缺点和困难

• 读写代码很难
  
  • 程序员需要能运用信 量机制
• 容易出错
  
  • 使用的信 量已经被另一个线程占用
  • 忘记释放信 量
• 不能处理死锁问题

管程

描述

• 管程是一种用于多线程互斥访问共享资源的程序结构
  
  • 采用面向对象方法，简化了线程间的同步控制
  • 任一时刻最多只有一个线程执行管程代码
  • 正在管程中的线程可临时放弃管程的互斥访问，并等待时间出现时回复
• 管程的使用
  
  • 在对象/模块中，收集相关共享数据
  • 定义访问共享数据的方法

组成

• 一个锁
  
  • 控制管程代码的互斥访问
• 0或者多个条件变量
  
  • 管理共享数据的并发访问

条件变量

• 条件变量是管程内的等待机制
  
  • 进入管程的线程因为资源被占用而进入等待状态
  • 每个条件变量表示一种等待原因，对应一个等待队列
• wait()操作
  
  • 将自己阻塞在等待队列中
  • 唤醒一个等待着管程释放的互斥访问
• signal()操作
  
  • 将等待队列中的一个线程唤醒
  • 如果等待队列为空，则等同空操作

条件变量实现

用管程解决生产者- 消费者问题

代码实现：

管程条件变量的释放处理方式

根据方式不同可分为：

• Hansen管程
• Hoare管程