并发控制互斥与同步.pptx

《并发控制互斥与同步.pptx》由会员分享，可在线阅读，更多相关《并发控制互斥与同步.pptx（179页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1进程的并发控制进程的并发控制互斥与同步互斥与同步3.1 3.1 前趋图前趋图(Precedence Graph)(Precedence Graph)3.2 3.2 进程的同步与互斥进程的同步与互斥3.3 3.3 信号量和管程信号量和管程3.4 3.4 进程通信进程通信第1页/共179页2互斥与同步概念互斥与同步概念在多道程序环境中，由于进程合作和资源在多道程序环境中，由于进程合作和资源共享，使得并发执行的多个进程之间存在共享，使得并发执行的多个进程之间存在两种制约关系两种制约关系同步与互斥同步与互斥第2页/共179页3互斥与同步概念互斥与同步概念（1 1）同步，）同步，也称为直接也称为直接相

2、互制约相互制约，是指某些并发执行的进程为，是指某些并发执行的进程为共同完成一个任务，需要相互合作、协同工作，这些合作的进共同完成一个任务，需要相互合作、协同工作，这些合作的进程都是独立地以不可预知的速度推进，这就需要在一些关键点程都是独立地以不可预知的速度推进，这就需要在一些关键点上互相等待，互通消息。上互相等待，互通消息。第3页/共179页4互斥与同步概念互斥与同步概念（2 2）互斥，）互斥，也称间接相互制约关系，是指也称间接相互制约关系，是指多个进程同时竞争一个需要互斥使用的资源多个进程同时竞争一个需要互斥使用的资源（如打印机等），当该资源已经分配给某个（如打印机等），当该资源已经分配给某

3、个进程使用时，其它进程只能等待，直到该资进程使用时，其它进程只能等待，直到该资源被释放。源被释放。第4页/共179页5互斥与同步概念互斥与同步概念可见，进程的同步是我们需要的，而互斥是可见，进程的同步是我们需要的，而互斥是被迫的。被迫的。为了说明进程的同步，引入一个为了说明进程的同步，引入一个前趋图前趋图的概的概念念第5页/共179页63.1 3.1 前趋图前趋图(Precedence Graph)(Precedence Graph)前趋图前趋图(Precedence Graph)(Precedence Graph)是一个有向无循环是一个有向无循环图，记为图，记为DAG(Directed Ac

4、yclic Graph)DAG(Directed Acyclic Graph)，用，用于描述进程之间执行的于描述进程之间执行的前后关系前后关系。图中的每个图中的每个结点结点可用于描述一个程序段或进程，可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序个结点之间存在的偏序(Partial Order)(Partial Order)或前或前趋关系趋关系第6页/共179页7第7页/共179页8图 3-3 并发执行时的前趋图第8页/共179页9图 3-4 四条语句的前趋关系第9页/共179页103.2进程的同步与互斥进程的同

5、步与互斥进程互斥定义进程互斥定义:所谓进程互斥所谓进程互斥是指当有若干进程都要使用某一共享资源时，是指当有若干进程都要使用某一共享资源时，最多允许一个进程使用，而其他要使用该资源的进程必须等待，最多允许一个进程使用，而其他要使用该资源的进程必须等待，直到占用该资源的进程释放了该资源为止直到占用该资源的进程释放了该资源为止。进程互斥进程互斥是进程之间发生的一种间接性作用，一般是程序不希是进程之间发生的一种间接性作用，一般是程序不希望的。望的。两个进程不能同时进入两个进程不能同时进入临界区临界区，否则就会导致数据的不一致，否则就会导致数据的不一致，产生与时间有关的错误。产生与时间有关的错误。第10

6、页/共179页113.2进程的同步与互斥进程的同步与互斥临界资源定义临界资源定义:操作系统中将一次仅允许一个进程访问的资操作系统中将一次仅允许一个进程访问的资源称为临界资源源称为临界资源,如打印机、共享变量等。如打印机、共享变量等。临界区定义临界区定义:操作系统中把每个进程中访问临界资源的那操作系统中把每个进程中访问临界资源的那段代码段称为段代码段称为临界区。临界区。第11页/共179页123.2进程的同步与互斥进程的同步与互斥如变量如变量N N是是临界资源临界资源，程序，程序A A中有访问中有访问N N的代码：的代码：.X=N;X=N;N+;N+;.上面访问上面访问N N的两句代码就是程序的

