《互斥同步与通信》PPT课件.ppt

《《互斥同步与通信》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《互斥同步与通信》PPT课件.ppt（116页珍藏版）》请在三一办公上搜索。

1、1,第四章 互斥、同步与通讯,并发进程(concurrent processes)进程互斥(mutual exclusion)进程同步(synchronization)进程高级通讯(communication),2,4.1 并发进程,4.1.1 顺序程序及其特性程序的顺序性-内部顺序性：P1:a1,a2,a3;P2:b1,b2,b3-外部顺序性：情形1：a1,a2,a3,b1,b2,b3;情形2：b1,b2,b3,a1,a2,a3顺序程序设计的特性：-顺序性：处理机严格按指令依次执行；-封闭型：执行过程独占资源；-可再现性：程序执行的结果与执行速度无关。,多个进程依次执行,进程内所有指令按顺序

2、执行,3,4.1 并发进程,4.1.2 并发程序及其特性程序的并发性内部并发性：P2:b1,b2,b3;P2:b1,b3,b2外部并发性：情形1：a1,b1,b2,a2,a3,b3;情形2：b1,b2,a1,b3,a2,a3并发程序的特性（带来好处也引发问题）：-交叉性：不同的交叉可能导致不同的结果；-非封闭性：进程的运行环境可被其他进程所改变；-不可再现性：不可再现上次运行的结果。,指令可以按顺序也可以不按顺序执行,进程交叉执行,并发特性将引发一系列问题如互斥、死锁、饿死等,4,4.1.2 与时间有关的错误,例：图书借阅系统（x:某种书册数，设当前x=1.）终端1（进程p1）：终端2（进程p

3、2）：do do 等待借书者；等待借书者；IF(x=1)IF(x=1)x=x-1;x=x-1;借书 借书 Else 无书 Else 无书 while(1)while(1),1,2,3,4,5,4.1.2 与时间有关的错误(Cont.),错误原因之1：进程执行交叉(进程推进速度不同);错误原因之2：涉及公共变量(x)。Remarks:某些交叉导致结果不正确;必须去掉导致不正确结果的交叉。,6,4.2 进程互斥(mutual exclusion),进程间发生的一种间接性相互作用。4.2.1 共享变量与临界区4.2.2 临界区域与进程互斥4.2.3 进程互斥的实现4.2.4 多处理机环境下的互斥,7

4、,4.2.1 共享变量与临界区域,共享变量（shared variable）多个进程都需要访问的变量。临界区（critical region）访问共享变量的程序段。,一组共享变量,CR1,CR2,CRn,.,程序段1,程序段2,程序段n,8,共享变量与临界区表示,共享变量:shared 临界区域:region do 语句例子：shared x1,x2;shared y1,y2;region x1,x2 do region y1,y2 do,临界区可以嵌套,9,4.2.2 临界区域与进程互斥,定义：两个或两个以上进程不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象

5、称为进程互斥。二层涵义：（1）不容许多个进程同时进入关于同一组共享变量的相同的临界区域；（2）不容许多个进程同时进入关于同一组共享变量的不同的临界区域。Remarks:互斥是相对于公共变量而言的。,10,嵌套临界区域,shared x;shared y;region x do region y do.region y do region x do.,临界区可以嵌套：,已进入临界区域可能引发死锁！,11,4.2.3 进程互斥的实现,Framework,Repeat critical section remainder sectionUntil false,entry section,exit s

6、ection,12,4.2.3 进程互斥的实现,实现临界区管理的三个原则：正确性原则：任意时刻至多只能有一个进程处于同一组共享变量的临界区域中；公平性原则：一个请求进入临界区的进程应当在有限等待时间内获得进入临界区的机会；进展性原则：当临界区空闲时，竞争进入临界区的多个进程在有限的时间内确定下一个进入临界区的进程。临界区调度原则：！临界区空闲，想进入的应能进入；！临界区不空闲，进程应等待；！进程离开临界区时，应能唤醒等待进入的进程。,13,4.2.3.1 进程互斥的软件实现,完全用程序实现，不需特殊硬件指令支持。可用于单CPU和多CPU环境中。有忙式等待问题。,Busy waiting“运行”

