[第四章]进程同步

基本概念

• 主要任务：使并发的各进程之间能有效地共享资源和相互合作，从而使程序的执行有可再现性

• 进程间制约关系
• 间接相互制约关系（互斥关系），对共享资源进行互斥访问
• 直接相互制约关系（同步关系），保证进程之间操作的先后次序

• 临界资源
• 只允许一个进程使用
• 可以是硬件资源也可以是软件资源

• 生产者-消费者问题
• 共享一个缓冲池
• 异步运行，二者保持同步
• 消费者不能从空取，生产者也不能从满放
• 数据结构：缓冲池buffer 输入指针in 输出指针out 整型变量 cout
• 临界资源必须一个进程全访问部完成再其他访问，否则可能出错

• 临界区问题
• 临界区：涉及临界资源的代码
• 进入区：是否可以进入临界区的代码
• 退出区：修改标志位，表示访问完成
• 剩余区：其他代码

• 进程同步机制的原则
• 空闲让进
• 忙则等待
• 有限等待
• 让权等待：不能进入临界区的进程应释放CPU

• 进程同步机制
• 软件同步机制
• 硬件同步机制
• 信号量机制
• 管程机制

软件同步机制

Peterson解决方案

• 没有实现让权等待

硬件同步机制

• 关中断

• Test-and-Set

• Swap

信号量机制

整型信号量

• 忙等，没有遵循让权等待

记录型信号量

• 数据结构
• 增加一个队列，当要等待时，用队列记录当前的值

• S→是指针

• 实现了让权等待

• 主动阻塞，被动唤醒

• 先加减再挂起或唤醒

AND型信号量

• 适用于同时需要多种资源，每种占一个

• 要么临界资源全分配，要么不分配

• 操作
• P原语：Swait
• V原语：Ssignal

信号量集

• 下限值ti（信号量的判断条件，当资源数量低于ti时，不予分配）

• 需求量di（对资源i的申请量）

• Swait(S1, t1, d1; ...; Sn, tn, dn);

• Ssignal(S1, d1; ...; Sn, dn);

信号量应用

• 实现互斥
• P→临界区→V

• 实现前趋关系
• 先执行A再执行BC



• 定义初值为0的信号量，如下所示：a=b=c=d=e=f=g=0
• 只能置一次非负初值

• 物理意义
• S>0表示资源可用
• S=0表示无资源可用
• S<0表示挂起的进程个数
• P（S）表示申请一个资源
• V（S）表示释放一个资源
• S=n说明允许n个进程运行，进程数为m说明最小为S最小为n-m，

结论

• PV成对出现

• 互斥在同一进程中（自己锁自己）

• 同步在互相协作的两个进程（两个分先后运行）

• 如果同步和互斥在进程中，先同步后互斥
• 一旦互斥被阻塞，可能永远不被唤醒，死锁

• 单缓冲区不用互斥操作

经典进程同步问题

生产者-消费者

单缓冲问题

• 两个信号同步

• empty空缓冲区数目=1

• full已有产品数目=0

多缓冲区问题

• 数组buffer[]：有n个(0，1，…，n-1)缓冲区的缓冲池
• 每一个生产或消费放到一个地址

• 互斥信号量mutex=1
• 多个生产者之间互斥，不能存到同一个地址
• 多个消费者之间互斥，不能存到同一个地址

• empty初值为n

• full初值为0

• 生产消费判断标准
• 根据资源而定Buffer(in)/Buffer(out)

记录型信号量解决生产者消费者问题

• 信号empty或full与mutex交换情况
• 生产者或消费者先执行后如果在同步进程上阻塞，另一方因为mutex=0故也阻塞，造成死锁
• 互斥条件放在最内层

• 缺少signal(empty)或singnal(full)
• 造成另一方的阻塞无法被唤醒

AND型信号量解决生产者消费者问题

• AND信号量互斥信号不必在内层

哲学家进餐

• 问题描述：哲学家围坐，两两间有一根筷子

问题分析

• AND型信号量解决
• 其他信号量可能导致同时取左，取右时右在别人手里，死锁
• AND解决：同时有左和右时才可以取

读者-写者

• 问题描述：读时可读不可写，写时不可读不可写

• 读进程共享同一对象，写进程不共享同一对象

读优先

• 当读者正在读，有写着等，新读者也可以读

• readcount为临界资源，记录读者数目，多个读者互斥访问
• 信号量rmutex=1

• 信号量wmutex=1用于读写、写写互斥访问

写优先

• 当读者正在读，新读者等写者写完再读

• 增加一个信号量，使读者在读的时候若有写着不可读
• 进程同步，S=1

信号量集

• 最多只允许RN个读者读

• L控制读者数量

解决问题

• 分析类型

• 分析缓冲区

• 设置信号源

• 设置信号量初值

• 给出初步解

• PV配对

管程机制

• 类似封装，不透明

• 定义一个数据结构并提供调用的接口

课后题

• 先做后V，后做先P

• 信号量控制两个事件的关系

课后题