第四章互斥同步与通讯课件.ppt

1、进程进程(线程线程)之间的相互作用：之间的相互作用：互斥、同步、通讯互斥、同步、通讯4.1 并发进程并发进程(concurrent processes)4.2 进程进程互斥互斥(mutual exclusion)4.3 进程进程同步同步(synchronization)4.4 进程高级进程高级通讯通讯(communication)4.1.1 顺序程序及其特性顺序程序及其特性程序的顺序性程序的顺序性有两层含义:(1)内部顺序性：指一个进程的所有指令 按序执行按序执行;(2)外部顺序性：指多个进程依次执行依次执行;例如,假设有两个进程P1和P2：P1活动:a1 a2 a3 a4 P2活动:b1 b

2、2 b3 顺序执行时,有如下两种情形:情形1:a1 a2 a3 a4 b1 b2 b3 情形2:b1 b2 b3 a1 a2 a3 a4 顺序程序的特性顺序程序的特性：(1)顺序性顺序性：处理机严格按指令次序依次执行，仅当一条指令执行完才开始执行下一指令；(2)封闭性封闭性：程序在执行过程中独占系统的全部 资源。该程序的运行环境只与其自身动作有 关，不受其它程序及外界因素影响；(3)可再现性可再现性：程序的执行结果只与初始条件有 关，与执行速度无关。给定相同的初始条件 ，程序的任意多次执行一定得到相同结果。4.1.2 并发程序及其特性并发程序及其特性程序的并发性程序的并发性有两层含义:(1)内

3、部并发性内部并发性：指一个进程的所有指令不一定不一定 按序执行;(2)外部并发性外部并发性:指多个进程交叉执行交叉执行。例如，假设有两个进程：P1活动:a1 a2 a3 a4 P2活动:b1 b2 b3 内部并发性如内部并发性如：P2:b1,b3,b2;外部并发性如外部并发性如:情形1:a1 b1 b2 a2 a3 b3 a4 情形2:b1 b2 a1 a2 a3 b3 a4 并发进程在执行过程中出现哪种交叉情形是不可预知的,这就是并发程序的不确定性并发程序的不确定性。并发程序的特性并发程序的特性：(1)交叉性交叉性：一个进程的某些指令可交叉执行，不同的进程亦可交叉执行；程序并发执行时，不同的

4、交叉可能导致不同的 计算结果。OS应保证只产生导致正确结果的交 叉，去除那些可能导致不正确结果的交叉。(2)非封闭性非封闭性：一个进程的运行环境可能被其它进 程改变，从而相互影响。(3)不可再现性不可再现性：并发程序的多次执行可能对应不 同的交叉，因而不能期望重新运行的程序能够 再现上次运行的结果。如运行时间4.1.2 与时间有关的错误与时间有关的错误例如 图书借阅系统(设x:某种书册数，当前x=1)终端1：终端2：CYCLE CYCLE 等待借书者；等待借书者；IF x=1 Then IF x=1 Then Begin Begin x:=x-1;x:=x-1;借书 借书 End End El

5、se 无书 Else 无书 End End 1234 上述错误的发生与进程的推进速度有关(速度是时间的函数)。当进程P1执行到处被中断,之后P2插入,则不会发生上述错误。若一种错误的发生与进程的推进速度有关，则称这种错误为与时间有关的错误与时间有关的错误。发生与时间有关错误与时间有关错误的原因：(1)进程执行交叉(interleave)。(2)涉及公共变量(x)。若两个进程同时对变量x进行操作,其中一个进程对x的操作仅做了一部分时,另一个进程中途插入，则可能使变量x处于一种不确定状态，从而失去其数据完整性。OS必须防止这种情况的发生。进程互斥进程互斥是进程间发生的一种间接相互作用,这种相互作用

6、是进程本身不希望的,也是运行进程感觉不到的。进程互斥可能发生在相关进程之间进程互斥可能发生在相关进程之间,也可也可能发生在无关进程之间能发生在无关进程之间。4.2.1 共享变量与临界区共享变量与临界区 (shared variable&critical region)1.1.共享变量与临界区的概念共享变量与临界区的概念共享变量共享变量：可以被多个进程访问的变量。也称公共变量。临界区临界区：访问共享变量的程序段。也称为临界段(critical section)。共享变量与临界区的关系：一组公共变量一组公共变量CR1CR2CRn.2.2.共享变量与临界区的表示共享变量与临界区的表示共享变量的表示共

