数据结构第二章第4小结

1、12.3 2.3 进程同步进程同步2.3.2 2.3.2 信号量机制信号量机制一段处理代码需要一段处理代码需要同时同时获取获取两个或多个两个或多个临界资源临界资源会出现什么问题？会出现什么问题？3. AND3. AND型信号量型信号量22.3 2.3 进程同步进程同步2.3.2 2.3.2 信号量机制信号量机制例如例如：设设S为进程为进程P1、P2实现互斥访问同一台打印机的信号量实现互斥访问同一台打印机的信号量semaphore S=1; semaphore S=1; main( )main( ) cobegin cobeginP1();P1();P2();P2(); coend coend

2、P1( ) P1( ) P(S); P(S); P1 P1进入临界区；进入临界区； V(S);V(S); P2( ) P2( ) P(S); P(S); P2 P2进入临界区；进入临界区； V(S);V(S); 3 需要需要同时同时获取获取两个或多个两个或多个临界资源临界资源举例：举例：semaphore S1=1; semaphore S1=1; semaphore S2=1;semaphore S2=1;main( )main( ) cobegin cobeginP1();P1();P2();P2(); coend coend P1( ) P1( ) P(S1); P(S1); a a P

3、(S2); P(S2); b b P1P1进入临界区；进入临界区； V(S1);V(S1); V(S2); V(S2); P2( ) P2( ) P(S2); P(S2); a a P(S1); P(S1); b b P2P2进入临界区；进入临界区； V(S2); V(S2); V(S1); V(S1); 进程进程P1与与P2同时需要获得两个临界资源同时需要获得两个临界资源C1和和C2。分别给两个临界资源分别给两个临界资源C1和和C2设置信号量设置信号量S1和和S2。42.3 2.3 进程同步进程同步2.3.2 2.3.2 信号量机制信号量机制一段处理代码需要一段处理代码需要同时同时获取获取两

4、个或多个两个或多个临界资源临界资源ANDAND型信号量集型信号量集用于用于同时需要多种资源同时需要多种资源且且每种占用每种占用一个一个时的信号量操作；时的信号量操作；可能死锁可能死锁：各进程分别获得部分临界资源，：各进程分别获得部分临界资源，然后等待其余的临界资源，然后等待其余的临界资源， 各不相让各不相让 52.3 2.3 进程同步进程同步2.3.2 2.3.2 信号量机制信号量机制基本思想：基本思想： 在一个原语中，将一段代码同时需要的在一个原语中，将一段代码同时需要的多个临界资源，多个临界资源，要么全部分配给它，要么一要么全部分配给它，要么一个都不分配。个都不分配。 称为称为Swait(

5、Simultaneous Wait)Swait(Simultaneous Wait)。6 Swait(S1, S2, , Sn)Swait(S1, S2, , Sn)/P/P原语；原语； if (S1 =1 & S2 = 1 & & Sn = 1)if (S1 =1 & S2 = 1 & & Sn = 1) /满足资源要求时的处理；满足资源要求时的处理； for (i = 1; i = n; +i) -Si;for (i = 1; i = n; +i) -Si; /注：与注：与waitwait的处理不同，这里是在确信可满足的处理不同，这里是在确信

6、可满足 /资源要求时，才进行减资源要求时，才进行减1 1操作；操作； else else /某些资源不够时的处理；某些资源不够时的处理； 调用进程进入第一个小于调用进程进入第一个小于1 1信号量的等待队列信号量的等待队列 Sj.queue;Sj.queue; 阻塞调用进程阻塞调用进程; ; 72.3 2.3 进程同步进程同步2.3.2 2.3.2 信号量机制信号量机制在在SwaitSwait时，各个信号量的次序并不重要时，各个信号量的次序并不重要，它，它只会影响进程归入哪个阻塞队列。只会影响进程归入哪个阻塞队列。由于是对资源由于是对资源全部全部分配或不分配，所以总有分配或不分配，所以总有进程获