7、两句代码就是程序A A的临界区的临界区。第12页/共179页133.2进程的同步与互斥进程的同步与互斥显然，若能保证每个进程互斥地进入显然，若能保证每个进程互斥地进入自己的自己的临界区临界区，便可实现诸进程对临界资源的互斥便可实现诸进程对临界资源的互斥访问访问第13页/共179页14 3.2 3.2 进程同步与互斥进程同步与互斥解决互斥问题应该满足解决互斥问题应该满足互斥和公平互斥和公平两个原则，两个原则，即任意时刻只能允许一个进程处于同一共享变量的临界区，而即任意时刻只能允许一个进程处于同一共享变量的临界区，而且不能让任一进程无限期地等待。且不能让任一进程无限期地等待。第14页/共179页1

8、5进程同步机制的准则进程同步机制的准则:空闲让进：空闲让进：当无进程处于临界区时，必须让一个要求进入它的临界区当无进程处于临界区时，必须让一个要求进入它的临界区的进程立即进入，以提高临界资源的利用率。的进程立即进入，以提高临界资源的利用率。忙则等待：忙则等待：当已有进程处于临界区时，其他试图进入自己临界区的进程当已有进程处于临界区时，其他试图进入自己临界区的进程必须等待，以保证它们互斥地进入临界区。必须等待，以保证它们互斥地进入临界区。让权等待：让权等待：对于等待进入临界区的进程而言，它必须立即释放处理机，对于等待进入临界区的进程而言，它必须立即释放处理机，以避免进程以避免进程 忙等忙等 而降

9、低而降低CPUCPU的效率。的效率。有限等待：有限等待：对要求进入临界区的进程，应在有限时间内进入，以免陷入对要求进入临界区的进程，应在有限时间内进入，以免陷入 死等死等。第15页/共179页163.2进程的同步与互斥（续）进程的同步与互斥（续）进程同步概念进程同步概念:一般来说，一个进程对于其它的进程运行速度是一般来说，一个进程对于其它的进程运行速度是不确定的。但是相互合作的几个进程需要在某不确定的。但是相互合作的几个进程需要在某些确定点上协调它们的工作。些确定点上协调它们的工作。所谓进程同步，所谓进程同步，是指多个相互合作的进程，在一些关键点上可是指多个相互合作的进程，在一些关键点上可能需

10、要互相等待或互相交换信息，这种相互制能需要互相等待或互相交换信息，这种相互制约的关系称为进程同步。约的关系称为进程同步。进程同步进程同步是进程之间直接的相互作用，是合作是进程之间直接的相互作用，是合作进程间有意识的行为。进程间有意识的行为。第16页/共179页173.2 3.2 进程同步与互斥进程同步与互斥进程同步实例进程同步实例1 1：典型的同步例子是公共汽车上司机与售票员的典型的同步例子是公共汽车上司机与售票员的合作合作：只有当售票员关门之后司机才能启动车辆，只有司机停车之后售只有当售票员关门之后司机才能启动车辆，只有司机停车之后售票员才能开车门。票员才能开车门。司机和售票员的行动需要一定

11、的协调。同样地，两个进程之间有时司机和售票员的行动需要一定的协调。同样地，两个进程之间有时也有这样的依赖关系，因此我们也要有一定的同步机制保证它们的执行次也有这样的依赖关系，因此我们也要有一定的同步机制保证它们的执行次序。序。第17页/共179页18 进程同步实例进程同步实例2 2：系统中有两个合作的进程，他们共用一个单缓系统中有两个合作的进程，他们共用一个单缓冲区。这两个进程一个是冲区。这两个进程一个是计算进程计算进程，负责对数负责对数据进行计算；另一个为据进行计算；另一个为打印进程打印进程，负责对计算，负责对计算结果进行打印。结果进行打印。当计算进程没有计算完毕，计算结果没有送到当计算进程

12、没有计算完毕，计算结果没有送到缓冲区的时候，打印进程就不能打印。缓冲区的时候，打印进程就不能打印。一旦计算进程把计算结果送入缓冲区，就应该一旦计算进程把计算结果送入缓冲区，就应该给打印进程发送一个信号，打印进程收到信号给打印进程发送一个信号，打印进程收到信号后就可以从缓冲区中取出计算结果进行打印。后就可以从缓冲区中取出计算结果进行打印。第18页/共179页19 进程同步实例进程同步实例2 2（续）（续）：在在打印进程打印进程尚未把缓冲区中的计算结果取出打印之前，尚未把缓冲区中的计算结果取出打印之前，计算进计算进程程也不能把下一次的计算结果送入缓冲区。也不能把下一次的计算结果送入缓冲区。只有在只

