第3章 并发控制-互斥及同步

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

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

3、程使用时，等），当该资源已经分配给某个进程使用时，其它进程只能等待，直到该资源被释放。其它进程只能等待，直到该资源被释放。6 互斥与同步概念互斥与同步概念n可见，进程的同步是我们需要的，而互斥是可见，进程的同步是我们需要的，而互斥是被迫的。被迫的。n为了说明进程的同步，引入一个为了说明进程的同步，引入一个前趋图前趋图的概的概念念73.1 3.1 前趋图前趋图(Precedence Graph)(Precedence Graph)n前趋图前趋图(Precedence Graph)(Precedence Graph)是一个有向无循是一个有向无循环图，记为环图，记为DAG(Directed Acyc

4、lic Graph)DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。用于描述进程之间执行的前后关系。n图中的每个图中的每个结点结点可用于描述一个程序段或进可用于描述一个程序段或进程，乃至一条语句；程，乃至一条语句；n结点间的有向边则用于表示两个结点之间存结点间的有向边则用于表示两个结点之间存在的偏序在的偏序(Partial Order)(Partial Order)或前趋关系或前趋关系8P1P3P8P9P4P2P5P6P7S1S2S3(a) 具有九个结点的前趋图(b) 具有循环的前趋图9P1P2P3P4I1I2I3I4C1C2C3C4图图 3-3 并发执

5、行时的前趋图并发执行时的前趋图10S1S2S3S4图图 3-4 四条语句的前趋关系四条语句的前趋关系11 3.2 进程的同步与互斥进程的同步与互斥进程互斥定义进程互斥定义: : n 所谓所谓进程互斥进程互斥是指当有若干进程都要使用是指当有若干进程都要使用某一共享资源时，最多允许一个进程使用，某一共享资源时，最多允许一个进程使用，n而其他要使用该资源的进程必须等待，直到占而其他要使用该资源的进程必须等待，直到占用该资源的进程释放了该资源为止。用该资源的进程释放了该资源为止。12n进程互斥进程互斥是进程之间发生的一种间接性作用，是进程之间发生的一种间接性作用，一般是程序不希望的。一般是程序不希望的

6、。n两个进程不能同时进入两个进程不能同时进入临界区临界区，否则就会导致否则就会导致数据的不一致，产生与时间有关的错误。数据的不一致，产生与时间有关的错误。133.2 进程的同步与互斥进程的同步与互斥n临界资源定义临界资源定义: :操作系统中将一次仅允许一个进程访问的资源操作系统中将一次仅允许一个进程访问的资源称为临界资源称为临界资源, ,如打印机、共享变量等。如打印机、共享变量等。n临界区定义临界区定义: :操作系统中把每个进程中访问临界资源的那段操作系统中把每个进程中访问临界资源的那段代码段称为代码段称为临界区。临界区。14 3.2 进程的同步与互斥进程的同步与互斥n如变量如变量N N是是临

7、界资源临界资源，程序，程序A A中有访问中有访问N N的代码：的代码： . X=N; X=N; N+; N+; . . 上面访问上面访问N N的两句代码就是程序的两句代码就是程序A A的临界区的临界区。15 3.2 进程的同步与互斥进程的同步与互斥n显然，若能保证每个进程互斥地进入显然，若能保证每个进程互斥地进入自己的自己的临界区临界区，便可实现诸进程对临界资源的互斥，便可实现诸进程对临界资源的互斥访问访问16 3.2 3.2 进程同步与互斥进程同步与互斥n解决互斥问题应该满足解决互斥问题应该满足互斥和公平互斥和公平两个原则两个原则n即任意时刻只能允许一个进程处于同一共享即任意时刻只能允许一个

8、进程处于同一共享变量的临界区，而且不能让任一进程无限期变量的临界区，而且不能让任一进程无限期地等待。地等待。17 进程同步机制的准则进程同步机制的准则: : 空闲让进：空闲让进：当无进程处于临界区时，必须让一当无进程处于临界区时，必须让一个要求进入它的临界区的进程立即进入，以提高个要求进入它的临界区的进程立即进入，以提高临界资源的利用率。临界资源的利用率。忙则等待：忙则等待：当已有进程处于临界区时，其他试当已有进程处于临界区时，其他试图进入自己临界区的进程必须等待，以保证它们图进入自己临界区的进程必须等待，以保证它们互斥地进入临界区。互斥地进入临界区。让权等待：让权等待：对于等待进入临界区的进

9、程而言，对于等待进入临界区的进程而言，它必须立即释放处理机，以避免进程它必须立即释放处理机，以避免进程 忙等忙等 而降而降低低CPUCPU的效率。的效率。有限等待：有限等待：对要求进入临界区的对要求进入临界区的进程，应在有进程，应在有限时间内进入，以免陷入限时间内进入，以免陷入 死等死等 。183.2 进程的同步与互斥（续）进程的同步与互斥（续）n进程同步概念进程同步概念: :一般来说，一个进程对于其它的进程运行速一般来说，一个进程对于其它的进程运行速度是不确定的。但是相互合作的几个进程度是不确定的。但是相互合作的几个进程需要在某些确定点上协调它们的工作。需要在某些确定点上协调它们的工作。所所

