[操作系统]管程.ppt

《[操作系统]管程.ppt》由会员分享，可在线阅读，更多相关《[操作系统]管程.ppt（29页珍藏版）》请在优知文库上搜索。

1、管程(monitor)参看参看P51P51OS设计中引入了信号量以后，互斥实现起来似乎很容易，果真是这样吗？答案是否定的！在生产者消费者问题中，曾提到：wait(mutex)、wait(empty)两个语句不能对调，否则系统死锁。说明系统的编制人员使用信号量时要特别小心。很小的错误将产生极大的麻烦。因为出现的错误与资源竞争、死锁、不可预测、不可再现有关。1、问题提出 用信号量机制编制并发程序，对共享变量、信号量的操作（同步、互斥）被分散在各个进程中。缺点：易读性差易读性差：因为要了解对一组变量及信号量的操作，需要读懂全部并发的程序。难以修改和维护难以修改和维护：对一组变量和代码的修改，必须对使

2、用它的全部程序进行修改（因为同步、互斥分散在所有相关并发程序中。正确性难以保证正确性难以保证：OS通常很复杂，同步、互斥过于分散，很难保证逻辑上的正确性。 既然分散的同步操作有缺点，人们就想到把同步机制集中到一个模块中，这就是早期（1971）的秘书进程秘书进程思想。Dijkstra(1971)：提出“秘书”进程的思想。Hansen和Hoare(1973)：推广为“管程”。管程基本思想： 把把信号量信号量及其操作原语操作原语封装在一个对象内部一个对象内部。（将共享变量以及对共享变量能够进行的所有操作集中在一个模块中）。 每次只允许一个进程访问管程内的资源。进程1请求使用共享资源进程2请求使用共享

3、资源进程n请求使用共享资源资源资源互斥R/W秘秘书书进进程程结论：结论： 用信号量实现的互斥机制，其正确性依赖于用户进程（程序员编写的程序）：如果用户进程在进入临界区之前没有用 Wait（mutex）申请，或退出临界区时没有用 Signal（mutex）释放临界区，互斥就不能正确的实现。 OS的工作者设计了一种靠语言编译器实现互斥正确性的机制-管程机制。管程是编程的构件。 管程机制确保一次只有一个进程在管程内活动，程序员不需要显式地用信号量机制编写实现互斥的代码。2. 管程的引入 管程：一种同步机制，是编程的构件。 管程定义:X状态：busy 忙、free 闲一组操作: request(X)申