13、有在打印进程打印进程取出缓冲区中的内容，给取出缓冲区中的内容，给计算进程计算进程发一个信号发一个信号后，计算进程才能将下一次的计算结果送入缓冲区。后，计算进程才能将下一次的计算结果送入缓冲区。计算进程和打印进程就是通过这种互相发信号的方式实现同步计算进程和打印进程就是通过这种互相发信号的方式实现同步的。的。第19页/共179页203.3 3.3 信号量和管程信号量和管程本章主要介绍以下两种同步和互斥机制：本章主要介绍以下两种同步和互斥机制：信号量信号量 管程管程第20页/共179页21 3.3 3.3 信号量和管程信号量和管程互斥问题可以用硬件方法，也可以用软件方互斥问题可以用硬件方法，也可以

14、用软件方法解决。法解决。“开关中断开关中断”称为称为硬件锁硬件锁，是最简单的用硬，是最简单的用硬件实现互斥的方法。件实现互斥的方法。第21页/共179页22 3.3 3.3 信号量和管程信号量和管程即在进程进入临界区之前，先执行即在进程进入临界区之前，先执行“关中断关中断”指令，即屏蔽所有中断，在进程执行自己指令，即屏蔽所有中断，在进程执行自己的临界区期间，计算机系统不响应中断，直的临界区期间，计算机系统不响应中断，直到进程完成临界区的执行，才执行到进程完成临界区的执行，才执行“开中断开中断”指令。指令。这样，进程在执行临界区时，会一直占用这样，进程在执行临界区时，会一直占用CPUCPU，使其

15、它进程不能再执行临界区，从而，使其它进程不能再执行临界区，从而有效地保证了临界区的互斥使用，有效地保证了临界区的互斥使用，实现了进实现了进程的互斥。程的互斥。第22页/共179页23 3.3 3.3 信号量和管程信号量和管程用用“开关中断开关中断”指令实现互斥的模板如下：指令实现互斥的模板如下：P1：.关中断；关中断；临界区；临界区；开中断；开中断；第23页/共179页24 3.3 3.3 信号量和管程信号量和管程这种方法虽然简单，但如果关中断的时间过这种方法虽然简单，但如果关中断的时间过长，会导致系统效率下降，甚至如果关中断长，会导致系统效率下降，甚至如果关中断处理不当，还会引起系统无法正常

16、调度，而处理不当，还会引起系统无法正常调度，而且这种方法仅适用于单且这种方法仅适用于单CPUCPU系统。系统。还有其它一些用还有其它一些用硬件硬件进行互斥方法，但都有进行互斥方法，但都有许多缺陷。后来人们用许多缺陷。后来人们用软件方法软件方法解决互斥，解决互斥，取得较好的效果，其中比较常用的有信号量取得较好的效果，其中比较常用的有信号量机制和管程。机制和管程。第24页/共179页25 3.3 3.3 信号量和管程信号量和管程3.3.1 3.3.1 信号量信号量 1.1.信号量及信号量及P P、V V操作操作 2.2.利用信号量实现互斥利用信号量实现互斥 3.3.利用利用P P、V V操作描述前

17、趋关系操作描述前趋关系 4.4.生产者生产者-消费者问题消费者问题 5.5.哲学家就餐问题哲学家就餐问题 6.6.读者读者-写者问题写者问题第25页/共179页26 3.3 3.3 信号量和管程信号量和管程3.3.1 3.3.1 信号信号量量1.1.信号量及信号量及P P、V V操作操作l 信号量是一种有效的用来解决信号量是一种有效的用来解决进程同步与互进程同步与互斥斥问题的机制。问题的机制。l信号量最早是在信号量最早是在19651965年由荷兰学者提出来的。年由荷兰学者提出来的。这种方法是通过使用信号量及有关的这种方法是通过使用信号量及有关的P P、V V操操作原语来实现进程的互斥与同步的。

18、作原语来实现进程的互斥与同步的。l操作又叫操作又叫WaitWait操作，操作，V V操作又叫操作又叫SignalSignal操作操作第26页/共179页273.3 3.3 信号量和管程信号量和管程 3.3.1 3.3.1 信号量信号量l 信号量是一个确定的两元组（信号量是一个确定的两元组（S S，Q Q），其中），其中S S是一个是一个具有非负初值的整型变量具有非负初值的整型变量，Q Q是一个是一个初初始状态为空的队列始状态为空的队列。l 整型变量整型变量S S表示系统中某类资源的数目，当其表示系统中某类资源的数目，当其值大于或等于值大于或等于0 0时，表示系统中当前可用资源时，表示系统中当前

