第3章 进程的同步与通信

1、lChap.3 进程的同步与通信进程的同步与通信1 1、如何控制和协调并发进程异步执行、如何控制和协调并发进程异步执行 的时序？的时序？ 2 2、进程之间如何互相联系，传递信息？、进程之间如何互相联系，传递信息？ 本章讨论的主要问题本章讨论的主要问题3.1 3.1 进程间的相互作用进程间的相互作用n进程间的联系进程间的联系n进程的同步机制进程的同步机制信号量及信号量及P.VP.V操操作（解决进程同步互斥问题）作（解决进程同步互斥问题）1.1.进程间的联系进程间的联系相交进程与无关进程相交进程与无关进程相交进程：指多个并发进程在逻辑上有相交进程：指多个并发进程在逻辑上有某种联系某种联系无关进程（

2、不相交进程）：在逻辑上无无关进程（不相交进程）：在逻辑上无任何联系的进程任何联系的进程直接作用和间接作用直接作用和间接作用直接作用：直接作用：进程间的相互联系是进程间的相互联系是有意识的安排的有意识的安排的，直接作用只发生在相交进程间直接作用只发生在相交进程间间接作用：间接作用：进程间要通过进程间要通过某种中介某种中介发生联系，是无发生联系，是无意识安排的，可发生在相交进程之间，意识安排的，可发生在相交进程之间，也可发生在无关进程之间也可发生在无关进程之间进程的同步（直接作用）进程的同步（直接作用）进程的同步：进程的同步：synchronism指系统中多个进程中发生的事件存在某种指系统中多个进

3、程中发生的事件存在某种时序关系，需要相互合作，共同完成一项时序关系，需要相互合作，共同完成一项任务。任务。具体说，一个进程运行到某一点时具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态消息后被唤醒进入就绪态同步问题同步问题1nA race between two or more teams, in which each team member runs only a set part of the race and is then relieved

4、 by another member of the team.缓冲区键盘键盘计算计算缓冲区缓冲区缓冲区B进程A进程 A A进程只有当缓冲区为空时，才能将数据输入缓冲区，进程只有当缓冲区为空时，才能将数据输入缓冲区， B B进程只有当缓冲区有数据时，才能从缓冲区取数进行计算。进程只有当缓冲区有数据时，才能从缓冲区取数进行计算。 进程的同步与互斥虽然是两个既有区别又有联系的概念，进程的同步与互斥虽然是两个既有区别又有联系的概念，但从本质上看并发进程的异步执行都必须按一定的相互约束但从本质上看并发进程的异步执行都必须按一定的相互约束的时序进行，因此统称为的时序进行，因此统称为“进程同步进程同步”。

5、显然，必须解决好进程的同步问题，才能保证并发进程显然，必须解决好进程的同步问题，才能保证并发进程的正常执行。的正常执行。同步问题同步问题2进程的互斥（间接作用）进程的互斥（间接作用）由于各进程要求共享资源，而有些资源需由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥些资源，进程的这种关系为进程的互斥临界资源：临界资源：critical resource 系统中某些资源一次只允许一个进程使系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资用，称这样的资源为临界资源或互斥资源或共享变量源或共

6、享变量临界区（互斥区）：临界区（互斥区）：critical section一个程序片段的集合，这些程序片段分散一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结在不同的进程中，对某个共享的数据结构（共享资源）进行操作构（共享资源）进行操作 在进程中涉及到临界资源的程序段叫在进程中涉及到临界资源的程序段叫临临界区界区 多个进程的临界区称为多个进程的临界区称为相关临界区相关临界区 每个进程每个进程 互斥访问互斥访问临界资源临界资源的那段代码称为的那段代码称为临界区临界区。代。代码构成如下码构成如下： repeatrepeat entry section entry sectio

