[操作系统]管程.ppt

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

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

2、同步、互斥分散在所有相关并发程序中。正确性难以保证：OS通常很复杂，同步、互斥过于分散，很难保证逻辑上的正确性。既然分散的同步操作有缺点，人们就想到把同步机制集中到一个模块中，这就是早期（1971）的秘书进程思想。,Dijkstra(1971)：提出“秘书”进程的思想。Hansen和Hoare(1973)：推广为“管程”。,管程基本思想：把信号量及其操作原语封装在一个对象内部。（将共享变量以及对共享变量能够进行的所有操作集中在一个模块中）。每次只允许一个进程访问管程内的资源。,结论：用信号量实现的互斥机制，其正确性依赖于用户进程（程序员编写的程序）：如果用户进程在进入临界区之前没有用 Wait

3、（mutex）申请，或退出临界区时没有用 Signal（mutex）释放临界区，互斥就不能正确的实现。OS的工作者设计了一种靠语言编译器实现互斥正确性的机制-管程机制。管程是编程的构件。管程机制确保一次只有一个进程在管程内活动，程序员不需要显式地用信号量机制编写实现互斥的代码。,2.管程的引入,管程：一种同步机制，是编程的构件。管程定义:,X状态：busy 忙、free 闲一组操作:request(X)申请、release(X)释放。,封装在一个管程中,管程外某进程申请/释放资源时，调用request(X)或release(X)即可，同步与互斥由管程完成。,管程是关于共享资源的数据结构及一组针