7、得全部资源并在推进之后释放资源，进程获得全部资源并在推进之后释放资源，因此因此不会死锁不会死锁。8 Ssignal(S1, S2, , Sn)Ssignal(S1, S2, , Sn) for (i = 1; i = n; +i) for (i = 1; i = tiSi = ti，表示资源数量低于表示资源数量低于titi时，便不予分配），时，便不予分配），占用值为占用值为didi（用于信号量的增减，即（用于信号量的增减，即Si = Si - diSi = Si - di和和Si = Si Si = Si + di+ di）Swait(S1, t1, d1, , Sn, tn, dn);Swa

8、it(S1, t1, d1, , Sn, tn, dn);Ssignal(S1, d1, , Sn, dn);Ssignal(S1, d1, , Sn, dn);12Swait(S1 , t 1 ,d 1 , , Sn , t n , d n ) if (S1 = t 1 )& .&(Sn =tn ) for(i=1;i=n;i+) Si = Si - d i ; else Place the executing process in the waiting queue of the first Si with Si t i and set its program counte

9、r to the beginning of the the Swait operation.13Ssignal(S1 ,d 1 , , Sn , d n ) for(i=1;i=1S=1时，允许多个进程进入临界区；时，允许多个进程进入临界区；当当S=0S=0时，禁止任何进程进入临界区；时，禁止任何进程进入临界区；信号量集信号量集未必未必成对使用成对使用SwaitSwait和和SsignalSsignal：如：一：如：一起申请，但不一起释放；起申请，但不一起释放；152.4 2.4 经典进程同步问题经典进程同步问题1. 1. 生产者消费者问题生产者消费者问题(the producer-consu

10、mer problem)问题描述：问题描述：若干进程通过若干进程通过有限的共享缓冲区有限的共享缓冲区交换数据交换数据。其中，。其中， 生产者生产者 进程不断写入，而进程不断写入，而 消费者消费者 进程不进程不断读出；共享缓冲区共有断读出；共享缓冲区共有N N个个；任何任何时刻时刻只能有只能有一个一个进进程可对共享缓冲区进行操作。程可对共享缓冲区进行操作。共享缓冲区生产指针消费指针Producer 1Producer 2.Producer MConsumer 1Consumer 2.Consumer N满空指针移动方向16生产者和消费者二类进程生产者和消费者二类进程P P和和C C之间应满足下列

11、二个同步条件：之间应满足下列二个同步条件：l 只有在缓冲池中至少有一个缓冲区已存入消息后，消费者才只有在缓冲池中至少有一个缓冲区已存入消息后，消费者才能从中提取消息，否则消费者必须等待。能从中提取消息，否则消费者必须等待。l 只有缓冲池中至少有一个缓冲区是空时，生产者才能把消息只有缓冲池中至少有一个缓冲区是空时，生产者才能把消息放入缓冲区，否则生产者必须等待。放入缓冲区，否则生产者必须等待。l 为了满足第一个同步条件，设置一个同步信号量为了满足第一个同步条件，设置一个同步信号量fullfull，它代，它代表的资源是缓冲区满，它的初始值为表的资源是缓冲区满，它的初始值为0 0，它的值为，它的值为

12、n n时整个缓时整个缓冲池满。同样为了满足第二个同步条件，设置另一个同步信冲池满。同样为了满足第二个同步条件，设置另一个同步信号量号量emptyempty，它代表的资源是缓冲区空，它的初始值为，它代表的资源是缓冲区空，它的初始值为n n，表，表示缓冲池中所有缓冲区空。示缓冲池中所有缓冲区空。17生产者消费者问题生产者消费者问题Shared datasemaphore full, empty, mutex;Initially:full = 0, empty = n, mutex = 118The structure of Producer Processdo produce an item in

13、 nextp add nextp to buffer while (1);19The structure of the Consumer Processdo remove an item from buffer to nextc consume the item in nextc while (1);20The structure of Producer Processdo produce an item in nextp wait(mutex); add nextp to buffer signal(mutex); while (1);21The structure of the Consu

14、mer Processdo wait(mutex); remove an item from buffer to nextc signal(mutex); consume the item in nextc while (1);22The structure of Producer Processdo produce an item in nextp wait(empty);wait(mutex); add nextp to buffer signal(mutex);signal(full); while (1);23The structure of the Consumer Processd

15、o wait(full);wait(mutex); remove an item from buffer to nextc signal(mutex);signal(empty); consume the item in nextc while (1);讨论wait或signal语句的顺序对进程的影响24分析：在生产者在生产者消费者问题中，如果将两个消费者问题中，如果将两个 wait wait 操作，即操作，即 wait(full)wait(full)和和 wait(mutex)wait(mutex)互换位置，或者互换位置，或者 wait(empty)wait(empty)和和 wait(mu

16、tex)wait(mutex)互换互换位置，都可能引起死锁。位置，都可能引起死锁。考虑系统中缓冲区全满时，若一生产者进程先执行了考虑系统中缓冲区全满时，若一生产者进程先执行了 wait(mutex)wait(mutex)操作并获得成功，当再执行操作并获得成功，当再执行 wait(empty)wait(empty)操作时，它将因失败而进操作时，它将因失败而进入阻塞状态，它期待消费者执行入阻塞状态，它期待消费者执行 signal(empty)signal(empty)来唤醒自己，在此来唤醒自己，在此之前，它不可能执行之前，它不可能执行 signal(mutex)signal(mutex)操作，从而

17、使企图通过操作，从而使企图通过 wait(mutex)wait(mutex)进入自己的临界区的其他生产者和所有的消费者进程全进入自己的临界区的其他生产者和所有的消费者进程全部进入阻塞状态，从而引起系统死锁。类似地，消费者进程若先执部进入阻塞状态，从而引起系统死锁。类似地，消费者进程若先执行行 wait(mutex)wait(mutex)，后执行，后执行 wait(full)wait(full)，同样可能造成死锁。，同样可能造成死锁。 signal(full)signal(full)和和 signal(mutex)signal(mutex)互换位置，或者互换位置，或者 signal(empty)

18、signal(empty)和和 signal(mutex)signal(mutex)互换位置，则不会引起死锁，其影响只是使临界资源互换位置，则不会引起死锁，其影响只是使临界资源的释放略为推迟一些。的释放略为推迟一些。 25课堂问题1、什么是记录型信号量？2、什么是AND型信号量？3、信号量有什么作用？26The structure of Producer Process(使用AND信号量）do produce an item in nextp swait(empty,mutex); add nextp to buffer ssignal(mutex,full); while (1);27The

19、 structure of the Consumer Process(使用AND信号量）do swait(full,mutex); remove an item from buffer to nextc ssignal(mutex,empty); consume the item in nextc while (1);282. 2. 读者写者问题读者写者问题(the readers-writers problem)问题描述：问题描述：对共享资源的读写操作，任一对共享资源的读写操作，任一时刻时刻“写者写者”最多只允许最多只允许一个一个，而，而“读者读者”则允许则允许多多个个 “读写读写”互斥，互

20、斥， “写写写写”互斥，互斥， 读读读读 允许允许2.4 2.4 经典进程同步问题经典进程同步问题29The structure of a Writer Process引人引人互斥信号量互斥信号量 wrt wait(wrt); writing is performed signal(wrt);30The structure of a Reader Process第一个读者到时第一个读者到时wait(wrt); reading is performed 最后一个读者离开时最后一个读者离开时signal(wrt);31The structure of a Reader Process用用readc

21、ount变量来记录读者数，读者变量来记录读者数，读者程序为：程序为：readcount+;if (readcount = 1)wait(wrt); reading is performed readcount-;if (readcount = 0)signal(wrt);32The structure of a Reader Process由于由于readcountreadcount是读者间共享变量，属于临界资源，它也需互斥，为此又是读者间共享变量，属于临界资源，它也需互斥，为此又增设互斥信号量增设互斥信号量mutex wait(mutex); readcount+; if (readcoun

22、t = 1)wait(wrt); signal(mutex); reading is performed wait(mutex); readcount-; if (readcount = 0) signal(wrt); signal(mutex)；思考：想进入临界区的思考：想进入临界区的进程中，哪一类进程的进程中，哪一类进程的优先级高？优先级高？33用一般信号集机制解读者-写者问题采用一般采用一般 信号量集信号量集 机制：问题增加一个限制条件：同时机制：问题增加一个限制条件：同时读的读的 读者读者 最多最多RNRN个个mxmx表示表示 允许写允许写 ，初值是，初值是1 1L L表示表示 允许读

23、者数目允许读者数目 ，初值为，初值为RNRNThe structure of a Reader Process S Swait (L , 1 , 1 ) ; (L , 1 , 1 ) ; S Swait (mx , 1 , 0 ) ; (mx , 1 , 0 ) ; perform read operation perform read operation S Ssignal (L , 1) ; (L , 1) ; 34用一般信号集机制解读者-写者问题-1The structure of a Writer Process S Swait (mx ,1, 1, L , RN , 0 ); (mx

24、 ,1, 1, L , RN , 0 ); perform write operation perform write operation S Ssignal (mx , 1 ) ; (mx , 1 ) ; 35 第二类读者写者问题：第二类读者写者问题：写者优先写者优先条件：条件：1 1）多个读者可以同时进行读）多个读者可以同时进行读2 2）写者必须互斥（只允许一个写者写，也）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）不能读者写者同时进行）3 3）写者优先于读者（一旦有写者，则后续）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）读者必须等待，唤醒时优先考虑写

25、者）【思考】36The structure of a Writer Process引人引人互斥信号量互斥信号量 w，初值设置为，初值设置为1 wait(w); wait(wrt); writing is performed signal(wrt); signal(w);37The structure of a Reader Process由于由于readcount是读者间共享变量，属于临界资源，它也需互斥，为此是读者间共享变量，属于临界资源，它也需互斥，为此又增设互斥信号量又增设互斥信号量mutex wait(w); wait(mutex); readcount+; if (readcount

26、 = 1)wait(wrt); signal(mutex);signal(w); reading is performed wait(mutex); readcount-; if (readcount = 0) signal(wrt); signal(mutex)；383. 3. 哲学家进餐问题哲学家进餐问题(the dining philosophers problem)问题描述：问题描述：（由（由DijkstraDijkstra首先提出并首先提出并解决）解决）5 5个哲学家个哲学家围绕一张围绕一张圆桌圆桌而而坐，桌子上放着坐，桌子上放着5 5把筷子把筷子，每两个，每两个哲学家之间放一把；哲

27、学家的动作哲学家之间放一把；哲学家的动作包括包括思考思考和和进餐进餐，进餐时进餐时需要同时需要同时拿起他左边和右边的两把筷子，拿起他左边和右边的两把筷子，思思考时考时则同时将两把筷子放回原处。则同时将两把筷子放回原处。如何保证哲学家们的动作有序进行如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子；不出现有人永远拿不到筷子；2.4 2.4 经典进程同步问题经典进程同步问题39The structure of Philosophers i semaphore chopstick5;Initially all values are

28、1Philosopher i:do wait(chopsticki)wait(chopstick(i+1) % 5) eat signal(chopsticki);signal(chopstick(i+1) % 5); think while (1);40哲学家就餐问题讨论哲学家就餐问题讨论为防止死锁发生可采取的措施：为防止死锁发生可采取的措施： 最多允许最多允许4 4个哲学家同时坐在桌子周围个哲学家同时坐在桌子周围 仅当一个哲学家左右两边的筷子都可用时，才允许仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子他拿筷子 给所有哲学家编号，奇数号的哲学家必须首先拿左给所有哲学家编号，奇数号的哲

29、学家必须首先拿左边的筷子，偶数号的哲学家则反之边的筷子，偶数号的哲学家则反之 41do 思考；wait(count); wait(chopsticki);wait(chopstick(i+1) % 5)； 进食； signal(chopsticki);signal(chopstick(i+1) % 5)； signal(count); while(1);方法142do 思考；swait(chopsticki,chopstick(i+1) % 5)； 进食； ssignal(chopsticki,chopstick(i+1) % 5); while(1);方法24344do 思考； if (i

30、% 2)=1 wait(chopsticki);wait(chopstick(i+1) % 5)； else wait(chopstick(i+1) % 5)； wait(chopsticki); 进食； signal(chopsticki);signal(chopstick(i+1) % 5)； while(1);方法345The Sleeping Barber Problem (1)46The Sleeping Barber Problem (2)47The Sleeping Barber Problem (3)482.5 2.5 管程管程(monitor)(monitor)机制机制 用信

31、号量可实现进程间的同步，但由于信号量的用信号量可实现进程间的同步，但由于信号量的控制分布在整个程序中，其正确性分析很困难。控制分布在整个程序中，其正确性分析很困难。管程管程是管理进程间同步的机制，它保证进程互斥地访问共是管理进程间同步的机制，它保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程享变量，并方便地阻塞和唤醒进程。管程可以函数库。管程可以函数库的形式实现。相比之下，管程比信号量好控制。的形式实现。相比之下，管程比信号量好控制。491. 1. 信号量同步的缺点信号量同步的缺点同步操作分散同步操作分散：信号量机制中，同步操作分散在各个：信号量机制中，同步操作分散在各个进程中，使用不当就可

32、能导致各进程死锁（如进程中，使用不当就可能导致各进程死锁（如P P、V V操作的次序错误、重复或遗漏）操作的次序错误、重复或遗漏）易读性差易读性差：要了解对于一组共享变量及信号量的操作：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序；是否正确，必须通读整个系统或者并发程序；不利于修改和维护不利于修改和维护：各模块的独立性差，任一组变量：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局；或一段代码的修改都可能影响全局；正确性难以保证正确性难以保证：操作系统或并发程序通常很大，很：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误；难保证这样一

33、个复杂的系统没有逻辑错误；2.5 2.5 管程管程(monitor)(monitor)机制机制502. 2. 管程的引入管程的引入19731973年，年，HoareHoare和和HansonHanson所提出；其基本思想是所提出；其基本思想是把信把信号量及其操作原语封装在一个对象内部号量及其操作原语封装在一个对象内部。即：将共。即：将共享变量以及对共享变量能够进行的所有操作集中在享变量以及对共享变量能够进行的所有操作集中在一个模块中。一个模块中。管程的定义：管程的定义：管程是管程是关于共享资源的数据结构关于共享资源的数据结构及一组及一组针对该资源的针对该资源的操作过程操作过程所构成的所构成的软

34、件模块软件模块。2.5 2.5 管程管程(monitor)(monitor)机制机制51管程可增强模块的独立性管程可增强模块的独立性：系统系统按资源管理的观点按资源管理的观点分分解成解成若干若干模块模块，用数据表示抽象系统资源，同时分，用数据表示抽象系统资源，同时分析了共享资源和专用资源在管理上的差别，按不同析了共享资源和专用资源在管理上的差别，按不同的管理方式定义模块的类型和结构，的管理方式定义模块的类型和结构，使同步操作相使同步操作相对集中对集中，从而增加了模块的相对独立性，从而增加了模块的相对独立性引入管程可提高代码的可读性，便于修改和维护，正引入管程可提高代码的可读性，便于修改和维护，

35、正确性易于保证确性易于保证：采用：采用集中式同步机制集中式同步机制。一个操作系。一个操作系统或并发程序由若干个这样的模块所构成，统或并发程序由若干个这样的模块所构成，一个模一个模块通常较短块通常较短，模块之间关系清晰模块之间关系清晰。2.5 2.5 管程管程(monitor)(monitor)机制机制523. 3. 管程的主要特性管程的主要特性模块化模块化：一个管程是一个基本程序单位，可以单：一个管程是一个基本程序单位，可以单独编译；独编译；抽象数据类型抽象数据类型：管程是一种特殊的数据类型，其：管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码中不仅有数据，而且有对数据进行

36、操作的代码信息封装信息封装：管程是半透明的，管程中的外部过程：管程是半透明的，管程中的外部过程（函数）实现了某些功能，至于这些功能是怎（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的；样实现的，在其外部则是不可见的；2.5 2.5 管程管程(monitor)(monitor)机制机制534. 4. 管程的实现要素管程的实现要素管程中的共享变量在管程外部是不可见的，外部只管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的能通过调用管程中所说明的外部过程外部过程（函数）来（函数）来间接地访问管程中的共享变量；间接地访问管程中的共享变量；为了保证管程共享变量的

37、数据完整性，规定为了保证管程共享变量的数据完整性，规定管程互管程互斥进入斥进入；管程通常是用来管理资源的，因而在管程中应当设管程通常是用来管理资源的，因而在管程中应当设有有进程等待队列进程等待队列以及相应的以及相应的等待及唤醒操作等待及唤醒操作；2.5 2.5 管程管程(monitor)(monitor)机制机制545. 5. 管程中的多个进程进入管程中的多个进程进入当一个进入管程的进程当一个进入管程的进程执行等待操作执行等待操作时，它应当时，它应当释放管程的互释放管程的互斥权斥权；当一个进入管程的进程；当一个进入管程的进程执行唤醒操作执行唤醒操作时（如唤醒时（如唤醒），管程中便存在），管程中

38、便存在两个同时处于活动状态的进程两个同时处于活动状态的进程。管程中的管程中的唤醒切换方法唤醒切换方法： P P等待等待Q Q继续，直到继续，直到Q Q等待或退出；等待或退出； Q Q等待等待P P继续，直到继续，直到P P等待或退出；等待或退出； 规定唤醒为管程中规定唤醒为管程中最后一个可执行的操作最后一个可执行的操作；2.5 2.5 管程管程(monitor)(monitor)机制机制55入口等待队列入口等待队列：因为管程是：因为管程是互斥进入互斥进入的，所以当一个的，所以当一个进程试图进入一个进程试图进入一个巳被占用的管程巳被占用的管程时它应当时它应当在管程在管程的入口处等待的入口处等待，

39、因而在管程的入口处应当有一个进，因而在管程的入口处应当有一个进程等待队列，称作入口等待队列。程等待队列，称作入口等待队列。紧急等待队列紧急等待队列：如果进程唤醒进程，则等待：如果进程唤醒进程，则等待继续，如果进程在执行又唤醒进程，则等待继续，如果进程在执行又唤醒进程，则等待继续，继续，.，如此，在管程内部，由于执行唤醒，如此，在管程内部，由于执行唤醒操作，可能会出现多个等待进程（操作，可能会出现多个等待进程（已被唤醒，但由已被唤醒，但由于管程的互斥进入而等待于管程的互斥进入而等待），因而还需要有一个进），因而还需要有一个进程等待队列，这个等待队列被称为紧急等待队列。程等待队列，这个等待队列被称

40、为紧急等待队列。它的优先级应当高于入口等待队列的优先级它的优先级应当高于入口等待队列的优先级。2.5 2.5 管程管程(monitor)(monitor)机制机制566. 6. 条件变量条件变量(condition)(condition)由于管程通常是用于管理资源的，因而在管程内由于管程通常是用于管理资源的，因而在管程内部，应当存在某种部，应当存在某种等待机制等待机制。当进入管程的进。当进入管程的进程因资源被占用等原因不能继续运行时使其等程因资源被占用等原因不能继续运行时使其等待。为此在管程内部可以说明和使用一种特殊待。为此在管程内部可以说明和使用一种特殊类型的变量类型的变量-条件变量条件变量

41、。每个表示一种等待每个表示一种等待原因，并不取具体数值原因，并不取具体数值相当于每个原因对相当于每个原因对应一个队列。应一个队列。2.5 2.5 管程管程(monitor)(monitor)机制机制57同步操作原语同步操作原语waitwait和和signalsignal：针对条件变量：针对条件变量c c，c.waitc.wait将将自己阻塞在自己阻塞在c c队列中，队列中，c.signalc.signal将将c c队列中的一个进程唤队列中的一个进程唤醒。醒。 c.waitc.wait：如果如果紧急等待队列紧急等待队列非空，则唤醒第一个等待者；否非空，则唤醒第一个等待者；否则释放则释放管程的互斥

42、权管程的互斥权，执行此操作的进程，执行此操作的进程排入排入c c队列尾部队列尾部（紧紧急等待队列与急等待队列与c c队列的关系队列的关系：紧急等待队列是由于管程的互斥：紧急等待队列是由于管程的互斥进入而等待的队列，而进入而等待的队列，而c c队列是因资源被占用而等待的队列）队列是因资源被占用而等待的队列） c.signalc.signal：如果如果c c队列为空，则相当于空操作，执行此操作的队列为空，则相当于空操作，执行此操作的进程继续；否则唤醒第一个等待者，执行此操作的进程排入进程继续；否则唤醒第一个等待者，执行此操作的进程排入紧急等待队列的尾部紧急等待队列的尾部若进程若进程P P唤醒进程唤

43、醒进程Q Q，则随后可有两种执行方式（进程，则随后可有两种执行方式（进程P P、Q Q都是管程中的进程）都是管程中的进程） P P等待，直到执行等待，直到执行Q Q离开管程或下一次等待。离开管程或下一次等待。HoareHoare采用。采用。 Q Q送入送入ReadyReady队列，直到执行队列，直到执行P P离开管程或下一次等待。离开管程或下一次等待。19801980年年，LampsonLampson和和RedellRedell采用。采用。587. 7. 管程的格式管程的格式monitor monitor 管程模块名管程模块名; ;共享变量说明共享变量说明; ;condition condit

44、ion 条件变量条件变量1 1，条件变量，条件变量2 2， , ,条件变量条件变量n;n;过程名（形参表）；过程名（形参表）； 语句序列；语句序列； .2.5 2.5 管程管程(monitor)(monitor)机制机制59函数名（形参表）函数名（形参表） 语句序列；语句序列； . 共享变量初始化语句序列；共享变量初始化语句序列； 608. 8. 管程的组成管程的组成名称名称：为每个共享资源设立一个管程：为每个共享资源设立一个管程数据结构说明：数据结构说明：一组局部于管程的控制变量一组局部于管程的控制变量操作原语：操作原语：对控制变量和临界资源进行操作的一组原对控制变量和临界资源进行操作的一组

45、原语过程（程序代码），是访问该管程的唯一途径。语过程（程序代码），是访问该管程的唯一途径。这些原语本身是互斥的，任一时刻只允许一个进程这些原语本身是互斥的，任一时刻只允许一个进程去调用，其余需要访问的进程就等待。去调用，其余需要访问的进程就等待。初始化代码：初始化代码：对控制变量进行初始化的代码对控制变量进行初始化的代码2.5 2.5 管程管程(monitor)(monitor)机制机制61利用管程解决生产-消费者问题type producer-consumer=monitor var in,out,count:integer; buffer: array 0.n-1 of item; not

46、full, notempty: condition; procedure entry put(item) begin if countn then notfull.wait; buffer(in):=nextp; in:=(in+1) mod n; count:=count+1; if notempty.queue then notempty.signal; end 62procedure entry get(item) begin if count0 then notempty.wait; nextc:=buffer(out); out:=(out+1) mod n; count:=coun

47、t-1; if notfull.quene then notfull.signal; end begin in:=out:=0; count:=0; end 63生产者和消费者可描述为：生产者和消费者可描述为： producer:begin repeat produce an item in nextp; PC.put(item); until false; endcousumer:begin repeat PC.get(item); consumer the item in nextc; until false; end 642.6 2.6 进程通信进程通信低级通信：低级通信：只能传递状态和

48、整数值（控制信息）只能传递状态和整数值（控制信息），包括进程互斥和同步所采用的信号量和管程，包括进程互斥和同步所采用的信号量和管程机制。优点的速度快。缺点是：机制。优点的速度快。缺点是： 传送信息量小：效率低，每次通信传递的信息量固传送信息量小：效率低，每次通信传递的信息量固定，若传递较多信息则需要进行多次通信。定，若传递较多信息则需要进行多次通信。 通信对用户不透明，编程复杂：用户要直接实现通通信对用户不透明，编程复杂：用户要直接实现通信的细节，编程复杂，容易出错。信的细节，编程复杂，容易出错。高级通信：高级通信：能够传送任意数量的数据，包括三类能够传送任意数量的数据，包括三类：共享存储器、

49、管道、消息传递。：共享存储器、管道、消息传递。返回低级通信和高级通信低级通信和高级通信651 1、共享存储系统（、共享存储系统（Shared-Memory SystemShared-Memory System）：）： （1 1）共享数据结构：）共享数据结构：q 进程公用某些数据结构，借以实现进程间的信息交换进程公用某些数据结构，借以实现进程间的信息交换。q 低效，只适于相对少量的数据低效，只适于相对少量的数据 （2 2）共享存储区：）共享存储区： 相互通信的进程间设有公共内存，一组进程向该公共内存中相互通信的进程间设有公共内存，一组进程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实

50、现两组进写，另一组进程从公共内存中读，通过这种方式实现两组进程间的信息交换程间的信息交换2.6 2.6 进程通信进程通信 2.6.1 2.6.1 进程通信的类型进程通信的类型进程通信的类型进程通信的类型662 2、消息传递（、消息传递（Message Passing SystemMessage Passing System）：）：系统为进程提供了两个高级通讯原语系统为进程提供了两个高级通讯原语, ,sendsend和和receive(receive(也有用也有用read)read)qsendsend：当要进行消息传递时执行当要进行消息传递时执行sendsendqreceivereceive：当

51、接收者要接收消息时执行当接收者要接收消息时执行receivereceive2.6 2.6 进程通信进程通信2.6.1 2.6.1 进程通信的类型进程通信的类型67消息传递按实现方式分类：消息传递按实现方式分类：1 1、直接方式：、直接方式：q发送进程直接把消息发送给接受进程。发送进程直接把消息发送给接受进程。q发送进程发消息时要指定接收进程的名字，发送进程发消息时要指定接收进程的名字， 反过来，接收时要指明发送进程的名字反过来，接收时要指明发送进程的名字 Send(receiver,message)Send(receiver,message) Receiver(sender,message)R

52、eceiver(sender,message) 对称形式：一对一对称形式：一对一 非对称形式：多对一非对称形式：多对一 （客户（客户/ /服务器）服务器）q有缓冲（有界，无界），无缓冲有缓冲（有界，无界），无缓冲2.6 2.6 进程通信进程通信682 2、间接方式：、间接方式：q发送进程发消息时不指定接收进程的名字，而是指定一发送进程发消息时不指定接收进程的名字，而是指定一个中间媒介，即信箱。进程间通过信箱实现通信，调用相个中间媒介，即信箱。进程间通过信箱实现通信，调用相应的原语来实现。应的原语来实现。q发送原语：发送原语：send(MB,Message)send(MB,Message)q接收

53、原语：接收原语：receive(MB,Message)receive(MB,Message)q邮箱的类型：私用、公用、共享邮箱的类型：私用、公用、共享 q发送和接收进程的关系：发送和接收进程的关系： 一对一：专用通信链路一对一：专用通信链路 多对一：服务进程与多个用户进程进行交互（客户多对一：服务进程与多个用户进程进行交互（客户/ /服务器）服务器） 一对多：一个发送进程与多个接受进程进行交互一对多：一个发送进程与多个接受进程进行交互 多对多：公共信箱多对多：公共信箱2.6 2.6 进程通信进程通信693 3、管道通信方式、管道通信方式 PipePipe 也称共享文件方式，基于文件系统，利也称

54、共享文件方式，基于文件系统，利用一个打开的共享文件连接两个相互通信的进用一个打开的共享文件连接两个相互通信的进程，文件作为缓冲传输介质程，文件作为缓冲传输介质发送进程发送进程接收进程接收进程q字符流方式写入读出字符流方式写入读出q先进先出顺序先进先出顺序2.6 2.6 进程通信进程通信701 1、消息缓冲（、消息缓冲（Message Buffer)Message Buffer)：一种直接通信方式：一种直接通信方式q HansenHansen于于19731973年首先提出用消息缓冲作为进程通信的基年首先提出用消息缓冲作为进程通信的基本手段。本手段。q 在内存中开设缓冲区，发送进程将消息送入缓冲区

55、，接在内存中开设缓冲区，发送进程将消息送入缓冲区，接收进程接收传递来的缓冲区收进程接收传递来的缓冲区q 消息组成：消息组成：q 消息头：消息在传输时所需的控制信息消息头：消息在传输时所需的控制信息q 消息正文消息正文q 消息缓冲区包括：消息缓冲区包括：q 指向发送进程的指针指向发送进程的指针SptrSptrq 指向下一个消息换冲区的指针指向下一个消息换冲区的指针NptrNptrq 消息长度消息长度SizeSizeq 消息正文消息正文TextText2.6 2.6 进程通信进程通信2.6.2 2.6.2 典型通信方式典型通信方式71消息传递系统消息传递系统-1消息缓冲队列通信原理消息缓冲队列通信

56、原理 消息缓冲队列通信机制的原理是：由系统管理一组缓冲区，其中每个消息缓冲队列通信机制的原理是：由系统管理一组缓冲区，其中每个缓冲区可以存放一个消息。当发送进程要发送消息时先要向系统申请一缓冲区可以存放一个消息。当发送进程要发送消息时先要向系统申请一个缓冲区，然后把消息写进去，接着把该缓冲区连接到接收进程的消息个缓冲区，然后把消息写进去，接着把该缓冲区连接到接收进程的消息缓冲队列中。接收进程可以在适当的时候从消息缓冲队列中摘下消息缓缓冲队列中。接收进程可以在适当的时候从消息缓冲队列中摘下消息缓冲区，读取消息，并释放该缓冲区。冲区，读取消息，并释放该缓冲区。消息缓冲队列通信的数据结构有消息缓冲区

57、和进程消息缓冲队列通信的数据结构有消息缓冲区和进程PCBPCB中有关通信的扩充中有关通信的扩充数据项，消息缓冲区描述如下：数据项，消息缓冲区描述如下：type message buffer=recordtype message buffer=record sender sender ；发送进程的标识符；发送进程的标识符 size size ；消息长度；消息长度 text text ；消息正文；消息正文 next next ；指向下一个消息缓冲区的指针；指向下一个消息缓冲区的指针 endend72消息传递系统消息传递系统-2PCB 有关通信的扩充数据项type PCB = record mute

58、x ；消息缓冲队列互斥信息量 ； Sm ；消息缓冲队列资源信息量 ； mq ；消息缓冲队列首指针 ； End73消息缓冲通信 sender：Asize：5text：Hellomqmutexsmsender：Asize：5text：Hellonext：0send (B, a)第一消息缓冲区sender：Asize：5text：Helloreceive (b)a发送区ab接收区b进程BPCB(B)进程A74图图: :消息缓冲队列通信的发送和接收过程消息缓冲队列通信的发送和接收过程 系统管理的组缓冲区系统管理的组缓冲区 进程进程A 进程进程B PCB 进程进程B . mutex sm mq . .

59、.send(B,a);sender :Asize : 13text :How are you?Nextsend :Asize :13text:H o w a r e you?Next:sender :Asize :5text :HelloNext : sender :Asize:13text:H o w a r e you?Next:0sender :Asize :5text :HelloNext:.receive(b);sender :Asize :5text :Hello75消息传递系统消息传递系统-3发送原语发送原语Proceduce send (receiver,a)Proceduce

60、 send (receiver,a) begin begin getbuf(a.size getbuf(a.size，i) i) ；申请；申请 i.sender = a.senderi.sender = a.sender；复制；复制 i i.size = a.size size = a.size ； i.text = a.text i.text = a.text ； i i.next = 0 next = 0 ； getid (PCB set , receiver getid (PCB set , receiver ，j) j) ；获取接收进程；获取接收进程P(j.mutex) P(j.mutex) ；insert(j.mqinsert(j.mq，i