7、n 进入区进入区 申请进入临界区申请进入临界区 critical section critical section 临界区临界区 访问临界资源访问临界资源 exit section exit section 退出区退出区 退出对临界资源的访退出对临界资源的访问问 remainder section remainder section 剩留区剩留区 进程的其他代码进程的其他代码 until false until false 1 1。什么是临界资源。什么是临界资源 凡是以互斥方式使用的共享资源都称为临界资源。临界凡是以互斥方式使用的共享资源都称为临界资源。临界资源具有一次只允许一个进程使用的属性

8、资源具有一次只允许一个进程使用的属性。2 2。临界区。临界区 （critical section）使用互斥区的原则使用互斥区的原则有空让进：有空让进：当无进程在互斥区时，任何有权使用当无进程在互斥区时，任何有权使用互斥区的进程可进入互斥区的进程可进入无空等待：无空等待：不允许两个以上的进程同时进入互斥不允许两个以上的进程同时进入互斥区区多中择一：多中择一：当没有进程在临界区，而同时有多个当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待界区，其他进程必须等待有限等待：有限等待：任何进入互斥区的要求应在有限的时任

9、何进入互斥区的要求应在有限的时间内得到满足间内得到满足让权等待：让权等待：处于等待状态的进程应放弃占用处于等待状态的进程应放弃占用CPUCPU，以使其他进程有机会得到以使其他进程有机会得到CPUCPU的使用权的使用权前提：任何进程无权停止其它进程的运行前提：任何进程无权停止其它进程的运行 进程之间相对运行速度无硬性规定进程之间相对运行速度无硬性规定进程互斥的解决有两种做法进程互斥的解决有两种做法: :n由竞争各方平等协商由竞争各方平等协商n引入进程管理者，由管理者来协调竞争引入进程管理者，由管理者来协调竞争各方对互斥资源的使用各方对互斥资源的使用具体方法：具体方法：n硬件硬件n软件软件使用互斥

10、区的原则（续）使用互斥区的原则（续）软件解法软件解法 (1)(1)free: free: 表示临界区标志表示临界区标志 true: true: 有进程在临界区有进程在临界区 false:false:无进程在临界区无进程在临界区( (初值初值) ) . . while (free); while (free); free = true; free = true; 临界区临界区 free = false;free = false;空循环空循环软件解法软件解法 (2)(2)turn: true turn: true P P进入临界区进入临界区 false false Q Q进入临界区进入临界区 .P

11、: while (not turn);P: while (not turn); 临界区临界区 turn = true;turn = true;Q: while (turn);Q: while (turn); 临界区临界区 turn = false;turn = false;软件解法的缺点：软件解法的缺点： 1. 1. 忙等待忙等待 2. 2. 实现过于复杂，需要高的编程技巧实现过于复杂，需要高的编程技巧硬件解法：提供专门的硬件指令，允许对一个字的硬件解法：提供专门的硬件指令，允许对一个字的内容进行检测和修正，或交换两个字的内容内容进行检测和修正，或交换两个字的内容目的：解决共享变量的目的：解决

12、共享变量的完整性和正确性完整性和正确性 简单、有效，特别简单、有效，特别适用于多处理机适用于多处理机缺点：忙等待缺点：忙等待硬件解法硬件解法 (1)(1) “测试并设置测试并设置”指令指令 TSTS指令执行过程不可分割。指令执行过程不可分割。 为临界资源设置一个布尔量为临界资源设置一个布尔量 LOCKLOCK：实现的基本思想是：对实现的基本思想是：对临界资源临界资源“加锁加锁” 进程的同步机制可以用软件实现，也可以用硬件实现。进程的同步机制可以用软件实现，也可以用硬件实现。（1 1）用）用T TestandestandS Set et 指令实现互斥指令实现互斥LOCK LOCK = false

13、 false 没有进程在临界区没有进程在临界区true true 有进程进入临界区有进程进入临界区 TSTS指令的形式指令的形式： function function tsts（varvar lock lock：booleanboolean）：）：booleanboolean； begin begin tsts：=lock=lock； locklock：=true=true； endend；以两进程以两进程P1P1、P2P2并发执行为例，如果并发执行为例，如果P1P1先执行：先执行：若若P1P1先进入临界区，则先进入临界区，则P2P2循环执行循环执行TSTS指令，直到指令，直到P1P1退出临界

