第九章节进程同步和通信

1、第九章节进程同步和通信4.2.5 进程同步与互斥举例 一、有限缓冲区问题 问题描述：设有问题描述：设有n n个缓冲区，一组生产个缓冲区，一组生产者进程往缓冲区写数据，一组消费者进程者进程往缓冲区写数据，一组消费者进程从缓冲区取数据，写取都以一个缓冲区为从缓冲区取数据，写取都以一个缓冲区为单位。单位。 说明：说明： 将缓冲池看做是共享数据，对缓冲区的将缓冲池看做是共享数据，对缓冲区的 操作必须是互斥操作。操作必须是互斥操作。 如果如果n n个缓冲区全满，生产者进程必须个缓冲区全满，生产者进程必须 等待。等待。 如果缓冲区全空，消费者进程必须等待。如果缓冲区全空，消费者进程必须等待。 有限缓冲区的

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

3、缓冲区生产者/ /消费者进程描述如下：消费者进程描述如下： 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(mutex); V(full); un

4、til 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，那些对它进行读，那些对它进行读访问者叫访问者叫ReaderReader，对它进行写访问者叫做，对它进

5、行写访问者叫做WriterWriter。 第一类第一类Reader/ WriterReader/ Writer问题：问题： ReaderReader和和WriterWriter争夺访问共享数据争夺访问共享数据A A时，时，ReaderReader有较高优先数。有较高优先数。 表现在：除了某个表现在：除了某个WriterWriter正在访问数正在访问数据之外，任何情况下据之外，任何情况下ReaderReader欲访问数据均欲访问数据均可以直接进行访问。可以直接进行访问。二、Readers/Writers问题该问题可具体描述为：1.1.如果当前无人访问数据，则如果当前无人访问数据，则Reader/

6、 WriterReader/ Writer欲访问即可访问。欲访问即可访问。2.2.如果已存在一个如果已存在一个ReaderReader正在访问数据，其他正在访问数据，其他欲访问欲访问ReaderReader可马上访问（这体现可马上访问（这体现ReaderReader有较有较高优先权）；而欲访问的高优先权）；而欲访问的WriterWriter必须等待。必须等待。3.3.若某个若某个WriterWriter正访问数据，则欲访问的正访问数据，则欲访问的Reader/ WriterReader/ Writer都必须等待。都必须等待。（续）4.4.当最后一个结束访问数据的当最后一个结束访问数据的Read

7、erReader发现有发现有WriterWriter正在等待时，则将其中一个唤醒。正在等待时，则将其中一个唤醒。5.5.当某个当某个WriterWriter结束访问时，若只有结束访问时，若只有WriterWriter在等待，则唤醒某个在等待，则唤醒某个WriterWriter，若既有，若既有WriterWriter也有也有ReaderReader；则按；则按FIFOFIFO或某它原则唤醒一个或某它原则唤醒一个WriterWriter或所有或所有ReaderReader。Reader的一般结构为：P(mutex)； readcount:=readcount+1; If readcount=1 t

8、hen 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,=0, ,4) ,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(),如果如果SIGUSR1S

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

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

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

16、nd( )的同步问题： 1.1.将发送者消息拷入通信链缓冲区，即将控将发送者消息拷入通信链缓冲区，即将控制返回发送者。制返回发送者。 2.2.在将消息从硬通信通道发出后，将控制返在将消息从硬通信通道发出后，将控制返回发送者。回发送者。 3.3.在消息由接收方节点的系统收到后，再将在消息由接收方节点的系统收到后，再将控制返回发送者。控制返回发送者。 4.4.在消息由接收方收到后，再将控制返回发在消息由接收方收到后，再将控制返回发送者。送者。 5.5.在消息由接收方处理完后，再将控制返回在消息由接收方处理完后，再将控制返回发送者（发送者（RPCRPC，LPCLPC）。）。 为实现为实现3.,4.3

17、.,4.情形同步，需要建立回送情形同步，需要建立回送到发送者所在系统的通信链，到发送者所在系统的通信链，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消息缓冲区消息缓冲区Send(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