信号量和管程

信号量

抽象数据类型：

• 一个整形(sem)，两个原子操作

P:sem减一，如果sem<0则等待，否则继续

V:sem加一，如果sem<=0唤醒一个等待的P

• 信号量是证书

• 信号量是被保护的变量

初始化完成之后，唯一改变一个信号量的值的办法是通过P()和V()

操作必须是原子的

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

信号量的使用

• 两种类型信号量

二进制信号量：可以是0或者1

一般/计数信号量：可以取任何非负值

两者互相表现（给定一个可以实现另外一个）

• 信号量可以在2个方面使用

互斥

条件同步

例子：

• 一个线程等待另外一个线程处理事情

比如生产东西和消费东西

互斥是不够的

使用约束

• 正确性要求

在任何一个时间只能由一个线程操作缓冲区

当缓冲区为空，消费者必须等待生产者

当缓冲区满时，生产者必须等待消费者

• 上面对应的每个约束用一个单独的信号量

二进制信号量，互斥

一般信号量

一般信号量

信号量的实现

使用操作系统的等待队列，使得不满足信号量的情况下，睡眠

• 信号量的双用途

互斥和条件同步

等待条件是独立的互斥

• 读、开发代码比较困难

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

• 容易出错

使用信号量已经被另一个线程占用

忘记释放信号量

• 不能够处理死锁问题

管程

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

• 什么是管程：

一个锁：指定临界区

0或者多个条件变量：等待/通知信号量用于管理并发访问共享数据

• 一般方法

手机在对象/模块中的相关共享数据

定义方法来访问共享数据

经典同步问题

读者-写者问题

• 动机

共享数据访问

• 两种类型使用者

读者：不需要修改数据

写者：读取和修改数据

• 问题约束

允许同一时间有多个读者，但在任何时候只有一个写者

当没有写者时，读者才能访问

当没有读者和写者时，写者才能访问数据

在任何时候只有一个线程可以操作共享变量

• 多个并发线程的数据集共享

读者：只读数据集，他们不执行任何更新

写者：可以读取和写入

• 共享数据

数据集

信号量countmutex初始化为1

信号量writemutex初始化为1

整数rcount初始化为0

基于读者有限策略的方法，只要有一个读者处于活动状态，后来的读者都会被接纳。如果读者源源不断的出现的话，那么写者就会始终处于阻塞状态。

基于写者优先的策略的方法：一旦写者就绪，那么写者会尽可能快的执行写操作，如果写者源源不断的出现的话，那么读者就始终处于阻塞状态。

哲学家就餐问题

5个哲学家围绕一张圆桌而坐，桌子上放着5个叉子，每两个哲学家之间放一个；哲学家的动作包括思考和进餐，进餐时需要同时拿起左边和右边的两个叉子，思考时候需要把叉子放回原处。如何保证哲学家们动作有序进行？

• 必须有一个数据结构描述每个哲学家的状态
• 该状态是一个临界资源，对它的访问应该互斥的进行
• 一个哲学家吃饱之后，可能要唤醒邻居，存在着同步关系