7、享变量的表示(说明)：shared 如，shared x1,x2;临界区的表示临界区的表示:region do 这是一个语句,称作临界区语句。其中可为任意语句,包括临界区语句。例如，region x1,x2 do (访问x1,x2)再如，shared b:array0,.,n-1 of integer;region b do begin (访问b)end;若一个临界区语句中的部分包括另一个临界区语句,便发生了临界区嵌套临界区嵌套。例如，shared x1,x2;shared y1,y2;region x1,x2 do region y1,y2 do 再如，shared x1,x2;shared

8、 y1,y2;region x1,x2 do region y1,y2 do begin begin .region y1,y2 do region x1,x2 do begin begin .end end end;end;4.2.2 临界区与进程互斥临界区与进程互斥进程互斥进程互斥:两个或两个以上的进程不能同时进入 关于同一组共享变量的临界区,否则可能发 发生与时间有关的错误与时间有关的错误,这种现象被称作进进 程互斥程互斥。进程互斥有两层含义进程互斥有两层含义:(1)不容许多个进程同时进入关于同一组共享 变量的相同的临界区；(2)不容许多个进程同时进入关于同一组共享 变量的不同的临界区。

9、注意：进程互斥是相对于共享变量而言的。当然，若容许多个进程同时进入关于同一组共享变量的临界区，也不是一定会发生错误。是否会发生错误与进程并发执行时的推进速度有关。不容许多个进程同时进入关于同一组共享变量的临界区，是保证正确性的要求。这件事的实现应由OS及并发程序设计者在编写程序时保证，这需要必要的互斥机制。使用嵌套的临界区时需特别注意，否则可能会发生不期望的后果。例如，shared x;shared y;region x do region y do (1)(2)region y do region x do 当进程P1执行到(1)、进程P2执行到(2)时，P1已进入关于x的临界区，要求进入关

10、于y的临界区，P2则反之。由于临界区是互斥的，因此二者均无法继续向前推进，这种现象称为死锁死锁(第五章)。4.2.3 进程互斥的实现进程互斥的实现 进程互斥的实现进程互斥的实现就是实现对临界区的管理。对临界区的管理对临界区的管理应满足如下管理原则管理原则：(进程互斥的Requirements)(1)正确性原则正确性原则(correctness)：mutual exclusion 一次只允许一个进程活动在关于同一组公共 变量的临界区中。即任意时刻最多只能有一个进程处于关于同 一组共享变量的临界区中；(2)公平性原则公平性原则(fairness)：bounded waiting 一个请求进入临界区

11、的进程应在有限时间内 获得进入该临界区的机会；(3)进展性原则进展性原则(progress)：临界区空闲时，竞争进入临界区的多个进程 在有限时间内确定下一个进入临界区的进程。以上原则是对互斥的实现互斥的实现而言的。临界区的管 理实现后，使用时使用时，如果不慎可能会违背上述 原则。例如，临界区中的程序出现了死循环。临界区相当于一个独占型资源。对临界区资源的管理应满足如下调度原则调度原则:(1)当关于某一组共享变量的所有临界区均为空闲时,一个要求进入该组共享变量某一临界区的进程应能立即进入;(2)当关于某一组共享变量的某一临界区域被占用时,一个要求进入该组共享变量某一临界区域的进程应等待;(3)当

12、一个进程离开关于某一组共享变量的某一临界区时,应容许某一个等待进入关于该组共享变量某一临界区域的进程进入。完全用程序实现进程的互斥，不需特殊硬件指令的支持。可用于单CPU和多CPU环境中。有忙式等待忙式等待问题。Repeat critical section remainder sectionUntil falseentry sectionexit sectionFramework进程互斥的软件实现算法：Lamport面包店算法两种算法均假定系统中进程的个数有限，如n个实现进程互斥的软件的结构框架结构框架：面包店算法的基本思想来源于顾客在面包店购买面包时的排队原理。顾客进入面包店前,首先首先抓

