管程
管程的基本概念
管程的 汉森方法
管程的 霍尔方法管程:基本概念
管程是由若干公共变量及其说明和所有访问这些变量的过程所组成
管程把分散在各个进程中互斥地访问公共变量的那些临界区集中起来管理,管程的局部变量只能由该管程的过程存取
进程只能互斥地调用管程中的过程管程有以下属性:
共享性:管程中的移出过程可被所有要调用管程的进程所共享 。
安全性:管程的局部变量只能由该管程的过程存取,不允许进程或其它管程来直接存取,
一个管程的过程也不应该存取任何非局部于它的变量 。
互斥性:在任一时刻,共享资源的进程可访问管理该资源的过程,最多只有一个调用者能真正地进入管程,而任何其它调用者必须等待 。 直到访问者退出 。
管程:基本形式
TYPE <管程名 > = MONITOR
<管程变量说明 >;
define <( 能被其他模块引用的 ) 过程名列表 >;
use <( 要引用的模块外定义的 ) 过程名列表 >;
procedure <过程名 >(<形式参数表 >);
begin
<过程体 >;
end;
……
procedure <过程名 >(<形式参数表 >);
begin
<过程体 >;
end;
begin
<管程的局部数据初始化语句 >;
end;
管程:条件变量
条件变量 ( condition variables),
当调用管程过程的进程无法运行时,
用于阻塞进程的信号量
同步原语 wait,当一个管程过程发现无法继续时 ( 如发现没有可用资源时 ),它在某些条件变量上执行 wait,
这个动作引起调用进程阻塞
同步原语 signal
管程:结构
condition c1
wait(c1)

