第三章 进程的同步与通信第二篇 操作系统进程的同步关系进程的同步原则信号量与 P,V操作进程的通信进程的同步
进程同步问题的提出
进程异步推进可能造成混乱
混乱可能导致不可再现
进程同步目标维持进程并发性以提高系统效率进程执行异步（断续）
资源的非封闭（共享）
结果不可再现进程同步 进程间相互合作资源有效共享 结果可再现进程的同步关系
3.1进程同步的基本概念
3.1.1进程间的两种主要关系
进程间的关系与进程间的独立性
进程间的关系是在进程间相对独立的前提下发展的
独立获得资源
独立调度进程间的同步关系（一）
正常行车到站停车开车售票开车门关车门司机 售票员合作合作检查车况 维持秩序获得打印数据进程间的同步关系（二）
打印进程 1 打印进程 2
打印 打印互斥获得打印数据进程间的同步关系（三）
计算进程打印进程计算结果送到 Buffer
从 Buffer中取数
Buffer
互斥完成数据计算打印通知打印进程打印通知计算进程送下一个数合作进程间的同步关系司机与售票员多个打印者计算者与打印者正常行车到站停车开车售票开车门关车门司机 售票员同步同步到站停车 否是检查车况维持秩序否关车门是同步实现初探（二）
打印进程 1 打印进程 2
打印 打印互斥获得打印数据 获得打印数据打印机可用？
设置打印机为不可用是否打印机可用？
设置打印机为不可用是否同步实现初探（三）
计算进程 打印进程计算结果送到 Buffer
从 Buffer中取数
Buffer
互斥互斥向打印进程发信号通知其从 Buffer里取数
Buffer空？
否是完成数据计算打印向计算进程发信号通知其向 Buffer送数
Buffer空？
否是合作进程间的同步关系
进程同步时面临的两种主要关系司机与售票员多个打印者计算者与打印者事件、设备等抽 象为 资源对进程间关系的处理变为对 资源 的访问方式临界资源
3.1.2 临界资源与临界区
(1)临界资源
一次只允许一个进程访问的资源
资源状态为临界,0 或 1
(2)临界区
每个进程用于访问临界资源的那段程序
同类临界区,同类资源的临界区
进入区
退出区最简单的资源临界区进入区临界区退出区进入区临界区退出区
...
...
...
...
...
...
...
...
阻塞等待资源释放改变资源状态释放资源唤醒等待进程进程 1 进程 2
同步四原则
3.1.3同步机制应遵循的原则空闲让进忙则等待有限等待让权等待同步原则
进程同步应遵循的原则
空闲让进
当资源空闲时，应当允许访问资源的进程进入临界区
忙则等待
当资源被占用时，应使申请访问该资源的进程等待，等待使用者归还资源两个基本原则，必须遵循同步原则
进程同步应遵循的原则
让权等待
在进程等待资源时，从执行态转为阻塞态，应当让出 CPU的使用权。系统将把 CPU分配给其它进程使用，以提高系统效率
有限等待
系统应保证等待的进程能在有限的时间内获得资源，继续执行，以防止无限等待浪费该进程已占用的资源锁机制
3.1.4 临界资源锁机制
例：商场的试衣间
是互斥资源
是临界资源
是共享资源
每个顾客必须遵循以下过程使用试衣间：
靠锁实现资源的共享管理观察锁状态 关锁 使用试衣间 开锁锁机制
临界资源锁机制锁锁变量 L
每个进程必须按照以下过程操作资源
L = 1 关闭状态，资源忙
L = 0 打开状态，资源空闲抽象
L=1 临界区 L=0… …
锁机制实现
一种简单的锁操作实现
void lock( L ){
check,if ( L = = 1 )
goto check;
else
L = 1;
}
void unlock( L ){
L = 0;
}
锁机制实现
......,.....
check,if ( L = = 1){
goto check;
else L = 1;
临界区
L
进程 1 进程 2
unlock( L );
......
check,if ( L = = 1){
goto check;
else L = 1;
临界区
unlock( L );
......
01
锁操作模型
锁操作的一般模型
Pi,.....,lock( L ) C( i ) unlock( L ),........
Pj,.....,lock( L ) C( j ) unlock( L ),........
C( i ),Pi的临界区
Pi,进程 i
出了问题的锁
......,.....
check,if ( L = = 1){
goto check;
else L = 1;
临界区
unlock( L );
......
check,if ( L = = 1){
goto check;
else L = 1;
临界区
unlock( L );
......
出现问题的锁进程 1 进程 2
L
01
尚未执行问题出在？
判断状态后改变状态前被打断锁与中断
通过开、关中断，保证关锁操作不被打断
L==0？
L＝ 1
关中断开中断开中断是否锁操作特点
锁操作的特点：
实现了进程互斥访问临界资源。
不遵循让权等待原则。 —— 忙等
L==0？
L＝ 1
关中断开中断开中断是否信号量机制
3.2 进程同步的信号量机制（ semaphore）
（ 1）信号量
信号量是对具体物理资源的抽象
不同类的资源用不同名称的信号量代表
同类资源的个数 用 > 0的信号量值表示
信号量值为 0 或 1 的信号量表示临界资源信号量是比锁更高级的资源抽象方式经典信号量
（ 2）经典信号量的 P,V操作
资源的申请与释放－－ 原语信号量,S
P（ s）
s <= 0?
s = s -1
N
Y
V（ s）
s = s + 1
申请一个资源释放一个资源忙等临界区 /资源访问区资源竞争
3.3经典进程同步问题
资源竞争时的进程同步
对竞争资源的互斥访问
…
P（ s）
临界区
V（ s）
进程 1 进程 2
…
…
P（ s）
临界区
V（ s）
…
P（ s）
访问资源
V（ s）
状态,状态：唤醒就绪 执行 就绪 执行 阻塞
相互合作时的进程同步
保证进程间的前驱、后继关系相互合作司机进程正常行车到站停车
V（停车）
喝茶
P（关车门）
正常行车售票
P（停车）
开车门关车门
V（关车门）
售票售票员进程同步点同步点V（ s） P（ s）
前驱 后继信号量初值为 0
公用与私用信号量公用信号量：
私用信号量：
一组进程共享，都可进行 P,V操作用于进程间资源的竞争拥有信号量的进程只对信号量进行 P操作
V操作由其他进程进行用于进程间的合作
P（ s） V（ s）访问资源
P（ s） V（ s）访问资源进程 1：
进程 2：
P（ s）
V（ s）
后继进程：
前驱进程：
经典进程同步问题
经典进程同步问题
生产者 —— 消费者问题
读者 —— 写者问题
哲学家进餐问题生产者消费者问题
3.3.1生产者 —— 消费者问题
问题描述,
有多个生产者在生产消息
有多个消费者在消费消息
消费者消费的是生产者生产的消息生产者消费者问题
消息缓冲池
生产者产生的消息放入缓冲池内；
消费者从缓冲池内取走消息消费；
消费者消费后的空白消息块放进空白缓冲池内供生产者使用。
生产者 消费者消息缓冲池空白块缓冲池
2 31 21
生产者消费者算法分析
算法分析
两类进程：生产者进程和消费者进程
（ 1）进程间的关系
生产者生产消息后消费者消费
消费者消费后的空白缓冲块由生产者生产消息
P（ s）
V（ s）
后继进程：
前驱进程：
P（ s）
V（ s）
后继进程：
前驱进程：
（ full）
（ full）
生产者：
消费者：
生产者：
消费者：
（ empty）
（ empty）
生产者消费者算法分析
（ 2）队列的操作
两个共享队列：
消息缓冲队列
空白缓冲队列
多个进程共享一个队列
是否需要保护消息缓冲池空白块缓冲池生产者放入消息 取空白块生产者消费者消费者取走消息 放空白块生产者消费者算法分析
入队操作
newmsg->next = msglist->head;
msglist->head = newmsg;
msglist->head
newmsg
队列操作
同时入队 进程 1 进程 2
newmsg1->next =
msglist->head;
msglist->head =
newmsg1;
msglist->head
newmsg1
newmsg2
两个 message都挂到了队列上就绪 执行 就绪 执行
newmsg2->next =
msglist->head;
msglist->head =
newmsg2;
出了问题的队列操作
同时入队 进程 1 进程 2
newmsg1->next =
msglist->head;
msglist->head =
newmsg1;
msglist->head
newmsg1
newmsg2
队列操作过程需要互斥进行就绪 执行 就绪 执行
newmsg2->next =
msglist->head;
msglist->head =
newmsg2;
出了问题的队列操作
同时入队 进程 1 进程 2
newmsg1->next =
msglist->head;
msglist->head =
newmsg1;
msglist->head
newmsg1
newmsg2
就绪 执行 就绪 执行
newmsg2->next =
msglist->head;
msglist->head =
newmsg2;
生产者消费者算法分析
进程间的关系
生产者生产消息 后 消费者消费的合作关系
消费者消费 后 的空白缓冲块由生产者生产消息的合作关系
进程间在队列操作上的互斥关系
P（ s） V（ s）访问资源
P（ s） V（ s）访问资源进程 1：
进程 2：
（ mutex） V（ mutex）
（ mutex） V（ mutex）
操作队列操作队列生产者消费者算法分析
信号量
full：私有信号量
empty：私有信号量
mutex：公用信号量
队列
full_list：消息队列
empty_list：空白块队列生产者消费者算法流程生产者产生一个消息；
申请一个空白缓冲区；
从空白队列中取一个空白缓冲区；
申请队列操作的互斥；
释放队列操作的互斥；
在空白缓冲区内填充消息消息放入消息队列申请队列操作的互斥；
释放队列操作的互斥；
释放一个消息信号消费者申请一个消息申请队列操作的互斥；
释放队列操作的互斥从消息队列中取一个消息；
消费消息将消息清空为空白空白块放入空白队列申请队列操作的互斥；
释放队列操作的互斥；
释放一个空白块信号
void producer( ){
while( 1 ){
create( msg );
P( empty );
P( mutex );
buffer = pop( empty_list )；
V( mutex );
fill_buffer( buffer,msg);
P( mutex );
push( full_list,buffer);
V( mutex );
V( full ); }
}
semaphore full = { 0,NULL };
semaphore empty = { n,NULL};
semaphore mutex = {1,NULL};
void consumer( ){
while( 1 ){
P( full );
P( mutex );
msg = pop( full_list )；
V( mutex );
consume( msg );
fill_zero( msg );
P( mutex );
push( empty_list,msg);
V( mutex );
V( empty ); }
}
生产者消费者算法小结
小结：
在分析进程同步问题中，逐个分析进程间的关系是关键
不管多复杂的关系，总能归结为两种基本关系
（竞争与合作），总是这两种关系的组合
不管公用还是私用，信号量的使用必须成对出现思考多个生产者之间是什么关系，需要特别的实现吗？
多个消费者之间是什么关系，需要特别的实现吗？
读者写者问题
3.3.2读者 —— 写者问题
（ Reader and Writer ）
问题描述
一个数据纪录，有多个进程进行读操作，另一些进程进行修改操作
（ Reader）
（ Writer）
读写策略
允许多个进程同时进行读操作 —— 读不互斥
不允许多于一个进程进行写操作 —— 写互斥
不允许读写操作同时进行 —— 读写互斥读者写者问题分析读者 写者读操作 写操作
p（ mutex）
v（ mutex）
p（ mutex）
v（ mutex）
写者之间互斥读者与写者之间互斥读者之间 互斥哲学家问题
3.3.3哲学家进餐问题
问题描述
五位哲学家围桌而坐
哲学家在思考问题时不需要任何资源，思考完问题后进入进餐态。
每人必须获得左右两支筷子才能进餐思考思考思考思考思考准备进餐进餐准备进餐进餐哲学家问题分析死锁思考思考思考思考思考准备进餐准备进餐 准备进餐准备进餐准备进餐思考
p（ left_stick）
p（ right_stick)
v（ right_stick)
v（ left_stick）
eat
进程的通信
3.4 进程的通信
进程之间的信息交换
低级通信
进程的同步，简单的信号交换
如：锁、信号量
高级通信－－进程通信
高效、大量数据传递进程通信的类型
3.4.1进程通信类型
1）共享存贮器
共享数据
共享存贮区
通过数据、数据区的共享，写入与读出达到通信的目的
2）直接通信方式 —— 消息缓冲
采用进程的消息缓冲队列
消息发送者将消息直接放在接收者的消息缓冲队列进程通信的类型
3）间接通信方式
利用中间者 —— 信箱、邮局来传递信件。
发送进程将消息发送到信箱中，接收进程从信箱中取出消息
4）管道通信
用以连接读、写进程的共享文件消息缓冲通信
3.4.2 消息缓冲通信
用消息传递的方式 (传递数据块 )达到通信的目的
1)系统管理空白缓冲池
2)发送者向系统申请空白缓冲区
3)发送者将填有消息的缓冲区挂到接收者的消息队列
4)接收者在适当时候从消息队列中读取数据
5)系统提供消息通信原语：
send_message( ),
receive_message( );
sender
receiver
每个接收者有自己的消息队列信箱通信
3.4.3信箱通信方式
A
B
C
D
E
中间实体 信箱头与信箱体用户号与口令存放多种格式消息定长消息变长消息类型消息信箱头
（信箱名、口令）
信格信格信格信格信格管道通信
3.4.4管道通信
管道
是连接接收进程和发送进程的共享文件
共享文件可居于外存
（ 1）互斥访问
（ 2）写后读，读后写的同步
（ 3）只有在管道双方都存在时才能通信进程 2读出 写入进程 1写入 进程 3读出作业
进程同步的主要关系有哪些？
进程同步的原则是什么，请分别解释
请用信号量描述计算进程向缓冲区写数据，
打印进程从缓冲区取出数据并打印的过程
进程间高级通信有哪些方式？
公用与私用信号量公用信号量：
私用信号量：
一组进程共享，都可进行 P,V操作用于进程间资源的竞争拥有信号量的进程只对信号量进行 P操作
V操作由其他进程进行用于进程间的合作
P（ s） V（ s）访问资源
P（ s） V（ s）访问资源进程 1：
进程 2：
P（ s）
V（ s）
后继进程：
前驱进程：
苹果桔子问题桌上有 一只盘子,每次 只能放入一只水果 ；爸爸专向盘子中 放苹果 (apple),妈妈专向盘子中 放桔于 (orange),一个儿子专等 吃盘子中的桔子,一个女儿专等 吃盘子里的苹果信号量解决苹果桔子问题
plate,integer;
sp:semaphore； /* 盘子里可以放几个水果 */
sg1:semaphore; /* 盘子里有桔子 */
sg2:semaphore; /* 盘子里有苹果 */
cobegin
process father
begin
L1:削一个苹果 ；
把苹果放入 plate；
goto L1;
end;
process mother
begin
L2:剥一个桔子 ；
把桔子放入 plate；
goto L2;
end;
process son
begin
L3:
从 plate中取桔子；
吃桔子；
goto L3;
end;
process daughter
begin
L4:
从 plate中取苹果；
吃苹果；
goto L4;
end;
coend
P(sp);
V(sg2);
V(sp);
P(sg1);
P(sg2);
P(sp);
V(sg1);
V(sp);
sp,= 1; /* 盘子里允许放一个水果 */
Sg1,= 0; /* 盘子里没有桔子 */
sg2,= 0; /* 盘子里没有苹果 */
进程同步问题的提出
进程异步推进可能造成混乱
混乱可能导致不可再现
进程同步目标维持进程并发性以提高系统效率进程执行异步（断续）
资源的非封闭（共享）
结果不可再现进程同步 进程间相互合作资源有效共享 结果可再现进程的同步关系
3.1进程同步的基本概念
3.1.1进程间的两种主要关系
进程间的关系与进程间的独立性
进程间的关系是在进程间相对独立的前提下发展的
独立获得资源
独立调度进程间的同步关系（一）
正常行车到站停车开车售票开车门关车门司机 售票员合作合作检查车况 维持秩序获得打印数据进程间的同步关系（二）
打印进程 1 打印进程 2
打印 打印互斥获得打印数据进程间的同步关系（三）
计算进程打印进程计算结果送到 Buffer
从 Buffer中取数
Buffer
互斥完成数据计算打印通知打印进程打印通知计算进程送下一个数合作进程间的同步关系司机与售票员多个打印者计算者与打印者正常行车到站停车开车售票开车门关车门司机 售票员同步同步到站停车 否是检查车况维持秩序否关车门是同步实现初探（二）
打印进程 1 打印进程 2
打印 打印互斥获得打印数据 获得打印数据打印机可用？
设置打印机为不可用是否打印机可用？
设置打印机为不可用是否同步实现初探（三）
计算进程 打印进程计算结果送到 Buffer
从 Buffer中取数
Buffer
互斥互斥向打印进程发信号通知其从 Buffer里取数
Buffer空？
否是完成数据计算打印向计算进程发信号通知其向 Buffer送数
Buffer空？
否是合作进程间的同步关系
进程同步时面临的两种主要关系司机与售票员多个打印者计算者与打印者事件、设备等抽 象为 资源对进程间关系的处理变为对 资源 的访问方式临界资源
3.1.2 临界资源与临界区
(1)临界资源
一次只允许一个进程访问的资源
资源状态为临界,0 或 1
(2)临界区
每个进程用于访问临界资源的那段程序
同类临界区,同类资源的临界区
进入区
退出区最简单的资源临界区进入区临界区退出区进入区临界区退出区
...
...
...
...
...
...
...
...
阻塞等待资源释放改变资源状态释放资源唤醒等待进程进程 1 进程 2
同步四原则
3.1.3同步机制应遵循的原则空闲让进忙则等待有限等待让权等待同步原则
进程同步应遵循的原则
空闲让进
当资源空闲时，应当允许访问资源的进程进入临界区
忙则等待
当资源被占用时，应使申请访问该资源的进程等待，等待使用者归还资源两个基本原则，必须遵循同步原则
进程同步应遵循的原则
让权等待
在进程等待资源时，从执行态转为阻塞态，应当让出 CPU的使用权。系统将把 CPU分配给其它进程使用，以提高系统效率
有限等待
系统应保证等待的进程能在有限的时间内获得资源，继续执行，以防止无限等待浪费该进程已占用的资源锁机制
3.1.4 临界资源锁机制
例：商场的试衣间
是互斥资源
是临界资源
是共享资源
每个顾客必须遵循以下过程使用试衣间：
靠锁实现资源的共享管理观察锁状态 关锁 使用试衣间 开锁锁机制
临界资源锁机制锁锁变量 L
每个进程必须按照以下过程操作资源
L = 1 关闭状态，资源忙
L = 0 打开状态，资源空闲抽象
L=1 临界区 L=0… …
锁机制实现
一种简单的锁操作实现
void lock( L ){
check,if ( L = = 1 )
goto check;
else
L = 1;
}
void unlock( L ){
L = 0;
}
锁机制实现
......,.....
check,if ( L = = 1){
goto check;
else L = 1;
临界区
L
进程 1 进程 2
unlock( L );
......
check,if ( L = = 1){
goto check;
else L = 1;
临界区
unlock( L );
......
01
锁操作模型
锁操作的一般模型
Pi,.....,lock( L ) C( i ) unlock( L ),........
Pj,.....,lock( L ) C( j ) unlock( L ),........
C( i ),Pi的临界区
Pi,进程 i
出了问题的锁
......,.....
check,if ( L = = 1){
goto check;
else L = 1;
临界区
unlock( L );
......
check,if ( L = = 1){
goto check;
else L = 1;
临界区
unlock( L );
......
出现问题的锁进程 1 进程 2
L
01
尚未执行问题出在？
判断状态后改变状态前被打断锁与中断
通过开、关中断，保证关锁操作不被打断
L==0？
L＝ 1
关中断开中断开中断是否锁操作特点
锁操作的特点：
实现了进程互斥访问临界资源。
不遵循让权等待原则。 —— 忙等
L==0？
L＝ 1
关中断开中断开中断是否信号量机制
3.2 进程同步的信号量机制（ semaphore）
（ 1）信号量
信号量是对具体物理资源的抽象
不同类的资源用不同名称的信号量代表
同类资源的个数 用 > 0的信号量值表示
信号量值为 0 或 1 的信号量表示临界资源信号量是比锁更高级的资源抽象方式经典信号量
（ 2）经典信号量的 P,V操作
资源的申请与释放－－ 原语信号量,S
P（ s）
s <= 0?
s = s -1
N
Y
V（ s）
s = s + 1
申请一个资源释放一个资源忙等临界区 /资源访问区资源竞争
3.3经典进程同步问题
资源竞争时的进程同步
对竞争资源的互斥访问
…
P（ s）
临界区
V（ s）
进程 1 进程 2
…
…
P（ s）
临界区
V（ s）
…
P（ s）
访问资源
V（ s）
状态,状态：唤醒就绪 执行 就绪 执行 阻塞
相互合作时的进程同步
保证进程间的前驱、后继关系相互合作司机进程正常行车到站停车
V（停车）
喝茶
P（关车门）
正常行车售票
P（停车）
开车门关车门
V（关车门）
售票售票员进程同步点同步点V（ s） P（ s）
前驱 后继信号量初值为 0
公用与私用信号量公用信号量：
私用信号量：
一组进程共享，都可进行 P,V操作用于进程间资源的竞争拥有信号量的进程只对信号量进行 P操作
V操作由其他进程进行用于进程间的合作
P（ s） V（ s）访问资源
P（ s） V（ s）访问资源进程 1：
进程 2：
P（ s）
V（ s）
后继进程：
前驱进程：
经典进程同步问题
经典进程同步问题
生产者 —— 消费者问题
读者 —— 写者问题
哲学家进餐问题生产者消费者问题
3.3.1生产者 —— 消费者问题
问题描述,
有多个生产者在生产消息
有多个消费者在消费消息
消费者消费的是生产者生产的消息生产者消费者问题
消息缓冲池
生产者产生的消息放入缓冲池内；
消费者从缓冲池内取走消息消费；
消费者消费后的空白消息块放进空白缓冲池内供生产者使用。
生产者 消费者消息缓冲池空白块缓冲池
2 31 21
生产者消费者算法分析
算法分析
两类进程：生产者进程和消费者进程
（ 1）进程间的关系
生产者生产消息后消费者消费
消费者消费后的空白缓冲块由生产者生产消息
P（ s）
V（ s）
后继进程：
前驱进程：
P（ s）
V（ s）
后继进程：
前驱进程：
（ full）
（ full）
生产者：
消费者：
生产者：
消费者：
（ empty）
（ empty）
生产者消费者算法分析
（ 2）队列的操作
两个共享队列：
消息缓冲队列
空白缓冲队列
多个进程共享一个队列
是否需要保护消息缓冲池空白块缓冲池生产者放入消息 取空白块生产者消费者消费者取走消息 放空白块生产者消费者算法分析
入队操作
newmsg->next = msglist->head;
msglist->head = newmsg;
msglist->head
newmsg
队列操作
同时入队 进程 1 进程 2
newmsg1->next =
msglist->head;
msglist->head =
newmsg1;
msglist->head
newmsg1
newmsg2
两个 message都挂到了队列上就绪 执行 就绪 执行
newmsg2->next =
msglist->head;
msglist->head =
newmsg2;
出了问题的队列操作
同时入队 进程 1 进程 2
newmsg1->next =
msglist->head;
msglist->head =
newmsg1;
msglist->head
newmsg1
newmsg2
队列操作过程需要互斥进行就绪 执行 就绪 执行
newmsg2->next =
msglist->head;
msglist->head =
newmsg2;
出了问题的队列操作
同时入队 进程 1 进程 2
newmsg1->next =
msglist->head;
msglist->head =
newmsg1;
msglist->head
newmsg1
newmsg2
就绪 执行 就绪 执行
newmsg2->next =
msglist->head;
msglist->head =
newmsg2;
生产者消费者算法分析
进程间的关系
生产者生产消息 后 消费者消费的合作关系
消费者消费 后 的空白缓冲块由生产者生产消息的合作关系
进程间在队列操作上的互斥关系
P（ s） V（ s）访问资源
P（ s） V（ s）访问资源进程 1：
进程 2：
（ mutex） V（ mutex）
（ mutex） V（ mutex）
操作队列操作队列生产者消费者算法分析
信号量
full：私有信号量
empty：私有信号量
mutex：公用信号量
队列
full_list：消息队列
empty_list：空白块队列生产者消费者算法流程生产者产生一个消息；
申请一个空白缓冲区；
从空白队列中取一个空白缓冲区；
申请队列操作的互斥；
释放队列操作的互斥；
在空白缓冲区内填充消息消息放入消息队列申请队列操作的互斥；
释放队列操作的互斥；
释放一个消息信号消费者申请一个消息申请队列操作的互斥；
释放队列操作的互斥从消息队列中取一个消息；
消费消息将消息清空为空白空白块放入空白队列申请队列操作的互斥；
释放队列操作的互斥；
释放一个空白块信号
void producer( ){
while( 1 ){
create( msg );
P( empty );
P( mutex );
buffer = pop( empty_list )；
V( mutex );
fill_buffer( buffer,msg);
P( mutex );
push( full_list,buffer);
V( mutex );
V( full ); }
}
semaphore full = { 0,NULL };
semaphore empty = { n,NULL};
semaphore mutex = {1,NULL};
void consumer( ){
while( 1 ){
P( full );
P( mutex );
msg = pop( full_list )；
V( mutex );
consume( msg );
fill_zero( msg );
P( mutex );
push( empty_list,msg);
V( mutex );
V( empty ); }
}
生产者消费者算法小结
小结：
在分析进程同步问题中，逐个分析进程间的关系是关键
不管多复杂的关系，总能归结为两种基本关系
（竞争与合作），总是这两种关系的组合
不管公用还是私用，信号量的使用必须成对出现思考多个生产者之间是什么关系，需要特别的实现吗？
多个消费者之间是什么关系，需要特别的实现吗？
读者写者问题
3.3.2读者 —— 写者问题
（ Reader and Writer ）
问题描述
一个数据纪录，有多个进程进行读操作，另一些进程进行修改操作
（ Reader）
（ Writer）
读写策略
允许多个进程同时进行读操作 —— 读不互斥
不允许多于一个进程进行写操作 —— 写互斥
不允许读写操作同时进行 —— 读写互斥读者写者问题分析读者 写者读操作 写操作
p（ mutex）
v（ mutex）
p（ mutex）
v（ mutex）
写者之间互斥读者与写者之间互斥读者之间 互斥哲学家问题
3.3.3哲学家进餐问题
问题描述
五位哲学家围桌而坐
哲学家在思考问题时不需要任何资源，思考完问题后进入进餐态。
每人必须获得左右两支筷子才能进餐思考思考思考思考思考准备进餐进餐准备进餐进餐哲学家问题分析死锁思考思考思考思考思考准备进餐准备进餐 准备进餐准备进餐准备进餐思考
p（ left_stick）
p（ right_stick)
v（ right_stick)
v（ left_stick）
eat
进程的通信
3.4 进程的通信
进程之间的信息交换
低级通信
进程的同步，简单的信号交换
如：锁、信号量
高级通信－－进程通信
高效、大量数据传递进程通信的类型
3.4.1进程通信类型
1）共享存贮器
共享数据
共享存贮区
通过数据、数据区的共享，写入与读出达到通信的目的
2）直接通信方式 —— 消息缓冲
采用进程的消息缓冲队列
消息发送者将消息直接放在接收者的消息缓冲队列进程通信的类型
3）间接通信方式
利用中间者 —— 信箱、邮局来传递信件。
发送进程将消息发送到信箱中，接收进程从信箱中取出消息
4）管道通信
用以连接读、写进程的共享文件消息缓冲通信
3.4.2 消息缓冲通信
用消息传递的方式 (传递数据块 )达到通信的目的
1)系统管理空白缓冲池
2)发送者向系统申请空白缓冲区
3)发送者将填有消息的缓冲区挂到接收者的消息队列
4)接收者在适当时候从消息队列中读取数据
5)系统提供消息通信原语：
send_message( ),
receive_message( );
sender
receiver
每个接收者有自己的消息队列信箱通信
3.4.3信箱通信方式
A
B
C
D
E
中间实体 信箱头与信箱体用户号与口令存放多种格式消息定长消息变长消息类型消息信箱头
（信箱名、口令）
信格信格信格信格信格管道通信
3.4.4管道通信
管道
是连接接收进程和发送进程的共享文件
共享文件可居于外存
（ 1）互斥访问
（ 2）写后读，读后写的同步
（ 3）只有在管道双方都存在时才能通信进程 2读出 写入进程 1写入 进程 3读出作业
进程同步的主要关系有哪些？
进程同步的原则是什么，请分别解释
请用信号量描述计算进程向缓冲区写数据，
打印进程从缓冲区取出数据并打印的过程
进程间高级通信有哪些方式？
公用与私用信号量公用信号量：
私用信号量：
一组进程共享，都可进行 P,V操作用于进程间资源的竞争拥有信号量的进程只对信号量进行 P操作
V操作由其他进程进行用于进程间的合作
P（ s） V（ s）访问资源
P（ s） V（ s）访问资源进程 1：
进程 2：
P（ s）
V（ s）
后继进程：
前驱进程：
苹果桔子问题桌上有 一只盘子,每次 只能放入一只水果 ；爸爸专向盘子中 放苹果 (apple),妈妈专向盘子中 放桔于 (orange),一个儿子专等 吃盘子中的桔子,一个女儿专等 吃盘子里的苹果信号量解决苹果桔子问题
plate,integer;
sp:semaphore； /* 盘子里可以放几个水果 */
sg1:semaphore; /* 盘子里有桔子 */
sg2:semaphore; /* 盘子里有苹果 */
cobegin
process father
begin
L1:削一个苹果 ；
把苹果放入 plate；
goto L1;
end;
process mother
begin
L2:剥一个桔子 ；
把桔子放入 plate；
goto L2;
end;
process son
begin
L3:
从 plate中取桔子；
吃桔子；
goto L3;
end;
process daughter
begin
L4:
从 plate中取苹果；
吃苹果；
goto L4;
end;
coend
P(sp);
V(sg2);
V(sp);
P(sg1);
P(sg2);
P(sp);
V(sg1);
V(sp);
sp,= 1; /* 盘子里允许放一个水果 */
Sg1,= 0; /* 盘子里没有桔子 */
sg2,= 0; /* 盘子里没有苹果 */
