九章节进程同步与通信.PPT

《九章节进程同步与通信.PPT》由会员分享，可在线阅读，更多相关《九章节进程同步与通信.PPT（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、九章节进程同步与通信 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望4.2.5 进程同步与互斥举例 一、有限缓冲区问题 问题描述：问题描述：设有设有n n个缓冲区，一组生产者个缓冲区，一组生产者进程往缓冲区写数据，一组消费者进程从缓进程往缓冲区写数据，一组消费者进程从缓冲区取数据，写取都以一个缓冲区为单位。冲区取数据，写取都以一个缓冲区为单位。说明：说明：将缓冲池看做是共享数据，对缓冲区的将缓冲池看做是共享数据，对缓冲区的 操作必须是互斥操作。操作必须是互斥操作。

2、如果如果n n个缓冲区全满，生产者进程必须个缓冲区全满，生产者进程必须 等待。等待。如果缓冲区全空，消费者进程必须等待。如果缓冲区全空，消费者进程必须等待。有限缓冲区的生产者有限缓冲区的生产者/消费者问题（生消费者问题（生产者和消费者共享一个产品缓冲池）。产者和消费者共享一个产品缓冲池）。共享N个缓冲区P1 P2 Pm C1 C2 Cn生生产产者者消消费费者者缓冲池缓冲池解：解：设置以下信号量设置以下信号量mutex,mutex,初值为初值为1 1，控制互斥访问缓冲池。，控制互斥访问缓冲池。full,full,初值为初值为0 0，表示当前缓冲池中满缓冲区，表示当前缓冲池中满缓冲区数，用于同步。

3、数，用于同步。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;

4、P(empty);P(mutex);add nextp to buffer;V(mutex);V(full);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(mutex);V(empty);若存在一共享数据若存在一共享数据A A，那些对它进

5、行读，那些对它进行读访问者叫访问者叫ReaderReader，对它进行写访问者叫做，对它进行写访问者叫做WriterWriter。第一类第一类Reader/WriterReader/Writer问题：问题：Reader Reader和和WriterWriter争夺访问共享数据争夺访问共享数据A A时，时，ReaderReader有较高优先数。有较高优先数。表现在：除了某个表现在：除了某个WriterWriter正在访问数正在访问数据之外，任何情况下据之外，任何情况下ReaderReader欲访问数据均欲访问数据均可以直接进行访问。可以直接进行访问。二、Readers/Writers问题该问题可

6、具体描述为：1.1.如果当前无人访问数据，则如果当前无人访问数据，则Reader/WriterReader/Writer欲访问即可访问。欲访问即可访问。2.2.如果已存在一个如果已存在一个ReaderReader正在访问数据，其他正在访问数据，其他欲访问欲访问ReaderReader可马上访问（这体现可马上访问（这体现ReaderReader有较有较高优先权）；而欲访问的高优先权）；而欲访问的WriterWriter必须等待。必须等待。3.3.若某个若某个WriterWriter正访问数据，则欲访问的正访问数据，则欲访问的Reader/WriterReader/Writer都必须等待。都必须等

7、待。（续）4.4.当最后一个结束访问数据的当最后一个结束访问数据的ReaderReader发现有发现有WriterWriter正在等待时，则将其中一个唤醒。正在等待时，则将其中一个唤醒。5.5.当某个当某个WriterWriter结束访问时，若只有结束访问时，若只有WriterWriter在在等待，则唤醒某个等待，则唤醒某个WriterWriter，若既有，若既有WriterWriter也有也有ReaderReader；则按；则按FIFOFIFO或某它原则唤醒一个或某它原则唤醒一个WriterWriter或所有或所有ReaderReader。Reader的一般结构为：P(mutex)；read

8、count:=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）;三、哲学家就餐问题 问题描述：问题描述：五个哲学家五只筷子，五个哲学家五只筷子，哲学家循环做着思考和吃饭的动作，吃哲学家循环做着思考和吃饭的动作，吃饭程序是：先取左边筷子，再取右边筷饭程序是：先取左边筷子，再取右边筷子，再吃饭，再放筷子。子，再吃饭，再放筷子。实现