10、谓进程同步，谓进程同步，是指多个相互合作的进程，是指多个相互合作的进程，在一些关键点上可能需要互相等待或互相在一些关键点上可能需要互相等待或互相交换信息，这种相互制约的关系称为进程交换信息，这种相互制约的关系称为进程同步。同步。n进程同步进程同步是进程之间直接的相互作用，是是进程之间直接的相互作用，是合作进程间有意识的行为。合作进程间有意识的行为。193.2 3.2 进程同步与互斥进程同步与互斥进程同步实例进程同步实例1 1：典型的同步例子是公共汽车上典型的同步例子是公共汽车上司机与售票员的合作司机与售票员的合作：l只有当只有当售票员售票员关门之后关门之后司机司机才能启动车辆，只有才能启动车辆

11、，只有司司机机停车之后停车之后售票员售票员才能开车门。才能开车门。l 司机和售票员的行动需要一定的协调。司机和售票员的行动需要一定的协调。l同样地，两个进程之间有时也有这样的依赖关系，同样地，两个进程之间有时也有这样的依赖关系，因此我们也要有一定的同步机制保证它们的执行次因此我们也要有一定的同步机制保证它们的执行次序。序。 20 进程同步实例进程同步实例2 2：l系统中有两个合作的进程，他们共用一个单系统中有两个合作的进程，他们共用一个单缓冲区。这两个进程一个是缓冲区。这两个进程一个是计算进程计算进程，负责负责对数据进行计算；对数据进行计算；l另一个为另一个为打印进程打印进程，负责对计算结果进

12、行打，负责对计算结果进行打印。印。l当当计算进程计算进程没有计算完毕，计算结果没有送没有计算完毕，计算结果没有送到缓冲区的时候，到缓冲区的时候，打印进程打印进程就不能打印。就不能打印。21l一旦一旦计算进程计算进程把计算结果送入缓冲区，就应把计算结果送入缓冲区，就应该给该给打印进程打印进程发送一个信号发送一个信号; ;l打印进程打印进程收到信号后就可以从缓冲区中取出收到信号后就可以从缓冲区中取出计算结果进行打印。计算结果进行打印。22进程同步实例进程同步实例2 2（续）（续）：l在在打印进程打印进程尚未把缓冲区中的计算结果取出尚未把缓冲区中的计算结果取出打印之前，打印之前，计算进程计算进程也不

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

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

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

16、仅适用于度，而且这种方法仅适用于单单CPUCPU系统。系统。29l还有其它一些用还有其它一些用硬件硬件进行互斥方法，但都有进行互斥方法，但都有许多缺陷。许多缺陷。l后来人们用后来人们用软件方法软件方法解决互斥，取得较好的解决互斥，取得较好的效果，其中比较常用的有效果，其中比较常用的有信号量机制信号量机制和和管程。管程。30 3.3 3.3 信号量信号量 1. 1.信号量及信号量及P P、V V操作操作 2.2.利用信号量实现互斥利用信号量实现互斥 3.3.利用利用P P、V V操作描述前趋关系操作描述前趋关系 4.4.生产者生产者- -消费者问题消费者问题 5.5.哲学家就餐问题哲学家就餐问题

17、 6.6.读者读者- -写者问题写者问题31 3.3 3.3 信号量信号量1.1.信号量及信号量及P P、V V操作操作l 信号量是一种用来有效地解决信号量是一种用来有效地解决进程同步与互进程同步与互斥斥问题的机制。问题的机制。l信号量最早是在信号量最早是在19651965年由荷兰学者年由荷兰学者E.W.DijkstraE.W.Dijkstra提出来的。提出来的。l这种方法是通过使用信号量及有关的这种方法是通过使用信号量及有关的P P、V V操作操作原语来实现进程的互斥与同步的。原语来实现进程的互斥与同步的。32lP P操作又叫操作又叫WaitWait操作，操作，V V操作又叫操作又叫Sign

18、alSignal操作操作33 3.3 3.3 信号量信号量l 信号量是一个确定的两元组（信号量是一个确定的两元组（S S，Q Q），其），其中中S S是一个是一个具有非负初值的整型变量具有非负初值的整型变量，Q Q是一是一个个初始状态为空的队列初始状态为空的队列。l 整型变量整型变量S S表示系统中某类资源的数目，当表示系统中某类资源的数目，当其值大于或等于其值大于或等于0 0时，表示系统中当前可用时，表示系统中当前可用资源的数目；资源的数目；34 3.3 3.3 信号量信号量l当当S S值小于值小于0 0时，其绝对值表示系统中因请求时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目。该类