14、区。退出临界区。调用TS指令p1TS=true进入P1临界区Lock：=false进入剩余区调用TS指令p2TS=true进入P2临界区Lock：=false进入剩余区进入剩余区调用调用TS指令指令TS=trueNY进入进入P1临界区临界区调用TS指令TS=trueYN调用TS指令调用调用TS指令指令TS=trueTS=trueLock：=false进入进入P2临界区临界区进入剩余区进入剩余区 如果如果P2P2先执行：若先执行：若P2P2先进入临界区，则先进入临界区，则P1P1循环执行循环执行TSTS指令，直指令，直到到P2P2退出临界区。退出临界区。 结论：结论： TSTS指令有效实现互斥（

15、空闲让进、忙则等待）指令有效实现互斥（空闲让进、忙则等待） 循环测试，处于循环测试，处于“忙等待忙等待”（未让权等待）（未让权等待）调用TS指令p2TS=true进入P1临界区Lock：=false进入剩余区调用调用TS指令指令TS=trueNY进入进入P2临界区临界区Lock：=false进入剩余区进入剩余区调用TS指令p1TS=true进入P2临界区Lock：=false进入剩余区进入剩余区调用TS指令TS=trueYN调用TS指令调用调用TS指令指令TS=trueTS=true进入进入P1临界区临界区Lock：=false进入剩余区进入剩余区2.2.进程的同步机制进程的同步机制信号量及信

16、号量及P.VP.V操作操作 以上介绍的各种算法都存在问题，它们是以上介绍的各种算法都存在问题，它们是平平等进程等进程间的一种间的一种协商机制协商机制，需要一个地位高，需要一个地位高于进程的于进程的管理者管理者来解决公有资源的使用问题来解决公有资源的使用问题 操作系统操作系统可从进程管理者的角度来处理互斥可从进程管理者的角度来处理互斥的问题，的问题，信号量信号量就是操作系统提供的管理公就是操作系统提供的管理公有资源的有效手段有资源的有效手段进程的同步机制（续）进程的同步机制（续）同步机制：同步机制： 信号量信号量及及P P、V V操作；管程；操作；管程；条件临条件临界域；路径表达式等（用于集中式

17、系界域；路径表达式等（用于集中式系统中）统中）同步机制应满足的基本要求：同步机制应满足的基本要求：* * 描述能力描述能力* * 可以实现可以实现* * 效率高效率高* * 使用方便使用方便n1965年，由荷兰学者年，由荷兰学者Dijkstra提出（所以提出（所以P、V分别是荷兰语的分别是荷兰语的test(proberen)和和increment(verhogen)）n一种卓有成效的进程同步机制一种卓有成效的进程同步机制n最初提出的是二元信号量（互斥）最初提出的是二元信号量（互斥） 推广到一般信号量（多值）（同步）推广到一般信号量（多值）（同步）n广泛应用于存在临界资源和临界区控制广泛应用于存

18、在临界资源和临界区控制的场合的场合信号量及信号量及P、V操作操作Semaphores (proposed by Dijkstra in 1965)nWhat a Semaphore is?nAn integer variablenRepresent the number of resources available (when it is greater than or equals to 0)nRepresent the number of processes waiting for the resources( when it is less than 0)nOperations on a

19、 semaphorenInitializationnP operation - to testnV operation - to increment信号量：信号量：semaphoresemaphoren是一个数据结构是一个数据结构n定义如下：定义如下： strucstruc semaphore semaphore intint value; value;pointer_PCB queue;pointer_PCB queue; n信号量说明：信号量说明： semaphore s;semaphore s; S.value ：= S.Value + 1； 若 S.Value 0 进程继续执行。 若