9、：实现：为每个筷子设一把锁（信号量，初值为每个筷子设一把锁（信号量，初值为为1 1）每个哲学家是一个进程。共享数据结构为：）每个哲学家是一个进程。共享数据结构为：Var Chopstick;array 0,4of semaphore;Var Chopstick;array 0,4of semaphore;第第i i个进程描述为个进程描述为(i i=0,4)=0,4)repeat P（chopsticki）;P(chopstick(i+1)mod 5)；吃 V(chopsticki);V(Chopstick(i+1)mod 5；思考 until false;(这可能导致死锁这可能导致死锁)4.3

10、 进程通信 两种基本进程通信方法：两种基本进程通信方法：1.1.共享存储（共享存储（Shared-memoryShared-memory）：相互：相互通信的进程有共享存储区。进程间可通信的进程有共享存储区。进程间可以通过直接读写共享存储区的变量来以通过直接读写共享存储区的变量来交互数据，同步与互斥在并发程序设交互数据，同步与互斥在并发程序设计时安排进入程序。操作系统提供这计时安排进入程序。操作系统提供这样的共享存储区及某些同步互斥工具。样的共享存储区及某些同步互斥工具。2.2.消息传递消息传递(message-passing)(message-passing)：若进：若进程间无共享空间，则必须

11、通过消息传程间无共享空间，则必须通过消息传递通信，且必须通过递通信，且必须通过OSOS系统调用实现。系统调用实现。消息传递系统调用语句的一般形式:发送：发送：Send&Send&消息消息 to to 目的地标识目的地标识 接收：接收：Receive&Receive&消息消息 from from 源地址标识源地址标识.一、消息传递方法 1.直接通信法 基本思想：基本思想：进程在发送和接收消息时直进程在发送和接收消息时直接指明接收者或发送者进程接指明接收者或发送者进程IDID。缺点：缺点：必须指定接收进程必须指定接收进程IDID（UNIXUNIX的信的信号机制类似这种形式）。号机制类似这种形式）。

12、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 信号未到，则系统登记信号未

13、到，则系统登记funcfunc函数，函数，待其信号到时再调用执行。待其信号到时再调用执行。2.间接通信法（信箱命名法基本思想：基本思想：系统为每个信箱设一个消息队系统为每个信箱设一个消息队列，消息发送和接收都指向该消息队列，列，消息发送和接收都指向该消息队列，（每个进程可以对消息队列发送并接收（每个进程可以对消息队列发送并接收/只只发送发送/只接收只接收)缺点缺点：必须有一个通信双方共享的一个逻：必须有一个通信双方共享的一个逻辑消息队列（辑消息队列（UNIXUNIX的的PIPEPIPE，FIFOFIFO及及IPCIPC消息消息传递机制都属于这种形式），使用时消息传递机制都属于这种形式），使用时

14、消息发送者约定写方式打开信箱发送者约定写方式打开信箱,消息接收者约消息接收者约定读方式打开信箱或同时读写打开。定读方式打开信箱或同时读写打开。优点优点：很容易建立双向通信链：很容易建立双向通信链(只要对信箱只要对信箱说明为读写打开说明为读写打开)。逻辑通信链容量：在通信发送者和接收者之间存在一条逻辑通在通信发送者和接收者之间存在一条逻辑通信链，设链的容量是指该链暂存消息的能力。信链，设链的容量是指该链暂存消息的能力。1.1.容量为容量为0 0，表示链中无缓冲，表示链中无缓冲(不计链头的发不计链头的发送缓冲和链尾的接收缓冲送缓冲和链尾的接收缓冲)，这要求接收方必须，这要求接收方必须在发送方之前发

