主要内容

• 背景
• 信号量
• 信号量使用
• 信号量实现
• 管程
• 经典同步问题

内容回顾

1. 并发问题:竞争条件(竞态条件)

• 多程序并发存在大的问题

2. 同步

• 多线程共享公共数据的协调执行
• 包括互斥与条件同步
• 互斥:在同一时间只有一个线程可以执行临界区

3. 确保同步正确很难?

• 需要高层次的编程抽象（如:锁)
• 从底层硬件支持编译

4. 解决方案

 

信号量

抽象数据类型

• 一个整型(sem)，两个原子操作
• P(): sem减1，如果sem<0，等待，否则继续>
• V(): sem加1，如果sem<=0,唤醒一个等待的P

 

信号量类似铁路

 

信号量是整数
信号量是被保护的变量

• 初始化完成后，唯一改变一个信号量的值的办法是通过PO和VO
• 操作必须是原子

P()能够阻塞，V()不会阻塞

我们假定信号量是“公平的”

• 没有线程被阻塞在PO仍然堵塞如果VО被无限频繁调用(在同一个信号量)
• 在实践中，FIFO经常被使用

两种类型信号量

• 二进制信号量:可以是0或1
• 一般/计数信号量:可取任何非负值〉
• 两者相互表现(给定一个可以实现另一个)

信号量可以用在2个方面

• 互斥
• 条件同步(调度约束———个线程等待另一个线程的事情发生)

 

生产者消费者问题

• 一个或多个生产者产生数据将数据放在一个缓冲区里
• 单个消费者每次从缓冲区取出数据
• 在任何一个时间只有一个生产者或消费者可以访问该缓冲区

正确性要求

• 在任何一个时间只能有一个线程操作缓冲区(互斥)
• 当缓冲区为空，消费者必须等待生产者（调度/同步约束)
• 当缓存区满，生产者必须等待消费者（调度/同步约束)

每个约束用一个单独的信号量

• 二进制信号量互斥
• 一般信号量fullBuffers
• 一般信号量emptyBuffers

P,V操作的顺序会对结果产生影响。

 

信号量的实现

使用硬件原语

• 禁用中断
• 原子指令(test-and-set)

类似锁

例如:使用‘禁用中断’

 

信号量的数据结构

信号量总结

信号量的双用途

• 互斥和条件同步
• 但等待条件是独立的互斥

读/开发代码比较困难

• 程序员必须非常精通信号量

容易出错

• 使用的信号量已经被另一个线程占用
• 忘记释放信号量

不能够处理死锁问题

 

管程

目的:分离互斥和条件同步的关注

什么是管程

• 一个锁:指定临界区
• 0或者多个条件变量:等待/通知信号量用于管理并发访问共享数据

一般方法

• 收集在对象/模块中的相关共享数据
• 定义方法来访问共享数据

管程示意图

 

Lock

• Lock: : Acquire( -等待直到锁可用，然后抢占锁
• Lock:: Release()-释放锁，唤醒等待者如果有

Condition Variable

• 允许等待状态进入临界区
  • 允许处于等待（睡眠）的线程进入临界区
  • 某个时刻原子释放锁进入睡眠
• Wait ( operation)
  • 释放锁，睡眠，重新获得锁返回后
• Signal () operation (or broadcast () operation)
  • 唤醒等待者（或者所有等待者)，如果有

条件变量的实现方式

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

 

Hansen-style 和 Hoare-style

 

总结

开发/调试并行程序很难

• 非确定性的交叉指令

同步结构

• 锁:互斥
• 条件变量:有条件的同步
• 其他原语:信号量

怎样有效的使用这些结构?

• 制定并遵循严格的程序设计风格/策略