20、S.Value 0 则释放S等待队列中的一个进程 ， 使之转为就绪状态。P P、V V操作原语操作原语 定义：定义：VARVAR S S：SemaphoreSemaphore； 1 1。P P操作（操作（wait wait 原语）原语） 每作一次每作一次P P操作，申请分配一个单位的资源。操作，申请分配一个单位的资源。 P P（S S） 对信号量对信号量S S 进行进行P P操作。操作。 2 2。V V操作（操作（SignalSignal原语）原语） V V（S S） 对信号量对信号量S S 进行进行V V操作，释放一个单位的资源。操作，释放一个单位的资源。 S.value ：= S.Valu

21、e - 1； 若若 S.Value 0 进程继续执行。进程继续执行。 若若 S.Value 0 0 时，其值表示某类资源可用数量。时，其值表示某类资源可用数量。 S.ValueS.Value 0 0 时，其绝对值表示在信号量队列中等待时，其绝对值表示在信号量队列中等待 该资源的进程数。该资源的进程数。 P P、V V操作有严格的不可分割性；执行过程不允许中断；操作有严格的不可分割性；执行过程不允许中断； P P、V V操作成对出现。操作成对出现。 （根据同步机制的原则，分析P、V操作的特点，）？问题？问题？如何使用如何使用P P、V V操作实现同步机制？操作实现同步机制？ 考虑：考虑： 如何控

22、制互斥地使用临界资源？如何控制互斥地使用临界资源？ 如何控制进程并发执行的时序？如何控制进程并发执行的时序？实现同步机制实现同步机制基本思想是：加基本思想是：加锁、解锁锁、解锁Another Meaning from SemaphorenP to request resourcesnV to release resources1、利用信号量实现进程互斥、利用信号量实现进程互斥n共享某个公有资源共享某个公有资源 定义一个互斥信号量，初定义一个互斥信号量，初值为值为1P(S)V(S)临界区Mutual Exclusion Achieved by Using Semaphoreshared sema

23、phore S = 1;/P(S);/ Critical SectionV(S);The Bounded-Buffer Problem 1PAPAPBPBbuf设 mutex 公共互斥信号量 初值：mutex.Value = 1利用P、V操作实现互斥的模型实现进程互斥实现进程互斥 以两个进程并发执行为例以两个进程并发执行为例进程进程P1P1.P P（mutexmutex）；）；进入进入P1P1临界区；临界区；V V（mutexmutex）；）；.值值0 0 进程进程P2P2.P P（mutexmutex）；）； 进入进入P2P2临界区；临界区； V（mutex）；）；.值值0 0 值值-1-1

24、 进程进程P1P1先执行先执行 P P（mutexmutex）；）；进程进程P1P1进入临界区；进入临界区； 进程进程P2P2开始执行开始执行 P P（mutexmutex）；）；进程进程P2P2阻塞，插入阻塞队列。阻塞，插入阻塞队列。 若进程若进程P1P1再次执行再次执行 V V（mutexmutex）；）；mutex.Valuemutex.Value=0 =0 释放资源。释放资源。 2、实现进程间的同步、实现进程间的同步nPA：需要空缓冲区资源，该资源由需要空缓冲区资源，该资源由PB取取数后产生，空缓冲区资源用信号量数后产生，空缓冲区资源用信号量Sempty表示表示nPB：需要满缓冲区资源

25、，该资源由需要满缓冲区资源，该资源由PA送送数后产生，满缓冲区资源用信号量数后产生，满缓冲区资源用信号量Sfull表表示示PAPAPBPBbuf实现进程间的同步实现进程间的同步PA:P(Sempty);V(Sfull);Goto PA;PB:P(Sfull);V(Sempty);Goto PB;Shared Semaphore Sempty := 1Shared Semaphore Sfull := 0 分析：打印进程与计算进程之间有两个约束： 1）计算进程只有当缓冲区为空时，才能放入计算结果。 2）打印进程只有当缓冲区有结果时，才能从缓冲区取 计算结果打印。定义两个信号量：Sempty、 S