7、或“就绪”,14,Lamport面包店算法,算法思想：设置一个发号者，按0,1,2,发号。想进入临界区的进程抓号，抓到号之后按由小到大的次序依次进入。Problem:两个进程可能抓到相同的号。Why?为保证抓到不同的号，需要互斥机制。Resolution:若抓到相同的号，按进程编号依次进入。Definition:(a,b)(c,d)if(ac)or(a=c and bd),15,Lamport面包店算法,int choosing n;表示进程是否在抓号int number n;记录进程所抓到的号码Pi 进入：do choosingi=1;numberi=maxnumber0,numbern-1

8、+1;choosingi=0;for(j=0;j0),正在抓号,抓到号码,抓号完毕,比较号码决定谁进入,忙等待,16,Lamport面包店算法(Cont.),临界区(CS)其余部分while(1);变量choosing的作用：P1：抓到1;P2：抓到1;正确次序：P1，P2，P3P3：抓到2;,可能按P2,P3,P1次序进入！,numberi=0；,进入临界区,出临界区，号码清零,17,Eisenberg/Mcguire算法（令牌法）,enum flag n;(取值：idle,want_in,in_cs);int turn;（取值：0.n-1，初始任意）,flagi=idle:进程Pi不想进入

9、临界区flagi=want_in:进程Pi想进入临界区flagi=in_cs:进程Pi想进入或已进入临界区,18,Eisenberg/Mcguire算法,Pi进入:Do do flagi=want_in;我要进入 j=turn;取令牌 While(j!=i)令牌是我的？If(flagj!=idle)j=turn;不是，有令牌的要进？Else j=(j+1)%n;有令牌的不进，看下一个 flagi=in_cs;j=i令牌轮到我，设置标志表示要进 j=0;While(jn)确实没有，进临界区,忙等待,19,Eisenberg/Mcguire算法,Pi离开：从临界区离开 j=(turn+1)%n;向

