Sistemas Operacionais e Programação Concorrente - Capítulo 8

Prévia do material em texto

Scanned by CamScanner
)
. 
e
C a p f t u l o 8
FA IN?R I
0 M E C A N I SM O
D A S R E G I L E S C R Í T I C A S 
M a r t fn F i e r r o E t m o r e n o
M o r e n o v u e l v o a d e c i r t e N o t e t r a b e s l e n gu a m f \
y a c o n o z c o t u m e d id a n o t e v a ya s a tu r b m
h a s a p r o v e c h a o Ia v id a n a di e a c i e r t a a n t e s de e r r a r
y 1n e a l e g r o d e e s t e e n c u e n t r o y a u n qu e l a fa m a s e j u e gA
y a v e o qu e t e n e s a de n t r o e l qu e p o r gu s t o n a v e ga
c a p i t a l pa e s t a pa r t ida N o de be t e m e r le a l m a r
Y a u r a t e v o y a d e c i r , V o y a h a c e r l e m i s p r egu n t a s
po r qu e e n m i d e b e r e s t á y a qu e a t an t o m e c o n v i
y h a c e ho n o r a l a v e r dá y v e n c e r á e n 1a pa r t i da
qu ie n a l a v e r dá s e du e b l a , s i u n a e s p l i c a c i ón m e da
qu e s o s po r j u e r a t i n i e b la s s o b r e e l t ie m po y l a me d i
y po r de n t r o c l a r i dá El pe s o y 1a cant i ci &
No ha de de c ir s e j a m ás Su ya s e r á \a v i t o r ia
qu e a bu s é de tu p a c e n c i a : s i e s qu e sabc c o n t es 1m
y e n j u s t a c o m s po n de n c ia , se lo de b o de c la r a r
s i a lgo qu e r s pr egu n t a r , c o n c l a r i dá n o se a s o m b r e
po dés a l pu n t o e n pe z a r , pu e s ha s t a a u r a n in ¢ün hc Bn b t e
pu e s ya t e n s m i l i c e n c ia M e 1o ha sa b ido c s pl ic a r
N a " e s c a l a e v o l u t i v a ' do s m e c a n i s m o s de s in c r o n iz a çko , a s r e g iöe s c r l t lc a s o c u pa m 
u m a po s i q o
i n t e r m ed i ár i a
, 
1 i tu a n d o i e e n t r e a s v a r láv e i a s e m ii fo r a s v is ta s n o c a pi t u lo a n te r i o r e o s m o n
i to r e s
,
qu e s e r i1o e s t u d ado s n o p r ó x im o c a p ft u lo V a le le m b r a r q
u o a de n o m i n a çäo ' Cgi äo c D t ic a "
t a m b ém u s a da pa r a s ign i f i c a r a pa r t e do c ód igo o n de u m p r o c e s s o 
m a n i pu l a da do s
c o m p a r t i lha d o s (t r e c ho c r f t i c o o u s e çao c r f t ic a ) " : . * 11 . ' x ; / ï i
Scanned by CamScanner
102 s i s t e m a s o pe r a c i o n a i s e p r o l - C o n c o r r e n
t e S S T o s c a n i , R S de O l i v e i r a e A s c q » im i
E i n bo r a o m c a n i s m o d a s r e g iö e s c r f t ic a s te n ha s ido u m a v a n ço e m r e la çäo aoa
s c m áf o r o s 4 7
, 
e le n ào a lc a n ço u o s u c e s s o do s s e m áfo r o s , n a p r
á t i c a Em p a r t e , i s t o fo i de v ido 4o
s u r g i m e n t o d o s m o n i t o r e s . Io go e m s e g u id a
8
. 
1 R e g i õ e s c r í t i c a s c o n d i c i o n a i s
U m a r e g i ão c r f t i c a c o n d i c i o n a l p o s s u i a s e gu i n t e s i n t a x e
r e g io n < v a f > w he n < c o n d»
< s e q ü ên c i a d e c o m a n d o s >
e n d r e g i o n
o n de < v a r > é u m a v a r i áv e l (p o de s e r u m a v a r iáv e l e s t r u t u r a d a ) d e c l a r a d a p r e v i a m e n t e c o m o
c o m p a r t i l h a d a (s l 1a r e d )
< c o n d> é u m a e x p r e s s ão b o o l e a n a q u e e s p e c i ' c a a c o n d i ç ão d e e n t r a da n a r e gião
c r i t i c a
< s e q ü ên c i de c o m a n d o s > é o c ód i g o c r i t i c o q u e s e r á e x e c u t a d o t e n do a c e sso
e x c l u s i v o à v a r i áv e l < v a r >
A s e m ân t i c a é c o m o s e g u e U m p r o c e s s o s ó e n t r a n a r e g i ão < v a r > q u a n do < c o n d» é
v e r d a d e i r a e (a o m e s m o (e m p o ) n ão e x i s te o u t r o p r o c e s s o e x e c u t a n d o n e s s a r e g i ão
Po r o u t r o l a d o
, 
u m a v a r i áv e l de c l a r a da c o m o c o m p a r t i l h a d a s ó p o d e s e r a c e s s a da de n tr o
de u m a r e g i ão c r i t i c a p r e f i x a d a pe lo n o m e de s s a v a Dáv e l A d e c l a r a ç ão de c o m p a r t i l ha m e n to é
u m a d e c l a r a çäo n o r m a l , p r e f 1x a d a p e l a p a l a v r a s ha r e d E x e m p lo s s ão a p r e s e n t a do s a s e gu i r
c o u n t e r s ha r e d i n te ge r i n i t i a l 0
l i v r e : s ha r e d bo o l e a n
R s ha r e d a r r a y [20J o f i n te ge r
b u ûir r s ha r e d r e c o rd
p l a c e : a r r a y t l o ] o f i n t e ge r
c o u n t
, 
in
, 
o u 1 : i n te ge r
e n d r e c o r d
C o m r e g iö e s c r f t i c a s , f ic a m v i s ív e i s o s t r e c ho s do s pr o c e s s o s o n de a s v a r i á" i s X s ão u s ad a s e
, 
n a t u r a l m e n te
, 
o s p r o g r a m a s f i c a m m i 1i s be m e s t r u t u r a do s A I
n l o c o n u i b u i r e m n a e 1 l r u tu r a ç1o do a p r o w a m a i e o r i ¢ in a r e m p r o 吕 r a m a a po u c o c o n fl av e i 1 , O
* a : '
c o ¢1s ide t a d o s u m m e c a n i s m o de ba i x o n f v e l
Scanned by CamScanner
C a p ft u lo 8 0 M e c a n i s m o d a s R e g iö c s C r f t i c a s 10 3
c o m p i l a d o r i n d i c a c o m o e r r o a te n t a t i v a d e u s a r u m a v a r i áv e l s ha r e d f o r a d a r e g i ão c r f t ic a
c o n e [ a C o m o o p r o s r a m a d o r é fo rç a do a e x p l ic i t a r a s v a r i áv e i s c o m p a r t i l ha d a s e o s t r e c ho s
o n d e o s p r o c e s s o s a s m a n i pu l a m , i s t o f a z c o m q u e o s p r o g r a m a s f i q u e m m a i a c l a r o s e m a i s
c o n f i áv e i s (e m c o m p a r a ç ão c o m o s p r o g r a m a s q u e u t i l i z a m s e m áf o r o s )
0 m o t i v o pe l o q u a l a s r e g iMe s c r f t i c a s n ão a l c a n ça r a m o s u c e s s o p r át i c o e s p e r a d o f o i a
i n e f i c iên c i a i n e r e n t e às m e s m a s A i m p l e m e n t a ção de s s e m e c a n i s m o i m p l i c a i n e f i c iên c i a N a
i r r q»l e m e n t a ç ão , é n e c e s s ár i o r e a v a l i a r a s c o n d içMe s d e e n t r a d a d o s p r o c e s s o s q u a n d o u m
p r o c e s s o s a i d e u m a r e g i ão c r í t i c a E s t a s r e pe t id a s a v a l i a çMe s de e x p r e s s õ e s bo o le a n a s c a d a v e z
q u e u m p r o c e s s o d e i x a u m a r e g i ão c r i t i c a é u m a f o n te d e i n e f i c i ên c i a p a r a e s t e m e c a n i s m o d e
s i n c r o n i z a ç ão
8
. 
2 E x e m p l o s d e p r o g r a m a s
E s t a s e ç ão a p r e s e n t a d o i s e x e r n p l o s d e u s o d o m e c a n i s m o d a s r e g i õ e s c r í t i c a s
4 a
8 2 1 S i m u l a çã o d e u m s e m á f o r o
O e x e m p l o a s e g u i r m o s t r a c o m o r e g iõ e s c r í t i c a s c o n d i c i o n a i s p o d e m s e r u s a d a s p a r a s i m u l a r a s
o p e r a çõ e s P e V s o b r e u m s e m á f o r o S d e v a l o r i n i c i a l 2
V a r i j i v e 1 g l o b a l S s h a r e d i n t e g e r i n i t i a l 2
P (S ) : V (S)
r e g i o n S w h e n S> O r e g
i o n S
S = S l S = S+ l
e n d r e g i o n e n
d r e g io n
8 2 2 p r o d u t o r e s c o n s u m i d o r e s c o m buf er l i m i t a d o
O e x e m p l o a s e g u i r m o s t r a u m c o n j u n t o de p r o c e s s o s p r o d u t o r e s c o n s u m i d o r ¬ s c o m pa r t i l hBu rd o
u m b u jde r de 10 po s içõ e s O b u oe r é u m a e s t r u t u r a 
fo r m a d a po r u m v e t o r de i n t e i ,
d e n o m i n a do p l a c e , e 3 v a r i á v e i si n t e i r a s , p
a r a c o n t r o l e O s p r o d u t o r es 吕 e r a m m e n s a ge n s
(n ú m e r o s i n t e i r o s ) e a s c o l o c a m n o v e t o r p l a c e : o s c o n s u m id o r e s r e t i r a m a s m ie n s a gc n s do v e t o r
e a s c o n s o m e m
C o n v m o b s e r v a r q u e s e 0 s i s t e m a >o s s e l o r 1n a J u po r u
m ún i c o p a r p r o du t
c o n s u m i d o r
, 
e n t äo n ao s e r i a n e c e s s á r i a a e x c l u s o m ú t u a n a m a n i p u la ç i \ o 
d a s v a r i áv e is i n e o u l
,
4 8 Es te s e x e m p l o s n #o a äo v á1id o《 【1a 1in s u a 吕 e m 
v 4 po i s V 4 n ao i 1n p le m e n t a o 1n e c a n i sm o da s r e 吕 iðe s c r f t ic a s
Scanned by CamScanner
10 4
-
e - -
e s s T - m d e o 1 i w i n n i
po i l ü l 1 e r i a u s a d a e x c l u s i v - p { r u m p r o d u t o r e o 1
d s e r i i U e x c lm
- te po r um
- do r C o n t u do c o n t i n u a r i a - - a a e x c l u s ão m ï t u a s a b l e 1 w i * w l o o u u
V « Uiv e B g1u b a 1 bM e r s ha r e
p la c e : a m y t 1o ] o f i n t e ge r
c o u n 1 : in te ge r i n i t i a l 0
in
, 
o u f : i n t e g e r i n i t i a l 1
c n d r e c o r d
P r o c e s s o p r o d u t o r Pr o c e s s o c o n s u n 1i d o r
i n sg : i n te ge r n u g : i n t e ge r
lo o p lo o p
/ * p r o d u z m e n s a g e m m s g * / r e g i o n b u ßr r w he n c o tBn t> O
r e g i o n bußr w he n c o u n l < I O m 5 g : - p l a c t [o u 1]
p l a c e [ i n ] : - m s g o w = ( o u l m o d 10 )+ 1
in : - ( in m o d I O) + i c o Au 1I : = c o l u l 1 1
c o u n t : = c o u n 1+ 1 c n d r e g i o n
e n d r e g i o n / · c o n - 11 1c n s a gc m m s g 1 /
e n d lo o p c n d lo o p
8
. 
3 R e g i õ e s n ã o p a r a m e t r i z a d a s e r e g iMe s i n c o n d i c i o n a i s
A s r e g i õe s c r f t i c a s po de m s e r s i r n p l 1li c a d a s SUp n mi s e a
-
w 1r i z a ç ão ( i s t o , s u pDm in do
a e s pe c i f i c aç ão d o c o m p o n e n te < v a r > ) N e s te c c ta s f i c a m n â o a s s o c i a d a s a u m c o n ju n to dc
d a do s e t o d a s e l a s p a s s a m a s e r m u t u a m e n te e x c l u s r v a s e n t r e s l p o n a n to
, pa r a a v e r s ão n
ao
p a r a m e t r i z a da , n ào po s s í v e l t r a ba l ha r s i m u l t a n e a m e n t e s o b r e d r f c r e n t e s c o n j u n t o s dc dado s 
N e s te c a s o
. 
a r e g i ão c r í t i c a c o n d ic io n a l f ic a e q u i v a l e n t e a o c o - do " w he n « c o n d» 
do
< c o - do > " d a l i n g u a ge m Ed is o n [B R I 8 1] 
o u t r a i 呷 le m e n t a ção s i m pl i tì c a da de n o m i n a da r e g iâ o c r Tt i c a i r 1c o n d ic io n û
1 NesE
c a s o
, 
n ao e x i s t e a c o n d iç o dc e n t r a d a « c o n d> ( c o m o s e a c o n d ição f o s s e s e m p r e v e rda
de ira) 
c o m e s t a s i m p l i f i c a ção , a v e r s o p - t r i 7 a d a e q u i v a le n te a o p a r m u I e x b t g i11
/M v n
d
-
u i z a d o e a v e r s ão n äo p- t r i z a da e qu i v a l e n t e a o pa r txbegin / rn u 1t x t nd nao
-
t r i z a d o
8
. 
4 E X E R C I C l O S
E s e - & 1 Fo i - c o m o s i n u 1a r s e -
- r e g i ð e s c D t i c a s
: i m u lw r c g i ö es c r í t i c a s c o m s e - ( i s t o
- q u le o s do i s m c a n i s m o : são
Scanned by CamScanner
-
8 0 M e c a n i s m o d a s R c 吕 io c 1 C « t i c a s 105
D IC A D a d a u m a < c o n d i ç ao > e u r r 1a < s e q u en c i a de c o m a n d o s > , b a s t a m o s t r a r c o m o f a z e r a
< s e q uén c i a de c o m a n d o s > s e r e x e c u t a da d e f o r m a m u t u a m e n te e x c l u s i v m a s i s to a p e n a s
q u a n d o < c o n d iç o > f o r v e r da d e i r a
E x e r c fc i o 8 2 U s a n d o r e g i õ e s c r i t i c a s c o n d i c i o n a i s , a p r e s e n t e u m a s o l u ç ão p a r a o p r o le m a d o s
f i l ósof os
E x e r c íc i o 8 3 U s a n d o r e g i õ e s c r i t i c a s c o n d i c i o n a i s , a p r e s e n t e u m a s o l u ç ão p a r a o p r o le m a d o
b a r b e i r o d o r m i n h o c o
E x e r c íc i o 8 4 U s a n d o r e g i Me s c D t ic a s c o n d i c i o n a i s , a p r e s e n t e u m a s o l u ç ão p a r a o p r o l e m a d o s
r e a d e r s & w D t e r s
E x e r c íc i o 8 5 U s a n d o r e g i õ e s c r i t i c a s c o n d i c i o n a i s , e s c r e v a u m p r o c e d i m e n t o d e n o m i n a d o
g a t h e r 3 q u e i m p l e m e n t e u m a b a r r e i r a d e v a l o r 3
E x e r c : c i o 8 6 D e s c r e v a c o m o r e g i õ e s c r i t i c a s c o n d i c i o n a i s p o d e D a m s e r i m p l e m e n t a d a s n o
k e r n e l d e u m s i s t e m a o p e r a c i o n a l
e x e r c i c i o 8 7 U s a n d o r e g i õ e s c r i t i c a s c o n d i c i o n a i s , e s p e c i f iq u e o s p r o c e s s o s p l , p 2 _ , p6 . d e
m o d o a s a t i s f a z e r a r e l a ç ão d e p r e c e dên c i a m o s t r a d a n o g r a f o d o e x e r c i c i o 3 1
Scanned by CamScanner
106 Si s t e m a s
-
o n a i s e pT o s r a m a çao C o n c o r r e n t e S S T o s c a n i , R S de O 1i v e i r a e A S im i
E B m o r e n o M a r t ín F ie r m
q u i e r o s a b e r y 1o i n o r o M o r e n o t e de jás c a i r
pu e s e n m i s l i b r o s n o e s t á c o m o c a r a n c ho e n s u n ido
y s u r e s pu e s t a v e n d r á ya v e o qu e s o s p r e v e n ido
a s e r v i r m e de Bobi er no : 1Ti a s ta m b ién e s to y d is pu e s to
pa r a q u f 1n c l Et er no v e r e m o s s i t e c o n te s t o
ha c r i a do 1a c a n 山 1á y s i te d a s po r v e n c id o
U n o e s c l 8 o I u n o e l m u n d o
s o la y ú t1i c a e s l a Iu 11u
a n s f ha n d e s a be r qu e D i o s
n o c r iá c a m id á n i n 吕 u n a
El s e r d e t o d o s 1o s s e r e s
aó lo fo r m ó 1a u n id á
1o de 1n ú* l o ha c T i a do e l ho m b r e
de s pu 1 q u c a p r e n d iö a c o n t a r
, 
t