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

Prévia do material em texto

Scanned by CamScanner
C a p f t u l o 6
S I N C R O N I Z A ÇÕE S
B Á S I C A S
M a r t i n F i e r r o E t m o r e n o
M e g u s t a n e g r o la d i n o Y o n o s o y c a n t o r 1a d i n o
1o q u e a c a b ás d e e s p l i c a r y m i h a b i l i d á e s m u y po c a
y a [ e e n p i e z o a r e s pe t a r m a s c u a n d o c a n t a r m i t o c a
a u n q u e a l p r i n c i p i o m e r e i m e d e f i e n d o e n e l c o m b a t e
y t e qu ie r o p r e g u n t a r po r qu e s o y c o m o lo s 1n a 1e s
lo q u e e n t e n d s po r 1a 1e y s i r v o s i m e a b r e n Ia b
D e n d e q u e e l i ge a s u gu s t o
Io m a s c s p i n o s o e l ig e
pe r o e s t o po c o m e a f1i 
 
e
y le c o n t e s t o a m i 1n o do
1a l e y s e ha c e pa r a t o do s
m a s s ó l o a l po b r e I¢ Dge
A p a r t i r de s te c a p í t u l o , s ão a p r e s e n t a d o s d i v e r s o s m e c a n i s m o s p a r a s i n c r o n i z a ç o e c o m u n ic a ç ão
d e p r o c e s s o s p a r a c ad a m e c a n i s m o , é m o s t r a d o c o m o o m e s m o po d e s e r i m p le 1n e n t a d o n o
ke r n e l d o SO i n i c i a l m e n t e , s ão c a r a c t e r i z a do s o s t i p o s bás i c o s d e s i n c r o n i z a ç o
6
. 
1 A s t r ês s i n c r o n i z a ç t ie s b ás i c a s
C o n s id e r e do i s p r o c e s s o s , c a d a u m e x e c u t a n do u r r 1a1 u pe r a q u d i s t i n t a Se a lg u n 1a s in c 1u n i z a ç i lo
fo r r e q u e r i da pa r a e s s e s pmc es s us (e m r e l a ç o a e s s a s d u u s o pe r a çöe s ) , e n t o c e r ta m e n t e e l a s e
e n q u a dr a r á e m u m d o s s e g u i n t e s t r ês c a s o s
(a ) a s o pe r a çõ e s n ão d e v e m s e r e x e c u t a d a s s i m u l t a n e a m e n te
(b ) u m a d a s o pe r a çò e s de v e i n i c i a r a pó s o tér m i n o d a o u t r a
Scanned by CamScanner
78 Si s t e m a s 
 Æ o n a i s e p r o 8 r a m a çao Co n c o r r e n t e S - de O l i v e i r a e A S Car i » j m i
(c ) a s o pe r a çö e s de v e m i n i c i a r " s i m u l t a n e a m e n te "
A p r i m e i r a s i n c r o n i z a ção s u r ge n o u s o de r e c u r s o s c o m pa r t i l ha do s q u e de v e m ser
u s a d o s p o r u m ú n i c o p r o c e s s o d e c a da v e z
4 1 E x e m p l o s de r e c u r s o s c o m pa r t i lha do s são
e s t r u t u r a s d e d a do s g lo ba i s , d i s po s i t i v o s de E/ S e p r o c e d i m e n t o s n ão r e e n t r áv e i s D i z se qu e o s
m e c a n i s m o s p a r a e s te t i po de s i n c r o n i z a ção s ão v o l ta do s pa r a o c o m p a r 1i l l ia m e n t o de r e c u r t o r
O s e g u n d o t i po d e s i n c r o n i z a ção s u r ge qu a n do p r o c e s s o s c o o pe r a m e n t r e s i , po r
e x e n q»lo , e x e c u t a n d o e t a p a s s e qü e n c ia i s de u m s e r v i ço E s te t i po de s i n c r o n i z a ção r e q u e r u m
m e c a n i s m o q u e pe r m i t a b l o q u e a r u m p r o c e s s o a té a c he g a da de u m s i n a l (a v i s o ) de o u t r o
Pr o c e s s o Po r t a n t o
, 
é r e q u e r i do u m m e c a n i s m o de c o m u n i c a ção D i z s e qu e o s m e c a n i s m o s pa r a
e s t e t i p o d e s i n c r o n i z a ção s ão v o l t a d o s p a r a a c o m u n i c a çã o de p r o c e s s o s
O t e r c e i r o t i p o d e s i n c r o n i z a ção s u r ge q u a n do p r o c e s s o s p r e c i s a m s e a g r u p a r , pa r a
d e p o i s p r o s s e g u i r e m a o m e s m o t e m po E s t a s i n c r o n i z a ç ão é n e c e s s á r i a , po r e x e m p l o q u a n d o u m
g r u p o d e p r o c e s s o s p r e c i s a s e c e r t i f i c a r q u e to d o s e le s j á a c a b a r a m s u a s o p e r a çõ e s (t a l v e z pa r a
i n i c i a r e m o u t r a ) E s t e t i p o d e s i t u a ç o é c o m u m e m a p l i c a çõ e s d i s t r i b u :d a s e r e q u e r u m
m e c a n i s m o p a r a a g r u p a r (o u r e s i n c r o n i z a r ) p r o c e s s o s Po de s e d i z e r q u e o m e c a n i s m o a t u a
c o m o u m a b a r r e i r a (o u b a r r a g e m ) , q u e s e g u r a t e m p o r a r i a m e n te o s p r o c e s s o s
6 1 1 S i n c r o n i z a çã o p a r a c o m p a r t i l h a m e n t o
E s t e t i p o d e s i n c r o n i z a ção é c a r a c t e r i z a do p e l a s o pe r a çõ e s p r i m i t i v a s m u t e x be g i n e m u t e x e n d
c o n s i d e r a d a s n o c a p í t u l o a n t e r i o r R e c o r da n do , a o pe r a ção m u l e x b e g i n s ó de i x a pa s s ar o
p r i m e i r o p r o c e s s o q u e a e x e c u t a , o s d e m a i s f i c a m b l o q u e a d o s Qu a n d o o p r i m e i r o (o q u e p a s s o u
pe l a o pe r a ção m u t e x b e g i n ) e x e c u t a a o pe r a ç ão m u t ex e n d u m ú n i c o p r o c e s s o (de n t r e o s
b l o q u e a d o s ) o b tém pe r m i s s ão pa r a p r o s s e g u i r D e s s a m a n e i r a , n u n c a s e t e m m a i s de u m
p r o c e s s o e x e c u t a n d o de n t r o de u m t r e c ho d e l i m i t a d o pe l o p a r m u t e x be E n m u t e x e n d A iì gu r a
6 1 m o s t r a c o m o s e r i a a i mpl ement açi o da e x c l u s ão m ú t u a de n r e g iõ e s c r i t i c a s
m u t e x be g i n ; m u t e x be g i n ; m u t e x be g i n
R E G IÃ O C R 9T IC A ; R E G IÃO C R IT IC A ; R EG IÃO C R ÍT ICA
m 11t e x e n d m u [e x e n d ; m u te x e n d
月 l u r a 6 1 E Jrc l u · * o m ú t u a · n t r e n p r o c e s · o ·
4 1 A pó 1 1e r l ibe r ado po r u m 1 1o o r e c u n o po d e s e r u s a do po r o u 1r o p r o c e i s o D e s s a m a n e i r a u m a 
s r ie d¢
p- s o s po de u s a r o m e s m o r e c u n o u m pr o c e a 1o d e c a d a v e z p o r e s t a r a z üo e s t e s r e c w so s s
=o di1o s
s e r ia Bn Be n Bt r e iBs á v t i s
Scanned by CamScanner
C a p i t u lo 6 S i n c r o n i z a ço c s B #a i c a s 79
6
. 
1 2 Si n c r o n i z a çã o p a r a c o m u n l c a ç o
E s t e t i & » d e s i n c r o n i z a ç o é c a r a c te D z a do pe l a s o pe r a çöe s p r i m i t i v a s b lo c k e w a ke u p (p ) , - m
j á a p r e s e n t a d a s n o c a p f t u l o a n t e Do r A o pe r a ção b l o c k b lo qu e ia o p r o c e s s o q u e a e x e c u ta e a
o pe r a ção w a k e u p (p ) d e s b l o q u e i a o p r o c e s s o p e s pe c i f 1c a do c o m o a rg u m e n t o E s s a i - ö c s
i m p l e m e n t a m u m a fo r m a de c o m u n ic a ção s i m pl e s , o n de n ão há pa s s a g e m dc i n f o r m a ç ão 
42 A
s i n c r o n i z a ç ão " a o pe r a ção A de P 1 de v e s e r e x e c u t a da a pós a o pe r a ção B de P2
-
 o b «ida d a
m a n e i r a m o s t r a d a n a f i gu r a 6 2
丝 丝
b l o c k
A B
w a k e u p (P 1)
F Ig u r a 6 2 A o p e r a ç ã o A v a i s e r e x e c u t a d a a p ó s a o p e r a ç ã o B
6 1 3 S i n c r o n i z a ç ã o t i p o b a r r e i r a
E s t e t i po d e s i n c r o n i z a ção é c a r a c t e r i z a d o p e l o m e c a n i s m o c o n h e c i d o c o m o b a r r i e r (b a r r e i r a )
U m a b a r r e i r a B d e v a l o r n (i n t e i r o ) b l o q u e i a o s n 1 p r i m e i r o s p r o c e s s o s q u e e x e c u t a m a o pe r a ç ão
g a t h e r ( B ) 4 3 Qu a n d o o n és i m o p r o c e s s o e x e c u t a e s s a o p e r a ç ão , t o d o s o s n p r o c e s s o s
p r o s s e g u e m s u a s e x e c u çMes Po r e x e m p l o , s e 
f o r d e c l a r a d o " X : b a r r ie r i n i t i a l 3 " , o s 2 p D m e i r o s
p r o c e s s o s q u e e x e c u t a r e m a o p e r a ç ão g a
th e r (X ) v o f i c a r b l o q u e a d o s ; q u a n d o u m t e r c e i r o
p r o c e s s o e x e c u t a r e s s a o pe r a ção , o s 
3 p r o c e s s o s p r o s s e g u i r ão s u a s e x e c u çõe s n o r m a l m e n t e
A f i g u r a 6 3 m o s t r a c o m o a o pe r a ç
ão de j u n t a r d o i s p r o c e s s o s (b a r r e i r a de v a l o r 2 )
po de r i a s e r o b t i d a a p a r t i r d o s m e c
a n i s m o s b to c k e w a k e u p (p ) N e s se e x e m p l o , o s p r o c e s s o s P l e
p 2 i n i c i a r ão a s o pe r a çõ e s A e B
"
a o m e s m o t e m po
"
P l 丝
w a k e u p (P2 ) : w a k e u p(P 1)
b l o c k ; b lo c k
A B
F1g u m 6 3 0 p r i m e i r o q u · c h 1 g 1 · r p r a p 
· Bo * 1 g u n d o
41 Qu a n do u m r i n a l n ao c o n d u z i n fo r m a ç=o e le e d i to 1e r u m s
in a l p u m Em o u t r a i pa la v r a s u m s in a l pu r o n l o
t r a n s fe r e da d o » de u m pï o c e 1 1o pa r a o u t r o , e le c o n
du B a pe n a1 u m a in fo r m 1q1o de 1 i n c r o n iz aç1o qu e ¢ u sad a
i n t - n t e pe lo * t mw t l do SO
4 3 A lbu m a u t o r e 1 u t i l i z a m a de n o m in aç
1o ban te r a o in v ëa de 吕 a t he r pa r a e r ta o pe r a ç&o pr i m i t i v 1
Scanned by CamScanner
80 s i s t e m a s o pe r a c i o n a i s e pTo8r ama£ C o n c o r r e n t e S S T o s c a n i R S d e g v e i r a e A s c ar i r s i 1n i
6
. 
1
. 
4 So b r e a n e c e s s i d a d e d a s o p e r a çõ e s b i l s l c a s
A s o pe r a qöe s m u t e x b e g i n / m u re x e n d e b l o c k/ w a ke u p (p ) c o s t u m a m s e r c o n s i de r a d a s " s u f 1c ie n te i "
p a r a i m p le m e n t a r q u a lq u e r e s q u e m a de s i n c r o n i z a ção o u p r o t o c o l o d e c o m u n i c aç ão qu e se
i n 1a g i n e , c o m q u a lqu e r n ú m e r o de p r o c e s s o s C o m o a p a r t i r de q u a lq u e r u m a de s s a s oper aç
(r n Bu e x be g i n l m u 1e x e n d o u b l o c k l w a lce u p (p )) po de s e s i m u l a r a o u t r a , p o d e s e d i z e r qu e a pm as
u m a d e l a s j á é " s u f i c i e n t e " M a s
, 
n a v e r d a de
,
"
n a da " j á é s u f i c i e n t e , po i s a p a r t i r do n a d a (i s to 
,
s e m u s a r n e n hu m r e c u r s o e s pe c i a l ) po de s e c r i a r q u a lq u e r m e c a n i s m o 44 Po r e x e m p l o , a s o lu ção
de D e k k e r m o s t r a c o m o c o n s t r u i r u m m e c a n i s m o de e x c l u s ão m ú t u a p a r a 2 p r o c e s s o s s e m u sa r
q u a l q u e r r e c u r s o e s p e c i a l e a s o l u ç ão de L a m p o r t f a z i s s o p a r a n p r o c e s s o s A s e ção a s e gu ir
m o s t r a c o m o i m p le m e n t a r a s o pe r a çô e s bl o c k e w a ke u p (p ) " f r o m t he s c r a t c h "
6
. 
2 C o n s t r u i n d o b l o c k / w a k e u p (p ) a p a r t i r d o n a d a
O e x e m p l o a s e g u i r m o s t r a a i m p l e m e n t a ç o d a s o p e r a çõ e s b to c k e w a k e u p (p ) , f o r a d o k e r n e l
s e m u s a r q u a l q u e r r e c u r s o e s p e c i a l O t r u q u e c o n s i s t e e m u t i l i z a r u m p r o c e s s o e x t r a (e s péc i e de
s e r v i d o r ) q u e i m p l e m e n t a e s t a s o p e r a çõ e s p a r a o s d e m a i s A c o m u n i c a ç ão e n t r e u m " p r o c e s s o
u s u á r i o e o s e r v i d o r é fe i t a a t r a v és de d o i s v e t o r e s g l o b a i s , d e n o m i n a d o s q u e r e o p e r , a m bo s
c o m n e l e m e n t o s o n d e n é o n ú m e r o d e p r o c e s s o s
V a D á v e i s g l o b a is q u e r a r r a y [n ] o f bo o 1e a n i n i t ia l f a l s e
o p e r a r r a y [n ] o f in te g e r
O s p r o c e s s o s u s u i o s e x e c u t a m a s o pe r a çõ e s b l o c k e w a ke u p (p ) c o m o m o s t r a d o a s e g u i r
P r o c e s s o i I [ i [ n »
b l o c k
o p e r t i ] : - O ; / * r e q u i s i t a o pe r a ção b to c k * /
q u e r M t r ue
】o o p
e x h w he n n q u e r w
e n d l o o p
w a k e u p (k )
q u e r 【i ] : - t r u e ; 
/ * r e q u i s i t a o pe r a ç ão w a ke u p (k ) * /
l o o p
e x h w he n q u e r M
e n d l o o p
m u i t o r edu z i do de in « r u çöe 1
Scanned by CamScanner
C a p i tu lo 6 Si n - i z a çö cs B ás i c a s 8 1
C o m o s e v ë
,
' " OCes s o 1 c o m u n ic a a o pe r a ç o a s e r e x e c u t a d a a t r a v s do e l e m e n t o
o p e r { i ] V a l o r z e r o s ig n i fi c a b l o c k e v a lo r k s ig n i f ic a w a ke u p (k ) O p r o c e s so s e r v id o r é m o s rr a d o
a s e g u i r A l m d o s v e t o r e s g l o b a i s o p e r e q u e r , o s e r v ido r u s a u m v e t o r l o c a l * e m qf de n
e le m e n t o s
, 
i n ic i a l i z a do c o m z e r o s
, 
e a s v a Dáv e i s l o c a i s i e k
P r o _ o s e r v i d o r
Va r i d v e i s l o c a i s s e m a m y [n 】 o f i n t e ge r i n i t i a l 0
i
, 
k i n t e g e r
l o o p
i : - ( i m o d n ) + l
i f q u e r w
t h e n i f op e r n O
t h e n i f se1Ai ] > 0 / * o pe r a ção é b l o c k * /
t h e n { s e m a A i ] : = s e m a A i ] 1
q u e r w f a l s e
e l s e n o t h i n g
e l s e ( k : = o p e r t i ] ; / * o pe r a ç ão é w a k e u p * /
s e m a ßk ] : = s e m a j tk l + l
q u e r w f a l s e
e l s e n o t h i n g
e n d l o o p
T a l c o m o o c o r r e n o s a lg o r i t m o s de e x c l u s ão m ú t u a , a e s p e r a d e u m p r o c e s s o 
i m p l e m e n ta da a t r a v és de b u s y l o o p
6
. 
3 A l i n g u a g e m W e a s s i n c r o n i z a çõ e s b á s i c a s
A l i n g u a g e m W i m p l e m e n t a a s o pe r a çö e s m u t e x be g in
/ n Bu t e x e n d e bl o c k/ w a ke u p (p ) e x a t a m e n te
c o m e l a s f o r a m d e f i n id a s n o k e r n e l de SO , v i s t o n o c a p í t u l o a n t e Do r
E m b o r a n ão s e j a c o r r e t o d i z e r q u e a s o pe r a çö e s m u t e x b r g in / r n d e bl u c Bl w Be idp M o
s u f ic ie n te s " p a r a r e s o l v e r p r o b l e m a s de s i n c r o n
i z a çäo , s e m d úv ida po de s c d i z e r q u e e s t a s
o pe r a çö e s s o a d e q u a d a s pa r a e s s e f i m E u m bo m e x e r c fc i o de pr o g r a n í1a q
i lo s e M r e s o l v e r o s
p r o b le m a s a p r e s e n t a d o s n e s t e l i v r o , u s a n do e s te c o n j u n t o de o pe r a çö e s (e x c r c fc io s se r ao
p r o po s t o s n o d e c o r r e r d o te x t o , o po r t u n a m e n te ) 
N a s e ção 6 3 2 , a p r e s e n t a d o u m p r o g r a m a W c o m p le t o , q u e u s a a s o pc r a çöe s bás ic a s
p u a r e s o l v e r o p r o b le m a de a l o c a r u m r e c u r s o de N u n ida de s pa r a u m c o n ju n to de p r o c e s s o s
Scanned by CamScanner
82 s i s t e m 1 s OpeFci onr e - ® o c o n c o r r e n t e s s TOSCani . s de o l i v e i r a e A
. 
s c ar i
* iN
i n d epe n de n te s E s s e p r o g r a m a u t
i l i z a a lgu n s r e c u r s o s d e p r o g r a m a ção q u e s ão a pr e sm tados a
s e gu i r
6 3
. 
1 F i l a s e s i m u l a ção d o t e m p o n a l i n g u a ge m V 4
A l i n g u a ge m v a l e 4 o fe r e c e f a c i lida de s pa r a cr i açi o e u s o de f i l a s , j á qu e e s te t i po de e i tn Btu r a
o c - f r e qü e n t e m e n t e e m a p l ic a çõe s c o n c o r r e n t e s A l i n gu a ge m t a m bém pe r m i te a s i ï m Blação da
p a s s a ge m d o t e r n p o , du r a n t e a e x e c u ção de u m p r o g r a m a
V a D áv e l t i p o q u e u e
So b r e u m a v a r i áv e l X
, 
de c l a r a d a c o m o s e n do do t i p o q u e u e , p o de m s e r a p l i c a da s a s se gu in tes
o p e r a çõ e s
 e mp t y (X) , f un ç ão boo l ea n a qu e r e t om a t r ue se a f i l a X es t á va z i a
 c o u n 1 (X) ,
 f
