第三章-习题解答（课堂PPT）

3.10设在书3.6节中所描述的生产者-消费者问题中，其缓冲部分为m个长度相等的有界缓冲区组成，且每次传输数据长度等于有界缓冲区长度以及生产者和消费者可对缓冲区同时操作。重新描述发送过程deposit(data)和接收过程remove(data)。,1,作业中主要问题：1、设第1块缓冲区的公用信号量为mutex12、mutexi；mutexti；mutexn3、P(avail)P(mutexi)V(full)V(mutexi),2,分析：1、本题所描述的生产者-消费者问题中，“其缓冲部分为m个长度相等的有界缓冲区组成，且每次传输数据长度等于有界缓冲区长度”，与教材中3.6节（P62）问题有所不同。(1)教材中3.6节问题中，一次从有界缓冲区中取一个单元；(2)这里，一次从m个有界缓冲区中取一个缓冲区。,3,2、本题所描述的生产者-消费者问题中，“生产者和消费者可对缓冲区同时操作”，与教材中3.6节（P62）问题有所不同。(1)教材中3.6节问题中，由于有界缓冲区是临界资源，因此，各生产者进程和各消费者进程之间必须互斥执行。(2)这里，生产者和消费者之间不需要互斥。(3)生产者和生产者之间？消费者和消费者之间？,4,解：首先，可以看到，本问题是一个同步问题。即生产者和消费者之间满足如下条件：(1)消费者想接收数据时，有界缓冲区中至少有一个缓冲区是满的；(2)生产者想发送数据时，有界缓冲区中至少有一个缓冲区是空的。,5,其次，虽然生产者和消费者之间不需要互斥，但在生产者（消费者）之间，由于有界缓冲区是临界资源，因此，各生产者（消费者）进程之间必须互斥执行。由上分析，设公用信号量mutex1用来保证生产者进程间的互斥，公用信号量mutex2用来保证消费者进程间的互斥，mutex1和mutex2初值均为1；,6,设信号量avail为生产者进程的私用信号量，表示空缓冲区数目，初值为m；设信号量full为消费者进程的私用信号量，表示非空缓冲区数目，初值为0；从而有：,7,生产者进程deposit(data):begin（avail）（mutex1）送数据入某空缓冲区（mutex1）（full）end,消费者进程remove(data):begin（full）（mutex2）取某缓冲区中数据（mutex2）（avail）end,8,3.11两进程PA，PB通过两FIFO缓冲区队列连接（如图），每个缓冲区长度等于传送消息长度。进程PA，PB之间的通信满足如下条件：(1)至少有一个空缓冲区存在时，相应的发送进程才能发送一个消息。(2)当缓冲队列中至少存在一个非空缓冲区时，相应的接收进程才能接收一个消息。试描述发送过程send(i,m)和接收过程receive(i,m)。这里i代表缓冲队列。,9,作业中主要问题：1、bufempty0=bufempty1=n2、localxbufi(x)bufi(x)m3、算法格式：缩进；分号4、教材P61,10,分析：1、本题所描述问题中（设上面的缓冲队列为0，下面的缓冲队列为1，即i的值为0和1），(1)PA从队列1中接收数据时，要求至少有一个缓冲区是非空的；向队列0中发送数据时，要求至少有一个缓冲区是空的；,11,分析：(2)PB从队列0中接收数据时，要求至少有一个缓冲区是非空的；向队列1中发送数据时，要求至少有一个缓冲区是空的。2、因为是FIFO缓冲区队列，所以对缓冲区队列的操作不需要互斥。3、由于PA和PB的对称性，对i要进行一定处理,12,解：首先，可以看到，本问题存在同步关系，即PA和PB之间存在着同步关系。(1)设ni为缓冲队列i中缓冲区的个数。(2)设SM(i)为发送进程的私用信号量，表示缓冲队列i中空缓冲区的个数，其初值为ni。(3)设RM(i)为接收进程的私用信号量，表示缓冲队列i中满缓冲区的个数，其初值为0。,13,(2)设SM(i)为发送进程的私用信号量，表示缓冲队列i中空缓冲区的个数，其初值为ni。(3)设RM(i)为接收进程的私用信号量，表示缓冲队列i中满缓冲区的个数，其初值为0。(4)进程PA或PB调用过程receive(i,m)将消息m从缓冲队列i读往自己的数据区；调用过程send(i,m)将消息m送往缓冲队列i。,(4)进程PA或PB调用过程receive(i,m)将消息m从缓冲队列i读往自己的数据区；调用过程send(i+1mod2,m)将消息m送往缓冲队列i+1mod2。,14,send(i,m):begin建立消息m（SMi）将消息m送入消息缓冲队列i（RMi）end,可描述过程send(i,m)和receive(i,m)如下：,15,receive(i,m):begin（RMi）从消息缓冲队列i中接收消息m，并送入接收进程的数据区（SMi）end,可描述过程send(i,m)和receive(i,m)如下：,16,PA：(i=0)cobeginsend(i,m)receive(i+1mod2,m)coend,PA和PB的描述如下：,PB：(i=1)cobeginsend(i,m)receive(i+1mod2,m)coend,17,PA：(i=0)cobeginsend(0,m)receive(1,m)coend,PA和PB的描述如下：,PB：(i=1)cobeginsend(1,m)receive(0,m)coend,18,3.14设有5个哲学家，共享一张放有五把椅子的桌子，每人分得一把椅子。但是，桌子上总共只有5支筷子，在每人两边分开各放一支。哲学家们在肚子饥饿时才试图分两次从两边拾起筷子就餐。条件：(1)只有拿到两支筷子时，哲学家才能吃饭。(2)如果筷子已在他人手上，则该哲学家必须等待到他人吃完之后才能拿到筷子。(3)任一哲学家在自己未拿到两支筷子吃饭之前，决不放下自己手中的筷子。,19,试:(1)描述一个保证不会出现两个邻座同时要求吃饭的通信算法。(2)描述一个既没有两邻座同时吃饭，又没有人饿死（永远拿不到筷子）的算法。(3)在什么情况下，5个哲学家全部吃不上饭？,20,哲学家就餐问题：,21,作业中主要问题：1、信号量的说明2、分奇偶；3、“任一哲学家拿到一支筷子，就已经阻止了邻座的哲学家吃饭”,22,作业中主要问题：4、send(i)；(与c5、P(ci,ci+1mod5)或P(ci),P(ci+1mod5)6、“看到右侧筷子不可用，又放下左侧筷子”7、5个哲学家同时拿起筷子8、如果出现死锁，则5个哲学家都吃不上饭9、在本题（1）中，5个哲学家都吃不上饭,23,解：显然，5支筷子都是临界资源，五个哲学家philosopher(i)取用筷子就餐时要进行互斥。(1)要保证不会出现两个邻座同时要求吃饭，就要求各philosopher(i)按一定的顺序取筷子。设公用信号量forki用于philosopher(i)取用筷子就餐时的互斥，其初值均为1。这里i的取值为04，并且都是先取右边的筷子，再取左边的筷子。当i=4时，左边的筷子是i+1mod5，即0。,24,算法如下（i=0,1,2,3,4）：philosopher(i)begin/Think/EatP(forki)P(forki+1mod5)eat()V(forki+1mod5)V(forki)end,25,(3)从算法中可以看到，当每位philosopher(i)都取到了左边的筷子，然后试图取右边的筷子时，会出现5位哲学家都吃不上饭的情形。即出现饿死现象。,philosopher(i)beginP(forki)P(forki+1mod5)eat()V(forki+1mod5)V(forki)end,26,(2)要保证不出现既没有两邻座同时吃饭，又没有人饿死（永远拿不到筷子）的情形，只要某位philosopher(i)按相反的顺序取筷子即可。设公用信号量forki用于philosopher(i)取用筷子就餐时的互斥，其初值均为1。这里i的取值为04，规定philosopher(4)先取左边的筷子，再取右边的筷子。,27,算法如下(i=0,1,2,3)：philosopher(i)begin/Think/EatP(forki)P(forki+1)eat()V(forki+1)V(forki)end,philosopher(4)begin/Think/EatP(fork0)P(fork4)eat()V(fork4)V(fork0)end,28,补：荷兰科学家E.W.Dijkstra在1968年发表的一篇论文中提出了三种用来解决临界区互斥问题的算法。这三种算法正确吗？若不正确，请分别说明为什么不正确。即指出在什么情况下不正确。,29,(a),proc(inti=0)while(TRUE)compute;while(turn!=0);criticalsection;turn=1;,proc(inti=1)while(TRUE)compute;while(turn!=1);criticalsection;turn=0;,sharedintturn;turn=1;fork(proc,1,0);fork(proc,1,1);,30,(b),proc(inti)while(TRUE)compute;while(flag(i+1)mod2);flagi=TRUE;criticalsection;flagi=FALSE;sharedbooleanflag2;flag0=flag1