19、可用资源的数目；的数目；l当其值小于当其值小于0 0时，其绝对值表示系统中因请求时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目。该类资源而被阻塞的进程数目。第27页/共179页283.3 3.3 信号量和管程信号量和管程 3.3.1 3.3.1 信号量信号量 除信号量的初值外，信号量的值仅能由除信号量的初值外，信号量的值仅能由P P操作操作（又叫（又叫WaitWait操作）和操作）和V V操作（又称操作（又称SignalSignal操作）操作）来改变。来改变。第28页/共179页293.3 3.3 信号量和管程信号量和管程 3.3.1 3.3.1 信号量信号量一个信号量的建立必须经过说

20、明，即应该准确说明一个信号量的建立必须经过说明，即应该准确说明S S的意义和初的意义和初值（值（注意这个初值不是一个负值注意这个初值不是一个负值）。每个信号量都有一个相应）。每个信号量都有一个相应的队列，在建立信号量时，队列为空。的队列，在建立信号量时，队列为空。P P、V V操作以原语方式实现，信号量的值仅能由这两条原语加以操作以原语方式实现，信号量的值仅能由这两条原语加以改变。改变。P P、V V操作的定义为：操作的定义为：第29页/共179页30 3.3 3.3 信号量和管程信号量和管程 3.3.1 3.3.1 信号量信号量（1 1）P P操作。操作。P P操作记为操作记为P(S)P(S

21、)，其中，其中S S为一个信号量，为一个信号量，它执行时主要完成下述动作：它执行时主要完成下述动作：S=S-1S=S-1；若若S=0S=0则进程继续运行；否则（即则进程继续运行；否则（即S0)S0)阻塞该进程，并将它插入该信号阻塞该进程，并将它插入该信号量的等待队列中。量的等待队列中。第30页/共179页31 3.3 3.3 信号量和管程信号量和管程 3.3.1 3.3.1 信号量信号量（2 2）V V操作。操作。V V操作记为操作记为V V（S S），），S S为一个信号量，它为一个信号量，它执行时主要完成下述动作：执行时主要完成下述动作：S=S+1S=S+1；若若S S大于大于0 0则进程

22、继续执行；则进程继续执行；否则（即否则（即S=0)S0empty 0 empty empty 的值表示可继续进入售票厅的的值表示可继续进入售票厅的人数人数 empty=0empty=0 表示售票厅中已有表示售票厅中已有 20 20 名顾客名顾客 (购购票者票者 )empty 0empty 0)n0)与一群与一群生产者进程生产者进程P1P1、P2P2、PmPm和一群消费者进程和一群消费者进程C1C1、C2C2、CkCk联系起来联系起来。l假定这些消费者和生产者都是等效的。假定这些消费者和生产者都是等效的。l只要缓冲区未满，只要缓冲区未满，生产者生产者就可以把产品送入缓就可以把产品送入缓冲区，类似

23、地，冲区，类似地，l只要缓冲区未空，只要缓冲区未空，消费者消费者就可以从缓冲区中取就可以从缓冲区中取走产品并消费之。走产品并消费之。第82页/共179页83l生产者和消费者的同步关系，将禁止生产者向满的缓冲区输送生产者和消费者的同步关系，将禁止生产者向满的缓冲区输送产品，也禁止消费者从空的缓冲区中提取产品。产品，也禁止消费者从空的缓冲区中提取产品。第83页/共179页84 4.4.生产者生产者-消费者问题消费者问题l为了解决为了解决生产者生产者-消费者问题，消费者问题，应该设置应该设置两个同步信号量两个同步信号量.l一个说明空缓冲单元的数目，用一个说明空缓冲单元的数目，用emptyempty表

24、示，其初值为有界缓冲表示，其初值为有界缓冲区的大小区的大小n n，l另一个说明满缓冲单元的数目，用另一个说明满缓冲单元的数目，用fullfull表示，其初值为表示，其初值为0 0。第84页/共179页85l本例有本例有P1P1、P2P2，PmPm个生产者和个生产者和C1C1、C2C2、CkCk个消费者，它们在生产和消费活动中要对有界个消费者，它们在生产和消费活动中要对有界缓冲区进行操作，缓冲区进行操作，l而有界缓冲区是一个而有界缓冲区是一个临界资源，临界资源，必须互斥使用，必须互斥使用，l因此还需要另外设置一个互斥信号量因此还需要另外设置一个互斥信号量mutexmutex，其，其初值为初值为1

25、 1。l生产者生产者-消费者问题的同步描述如下：消费者问题的同步描述如下：第85页/共179页86semaphore semaphore full=0;full=0;/第一步：第一步：定义信号定义信号量，量，semaphore semaphore empty=n;empty=n;/并为信号量赋初值并为信号量赋初值semaphore semaphore mutex=1;mutex=1;main()main()/第二步：第二步：编写主函编写主函数数，cobegin cobegin /在其中调用各个在其中调用各个进程进程 producer(i);producer(i);/i=1,2,m/i=1,2,

