《Chap3.4管程_2013》由会员分享，可在线阅读，更多相关《Chap3.4管程_2013（30页珍藏版）》请在金锄头文库上搜索。
1、3.4 管程,3.4.1 管程和条件变量3.4.2 管程的实现3.4.3 管程解决进程同步问题,1,C. A. R. Hoare,昵称 Tony Hoare, 1980年图灵奖Quicksort算法Hoare LogicCommunicating Sequential Processes/并发进程理论, CSP进程代数http:/ CSP电子书下载在2000年，Hoare由于其在计算机科学和教育方面的杰出贡献被英国皇家授予爵士爵位。 管程C. A. R. Hoare: Monitors: An Operating System Structuring Concept. Commun. ACM,
2、 17 (10): 549-557 (1974),2,3.4.1管程和条件变量,为什么要引入管程把分散在各进程中的临界区集中起来进行管理 ；防止进程有意或无意的违法同步操作， 便于用高级语言来书写程序，也便于程序正确性验证。,3,管程定义和属性,管程的定义 管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块。 管程的属性 共享性： 安全性： 互斥性：,4,管程定义和属性,共享性：管程中的移出过程可被所有要调用管程的过程的进程所共享。安全性： 管程的局部变量只能由该管程的过程访问，不允许进程或其他管程来直接访问，一个管程的过程也不应该访问任何非局部于它的变量。
3、互斥性： 在任一时刻，共享资源的进程可访问管程的管理该资源的过程，但最多只有一个调用者能真正地进入管程，任何其他调用者必须等待直到管程可用。,5,管程的形式,type 管程名=monitor 局部变量说明； 条件变量说明； 初始化语句；define 管程内定义的，管程外可调用的过程或函数名列表；use 管程外定义的，管程内将调用的过程或函数名列表；过程名/函数名(形式参数表) ; 过程名/函数名(形式参数表) ; ,6,管程的结构,7,管程的条件变量,条件变量-是出现在管程内的一种数据结构，且只有在管程中才能被访问，它对管程内的所有过程是全局的，只能通过两个原语操作来控制它。wait( )-阻
4、塞调用进程并释放管程，直到另一个进程在该条件变量上执行signal( )。signal( )-如果存在其他进程由于对条件变量执行wait( )而被阻塞，便释放之；如果没有进程在等待，那么，信号不被保存。条件变量与P、V操作中信号量的区别?,8,管程问题讨论,使用signal释放等待进程时，可能出现两个进程同时停留在管程内。解决方法：执行signal的进程等待，直到被释放进程退出管程或等待另一个条件被释放进程等待，直到执行signal的进程退出管程或等待另一个条件霍尔(Hoare, 1974)采用第一种办法，汉森(Hansen)选择两者的折衷，规定管程中的过程所执行的signal操作是过程体的最
5、后一个操作。,9,比较: 管程与进程,管程定义的是公用数据结构，而进程定义的是私有数据结构；管程把共享变量上的同步操作集中起来，而临界区却分散在每个进程中；管程是为管理共享资源而建立的，进程主要是为占有系统资源和实现系统并发性而引入的；管程是被欲使用共享资源的进程所调用的，管程和调用它的进程不能并行工作，而进程之间能并行工作，并发性是其固有特性；管程是语言或操作系统的成分，不必创建或撤销，而进程有生命周期，由创建而产生至撤销便消亡。,10,3.4.2管程的实现: Hoare方法,霍尔方法使用P和V操作原语来实现对管程中过程的互斥调用，及实现对共享资源互斥使用的管理。不要求signal操作是过程
6、体的最后一个操作，且wait和signal操作可被设计成可以中断的过程。,11,Hoare管程数据结构(1),1. mutex对每个管程，使用用于管程中过程互斥调用的信号量mutex(初值为1)。进程调用管程中的任何过程时，应执行P(mutex)；进程退出管程时应执行V(mutex)开放管程，以便让其他调用者进入。为了使进程在等待资源期间，其他进程能进入管程，故在wait操作中也必须执行V(mutex)，否则会妨碍其他进程进入管程，导致无法释放资源。,12,Hoare管程数据结构(2),2. next和next-count对每个管程，引入信号量next(初值为0)，凡发出signal操作的进程
7、应该用P(next)阻塞自己，直到被释放进程退出管程或产生其他等待条件。进程在退出管程的过程前，须检查是否有别的进程在信号量next上等待，若有，则用V(next)唤醒它。next-count(初值为0)，用来记录在next上等待的进程个数。,13,Hoare管程数据结构(3),3.x-sem和 x-count引入信号量x-sem(初值为0)，申请资源得不到满足时，执行P(x-sem)阻塞。由于释放资源时，需要知道是否有别的进程在等待资源，用计数器x-count(初值为0)记录等待资源的进程数。执行signal操作时，应让等待资源的诸进程中的某个进程立即恢复运行，而不让其他进程抢先进入管程，这
8、可以用V(x-sem)来实现。,14,Hoare管程数据结构(4),每个管程定义如下数据结构 ：typedef struct InterfaceModule /InterfaceModule是结构体的名字semaphore mutex; /进程调用管程过程前使用的互斥信号量semaphore next; /发出signal的进程阻塞自己的信号量int next_count; /在next上等待的进程数;mutex=1; next=0; next_count=0; /初始化语句,15,Hoare管程的enter( )和leave( )操作,void enter(InterfaceModule /
9、判有否发出过signal的进程?,void leave(InterfaceModule /否则开放管程 ,16,Hoare管程的wait( )操作,void wait(semaphore /等资源进程个数减1 ,17,Hoare管程的signal( )操作,void signal(semaphore /发出signal进程个数减1 ,18,19,3.4.3 使用管程解决进程同步问题,1霍尔管程解决五个哲学家吃通心面问题(1)type dining_philosophers=monitor enum thinking,hungry,eating state5; semaphore self5;
10、int self_count5; InterfaceModule IM; for (int i=0;i5;i+)/初始化，i为进程号 statei=thinking; define pickup,putdown; use enter,leave,wait,signal；,20,霍尔管程解决五个哲学家吃通心面问题(2),void pickup(int i) /i=0,1,.,4 enter(IM);statei=hungry;test(i);if(statei!=eating) wait(selfi,self_counti,IM); leave(IM);void putdown(int i) /
11、i=0,1,2,.,4 enter(IM); statei=thinking; test(i-1)%5); test(i+1)%5); leave(IM);,21,void test(int k) /k=0,1,.,4if(state(k-1)%5!=eating) ,霍尔管程解决五个哲学家吃通心面问题(2),22,2管程解决生产者-消费者问题(1),type producer_consumer=monitoritem Bk; /缓冲区个数int in,out; /存取指针int count; /缓冲中产品数semaphore notfull,notempty; /条件变量int notful
12、l_count,notempty_count;InterfaceModule IM;define append,take;use enter,leave,wait,signal；,23,管程解决生产者-消费者问题(2),void append(item x) enter(IM);if(count=k) /缓冲已满 wait(notfull,notfull_count,IM);Bin=x;in=(in+1)%k;count+; /增加一个产品signal(notempty,notempty_count,IM); /唤醒等待消费者 leave(IM);,24,管程解决生产者-消费者问题(3),void take(item ,25,读者写者问题(管程方法),26,27,苹果桔子问题(管程方法),桌上有一只盘子，每次只能放入一只水果。爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔子(orange)，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果。写出能使爸爸、妈妈、儿子和女儿正确同步工作的管程。,28,29,自底向上构筑操作系统中“并发问题”解决方案的知识框架,30,