4、请、release(X) 释放 。 封装在一个管程中封装在一个管程中管程外某进程申请/释放资源时，调用request(X)或release(X) 即可，同步与互斥由管程完成。 管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。使互斥操作相对集中，从而增加了模块的相对独立性。 数据结构是资源的抽象描述例如：对于某临界资源用共享变量X表示例如：对于进程阻塞队列（临界资源）用变量bq表示数据结构: 队首指针、队尾指针、队列长度一组操作: insertF(bq）、 insertL(bq）、 remove（bq）、 insert (bq）等执行的进程等待事件时 Block(bq)调

5、用insert（bq）进入 阻塞 队 列阻塞队列是一个临界资源，为各进程所共享，阻塞进队、唤醒出队要互斥进行。在使用管程后，进队由block（bq）调用管程中的insert（bq）过程，就可进入阻塞队列， block（bq）设计者无须再考虑互斥、同步问题。封装在管程中3、管程的结构和特性 抽象数据类型：管程中不仅有数据，而且有对数据进行操作的代码。 模块化：一个管程是一个基本程序单位，可以单独编译； 信息封装：管程是半透明的，管程中的内部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的。Type 管程名=monitor变量说明： Procedure entry p1(

6、参数）begin en Procedure entry pn(参数）begin endbegin 变量初始化 end管程有四部分组成 名称：为每个共享资源设立一个管程 数据结构说明：一组局部管程的控制变量 操作原语： 对控制变量和临界资源进行操作 的一组原语，是访问该管程的唯一途径。这些原语本身是互斥的，任一时刻只允许一个进程去调用，其余需要访问的进程就等待。 初始化代码：对控制变量进行初始化的代码教材中称之过程教材中称之过程1）局部数据（共享变量）在管程外不可见，只能通过管程内部的过程访问。2）管程要互斥进入，其中只能有一个活动的进程。当活动的进程 退出管程，或阻塞阻塞才允许下一个进程进入管

7、程。当一个进程试图进入一个被占用的管程时，在入口出等待。过程n 过程1初始化程序条件变量局部数据管理部分c1.wait条件条件c1队列队列c1.signalcn.wait条件条件cn队列队列紧急队列紧急队列进入队列入口等待队入口等待队列列队列部分退出过程n 过程1初始化程序条件变量局部数据管理部分c1.wait条件条件c1队列队列c1.signalcn.wait条件条件cn队列队列紧急队列紧急队列进入队列入口等待入口等待队列队列队列部分3）管程是管理资源的（资源用共享数据抽象表示），因此，管程内部有进程等待（阻塞）队列，以及等待与唤醒操作，这种队列称之：条件队列。4）管程是一个编程单位，相应的

8、编译器能识别，入口处互斥进入代码和出口退出代码由编译器自动产生。4、条件变量引入过程n 过程1初始化程序条件变量局部数据管理部分c1.wait条件条件c1队列队列c1.signalcn.wait条件条件cn队列队列紧急队列紧急队列进入队列入口等入口等待队列待队列队列部分 当进入管程的进程因资源被占用等原因不能继续运行时,使其等待。（让出让出CPU称之释放管程互斥权）。 为此在管程内部可以说明和使用一种特殊类型的变量：条件变量。 每个条件变量表示一种等待原因，并不取具体数值。每个原因对应一个等待队列。例如，X代表某临界资源，变量busy表示X的状态：忙、或闲。定义一个条件变量nonbusy（等待

9、条件不忙） 。当进入管程的进程R/W该资源时，发现资源X的状态为忙（busy为“忙”），则该进程：进入等待该资源的阻塞队列或称之进入X的等待条件不忙队列或称之进入nonbusy条件队列。并释放管程的互斥权。 当进入管程的另一进程释放与某条件变量相关的资源时，应该唤醒在该条件上等待的一个进程。5、多个进程出现在管程中当一个进入管程的进程执行唤醒操作时（如唤醒），管程中便存在两个同时处于活动状态的进程。1） 处理方法有三种： 当唤醒时 等待继续，直到退出或等待；（Hoare方法）； 等待继续，直到等待或退出；（Hansan方法 )；被唤醒而等待的进程进入紧急等待队列。 规定唤醒操作为管程各过程中最

10、后一个可执行的语句。概念上更简单的方法（缺点，过程中只能有一个 唤醒操作）2）多个进程出现在管程中如果进程唤醒进程，则等待继续；如果进程在执行又唤醒进程，则等待续；这时，在管程内部，由于执行唤醒操作，可能会出现多个等待进程，这些等待的进程进入紧急等待队列。紧急等待队列优先级高于入口等待队列的优先级。过程n 过程1初始化程序条件变量局部数据管理部分C1.wait条件条件c1队列队列C1.signalCn.wait条件条件cn队列队列紧急队列紧急队列进入队列入口等待入口等待队列队列队列部分6、条件变量上的wait、signal操作 条件变量的定义：Var 变量1, 变量2, ，变量n : cond

11、ition 对条件变量可执行wait和signal操作。对于条件变量y ： y. wait将自己阻塞在y条件队列中； y . Signal可以将y队列中的一个进程唤醒。条件变量表示一种等待原因，并不取具体数值（即不是计数器、也不是信号量）。每个原因（条件变量）对应一个等待队列。例，某资源多进程共享，每次只能一个进程访问。资源状态：用变量busy表示, 取值T、F定义一个条件变量：nonbusy一个进程申请使用资源： If busy then nonbusy.wait另一个进程释放该资源： nonbusy.signal唤醒一个等不忙条件的进程。进入等待不忙条件队列等待不忙条件队列（进入nonbu

12、synonbusy条件队列条件队列）* 对条件变量操作进一步说明设：条件变量为C1C1.wait :紧急队列非空, 则唤醒第一个等待进程执行此操作的进程投入C1链尾紧急队列空,则释放互斥权, 开放管程入口执行此操作的进程投入紧急等待队列的尾部C1.signal:如果C1队列为空，则相当于空操作执行此操作的进程继续不空唤醒C1队列第一个等待者Hoare方法方法带有紧急队列管程内部示意图过程n 过程1初始化程序条件变量局部数据(管理区)c1.wait条件条件c1队列队列c1.signalcn.wait条件条件cn队列队列紧急队列紧急队列进入队列入口等待入口等待队列队列(队列区)按简单方法处理时管程

13、内部示意图为:过程n 过程1初始化程序条件变量局部数据管理部分C1.wait条件条件c1队列队列C1.signalCn.wait条件条件cn队列队列进入队列入口等待入口等待队列队列队列部分 7、利用管程解决“生产者/消费者”问题 定义管程名：PC 共享的数据结构： 环形缓冲buffer ，大小为n 条件变量 notfull、notempty 环形缓冲区中产品计数：count 设两个过程：put（item）、get（item） Producer调用PC. put(item) 生产的产品送缓冲区 consumer调用PC. get(item) 从缓冲区取一个产品 进入管程的Producer如果发现

14、缓冲区满：countn 执行notfull.wait把自己阻塞入等待不满条件队列。 进入管程的consumer如果发现缓冲区空：count0执行notempty.wait把自己阻塞入等待不空条件队列。过程2:get(item)过程1:put(item)初始化程序in=out=coun=0条件变量：notfull,notempty局部数据：bufferin, out, countnotfull.wait条件队列条件队列notfull.signalnotempty.wait条件队列条件队列入口入口等待等待队列队列notempty.signaltype pc= moniter Var in，out

15、, count ：integer；buffer：array 0,n-1 of item； （有界缓冲区）notempty，notfull：Condition；（不空、不满两个条件）procedure entry put(item) begin if Countn then notfull .Wait；(满，进入等待不满条件队列） bufferin：=nextp； in : = in+1 mod n； Count : =Count+1; if notempty.queue then notempty .Signal；end唤醒不空条件队列一个进程相当Count：=1procedure entry

16、 get(item) begin if Count0 then notempty.Wait；（缓冲区空，等待 不空条件） nextc：=bufferout； out：=out+1 mod n； Count：=Count-1； if notfull.queue then notfull.Signal; endbegin in：=out：=Count：=0 ； （初始化）end相当Count:=n-1Producer : begin repeat produce an item in nextp; pc.put(item); until false; endConsumer : begin repeat pc.get(item);consume the item in nextc; until false; end 管程优点：避免了用户程序在互斥实现上可能发生的错误。 管程缺点：1）大多数语言不支持管程。2）管程与信号量机制一样不适用于没有共享内存的多CPU系统和分布式系统。因此需要引入更高级的同步机制-消息传递机制。思考题：编译器如何实现管程入口、出口代码？假设：1) 对管程的互斥信号量