26、m consumer(j);consumer(j);/j=1,2,k/j=1,2,k coend coend 第86页/共179页87/第三步：第三步：编写各个具体的进程，其中加上编写各个具体的进程，其中加上P P、V V操作操作producer(i)producer(i)while(1)while(1)生产一个产品；生产一个产品；p(empty);p(empty);p(mutex);p(mutex);将一个产品送入有界将一个产品送入有界 缓冲区；缓冲区；V(mutex);V(mutex);V(full);V(full);consumer(j)while(1)p(full);p(mutex);

27、从缓冲区中取出一个 产品；V(mutex);V(empty);消费一个产品 第87页/共179页88 4.4.生产者生产者-消费者问题消费者问题注意：无论在生产者进程还是消费者进程中，注意：无论在生产者进程还是消费者进程中，P P操作操作的次序都不的次序都不能颠倒，否则将可能造成死锁。能颠倒，否则将可能造成死锁。练习：思考一下，在上面的例子中，在一个进程中颠倒一下两练习：思考一下，在上面的例子中，在一个进程中颠倒一下两个个P P操作，可能会产生什么样的不利后果？操作，可能会产生什么样的不利后果？第88页/共179页89练习练习6.6.兄弟俩共同使用一个账号，每次限存和兄弟俩共同使用一个账号，每

28、次限存和取取100100元钱。如何用元钱。如何用P P、V V操作来实现两个并发操操作来实现两个并发操作的互斥，以避免账号里的钱数发生错误作的互斥，以避免账号里的钱数发生错误分析：分析：无论存钱还是取钱都要分为无论存钱还是取钱都要分为3 3个步骤：个步骤：（1 1）把账户对应的金额读到一个变量中；）把账户对应的金额读到一个变量中；（2 2）让该变量）让该变量+100+100或或-100-100 （3 3）把该变量的值写回账户中）把该变量的值写回账户中第89页/共179页90 练习练习6 6分析：分析：先存钱和先取钱都不会发生错误，但若两个进程交错使用先存钱和先取钱都不会发生错误，但若两个进程交

29、错使用CPUCPU时就会产生不同的值。时就会产生不同的值。用互斥信号量用互斥信号量mutexmutex来互斥存钱和取钱两个进程对帐户金额来互斥存钱和取钱两个进程对帐户金额amountamount的修改的修改第90页/共179页91 练习练习6 6参考解答：参考解答：Semaphoremutex=1;/表示每次只有一个进程（用户）可以存取该帐户，故可用资源总数为1intamount=0;/假定刚开始帐户里的余额为0；main()cobeginsave();take();coend第91页/共179页92练习练习6 6参考解答：参考解答：take()P(mutex);m2=amount;m2=m2

30、-100;amount=m2;V(mutex);save()P(mutex);m1=amount;m1=m1+100;amount=m1;V(mutex);第92页/共179页93练习练习7 7：（1 1）写出）写出P P、V V操作的定义操作的定义（2 2）三个进程）三个进程PAPA、PBPB、PCPC协作解决文件打印问协作解决文件打印问题：题：PAPA将文件记录从磁盘读入到内存缓冲区将文件记录从磁盘读入到内存缓冲区1 1，每每执行一次读一个记录；执行一次读一个记录；PBPB将缓冲区将缓冲区1 1中的内容复制到缓冲区中的内容复制到缓冲区2 2，每执行每执行一次复制一个记录；一次复制一个记录；

31、PCPC将缓冲区将缓冲区2 2的内容打印出来的内容打印出来，每执行一次打，每执行一次打印一个记录；印一个记录；假定缓冲区的大小和一个记录一样大。请用假定缓冲区的大小和一个记录一样大。请用P P、V V操作来保证文件的正确打印操作来保证文件的正确打印第93页/共179页94本题也是一个典型的生产者本题也是一个典型的生产者-消费者问题，其中的难点消费者问题，其中的难点在于在于PBPB既是一个消费者，又是一个生产者既是一个消费者，又是一个生产者缓冲区1缓冲区2PAPBPC从磁盘读入复制打印第94页/共179页95 练习练习7 7参考解答：参考解答：设置设置4 4个信号量：个信号量：emptyempt

