并发性 – 互斥和同步

并发的原理

竞争

• 通过信号量等方式解决
• 多个进程的指令执行顺序的“竞争”

操作系统的资源

• 处理器时间
• 存储器
• 文件
• I/O

进程的交互

• 交互方式分类
  • 进程之间相互不知道对方的存在
  • 进程间接知道对方的存在
  • 进程直接知道对方的存在
• 进程间竞争
  • 互斥
  • 死锁
  • 饥饿
• 共享 ⇒ 需要保证数据一致性

互斥的要求

• 空闲让进 – 临界区没有进程时 任何需要进入的进程一定立刻能够进入
• 忙则等待 – 强制互斥 一次只允许一个进程进入临界区
• 有限等待 – 对要求访问临界资源的进程 应保证有限时间内能进入自己的临界区
• 让权等待 – 当进程不能进入自己的临界区时 应立即释放处理避免无限延迟

3种解决方法

软件实现

Mutual Exclusion: Software Approaches

Dekker’s Algorithm

• 原始算法：程序异常终止会导致另外一个进程被永久阻塞
• 双标志先检测法：使用数组来标记多个进程 但不能有效实现互斥
• 双标志后检测法：访问资源之前改变对应的状态 发表请求使用资源的声明 但存在死锁 无法处理同时发起的访问请求
• 引入随机等待时间后存在活锁
• Final Version：
  • 两个全局共享的状态变量flag[0]和flag[1] 表示临界区状态及哪个进程想要占用临界区 初始为0
  • 全局共享变量turn 代表能进入临界区的进程序号
  • 规定了进程执行的顺序 不够灵活
  

Peterson Algorithm

• 使用两个控制变量flag与turn
• flag[n]的值为真时表示ID号为n的进程希望进入该临界区
• 变量turn保存有权访问共享资源的进程的ID号
• 满足了互斥、空闲让进、有限等待三个标准

硬件实现

两类方法

中断禁用

• 在单处理机器中，只要保证一个进程不被中断就可以保证互斥
• 这可以通过系统内核启用和禁用中断定义的原语实现
• 只适用单处理器

专用机器指令

• 通过机器指令保证两个动作之间的原子性 不接受中断
• 比较和交换指令：比较内存单元值和测试值相同时产生交换 比较和交换功能按原子操作执行 不接受中断
• exchange指令
• 优点：
  1. 适用于单处理器或共享内存的多处理器的任意数量的进程
  2. 简单且易于证明
  3. 可以支持多个临界区
• 缺点：
  1. 使用忙等待 ->消耗处理器时间
  2. 选择等待进程->饥饿
  3. p1占用临界资源被p2中断而p2试图使用临界资源->死锁

信号量

| 信号量 | 用于在进程间传递信号的整数值 | | 二元信号量 | 只能取0和1的信号量 | | 互斥量 | 为其加锁和解锁的进程为同一个的二元信号量 | | 条件变量 | 一种数据类型，用于阻塞进程或线程 | | 管程 | 一种编程语言结构，在一个抽象数据类型中封装了变量、访问过程和初始化代码 | | 事件标志 | 用作同步机制的一个内存字 | | 信箱/消息 | 两个进程交换信息的一种方法 | | 自旋锁 | 一种互斥机制，进程在一个无条件循环中执行，等待变量的值可用 |

本质：信号量是用于进程间传递信号的一个整数值

信号量操作

• 一个信号量可以初始化成非负数
• semWait操作使信号量减1。若值变成负数，则阻塞执行semWait的进程，否则进程继续执行
• semSignal操作使信号量加1。若值小于等于0，则被semWait操作阻塞的进程借出阻塞

一些结论

• 在进程对信号量减1之前，无法提前知道这个信号量是否会被阻塞
• 当进程对一个信号量加1后，会唤醒另一个进程，两个进程继续并发运行。在一个单处理器系统中，同样无法知道哪个进程会立即运行
• 向信号量发出幸好后，不需要知道是否有另一个进程正在等待，被解除阻塞的进程数要么没有，要么为1
• 二元信号量就是 0或1 不会累加

生产者消费者

有一个或多个生产者生产某种类型的数据（记录，字符），并放置在缓冲区中；有一个消费者从缓冲区中读数据，每次读取一项；系统保证避免对缓冲区的重复操作，即在任何时候只有一个主体（生产者或消费者）可以访问缓冲区。要确保：当缓存已满时，生产者不会继续向其中添加数据；当缓存为空时，消费者不会从中移走数据

管程

使用信号的管程（Hoare管程）

• 主要特点
  • 局部变量只能被管程的过程访问
  • 通过调用管程的一个过程进入进程
  • 一个进程执行 其余阻塞
• 使用条件变量(condition variable)来支持同步
  • cwait(c)
  • csignal(c)
  • 和信号量的区别：若无c条件等待的任务则丢弃 而不是对一个值固定产生影响
• 管程结构
• 优点：所有同步机制限制在管程内部
  • 易于验证同步正确性
  • 易于检测出错误
  • 管程正确：所有进程访问正确

使用通知和广播的管程（Lampson/Redell管程）

• 当前管程定义缺陷
  • 两次额外进程切换：产生csignal进程在管程中未结束
    • 阻塞
    • 恢复
  • 与信号相关进程调度必须非常可靠
• 解决措施：使用cnotify替换csignal
  • 等待进程必须重新检查条件
  • 使x得到通知 但发信号进程继续执行
• 优点
  • 错误少
  • 有助于程序结构模块化方法

消息传递

• 进程交互时必须满足两个基本要求：
  • 同步：为实施互斥，进程间需要同步
  • 通信：为实现合作，进程间需要交换信息
• 消息传递
  • 定义：提供同步和通信功能的一种方法
  • 优点：消息传递可以在分布式系统、多处理器系统和单处理器系统中实现
  • 功能：消息传递以一对原语提供同步和通信功能
    • send(destination, message) 【向目的进程发送消息】
    • receive(source, message) 【接收源进程发送的消息】

同步

• 原语组合类型
  • 阻塞send，阻塞receive：发送者和接收者都被堵塞，直到消息投递完成
  • 无阻塞send，阻塞receive：发送者可以继续，但接收者被阻塞直到消息到达
  • 无阻塞send，无阻塞receive：不要求任何一方等待
• 无阻塞send常用于请求输出操作，但需注意重复消息和资源消耗
• 阻塞receive常用于等待消息继续执行，但需注意消息丢失和无限期阻塞的问题

寻址

直接寻址 间接寻址

• 直接寻址：send原语中包含目标进程的标识号
• 间接寻址：消息不直接从发送者发送到接收者，而是发送到一个共享数据结构
• 间接寻址支持一对一、多对一、一对多和多对多
• 间接寻址通过解除发送者和接收者之间的耦合关系，可更灵活地使用消息

消息格式

稍微有个印象就行

排队原则

FIFO 优先级 接受者检查

消息传递实现

读者写者

• 允许多个读者可以同时对文件执行读操作
• 只允许一个写者往文件写信息
• 任一写者在完成写操作之前不允许其他读者后写者工作
• 写者执行写操作前，应该让已经有的读者或者写者全部退出
• 读者优先 vs. 写者优先