19、资源而被阻塞的进程数目。l除信号量的初值外，信号量的值仅能由除信号量的初值外，信号量的值仅能由P P操作操作（又叫（又叫WaitWait操作）和操作）和V V操作（又称操作（又称SignalSignal操作）操作）来改变。来改变。353.3 3.3 信号量信号量l一个信号量的建立必须经过说明，即应该准一个信号量的建立必须经过说明，即应该准确说明确说明S S的意义和初值的意义和初值（注意这个初值不是一注意这个初值不是一个负值个负值）。）。l每个信号量都有一个相应的队列，在建立信每个信号量都有一个相应的队列，在建立信号量时，队列为空。号量时，队列为空。lP P、V V操作以原语方式实现，信号量的值

20、仅能操作以原语方式实现，信号量的值仅能由这两条原语加以改变。由这两条原语加以改变。P P、V V操作的定义为：操作的定义为：363.3 3.3 信号量信号量（1 1）P P操作。操作。 P P操作记为操作记为P(S)P(S)，其中，其中S S为一个信号量，为一个信号量，它执行时主要完成下述动作：它执行时主要完成下述动作：n S=S-1S=S-1；n 若若S=0S=0则进程继续运行；则进程继续运行；n否则（即否则（即S0)S0)阻塞该进程，并将它插入阻塞该进程，并将它插入该信号量的等待队列中。该信号量的等待队列中。37 3.3 3.3 信号量信号量（2 2）V V操作。操作。 V V操作记为操作

21、记为V V（S S），），S S为一个信号量，它执行时为一个信号量，它执行时主要完成下述动作：主要完成下述动作：n S=S+1S=S+1；n 若若S S大于大于0 0则进程继续执行；则进程继续执行；n否则（即否则（即S=0)S0empty 0 empty empty 的值表示可继续进入售票厅的值表示可继续进入售票厅的人数的人数 empty =0empty =0 表示售票厅中已有表示售票厅中已有 20 20 名顾客名顾客 ( ( 购票者购票者 ) ) empty 0empty 0)n0)与与一群生产者进程一群生产者进程P1P1、P2P2、PmPm和一群消费和一群消费者进程者进程C1C1、C2C2

22、、CkCk联系起来联系起来。l假定这些消费者和生产者都是等效的。假定这些消费者和生产者都是等效的。l只要缓冲区未满，只要缓冲区未满，生产者生产者就可以把产品送入就可以把产品送入缓冲区；缓冲区；l类似地，只要缓冲区不是全空，类似地，只要缓冲区不是全空，消费者消费者就可就可以从缓冲区中取走产品并消费之。以从缓冲区中取走产品并消费之。94l生产者和消费者的生产者和消费者的同步关系同步关系，将禁止生产者，将禁止生产者向满的缓冲区输送产品；向满的缓冲区输送产品；l也禁止消费者从空的缓冲区中提取产品。也禁止消费者从空的缓冲区中提取产品。95 4.4.生产者生产者- -消费者问题消费者问题l 为了解决为了解

23、决生产者生产者- -消费者问题，消费者问题，应该设置应该设置两个同两个同步信号量步信号量. .l一个说明空缓冲单元的数目，用一个说明空缓冲单元的数目，用emptyempty表示，其初表示，其初值为有值为有界缓冲区的大小界缓冲区的大小n n，l另一个说明满缓冲单元的数目，用另一个说明满缓冲单元的数目，用fullfull表示，其表示，其初值为初值为0 0。96l本例有本例有P1P1、P2P2，PmPm个生产者和个生产者和C1C1、C2C2、CkCk个消费者，它们在生产和消费活动中要对有界个消费者，它们在生产和消费活动中要对有界缓冲区进行操作，缓冲区进行操作，l而有界缓冲区是一个而有界缓冲区是一个临

24、界资源，临界资源，必须互斥使用，必须互斥使用，l因此还需要另外设置一个互斥信号量因此还需要另外设置一个互斥信号量mutexmutex，其初值为其初值为1 1。l生产者生产者- -消费者问题的同步描述如下：消费者问题的同步描述如下：97semaphore semaphore full=0; full=0; /第一步：第一步：定义信号量，定义信号量，semaphore semaphore empty=n;empty=n; /并为信号量赋初值并为信号量赋初值semaphore semaphore mutex=1;mutex=1; main( ) main( ) / / 第二步：第二步：编写主函数编写

25、主函数， cobegin cobegin /在其中调用各个进程在其中调用各个进程 produceri ( ); produceri ( ); /i=1,2,m/i=1,2,m consumerj ( ); consumerj ( ); /j=1,2,k/j=1,2,k coend coend 98/第三步：第三步：编写各个具体的进程，其中加上编写各个具体的进程，其中加上P P、V V操作操作producer i( )producer i( ) while (1) while (1) 生产一个产品；生产一个产品； p(empty) ;p(empty) ; p(mutex); p(mutex);