32、y1 1 ：表示缓冲区：表示缓冲区1 1空位数，初值为空位数，初值为1 1；fullfull1 1 ：表示缓冲区：表示缓冲区1 1满记录数，初值为满记录数，初值为0 0 empty empty2 2：表示缓冲区表示缓冲区2 2空位数，初值为空位数，初值为1 1；fullfull2 2：表示缓冲区：表示缓冲区2 2满记录数，初值为满记录数，初值为0 0 第95页/共179页96 练习练习7 7参考解答：参考解答：main()cobeginPA();PB();PC();coend第96页/共179页97 练习练习7 7参考解答：参考解答：PA()PA()while(1)while(1)从磁盘读一个

33、记录；从磁盘读一个记录；P(empty1);P(empty1);将记录存入缓冲区将记录存入缓冲区1 1；V(full1);V(full1);PB()while(1)P(full1);从缓冲区1取出记录；V(empty1);P(empty2);将记录存入缓冲区2；V(full2);第97页/共179页98 练习练习7 7参考解答：参考解答：PC()PC()while(1)while(1)P(full2);P(full2);从缓冲区从缓冲区2 2取出记录；取出记录；V(empty2);V(empty2);打印记录；打印记录；第98页/共179页99练习8.桌上有一个盘子，只能存放一个水果。父亲总是

34、放苹果到盘子中，而母亲总是放香蕉到盘子中；一个女儿专等吃盘中的苹果，一个儿子专等吃盘中的香蕉。请用信号量机制解决该问题。分析：分析：l在本题中，爸爸、妈妈、儿子、女儿共用一个在本题中，爸爸、妈妈、儿子、女儿共用一个盘子，且盘子每次只能放一个水果；盘子，且盘子每次只能放一个水果；l当盘子为空时，爸爸可以放入苹果，当盘子为空时，爸爸可以放入苹果，或或妈妈可妈妈可以放入香蕉；以放入香蕉；l若放入盘中的是苹果，则允许女儿吃，若放入若放入盘中的是苹果，则允许女儿吃，若放入盘中的是香蕉，则允许儿子吃。盘中的是香蕉，则允许儿子吃。第99页/共179页100 练习题练习题8 8分析：分析：本题实际上是生产者本

35、题实际上是生产者消费者问题的一种消费者问题的一种变形。变形。这里生产者有两类爸爸和妈妈；这里生产者有两类爸爸和妈妈；每类生产者只生产其中固定的一类产品：爸每类生产者只生产其中固定的一类产品：爸爸放苹果，妈妈放香蕉；爸放苹果，妈妈放香蕉；消费者也有两类儿子和女儿；消费者也有两类儿子和女儿；每类消费者只消费其中固定的一类产品每类消费者只消费其中固定的一类产品:儿儿子消费香蕉，女儿消费苹果。子消费香蕉，女儿消费苹果。第100页/共179页101 练习题练习题8 8参考解答：参考解答：爸爸、妈妈、儿子、女儿的四个进程都是随爸爸、妈妈、儿子、女儿的四个进程都是随机地并发执行自己的循环操作；机地并发执行自

36、己的循环操作；但爸爸妈妈放水果前，要先看看盘子是否为但爸爸妈妈放水果前，要先看看盘子是否为空，空，若为空则放入自己的水果，若不空则等若为空则放入自己的水果，若不空则等待（阻塞）；待（阻塞）；第101页/共179页102儿子拿水果前，要先看看盘中有无香蕉，儿子拿水果前，要先看看盘中有无香蕉，有有则拿来吃，没有则等待（阻塞）；则拿来吃，没有则等待（阻塞）；女儿拿水果前要先看看盘中有无苹果，女儿拿水果前要先看看盘中有无苹果，有则有则拿来吃，没有则等待（阻塞）。拿来吃，没有则等待（阻塞）。第102页/共179页103练习题练习题8 8参考解答：参考解答：本题设置三个信号量：本题设置三个信号量：l爸爸妈

37、妈要用到的表示爸爸妈妈要用到的表示盘子是否有空位盘子是否有空位的的信号量信号量S SEmptyEmpty，l 因最多只有一个空位（可放一个水果），因最多只有一个空位（可放一个水果），所以初值为所以初值为1 1，表示开始时盘子有一个空，表示开始时盘子有一个空位；位；第103页/共179页104l女儿吃水果前要看看盘中有没有苹果，用信号量女儿吃水果前要看看盘中有没有苹果，用信号量S SAppleApple 表示盘中可用的苹果个数，表示盘中可用的苹果个数，l初值设为初值设为0 0，表示开始时没有苹果在盘中；，表示开始时没有苹果在盘中；l儿子吃水果前要先看看盘中有无香蕉，用信号量儿子吃水果前要先看看盘