un ç ão i nt ei ra qu e r et oma o t ama n h o da f i l a X
* i n s e r 1(P
, 
X )
, p r o c e d i m e n t o q u e i n s e r e o e le m e n t o P (v a l o r in t e i r o ) n o f i m da f i la X
* ß r s 1 (X ) , f u n ção i n te i r a qu e r e t o m a o p r i m e i r o e le m e n t o d a f i l a X e r e m o v e e s se e le m e n to
d a f i l a
C o m a n d o s h o ld (K ) e y i e ld
0 c o m a n d o ho ld (K ) a t r a s a a e x e c u ção d o p r o c e s s o e m K u n id a d e s d e t e m p o Se K é z e ro , o
e f e i t o l íq u i do é c o l o c a r o p r o c e s s o n o f i m d a r e a d y t i s l e p a s s a r a U C P pa r a o u t r o p r o c e
sso O
m e s m o e fe i t o de ho ld (0) é c o n s e g u i do c o m o c o m a n do y ie l d c u j a ún ic a f in a l idade é pas sar
a d i a n t e o p r o c e s s a do r E s t e c o m a n do é ú t i l e m b u s y to o p s , q u a n do s e v e r i f ic a qu e n o 
há n ada
pa r a f a z e r , a lém d e r e pe t i r o lo o p
Pa r a i 呷 le m e n t a r o c o m a n do /1o ld (K )
, 
o a m b i e n te de e x e c u ç o w u s a u m
a t& n iLa
c o m u m d e s i m u l a ção d i s c r e ta , q u e é de s c D (a a s e g u i r o s i s te m a po s s u i u m r e ldg io , re p
æ se n ca
l o
po r u m a v a r i á v e l i n t e i r a i n ic i a l iz a d a c o m z e r o
, 
e e s s e r e lóg io po s s u i u m a 
l is t a de esp
e ra
a s so c i a da s e u m p r o c e s s o , n o te m po T (i s t o é
, 
c o m a v a r i áv e l q u e r e p r e s e n t a o 
r e 1ö 吕 io v a
le ndo
7)
. 
E x e c u t a u m c o m a n do ho ld (K )
, 
e le c o l o c a do n a l i s t a de e s pe r a pa r a s e r a c
o r dado n o 
tens o
T+ K Qu a n d o a r e a dy i is i f i c a v a z ia
, 
o v a lo r do r e lóg io é a tu a l i z a do pa r a o 
te m po do primei 
rl )
p r o c e s s o da l i s t a de e s pe r a (a l i s t a é o r ga n i z a d a n a o r de m c r e s c e n t e do s t e m po
s ) e todo s 
os
pr o c e s so s q u e a 吕 u a r da m po r e s s e m e s m o t e m po s üo m o v id o s da l is t a do r e lóg
io pa r a a 1
ì¢Qdy lb t 
o t e n q»o a t u a l d o r e l óg i o po de s e l. Re f e r ido e m u m p r o g r a m
a v 4 o
tr a v s 
dos
ide n t i fì c a do r e s c to c k t im e
, 
c to c kT im e o u c u r r e n t t i m e
, 
i n d i fe r e n te m e n te
i =
Scanned by CamScanner
C a p« u lo 6 - z a ç û ca B ás i c a s 83
6 3
. 
2 U m e x e m p l o
O p r o g r a m a V 4 a s e g u i r u t i l i z a o pe r a çö e s m u t e x be g tn / m u t e x e n d c b l o c k / w a ke u p (p ) pa r a
c o n t r o l a r a a l o c a ção d e u m r e c u r s o O p r o g r a m a i m p l e m e n t a a s o pe r a çöe s r e q u e s t e r e te m e ,
s e n d o u t i l i z a d a s a s e s t r u t u r a s de d a do s e o s a lg o r i t m o s j á a p r e s e n t a do s n a s e ção 4 1 0 p r o g r a m a
e s tá c o m p le t o , t e n d o s i d o c o d i f ic a d o s
, 
i n c l u s i v e
, 
d o i s p r o c e s s o s p a r a r e a l i z a r c h a m a d a s pa r a a s
o pe r a qð e s r e q u e s t e r e l e a s e
% A l o c a ção d e u m r e c u r s o d e 5 u n i d a de s
V 4 p r o g r a m
R a m y [5 ] o f i n t e ge r
T i n t e g e r
Q q u e u e
p r o c e d u r e r e q u e s t o r e t ur ns i n t e g e r
b l o q u e a r b o o i e a n
l o o p
bl oquear - f al se
m u t e x b e g i n
i f T / 0
t h e n { b l o q u e a r = t r u e ; i n s e r t (m y s e l f , Q) }
e l s e { r e q u e s t : = R [71 ; T = T l }
m u t e x e n d
i f b l o q u e a r th e n b lo c k e l s e e x i t
e n d l o o p
p r o c e d u r e r e l e a s e (U : i n t e g e r )
i d i n t e g e r
m u t e x be g i n
T = T + L ; R [71: = U
. 
i f n o t e m p t y (Q) t he n { id = f i r s t (Q) ; w a k e u p ( id) }
m u t e x e n d
p r o c e du r e i n i c ia l i za o
l o o p
T = T+ l
R t71 : = 6 T
e x i t w h e n T= 5
e n d lo o p
Scanned by CamScanner
84 s i s t e m a s o pe r a c io n a i s e n o w a m a ç* o Co n c o r r e n t e
S S T o s c a n i
, 
R S de O1i v e i r a y s
. 
c ar i r 1im i
p t o c e s s pl
u i n t e ge r
i nóauz ao
w a k e u p(p 2 )
U = r e q u e s K)
n l ; w D te (m y s e tj ) ; t a b ( 1) ; w Dt e (U )
: 
e 
1 d 
e 
( 1 
a s
) ; 
(U)
p r o c e s s p 2
U
, 
K i n t e ge r
b lo c k
w hü e K 5 d o
U r equest o
n l ; w r i t e (m y s e t l ) ; t a b ( 1) ; w r i t e (U )
K = K + l
e n d p r o g r a m
E x a m i n a n d o o p r o g r a m a , p o de s e v e r q u e o p r o c e s s o p ì v a i i n i c i a l i z a r a s v a r iáv e is
g l o b a i s , a t r a v s d o p r o c e d i m e n t o i n i c ia t i z a , e l o g o e m s e g u i d a v a i d e sb l o q u e a r o p r o c e s so p2 A
s e g u i r , p l v a i r e q u i s i t a r u m a ún i c a u n i da de d o r e c u r s o e " d o r m i r p o r u m a u n i da de de te m po
O p r o c e s s o p 2 v a i r e q u i s i t a r 5 u n i d a de s d o r e c u r s o
, 
u m a a pó s a o u t r a C o m o u m a 
das
u n i ó d c s v a i e s t a r a l o c a d a p a r a p ] , o p r o c e s s o p 2 v a i b l o q u e a r s e q u a n d o r e qu i s i t ar a qu i n t
a
u n i d a de e a r e a dy l i s t f i c a r á v a z i a o r e l óg i o do s i s t e m a v a i e n t o a v a n ça r pa r a o te m po 
1 e
(n e s s e t e m po ) p / v a i s e r de s pe r t a d o
, 
v a i l ibe r a r a u n id a de qu e e l e po s s u i a e v a i te r m
in ar sua
e x e c u ção A u n id a de l i be r a d a po r p l v a i s e r v i r pa r a de s bl o q u e a r p 2 , q u e r e c e be r á su
a qu in ta
u n i da de e te r m i n a r á s u a e x e c u ção Po r t a n t o
, 
a e x e c u ç tio do p r o g r a m a c o n c o r r e n te v a
i te r m in ar
c o m o r e l óg i o d o s i s te m a m a r c a n do 1 (u m a u n id a de de te m po )
6
. 
4 So \ u çã o d e p r o b \ e m a s c o m m u t e x be g i n l e n d e b l o c k lw a k e u p
Em ge r a l , a so l u ç o de u m p r o b le m a a tr a v s d a s o pe r a çö e s n Bu t e x be g in / e n d e 
blo c u w a
Bt up
u t i l i z a
, 
a lém da s e s t r u t u r as de da do s r e la t i v a s a o p r o b le m a , u m a f i l a g l o ba l pa
r a e n
c adc ar 
as
id e n t i f 1c açöe s do a p r o c e s s o s b l o qu e a do s (v a m o s c ha m a r e s s a f i la de ß1a Bto q ) e u n 1a 
v ar iáve
l
PD v a t i v a de c a d a p r o c e s s o
, pa r a i n d ic a r s e o m e s m o de v e b lo q u e a r o u n äo (v a m o s c
ha ï n ar 
essa
v a r i áv e l de b to q u e a r ) A s e quên c i a de pa s s o s
, j á i l u s t r a da n o p r o g r a m a a n te r i o r , é aqu
i re pe t i
da
Scanned by CamScanner
C a p f ru l o 6 Si n c r o n i z a ço c s B ás i c a s 85
(a ) G a r a n t i r a e x c l u s o m ú t u a p a r a m a n i p u l a r o s d a d o s c o m p a r t i l h a do s
C o m e x c l u s o m ú t u a g a r a n t id a , e x a m i n a r o e s t a d o d o s d a do s (s i t uaçi o a t u a l do
s i s t e m a ) e
(b 1) Se o e s t a do pe r m i t i r a e x e c u ção d a f u n ção de s e j a d a , e n t ão e x e c u t a r e s s a f u n ção
e f a z e r b l o q u e a r - f a l s e
(b 2 ) C a s o c o n t r ár i o
, 
f a z e r b l o q u e a r - t r u e (n e s t e c a s o , o p r o c e s s o v a i b l o q u e a r s e n o
p a s s o (d ) , l o g o a pó s l ib e r a r a e x c l u s ão m ú t u a ) e c o lo c a r s u a id e n t i f i c a ção n o f i m d e
f 1ta B 1
(c ) L i b e r a r a e x c lu s ão m ú t u a
(d ) Se b l o q u e a r - t r u e , e n t ão b l o qu e a r a s i m e s m o C a s o c o n t r ár i o p r o s s e g u i r n a e x e c u ç ão
A o p e r a ç ão q u e b l o q u e i a o p r o c e s s o d e v e s e r r e a l i z a d a f o r a d o t r e c h o m u t u a m e n t e
e x c l u s i v o p a r a q u e n ão o r r a s i t u a ção d e b l o q u e i o et e r n o (d e a d to c k ) O p r o c e s s o pe r m a n e c e r á
b lo q u e a d o a t é q u e u m o u t r o p r o c e s s o m o d i f iq u e a c o n d i ç ão q u e d e t e r m i n o u o b l o q u e i o e o
d e s b l o q u e i e S e a s o l u ç ão d o p r o b l e m a e s t i v e r c o r r e t a , p a r a c a d a o p e r a çã o b l o c k h a v e r á u m a
o p e r a ção w a k e u p c o m p l e m e n t a 】 :
N a v e r d a de
, 
o s p r o b l e m a s d e s i n c r o n i z a ç ão e c o m u n i c a ç ão s e m p r e e n v o l v e m u m p a r de
o p e r a çMe s c o r n p l e m e n t a r e s Po r e x e m p l o , e n t r a d a n a r e g i ão c r i t i c a e s a íd a d a r e g i ão c r i t i c a ,
r e q u e s t e r e te a s e , s e n d e r >c e i v e , e t c Se a s o l u ç ão e s t i v e r c o r r e t a , c e r t a m e n t e h a v e r á u m o u t r o
p r o c e s s o q u e , n a o p e r a ção c o m p l e m e n t a r , i r á de s b l o q u e a r o p r o c e s s o q u e a n t e r i o r m e n t e s e
b l o q u e o u
6
. 
5 0 p e r a çMe s m u t e x b e g i n Tm u t e x e n d p a r a m e t r i z a d a s
U r n a g e n e r a l i z a ç ão d a s o pe r a çõ e s m u 1e x b e g i n / e n
d e n v o l v e a u t i l i z a ç ão de p a r m e t r o s Se
e x i s t e m d i v e r s o s c o n j u n t o s de d a d o s i n de pe n de n t e s , po de s e a s s o c i a r a c a d a c o n j u n t o u m
ide n t i f i c a do r
, 
o q u a l p a s s a a s e r p a r âm e t r o pa r a a s o pe r a ç
Me s n Bu t e x be g i n e m u t e x e n d A c a da
ide n t i f i c a do r v a i c o r r e s po n de r u m a v a r iá v e l bo o le a n a e u m a t i l a d e e s pe r a A s o pe r a ç
ð e s
m u t e x be g i n / e n d , c o m e s t a g e n e r a l i z a ção , pe r m i t e m qu e c o n j u n t o s de d a do s i n de pe n de n t e s s e j a m
a c e s s a d o s s i m u l t a n e a m e n t e
N a da i m pe de q u e a s o pe r a çöe s pa r a m e t r iz a d a s s e j a m u s a da s de f o r m a a n i n ha da
I nf el i zment e
, 
e s s e a n i n ha m e n to to m a po s s ív e l a o c o rT ën c ia de b l o q u e i o s et er nos (d e a d lo c * s ) 
Pa r a e x e m p l i f i c a r , a f 1g u r a 6 4 m o s t r a u m c a s o e m q u e o s p
r o c e s s o s f i c a r ão et c r nament e
b l o q u e a do s s e p 1 c o n s e g u i r a c e s s a r o c o n ju n t o d e d a do s X e n qu a n to P2 e s t á a c e s s a n do o
c o n j u n t o Y (e v ic e v e r s a ) 
Scanned by CamScanner
86 s i s t e m a s o pe r a c i o n a i s e pT o 8 r a m a ç=o 
C o n
-
S S T o s c a n i R S d e O1iv e ir a e A s
E1 : E2
m u te x be g i n (X ) ; m u te x b e g i n (Y )
(u s a d a do s X ) ; (u s a d a d o s Y )
m u te x be g i n (Y ) ; m u t e x be g i n (X )
(u s a d a do s X e Y ) : (u s a d a do s X e Y )
m u te x e n d (Y ) ; m u te x e n d (X )
m u te x e n d (X ) ; m u te x e n d (Y )
F Ig u r a 6 4 P o s s :v e l s i t u a çã o d e d e a d lo c k
6
. 
6 U m a ú l t i m a o b s e r v a çã o
A i n da s o b r e o a s s u n t o d a s e ção 6 I 4 (n e c e s s i da d e da s o pe r a çõ e s b ás ic a s ) , c o n v ém di z e r o que
s e g u e D e f a to , a t r a v és do s o f t w a r e de u m c o m p u t a do r q u a lq u e r (d e s de q u e ha ja m e m ór ia
s u f i c i e n t e e t e m po d e p r o c e s s a do r à v o n t a de ) , é p o s s ív e l s i m u l a r q u a l q u e r o u t r o c o m pu ta do r e
s e u s o f t w a r e I s t o s ig n i f ic a q u e , t e o r i c a m e n te q u a l q u e r h a r d w a r e q u e o fe r e ç a u m c o n ju n to
m í n i m o d e i n s t r u çõ e s j á é s u f i c i e n te p a r a r e s o l v e r q u a lq u e r p r o b l e m a q u e s e j a r e s o l v ív e l po r
c o 呷 u t a d o r
p o r o u t r o l a d o
, 
n ão de i x a de s e r v e r d a de qu e h a r d w a r e e s o f t w a r e a p r o p r i a do s fa c i
l i tam
a s o l u ç ão d c p r o b le m a s o i n t e r e s s e de s t e l i v r o é e s tu d a r o s m e c a n i s m o s u s a d o s n a c o
n s tr u ção de
s i s t ie m a s o pe r a c i o n a i s pa r a m áq u in a s c o m h a r d w a r e a p r o p r i a d o (c o m s i s t e m a de in te r r u pç o ,
i n s t r u çö e s p r i v i le g i a d a s , p r o te ção de m e m ó r i a , i n s t r u çõ e s t i p o t e s t a n d s e l , e tc ) E é is s o qu e se
rá
f e i t o da q u i pa r a a f r e n te A e s t r a tég i a s e r á e s t u da r o s m e c a n i s m o s u s a do s p a r a c o n s t r u
i r s is te m as
o pe r a c i o n a i s , n a o r d e m e m q u e e le s s u r g i r a m (i s t o é , d o s m a i s s i m p le s p a r a o s m ai s c o m p
le x os) 
T a m bém s e r á e s t u d a do c o m o , a pa r t i r de u m m e c a n i s m o , p o de s e s i m u l a r o s o u tr o s , e p
ar a isto
e x i s te m do i s m o t i v o s : po r q u e é d i d át ic o e , s o b r e t u do , po r q u e é u m ó t i m o e x
e r c íc io de
p r o g r a m a ç ão
6
. 
7 E X E R C FC l O S
E x e r c fc i o 6 1 M o s t r e c o m o i m p le m e n t a r u m c o n j u n to de 1o b a r r e i r a s a pa r t i r do n a
da Pe n 1
l i ta
qu e c ad a u m a d a s 1o ba r r e i r a s po s s a s e r u s a da c o m u m v a lo r d i f e r e n te ( i s t o é , c ada b
an e
i ra poJ
'
s e r u s ada pa r a a g r u pa r u m n ú m e r o di fe r e n te de p r o c e s s o s )
E x e r c fc i o 6 2 Su po n do q u e e s tao d i s po n f v e i s a s o pe r a çö e s n i u t e x be g i n
/ e n d , m o
s tre 
co m
o
i m p le m e n t a r a s o pe r a çõe s bl o c k/ w a k e u p (p ) (N äo p r e c is a u s a r u m p r a c e s s o e x t r a )
/
A
Scanned by CamScanner
C a p t 6 Si n c r o n i z a çö e s B s i c a r 87
E x e r c f f io 6 3 Su po n d o q u e e s t o d i s p o n í v e i s a s o pe r a çö e s b to c k e w a ke u p (p ) , m o s t r e c o m o
i n q»le m e n t a r a s o pe r a çöe s m u 1e x be g i n / e n d Fa ç a i s t o p a r a o c a s o de d o i s p r o c e s s o s
E x e M i o 6 4 C o n s id e r a n d o a i m p l e m e n t a ç ão d a s o pe r a çõe s b l o c k e w a k e u p (p ) a pa r t i r do n a d a
(s e ição 6 2 ), d i g a s e o c o m a n d o l o o p d o p r o c e s s o s e r v i d o r po de s e r s u b s t i t u fdo pe l o q u e s e g u e
l o o p
i : - ( i m o d n ) + i
i f q u e rm
th e n i f o p e r n O
t he n { s e n 1a í t i ] : = s e m a l . i ] 1 ; / * o pe r a ção é b l o c k * /
i f s e n zqM | o t he n q u e r M f a l s e
e l s e { k : = o p e r t i ] ; / * o p e r a ç o é w a k e u p * /
s e m M k ] : = s e m a j l k l + l
i f s e m a ñ k ] = O t he n q u e r tk ] : - f a l s e
q u e r w f a l s e
e l s e n o t h i n g
e n d l o o p
E x e r c : c i o 6 5 U s a n d o a l i n g u a g e m V 4 , e s c r e v a u m p r o g r a m a c o m 6 p r o c e s s o s q u e s a t i s f a ç a o
g r a f o d e f l u x o d e p r o c e s s o s d o e x e r c íc i o 3 1 0 p r o g r a m a de v e u t i l i z a r a pe n a s o pe r a ç Me s b l o c k e
w a ke u p (p ) 
E x e r c íc i o 6 6 U s a n d o a l i n g u a g e m W c o m s u a s o pe r a çõ e s m u t e x b e g i n , m u t e x e n d , b l o c k e
w a ke u p (p ) , c o n s t r u a u m a lg o r i t m o p a r a a g r u p a r n p r o c e s s o s ( i s t o é , s i m u l e a o pe r a ção g a 1he r
p a r a u m a b a r r e i r a c o m v a l o r i n i c i a l n )
E x e r c í c i o 6 . 7 M o s t r e c o m o po d e r i a s e r f e i t a a i m p le m e n t a ç o de ba r r e i r a s n o k e r n e l de u m
s i s t e m a o pe r a c i o n a l
E x e r c i c 1o 6 8 N o p r o g r a m a a p r e s e n t a do n a s e ç o 6 3 2 , o r e c u r s o é f o r m a \ l o po \r 5 u n id a de s
id ên t i c a s C o n s i de r e a g o r a q u e , a o i n v és de u m ún ic o r e c u r s o c o m 5 u n id a de s . s e te n ha 5
r e c u r s o « d i s t i n t o s c a d a u m c o m u m a ún i c a u n id a t le U s a n d o o pe r a çò e s N Bu l e ¥b eg in / r rBu t t x e n d e
bl o c k l 1v a k t u p (p ) , c o n s t r u a a s o pe r a çö e s r e q u e s t (R) e r ¬ I ¬ a s r (R) , t 》n de R u m i n te i r o (A s o r a . o
a r gu m e n t o de r e q u e M pa s s a a s e r u m a r g u m e n t o d e e n t r a d a )
E x e r c l c 1o 6 9 I m a g i n e q u e a s o pe r a çö e s n Bu l ¬ x b ¬ g in / n 1u l e x ¬ n d e b l o c Bl w a * e u p (p ) e s te ju n
r e l a c i o n a d a s e n t r e s i , da s e g u i n t e m a n e i r a (c o m n o v a s e m an t ic a ) A s o pe r a çöe s b l o c k e
w a ke u p (p ) de v e m o b r i g a t o Da m e n t e , s c r e x e c u t a d a s de n t r o de u m pa r m u t e x be g in n ru t e x e n d (i s to
Scanned by CamScanner
88 s i s t e m a s o pc - e p r o 吕 r a 1n a çüo C o n c -
S s T o s c a n i R s de O l ig r a a s m j
, 
d e n u \o d c u m a r e g i o c r f t i c a ) A o pe r a q o b lo c k , a l m d e b lo q u e a r o p r o c e s s o , l ibe r a o a c e sso à
r e g i ão c r f t i c a (c o m o s e o b l o c k t i v e s s e u m m u t t x e n
d i m p l :c i t o ) e a o pe r a ç o w a ke u p (p ) , a lém de
d e s b lo qu e a r o p r o c e s s o p , p a s s a o c o n t r o
le da r e g i o c r f t i c a p a r a o m e s m o C o m e s s a s n o v a
o p e r a çö e s , ï e s o l v a 0 p r o b l e m a de a l o c a r u m 
r e c u r s o p a r a u m c o n j u n t o de p r o c e s s o s (* çäo
6 3 2 ) p a r a n £io c a u s a r c o n f u s ão , de n o m i n e a s n o v a s o pe r a çõ e s d e n e w m u 1e x be g in
,
n e w m Æ e x e n d , n e w b l o c k e n e w w a ke u p (p) 
E x e r c í c i o 6 10 U m p a r d e p r o c e s s o s s e c o m u n i c a a t r a v és de u m 
v e t o r d e 5 e l e m e n t o s O
p r i m e i r o p r o c e s s o , d e n o m i n a d o p r o d u t o r , p r o d u z n ú m e r o s p a r e
s e o s c o l o c a n o v e to r O
s e g u n d o , d e n o m i n a d o c o n s 1u ?1i do r , r e t i r a o s n ú m e r o s d o v e t o r (u m p o r v e z , n a m e s m a o r de m e m
q u e e l e s f o r a m c o l o c a d o s ) , i n c r e m e n t a o i d e 1 e i m p r i m e o s O e s q u e l e t o d e s s e s i s te m a é
m o s t r a d o a s e g u i r C o m p l e t e o p r o g r a m a u s a n d o a s o p e r a çõ e s m u t e x
b e g in / m u l e x e n d e
b l o c k / w a k e u p (p ) (Qu a n do o v e t o r e s t á c h e i o o p r o d u t o r d e v e s e b l o q u e a r e q u a n do o v e to r e s tá
v a z i o
, 
o c o n s u n 1i d o r d e v e s e b l o q u e a r )
V a D á v e i s g l o b a i s v e t : a r r a y [5 ] o f i n t e g e r
i n
, 
o u t i n t e g e r i n i t i a l l
c o u n 1 : i n t e g e r i n i t i a l O ; % p o s i ç õ e s p r e e n c h i d a s n o v e t o r
P r o c e s s o p r o d u t o r P r o c e s s o c o n s u m i d o r
m s g : i n t e ge r i n i t i a l O, m s g : i n t e g e r
l o o p l o o p
m s g : = n zs g + 2
o u t : = (o u t m o d 5 ) + l
in : = ( i n m o d 5 ) + l ; m s g : = v e t [o u t j + l
v t l t i n ] : = n ï s g ; n l ; w r i t e (m s g )
e n d l o o p e n d lo o p
p a r a m e t r i z a d a s a p a r t i r d a s o pe r a çö e s bás i c a s )