26、将一个产品送入有界将一个产品送入有界 缓冲区；缓冲区； V(mutex);V(mutex); V(full); V(full); consumer consumer j( )( ) while (1) while (1) p(full) ; p(full) ; p(mutex); p(mutex); 从缓冲区中取出一个从缓冲区中取出一个 产品；产品； V(mutex);V(mutex); V(empty); V(empty); 消费一个产品消费一个产品 99 4.4.生产者生产者- -消费者问题消费者问题n注意：无论在生产者进程还是消费者进程注意：无论在生产者进程还是消费者进程中，中，P P操

27、作操作的次序都不能颠倒，否则将可能的次序都不能颠倒，否则将可能造成死锁。造成死锁。n练习：思考一下，在上面的例子中，在一练习：思考一下，在上面的例子中，在一个进程中颠倒一下两个个进程中颠倒一下两个P P操作，可能会产生操作，可能会产生什么样的不利后果？什么样的不利后果？100练习练习6.6.兄弟俩共同使用一个账号，每次限存和取兄弟俩共同使用一个账号，每次限存和取100100元钱。如何用元钱。如何用P P、V V操作来实现两个并发操作的操作来实现两个并发操作的互斥，以避免账号里的钱数发生错误互斥，以避免账号里的钱数发生错误n分析：分析：无论存钱还是取钱都要分为无论存钱还是取钱都要分为3 3个步骤

28、：个步骤： （1 1）把账户对应的金额读到一个变量中；）把账户对应的金额读到一个变量中； （2 2）让该变量）让该变量+100+100或或-100-100 （3 3）把该变量的值写回账户中）把该变量的值写回账户中101 练习练习6 6分析：分析：n先存钱和先取钱都不会发生错误，但若两个先存钱和先取钱都不会发生错误，但若两个进程交错使用进程交错使用CPUCPU时就会产生不同的值。时就会产生不同的值。n用互斥信号量用互斥信号量mutexmutex来互斥存钱和取钱两个来互斥存钱和取钱两个进程对帐户金额进程对帐户金额amountamount的修改的修改102 练习练习6 6参考解答：参考解答：Sema

29、phore mutex=1; / / 表示每次只有一表示每次只有一个进程（用户）可以存取该帐户，故可用个进程（用户）可以存取该帐户，故可用资源总数为资源总数为1 1int amount=0; /假定刚开始帐户里的余额假定刚开始帐户里的余额为为0； main( ) cobegin save( ); take ( ); coend103练习练习6 6参考解答：参考解答：take( ) P(mutex); m2=amount; m2=m2-100; amount=m2; V(mutex);save( ) P(mutex); m1=amount; m1=m1+100; amount=m1; V(mut

30、ex);104练习练习7 7：（1 1）写出）写出P P、V V操作的定义操作的定义（2 2）三个进程）三个进程PAPA、PBPB、PCPC协作解决文件打印问题：协作解决文件打印问题： PAPA将文件记录从磁盘读入到内存缓冲区将文件记录从磁盘读入到内存缓冲区1 1，每执每执行一次读一个记录；行一次读一个记录； PBPB将缓冲区将缓冲区1 1中的内容复制到缓冲区中的内容复制到缓冲区2 2，每执行一每执行一次复制一个记录；次复制一个记录； PCPC将缓冲区将缓冲区2 2的内容打印出来的内容打印出来，每执行一次打印，每执行一次打印一个记录；一个记录；假定缓冲区的大小和一个记录一样大。请用假定缓冲区的

31、大小和一个记录一样大。请用P P、V V操操作来保证文件的正确打印作来保证文件的正确打印105本题也是一个典型的生产者本题也是一个典型的生产者- -消费者问题，其中的难点在于消费者问题，其中的难点在于PBPB既是一个消费者，又是一个生产者既是一个消费者，又是一个生产者缓冲区1缓冲区2PAPBPC从磁盘读入从磁盘读入复制复制打印打印106 练习练习7 7参考解答：参考解答：n设置设置4 4个信号量：个信号量： empty1 empty1 ：表示缓冲区：表示缓冲区1 1空位数，初值为空位数，初值为1 1； full1 full1 ：表示缓冲区：表示缓冲区1 1满记录数，初值为满记录数，初值为0 0

32、 empty2 empty2： 表示缓冲区表示缓冲区2 2空位数，初值为空位数，初值为1 1； full2full2：表示缓冲区：表示缓冲区2 2满记录数，初值为满记录数，初值为0 0 107 练习练习7 7参考解答：参考解答：main( ) cobegin PA( ); PB( ); PC( ); coend108 练习练习7 7参考解答：参考解答：PA( )PA( ) while(1) while(1) 从磁盘读一个记录；从磁盘读一个记录； P(emptyP(empty1 1);); 将记录存入缓冲区将记录存入缓冲区1 1； V(fullV(full1 1);); PB( )PB( ) w

