进程同步与通讯.pptx

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