26、full ，用于控制这两个约束：Sfull 控制打印进程从缓冲区取计算结果打印。Sempty 控制计算进程向缓冲区送计算结果。2 2、实现进程同步、实现进程同步 实例：实例： 打印进程与计算进程的同步问题。打印进程与计算进程的同步问题。缓冲区计算计算打印机打印机缓冲区缓冲区缓冲区打印打印进程进程计算进程计算进程SfullSempty设：设： Sempty 初值为初值为1 1 Sfull初值为初值为0 0 表示缓冲区为空。表示缓冲区为空。 当当 Sfull 0 0 表示可以打印表示可以打印 当当 Sempty 0 0 表示可以表示可以放入计算结果。放入计算结果。信号量机制的基本原理信号量机制的基

27、本原理n两个或两个或多个进程可以通过简单的信号进行合作，一多个进程可以通过简单的信号进行合作，一个进程被迫在某个指定位置停止，直到它收到一个个进程被迫在某个指定位置停止，直到它收到一个特定的信号才继续。特定的信号才继续。n通过合适的信号结构可以满足任何复杂的协作要求。通过合适的信号结构可以满足任何复杂的协作要求。n为了发信号，使用特殊的变量为了发信号，使用特殊的变量信号量。信号量。n进程执行原语进程执行原语 signal(S) / V(S)发出信号，通过执行发出信号，通过执行 wait(S) / P(S)接收信号；如果没有相应的信号到达，接收信号；如果没有相应的信号到达，该进程将被挂起直到所需

28、信号到达。该进程将被挂起直到所需信号到达。Another Meaning from SemaphorenP wait nTo wait for a signalnV signal nTo give a signal to somebody.The Bounded-Buffer Problem 2PAPAPBPBbufbufbuf.bufThe buffer is finite and consists of a linear array of elementsQ: How to describe ? Mutual Exclusion Needed!Synchronization Between

29、 Producer and ConsumernProducer:repeatproduce P(Sempty); V(Sfull);forevernConsumer:repeat P(Sfull); V(Sempty);consumeforeverSempty, Sfull : Semaphore;Sempty := n;Sfull := 0;Classical Synchronization Problemsn生产者生产者消费者问题消费者问题( the Producer-Consumer Problem )n读者与写者问题读者与写者问题( the Readers and Writers Pr

30、oblem )经典的生产者经典的生产者消费者问题消费者问题消费者消费者生产者生产者生产者生产者消费者问题分析消费者问题分析n生产者与消费者间的同步关系生产者与消费者间的同步关系n生产者之间互斥访问缓冲区生产者之间互斥访问缓冲区n消费者之间互斥访问缓冲区消费者之间互斥访问缓冲区n生产者与消费者之间互斥访问缓冲区生产者与消费者之间互斥访问缓冲区 P P进程不能往进程不能往“满满”的缓冲区中放产品，的缓冲区中放产品，设置信号量为设置信号量为Sempty Q Q进程不能从进程不能从“空空”的缓冲区中取产品，的缓冲区中取产品，设置信号量设置信号量Sfull Synchronization Between

31、 Producer and ConsumernProducer:repeatproduce P(Sempty);V(Sfull);forevernConsumer:repeat P(Sfull);V(Sempty);consumeforeverSempty, Sfull : Semaphore;Sempty := n;Sfull := 0;.PQ放 消 息取 消 息nn个 缓 冲 区(Buffer)ijMutual Exclusion Among Producers/ConsumersnProducer:RepeatproduceP(mutex);V(mutex);forevernConsum