33、hile(1) while(1) P(fullP(full1 1);); 从缓冲区从缓冲区1 1取出记录；取出记录； V(empty1);V(empty1); P(empty2); P(empty2); 将记录存入缓冲区将记录存入缓冲区2 2； V(fullV(full2 2);); 109 练习练习7 7参考解答：参考解答： PC( ) PC( ) while(1) while(1) P(full2);P(full2); 从缓冲区从缓冲区2 2取出记录；取出记录； V(empty2);V(empty2); 打印记录；打印记录； 110n练习练习8.8. l桌上有一个盘子，只能存放一个水果。桌

34、上有一个盘子，只能存放一个水果。l父亲总是放苹果到盘子中，而母亲总是放香蕉父亲总是放苹果到盘子中，而母亲总是放香蕉到盘子中；到盘子中；l一个女儿专等吃盘中的苹果，一个儿子专等吃一个女儿专等吃盘中的苹果，一个儿子专等吃盘中的香蕉盘中的香蕉。 请用信号量机制解决该问题。请用信号量机制解决该问题。111分析：分析：l在本题中，爸爸、妈妈、儿子、女儿共用一个在本题中，爸爸、妈妈、儿子、女儿共用一个盘子，且盘子每次只能放一个水果；盘子，且盘子每次只能放一个水果；l当盘子为空时，爸爸可以放入苹果，当盘子为空时，爸爸可以放入苹果，或或妈妈可妈妈可以放入香蕉；以放入香蕉；l若放入盘中的是苹果，则允许女儿吃，若

35、放入若放入盘中的是苹果，则允许女儿吃，若放入盘中的是香蕉，则允许儿子吃盘中的是香蕉，则允许儿子吃。112 练习题练习题8 8分析：分析：n本题实际上是生产者本题实际上是生产者消费者问题的一种消费者问题的一种变形。变形。n这里生产者有两类：爸爸和妈妈；这里生产者有两类：爸爸和妈妈；n每类生产者只生产其中固定的一类产品：爸每类生产者只生产其中固定的一类产品：爸爸放苹果，妈妈放香蕉；爸放苹果，妈妈放香蕉；n消费者也有两类：儿子和女儿；消费者也有两类：儿子和女儿；n每类消费者只消费其中固定的一类产品每类消费者只消费其中固定的一类产品: :儿子儿子消费香蕉，女儿消费苹果。消费香蕉，女儿消费苹果。113

36、练习题练习题8 8参考解答：参考解答：n爸爸、妈妈、儿子、女儿的四个进程都是随爸爸、妈妈、儿子、女儿的四个进程都是随机地并发执行自己的循环操作；机地并发执行自己的循环操作；n爸爸妈妈总是不停地放水果，但爸爸妈妈放爸爸妈妈总是不停地放水果，但爸爸妈妈放水果前，要先看看盘子是否为空，水果前，要先看看盘子是否为空，若为空则若为空则放入自己的水果，若不空则等待（阻塞）；放入自己的水果，若不空则等待（阻塞）；114n儿子则不停地拿水果吃。但儿子拿水果前，儿子则不停地拿水果吃。但儿子拿水果前，要先看看盘中有无香蕉，要先看看盘中有无香蕉，有则拿来吃，没有有则拿来吃，没有则等待（阻塞）；则等待（阻塞）；n女儿

37、不停地拿苹果吃。但女儿拿水果前要先女儿不停地拿苹果吃。但女儿拿水果前要先看看盘中有无苹果，看看盘中有无苹果，有则拿来吃，没有则等有则拿来吃，没有则等待（阻塞）。待（阻塞）。115练习题练习题8 8参考解答：参考解答：本题设置三个信号量：本题设置三个信号量：l爸爸妈妈要用到的表示爸爸妈妈要用到的表示盘盘子是否有空位子是否有空位的信的信号量号量S SEmptyEmpty， 或盘子的空位数或盘子的空位数emptyempty；l 因最多只有一个空位（可放一个水果），因最多只有一个空位（可放一个水果），所以初值为所以初值为1 1，表示开始时盘子是空的，盘，表示开始时盘子是空的，盘子有一个空位可用；子有一

38、个空位可用；116l女儿吃水果前要看看盘中有没有苹果，用信号量女儿吃水果前要看看盘中有没有苹果，用信号量S SAppleApple 表示盘中可用的苹果个数，表示盘中可用的苹果个数，l初值设为初值设为0 0，表示开始时没有苹果在盘中；，表示开始时没有苹果在盘中；l儿子吃水果前要先看看盘中有无香蕉，用信号量儿子吃水果前要先看看盘中有无香蕉，用信号量S SBananaBanana表示盘中香蕉的个数。表示盘中香蕉的个数。l初值设为初值设为0 0，表示开始时没有香蕉在盘中，表示开始时没有香蕉在盘中；117练习题练习题8 8参考解答：参考解答：Semaphore SEmpty Empty =1；Semap