13、一个号码抓一个号码,然后然后按号码由小到大的次序依次进按号码由小到大的次序依次进入面包店购买面包入面包店购买面包。这里假定：(1)面包店按由小到大由小到大的次序发放号码,且两个或两个以上的顾客有可能得到相同号码(要使顾客的号码不同，需互斥机制)。(2)若多个顾客抓到相同号码,则按顾客名字的字典次序排序(假定顾客没有重名)。计算机系统中,顾客相当于进程,每个进程有一个唯一的标识,用Pi,i=1,2,表示。对于Pi和Pj，若有ij，即Pi先进入临界区，则先为Pi服务。1.1.Lamport面包店算法面包店算法面包店算法的基本思想面包店算法的基本思想：首先设置一个发号器，按由小到大由小到大的次序发放

14、号码。进程进入临界区前先抓一个号码进程进入临界区前先抓一个号码，然后按号码由小到大的次序依次进入临界，然后按号码由小到大的次序依次进入临界区区。若多个进程抓到相同的号码，则按进程编号依次进入。实现面包店算法所需的数据结构实现面包店算法所需的数据结构:int choosingn；int numbern；或choosing:ARRAY 0.n-1 OF integer;number:ARRAY 0.n-1 OF integer;choosingn用来表示进程是否正在抓号，其初值均为0。若进程i正在抓号，则choosingi赋为1，否则choosingi为0。numbern用来记录进程抓到的号码，其

15、初值均为0。若numberi为0,则进程Pi没有抓号；若numberi不为0,则其正整数值为进程Pi抓到的号码。为便于面包店算法的描述为便于面包店算法的描述,引入下述表记法：引入下述表记法：设设(a,b):Pi，(c,d):Pj，则，则 (a,b)(c,d)iff(ac)or(a=c and bd)max(a0,an-1)=k：对所有的对所有的i,0 i n-1,kai,k为正整数。为正整数。算法4.1 Lamport面包店算法面包店算法do choosingi=1;numberi=max(number0,number1,numbern-1)+1;choosingi=0;for(j=0;jn;

16、j+)while(choosingj)skip;while(numberj0)&(numberj,j)(numberi,i)skip;临界区临界区 numberi=0;其余部分其余部分 while(1);(1)P1抓到1尚未赋值(2)P2抓到1(3)P3抓到2变量变量choosing的作用的作用 当进程Pi计算完max()+1但尚未将值尚未将值赋给numberi时，进程Pj中途插入，计算max()+1，得到相同的值。在这种情况下，choosingj保证编号较小的进程先进入临界区。忙式等待忙式等待：上述Lamport面包店算法中，若while循环的循环条件成立，则进程将重复测试，直到条件为假。实

17、际上，当while循环条件成立时，进程Pi不能向前推进，而在原地踏步原地踏步，这种原地踏步被称为忙式等待(busy waiting)。忙式等待空耗CPU资源，因而是低效的。验证面包店算法是否满足临界区管理原则验证面包店算法是否满足临界区管理原则：(1)正确性正确性：若进程Pj已在CS，而进程Pi(ij)拥有 与Pj不同的号，则(numberj,j)(numberi,i)。此时进程Pi若试图进入该临界区，则忙式等待忙式等待，直至进程Pj离开临界区。(2)公平性公平性：因进程按FIFO次序进入临界区，且进 程个数有限，故进程不会无限等待进入临界区。(3)进展性进展性：当多个进程竞争进入临界区时，下

18、述 条件之一成立：一个进程抓到最小号码；若干进程抓到最小号码。情形抓到最小 号码的进程获准进入临界区；情形抓到最小 号码且编号最小的进程获准进入临界区。因而 能在有限时间内确定进入临界区的进程。Eisenberg算法采用的数据结构算法采用的数据结构:enum flagn(idle,want_in,in_cs);int turn;/in the range of(0,n-1)int j;/in the range of(0,n-1)或 flag:ARRAY 0.n-1 OF(idle,want_in,in_cs);其中,flagi=idle:进程Pi不想进入临界区,flagi=want_in:进