32、er:repeatP(mutex);V(mutex);consumeforevermutex: Semaphore;mutex := 1;A Solution to the Bounded-Buffer Producer/Consumer ProblemSemaphores:Sempty: Semaphore := n;Sfull: Semaphore := 0;Mutex: Semaphore := 1;A Solution to the Bounded-Buffer Producer/Consumer ProblemnProducer:RepeatproduceP(Sempty);P(mu

33、tex);V(Sfull);V(mutex);forevernConsumer:repeatP(Sfull);P(mutex);V(Sempty);V(mutex);consumeforeverV操作出现的次序能否颠倒？P操作出现的次序能否颠倒？得出结论：得出结论：生产一种产品P（S n）V（S 0)V(S)P（S ）产品送入缓冲区P(S0)P(S)V(S)消耗该产品从缓冲区取一产品V(Sn)生产者消费者ProducerConsumerProblem 1n桌上有一空盘，只允许放入一个水果。桌上有一空盘，只允许放入一个水果。爸爸专向盘中放苹果，妈妈专向盘中入爸爸专向盘中放苹果，妈妈专向盘中入桔子

34、，女儿专等吃盘中的苹果，儿子专桔子，女儿专等吃盘中的苹果，儿子专等吃盘中的桔子。试用等吃盘中的桔子。试用P、V原语实现爸原语实现爸爸、妈妈、儿子和女儿间能同步的程序。爸、妈妈、儿子和女儿间能同步的程序。 The Readers / Writers Problem There is a data area shared among a number of processes. The data area could be a file, a block of main memory, or even a bank of processor registers. There are a numbe

35、r of processes that only read the data area(readers) and a number that only write to the data area(writers).The Readers / Writers ProblemThe following conditions must be satisfied:1.Any number of reader may simultaneously read the file.2.Only one writer at a time may write to the file.3.If a writer

36、is writing to the file, no reader may read it.读者与写者问题读者与写者问题n读者：只能读取数据区中的数据读者：只能读取数据区中的数据n写者：只能往数据区中写入数据写者：只能往数据区中写入数据n满足的要求：满足的要求：1、同时可以有任意多个读者读取数据、同时可以有任意多个读者读取数据2、在某个时候只能有一个写者往里写数据、在某个时候只能有一个写者往里写数据3、在写的时候不能读，读的时候不能写、在写的时候不能读，读的时候不能写 与生产者与生产者/消费者问题的区别？消费者问题的区别？A Solution to Readers/Writers Proble

37、mnSemaphores:nreadcount: integer;/ number of readersnrmutex: semaphores := 1;/ mutual exclusionnwmutex: Semaphores := 1;/ mutual exclusion among writersA Solution to Readers/Writers ProblemnReader:repeatP(rmutex);readcount := readcount + 1;if readcount =1 then P(wmutex);V(rmutex);READUNIT;P(rmutex);

38、readcount := readcount - 1;if readcount = 0 then V(wmutex);V(rmutex);foreverlWriter:repeatP(wmutex);WRITEUNIT;V(wmutex);forever本讲内容本讲内容nP、V操作小结操作小结n信号量集信号量集n进程间通信进程间通信回顾回顾经典的进程同步问题：经典的进程同步问题：n生产者生产者消费者问题消费者问题n读者读者写者问题写者问题Problem 2n有一阅览室，共有有一阅览室，共有100个座位。读者进入个座位。读者进入前必须先在一张登记表上登记，该表为前必须先在一张登记表上登记，该表为

39、每一座位列一表目，包括座号和读者姓每一座位列一表目，包括座号和读者姓名。读者离开时要消掉登记内容。试用名。读者离开时要消掉登记内容。试用某一种语言（或类语言）和某一种语言（或类语言）和P、V操作描操作描述读者进程的同步结构。述读者进程的同步结构。 n【分析分析】n本例是考查操作系统中信号量的应用本例是考查操作系统中信号量的应用. 读者要申请座读者要申请座位，首先要获得登记表以便在上面进行登记；该读位，首先要获得登记表以便在上面进行登记；该读者在登记过程中是不允许其他读者进行登记的；因者在登记过程中是不允许其他读者进行登记的；因此，需要引入一个初值为此，需要引入一个初值为1的信号的信号量量mut