10、下传令牌 While(flagj=idle)j=(j+1)%n;turn=j;flagi=idle;清自己的标示为空 其余部分while(1);,CS,20,4.2.3.2 进程互斥的硬件实现,1.硬件提供“测试并建立”指令 int test_and_set(int,一条指令,21,进程互斥的硬件实现,2.硬件提供“交换”指令(swap)void swap(int,一条指令,22,进程互斥的硬件实现,Remarks：(1)test_and_set指令和swap指令是原子的，不可中断的。(2)test_and_set实际上是：将内存中一个单元的内容取出，再送一个新值。(3)swap实际上是：交换

11、内存两个单元的内容。,23,进程互斥的硬件实现,3.硬件提供“开关中断”指令 关中断 临界区(Critical Region)开中断Remarks:(1)开关中断只在单CPU系统中有效;(why?)(2)影响并发性。,24,4.2.4 多处理机环境下互斥,内存,单元 1000初值:0,CPU1,CPU2,Bus,1.Read 0,3.Write 1,2.Read 0,4.Write 1,CPU1、CPU2对单元1000同时读，同时写,25,多处理机环境下互斥,TS指令，Swap指令:硬件支持“锁总线”功能，保证指令执行的原子性。bus request protocol（总线请求协议）:使用前：

12、锁定总线 使用后：开放总线,26,多处理机环境下互斥,Do b=1;while(b)lock(bus);b=test_and_set(,CR,27,4.3 进程同步,4.3.1 进程同步的概念例：司机-售票员问题 司机活动：售票员活动：p1:do p2:do 启动车辆 关车门 正常行驶 售 票 到站停车 开车门 while(1);while(1);,28,4.3.1 进程同步的概念,定义：一组进程，为协调其推进速度，在某些关键点处需要相互等待与相互唤醒，进程之间这种相互制约的关系称为进程同步。,P1:,P2:,synchronize,后,先,29,4.3.1 进程同步的概念,定义：一组进程，如

13、果它们单独不能正常进行，但并发可以正常进行，称这种现象为进程的合作（cooperation）。参与合作的进程称为合作进程（cooperating process）如：司机与售票员是合作进程。,30,4.3.2 进程同步机制,定义：用于实现进程同步的工具称为同步机制（synchronization mechanism）同步机制要求：描述能力够用：能描述各种同步问题;可实现;高效;使用方便.,31,典型同步机制,信号灯与PV操作(semaphore and PV operations)管程(monitor)会合(rendezvous)条件临界区(conditional critical regio

14、n)路径表达式(path expression)事件(traditional UNIX),32,4.3.3 信号灯与PV操作,1965.4.3.3.1 信号灯与PV操作的定义 typedef semaphore struct int value;pointer_to_ PCB queue;信号灯变量 semaphore s;Remarks:(1)信号量是一个预定义的数据类型,(2)信号量s可根据要求定义。,33,信号灯变量,S.valueS.queue,信号灯变量和进程队列：,FIFO,34,P操作原语,P操作原语：void P(semaphore*s)s-value-;if(s-valueq

15、ueue);asleep(s-queue):(1)执行此操作进程的PCB入s-queue尾（状态改为等待）；(2)转处理机调度程序。,原语：一段不可间断执行的程序,35,V操作原语,V操作原语：void V(semaphore*s)s-value+;if(s-valuequeue);wakeup(s-queue)S-queue链头PCB出等待队列，进入就绪队列（状态改为就绪）。,36,规定和结论,对于信号灯变量的规定：必须置一次初值，只能置一次初值，初值=0;只能执行P操作和V操作，所有其它操作非法。几个有用的结论：当s-value=0时，s-queue为空；当s-valuevalue|为队列

16、s-queue的长度；当s-value初=1时，可以实现进程互斥；当s-value初=0时，可以实现进程同步；当s-value初=正整数，可以用来管理同类资源。,37,用信号灯实现进程同步,一般形式:Semaphore s;(initial value 0),P(S)后动作,先动作 V(S),P1:,P2:,38,用信号灯实现进程同步,例子：司机-售票员问题：semaphore s1,s2;(initial value 0)司机活动：售票员活动：Repeat Repeat P(S1)关车门 启动车辆 V(S1)正常行驶 售 票 到站停车 P(S2)V(S2)开车门 Until false Un

17、til false,39,例1.生产者/消费者问题,0 1 k-1,箱子，容量k，缓冲区 B:Array0.k-1Of item,生产者,消费者,生产物品放入B中,B中取物品消费之,40,环形缓冲区,1,0,K-1,in,(in+1)%k,out,(out+1)%k,41,问题分析,生产者活动：消费者活动：do do 加工一件物品；箱中取一物品；物品放入箱中；消耗这件物品；while(1)；while(1)；,资源：箱子（同种组合）资源：物品（同种组合）Semaphore S1;semaphore S2;S1.value=k;S2.value=0;放前：P（S1）取前：P（S2）放后：V（S2

18、）取后：V（S1）,42,同步,生产者活动：消费者活动：Repeat Repeat 加工一件物品 P(S2)P(S1)箱中取一物品 物品放入箱中 V(S1)V(S2)消耗这件物品 Until false Until false对B（缓冲区）和in,out（指针）的互斥：semaphore mutex;(mutex.value=1),43,互斥,生产者活动：消费者活动：Repeat Repeat 加工一件物品 P(S2)P(S1)P(mutex)P(mutex)箱中取一物品 物品放入箱中 V(mutex)V(mutex)V(S1)V(S2)消耗这件物品 Until false Until fal

19、se,44,程序清单,Program producers_consumers;itemType bufferk;semaphore S1=k;semaphore S2=0;int in=0;int out=0;semaphore mutex=1;,void producer()while(1)produceItem(V(S2),void consumer()itemType temp;while(1)P(s2);P(mutex);temp=bufferout;out=(out+1)%k;V(mutex);V(S1);,45,程序（续前）,Fork(producer,0);fork(produc

20、er,m-1);Fork(consumer,0);fork(consumer,n-1);,46,例2.读者/写者问题,P.T.Courtois 1971Communication of the ACM,Vol.14,667-669.ACM:Association for Computing Machinery解法1：写者可能饿死（允许写者饿死）解法2：写者优先（写者优先于读者）,生产者/消费者问题：多个进程协作，各有各的箱子；读者/写者问题：多个进程协作，共享同一箱子。,47,例2.读者/写者问题,问题描述:一组公共数据DB R1 Rm W1.Wn要求：（1）R-R可以同时（2）R-W不可同时

21、（3）W-W不可同时,accessing,48,正确解法（可能产生写者饥饿）,Int readCount=0;semaphore r_w_w=1;semaphore mutex=1;Reader()while(1)P(,读者加计数，互斥,有写者，读者等待于此信号灯多个读者不互斥,读者减计数，互斥,若无读者，唤醒等待的写者,只有一个读者进入计数其他要进入的读者等待,49,程序续前,Writer()While(1)P(,写者操作临界区域,如有读者，写者等待于此信号灯如已有写者，其他写者等待于此,写结束，唤醒其他写者或读者,50,分析：,问题：读者源源不断，read_count不归0，写者会被饿死。

22、策略：一旦有写者等待，新到达读者等待，正在读的读者都结束后，写者进入。,51,4.3.4 条件临界区Conditional Critical Region,背景PV操作低级，容易用错条件临界区形式region r when b do sR：共享变量；b：布尔表达式；s：语句进入条件临界区执行S的条件没有其它进程处于与r相关的条件临界区中进入s时b为真（true）,忘记P不能实现互斥忘记V可能导致死锁,52,条件临界区,实现互斥region v when true do sCCR与PV操作的等价性(证明从略）用CCR可以实现PV操作用PV操作可以实现CCR缺点：效率低可能产生忙等待,53,4.3

23、.5 管程（Monitor）,PV操作：分散式同步机制：共享变量操作，PV操作，分散在整个系统中或各个进程中。缺点：可读性差；正确性不易保证；不易修改。优点：高效，灵活。,管程：集中式同步工具：共享变量及其所有相关操作集中在一个摸块中。优点：可读性好；正确性易于保证；易于修改。缺点：不甚灵活，效率略低。,54,4.3.5.1 管程的提出,70年代初,By,C.A.R.Hoare,P.B.Hansen.背景:结构化程序设计（Structured programming）基于管程作为同步机制的高级语言Concurrent Pascal(Hansen)Modula(With)MesaMod*Conc

24、urrent EuclidXCY,55,管程的提出(Cont.),构造操作系统的PCM方法P：processC：classM：monitorExample systemsolo,56,4.3.5.2 管程形式（pascal语言描述）,Type monitor_name=MONITOR 共享变量说明 define 本管程内定义，本管程外可调用的过程（函数）名表；use 本管程外定义，本管程内可调用的过程（函数）名表；Procedure 过程名（形参表）；过程局部变量说明 Begin 语句序列 End;,57,管程形式(Cont.),Function 函数名（形参表）:值类型；函数局部变量说明 B

25、egin 语句序列；End;.Begin 共享变量初始化语句序列；End;语言特点：(1)模块化（modularized）;(2)抽象数据类型（abstract data type）;(3)信息掩蔽（information hiding）.,58,4.3.5.3 管程语义,管程的共享变量在管程外部不可见，外部只能通过调用管程中的外部过程（函数）间接的访问共享变量；为保证对共享变量操作的数据完整性，规定管程互斥进入；管程中有等待/唤醒机制，等待时释放管程的互斥权，唤醒时（P唤醒Q），有如下三种可能的解决方法：P等待，Q继续，直到Q退出或等待；(Hoare)Q等待，P继续，直到P退出或等待；(Ja

26、va)唤醒是管程中可执行的最后一个操作。（Hansen),59,Hoare管程设施,三个等待队列入口等待队列：每个管程变量一个，用于排队进入；紧急等待队列：每个管程变量一个，用于唤醒等待；内部等待队列：var c:condition;可根据需要定义多个，用于设置等待条件。,60,管程队列,x,y,PCB,PCB,PCB,PCB,入口队列,紧急队列,初始化代码,条件队列,操作,操作,操作,共享变量,互斥进入管程,离开管程时唤醒,61,进入与离开,进入管程：申请管程互斥权。离开管程：如紧急等待队列非空，唤醒第一个等待者；否则开放管程。,62,条件变量操作,Var c:condition;wait(

27、c):如紧急队列非空，唤醒第一个等待者，否则释放管程互斥权;执行此操作的进程（线程）进入c链尾。signal(c):如c链空，相当空操作。否则唤醒第一个，执行此操作的进程（线程）进入紧急队列。,63,4.3.5.4 管程的使用,读者/写者问题（写优先）哲学家就餐问题（another approach)Sleepy barbers problemDisk head scheduler Single resource management,64,例1.读者/写者问题,写者优先（偏向写者的解法）TYPE reaers_and_writers=MONITOR;Var rq,wq:condition;r

28、eading_count,write_count:integer;Define start_read,finish_read,start_write,finish_write;,65,例1.读者/写者问题,Procedure start_read;Begin If write_count0 Then wait(rq);reading_count+;signal(rq);End;,Procedure finish_read;Begin reading_count-;If reading_count=0 Then signal(wq)End;,66,例1.读者/写者问题,Procedure sta

29、rt_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 signal(rq)End;,67,例1.读者/写者问题,Begin reading_count:=0;write_count:=0;End;,读者：Readers_and_writers.start_read;读操作；Readers_and_writers.finish_read;

30、,写者：Reader_and_writers.start_write;写操作；Reader_and_writers.finish_write;,调用管程内的过程,68,例：磁头引臂调度问题,0 1 199,updown,磁头,引臂,扇区,略,69,调度算法,FCFS（first come first serve）公平效率低SSTF（shortest seek time first）效率高磁道歧视SCAN（elevator algorithm）效率较高，较公平,略,70,Hansen管程实现SCAN算法,外部过程：申请：require(dest:0.199)释放：release()使用方式：re

31、quire(dest);IO操作-(管程外操作)release,略,71,管程实现SCAN算法,TYPE disk_head_shared=MONITOR Var busy:BOOLEAN;headpos:0.199;direction:(up,down);cylinder:ARRAY0.199Of condition;count:ARRAY0.199Of integer;Define Apply,release;,略,72,管程实现SCAN算法,PRPCEDURE require(dest:0.199);Begin If busy Then Begin countdest:=countdes

32、t+1;wait(cylinderdest)End busy:=true;If destheadpos Then direction:=up;headpos:=dest End;,略,73,管程实现SCAN算法,Procedure upscan;Var I:0.200;Begin I:=headpos;While(I=199)and(countI=0)Do I:=I+1;If I=199 Then Begin countI:=countI-1;signal(cylinderI)End End;,略,74,管程实现SCAN算法,Procedure downscan;Var I:-1.199;Be

33、gin I:=headpos;While(I=0)and(countI=0)Do I:=I-1;If I=0 Then Begin countI:=countI-1;signal(cylinderI)End End;,略,75,管程实现SCAN算法,Procedure release;Begin busy:=false;If direction=up Then Begin upscan;downscan End Else Begin downscan;upscan End End;,略,76,管程实现SCAN算法,Procedure initialize;Var I:0.199;Begin b

34、usy:=false;headpos:=0;direction:=up;For I:=0 To 199 Do countI:=0 EndBegin initialize End;,略,77,4.3.5.5 管程与PV操作的等价性,用PV操作可以构造管程用管程可以构造PV操作,Implementing PV operationsusing monitors is trivial,略,78,用管程构造PV操作,TYPE semaphore=MONITOR(init_value)VAR c:condition;count:integer;DEFINE P,V;PROCEDURE P;BEGIN co

35、unt:=count-1;IF count0 THEN wait(c);END;,PROCEDURE V;BEGIN count:=count+1;IF count=0 THEN signal(c);END;BEGIN count:=init_value;END;,略,79,用管程构造PV操作(Cont.),略,80,用PV操作构造管程,略,81,用PV操作构造管程,略,82,Windows2000/XP互斥同步机制,Mutex(OS API)CreateMutex,/创建互斥对象，返回句柄OpenMutex,/打开并返回存在对象句柄ReleaseMutex;/释放对互斥对象的占用semaph

36、ore(OS API)CreateSemaphore,/创建信号量OpenSemaphore,/返回已存在信号量句柄ReleaseSemaphore;/释放对信号量的占用,83,Windows2000/XP互斥同步机制,Event(OS API)CreateEvent,OpenEvent,SetEvent,ResetEvent,PulseEvent.,84,Windows2000/XP互斥同步机制,CRITICAL_SECTION类型InitializeCriticalSection:初始化EnterCriticalSection:等待进入TryEnterCriticalSection:非等待

37、，失败返回0LeaveCriticalSection:离开DeleteCriticalSection:清除,85,4.4 进程高级通讯,进程通讯：进程之间的互斥、同步及信息交换。低级通讯（简单信号）进程互斥进程同步高级通讯（大宗信息）高级通讯（一般情况下，进程通讯专指进程间的高级通讯）共享内存 vs.消息传递直接通讯 vs.间接通讯对称性通讯 vs.非对称性通讯有缓冲通讯 vs.无缓冲通讯,4.4.1 进程通讯概念,86,P1,4.4.2 进程通讯模式,1.共享内存模式(shared memory)：,2.消息传递模式(message passing)：,P2,OS提供：（1）公共内存（2）互

38、斥同步机制,P1,P2,M,send,receive,OS提供通讯原语直接：进程-进程间接：进程-信箱-进程,87,4.4.3 直接方式,直接方式：通讯进程间彼此直呼其名（指定对方名字）对称形式(一对一方式)send(R,M)：将消息M发给进程Rreceive(S,N)：进程S接收消息至N,S:,R:,88,直接方式,receive(pid,N).,send(R,M1).,send(R,M2).,非对称形式(多对一方式)send(R,M)：将消息M发给进程Rreceive(pid,N)：接收消息至N，返回pid,C/S 模式,R:,S1:,S2:,纪录发送进程标识,89,4.4.3.1 有缓冲

39、途径,PCB,send(R,M)Size：消息长度 Text：消息正文.,消息链指针,receive(pid,N).,M:,N:,消息,消息,消息,.,Sizetext,发送者S:,接收者R:,操作系统提供缓冲区，消息经操作系统传递。,消息缓冲区,90,消息传递,直接,非对称,有缓冲通讯,Size：消息长度Text：消息正文Sender：发送者pointer：消息链指针,缓冲区中的消息：,进程消息队列管理：Var S_m:semaphore;(0)收取消息前：P（S_m）;消息入队后：V（S_m);消息队列互斥：Var m_mutex:semaphore;(1)P(m_mutex);取(放)动

40、作;V（m_mutex);,91,缓冲区池管理,Var S_b,b_mutex:semaphore;(k,1),申请：P(S_b);P(b_mutex);头缓冲出链;V(b_mutex);,释放：P(b_mutex);缓冲入链头;V(b_mutex);V(S_b);,Head：,92,发送-接收原语（发送原语的处理步骤）,Send(R,M)根据R找接收者；P(S_b);申请一个缓冲区 P(b_mutex);对消息缓冲区链互斥操作 取一空buf;V(b_mutex);对消息缓冲区链互斥操作 text,size,sender=buf 消息送消息缓冲区 P(m_mutex);对接收进程的消息链互斥操

41、作 消息缓冲区入链尾；V(m_mutex);对接收进程的消息链互斥操作 V(S_m);接收进程的消息资源增加一个,93,发送-接收原语（接收原语的处理步骤）,Receive(pid,N)P(S_m);申请消息资源 P(m_mutex);对自身的消息链互斥操作 头一个消息出链;V(m_mutex);对自身的消息链互斥操作 text,size=N 将消息正文和长度拷贝到接收区 sender=pid 将发送进程的名字记录到变量pid中 P(b_mutex);对消息缓冲区链的互斥操作 空buf入链；V(b_mutex);对消息缓冲区链的互斥操作 V(Sb);释放一个消息缓冲区,94,Remarks：,

42、Send/receive 为高级通讯原语，可用低级原语实现；Send/receive不是真正意义的原语，可以被中断。,95,4.4.3.2 无缓冲途径,操作系统不提供缓冲区，消息自发送进程空间直接传送到接收进程空间。特点：1、有发送无接收，发送等待；2、有接收无发送，接收等待；3、有发送有接收，通讯实现。,96,发送/接收原语,Send(R,M)根据R找到消息接收者；V(S_m);发消息进程个数增一，如接收进程等待则唤醒P(S_w);等待消息传送完毕Receive(pid,N)P(S_m);等待消息到达将消息内容有发送进程空间传送到接收进程空间；V(S_w);唤醒发送消息进程优点：节省空间；缺

43、点：并发性差。,97,4.4.4 间接方式,邮箱,Send(MB,M)消息M发送至邮箱MB,Receive(MB,N)由邮箱MB中接收消息至N,多发送者 多接收者;多发送者 单接收者,进程间通过信箱进行的通讯。,98,信箱属于操作系统（或用户）空间,Typedef mailbox struct in,out;/in the range of(0,n-1)semaphore s1,s2;semaphore mutex;message letterk;mailbox mb;定义信箱变量create_MB(mb);delete_MB(mb);Send_MB(mb);receive_MB(mb);,4

44、个操作系统调用命令,99,信箱通讯,发送进程：send_MB(mailbox A;massage M);P(A.s1);P(A.mutex);A.letterA.in=M;A.in=(A.in+1)%A.k;V(A.mutex);V(A.s2),100,信箱通讯,接收进程：receive_MB(mailbox A;massage N);P(A.s2);P(A.mutex);N=A.letterA.out;A.out=(A.out+1)%A.k;V(A.mutex);V(A.s1),101,属于操作系统空间的信箱,Var mb:mailbox,create_MB,delete_MB,send_M

45、B,receive_MB,creat_MB(mb)receive_MB(mb,N)delete_MB(mb)N:,send_MB(mb,M)M:,102,UNIX进程高级通讯机制,略,103,UNIX进程高级通讯机制,速度：pipe作为文件，需要两次IO，但一般不会真正执行IO操作:缓冲与延迟写(delayed write)Pipe文件大小的限制(Eg.2k)特点：基于文件系统实现，与文件统一的界面。,略,104,Windows2000/xp的管道,1.无名管道：BOOL CreatePipe(PHANDLE hReadPipe,PHANDLE hWritepipe,LPSECURITY_AT

46、TRIBUTES lpPipeAt,DWORD nSize)2.命名管道：服务器端：.pipePipeName;客户端：serverNamepipePipeNameCreateNamedPipe:在服务器端建立管道；ConnectNamedPipe:在服务器端等待客户连接请求；CallNamedPipe:客户进程建立与服务器管道连接；ReadFile,WriteFile:管道读写。,略,105,Windows2000/xp的mailslot,服务器端：.mailslotpathname客户进程：rangemailslotpathname range:本地或服务器CreatMailslot:服务

47、器端创建邮件槽；GetMailslotInfo:服务器查询邮件槽信息；ReadFile:服务器读邮件槽；WriteFile:客户端发送消息。,略,106,总 结,多道程序 并发程序设计并发程序的特性：交叉性 非封闭性 不可再现性并发程序可引发的错误：与时间有关的错误。,107,总 结,多道程序的基本矛盾（之一）：互斥：进程间共享资源引发的矛盾，即：进程对共享资源的互斥访问。问题的描述：共享变量：多进程共享 临界区：进程内访问共享变量的代码区问题的解决方法：互斥的访问共享变量 互斥的访问临界区,108,总 结,多道程序的基本矛盾（之二）：同步：合作进程间相互协作引发的时序问题问题的描述：进程运行

48、的速度需要协调，即：进程的执行有先后问题。问题解决的方法：进程间需相互等待（阻塞）或唤醒,109,总 结,解决互斥问题的方法：原则：正确性 公平性 进展性软件方法：Lamport算法 Eisenberg/Meguire算法软件方法的问题：忙等待,110,总 结,解决互斥问题的方法：硬件方法：设计硬件指令 多条指令实现的功能由一条指令实现 Test and Set,TS Swap R1=x;R1=R1+1;三条变一条 x=R1;,不能中断,111,总 结,方法图示：,X共享变量,进程ATS(lock)CSALock=0,进程BTS(lock)CSBLock=0,lock,112,总 结,解决互斥

49、、同步问题的机制信号量与P、V操作。信号量的定义：,S.valueS.queue,非负整数,等待于此信号量的进程队列,113,总 结,解决互斥、同步问题的机制两个原语：P、V,Void P(semaphore*s)s-value-;if(s-valuequeue);,Void V(semaphore*s)s-value+;if(s-valuequeue);,114,总 结,同步、互斥问题的一般性描述生产者/消费者问题：多生产者，多消费者 多缓冲区，各自使用各自的缓冲区读者/写者问题：多读者，多写者 共享同一缓冲区（资源）,115,总 结,解决同步、互斥问题的管程方法P、V操作方法：分散式同步机制管程方法：集中式同步机制,管程共享变量过程函数,进程队列,116,总 结,进程间的通讯：直接通信 间接通信,