19、程Pi想进入临界区,flagi=in_cs:进程Pi想进或已进临界区,flag的所有元素初值均为idle，turn的初值为0到n-1之间的任一正整数，j为每个进程拥有的一个局部变量,其初值为 0到n-1之间的任一正整数。2.2.Eisenberg/Mcguire 算法算法算法4.2 Eisenberg/Mcguire 算法算法do do flagi=want_in;j=turn;/turn表示允许进入CS的进程编号 while(j!=i)if(flagj!=!=idle)j=turn;else j=(j+1)%n;/mod flagi=in_cs;j=0;while(jvalue-；if(s-

20、value queue);asleep(s-queue)：(1)将执行此操作的那个进程的PCB插入 s-queue所指PCB队列的尾部,其状态 由运行转为等待；(2)转到处理机调度程序。原语原语:一段不可间断执行的程序称为原语。说明：P操作对应申请资源。V操作操作原语原语的定义:void V(semaphore*s)s-value+;if(s-value queue);wakeup(s-queue)：将s-queue所指队列首部的PCB取出 并将其插入就绪队列,其状态由等待 转为就绪。说明：V操作对应释放资源 使用信号灯变量的规定使用信号灯变量的规定：(1)必须置一次初值,只能置一次初值,且初

21、值 必需为非负整数：(2)只能执行P操作和V操作,其它操作均非法。关于信号灯变量关于信号灯变量 的几个有用结论的几个有用结论：(1)当s-valuevalue|为s-queue中 等待进程的个数;(2)当s-value0时,s-queue为空;(3)当s-value初值为初值为1,可用来实现进程互斥进程互斥。这只需在进入CS时执行一次P操作,离开CS 时执行一次V操作。(4)当s-value初值为初值为0,可用来实现进程同步进程同步。这只需在后进行的动作前后进行的动作前执行一次P操作，在先进行的动作后先进行的动作后执行一次V操作。(5)当s-value初值为正整数初值为正整数,可用来管理同种组

22、管理同种组 合资源合资源。使用资源前执行一次P操作(申请),用完后执行一次V操作(归还)。组合资源：若干相对独立的资源独立的资源构成的资源集 合,其中每个相对独立的资源称为子资源。同种组合资源:相同类型相同类型子资源构成的组合资源.对同种组合资源同种组合资源进行管理时 semaphore S=子资源个数;/初值例如，2台打印机 semaphore S=2;P(S)；/申请 使用 V(S)；/释放shared x,y,z:integer;CR1CR2CRn shared x,y,z:integer;P(mutex)P(mutex)P(mutex)CR1 CR2 CRnV(mutex)V(mute

23、x)V(mutex)semaphore mutex=1;semaphore mutex=1;终端1：终端2：CYCLE CYCLE 等待借书者；等待借书者；P(mutex)P(mutex)IF x=1 Then IF x=1 Then Begin Begin x:=x-1;x:=x-1;V(mutex)V(mutex)借书 借书 End End Else V(mutex);Else V(mutex);/无书 End End例例 图书借阅系统图书借阅系统 P(S)后动作后动作 先动作先动作 V(S)P1P2 例例 司机司机-售票员问题售票员问题 semaphore s1=0,s2=0;司机活动：

24、售票员活动：Repeat Repeat P(S1)关车门 启动车辆 V(S1)正常行驶 售 票 到站停车 P(S2)V(S2)开车门 Until false Until false2.信号灯与信号灯与PV操作的应用操作的应用 用信号灯与PV操作解决进程同步及互斥问题.(1)Producers and consumers problem (2)Readers and writers problem (3)Dining philosophers problem (4)Cigarette smokers problem (5)Sleepy barbers problem 例例1 生产者生产者-消费者

25、问题消费者问题 假设某工厂生产线上有一只用来装物品的箱子,其中有k个位置(k1),每个位置可容纳一件物品，如图所示 0 1 k-1箱子箱子(容量容量k)用数组表示用数组表示itemtype Bn;生产者消费者生产物品放入B中从B中取物品消费之10K-1in(in+1)%kout(out+1)%kin为放入指针,初值0out为取出指针,初值0为实现方便,将箱子中的位置(缓冲区)作成环形。生产者生产者-消费者问题消费者问题需解决的同步问题需解决的同步问题：箱子满时,P1等待于,P2执行到将其唤醒；箱子空时,P2等待于,P1执行到将其唤醒。生产者活动生产者活动P1:do 加工一件物品;物品放入放入箱

26、中;while(1);消费者活动消费者活动P2:do 箱中取取一物品;消耗这件物品;while(1);从资源角度看：箱子中的位置箱子中的位置相当于生产者资源,可用一个信号 灯变量S1表示,其初值为k；物品物品相当于消费者资源,可用一个信号灯变量S2 表示,其初值为0。生产者资源：箱子B 消费者资源：物品semaphore S1=k;semaphore S2=0;放前：P(S1)取前：P(S2)放后：V(S2)取后：V(S1)生产者活动生产者活动：消费者活动消费者活动：Repeat Repeat 加工一件物品加工一件物品 P(S2)P(S1)箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V

27、(S1)V(S2)消耗这件物品消耗这件物品 Until false Until false需解决的互斥问题需解决的互斥问题：需解决对关于共享变量B,in,out的临界区的互斥:semaphore mutex=1;生产者活动：消费者活动：Repeat Repeat 加工一件物品 P(S2)P(S1)P(mutex)P(mutex)箱中取一物品 物品放入箱中 V(mutex)V(mutex)V(S1)V(S2)消耗这件物品 Until false Until false生产者生产者-消费者问题的消费者问题的2 210-1-2P(S)P(S)P(S)P(S)P(S)V(S)V(S)V(S)V(S)V

28、(S)S.value=空闲资源数空闲资源数|S.value|=等待进程数等待进程数.S.queue=空空闲资源数=0 生产者生产者-消费者问题的求解程序消费者问题的求解程序 itemType Bk;semaphore S1=k;/S1表示箱子中的位置 semaphore S2=0;/S2表示物品 int in=0;int out=0;semaphore mutex=1;/初值为1,用于实现进程互斥 void producer()whlie(1)produceItem(&item);/生产一件产品 P(S1);P(mutex);Bin=item;in=(in+1)%k;V(mutex);V(S2

29、);void consumer()itemType temp;while(1)P(S2);P(mutex);temp=Bout;out=(out+1)%k;V(mutex);V(S1);/然后消费一件产品 fork(producer,0);fork(producer,m-1);fork(consumer,0);fork(consumer,n-1);生产者的共享变量:Bin,in消费者的共享变量:Bout,out当inout时,生产者和消费者不操作B的相同分量;当in=out时,缓冲区或空或满,PV操作操作已保证空时 消费者不会取,满时生产者不会放。可见,生产者和消费者任何情况下均不操作B的相同

30、分量。为提高程序的并发性,可将用于互斥的信号灯变量分为两个:mutex1和mutex2,分别用于生产者的互斥和消费者的互斥:semaphore mutex1=1,mutex2=1;生产者活动：消费者活动：Repeat Repeat 加工一件物品 P(S2)P(S1)P(mutex2)P(mutex1)箱中箱中取取一物品一物品 物品物品放入放入箱中箱中 V(mutex2)V(mutex1)V(S1)V(S2)消耗这件物品 Until false Until false 生产者-消费者问题在OS及并发程序设计中经常遇到。箱子相当于缓冲区缓冲区 生产者和消费者相当于进程进程 进程之间通过一个长度有界

31、的缓冲区长度有界的缓冲区通讯 生产者-消费者问题又称作有界缓冲区有界缓冲区问题一组公共数据DBRmW1R1Wn 设有一组共享数据DB和两组并发进程,一组进程只对此组数据执行读操作,另一组进程可对此组数据执行写操作和读操作。前一组进程称作读者读者,后一组进程称作写者写者.要求:(1)R-R可同时 (2)W-W不可同时 (2)R-W不可同时 例例2 读者读者写者问题写者问题 semaphore r_w_w=1;Reader()Writer()P(r_w_w);P(r_w_w);读操作 写操作 V(r_w_w);V(r_w_w);分析:写者活动正确,但R-R不能并发。改进:最先进入的R执行P,最后离

32、开的R执行V int readCount=0;Reader()readCount:=readCount+1;If readCount=1 Then P(r_w_w);读操作 readCount:=readCount-1;If readCount=0 Then V(r_w_w);分析:对Read_count操作不互斥.改进:用信号灯变量mutex实现对readCount的互斥.int readCount=0;semaphore mutex=1;Reader()P(mutex);readCount:=readCount+1;If readCount=1 Then P(r_w_w);V(mutex)

33、;读操作 P(mutex);readCount:=readCount-1;If readCount=0 Then V(r_w_w);V(mutex);int readCount=0;/readCount记录读者的数目semaphore r_w_w=1;semaphore mutex=1;reader()while(1)P(&mutex);/mutex实现对readCount的互斥 readCount=readCount+1;if(readCount=1)P(&r_w_w);/r_w_w实现R-W间及W-W间的互斥 V(&mutex);P(&mutex);readCount=readCount-

34、1;if(readCount=0)V(&r_w_w);V(&mutex);writer()while(1)P(&r_w_w);V(&r_w_w);fork(reader,0);fork(reader,m-1);fork(writer,0);fork(writer,n-1);分析:R-R不互斥.若读者源源不断,写者可能饿死.事实上,写者的操作是更新数据,应优先进行,否则读者将读到过时的数据.改进:写者优先写者优先,即一旦有写者等待,正在读的读者 都结束后,写者进入,新到达的读者等待.(Dining Philosophers Problem)Proposed and solved by E.W.D

35、ijkstra in 1965.Roomph0ph4ph3ph2ph1f0f4f3f2f1哲学家活动哲学家活动：Repeat 思考 进食 Until false进食：需要“叉子”叉子：不同种组合资源 哲学家活动哲学家活动(包含资源活动)Repeat 思考思考 取左叉 取右叉 进食进食 放左叉 放右叉 Until false哲学家问题的解法：VAR fork Array 0.4 of Semophore=(1,1,1,1,1)philosopher(i):begin repeat THINK;P(forki)P(forki+1 mod 5)EAT V(forki)V(forki+1 mod 5)

36、until false end;死锁情况死锁情况：每位哲学家拿到左叉，等待右叉。解决死锁的办法：限制最多4位哲学家同时进餐，VAR fork Array 0.4 of Semophore=(1,1,1,1,1)VAR count:semophore=4philosopher(i):begin repeat THINK;P(count)P(forki)P(forki+1 mod 5)EAT V(forki+1 mod 5)V(forki)V(count)until false end;(Cigarette Smokers Problem)3 supplier processes:X:suppli

37、es tobacco and match;Y:supplies match and wrapper;Z:supplies wrapper and tobacco.3 smoker processes:A:possess tobacco;B:possess match;C:possess wrapper.(1)only one of X,Y,Z can supply at a time;(2)X,Y,Z can proceed only after consumption.Var t,m,w,s:semaphore;(0,0,0,1)Process X process Y process Z P

38、(s);P(s);P(s);V(t);V(m);V(w);V(m);V(w);V(t);Process A Process B process C P(m);P(w);P(t);P(w);P(t);P(m);smoke;smoke;smoke;V(s);V(s);V(s);SP(S1,t1,d1;Sn,tn,dn);if S1=t1 and and Sn=tn then for I:=1 to n do Si:=Si-di endforelse (1)place the executing process in the waiting queue for the first Si with S

39、i0 Then wait(rq);reading_count+;signal(rq);End;Procedure finish_read;Begin reading_count-;If reading_count=0 Then signal(wq)End;Procedure start_write Begin write_count+;If(write_count1)or(reading_count0)Then wait(wq)End;Procedure finish_write;Begin write_count-;If write_count0 Then signal(wq)Else si

40、gnal(rq)End;Begin reading_count:=0;/正在读进程的个数 write_count:=0;/正在写进程与等待写进程的个数之和End;读者进程的活动读者进程的活动：(readers_writers rw;)rw.start_read;reading rw.finish_read;写者进程的活动写者进程的活动：rw.start_write;writing rw.finish_write;Note:管程与管程与PV操作是等价的操作是等价的 PV操作和管程这两种同步机制都只适合于单机系统及具有公共内存的多机系统，不适合于不具有公共内存的分布式系统。P1:共享变量(被动)C

41、R2P2:共享变量与访问进程在同一存储区,不适合分布环境CR1管程（被动）共享变量CR1CR2P1：.P2：.管程与调用进程在同一存储区，不适合分布环境。1.会合的描述会合的描述 Ada语言中活动的成分称作任务任务(Task)。任务相当于通常所说的进程。任务与任务之间可通过会合的方式直接进行相互作用,不需要被动成分的参与。因为多个任务可处于不同的主机中,所以这种同步机制适用于分布式系统。任务task(callee)任务task(caller)任务task(caller)调用语句调用语句接受语句选择语句被调用者代调用者执行调用代码。一个任务调用另一任务的入口时可携带调用参数,还可从被调用者处得到

42、返回参数。这样,任务之间可相互交换信息,实现消息通讯。此外，当多个入口处均有调用者时，被调用者可选择会合的入口。会合的一般形式：被调用任务入口1：accept入口2：acceptselect.PCBPCB.调用语句PCB.PCB调用任务入口FIFO队列调用语句4.4.1 进程通讯的概念进程通讯的概念 进程互斥可发生在任意进程之间，进程同步只发生在相关进程之间。无论是互斥还是同步，进程之间都发生了信息交换，只是交换的信息量很小，即一个简单的唤醒信号。进程互斥与进程同步称作进程之间的低级低级通讯通讯，进程之间大宗数据的传递称作进程之间的高级通讯高级通讯。进程通讯进程通讯：进程之间的互斥、同步及信息

43、交换统称进程通讯进程通讯(Inter-Process Communication,IPC)。1.共享内存模式共享内存模式(shared memory)：共享内存模式：一组进程向公共内存中写，另一组进程从该公共内存中读，如此便实现了进程之间的信息传递。共享内存模式需解决如下两个问题:(1)为相互通讯的进程之间提供公共内存公共内存 (2)为访问公共内存提供必要的同步机制同步机制注意：OS提供公共内存及互斥同步机制，而公共 内存及互斥同步机制的使用由进程完成。进程通讯主要有两种模式:共享内存模式、消息传递模式 2.消息传递模式消息传递模式(message passing)：P1P2Msendrece

44、ive 采用这种模式时，相互通讯的进程间不存在公共内存。操作系统为用户进程间的通讯提供了两个基本的系统调用命令：发送命令发送命令(send)、接收命令接收命令(receive)当需要进行消息传递时，发送者仅需执行发送命令，接收者仅需执行接收命令，消息便由发送者传送给接收者。消息如何由发送者传消息如何由发送者传送给接收者完全由送给接收者完全由OSOS完成，对用户是透明的完成，对用户是透明的。Send(R,M).Receive(S,N).S:R:信息传递模式在实现时又分为两种方式：直接方式：进程-进程 间接方式：进程-信箱-进程l对称形式(sender and receiver name each

45、 other)send(R,message)receive(S,message)receive(pid,N).send(R,M1).send(R,M2).C/S modelR:S1:S2:l非对称形式(only sender names receiver)send(R,message)receive(pid,message)PCBsend(R,M)size text .PCBreceive(pid,N).M:N:msgmsgmsg.发送者S:接收者R:Sizetextsenderlink载有消息的缓冲：进程消息队列管理：Var Sm:semaphore;(0)收取消息前：P（Sm）;消息入队后

46、：V（Sm);消息队列互斥：Var m_mutex:semaphore;(1)P(m_mutex);取(放)动作;V（m_mutex);bufbufbuf.Var Sb,b_mutex:semaphore;(k,1)申请：P(Sb);P(b_mutex);头缓冲出链;V(b_mutex);释放：P(b_mutex);缓冲入链头;V(b_mutex);V(Sb);Head：Send(R,M)根据R找接收者；P(Sb);P(b_mutex);取一空buf;V(b_mutex);text,size,sender=buf P(m_mutex);消息入链尾；V(m_mutex);V(Sm);Receiv

