《计算机操作系统原理-5.pdf》由会员分享，可在线阅读，更多相关《计算机操作系统原理-5.pdf（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、清华大学出版社1/19第第5章章 并发性并发性:互斥、同步和通信互斥、同步和通信并发执行的各个进程之间，既有独立性独立性，又有制约性制约性。独立性：独立性：各进程可独立地向前推进制约性：制约性：一个进程会受到其他进程的影响，这种影响关系可能有：互斥互斥同步同步通信通信清华大学出版社2/19第第5章章 并发性并发性:互斥、同步和通信互斥、同步和通信5.1 5.1 并发的原理并发的原理5.2 5.2 信号量机制信号量机制5.3 5.3 管程机制管程机制5.4 5.4 进程通信进程通信清华大学出版社3/195.1 并发的原理并发的原理5.1.1 与时间有关的错误5.1.2 互斥与同步的概念5.1.3
2、 临界区与进程互斥5.1.4 硬件支持互斥的方法清华大学出版社4/195.1.1 与时间有关的错误与时间有关的错误例：Pl，P2两并发进程共享变量count，如果按如下顺序运行：P1：R1=count；R1=R1+1；count=R1；P2:R2=count；R2=R2+1；count=R2；结果结果:count的值的值+2，正确正确清华大学出版社5/195.1.1 与时间有关的错误与时间有关的错误如果Pl，P2按如下顺序运行：P1：R1=count；R1=R1+1；count=R1；P2:R2=count；R2=R2+1；count=R2；结果结果:count的值的值+1,错误！错误！清华大
3、学出版社6/195.1.1 与时间有关的错误与时间有关的错误原因：1、共享了变量；、共享了变量；2、“同时”使用了这个变量。、“同时”使用了这个变量。解决办法：1、取消共享、取消共享（）2、允许共享，不允许同时使用、允许共享，不允许同时使用（）-进程互斥进程互斥清华大学出版社7/195.1.2 互斥与同步的概念互斥与同步的概念1、进程间两种形式的制约关系、进程间两种形式的制约关系间接制约关系：间接制约关系：进程间要通过某种中介发生联系，是无意识安排的。直接制约关系：直接制约关系：进程间的相互联系是有意识的安排的。清华大学出版社8/192 2、进程的同步（直接制约）、进程的同步（直接制约）进程的
4、同步：进程的同步：synchronismsynchronism指系统中多个进程中发生的事件存在某种时指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就该进程处于等待状态，获得消息后被唤醒进入就绪态绪态5.1.2 互斥与同步的概念互斥与同步的概念清华大学出版社9/19例例:司机司机P1 P1 售票员售票员P2P2while(truew
5、hile(true）while(true)while(true)启动车辆；启动车辆；关门；关门；正常运行；正常运行；售票；售票；到站停车；到站停车；开门；开门；5.1.2 互斥与同步的概念互斥与同步的概念清华大学出版社10/193 3、进程的互斥（间接制约）、进程的互斥（间接制约）mutual exclusion由于各进程要求共享资源，而有些资由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的用这些资源，进程的这种关系为进程的互斥。互斥。5.1.2 互斥与同步的概念互斥与同步的概念清华大学出版社11/195.1
6、.3 临界区与进程互斥临界区与进程互斥1 1、临界资源、临界资源(critical resource(critical resource）系统中某些资源一次只允许一个进程使系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源用，称这样的资源为临界资源或互斥资源或共享变量。或共享变量。2、临界区（互斥区）：、临界区（互斥区）：critical section在进程中涉及到临界资源的程序段叫临临界区界区多个进程的临界区称为相关临界区相关临界区清华大学出版社12/19进程的互斥（间接作用）进程的互斥（间接作用）a:=a+1 print(a)P1 互斥互斥a:=a-1 print(a
7、)P2互斥互斥If a 0then a:=a+1else a:=a-1 P3互斥互斥临界区的例子临界区的例子清华大学出版社13/19程序程序段段1共享变量共享变量程序程序段段2程序程序段段3临界区的例子临界区的例子清华大学出版社14/19While(1)While(1)进入区代码进入区代码;临界区代码临界区代码;退出区代码退出区代码;其余代码其余代码;3 3、实现各进程互斥进入临界区、实现各进程互斥进入临界区进程须在临界区前面增加一段用于进行上述检查的代码，称为进入区(entry section)。在临界区后面加上一段称为退出区(exit section)的代码5.1.3 临界区与进程互斥临界
8、区与进程互斥清华大学出版社15/19空闲让进：空闲让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入忙则等待：忙则等待：不允许两个以上的进程同时进入互斥区有限等待：有限等待：任何进入互斥区的要求应在有限的时间内得到满足让权等待：让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权4 4、使用互斥区的原则：使用互斥区的原则：5.1.3 临界区与进程互斥临界区与进程互斥清华大学出版社16/195 5、进程互斥的解决主要有两种、进程互斥的解决主要有两种:硬件方法：硬件方法：分为中断禁用、专用机器指令两种（5.1.4节节）软件软件方法：方法：用编程解决，包括操作系统
9、或程序设计语言中提供某种级别的支持，比如信号量机制和管程机制（5.25.3节节），但常常忙等待5.1.3 临界区与进程互斥临界区与进程互斥清华大学出版社17/195.1.4 硬件支持互斥的方法硬件支持互斥的方法1 1中断禁用中断禁用为保证互斥，只需保证进程不被中断就可以了，通过系统内核为启用中断和禁用中断定义的原语实现。进程结构：While(true)禁用中断禁用中断;临界区临界区;启用中断启用中断;其余部分其余部分;缺点：缺点：效率低，不能用于多处理器结构。清华大学出版社18/195.1.4 硬件支持互斥的方法硬件支持互斥的方法2专用机器指令专用机器指令可用于多处理器机器，2条硬件指令：te
10、stsettestset指令 和exchangeexchange指令testsettestset指令定义：指令定义：boolean testset(int i)if(i=0)i=1;return true;else return false;清华大学出版社19/195.1.4 硬件支持互斥的方法硬件支持互斥的方法testsettestset指令实现进程的互斥访问指令实现进程的互斥访问设置个共享变量bolt，其初值=0，代表资源空闲，其值为1代表资源被占用。实现互斥的各个进程为：while(true)while(!testset(bolt);/*当资源占用时等待当资源占用时等待*/临界区临界区;
11、bolt=0;其余部分其余部分;清华大学出版社20/195.1.4 硬件支持互斥的方法硬件支持互斥的方法exchangeexchange指令定义：指令定义：void exchange(int register,int memory)int temp;temp=memory;memory=register;register=temp;该指令交换一个寄存器和一个存储单元的内容清华大学出版社21/195.1.4 硬件支持互斥的方法硬件支持互斥的方法exchangeexchange指令实现进程的互斥访问指令实现进程的互斥访问设置一个共享变量bolt,初值为0,各个并发的进程设置一个局部变量key,初值
12、为1。实现互斥的各个进程描述为：while(true)key=1while(key!=0)exchange(key,bolt);临界区临界区;exchange(key,bolt);其余部分其余部分;清华大学出版社22/195.1.4 硬件支持互斥的方法硬件支持互斥的方法特点：特点：唯一可以进入临界区的进程是发现bolt等于0的进程，它将bolt置1排斥其它进程进入临界区。当该进程离开临界区时将bolt重新置0，允许另一个进程进入临界区。缺点：缺点：不能满足“让权等待”的准则，造成处理机空等（忙等忙等）。且只能解决互斥，不能用于同步。信号量机制能完满地解决上述问题。清华大学出版社23/195.2
13、 信号量机制信号量机制5.2.1 信号量的概念5.2.2 信号量的应用5.2.3 生产者消费者问题5.2.4 哲学家进餐问题5.2.5 读者写者问题清华大学出版社24/195.2.1 5.2.1 信号量的概念信号量的概念信号量信号量(semaphore(semaphore，信号灯，信号灯)定义定义信号量说明：信号量说明：semaphore s;semaphore s;是一个记录型数据结构是一个记录型数据结构定义如下：定义如下：struc semaphore struc semaphore int value;int value;pointer_PCB queue;pointer_PCB que
14、ue;清华大学出版社25/195.2.1 5.2.1 信号量的概念信号量的概念 P P、V V操作操作除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。很长时间以来，这两个操作一直被称为P、V操作。原子操作原子操作（atomic action）或简称“原语原语”(primitive)：在执行上不可中断的操作。清华大学出版社26/195.2.1 5.2.1 信号量的概念信号量的概念 P P、V V操作定义操作定义P(s)P(s)/*=wait(s)/*=wait(s)）*/s.value=s.values.value=s.value;if(s.value 0)if(
15、s.value 0)block(s.queue)block(s.queue)V(s)V(s)/*=signal(s)*/*=signal(s)*/s.value=s.value+;s.value=s.value+;if(s.value=0)if(s.value 0 表示有S个资源可用S=0 表示无资源可用S0 则|S|表示S等待队列中的进程个数2)2)P P、V V操作的含义操作的含义P(S):表示申请一个资源V(S)：表示释放一个资源。信号量的初值应0清华大学出版社28/195.2.2 5.2.2 信号量的应用信号量的应用利用信号量实现进程互斥利用信号量实现进程互斥while(true)P(
16、mutex);critical section;V(mutex);remainder section;while(true)P(mutex);critical section;V(mutex);remainder section;Process1:Process2:清华大学出版社29/195.2.2 5.2.2 信号量的应用信号量的应用P(mutex)V(mutex)P1P2P3互斥区互斥区P(mutex)P(mutex)V(mutex)V(mutex)清华大学出版社30/195.2.2 5.2.2 信号量的应用信号量的应用利用信号量实现前驱关系（利用信号量实现前驱关系（同步例子）P1P2设置
17、一个信号量S，其初值为0,P1；V(S);P(S)；P2;如此即可实现先执行P1，再执行P2清华大学出版社31/195.2.2 5.2.2 信号量的应用信号量的应用利用信号量实现前驱关系利用信号量实现前驱关系S1S2S3S4S5S6设5个信号量semaphore fl=f2=f3=f4=f5=O；含义：含义：分别表示进程S1、S2、S3、S4、S5是否执行完成。清华大学出版社32/195.2.2 5.2.2 信号量的应用信号量的应用各个进程的结构为：各个进程的结构为：void S1()V(f1);V(f1);V(f1);V(f1);void S2()P(f1);P(f1);V(f2);V(f2
18、);V(f2);V(f2);void S3()P(f1);P(f1);V(f3);V(f3);void S4()P(f2);P(f2);V(f4);V(f4);void S5()P(f2);P(f2);V(f5);V(f5);void S6()P(f3);P(f3);P(f4);P(f4);P(f5);P(f5);清华大学出版社33/195.2.3 5.2.3 生产者生产者消费者问题消费者问题单缓冲区单缓冲区：生产者进程P和消费者进程C共用一个缓冲区，P生产产品放入缓冲区，C从缓冲区取产品来消费。消费者消费者生产者生产者清华大学出版社34/195.2.3 5.2.3 生产者生产者消费者问题消费
19、者问题单缓冲区的同步问题单缓冲区的同步问题P进程不能往“满”的缓冲区中放产品，设置信号量为emptyC进程不能从“空”的缓冲区中取产品，设置信号量full单缓冲区的互斥问题单缓冲区的互斥问题P、C进程不能同时使用缓冲区清华大学出版社35/195.2.3 5.2.3 生产者生产者消费者问题消费者问题单缓冲区的生产者单缓冲区的生产者消费者问题解消费者问题解P：C：while (true)while (true)生产一个产品生产一个产品;P(full);P(empty);从缓冲区取产品从缓冲区取产品;送产品到缓冲区送产品到缓冲区;V(empty);V(full);消费产品消费产品;empty初值为初
20、值为1，full初值为初值为0清华大学出版社36/195.2.3 5.2.3 生产者生产者消费者问题消费者问题多个缓冲区多个缓冲区：若干个生产者进程P1,P2,Pn，若干个消费者进程Cl，C2，Cm。它们通过一个有界缓冲池(k个)联系。.PC生产者消费者kk个 Buffernm清华大学出版社37/195.2.3 5.2.3 生产者生产者消费者问题消费者问题多缓冲区的同步互斥问题多缓冲区的同步互斥问题同步：同步：当缓冲池已放满了产品时(供过于求)，生产者进程必须等待；当缓冲池已空时(供不应求)，消费者进程应等待。互斥：互斥：所有进程应互斥使用缓冲池这一临界资源。清华大学出版社38/195.2.3
21、 5.2.3 生产者生产者消费者问题消费者问题多缓冲区的生产者多缓冲区的生产者消费者问题解法消费者问题解法设置三个信号量mutex，empty，full的初始值分别为1，n，0；思考：思考：P操作的顺序可换吗？操作的顺序可换吗？清华大学出版社39/195.2.3 5.2.3 生产者生产者消费者问题消费者问题注意：注意：此解中，无论是生产者进程还是消费者进程，V操作的次序无关紧要操作的次序无关紧要，但P操作的操作的次序不能随意交换次序不能随意交换，否则可能造成死锁。例如，若将生产者进程中的P(empty)与P(mutex)的次序交换，则在一定条件下就会出现死锁现象。清华大学出版社40/195.2
22、.4 5.2.4 哲学家进餐问题哲学家进餐问题5个哲学家围坐在圆桌旁，每人面前有一只空盘子，每2人之间放一只筷子，如图所示。为了就餐，每个哲学家必须拿到两只筷子，并且只能直接从自己的左边或右边去取筷子。图图5 5.3 3哲学家进餐问题哲学家进餐问题清华大学出版社41/195.2.4 5.2.4 哲学家进餐问题哲学家进餐问题-解解Semaphore chopstick5=1；/为每支筷子设置一个信号量为每支筷子设置一个信号量哲学家哲学家i的活动为：的活动为：void philosopher(int i)while(true)思考；思考；P(chopsticki)；/取左边筷子取左边筷子P(cho
23、pstick(i+1)%5)；/取右边筷子取右边筷子进食；进食；V(chopsticki)；/放左边筷子放左边筷子V(chopstick(i+1)%5)；/放右边筷子放右边筷子清华大学出版社42/195.2.4 5.2.4 哲学家进餐问题哲学家进餐问题如果：如果：5人同时拿起左边筷子，再企图拿起右边的筷子时，会如何？死锁！死锁！清华大学出版社43/195.2.4 5.2.4 哲学家进餐问题哲学家进餐问题为防止死锁发生可采取的措施：为防止死锁发生可采取的措施：最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子
24、，偶数号的哲学家则反之为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿清华大学出版社44/195.2.5 5.2.5 读者读者写者问题写者问题有两组并发进程有两组并发进程:读者和写者，共享一组数据区要求：要求：允许多个读者同时执行读操作不允许读者、写者同时操作不允许多个写者同时操作清华大学出版社45/195.2.5 5.2.5 读者读者写者问题写者问题读者读者-写者问题有两种类型：写者问题有两种类型：第一类：读者优先第一类：读者优先附解附解当写者提出了写的要求后，允许允许新的新的读者继续进入（）第二类：写者优先第二类：写者优先当写者提出了写的要求后，不允许不
25、允许新的新的读者进入清华大学出版社46/195.2.5 5.2.5 第第1 1类读者类读者写者问题写者问题-解解读者进程：while(true)P(mutex);readcount+;if(readcount=1)P(wrt);V(mutex);读P(mutex);readcount-;if(readcount=0)V(wrt);V(mutex);写者进程：while(true)P(wrt);写V(wrt);初值说明：初值说明：wrt=1:能否写能否写mutex=1:互斥访问互斥访问readcountReadcount=0:读进程数读进程数清华大学出版社47/19信号量应用小结信号量应用小结P
26、.V操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要清华大学出版社48/195.3 管程机制管程机制管程的提出管程的提出采用PV同步机制来编写并发程序，对于共享变量及信号量变量的操作将被分散于各个进程中缺点：（）易读性差易读性差，因为要了解对于一组共享变量及信号量的操作是否正确，则必须通读整个系统或者并发程序清华大学出版社49/195.3 管程机制管程机制（）不利于修改和维
27、护不利于修改和维护，因为程序的局部性很差，所以任一组变量或一段代码的修改都可能影响全局（）正确性难以保证正确性难以保证，因为操作系统或并发程序通常很大，要保证这样一个复杂的系统没有逻辑错误是很难的解决上述问题的过程中，产生了种新的进程同步工具-管程（管程（Monitor）清华大学出版社50/195.3 管程机制管程机制5.3.1 管程的概念5.3.2 生产者消费者问题5.3.3 哲学家进餐问题清华大学出版社51/195.3.1 5.3.1 管程的概念管程的概念定义定义：管程定义了一个数据结构和在该数据结构上能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。管程的结构管程的结构
28、：(1)管程所管理的共享数据结构管程所管理的共享数据结构(变量变量)，这些数，这些数据结构是对相应临界资源的抽象；据结构是对相应临界资源的抽象；(2)建立在该数据结构上的一组操作建立在该数据结构上的一组操作(函数函数)；(3)对上述数据结构置初值的语句。对上述数据结构置初值的语句。1 1管程的定义管程的定义清华大学出版社52/195.3.1 5.3.1 管程的概念管程的概念管程的示意图共享数据一组操作过程初始化代码进入队列条件(不忙)队列清华大学出版社53/195.3.1 5.3.1 管程的概念管程的概念管程的语法管程的语法：Monitor monitor-name;*管程名字管程名字*/以下
29、为共享变量说明以下为共享变量说明define 本管程内所定义、本管程外可调用的过本管程内所定义、本管程外可调用的过程（函数）名字表程（函数）名字表use 本管程外所定义、本管程内将调用的过本管程外所定义、本管程内将调用的过程（函数）名字表程（函数）名字表清华大学出版社54/195.3.1 5.3.1 管程的概念管程的概念Void Entry Pl()*对数据结构进行操作的函对数据结构进行操作的函数数*Void Entry P2()Void Entry Pn()Initialization；*设置初始值的语句设置初始值的语句*清华大学出版社55/195.3.1 5.3.1 管程的概念管程的概念管
30、程的几点说明：管程的几点说明：管程（相当于围墙）把共享变量和对它进行操作的若干过程围起来。管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量为了保证管程共享变量的数据完整性，规定管程管程互斥进入，互斥进入，由编译程序 实现管程通常是用来管理资源管理资源的，因而在管程中应当设有进程等待队列设有进程等待队列以及相应的等待等待及唤醒唤醒操作清华大学出版社56/195.3.1 5.3.1 管程的概念管程的概念因为因为管程管程是是互斥进入互斥进入的，所以当一个进程试图进的，所以当一个进程试图进入一个巳被占用的管程时它应当在管程的入口处等待，入
31、一个巳被占用的管程时它应当在管程的入口处等待，因而在管程的入口处应当有一个进程等待队列，称作因而在管程的入口处应当有一个进程等待队列，称作入口等待队列入口等待队列如果进程唤醒进程，则等待继续，如果如果进程唤醒进程，则等待继续，如果进程在执行又唤醒进程，则等待继续，进程在执行又唤醒进程，则等待继续，如此，在管程内部，如此，在管程内部，由于执行唤醒由于执行唤醒操作，可能会操作，可能会出现出现多个多个等待进程等待进程，因而还需要有一个进程等待队列，这，因而还需要有一个进程等待队列，这个等待队列被称为个等待队列被称为紧急等待队列紧急等待队列。它的优先级应当高。它的优先级应当高于入口等待队列的优先级于入
32、口等待队列的优先级清华大学出版社57/195.3.1 5.3.1 管程的概念管程的概念2 2条件变量条件变量为了区别各种不同等待原因，在管程内设置若干为了区别各种不同等待原因，在管程内设置若干条件变条件变量量，局限于管程，并仅能从管程内进行访问。，局限于管程，并仅能从管程内进行访问。VAR C:condition;对于条件型变量，可以执行wait和signal操作：wait（c）：如果紧急等待队列非空，则唤醒第一个等待者；否则释放管程的互斥权，本进程进入c变量的等待队列链。signalsignal（c c）：）：如果c链为空，则相当于空操作，执行此操作的进程继续；否则唤醒第一个等待者，本进程的
33、PCB入紧急等待队列的尾部清华大学出版社58/195.3.1 5.3.1 管程的概念管程的概念2 2条件变量条件变量问题：多个进程出现在管程中问题：多个进程出现在管程中当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权；当一个进入管程的进程执行唤醒操作时（如唤醒），管程中便存在两个同时处于活动状态的进程处理方法有三种：处理方法有三种：等待继续，直到退出或等待（Hoare）等待继续，直到等待或退出规定唤醒为管程中最后一个可执行的操作清华大学出版社59/195.3.2 5.3.2 生产者生产者消费者问题消费者问题利用管程解生产者利用管程解生产者-消费者问题，首先是要建消费者问题，首先是要建
34、立一个管程，不妨命名为立一个管程，不妨命名为PC管程：管程：Monitor PC；共享变量定义;void Entry put(item)if countn then notfull.wait;/缓冲区满，进入等待队列bufferin=item;in=(in+1)mod n;count+;if notempty.queue then notempty.signal;/如果有进程因为缓冲区空而等待，唤醒它清华大学出版社60/195.3.2 5.3.2 生产者生产者消费者问题消费者问题void Entry get(item)if count0 then notempty.wait;/缓冲区空，进入等
35、待队列item=buffer out;out=(out+1)mod n;count-;if notfull.quene then notfull.signal;/如果有进程因为缓冲区满而等待，唤醒它 in=out=count=0;/*管程初始化*/清华大学出版社61/195.3.2 5.3.2 生产者生产者消费者问题消费者问题生产者和消费者进程为:producer(int i)while(true)produce an item in nextp;PC.put(nextp);consumer(int i)while(true)PC.get(nextc);consume the item in
36、nextc;清华大学出版社62/195.3.3 5.3.3 哲学家进餐问题哲学家进餐问题把哲学家分为三种状态：思考，饥饿，把哲学家分为三种状态：思考，饥饿，进食，并且一次拿到两只筷子，否则不进食，并且一次拿到两只筷子，否则不拿拿管程中设置了两个数组：管程中设置了两个数组：(thinking，hungry，eating)state5；表示哲学家处于三种不同的状态：进餐、饥饿和思考。condition self5；条件变量，当哲学家饥饿，而又不能获得进餐所需的筷子时，可以通过执行self(i).wait操作，来推迟自己的进餐。清华大学出版社63/195.3.3 5.3.3 哲学家进餐问题哲学家进餐
37、问题管程中设置了三个函数：管程中设置了三个函数：pickupi(外部函数外部函数)。如哲学家处于饥饿状态，且左、右两位哲学家都未进餐，允许这位哲学家进餐；但只要其左、右两位哲学家中有一位正在进餐，将执行selfiwait操作来推迟进餐。putdowni 函数函数(外部函数外部函数)。当哲学家进餐毕，通过该函数放下其手中的筷子。testi(内部函数内部函数)。测试哲学家是否已具备用餐条件，若为真，允许该哲学家进餐，否则，哲学家等待。该函数只能被本管程内的两个外部函数pickup和putdown调用，不能由进程直接调用。清华大学出版社64/195.3.3 5.3.3 哲学家进餐问题哲学家进餐问题利
38、用管程解哲学家进餐问题，要建立一个管利用管程解哲学家进餐问题，要建立一个管程程：Monitor Dining-Philosophers；共享变量定义;void Entry pickup(int i)statei=hungry;test(i);if statei!=eating selfi.wait;清华大学出版社65/195.3.3 5.3.3 哲学家进餐问题哲学家进餐问题void Entry putdown(int i)statei=thinking;test(i+4)%5);test(i+1l)%5);void test(int k)if(state(k+4)%5!=eating)&(st
39、atek=hungry)&(statek+1 mod 5!=eating)statek=eating;selfk.signal;清华大学出版社66/195.3.3 5.3.3 哲学家进餐问题哲学家进餐问题for(i=0;4;i+)/*管程初始化管程初始化*/statei=thinking;有了管程Dining-Philosophers以后，哲学家进程可描述如下:void philosopher(int i)while(true)thinking;pickup;eating;putdown;清华大学出版社67/195.4 5.4 进程通信进程通信进程通信：指的是并发进程之间相互交换信息，这种信息
40、交换的量可大可小。从某种意义上说，前面所讨论的进程之间的互斥与同步就是一种通信，只不过交换的信息量很小，因此这种进程通信方式称为低级进程通信方式低级进程通信方式。本节所讨论的通信，强调的是进程之间有较大信息量的交换，例如一进程向另一进程传送其获得的计算结果，称为高级通信方式高级通信方式。清华大学出版社68/195.4 5.4 进程通信进程通信5.4.1 进程通信的方式5.4.2 消息缓冲通信5.4.3 信箱通信5.4.4 共享文件通信5.4.5 消息传递系统的若干问题清华大学出版社69/195.4.1 5.4.1 进程通信的方式进程通信的方式高级进程通信机制可分为三大类：1.共享存储器系统共享
41、存储器系统(Shared-Memory System)2.消息传递系统消息传递系统(Message passing system)（1）直接通信方式：）直接通信方式：消息缓冲通信（2）间接通信方式：）间接通信方式：又称为信箱通信方式3.管道管道(Pipe)通信通信：又名共享文件通信清华大学出版社70/195.4.2 5.4.2 消息缓冲通信消息缓冲通信是一种直接通信方式，操作系统提供消息缓冲区。当一进程向另一进程发送消息时，便向系统申请一个缓冲区，并把已制备好的消息从发送区复制到该缓冲区，然后把它插入接收进程的消息链中。操作系统提供下述两个通信命令(原语)：Send(Receiver,mess
42、age)：发送消息Receive(Sender,message)：接收消息清华大学出版社71/195.4.2 5.4.2 消息缓冲通信消息缓冲通信消息缓冲通信示意图清华大学出版社72/195.4.2 5.4.2 消息缓冲通信消息缓冲通信在某些情况下，接收进程可与多个发送进程通信，因此，它不可能事先指定发送进程。例如，用于提供打印服务的进程，它可以接收来自任何一个进程的“打印请求”消息。接收原语可表示为：Receive(id,message)其中id是完成通信后的返回值。清华大学出版社73/195.4.3 5.4.3 信箱通信信箱通信是一种间接通信方式间接通信方式，通信时发送进程它的信件投入信箱
43、，接收进程可以在任何时候取走信件而不会丢失，进程间通过信箱实现通信。单向信箱通信单向信箱通信：只要信箱中有空格，发送进程便可向信箱中投递信件，若所有格子都已装满，则发送进程等待，或者继续执行，待有空格子时再发送。只要格子中有信，接收进程便能取出信件。若信箱为空，接收进程或者等待，或者继续执行。清华大学出版社74/195.4.3 5.4.3 信箱通信信箱通信双向信箱通信双向信箱通信：信箱中既有发送进程发出的信件，也有接收进程的回答信件。由于发送进程和接收进程均以各自独立的速度向前推进，当发送进程发送信件的速度超过接收进程的接收速度时，会产生上溢上溢(信箱满)。反之，会产生下溢下溢，即接收进程向空
44、信箱索取信件。这就需要在两个进程之间进行同步控制。清华大学出版社75/195.4.3 5.4.3 信箱通信信箱通信利用信箱通信时，发送进程和接收进程之间，存在以下四种关系：1 1、1 1对对1 12 2、多对、多对1 13 3、1 1对多对多4 4、多对多、多对多清华大学出版社76/195.4.4 5.4.4 共享文件通信共享文件通信消息缓冲通信和信箱通信有三个问题：占用了宝贵的内存空间；占用了宝贵的内存空间；通信信息在停电或关机后便会丢失通信信息在停电或关机后便会丢失(由内由内存物理特性决定存物理特性决定)发送和接收必须以整个消息或信件为单位，发送和接收必须以整个消息或信件为单位，不能存取其
45、中的一部分不能存取其中的一部分共享文件通信：共享文件通信：信息交换量可以很大，发送和接收更加灵活，信息保存期也较长。缺点是信息的交换涉及到IO操作，同步和控制机构也较为复杂。清华大学出版社77/195.4.4 5.4.4 共享文件通信共享文件通信共享文件方式，又称管道通信，基于文件系统，利用一个打开的共享文件连接两个相互通信的进程，文件作为缓冲传输介质发送进程发送进程接收进程接收进程字符流方式写入读出字符流方式写入读出先进先出顺序先进先出顺序清华大学出版社78/195.4.55.4.5消息传递系统的若干问题消息传递系统的若干问题1通信链路通信链路(communication link)根据建立
46、方式：显式的“建立”命令建立，显式拆除显式的“建立”命令建立，显式拆除利用系统发送命令利用系统发送命令(原语原语)，系统自动建立，系统自动建立根据链路的连接方法：点点-点连接通信链路点连接通信链路多点连接链路多点连接链路清华大学出版社79/195.4.55.4.5消息传递系统的若干问题消息传递系统的若干问题1通信链路通信链路(communication link)根据通信方式单向通信链路单向通信链路双向通信链路双向通信链路根据通信链路容量无容量通信链路无容量通信链路有容量通信链路有容量通信链路清华大学出版社80/195.4.55.4.5消息传递系统的若干问题消息传递系统的若干问题2消息的格式消
47、息的格式一个消息分成消息头消息头和消息正文消息正文两部分。消息头包括消息在传输时所需的控制信息，如源进程名、目标进程名、消息长度、消息类型、消息编号及发送的日期和时间；而消息正文则是发送进程实际上所发送的数据。在某些OS中，消息是采用比较短的定长消息格式，在有的OS中，采用另一种变长的消息格式，很多系统(包括计算机网络)中，是同时都用的。清华大学出版社81/195.4.55.4.5消息传递系统的若干问题消息传递系统的若干问题3进程同步方式：进程同步方式：发送和接收进程，在完成消息的发送或接收后，都存在进程或者继续发送(接收)，或者阻塞。有三种情况：(1)发送进程阻塞、接收进程阻塞。(2)发送进程不阻塞、接收进程阻塞。(3)发送进程和接收进程均不阻塞。清华大学出版社82/19第5章结束