40、ex以实现读以实现读者间对登记表的互斥使用；者间对登记表的互斥使用；n读者要在登记表上进行登记，前提是登记表要有空读者要在登记表上进行登记，前提是登记表要有空表目；为此，需要引入一个信号表目；为此，需要引入一个信号量量S，其初值其初值为为100，表示有空表目表示有空表目100项；项；n读者在完成登记后，放下登记表给其他读者使用，读者在完成登记后，放下登记表给其他读者使用，然后在申请到的座位上进行阅读活动；然后在申请到的座位上进行阅读活动； n在完成阅读后读者需删除登记表上的内容，在他进在完成阅读后读者需删除登记表上的内容，在他进行删除的同时是不允许其他读者进行删除的。行删除的同时是不允许其他读

41、者进行删除的。n读者进程：读者进程：nmutex, S: Semaphore;mutex := 1;S := 100;Process Readeri begin P( S ); /查找空表目查找空表目 P( mutex ); /申请登记申请登记 ; V( mutex ); /允许其他读者填写登记表允许其他读者填写登记表 ; P( mutex );V( mutex );V( S );end;Problem 3n设有四个进程设有四个进程A、X、Y、Z共享一个缓共享一个缓冲区，进程冲区，进程A负责循环地从文件读一个整负责循环地从文件读一个整数并放入缓冲区，进程数并放入缓冲区，进程X从缓冲区中循环从缓

42、冲区中循环地读入地读入MOD 3为为0的整数并累计求和；的整数并累计求和；Y从缓冲区中循环地读入从缓冲区中循环地读入MOD 3为为1的整数的整数并累计求和；并累计求和；Z从缓冲区中循环地读入从缓冲区中循环地读入MOD 3为为2的整数并累计求和。请用的整数并累计求和。请用PV操作写出能够正确执行的程序。操作写出能够正确执行的程序。 缓冲区AZYXnum MOD 3 = 0numnum MOD 3 = 1num MOD 3 = 2Sempty, SX, SY, SZ: Semaphore = 1, 0, 0, 0;num: integer; Process PABeginP(Sempty);if(

43、 num MOD 3 = 0 )V( SX )Else if ( num MOD 3 = 1 )V( SY )Else V( SZ );End;Process PXBeginP( SX );V( Sempty );End;Process PYBeginP( SY );V( Sempty );End;Process PZBeginP( SZ );V( Sempty );End;1) 信号量的物理含义信号量的物理含义：S0表示有表示有S个资源可用个资源可用S=0表示无资源可用表示无资源可用S=1 & S2 = 1 & & Sn = 1)/满足资源要求时的处理；满足资源要求时