47、e(pid,N)P(Sm);P(m_mutex);头消息出链;V(m_mutex);text,size=N sender=pid P(b_mutex);空buf入链；V(b_mutex);V(Sb);lSend/receive 为高级通讯原语，可用低级原语实现；lSend/receive不是真正意义的原语，可以被中断。MailboxSend_mb(mb,m)Receive_mb(mb,n).multi-sender-multi-receiver;multi-sender-one receiverType mailbox=record in,out:0.k;s1,s2:semaphore;(k,

48、0)mutex:semaphore;(1)letter:array0.k-1of message;end;Var mb:mailbox;create_mb(mb);系统调用delete_mb(mb);系统调用Procedure send_mb(var mb:mailbox;m:massage);begin with mb do begin P(s1);P(mutex);letterin:=m;in:=(in+1)mod k;V(mutex);V(s2)end;end;Procedure receive_mb(var mb:mailbox;var n:massage);begin with mb

49、 do begin P(s2);P(mutex);n:=letterout;out:=(out+1)mod k;V(mutex);V(s1)end;end;Var mb:mailboxcreate_MBdelete_MBsend_MBreceive_MBcreat_MB(mb)receive_MB(mb,N)delete_MB(mb)N:send_MB(mb,M)M:Pipe:an unnamed file with two fds,one for write,and the other for read.The size of pipe file is limited to 4 blocks(one block is 512 bytes).int fd2;pipe(fd):功能：创建一个pipe文件返回：fd0:读描述符；fd1:写描述符。pipe可以被子进程继承子进程1：write(fd1,buf1,count1);子进程2：read(fd0,buf2,count2)