condition cn
wait(cn)
Urgent queue
signal(ci)
局部数据条件变量过程 1
过程 n
出口变量初始化代码入口管程等待调用进程队列管程等待区域管程:示例
TYPE SSU = MONITOR
var busy,boolean;
nobusy,semaphore;
define require,return;
use wait,signal;
procedure require;
begin
if busy then wait(nobusy); /*调用进程加入等待队列 */
busy,= ture;
end;
procedure return;
begin
busy,= false;
signal(nobusy); /*从等待队列中释放进程 */
end;
begin /*管程变量初始化 */
busy,= false;
end;
管程:问题
当使用 signal释放一个等待进程时,可能出现两个进程同时停留在管程内 。 解决方法:
执行 signal的进程等待,直到被释放进程退出管程或等待另一个条件
被释放进程等待,直到执行 signal的进程退出管程或等待另一个条件
霍尔采用了第一种办法
汉森选择了两者的折衷,他规定管程中的过程所执行的 signal操作是过程体的最后一个操作管程的实现:汉森方法
每个管程均使用的一个数据类型,
TYPE interf = RECORD
intsem,semaphore; /* 开放管程的信号量 */
count1,integer; /* 等待调用的进程个数 */
count2,integer; /* 调用了管程中的过程且不
END; 处于等待状态的进程个数 */
管程的实现:汉森方法
调用查看原语 check,如果管程是开放的,
则执行这条原语后关闭管程,相应进程继续执行;如果管程是关闭的,则执行这条原语后相应进程被置成等待调用状态
procedure check(var IM interf);
begin
if IM.count2 = 0
then IM.count2,= IM.count2 + 1;
else
begin
IM.count1,= IM.count1 + 1;
W(IM.intsem);
end;
end;
管程的实现:汉森方法
开放原语 release,如果除了发出这条原语的进程外,不再有调用了管程中过程但又不处于等待状态的进程,那么就释放一个等待者或开放管程
procedure release(var IM interf);
begin
IM.count2,= IM.count2 - 1;
if IM.count2 = 0 and IM.count1 > 0 then
begin
IM.count1,= IM.count1 - 1;
IM.count2,= IM.count2 + 1;
R(IM.intsem);
end;
end;
管程的实现:汉森方法
等待原语 wait,执行这条原语后相应进程被置成等待状态,同时开放管程,允许其它进程调用管程中的过程
procedure wait(var s:semaphore; var IM interf);
begin
s,= s + 1;
IM.count2,= IM.count2 – 1;
if IM.count1 > 0 then
begin
IM.count1,= IM.count1 – 1;
IM.count2,= IM.count2 + 1;
R(IM.intsem);
end;
W(s);
end;
管程的实现:汉森方法
释放原语 signal,执行这条原语后释放指定等待进程队列中的一个进程 。 如指定等待进程队列为空,本操作相当于空操作
procedure signal(var s:semaphore; var IM interf);
begin
if s > 0 then
begin
s,= s – 1;
IM.count2,= IM.count2 + 1;
R(s);
end;
end;
汉森方法实现读者写者问题有两组并发进程:读者与写者,共享一个文件,要求,1) 允许多个读者同时执行读操作; 2) 任一写者在完成写操作之前不允许其他读者和写者工作; 3) 写者欲工作,要等待已存在的读者完成读操作,新的读者与写者均被拒绝汉森方法实现读者写者问题
T Y P E re a d- w ri te r = MO NI T O R
v a r r c,w c,in te g er ;
R,W,s e ma ph o re ;
d e fi n e st a rt - re ad,e n d- re a d,st ar t - wr it er,e n d- w rite r ;
u s e w ai t,si g na l,ch e ck,r el e as e ;
p r o ce du r e s ta rt - re a d;
b e g in
c h ec k (I M) ;
i f w c >0 t h en wa it ( R,I M) ;
r c,= r c + 1 ;
s i gn a l( R,IM ) ;
r e le a se (I M );
end;
p r o ce du r e e nd -r e ad ;
b e g in
c h ec k (I M) ;
r c,= r c - 1 ;
if rc= 0 the n s ig nal (W,IM ) ;
r e le a se (I M );
end;
p r o ce du r e s ta rt - wr i te ;
b e g in
c h ec k (I M) ;
w c,= w c + 1 ;
i f r c >0 o r w c >1
t h en wa it ( W,I M) ;
r e le a se (I M );
end;
p r o ce du r e e nd -w r it e ;
b e g in
c h ec k (I M) ;
w c,= w c - 1 ;
if wc> 0 the n s ig nal (W,IM ) ;
els e s ig nal (R,I M);
r e le a se (I M );
end;
b e g in rc,= 0 ; w c,= 0 ; R,= 0 ; W,= 0 ; e n d ;
汉森方法实现 苹果橘子 问题桌上有一只盘子,每次只能放入一只水果,爸爸专向盘中放苹果,妈妈专向盘中放橘子,一个儿子专吃盘中橘子,一个女儿专吃盘中苹果汉森方法实现苹果橘子问题
T Y P E FM S D = M ON I TO R
v a r p la te,( ap pl e,o ra ng e );
f ul l,b o ol ea n ;
S P,S S,S D,s em a ph or e ;
d e fi n e pu t,g et ;
u s e w ai t,si g na l,ch e ck,r el e as e ;
p r o ce du r e p ut (v a r
f ru i t,( ap pl e,o ra ng e ) );
b e g in
c h ec k (I M) ;
i f f u ll t h en wa it ( SP,IM ) ;
f u ll,= t r ue ;
p l at e,= f ru i t;
i f f r ui t= o ra n ge
t h en si gn a l( S S,IM ) ;
e l se si gn a l( S D,IM ) ;
r e le a se (I M );
end;
p r o ce du r e g et (v a r f ru it,
( a p pl e,o ra n ge ),x,p l at e );
b e g in
c h ec k (I M) ;
i f n o t fu l l o r pl a te < >f ru i t
t h en be gi n
i f fr ui t = or an g e
t h e n wa i t( S S,IM ) ;
e l s e wa i t( S D,IM ) ;
e n d;
x,= pl at e ;
f u ll,= f a ls e ;
s i gn a l( SP,I M );
r e le a se (I M );
end;
b e g in fu ll,= fa ls e ; S P,= 0; SS,= 0 ; S D,= 0 ; en d ;
管程的实现:霍尔方法
用于互斥调用管程过程的信号量:
TYPE interf = RECORD
mutex:semaphore;/*进程调用管程过程前使用的互斥信号量 */
next:semaphore; /*发出 signal的进程挂起自己的信号量 */
next-count:integer; /* 在 next上等待的进程数 */
END;
互斥调用管程过程:
P(IM.mutex);
<过程体 >;
if IM.next-count > 0 then V(IM.next); else V(IM.mutex);
管程的实现:霍尔方法
x - s em,se m ap ho r e; / * 与资源相关的信号量 * /
x - c ou nt,i nt eg e r; / * 在 x- sem 上等待的进程数 * /
wait 与 s i gn al 过程
p r o ce du r e w ai t( v ar x- se m
,s em a ph or e,v a r x- c ou n t
,i nt e ge r,v ar IM,i n te r f) ;
b e g in
x - co u nt,= x - co un t + 1;
i f I M,n ex t -c o un t > 0
t h en V( IM,ne x t) ;
e l se V( IM,mu t ex );
P ( x- s em );
x - co u nt,= x - co un t – 1;
end;
p r o ce du r e s ig na l (v a r x- s e m
,s em a ph or e,v a r x- c ou n t
,i nt e ge r,v ar IM,i n te r f) ;
b e g in
i f x - co un t > 0 th e n b eg in
I M,ne xt - co u nt,=
I M,n e xt -c o un t + 1 ;
V ( x -s em ) ;
P ( I M,n e xt );
I M,ne xt - co u nt,=
I M,n e xt -c o un t - 1 ;
e n d;
end;
霍尔方法实现哲学家问题五个哲学家围坐在一个圆桌旁,桌中央有一盘通心面,每人面前有一只空盘子,每两人之间放一把叉子 。
每个哲学家思考,饥饿,然后吃通心面,为了吃面哲学家必须获得自己左边和右边的两把叉子霍尔方法实现哲学家问题
T Y P E di n in g -p hi l os o ph er s = MO NI T OR
v a r s ta te,a rr ay [ 0.,4] o f ( t hi nk i ng,h un g ry,e a ti ng ) ;
s,a r ra y [0,,4 ] o f se m ap h or e;
s -c ou n t,a rr a y[ 0,,4] of in te g er ;
d e fi n e pi c ku p,pu t do w n;
u s e w ai t,si g na l ;
p r o ce du r e t es t( k,0.,4 ) ;
b e g in
i f s t at e[ ( k- 1 ) mo d 5 ] <> ea t in g a nd st a te [k ] =h u ng r y
a n d s ta t e[ (k + 1) mo d 5 ]< > ea ti n g t he n b eg i n
s t a te [k ],= e at i ng ; s ig n a l( s[ k],s - co un t [k ],IM ) ;
e n d;
end;
p r o ce du r e p ic ku p (i,0.,4 ) ;
b e g in
s t at e [ i ],= h un gr y ;
t e st ( i) ;
i f s t at e[ i ]< > ea ti n g
t h en wa it ( s[ i ],
s - c ou nt [ i ],IM ) ;
end;
p r o ce du r e p ut do w n( i,0,,4 ) ;
b e g in
s t at e [ i ],= t hi nk i ng ;
t e st ( ( i -1 ) m o d 5) ;
t e st ( ( i +1 ) m o d 5) ;
end;
b e g in f o r i,= 0 t o 4 do s t at e [ i ],= t hi nk i ng ; e nd ;