进程同步与通信概要.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,第九讲 进程同步与通信,目的与要求,：,掌握信号量解决进程同步互斥问题的方法，掌握进程通信的基本实现方法。,重点与难点,：,信号量的典型应用，通信实现。,作业,：,15,，,16,，,17,。,4.2.5,进程同步与互斥举例,一、有限缓冲区问题,问题描述：,设有,n,个缓冲区，一组生产者进程往缓冲区写数据，一组消费者进程从缓冲区取数据，写取都以一个缓冲区为单位。,说明：,将缓冲池看做是共享数据，对缓冲区的,操作必须是互斥操作。,如果,n,个缓冲区全满，生产者进程必须,等待。,如果缓冲区全空，消费者进程必须等待。,有限缓冲区的生产者,/,消费者问题（生产者和消费者共享一个产品缓冲池）。,共享,N,个缓冲区,P1 P2 P,m,C1 C2 C,n,生产者,消费者,缓冲池,解：,设置以下信号量,mutex,初值为,1,，控制互斥访问缓冲池。,full,初值为,0,，表示当前缓冲池中满缓冲区数，用于同步。,empty,初值为,n,，表示当前缓冲池中空缓冲区数，用于同步。,有限缓冲区生产者,/,消费者进程描述如下：,type item=,;,var buffer=,;,full,empty,mutex:semaphor;,nextp,nextc:item;,begin,full:=0;empty:=n;mutex:=1;,P(empty);,P(mutex);,add nextp to buffer;,V(mutex);,V(full);,until false;,end;,Parbegin,Producer:begin,repeat,produce an item in nextp;,.,consume the item in nextc;,until false;,end;,Parend;,consumer:begin,repeat,P(full);,P(mutex);,remove an item from buffer to nextc,释放缓冲区,V(mutex);,V(empty)若存在一共享数据,A,，那些对它进行读访问者叫,Reader,，对它进行写访问者叫做,Writer,。,第一类,Reader/Writer,问题：,Reader,和,Writer,争夺访问共享数据,A,时，,Reader,有较高优先数。,表现在：除了某个,Writer,正在访问数据之外，任何情况下,Reader,欲访问数据均可以直接进行访问。,二、,Readers/Writers,问题,该问题可具体描述为：,1.,如果当前无人访问数据，则,Reader/Writer,欲访问即可访问。,2.,如果已存在一个,Reader,正在访问数据，其他欲访问,Reader,可马上访问（这体现,Reader,有较高优先权）；而欲访问的,Writer,必须等待。,3.,若某个,Writer,正访问数据，则欲访问的,Reader/Writer,都必须等待。,（续）,4.,当最后一个结束访问数据的,Reader,发现有,Writer,正在等待时，则将其中一个唤醒。,5.,当某个,Writer,结束访问时，若只有,Writer,在等待，则唤醒某个,Writer,，若既有,Writer,也有,Reader,；则按,FIFO,或某它原则唤醒一个,Writer,或所有,Reader,。,Reader,的一般结构为：,P(mutex),；,readcount:=readcount+1;,If readcount=1 then,P(wrt);,V(mutex),；,读数据,A,P,（,mutex,）；,readcount:=readcount-1;,If readcount=0 then,V(wrt);,V(mutex);,Writer,的一般结构为：,P,（,wrt,）,;,写数据,A,V,（,wrt,）,;,三、哲学家就餐问题,问题描述：,五个哲学家五只筷子，哲学家循环做着思考和吃饭的动作，吃饭程序是：先取左边筷子，再取右边筷子，再吃饭，再放筷子。,实现：,为每个筷子设一把锁（信号量，初值为,1,）每个哲学家是一个进程。共享数据结构为：,Var Chopstick;array 0,4of semaphore;,第,i,个进程描述为,(,i,=0,4),repeat,P,（,chopsticki,）,;,P(chopstick(i+1)mod 5),；,吃,V(chopsticki);,V(Chopstick(i+1)mod 5,；,思考,until false;,(,这可能导致死锁,),4.3,进程通信,两种基本进程通信方法：,1.,共享存储（,Shared-memory,）：,相互通信的进程有共享存储区。进程间可以通过直接读写共享存储区的变量来交互数据，同步与互斥在并发程序设计时安排进入程序。操作系统提供这样的共享存储区及某些同步互斥工具。,2.,消息传递,(message-passing),：,若进程间无共享空间，则必须通过消息传递通信，且必须通过,OS,系统调用实现。,消息传递系统调用语句的一般形式,:,发送：,Send&,消息,to,目的地标识,接收：,Receive&,消息,from,源地址标识,.,一、消息传递方法,1.,直接通信法,基本思想：,进程在发送和接收消息时直接指明接收者或发送者进程,ID,。,缺点：,必须指定接收进程,ID,（,UNIX,的信号机制类似这种形式）。,4.3.1,消息传递通信原理,举例：（,UNIX,中两进程利用信号通信）。,Process A,kill(1040,SIGUSR1);,#,向,1040,号进程发送 一个,SIGUSR1信号。,Process B,Signal(SIGUSR1,func);,#,当收到,SIGUSR1,信,号时，就执行,func(),如果,SIGUSR1,信号未到，则系统登记,func,函数，,待其信号到时再调用执行。,2.,间接通信法（信箱命名法,基本思想：,系统为每个信箱设一个消息队列，消息发送和接收都指向该消息队列，（每个进程可以对消息队列发送并接收,/,只发送,/,只接收,),缺点：,必须有一个通信双方共享的一个逻辑消息队列（,UNIX,的,PIPE,，,FIFO,及,IPC,消息传递机制都属于这种形式），使用时消息发送者约定写方式打开信箱,消息接收者约定读方式打开信箱或同时读写打开优点：,很容易建立双向通信链,(,只要对信箱说明为读写打开,),。,逻辑通信链容量：,在通信发送者和接收者之间存在一条逻辑通信链，设链的容量是指该链暂存消息的能力。,1.,容量为,0,，表示链中无缓冲,(,不计链头的发送缓冲和链尾的接收缓冲,),，这要求接收方必须在发送方之前发接收请求，否则发送失败。,2.,有限容量，表示链中有有限缓冲区、发送者不必等接收者发出接收请求，不必等接收者准备好接收缓冲区，即可将消息存于通信链中的缓冲区中。,3.,消息从发送方缓冲进入系统缓冲区，即可再次发新消息，无需等上一消息被完全接收。,二、缓冲与同步,发送者执行,send(),的同步问题：,1.,将发送者消息拷入通信链缓冲区，即将控制返回发送者。,2.,在将消息从硬通信通道发出后，将控制返回发送者。,3.,在消息由接收方节点的系统收到后，再将控制返回发送者。,4.,在消息由接收方收到后，再将控制返回发送者。,5.,在消息由接收方处理完后，再将控制返回发送者（,RPC,，,LPC,）。,为实现,3.,4.,情形同步，需要建立回送到发送者所在系统的通信链，,5.,的情形需要建立回送到发送者的通信链。,4.3.2,进程通信示例,直接通信消息系统的两个基本操作为：,send(A),：,A,指向含接收者,pid,和消息正,文的空间。,Receive(A),：,A,指向缓冲区用于接收消,息，该系统调用函数返回值,是消息发送者,pid,。,实现,：,系统有一用于进程通信的缓冲池，池中缓冲区用于存放消息及消息发送者,pid,和消息链指针,(,用,pid,定位进程,PCB,表,),。,Senders pid,消息正文,Link,消息缓冲区,每个进程有一个消息队列，存放发送给该进程的消息，队列头存于,PCB,中，同时在,PCB,中设一互斥信号量,mutex(,初值为,1),和一同步通信的信号量,Sm,（初值为,0,），,Sm,也用于计录消息队列中的消息数。,.,mutex,Sm,.,Senders pid,text,Senders pid,text,Receivers PCB message message,Hptr,Send(A):,begin,New(p),；从缓冲池得一个,buffer,.,置,sender,s pid,；,将,A,中消息送,buffer p,；,获得,Receiver,s pid,；,P(mutex),；,将,buffer p,挂入相应的消息队列；,V(Sm),；,V(mutex),；,end,；,Receive(A),：,begin,P(Sm),；,P(mutex),；,从本进程的消息队列取一个,buffer f,；,V(mutex),；,从,buffer f,中取得消息正文送,A,并得到,sender,s pid,作为,Receive(),的返回值；,.,dispose(f),；,#,释放,buffer f,到缓冲池,end,；,注,:new,dispose,函数对,缓冲池的访问也需要互斥,.,