44、的处理； for (i = 1; i = n; +i) -Si; /注：注：与与P的处理不同，这里是在确信可满足的处理不同，这里是在确信可满足 / / 资源要求时，才进行减资源要求时，才进行减1操作；操作；break;else /某些资源不够时的处理；某些资源不够时的处理； 调用进程进入第一个小于调用进程进入第一个小于1信号量的等待队列信号量的等待队列Sj.queue; 阻塞调用进程阻塞调用进程; 信号量集信号量集AND型信号量集（续）型信号量集（续） Ssignal(S1, S2, , Sn)for (i = 1; i = ti；即当资源数量低于即当资源数量低于ti时，便不予时，便不予分配）

45、分配）占用占用值为值为di（表示资源的申请量，即表示资源的申请量，即Si = Si - di）对应的对应的P、V原语格式为：原语格式为：nSwait(S1, t1, d1; .; Sn, tn, dn);nSsignal(S1, d1; .; Sn, dn);一般一般“信号量集信号量集”（续）（续）一般一般“信号量集信号量集”可以用于各种情况可以用于各种情况的资源分配和释放，几种特殊情况的资源分配和释放，几种特殊情况：nSwait(S, d, d)表示每次申请表示每次申请d个资源，当少个资源，当少于于d个时，便不分配个时，便不分配nSwait(S, 1, 1)表示互斥信号量表示互斥信号量nSw

46、ait(S, 1, 0)可作为一个可控开关（当可作为一个可控开关（当S 1时，允许多个进程进入临界区；时，允许多个进程进入临界区；当当S=0时，时，禁止任何进程进入临界区）禁止任何进程进入临界区）管程的引入管程的引入n信号量机制中信号量机制中P、V操作使用不当会造成操作使用不当会造成与时间有关的错误与时间有关的错误P、V操作不当的例子操作不当的例子1V(mutex)P(mutex)P(mutex)V(mutex)P、V操作不当的例子操作不当的例子2V(mutex)V(mutex)P(mutex)V(mutex)P、V操作不当的例子操作不当的例子3P(mutex)P(mutex)V(mutex)

47、管程管程n1971年年, Dijkstra：把所有进程对某一种把所有进程对某一种临界资源的同步操作集成起来构成临界资源的同步操作集成起来构成“秘秘书书”进程；凡要访问该资源的进程都需进程；凡要访问该资源的进程都需先报告先报告“秘书秘书”，由其实现诸进程的同，由其实现诸进程的同步步n1973年，年，Hansan和和Hoare：管程概念管程概念管程概念管程概念n一个管程定义了一个数据结构和能为并一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管组操作，这组操作能同步进程和改变管程中的数据程中的数据Hansan M

48、onitors - high level synchronization constructsnSemaphores and event-counters are too primitive (low level) and are hard to programn Monitors are a special package of proceduresn Mutual exclusion constructs are generated by the compiler. Internal data structures are invisiblenOnly one process is act

49、ive in a monitor at the same time - high level mutual exclusionmonitor sharedData int *buffer;public:writeData(int byteNum) ;readData(int byteNum) ; ;type monitor-name = monitorvariable declarationsprocedure entry P1 ();begin end;procedure entry P2 ();begin end;.procedure entry Pn ();begin end; begi

50、ninitialization code endFigure 6.20 Monitor with Condition VariableShared dataxyQueues associated with x, y conditionsoperationsInitialization codeEntry queueMonitors - Condition variablesn Only one process is active in a monitor at the same time - high level mutual exclusionn To enable synchronizat

51、ion: Condition variables and operations on them: and n the monitor provides queuing for proceduresn When one procedure and another , the signaling procedure is inside the monitor ! n Operation signal must be either followed by or , so that only one procedure is active at one timeBounded-Buffer with

52、Monitorsmonitor ProducerConsumerconditionnotfull, notempty;integercount;procedure enter;beginif count = N then notfull.wait;enter_item;count := count + 1;if count = 1 then notempty.signal; endprocedure remove;beginif count = 0 then notempty.wait;remove_item;count := count - 1;if count = N - 1 then n

53、otfull.signal; endcount := 0;end monitorBounded-Buffer with Monitors (II)procedure producer;beginwhile true dobeginproduce_item;ProducerConsumer.enter;endend;procedure consumer;beginwhile true dobeginProducerConsumer.remove;consume_item;endend;Interprocess Communication (进程间通信进程间通信)n低级通信低级通信 交换的数据量较

54、小的情况，常常指的交换的数据量较小的情况，常常指的是控制信息的交换，往往用来控制进程是控制信息的交换，往往用来控制进程执行的速度，如锁或信号量执行的速度，如锁或信号量n高级通信高级通信 传送的数据量大，只是为了交换信息，传送的数据量大，只是为了交换信息，而不是为了控制进程的执行速度而不是为了控制进程的执行速度进程间高级通信进程间高级通信类型类型n共享存储区方式共享存储区方式n共享文件方式（管道方式）共享文件方式（管道方式）n邮箱通信邮箱通信n消息缓冲机制消息缓冲机制共享存储区方式共享存储区方式n在内存中开辟一块供多个进程共享使用在内存中开辟一块供多个进程共享使用的区域的区域n基于共享数据结构的通信方式基于共享数据结构的通信方式n由程序员完成同步处理n基于共享存储区的通信方式基于共享存储区的通信方式共享文件方式（管道方式共享文件方式（管道方式, Pipe）WriteReadFI