第三章进程互斥与同步课件

第三章 进程互斥与同步进程通信进程通信Communication.进程通信(Communication)进程通信：指进程间的信息交换。进程通信：指进程间的信息交换。按通信内容可以划分为按通信内容可以划分为2种种低级通信低级通信：进程之间控制信息的交换称为低级通信。：进程之间控制信息的交换称为低级通信。一般只传送一个和几个字节的信息，达到控一般只传送一个和几个字节的信息，达到控 制进程执行速度的作用。（进程的同步和互斥）制进程执行速度的作用。（进程的同步和互斥）信号量机制作为同步工具是卓有成效的，但作为通讯工具则不够理信号量机制作为同步工具是卓有成效的，但作为通讯工具则不够理想，（想，（效率低。效率低。通讯对用户不透明。）通讯对用户不透明。）高级通信高级通信：用户可以直接利用操作系统所提供的一组通信：用户可以直接利用操作系统所提供的一组通信命令，高效地传送大量数据的一种通信方式。可大大简命令，高效地传送大量数据的一种通信方式。可大大简化通信程序编制上的复杂性。化通信程序编制上的复杂性。.w进程的同步与互斥是一种通讯方式，一进程可进程的同步与互斥是一种通讯方式，一进程可通过修改变量或信号量告知另一进程，它是否通过修改变量或信号量告知另一进程，它是否可以继续执行下去，利用生产者可以继续执行下去，利用生产者消费者算消费者算法，生产者进程可以传送一批数据给消费进程，法，生产者进程可以传送一批数据给消费进程，或者说生产者通过缓冲区与消费者进行通讯，或者说生产者通过缓冲区与消费者进行通讯，但但P、V操作只能操作只能传递信号传递信号，信号本身不包含任信号本身不包含任何数据，而进程不当还容易导致进程死锁，因何数据，而进程不当还容易导致进程死锁，因此，称这些同步机构为低级通讯机构。此，称这些同步机构为低级通讯机构。.进程通信的类型w高级通讯机制类型高级通讯机制类型1 共享存储器系统共享存储器系统(Shared-Memory System)2 消息传递系统消息传递系统(Message passing System)3 管道管道(Pipe)通信系统通信系统.1 共享存储器系统共享存储器系统共享存储器系统：相互通讯的进程通过共享：相互通讯的进程通过共享数据数据结构结构和和存储区存储区进行通讯，因而可进一步分为：进行通讯，因而可进一步分为：基于共享数据结构的通讯方式；（低效，只基于共享数据结构的通讯方式；（低效，只适于传递少量数据）适于传递少量数据）基于共享存储区的通讯方式。基于共享存储区的通讯方式。为了传送大量为了传送大量数据，在存储区中划出一块共享存储区，诸进数据，在存储区中划出一块共享存储区，诸进程可通过对共享存储区进行读或写数据实现通程可通过对共享存储区进行读或写数据实现通讯。讯。1向系统申请共享存储区中的一个分区2指定该分区的关键字3如果已经给其他进程分配了这样的存储区，4 将使用分区的描述符返回给申请者54 申请者将申请到的共享分区挂到本进程上.2 消息传递系统w在消息传递系统中，进程间的数据交换是以消在消息传递系统中，进程间的数据交换是以消息息(message，在计算机网络中又称报文，在计算机网络中又称报文)为单位。为单位。程序员直接利用系统提供的一组通讯命令（原程序员直接利用系统提供的一组通讯命令（原语）来实现通讯。语）来实现通讯。w因其实现方法的不同，又可分为因其实现方法的不同，又可分为 直接通信方式（消息缓冲机制）间接通信方式（信箱通信方式）.w直接通信方式：直接通信方式：发送进程直接将消息发送给接收进程，并将它挂发送进程直接将消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上。接收进程从消息缓在接收进程的消息缓冲队列上。接收进程从消息缓冲队列中取得消息。故称为冲队列中取得消息。故称为消息缓冲机制。消息缓冲机制。w间接通信方式：间接通信方式：发送进程将消息发送到某个中间实体（一般称为发送进程将消息发送到某个中间实体（一般称为信箱）中，接收进程从中取得消息，所以称为信箱）中，接收进程从中取得消息，所以称为信箱信箱通讯方式通讯方式，相应地系统称为电子邮件系统。，相应地系统称为电子邮件系统。.2.1消息缓冲机制（直接通信）w消息缓冲通讯技术由消息缓冲通讯技术由Hansen 首先提出的，基首先提出的，基本思想是：根据本思想是：根据“生产者生产者消费者关系消费者关系”原原理，利用公用消息缓冲区实现进程间的信息交理，利用公用消息缓冲区实现进程间的信息交换。换。w 发送进程先申请一个消息缓冲区，写入消息发送进程先申请一个消息缓冲区，写入消息后把该消息缓冲区送入接收进程的消息队列中，后把该消息缓冲区送入接收进程的消息队列中，通知接收进程。接收进程从消息队列中摘下一通知接收进程。接收进程从消息队列中摘下一消息缓冲区，取出所需要的信息。消息缓冲区，取出所需要的信息。.消息的一般形式 发送消息的进程名发送消息的进程名 接收消息的进程名接收消息的进程名消息长度消息长度 消息正文消息正文消息缓冲区的数据结构消息缓冲区的数据结构struct msg sender;/消息发送者名消息发送者名size;/消息长度消息长度 Text;/消息正文消息正文Next;/下一个消息的链指针下一个消息的链指针.PCB中增加相关数据项typedef struct process_control_block.mq;/消息队列消息队列 message queuemutex;/消息队列互斥信号量消息队列互斥信号量sm;/消息队列资源信号量消息队列资源信号量.send原语void send(receiver,a)getbuf(a.size,msg);/申请缓冲区申请缓冲区,存入存入msgmsg.sender=a.sender;msg.size=a.size;strcpy(a.text,msg.text);msg.next=0;j=getinternal_name(receiver);P(j.mutext);insert(j.mq,msg);/加入接收者的消息队加入接收者的消息队列列V(j.mutext);V(j.sm);/消息个数加消息个数加1,可能会唤醒接收者可能会唤醒接收者.receive 原语void receive(b)P(j.sm);/申请取消息申请取消息,若无则阻塞若无则阻塞P(j.mutext);/互斥访问消息队列互斥访问消息队列remove(j.mq,msg);/摘下一个消息摘下一个消息V(j.mutext);b.sender=msg.sender;b.size=msg.size;strcpy(msg.text,b.text);putbuf(msg);/释放消息所占空间释放消息所占空间.接收者进程接收者进程Receive(b)发送者进程发送者进程准备消息准备消息aSend(PB,a)OS消息缓冲区消息缓冲区MSGabPAPBPCPDPCBjSend(receiver,a)Receive(b)bMSG.用通信原语解决生产者-消费者问题使用原语使用原语 send(A,m1)和和 receive(B,m2)cobeginvoidproduceri(void)/i=1,2.kmsg nextp;while(1)nextp=produce_an_msg();send(consumerj,nextp);voidconsumerj(void)/j=1,2.m msgnextc;while(1)receive(produceri,nextc);consumemsg(nextc);.2.2邮箱通信（间接通信）w信（邮）箱信（邮）箱信箱是一种数据结构，逻辑上它分成两部分：信箱是一种数据结构，逻辑上它分成两部分：信箱信箱头头和由若干格子组成的和由若干格子组成的信箱体信箱体。信箱中每个格子存放一封信，信箱中格子的数目和信箱中每个格子存放一封信，信箱中格子的数目和每格的大小在创建信箱时确定。每格的大小在创建信箱时确定。w 进程间的通信要满足如下条件：进程间的通信要满足如下条件：发送进程发送消息时，邮箱中至少要有一个空格存发送进程发送消息时，邮箱中至少要有一个空格存放该消息。放该消息。接收进程接收消息时，邮箱中至少要有一个消息存接收进程接收消息时，邮箱中至少要有一个消息存在。在。.w信箱可由信箱可由OS创建，也可由用户进程创建，创建者是信创建，也可由用户进程创建，创建者是信箱的拥有者，据此可把信箱分为：私用信箱，公用信箱，箱的拥有者，据此可把信箱分为：私用信箱，公用信箱，共享信箱。共享信箱。w在利用信箱通信时，在发送进程和接收进程之间，存在在利用信箱通信时，在发送进程和接收进程之间，存在着四种关系：着四种关系：一对一关系：即可以为发送进程和接收进程建立一条专一对一关系：即可以为发送进程和接收进程建立一条专用的通信链路；用的通信链路；多对一关系：允许提供服务的进程与多个用户进程进行多对一关系：允许提供服务的进程与多个用户进程进行交互，也称客户交互，也称客户/服务器交互；服务器交互；一对多关系：允许一个发送进程与多个接收进程交互，一对多关系：允许一个发送进程与多个接收进程交互，使发送进程用广播的形式，发送消息；使发送进程用广播的形式，发送消息；多对多关系：允许建立一个公用信箱，让多个进程都能多对多关系：允许建立一个公用信箱，让多个进程都能向信箱投递消息，也可取走属于自己的消息。向信箱投递消息，也可取走属于自己的消息。.发送进程A 邮箱头 邮箱体接收进程接收进程B Bsend(mailbox,msg)receive(mailbox,msg)邮箱头：邮箱名称、邮箱大小、拥有该邮箱的进程名邮箱体：存放消息使用邮箱的时候应该满足：1发送进程发送消息时，邮箱中至少要有一个空格能存放该消息2接收进程接收消息时，邮箱中至少有一个消息存在邮箱通信结构.3 管道(Pipe)通信系统w管道（管道（pipe）通讯由）通讯由UNIX首创的一种借助文件首创的一种借助文件和文件系统形成的一种通信方式，。由于其有和文件系统形成的一种通信方式，。由于其有效性，一些系统继效性，一些系统继UNIX之后相继引入了管道技之后相继引入了管道技术，如术，如pc-dos，管道通信将成为进程通讯的一，管道通信将成为进程通讯的一种重要方式。种重要方式。消息缓冲通信机构是以内存缓冲区为基础。消息缓冲通信机构是以内存缓冲区为基础。管道是以文件系统为基础。管道是以文件系统为基础。w管道类型管道类型有名管道有名管道无名管道无名管道.管道 是指用于连接一个读进程和一个写进程，以是指用于连接一个读进程和一个写进程，以实现它们之间通信的共享方式，又称实现它们之间通信的共享方式，又称pipe文件。文件。向管道（共享文件）提供输入的发送进程向管道（共享文件）提供输入的发送进程（即写进程），以字符流形式将大量的数据送（即写进程），以字符流形式将大量的数据送入管道；而接收管道输出的接收进程（即读进入管道；而接收管道输出的接收进程（即读进程），可从管道接收数据，由于发送和接收都程），可从管道接收数据，由于发送和接收都是利用管道进行通信的，故称为是利用管道进行通信的，故称为管道通信管道通信。.w为了协调双方的通信，管道通信机制必须提供为了协调双方的通信，管道通信机制必须提供以下三方面的协调能力：以下三方面的协调能力：互斥。一个进程正在对互斥。一个进程正在对pipe进行读进行读/写操作时，另一写操作时，另一进程必须等待。进程必须等待。同步。当写（输入）进程把一定数量的数据写入同步。当写（输入）进程把一定数量的数据写入pipe后，便去睡眠等待，直到读（输出）进程取走后，便去睡眠等待，直到读（输出）进程取走数据将其唤醒；当读进程读一空数据将其唤醒；当读进程读一空pipe，也应睡眠等，也应睡眠等待，直至写进程将数据写入管道，才将其唤醒。待，直至写进程将数据写入管道，才将其唤醒。对方是否存在。只有确定对方已存在时，才能进行对方是否存在。只有确定对方已存在时，才能进行管道通信，否则会造成因对方不存在而无限期等待。管道通信，否则会造成因对方不存在而无限期等待。.管道通信的思想w1 发送进程可以源源不断的从发送进程可以源源不断的从pipe一端写入数一端写入数据流，在规定的据流，在规定的pipe文件的最大长度（如文件的最大长度（如4096字节）范围内，每次写入的信息长度是可变的字节）范围内，每次写入的信息长度是可变的w2 接收进程在需要时可以从接收进程在需要时可以从pipe的另一端读出的另一端读出数据，读出单位长度也是可变的数据，读出单位长度也是可变的.第三章 进程互斥与同步管程管程Monitors.管程的引入w用信号量和用信号量和P、V操作来解决进程互斥同步问题，操作来解决进程互斥同步问题，需在程序中需在程序中适当位置安排适当位置安排P、V操作操作，否则会造，否则会造成死锁错误。为了解决分散编程带来的困难，成死锁错误。为了解决分散编程带来的困难，采用资源集中管理的方法，用某种数据结构表采用资源集中管理的方法，用某种数据结构表示某类资源，并将这种数据结构以及与资源有示某类资源，并将这种数据结构以及与资源有关操作集中一起定义为关操作集中一起定义为类程或管程类程或管程，并用类程，并用类程管理独立资源，用管程管理共享资源，它两个管理独立资源，用管程管理共享资源，它两个是能被进程调用的实体。是能被进程调用的实体。.管程定义w一个管程定义了一个数据结构和能为并发进程一个管程定义了一个数据结构和能为并发进程调用的在该数据结构上的一组操作过程调用的在该数据结构上的一组操作过程,这组操这组操作过程能作过程能同步进程同步进程和和改变管程中的数据改变管程中的数据。w管程提供了一种可以允许多进程安全有效地共管程提供了一种可以允许多进程安全有效地共享抽象数据类型的机制，管程实现同步机制由享抽象数据类型的机制，管程实现同步机制由“条件结构条件结构”（condition construct）所提供。）所提供。w管程中的局部数据仅能被管程入口进程访问管程中的局部数据仅能被管程入口进程访问(该该类过程名前有关键字类过程名前有关键字 entry)。局部于管程的入。局部于管程的入口过程也仅能访问管程内的数据。口过程也仅能访问管程内的数据。.实现管程的关键问题-1w互斥互斥管程必须能有效地实现互斥。管程是被动成分管程必须能有效地实现互斥。管程是被动成分,进程进程是主动成分。是主动成分。进程调用管程入口函由一个互斥信号量来实现。进程调用管程入口函由一个互斥信号量来实现。该互斥机制由编译程序来实现该互斥机制由编译程序来实现,编写管程程序的人无编写管程程序的人无须关心编译程序如何实现互斥须关心编译程序如何实现互斥,也不会有应用的失误。也不会有应用的失误。.实现管程的关键问题-2w同步同步管程结构中提供两个同步操作原语管程结构中提供两个同步操作原语wait()和和signal()。当进程通过管程请求访问共享数据而未能被满足时当进程通过管程请求访问共享数据而未能被满足时,管程入口过程中便调用管程入口过程中便调用wait()原语阻塞该进程。原语阻塞该进程。当另一进程访问完该共享数据且释放资源后当另一进程访问完该共享数据且释放资源后,入口过入口过程调用程调用signal()原语唤醒等待队列中的首进程。原语唤醒等待队列中的首进程。.实现管程的关键问题-3w条件变量条件变量为区别等待的原因而引入条件变量。为区别等待的原因而引入条件变量。条件变量数据类型名为条件变量数据类型名为 condition不同的条件变量有不同原因不同的条件变量有不同原因,对应由不同原因的进程对应由不同原因的进程阻塞而成的队列。阻塞而成的队列。条件变量上能做条件变量上能做wait()和和 signal()原语操作原语操作,例某条例某条件变量名为件变量名为nonbusy,则调用同步原语的形式为则调用同步原语的形式为wait(nonbusy)和和 signal(nonbusy).利用管程解决生产者消费者问题w建立一个管程建立一个管程Producer_Consumer，它包括两个过程，它包括两个过程put（item）和）和get（item），它们分别执行将生产的消），它们分别执行将生产的消息放入缓冲池和从缓冲池取出消息的操作。息放入缓冲池和从缓冲池取出消息的操作。w设置一变量设置一变量count表示缓冲池已存消息数目表示缓冲池已存消息数目,缓冲池大小缓冲池大小为为n。w当当count=n时时,put(item)必须等待必须等待wait(empty),若若count+后为后为1,则表缓冲池中原来并无数据则表缓冲池中原来并无数据,则执行则执行signal(full),唤醒一个等待的消费者唤醒一个等待的消费者w当当count=0时时,get(item)必须等待必须等待wait(full),当当count后后count值为值为n-1,则表原来缓冲池是满的则表原来缓冲池是满的,需执需执行行signal(empty),唤醒一个等待的生产者。唤醒一个等待的生产者。.type producer_consumer=monitor;/类类pascalvarin,out,count:integer;buffer:array0n-1 of item;full,empty:condition;procedure entry put(var item);beginif count=n thenwait(empty);bufferin:=item;in:=(in+1)mod n;coutn:=count+1;if count=1 then signal(full);end.procedure entry get(var item);beginif count=0 thenwait(full);item:=bufferout;out:=(out+1)mod n;count:=count-1;if count=n-1 thensignal(empty);endbegin in:=0;out:=0;count:=0end if.var pc:producer_consumer;cobeginproducer:beginrepeatproduce an item in x;pc.put(x);until false;end/-consumer:beginrepeatpc.get(y);consume the item in y;until false;end coend.VC+中的同步的机制wCSemaphore,CMutex,CCriticalSection,and CEventwCCriticalSectionCCriticalSection An object of class,CCriticalSection represents a critical section-a synchronization object that allows one thread at a time to access a resource or section of code.Critical sections are useful when only one thread at a time can be allowed to modify data or some other controlled resource.MethodLock()Use to gain access to the CCriticalSection object.Unlock()Releases the CCriticalSection object.