15、接收请求，否则发送失败。在发送方之前发接收请求，否则发送失败。2.2.有限容量，表示链中有有限缓冲区、发送有限容量，表示链中有有限缓冲区、发送者不必等接收者发出接收请求，不必等接收者准者不必等接收者发出接收请求，不必等接收者准备好接收缓冲区，即可将消息存于通信链中的缓备好接收缓冲区，即可将消息存于通信链中的缓冲区中。冲区中。3.3.消息从发送方缓冲进入系统缓冲区，即可消息从发送方缓冲进入系统缓冲区，即可再次发新消息，无需等上一消息被完全接收。再次发新消息，无需等上一消息被完全接收。二、缓冲与同步发送者执行send()的同步问题：1.1.将发送者消息拷入通信链缓冲区，即将控将发送者消息拷入通信链

16、缓冲区，即将控制返回发送者。制返回发送者。2.2.在将消息从硬通信通道发出后，将控制返在将消息从硬通信通道发出后，将控制返回发送者。回发送者。3.3.在消息由接收方节点的系统收到后，再将在消息由接收方节点的系统收到后，再将控制返回发送者。控制返回发送者。4.4.在消息由接收方收到后，再将控制返回发在消息由接收方收到后，再将控制返回发送者。送者。5.5.在消息由接收方处理完后，再将控制返回在消息由接收方处理完后，再将控制返回发送者（发送者（RPCRPC，LPCLPC）。）。为实现为实现3.,4.3.,4.情形同步，需要建立回送情形同步，需要建立回送到发送者所在系统的通信链，到发送者所在系统的通信

17、链，5.5.的情形需的情形需要建立回送到发送者的通信链。要建立回送到发送者的通信链。4.3.2 进程通信示例 直接通信消息系统的两个基本操作为：直接通信消息系统的两个基本操作为：send(A)send(A)：A A指向含接收者指向含接收者pidpid和消息正和消息正 文的空间。文的空间。Receive(A)Receive(A)：A A指向缓冲区用于接收消指向缓冲区用于接收消 息，该系统调用函数返回值息，该系统调用函数返回值 是消息发送者是消息发送者pidpid。实现：系统有一用于进程通系统有一用于进程通信的缓冲池，池中缓冲区用信的缓冲池，池中缓冲区用于存放消息及消息发送者于存放消息及消息发送者

18、pidpid和消息链指针和消息链指针(用用pidpid定定位进程位进程PCBPCB表表)。Senders pid消息正文Link消息缓冲区消息缓冲区 每个进程有一个消息队列，存放发送给每个进程有一个消息队列，存放发送给该进程的消息，队列头存于该进程的消息，队列头存于PCBPCB中，同时在中，同时在PCBPCB中设一互斥信号量中设一互斥信号量mutex(mutex(初值为初值为1)1)和一和一同步通信的信号量同步通信的信号量SmSm（初值为（初值为0 0），），SmSm也用也用于计录消息队列中的消息数。于计录消息队列中的消息数。.mutexSm.Senders pidtextSenders pi

19、dtextReceivers PCB message messageHptrSend(A):Send(A):begin begin New(p)New(p)；从缓冲池得一个；从缓冲池得一个bufferbuffer .置置senders pidsenders pid；将将A A中消息送中消息送buffer pbuffer p；获得获得Receivers pidReceivers pid；P(mutex)P(mutex)；将将buffer pbuffer p挂入相应的消息队列；挂入相应的消息队列；V(Sm)V(Sm)；V(mutex)V(mutex)；endend；Receive(A)Receiv

20、e(A)：begin begin P(Sm)P(Sm)；P(mutex)P(mutex)；从本进程的消息队列取一个从本进程的消息队列取一个buffer fbuffer f；V(mutex)V(mutex)；从从buffer fbuffer f中取得消息正文送中取得消息正文送A,A,并得到并得到 senders pid senders pid作为作为Receive()Receive()的返回值；的返回值；.dispose(f)dispose(f)；#释放释放buffer fbuffer f到缓冲池到缓冲池 end end；注注:new,dispose:new,dispose函数对函数对缓冲池的访问也需要互斥缓冲池的访问也需要互斥.