第三章-习题解答.ppt

3.10 设在书 3.6节中所描述的生产者-消费者问题中，其缓冲部分为m个长度相等的有界缓冲区组成，且每次传输数据长度等于有界缓冲区长度以及生产者和消费者可对缓冲区同时操作。重新描述发送过程deposit(data)和接收过程remove(data)。 作业中主要问题： 1、设第1块缓冲区的公用信号量为mutex[1] 2、mutex[i] ；mutex t[i] ； mutex [n] 3、P(avail) P(mutex[i] ) V(full) V(mutex[i] ) 分析： 1、本题所描述的生产者-消费者问题中，“其缓冲部分为m个长度相等的有界缓冲区组成，且每次传输数据长度等于有界缓冲区长度”，与教材中3.6节（P62）问题有所不同。 (1)教材中3.6节问题中，一次从有界缓冲区中取一个单元； (2)这里，一次从m个有界缓冲区中取一个缓冲区。 2、本题所描述的生产者-消费者问题中，“生产者和消费者可对缓冲区同时操作”，与教材中3.6节（P62）问题有所不同。 (1)教材中3.6节问题中，由于有界缓冲区是临界资源，因此，各生产者进程和各消费者进程之间必须互斥执行。 (2)这里，生产者和消费者之间不需要互斥。 (3)生产者和生产者之间？消费者和消费者之间？ 解：首先，可以看到，本问题是一个同步问题。即生产者和消费者之间满足如下条件： (1) 消费者想接收数据时，有界缓冲区中至少有一个缓冲区是满的； (2) 生产者想发送数据时，有界缓冲区中至少有一个缓冲区是空的。 其次，虽然生产者和消费者之间不需要互斥，但在生产者（消费者）之间，由于有界缓冲区是临界资源，因此，各生产者（消费者）进程之间必须互斥执行。 由上分析，设公用信号量mutex1用来保证生产者进程间的互斥，公用信号量mutex2用来保证消费者进程间的互斥， mutex1 和mutex2初值均为1； 设信号量avail为生产者进程的私用信号量，表示空缓冲区数目，初值为m； 设信号量full为消费者进程的私用信号量，表示非空缓冲区数目，初值为0； 从而有： 3.11 两进程PA，PB通过两FIFO缓冲区队列连接（如图），每个缓冲区长度等于传送消息长度。进程PA，PB之间的通信满足如下条件： (1) 至少有一个空缓冲区存在时，相应的发送进程才能发送一个消息。 (2) 当缓冲队列中至少存在一个非空缓冲区时，相应的接收进程才能接收一个消息。 试描述发送过程send(i,m)和接收过程receive(i,m)。这里i代表缓冲队列。 作业中主要问题： 1、bufempty[0]= bufempty[1]=n 2、local x buf [ i ] (x) buf [ i ] (x)←m 3、算法格式：缩进；分号 4、教材P61 分析： 1、本题所描述问题中（设上面的缓冲队列为0，下面的缓冲队列为1，即i的值为0和1）， (1)PA从队列1中接收数据时，要求至少有一个缓冲区是非空的；向队列0中发送数据时，要求至少有一个缓冲区是空的； 分析： (2)PB从队列0中接收数据时，要求至少有一个缓冲区是非空的；向队列1中发送数据时，要求至少有一个缓冲区是空的。 2、因为是FIFO缓冲区队列，所以对缓冲区队列的操作不需要互斥。 3、由于PA和PB的对称性，对i要进行一定处理 解：首先，可以看到，本问题存在同步关系，即PA和PB之间存在着同步关系。 (1) 设n[i]为缓冲队列i中缓冲区的个数。 (2)设SM(i) 为发送进程的私用信号量，表示缓冲队列i中空缓冲区的个数，其初值为 n[i] 。 (3)设RM(i) 为接收进程的私用信号量，表示缓冲队列i中满缓冲区的个数，其初值为0。 (2)设SM(i) 为发送进程的私用信号量，表示缓冲队列i中空缓冲区的个数，其初值为 n[i] 。 (3)设RM(i) 为接收进程的私用信号量，表示缓冲队列i中满缓冲区的个数，其初值为0 。 (4) 进程PA或PB调用过程receive(i,m)将消息m从缓冲队列i读往自己的数据区；调用过程send(i,m)将消息m送往缓冲队列i。 send(i,m): begin 建立消息m Ｐ（SM[i]） 将消息m送入消息缓冲队列i Ｖ（RM[i]） end receive (i,m): begin Ｐ（RM[i]） 从消息缓冲队列i中接收消息m， 并送入接收进程的数据区 Ｖ（SM[i]） end PA：(i=0) cobegin …… send(i,m) …… receive(