39、hore SApple Apple =0；Semaphore SBanana Banana =0； main( ) Cobegin father( ); mather( ); son( ); doughter Coend118n Father( ) Father( ) while(1) while(1) P(S P(SEmptyEmpty) ;) ; 把一只苹果放入盘把一只苹果放入盘 中；中； V(SV(SAppleApple) ;) ; Mather( ) Mather( ) while(1) while(1) P(P(Empty ) ; ) ; 把一只桔子放把一只桔子放 入盘中；入盘中；

40、V(BananaV(Banana );); 119nSonSon（ ） while(1) while(1) P(SP(SBananaBanana） ； 从盘中拿香蕉吃；从盘中拿香蕉吃； V(SV(SEmptyEmpty) ;) ; DaughterDaughter（ ） while(1) while(1) P(SP(SApple Apple ) ) ； 从盘中拿苹果吃；从盘中拿苹果吃； V(SV(SEmpty Empty ) ) 1205.5.哲学家就餐问题哲学家就餐问题nDijkstraDijkstra于于19651965年首先提出并解决了哲学家就餐年首先提出并解决了哲学家就餐问题。问题。n

41、该问题是大量该问题是大量并发控制问题并发控制问题中的一个典型的同步中的一个典型的同步例子例子。121 5. 5.哲学家就餐问题哲学家就餐问题n哲学家就餐问题描述如下：哲学家就餐问题描述如下：5 5个哲学家倾注毕生精个哲学家倾注毕生精力用于思考和吃饭。力用于思考和吃饭。n他们坐在一张放有他们坐在一张放有5 5把椅子的圆桌旁，每人独占一把椅子的圆桌旁，每人独占一把椅子。把椅子。n圆桌中间放置食品，桌上放着圆桌中间放置食品，桌上放着5 5根筷子根筷子，每个哲学，每个哲学家的左右各有一只筷子。家的左右各有一只筷子。122 5. 5.哲学家就餐问题哲学家就餐问题n哲学家只做哲学家只做2 2件事：思考和吃

42、饭件事：思考和吃饭n哲学家思考时并不影响他人，只有当哲学家哲学家思考时并不影响他人，只有当哲学家饥饿的时候，他才试图拿起左右两根筷子饥饿的时候，他才试图拿起左右两根筷子（一根一根拿起）。（一根一根拿起）。123n如果筷子已在他人手中，则需要等待。如果筷子已在他人手中，则需要等待。n饥饿的哲学家只有同时拿起了两根筷子后才可饥饿的哲学家只有同时拿起了两根筷子后才可以开始吃饭。以开始吃饭。n吃完饭后才放下筷子，重新开始思考。吃完饭后才放下筷子，重新开始思考。124 分析：分析：n放在桌子上的筷子是放在桌子上的筷子是临界资源，临界资源，在一段时间在一段时间内只允许一位哲学家使用。内只允许一位哲学家使用

43、。n为了实现对筷子的互斥使用，可以为了实现对筷子的互斥使用，可以用一个信用一个信号量表示一只筷子号量表示一只筷子，n由这由这5 5个信号量构成信号量数组。个信号量构成信号量数组。125n进行同步的解决方案如下：进行同步的解决方案如下：semaphore chopstick5semaphore chopstick5；/假定数组从下标假定数组从下标0 0开始：开始：所有信号量都被初始化为所有信号量都被初始化为1 1，即，即chopstick0= chopstick1= chopstick2=chopstick0= chopstick1= chopstick2=chopstick3= chopsti

44、ck4=1chopstick3= chopstick4=1；126n为了同步，第为了同步，第i i位哲学家的活动位哲学家的活动PiPi可描述为：可描述为： while(1) P( chopstic i ); P ( chopstic (i +1) mod 5 ); eating; V( chopstic i ); V (chopstic (i + 1 ) mod 5 ) ; thinking; 1275.5.哲学家就餐问题哲学家就餐问题n虽然上述解法可保证不会有两个相邻的哲学家虽然上述解法可保证不会有两个相邻的哲学家同时就餐，但有可能会引起死锁。同时就餐，但有可能会引起死锁。n假如假如5 5位

45、哲学家同时饥饿而拿起左边的筷子时，位哲学家同时饥饿而拿起左边的筷子时，就会使就会使5 5个信号量个信号量chopstickchopstick均为均为0 0；当他们试；当他们试图拿右边的筷子时，都将因无筷子可拿而无限图拿右边的筷子时，都将因无筷子可拿而无限期地等待。期地等待。n对于这样的死锁问题，可采用以下几种解决方对于这样的死锁问题，可采用以下几种解决方法：法：128 5.5.哲学家就餐问题哲学家就餐问题（1 1）至多只允许有至多只允许有4 4位哲学家同时去拿左边的筷子，位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能就餐，用毕后能最终能保证至少有一位哲学家能就餐，用毕后能释放两只筷子

46、，从而使更多的哲学家就餐。释放两只筷子，从而使更多的哲学家就餐。（2 2）仅当哲学家的左右两只筷子均可用时，才允许仅当哲学家的左右两只筷子均可用时，才允许他他拿起筷子拿起筷子, ,然后就餐。若左右有一只筷子不可用，然后就餐。若左右有一只筷子不可用，则不允许他拿一根筷子。则不允许他拿一根筷子。129 5.5.哲学家就餐问题哲学家就餐问题（3 3）规定奇数号哲学家先拿他左边的筷子，然后再拿规定奇数号哲学家先拿他左边的筷子，然后再拿他右边的筷子；偶数号哲学家则正相反。他右边的筷子；偶数号哲学家则正相反。按此规定，将是按此规定，将是1 1、2 2号哲学家竞争号哲学家竞争1 1号筷子；号筷子；3 3、4

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

48、文件，称为读者进读者进程（程（ReaderReader），），另一组进程只要求写该文件，另一组进程只要求写该文件，称为称为写者进程（写者进程（WriterWriter）。）。131 6. 6.读者读者- -写者问题写者问题l该问题还要求：该问题还要求：（1 1）允许多个读者进程同时对该文件执行读）允许多个读者进程同时对该文件执行读操作；操作；（2 2）不允许读者进程和写者进程同时对该文）不允许读者进程和写者进程同时对该文件进行操作，即读者和写者要互斥；件进行操作，即读者和写者要互斥；（3 3）不允许多个写者同时对文件进行）不允许多个写者同时对文件进行“写写”操作，即写者与写者之间要互斥操作，即

49、写者与写者之间要互斥132 分析：分析：n为满足要求为满足要求(1)(1)几个读者可以同时读同几个读者可以同时读同一个文件的要求，要设置一量一个文件的要求，要设置一量RcountRcount，表表示正在读文件的进程个数，初值设为示正在读文件的进程个数，初值设为0 0。n你现在还不能理解添加一个信号量你现在还不能理解添加一个信号量RounntRounnt的用处，后面就能明白了。的用处，后面就能明白了。n当一个读者进程要读该文件的时候，要先当一个读者进程要读该文件的时候，要先对对RcountRcount进行操作，让进行操作，让RcountRcount的值加的值加1 1；当；当一个进程读完该文件的时

50、候，也要对一个进程读完该文件的时候，也要对RcountRcount进行操作，让进行操作，让RcountRcount减减1 1；133n但是注意：但是注意：RcountRcount是可被多个读者进程访是可被多个读者进程访问的问的临界资源临界资源，应为它设置一个互斥信号，应为它设置一个互斥信号量量RmutexRmutex，初值设为初值设为1 1；134 分析：分析：n为满足要求条件为满足要求条件（2 2）即：即： “ “读者与写者保持互斥读者与写者保持互斥”以及满足要求以及满足要求（3 3）即：即： “ “ 写者与写者保持互斥写者与写者保持互斥”，要再设一个互斥信号量要再设一个互斥信号量Wmute

51、xWmutex，n这是一个和写有关的信号量，初值设为这是一个和写有关的信号量，初值设为1 1，Wmutex=1Wmutex=1135 总的来说：总的来说：n为了解决读写之间的同步，应设两个信号量为了解决读写之间的同步，应设两个信号量和一个共享变量：和一个共享变量：读互斥信号量读互斥信号量RmutexRmutex，用于使读进程互斥地访用于使读进程互斥地访问共享变量问共享变量RcountRcount，初值为初值为1 1；写互斥信号量写互斥信号量WmutexWmutex，用于实现写进程与写进用于实现写进程与写进程、写进程与读进程之间的互斥，初值为程、写进程与读进程之间的互斥，初值为1 1；共享变量共

52、享变量RcountRcount，记录当前正在读文件的进程记录当前正在读文件的进程个数，初值为个数，初值为0 0136读者读者- -写者工作过程描述如下：写者工作过程描述如下：Semephore Rmutex=1;Semephore Wmutex=1;int Rcount=0;main( ) cobegin reader i （）（）; i=1,2,3, writer j （）（）; j=1,2,3, coend137Reader i（）（） while(1) P(Rmutex）; if(Rcount=0)P(Wmutex); Rcount +; v(Rmutex); 读文件。；读文件。； P(

53、Rmutex); Rcount -; if(Rcount=0)V(Wmutex); V(Rmutex); writerj（ ） while(1) P(Wmutex); 写文件。；写文件。； V(Wmutex); 138 “读者优先读者优先”与与“写者优先写者优先”：n注意上面的读者注意上面的读者- -写者解决方案，它其实是一个对写者解决方案，它其实是一个对读者有利读者有利的解决方案。的解决方案。n只需设想一下：假设系统中顺序出现四个进程：只需设想一下：假设系统中顺序出现四个进程：reader1reader1，reader2reader2，writer1writer1，reader3reader

54、3nReader1Reader1、reader2reader2均可顺利进行读操作，当它们均可顺利进行读操作，当它们还在读的时候还在读的时候writer1writer1来到，可怜来到，可怜的的writer1writer1将被将被阻塞；阻塞；139 “读者优先读者优先”与与“写者优先写者优先”（续）：（续）：n接着接着reader3reader3、reader4reader4一系列读者相继来一系列读者相继来到到n尽管尽管writer1writer1先来到，但后来的先来到，但后来的readerreader们却抢们却抢在在writer1writer1的前面进行了读操作的前面进行了读操作n这样的解决方案

55、称为这样的解决方案称为“读者优先读者优先”140 “读者优先读者优先”与与“写者优先写者优先”（续）：（续）：n将上面的伪程序稍加改造，便可形成将上面的伪程序稍加改造，便可形成“写者优写者优先先”的读者的读者- -写者解决方案：写者解决方案：再增加一个信号量再增加一个信号量mutexmutex。在读者、写者进程开始时只有获得了这个资源在读者、写者进程开始时只有获得了这个资源才能继续进行；否则将会被阻塞。才能继续进行；否则将会被阻塞。141“写者优先写者优先”策略的读者写者问题：策略的读者写者问题：Semaphore mutex=1Semaphore Rmutex=1Semaphore Wmut

56、ex=1Int Rcount=0142 main( ) Cobegin readeri( ); / i=1,2,3, writerj( ); / j=1,2,3, Coend 143 readeri( ) while( 1 ) P(mutex); /新加的新加的 P(Rmutex); if(Rcount=0)P(Wmutex); Rcount=Rcount+1; V(Rmutex); V(mutex); /新加的新加的 Reading P(Rmutex); Rcount=Rcount-1; if(Rcount=0) V(Wmutex); V(Rmutex) 144 writeri（ ） whi

57、le（1） P(mutex); /新增加的新增加的 P(Wmutex); Writing V(Wmutex); V(mutex); /新增加的新增加的 145 “写者优先写者优先”策略的读者策略的读者-写者问题：写者问题：n在这种情况下，若依然按在这种情况下，若依然按reaer1,reader2,reaer1,reader2,writer1,writer1,reader3,reader4reader3,reader4的顺序到来一些进程，的顺序到来一些进程，nReader3Reader3，reader4reader4就不会象前面那样，插在就不会象前面那样，插在writer1writer1之前进行

58、读操作了。之前进行读操作了。146 3.4 3.4 管程机制管程机制n虽然信号量机制是一种既方便又有效的进程同步虽然信号量机制是一种既方便又有效的进程同步机制，但每个要访问临界资源的进程都必须自备机制，但每个要访问临界资源的进程都必须自备同步操作同步操作P(S)P(S)和和V(S) V(S) 。n这使得大量的同步操作分散在各个进程中。这使得大量的同步操作分散在各个进程中。这不这不仅给系统管理带来麻烦，而且还会因为同步操作仅给系统管理带来麻烦，而且还会因为同步操作的使用不当造成系统死锁。于是在解决上述问题的使用不当造成系统死锁。于是在解决上述问题的基础上，又产生了一种新的同步工具的基础上，又产生

59、了一种新的同步工具管程管程147一一. .管程定义：管程定义：nHasanHasan为管程下的定义为：为管程下的定义为：“一个管程定义了一个一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管上）的一组操作，这组操作能同步进程和改变管程中的数据程中的数据”。n管程机制提供了与信号量机制相同的表达能力，管程机制提供了与信号量机制相同的表达能力，但它更容易控制。但它更容易控制。n管程是一种软件模块，包括一个或多个过程、初管程是一种软件模块，包括一个或多个过程、初始化语句和局部数据。始化语句和局部数据。148

60、二二.管程的特点管程的特点：（1 1）只能通过管程中的过程，而不能通过其他外部）只能通过管程中的过程，而不能通过其他外部过程访问其局部数据变量；过程访问其局部数据变量；（2 2）进程通过调用管程的过程而进入管程；）进程通过调用管程的过程而进入管程；（3 3）为确保互斥，）为确保互斥，一个管程中一次只能有一个进程一个管程中一次只能有一个进程是活跃的，是活跃的，任何其它的想要调用管程的过程都将任何其它的想要调用管程的过程都将被阻塞，直至管程可用为止。被阻塞，直至管程可用为止。 因为管程是一个因为管程是一个语言成分语言成分，所以管程的互斥访问，所以管程的互斥访问完全完全由编译程序在编译时自动添加由编