《二章进程管理.ppt》由会员分享，可在线阅读，更多相关《二章进程管理.ppt（44页珍藏版）》请在三一文库上搜索。
1、第二章 进程管理,2.1 进程的基本概念 2.2 进程控制 2.3 进程同步 2.4 经典进程的同步问题 2.5 管程机制,上节回顾,四种信号量的比较 生产者-消费者问题 两私一公的典型，公用信号量与私用信号量 公用信号量用于资源（变量）互斥，一般在同个过程中 私用信号量用于进程控制，多交叉在不同过程中 先私后公 哲学家就餐问题：AND信号量,1. 利用记录型信号量解决生产者消费者问题 具有n个缓冲区公用缓冲池中 互斥信号量mutex实现诸进程对缓冲池的互斥使用 信号量empty表示缓冲池中空缓冲区数量。 信号量full表示缓冲池中满缓冲区的数量。 mutex为公用信号量，full与empty
2、与私用信号量 假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。,Var mutex, empty, full:semaphore=1,n,0; buffer:array0, , n-1 of item; in, out: integer=0, 0; begin parbegin proceducer:begin repeat producer an item nextp; wait(empty); wait(mutex); buffer(in)=nextp; in=(in+1) mod n; signal(mutex
3、); signal(full); until false; end,consumer:begin repeat wait(full); wait(mutex); nextc =buffer(out); out =(out+1) mod n; signal(mutex); signal(empty); consumer the item in nextc; until false; end parend end,2.4.3 读者-写者问题,1. 利用记录型信号量解决读者-写者问题 互斥信号量Wmutex：实现Reader与Writer进程的互斥 整型变量Readcount表示正在读的进程数目。
4、仅当Readcount=0, 表示尚无Reader进程在读时，Reader进程才需要执行wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader进程便可去读，相应地，做Readcount+1操作。 仅当Reader进程在执行了Readcount减1操作后其值为0时，才须执行signal(Wmutex)操作，以便让Writer进程写。 因为Readcount是一个可被多个Reader进程访问的临界资源，因此，应该为它设置一个互斥信号量rmutex。,读者-写者问题可描述如下： Var rmutex, wmutex:semaphore =1,1; Readcount:inte
5、ger =0; begin parbegin READER:begin repeat wait(rmutex); if readcount=0 then wait(wmutex); Readcount =Readcount+1; signal(rmutex); perform read operation; ,wait(rmutex); readcount =readcount-1; if readcount=0 then signal(wmutex); signal(rmutex); until false; end WRITER:begin repeat wait(wmutex); per
6、form write operation; signal(wmutex); until false; end parend end,2. 利用信号量集机制解决读者-写者问题,增加限制，最多允许RN个读者读 信号量L，初值RN，用于控制读者数目 在第RN+1个读者要进入读时，会引起阻塞 使用Swait(S, 1, 0)的方法实现开关作用,Var RN integer; L, mx:semaphore =RN,1; begin parbegin READER:begin repeat Swait(L,1,1); Swait(mx,1,0); perform read operation; Ssig
7、nal(L,1); until false; end,WRITER:begin repeat Swait(mx,1,1; L,RN,0); perform write operation; Ssignal(mx,1); until false; end parend end,2.5 管 程 机 制,管程的基本概念,管程由三部分组成： 局部于管程的共享变量说明； 对该数据结构进行操作的一组过程； 对局部于管程的数据设置初始值的语句。此外，还须为管程赋予一个名字。,2.6 进 程 通 信,信号量适合同步控制， 不适宜作为通信工具。 因此需要高级进程通信方式。,2.6.1 高级进程通信的类型,高级通
8、信的定义：P54,2.6.1 进程通信的类型,1. 共享存储器系统(Shared-Memory System),基于共享数据结构的通信方式。 例如生产者-消费者问题中的缓冲池。 该方式增加程序员负担，OS只须提供共享空间，低效，只能传递少量数据。 (2) 基于共享存储区的通信方式。 例如Windows的DDE,DDE技术通信原理 动态数据交换(Dynamic Data Exchange,DDE)是一种进程间通信形式。 两个同时运行的程序间通过DDE方式交换数据时是客户/服务器关系，一旦客户和服务器建立起来连接关系，则当服务器中的数据发生变化后就会马上通知客户。通过DDE方式建立的数据连接通道是
9、双向的，即客户不但能够读取服务器中的数据，而且可以对其进行修改。,2. 消息传递系统(Message passing system) 不论是单机系统、多机系统，还是计算机网络，消息传递机制都是用得最广泛的一种进程间通信的机制。 1、在消息传递系统中，进程间的数据交换，是以格式化的消息(message)为单位（在计算机网络中，又把message称为报文） 2、程序员直接利用系统提供的一组通信命令(原语)进行通信。 操作系统隐藏了通信的实现细节，大大减化了通信程序编制的复杂性，而获得广泛的应用。消息传递系统的通信方式属于高级通信方式。又因其实现方式的不同而进一步分成直接通信方式和间接通信方式两种。
10、,3. 管道(Pipe)通信 所谓“管道”，是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，又名pipe文件。向管道(共享文件)提供输入的发送进程(即写进程)， 以字符流形式将大量的数据送入管道；而接受管道输出的接收进程(即读进程)，则从管道中接收(读)数据。由于发送进程和接收进程是利用管道进行通信的，故又称为管道通信。这种方式首创于UNIX系统，由于它能有效地传送大量数据，因而又被引入到许多其它操作系统中。,为了协调双方的通信，管道机制必须提供以下三方面的协调能力： 互斥，即当一个进程正在对pipe执行读/写操作时，其它(另一)进程必须等待。 同步，指当写(输入)进程把一
11、定数量(如4 KB)的数据写入pipe，便去睡眠等待， 直到读(输出)进程取走数据后，再把他唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入管道后，才将之唤醒。 确定对方是否存在，只有确定了对方已存在时，才能进行通信。,2.6.2 消息传递通信的实现方法,1. 直接通信方式 这是指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。此时，要求发送进程和接收进程都以显式方式提供对方的标识符。,通常，系统提供下述两条通信命令(原语)： Send(Receiver, message); 发送一个消息给接收进程； Receive(Sender, message); 接收Sen
12、der发来的消息； 例如 原语Send(P2, m1)：表示将消息m1发送给接收进程P2; 原语Receive(P1，m1)：表示接收由P1发来的消息m1。,在某些情况下，接收进程可与多个发送进程通信，因此，它不可能事先指定发送进程。例如，用于提供打印服务的进程，它可以接收来自任何一个进程的“打印请求”消息。对于这样的应用，在接收进程接收消息的原语中的源进程参数，是完成通信后的返回值，接收原语可表示为： Receive (id, message);,利用直接通信原语解决生产者-消费者问题。 当生产者生产出一个产品(消息)后，便用Send原语将消息发送给消费者进程；而消费者进程则利用Receiv
13、e原语来得到一个消息。如果消息尚未生产出来，消费者必须等待，直至生产者进程将消息发送过来。生产者-消费者的通信过程可分别描述如下：,repeat produce an item in nextp; send(consumer, nextp); until false; repeat receive(producer, nextc); consume the item in nextc; until false;,2. 间接通信方式,间接通信的原语,(1) 信箱的创建和撤消。 进程可利用信箱创建原语来建立一个新信箱： Create (mailbox) 创建者进程应给出信箱名字、信箱属性(公用、私
14、用或共享)；对于共享信箱， 还应给出共享者的名字。 当进程不再需要读信箱时，可用信箱撤消原语将之撤消。 Delete (mailbox),2. 间接通信方式,(2) 消息的发送和接收。当进程之间要利用信箱进行通信时，必须使用共享信箱，并利用系统提供的下述通信原语进行通信。 Send(mailbox, message); 将一个消息发送到指定信箱； Receive(mailbox, message); 从指定信箱中接收一个消息；,信箱可由操作系统创建，也可由用户进程创建，创建者是信箱的拥有者。据此，可把信箱分为以下三类。 1) 私用信箱 用户进程可为自己建立一个新信箱，并作为该进程的一部分。信箱
15、的拥有者有权从信箱中读取消息，其他用户则只能将自己构成的消息发送到该信箱中。这种私用信箱可采用单向通信链路的信箱来实现。 当拥有该信箱的进程结束时，信箱也随之消失。,2) 公用信箱 它由操作系统创建，并提供给系统中的所有核准进程使用。核准进程既可把消息发送到该信箱中，也可从信箱中读取发送给自己的消息。显然，公用信箱应采用双向通信链路的信箱来实现。通常，公用信箱在系统运行期间始终存在。 3) 共享信箱 它由某进程创建，在创建时或创建后，指明它是可共享的，同时须指出共享进程(用户)的名字。信箱的拥有者和共享者，都有权从信箱中取走发送给自己的消息。,在利用信箱通信时，在发送进程和接收进程之间，存在以
16、下四种关系： (1) 一对一关系。这时可为发送进程和接收进程建立一条两者专用的通信链路，使两者之间的交互不受其他进程的干扰。 (2) 多对一关系。允许提供服务的进程与多个用户进程之间进行交互，也称为客户/服务器交互(client/server interaction)。 (3) 一对多关系。允许一个发送进程与多个接收进程进行交互，使发送进程可用广播方式，向接收者(多个)发送消息。 (4) 多对多关系。允许建立一个公用信箱，让多个进程都能向信箱中投递消息；也可从信箱中取走属于自己的消息。,2.6.3 消息传递系统实现中的若干问题,1. 通信链路(communication link) 为使在发送
17、进程和接收进程之间能进行通信，必须在两者之间建立一条通信链路。有两种方式建立通信链路。第一种方式是：由发送进程在通信之前，用显式的“建立连接”命令(原语)请求系统为之建立一条通信链路；在链路使用完后，也用显式方式拆除链路。 这种方式主要用于计算机网络中。第二种方式是发送进程无须明确提出建立链路的请求，只须利用系统提供的发送命令(原语)，系统会自动地为之建立一条链路。这种方式主要用于单机系统中。,根据通信链路的连接方法，又可把通信链路分为两类： 点点连接通信链路，这时的一条链路只连接两个结点(进程)； 多点连接链路，指用一条链路连接多个(n2)结点(进程)。 根据通信方式的不同，则又可把链路分成
18、两种： 单向通信链路，只允许发送进程向接收进程发送消息； 双向链路，既允许由进程A向进程B发送消息，也允许进程B同时向进程A发送消息。,2. 消息的格式,在某些OS中，消息是采用比较短的定长消息格式，这减少了对消息的处理和存储开销。这种方式可用于办公自动化系统中，为用户提供快速的便笺式通信；但这对要发送较长消息的用户是不方便的。 在有的OS中，采用另一种变长的消息格式，即进程所发送消息的长度是可变的。系统在处理和存储变长消息时，须付出更多的开销，但方便了用户。 这两种消息格式各有其优缺点，故在很多系统(包括计算机网络)中，是同时都用的。,3. 进程同步方式,发送进程阻塞、 接收进程阻塞。 (2
19、) 发送进程不阻塞、 接收进程阻塞。 (3) 发送进程和接收进程均不阻塞。,2.6.4 消息缓冲队列通信机制,1. 消息缓冲队列通信机制中的数据结构 (1) 消息缓冲区。在消息缓冲队列通信方式中，主要利用的数据结构是消息缓冲区。它可描述如下： type message buffer=record sender; 发送者进程标识符 size; 消息长度 text; 消息正文 next; 指向下一个消息缓冲区的指针 end,(2) PCB中有关通信的数据项。在利用消息缓冲队列通信机制时，在设置消息缓冲队列的同时，还应增加用于对消息队列进行操作和实现同步的信号量，并将它们置入进程的PCB中。在PCB
20、中应增加的数据项可描述如下： type processcontrol block=record mq; 消息队列队首指针 mutex; 消息队列互斥信号量 sm; 消息队列资源信号量 end,2. 发送原语 发送进程在利用发送原语发送消息之前，应先在自己的内存空间，设置一发送区a，见图 2 - 12 所示，把待发送的消息正文、发送进程标识符、消息长度等信息填入其中，然后调用发送原语，把消息发送给目标(接收)进程。 1、根据发送区a中所设置的消息长度a.size来申请一缓冲区i， 2、把发送区a中的信息复制到缓冲区i中。 3、获得接收进程的内部标识符j，然后将i挂在j.mq上。该队列属于临界资源
21、， 故执行insert操作的前后，都要执行P、V操作。 ,图 2 - 12 消息缓冲通信,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,3. 接收原语,接收原语描述如下： 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,