进程管理part7.pptx

第二章 进 程 管 理 Heb Nomal University Department of Computer Science1返回 2.3.4 管 程 机 制 2.利用管程解决生产者-消费者问题 管程的提出 采用PV同步机制来编写并发程序，对于共享变量及信号量变量的操作将被分散于各个进程中。P/V缺点：（）易读性差。（）不利于修改和维护。（）正确性难以保证。因为操作系统或并发程序通常很大，要保证这样一个复杂的系统没有逻辑错误是很难的第二章 进 程 管 理 Heb Nomal University Department of Computer Science21.管程的基本概念 1)管程的定义 管程由三部分组成：局部于管程的共享变量说明；对该数据结构进行操作的一组过程；对局部于管程的数据设置初始值的语句。此外，还须为管程赋予一个名字。第二章 进 程 管 理 Heb Nomal University Department of Computer Science3图 2-11 管程的示意图 管程：集中式同步机制。它的基本思想是：将共享变量以及对共享变量能够进行的所有操作集中在一个模块中，一个操作系统或并发程序由若干个这样的模块所构成。由于一个模块通常较短，模块之间关系清晰，提高了可读性，便于修改和维护，正确性易于保证第二章 进 程 管 理 Heb Nomal University Department of Computer Science4管程的语法描述如下：type monitor_name=MONITOR；define；use ；procedure()；beginend;function()：值类型；beginend；begin ；end 第二章 进 程 管 理 Heb Nomal University Department of Computer Science5说明：l局部于管程内部的数据结构，仅能被局部于管程内部的过程所访问，任何管程外的过程都不能访问它；l反之，局部于管程内部的过程也仅能访问管程内的数据结构。由此可见，管程相当于围墙，它把共享变量和对它进行操作的若干过程围了起来，所有进程要访问临界资源时，都必须经过管程(相当于通过围墙的门)才能进入，而管程每次只准许一个进程进入管程，从而实现了进程互斥。第二章 进 程 管 理 Heb Nomal University Department of Computer Science6管程是一种程序设计语言结构成分，它和信号量有同等的表达能力，从语言的角度看，管程主要有以下特性：(1)模块化。管程是一个基本程序单位，可以单独编译。(2)抽象数据类型。管程中不仅有数据，而且有对数据的操作。(3)信息掩蔽。管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部定义的，供管程外的进程调用，而管程中的数据结构以及过程(函数)的具体实现外部不可见。第二章 进 程 管 理 Heb Nomal University Department of Computer Science7 管程的要素：管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量。为了保证管程共享变量的数据完整性，规定管程互斥进入。管程通常是用来管理资源的，因而在管程中应当设有进程等待队以及相应的等待及唤醒操作第二章 进 程 管 理 Heb Nomal University Department of Computer Science8 问题：多个进程出现在管程中 当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权；当一个进入管程的进程执行唤醒操作时（如唤醒），管程中便存在两个同时处于活动状态的进程。处理方法有三种：等待继续，直到退出或等待 等待继续，直到等待或退出 规定唤醒为管程中最后一个可执行的操作HoareHansan为了解决这类问题，引入了条件变量condition。通常，一个进程被阻塞或挂起的条件(原因)可有多个，因此在管程中设置了多个条件变量，对这些条件变量的访问，只能在管程中进行。第二章 进 程 管 理 Heb Nomal University Department of Computer Science92)条件变量 管程中对每个条件变量，都须予以说明，其形式为：Var x,y:condition。该变量应置于wait和signal之前，即可表示为X.wait和X.signal。例如，由于共享数据被占用而使调用进程等待，该条件变量的形式为：nonbusy:condition。此时，wait原语应改为nonbusy.wait，相应地，signal应改为nonbusy.signal。应当指出，X.signal操作的作用，是重新启动一个被阻塞的进程，但如果没有被阻塞的进程，则X.signal操作不产生任何后果。这与信号量机制中的signal操作不同。因为，后者总是要执行s=s+1操作，因而总会改变信号量的状态。第二章 进 程 管 理 Heb Nomal University Department of Computer Science10管程和进程的异同点：（1）设置进程和管程的目的不同（2）系统管理数据结构 进程：PCB 管程：等待队列（3）管程被进程调用（4）管程是操作系统的固有成分，无创建和撤消第二章 进 程 管 理 Heb Nomal University Department of Computer Science112.利用管程解决生产者-消费者问题 在利用管程方法来解决生产者-消费者问题时，首先便是为它们建立一个管程，并命名为Proclucer-Consumer,或简称为PC。其中包括两个过程：(1)put(item)过程。(2)get(item)过程。第二章 进 程 管 理 Heb Nomal University Department of Computer Science12 (1)put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量count来表示在缓冲池中已有的产品数目，当countn时，表示缓冲池已满，生产者须等待。(2)get(item)过程。消费者利用该过程从缓冲池中取出一个产品，当count0时，表示缓冲池中已无可取用的产品，消费者应等待。第二章 进 程 管 理 Heb Nomal University Department of Computer Science13type producer-consumer=monitor Var in,out,count:integer;buffer:array0,n-1 of item;notfull,notempty:condition;procedure entry put(item)begin if countn then notfull.wait;buffer(in)=nextp;in =(in+1)mod n;count =count+1;if notempty.queue then notempty.signal;end第二章 进 程 管 理 Heb Nomal University Department of Computer Science14 procedure entry get(item)begin if count0 then notempty.wait;nextc=buffer(out);out=(out+1)mod n;count=count-1;if notfull.quene then notfull.signal;end begin in =out =0;count=0 end 第二章 进 程 管 理 Heb Nomal University Department of Computer Science15 在利用管程解决生产者-消费者问题时，其中的生产者和消费者可描述为：producer:begin repeat produce an item in nextp;PC.put(item);until false;end consumer:begin repeat PC.get(item);consume the item in nextc;until false;end 第二章 进 程 管 理 Heb Nomal University Department of Computer Science2.6 进进 程程 通通 信信 2.6.1 进程通信的类型进程通信的类型 1.共享存储器系统共享存储器系统(Shared-Memory System)(1)基于共享数据结构共享数据结构的通信方式。(2)基于共享存储区共享存储区的通信方式。第二章 进 程 管 理 Heb Nomal University Department of Computer Science 2.消息传递系统消息传递系统(Message passing system)不论是单机系统、多机系统，还是计算机网络，消息传递机制都是用得最广泛的一种进程间通信的机制。在消息传递系统中，进程间的数据交换，是以格式化的消息(message)为单位的；在计算机网络中，又把message称为报文。程序员直接利用系统提供的一组通信命令(原语)进行通信。操作系统隐藏了通信的实现细节，大大减化了通信程序编制的复杂性，而获得广泛的应用。消息传递系统的通信方式属于高级通信方式。又因其实现方式的不同而进一步分成直直接接通通信信方方式式和间间接接通通信信方方式式两种。第二章 进 程 管 理 Heb Nomal University Department of Computer Science 3.管道管道(Pipe)通信通信 所谓“管道”，是指用用于于连连接接一一个个读读进进程程和和一一个个写写进进程程以以实实现现他他们们之之间间通通信信的的一一个个共共享享文文件件，又又名名pipe文文件件。向管道(共享文件)提供输入的发送进程(即写进程)，以字符流形式将大量的数据送入管道；而接受管道输出的接收进程(即读进程)，则从管道中接收(读)数据。由由于于发发送送进进程程和和接接收收进进程程是是利利用用管管道道进进行行通通信信的的，故故又又称称为为管管道道通通信信。这种方式首创于UNIX系统，由于它能有效地传送大量数据，因而又被引入到许多其它操作系统中。第二章 进 程 管 理 Heb Nomal University Department of Computer Science 为了协调双方的通信，管道机制必须提供以下三方面的协调能力：互互斥斥，即当一个进程正在对pipe执行读/写操作时，其它(另一)进程必须等待。同同步步，指当写(输入)进程把一定数量(如4 KB)的数据写入pipe，便去睡眠等待，直到读(输出)进程取走数据后，再把他唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入管道后，才将之唤醒。确确定定对对方方是是否否存存在在，只有确定了对方已存在时，才能进行通信。第二章 进 程 管 理 Heb Nomal University Department of Computer Science2.6.2 消息传递通信的实现方法消息传递通信的实现方法 1.直接通信方式直接通信方式 这是指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。此时，要求发送进程和接收进程都以显式方式提供对方的标识符。通常，系统提供下述两条通信命令(原语)：Send(Receiver,message);发送一个消息给接收进程；Receive(Sender,message);接收Sender发来的消息；例如，原语Send(P2,m1)表示将消息m1发送给接收进程P2;而原语Receive(P1，m1)则表示接收由P1发来的消息m1。第二章 进 程 管 理 Heb Nomal University Department of Computer Science 在某些情况下，接收进程可与多个发送进程通信，因此，它不可能事先指定发送进程。例如，用于提供打印服务的进程，它可以接收来自任何一个进程的“打印请求”消息。对于这样的应用，在接收进程接收消息的原语中的源进程参数，是完成通信后的返回值，接收原语可表示为：Receive(id,message);第二章 进 程 管 理 Heb Nomal University Department of Computer Science 我们还可以利用直接通信原语，来解决生产者-消费者问题。当生产者生产出一个产品(消息)后，便用Send原语将消息发送给消费者进程；而消费者进程则利用Receive原语来得到一个消息。如果消息尚未生产出来，消费者必须等待，直至生产者进程将消息发送过来。生产者-消费者的通信过程可分别描述如下：repeat produce an item in nextp;send(consumer,nextp);until false;repeat receive(producer,nextc);consume the item in nextc;until false;第二章 进 程 管 理 Heb Nomal University Department of Computer Science2.间接通信方式间接通信方式 (1)信信箱箱的的创创建建和和撤撤消消。进进程程可可利利用用信信箱箱创创建建原原语语来来建建立立一一个个新新信信箱箱。创创建建者者进进程程应应给给出出信信箱箱名名字字、信信箱箱属属性性(公公用用、私私用用或或共共享享)；对对于于共共享享信信箱箱，还还应应给给出出共共享享者者的的名名字字。当当进进程程不不再需要读信箱时，可用信箱撤消原语将之撤消。再需要读信箱时，可用信箱撤消原语将之撤消。(2)消消息息的的发发送送和和接接收收。当当进进程程之之间间要要利利用用信信箱箱进进行行通通信信时时，必必须须使使用用共共享享信信箱箱，并并利利用用系系统统提提供供的的下下述述通通信信原原语语进进行行通通信信。Send(mailbox,message);将一个消息发送到指定信箱；将一个消息发送到指定信箱；Receive(mailbox,message);从指定信箱中接收一个消息；从指定信箱中接收一个消息；第二章 进 程 管 理 Heb Nomal University Department of Computer Science 信信箱箱可可由由操操作作系系统统创创建建，也也可可由由用用户户进进程程创创建建，创创建建者是信箱的拥有者。据此，可把信箱分为以下三类。者是信箱的拥有者。据此，可把信箱分为以下三类。1)私用信箱私用信箱 用用户户进进程程可可为为自自己己建建立立一一个个新新信信箱箱，并并作作为为该该进进程程的的一一部部分分。信信箱箱的的拥拥有有者者有有权权从从信信箱箱中中读读取取消消息息，其其他他用用户户则则只只能能将将自自己己构构成成的的消消息息发发送送到到该该信信箱箱中中。这这种种私私用用信信箱箱可可采采用用单单向向通通信信链链路路的的信信箱箱来来实实现现。当当拥拥有有该该信信箱箱的的进进程程结束时，信箱也随之消失。结束时，信箱也随之消失。第二章 进 程 管 理 Heb Nomal University Department of Computer Science 2)公用信箱公用信箱 它它由由操操作作系系统统创创建建，并并提提供供给给系系统统中中的的所所有有核核准准进进程程使使用用。核核准准进进程程既既可可把把消消息息发发送送到到该该信信箱箱中中，也也可可从从信信箱箱中中读读取取发发送送给给自自己己的的消消息息。显显然然，公公用用信信箱箱应应采采用用双双向向通通信信链链路路的的信信箱箱来来实实现现。通通常常，公公用用信信箱箱在在系系统统运运行行期期间间始始终存在。终存在。3)共享信箱共享信箱 它它由由某某进进程程创创建建，在在创创建建时时或或创创建建后后，指指明明它它是是可可共共享享的的，同同时时须须指指出出共共享享进进程程(用用户户)的的名名字字。信信箱箱的的拥拥有有者者和和共共享者，都有权从信箱中取走发送给自己的消息。享者，都有权从信箱中取走发送给自己的消息。第二章 进 程 管 理 Heb Nomal University Department of Computer Science 在在利利用用信信箱箱通通信信时时，在在发发送送进进程程和和接接收收进进程程之之间间，存存在在以以下四种关系：下四种关系：(1)一一对对一一关关系系。这这时时可可为为发发送送进进程程和和接接收收进进程程建建立立一一条条两两者专用的通信链路，使两者之间的交互不受其他进程的干扰。者专用的通信链路，使两者之间的交互不受其他进程的干扰。(2)多多对对一一关关系系。允允许许提提供供服服务务的的进进程程与与多多个个用用户户进进程程之之间间进行交互，也称为客户进行交互，也称为客户/服务器交互服务器交互(client/server interaction)。(3)一一对对多多关关系系。允允许许一一个个发发送送进进程程与与多多个个接接收收进进程程进进行行交互，使发送进程可用广播方式，向接收者交互，使发送进程可用广播方式，向接收者(多个多个)发送消息。发送消息。(4)多多对对多多关关系系。允允许许建建立立一一个个公公用用信信箱箱，让让多多个个进进程程都都能向信箱中投递消息；也可从信箱中取走属于自己的消息。能向信箱中投递消息；也可从信箱中取走属于自己的消息。第二章 进 程 管 理 Heb Nomal University Department of Computer Science2.6.3 消息传递系统实现中的若干问题消息传递系统实现中的若干问题 1.通信链路通信链路(communication link)为使在发送进程和接收进程之间能进行通信，必须在两者之间建立一条通信链路。有两种方式建立通信链路。第一种方式是：由发送进程在通信之前，用显式的“建立连接”命令(原语)请求系统为之建立一条通信链路；在链路使用完后，也用显式方式拆除链路。这这种种方方式式主主要要用用于于计计算算机机网络中。网络中。第二种方式是发送进程无须明确提出建立链路的请求，只须利用系统提供的发送命令(原语)，系统会自动地为之建立一条链路。这种方式主要用于单机系统中。这种方式主要用于单机系统中。第二章 进 程 管 理 Heb Nomal University Department of Computer Science 根据通通信信链链路路的的连连接接方方法法，又可把通信链路分为两类：点点连接通信链路，这时的一条链路只连接两个结点(进程)；多点连接链路，指用一条链路连接多个(n2)结点(进程)。而根根据据通通信信方方式式的不同，则又可把链路分成两种：单向通信链路，只允许发送进程向接收进程发送消息；双向链路，既允许由进程A向进程B发送消息，也允许进程B同时向进程A发送消息。第二章 进 程 管 理 Heb Nomal University Department of Computer Science2.消息的格式消息的格式 在某些OS中，消息是采用比较较短短的的定定长长消消息息格式，这减少了对消息的处理和存储开销。这种方式可用于办公自动化系统中，为用户提供快速的便笺式通信；但这对要发送较长消息的用户是不方便的。在有的OS中，采用另一种变变长长的的消消息息格格式式，即进程所发送消息的长度是可变的。系统在处理和存储变长消息时，须付出更多的开销，但方便了用户。这两种消息格式各有其优缺点，故在很多系统(包括计算机网络)中，是同时都用的。第二章 进 程 管 理 Heb Nomal University Department of Computer Science3.进程同步方式进程同步方式(1)发送进程阻塞、接收进程阻塞。(2)发送进程不阻塞、接收进程阻塞。(3)发送进程和接收进程均不阻塞。第二章 进 程 管 理 Heb Nomal University Department of Computer Science2.6.4 消息缓冲队列通信机制消息缓冲队列通信机制 1.消息缓冲队列通信机制中的数据结构消息缓冲队列通信机制中的数据结构 (1)消息缓冲区。在消息缓冲队列通信方式中，主要利用的数据结构是消息缓冲区。它可描述如下：type message buffer=record sender;发送者进程标识符发送者进程标识符 size;消息长度消息长度 text;消息正文消息正文 next;指向下一个消息缓冲区的指针指向下一个消息缓冲区的指针 end 第二章 进 程 管 理 Heb Nomal University Department of Computer Science (2)PCB中有关通信的数据项。在利用消息缓冲队列通信机制时，在设置消息缓冲队列的同时，还应增加用于对消息队列进行操作和实现同步的信号量，并将它们置入进程 的 PCB中。在 PCB中 应 增 加 的 数 据 项 可 描 述 如 下：type processcontrol block=record mq;消息队列队首指针消息队列队首指针 mutex;消息队列互斥信号量消息队列互斥信号量 sm;消息队列资源信号量消息队列资源信号量 end 第二章 进 程 管 理 Heb Nomal University Department of Computer Science 2.发送原语发送原语 发送进程在利用发送原语发送消息之前，应先在自己的内存空间，设置一发送区a，见图 2-12 所示，把待发送的消息正文、发送进程标识符、消息长度等信息填入其中，然后调用发送原语，把消息发送给目标(接收)进程。发送原语首先根据发送区a中所设置的消息长度a.size来申请一缓冲区i，接着，把发送区a中的信息复制到缓冲区i中。为了能将i挂在接收进程的消息队列mq上，应先获得接收进程的内部标识符j，然后将i挂在j.mq上。由于该队列属于临界资源，故在执行insert操作的前后，都要执行wait和signal操作。第二章 进 程 管 理 Heb Nomal University Department of Computer Science图 2-12 消息缓冲通信 第二章 进 程 管 理 Heb Nomal University Department of Computer Science procedure send(receiver,a)begin getbuf(a.size,i);根据根据a.size申请缓冲区申请缓冲区；i.sender =a.sender;将发送区将发送区a中的信息复制到消息缓冲区之中；中的信息复制到消息缓冲区之中；i.size =a.size;i.text =a.text;i.next =0;getid(PCB set,receiver.j);获得接收进程内部标识符获得接收进程内部标识符；wait(j.mutex);insert(j.mq,i);将消息缓冲区插入消息队列；将消息缓冲区插入消息队列；signal(j.mutex);signal(j.sm);end 第二章 进 程 管 理 Heb Nomal University Department of Computer Science3.接收原语接收原语 接收原语描述如下：接收原语描述如下：procedure receive(b)begin j =internal name;j为接收进程内部的标识符为接收进程内部的标识符；wait(j.sm);wait(j.mutex);remove(j.mq,i);将消息队列中第一个消息移出；将消息队列中第一个消息移出；signal(j.mutex);b.sender =i.sender;将将消消息息缓缓冲冲区区i中中的的信信息息复复制制到到接接收收区区b;b.size =i.size;b.text =i.text;end