4、对该资源的操作过程所构成的软件模块。使互斥操作相对集中，从而增加了模块的相对独立性。,数据结构是资源的抽象描述例如：对于某临界资源用共享变量X表示,例如：对于进程阻塞队列（临界资源）用变量bq表示,数据结构:队首指针、队尾指针、队列长度一组操作:insertF(bq）、insertL(bq）、remove（bq）、insert(bq）等,执行的进程等待事件时,Block(bq),调用insert（bq）进入 阻塞 队 列,阻塞队列是一个临界资源，为各进程所共享，阻塞进队、唤醒出队要互斥进行。在使用管程后，进队由block（bq）调用管程中的insert（bq）过程，就可进入阻塞队列，block

5、（bq）设计者无须再考虑互斥、同步问题。,封装在管程中,3、管程的结构和特性,抽象数据类型：管程中不仅有数据，而且有对数据进行操作的代码。,模块化：一个管程是一个基本程序单位，可以单独编译；,信息封装：管程是半透明的，管程中的内部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的。,管程有四部分组成,名称：为每个共享资源设立一个管程 数据结构说明：一组局部管程的控制变量 操作原语：对控制变量和临界资源进行操作 的一组原语，是访问该管程的唯一途径。这些原语本身是互斥的，任一时刻只允许一个进程去调用，其余需要访问的进程就等待。初始化代码：对控制变量进行初始化的代码,教材中称

6、之过程,1）局部数据（共享变量）在管程外不可见，只能通过管程内部的过程访问。,2）管程要互斥进入，其中只能有一个活动的进程。当活动的进程 退出管程，或阻塞才允许下一个进程进入管程。,当一个进程试图进入一个被占用的管程时，在入口出等待。,3）管程是管理资源的（资源用共享数据抽象表示），因此，管程内部有进程等待（阻塞）队列，以及等待与唤醒操作，这种队列称之：条件队列。,4）管程是一个编程单位，相应的编译器能识别，入口处互斥进入代码和出口退出代码由编译器自动产生。,4、条件变量引入,当进入管程的进程因资源被占用等原因不能继续运行时,使其等待。（让出CPU称之释放管程互斥权）。为此在管程内部可以说明和

7、使用一种特殊类型的变量：条件变量。每个条件变量表示一种等待原因，并不取具体数值。每个原因对应一个等待队列。,例如，X代表某临界资源，变量busy表示X的状态：忙、或闲。定义一个条件变量nonbusy（等待条件不忙）。当进入管程的进程R/W该资源时，发现资源X的状态为忙（busy为“忙”），则该进程：进入等待该资源的阻塞队列或称之进入X的等待条件不忙队列或称之进入nonbusy条件队列。并释放管程的互斥权。当进入管程的另一进程释放与某条件变量相关的资源时，应该唤醒在该条件上等待的一个进程。,5、多个进程出现在管程中,当一个进入管程的进程执行唤醒操作时（如唤醒），管程中便存在两个同时处于活动状态的

8、进程。1）处理方法有三种：当唤醒时 等待继续，直到退出或等待；（Hoare方法）；等待继续，直到等待或退出；（Hansan方法)；,被唤醒而等待的进程进入紧急等待队列。,规定唤醒操作为管程各过程中最后一个可执行的语句。概念上更简单的方法（缺点，过程中只能有一个 唤醒操作）,2）多个进程出现在管程中,如果进程唤醒进程，则等待继续；如果进程在执行又唤醒进程，则等待续；这时，在管程内部，由于执行唤醒操作，可能会出现多个等待进程，这些等待的进程进入紧急等待队列。紧急等待队列优先级高于入口等待队列的优先级。,6、条件变量上的wait、signal操作,条件变量的定义：Var 变量1,变量2,，变量n:c

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

10、条件变量操作进一步说明,设：条件变量为C1,C1.wait:,紧急队列非空,则唤醒第一个等待进程,执行此操作的进程投入C1链尾,紧急队列空,则释放互斥权,开放管程入口,执行此操作的进程投入紧急等待队列的尾部,C1.signal:,如果C1队列为空，则相当于空操作,执行此操作的进程继续,不空唤醒C1队列第一个等待者,Hoare方法,带有紧急队列管程内部示意图,按简单方法处理时管程内部示意图为:,7、利用管程解决“生产者/消费者”问题,定义管程名：PC共享的数据结构：环形缓冲buffer，大小为n 条件变量 notfull、notempty 环形缓冲区中产品计数：count设两个过程：put（it

11、em）、get（item）Producer调用PC.put(item)生产的产品送缓冲区 consumer调用PC.get(item)从缓冲区取一个产品进入管程的Producer如果发现缓冲区满：countn 执行notfull.wait把自己阻塞入等待不满条件队列。进入管程的consumer如果发现缓冲区空：count0执行notempty.wait把自己阻塞入等待不空条件队列。,type pc=moniter Var in，out,count：integer；buffer：array 0,n-1 of item；（有界缓冲区）notempty，notfull：Condition；（不空、不

12、满两个条件）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：=1,procedure entry get(item)begin if Count0 then notempty.Wait；（缓冲区空，等待 不空条件）nextc：=bufferout；out：=out+1 mod n；

13、Count：=Count-1；if notfull.queue then notfull.Signal;endbegin in：=out：=Count：=0；（初始化）end,相当Count:=n-1,Producer: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）管

14、程与信号量机制一样不适用于没有共享内存的多CPU系统和分布式系统。因此需要引入更高级的同步机制-消息传递机制。,思考题：编译器如何实现管程入口、出口代码？,假设：对管程的互斥信号量：Mutex，初值为1；管程内紧急队列信号量：urgent，初值为0;紧急队列中进程计数 urgent _count；退出代码：如果紧急队列空开放管程入口，否则唤醒紧急队列中的一个进程。,调用管程内某子过程,外部 过程调用,If(urgent _count 0)then beginurgent _count减1;Signal(urgent);endElse Signal(Mutex);end,出口代码,思考题：如何用

15、信号量实现条件变量？设:条件变量为C、条件队列的信号量Csem（初值0）、条件队列计数C_count（初值0）。,C.Wait操作：C_count加1；（条件队列计数增1）If(urgent _count 0)then begin（如果紧急队列不空）urgent _count 减1；Signal(urgent);（唤醒紧急队列中一个进程）end Else Signal(Mutex);（开放管程入口）Wait(Csem);（自身阻塞）end,C.Signal操作:If(C_count 0)（如果条件队列不空）then beginC_count 减1；（条件队列记数减1）urgent _count加1;（紧急队列增1）Signal(Csem);（唤醒条件队列一个进程）Wait(urgent);（两个活动进程之一阻塞到紧急队列）end,