38、中有无香蕉，用信号量S SBananaBanana表示盘中香蕉的个数。表示盘中香蕉的个数。l初值设为初值设为0 0，表示开始时没有香蕉在盘中；，表示开始时没有香蕉在盘中；第104页/共179页105练习题练习题8 8参考解答：参考解答：SemaphoreSEmpty Empty=1；SemaphoreSApple Apple=0；SemaphoreSBanana Banana=0；main()Cobeginfather();mather();son();doughterCoend第105页/共179页106 Father()Father()while(1)while(1)P(S P(SEmpt

39、yEmpty););把一只苹果放入盘把一只苹果放入盘 中；中；V(SV(SAppleApple););Mather()while(1)P(Empty);把一只桔子放 入盘中；V(Banana);第106页/共179页107SonSon（）while(1)while(1)P(P(BananaBanana）；从盘中拿桔子吃；从盘中拿桔子吃；V(SV(SEmptyEmpty););Daughter（）while(1)P(SApple)；从盘中拿苹果吃；V(SEmpty)第107页/共179页1085.5.哲学家就餐问题哲学家就餐问题DijkstraDijkstra于于19651965年首先提出并解决

40、了哲学家就年首先提出并解决了哲学家就餐问题。餐问题。该问题是大量该问题是大量并发控制问题并发控制问题中的一个典型的同中的一个典型的同步例子步例子。第108页/共179页109 5.5.哲学家就餐问题哲学家就餐问题哲学家就餐问题描述如下：哲学家就餐问题描述如下：5 5个哲学家倾注毕生个哲学家倾注毕生精力用于思考和吃饭。精力用于思考和吃饭。他们坐在一张放有他们坐在一张放有5 5把椅子的圆桌旁，每人独占把椅子的圆桌旁，每人独占一把椅子。一把椅子。圆桌中间放置食品，桌上放着圆桌中间放置食品，桌上放着5 5根筷子根筷子，每个哲，每个哲学家的左右各有一只筷子。学家的左右各有一只筷子。第109页/共179页

41、110 5.5.哲学家就餐问题哲学家就餐问题哲学家只做哲学家只做2 2件事：思考和吃饭件事：思考和吃饭哲学家思考时并不影响他人，只有当哲学家饥饿的时候，他才试图拿起左哲学家思考时并不影响他人，只有当哲学家饥饿的时候，他才试图拿起左右两根筷子（一根一根拿起）。右两根筷子（一根一根拿起）。第110页/共179页111如果筷子已在他人手中，则需要等待。如果筷子已在他人手中，则需要等待。饥饿的哲学家只有同时拿起了两根筷子后才可以开始吃饭。饥饿的哲学家只有同时拿起了两根筷子后才可以开始吃饭。吃完饭后才放下筷子，重新开始思考。吃完饭后才放下筷子，重新开始思考。第111页/共179页112分析：分析：放在桌

42、子上的筷子是放在桌子上的筷子是临界资源，临界资源，在一段时间在一段时间内只允许一位哲学家使用。内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以为了实现对筷子的互斥使用，可以用一个信用一个信号量表示一只筷子号量表示一只筷子，由这由这5 5个信号量构成信号量数组。个信号量构成信号量数组。第112页/共179页113进行同步的解决方案如下：进行同步的解决方案如下：semaphore chopstick5semaphore chopstick5；/假定数组从下标假定数组从下标0 0开始：开始：所有信号量都被初始化为所有信号量都被初始化为1 1，即，即chopstick0=chopstick1=c

43、hopstick2=chopstick0=chopstick1=chopstick2=chopstick3=chopstick4=1chopstick3=chopstick4=1；第113页/共179页114为了同步，第为了同步，第i i位哲学家的活动位哲学家的活动PiPi可描述为：可描述为：while(1)P(chopstici);P(chopstic(i+1)mod5);eatint;V(chopstici);V(chopstic(i+1)mod5);thinking;第114页/共179页1155.5.哲学家就餐问题哲学家就餐问题虽然上述解法可保证不会有两个相邻的哲学虽然上述解法可保证不

44、会有两个相邻的哲学家同时就餐，但有可能会引起死锁。家同时就餐，但有可能会引起死锁。假如假如5 5位哲学家同时饥饿而拿起左边的筷子位哲学家同时饥饿而拿起左边的筷子时，就会使时，就会使5 5个信号量个信号量chopstickchopstick均为均为0 0；当；当他们试图拿右边的筷子时，都将因无筷子可他们试图拿右边的筷子时，都将因无筷子可拿而无限期地等待。拿而无限期地等待。对于这样的死锁问题，可采用以下几种解决对于这样的死锁问题，可采用以下几种解决方法：方法：第115页/共179页116 5.5.哲学家就餐问题哲学家就餐问题（1 1）至多只允许有至多只允许有4 4位哲学家同时去拿左边的筷位哲学家同

45、时去拿左边的筷子，最终能保证至少有一位哲学家能就餐，用子，最终能保证至少有一位哲学家能就餐，用毕后能释放两只筷子，从而使更多的哲学家就毕后能释放两只筷子，从而使更多的哲学家就餐。餐。（2 2）仅当哲学家的左右两只筷子均可用时，才仅当哲学家的左右两只筷子均可用时，才允许他拿起筷子就餐。允许他拿起筷子就餐。第116页/共179页117 5.5.哲学家就餐问题哲学家就餐问题（3 3）规定奇数号哲学家先拿他左边的筷子，然后再拿他右边的筷子；规定奇数号哲学家先拿他左边的筷子，然后再拿他右边的筷子；偶数号哲学家则正相反。偶数号哲学家则正相反。按此规定，将是按此规定，将是1 1、2 2号哲学家竞争号哲学家竞

46、争1 1号筷子；号筷子；3 3、4 4号哲学家竞争号哲学家竞争3 3号筷子。即号筷子。即5 5位哲学家都先竞争奇数号筷子，获得后，再去竞位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总有一位哲学家能获得两只筷子而就餐。争偶数号筷子，最后总有一位哲学家能获得两只筷子而就餐。第117页/共179页118 6.6.读者读者-写者问题写者问题l读者读者-写者问题是写者问题是19711971年由年由CourtoisCourtois提出的提出的一个经典的同步问题。一个经典的同步问题。l该问题可描述为：两组并发进程共享一个数该问题可描述为：两组并发进程共享一个数据文件据文件;l其中，一组进程只

47、要求读该文件，称为读者其中，一组进程只要求读该文件，称为读者进程（进程（ReaderReader），另一组进程只要求写该文），另一组进程只要求写该文件，称为写者进程（件，称为写者进程（WriterWriter）。）。第118页/共179页119 6.6.读者读者-写者问题写者问题l该问题还要求：该问题还要求：（1 1）允许多个读者进程同时对该文件执行）允许多个读者进程同时对该文件执行读操作；读操作；（2 2）不允许读者进程和写者进程同时对该）不允许读者进程和写者进程同时对该文件进行操作，即读者和写者要互斥；文件进行操作，即读者和写者要互斥；（3 3）不允许多个写者同时对文件进行）不允许多个写者

48、同时对文件进行“写写”操作，即写者与写者之间要互斥操作，即写者与写者之间要互斥第119页/共179页120 分析：分析：为满足要求为满足要求(1)(1)几个读者可以同时读同一个几个读者可以同时读同一个文件的要求，要设置一个信号量文件的要求，要设置一个信号量RcountRcount，表示表示正在读文件的进程个数，初值设为正在读文件的进程个数，初值设为0 0。当一个读者进程要读该文件的时候，要先对当一个读者进程要读该文件的时候，要先对RcountRcount进行操作，让进行操作，让RcountRcount的值加的值加1 1；当一个进；当一个进程读完该文件的时候，也要对程读完该文件的时候，也要对Rc

49、ountRcount进行操作，进行操作，让让RcountRcount减减1 1；第120页/共179页121但是注意：但是注意：RcountRcount是可被多个读者进程访问的是可被多个读者进程访问的临界资源临界资源，应为它设置一个互斥信号量，应为它设置一个互斥信号量RmutexRmutex，初值设为初值设为1 1；第121页/共179页122 分析：分析：为满足要求为满足要求（2 2）：）：“读者与写者保持互斥读者与写者保持互斥”以及满足要求以及满足要求（3 3）：）：“写者与写者保持互斥写者与写者保持互斥”，要再设一个互斥信号量要再设一个互斥信号量WmutexWmutex，这是一个和写有关

50、的信号量，初值设为这是一个和写有关的信号量，初值设为1 1，Wmutex=1Wmutex=1第122页/共179页123即：为了解决读写之间的同步，应设两个信号量为了解决读写之间的同步，应设两个信号量和一个共享变量：和一个共享变量：读互斥信号量读互斥信号量RmutexRmutex，用于使读进程互斥地用于使读进程互斥地访问共享变量访问共享变量RcountRcount，初值为初值为1 1；写互斥信号量写互斥信号量WmutexWmutex，用于实现写进程与写用于实现写进程与写进程、写进程与读进程之间的互斥，初值为进程、写进程与读进程之间的互斥，初值为1 1；共享变量共享变量RcountRcount，