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

Prévia do material em texto

Scanned by CamScanner
C a p f t u l o 4
O P R O B L E M A D A
E X C L U S O m ú T U A
M a r t fn F i e r r o E l m o r e n o
Y e l c o n s e jo d e l p r u d e n t e A p r e gu n t a t an e s c u r a
n o h a c e fa l t a e n l a p a r t id a u a t a r é d e r e s po n d e r
s i e m p r e h a d e s e r c o m e d i d a a u n q u e e s m u c h o p r e t e n d e r
l a p a l a b r a de u n c a n t o r : d e u n p o b r e n e g r o d e e s t a n c i a
y a u r a qu i e r o qu e m e d i g a s m a s c o n o c e r s u i n o r a n c i a
d e d ón de n a c e e l a m o r E s pDn c i p i o d e l s a be r
A m a e l par o e n l o s a i r e s
q u e c r u z a p o r d o n d e qu ie r a
y s i a l f i n d e s u - r a
Se a s i e n t a e n a l g u n
c o n s u a le gr e c a n t o l la m a
a s u a m a n t e c o m pa i te r u
E s t e c a p í t u l o d i s c u te o p r o b l e m a de g a r a n t
i r e x c l u s i v i da de de e x e c u ção p a r a u m p r o c e s s o ¢ m
u m s i s t e m a de p r o c e s s o s c o n c o r r e n te s O s p r o t o c o
l o s qu e i m p l e m e n t a m e x c l u s o m ú t u a e n t r e
p r o c e s s o s s ão a l g o r i t m o s c l ás s i c o s e i n te r e s s a n
te s po r s i s ó N o s a l go r i t m o s a q u i a p r e s e n ta do s
n ão s ão u s a d o s r e c u r s o s e s p e c i a i s de p r o g r a m a ção N a v e r d a de , e
l e s po de m s e r e x p re s s o s e m
q u a l q u e r l i n g u a g e m d e p r o g r a m a ç ão
4
. 
1 C a r a c t e r i z a çã o d o p r o b l e m a
Qu a n do p r o c e s s o s c o n c o r r e n t e s c o m p a r t i l ha m d a do s (v a r i áv e i s , e s t r u t u r a s de da do s , a r q u
i v o s )
, 
ë
n e c e s s áD o c o n t r o l a r o a c e s s o a e s s e s d a do s , pa r a o b t e r d e t e r n B1n
d n c la de e x e c u ça o O pe r a çöe s de
a t u a l i z a çäo n äo p o de m s e r f e i t a s s im u l t a n e a m e n te po r 
d i fe r e n te s pr o c e s s o s T a m po u c o o pe r a çöe s
Scanned by CamScanner
4 2 s i s t e m a s ® i e r a c i o n a i s e pr o g r a m 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 ar i r si1n j
de l e i t u r a po de m o c o r r e r s i m u l ta n e a m e n te c o m a t u a l i z a ç
ð e s
, Po i s o s d a do s l ido s po de m es tar
te m p o r a r i a m e n t e i n c o n s i s t e n te s
o s e g u i n te e x e m p lo i lu s t r a o s p r o b l e m a s qu e po
de m o c o r r e r qu a n do n ão se gar i n te
e x c l u s o m k tu a n o a c e s s o a o s da do s c o m pa r t i lha do s Su po r q u e u m v e to r g l o ba l R de 5
e l e m e n t o s s e ja u t i l i z a do pa r a c o n t r o l a r a a l o c a ção de 5 u n ida de s de u m r e c u r s o (o r ec u rso
po de r i a s e r , po r e x e m pl o , 5 b lo c o s de m e m ór i a de ig u a l ta m a n hò) A v a r i áv e l g l o b a l T é u sada
c o m o c o n t a do r d e u n i d a d e s d i s po n fv e i s e c a da e le m e n t o do v e t o r ide n t
i f ic a u m a u n i d a de O v a lo r
R >r ] (i s t o é
, 
o e le m e n t o d e R c u j o ín d ic e é T ) i n d i c a a p r óx i m a u n i d a de a s e r a lo c a da O s v a lo r es
i n i c i a i s d e R e T (c o m t o da s a s u n i da de s l i v r e s ) s ão
R - [5
, 
4
, 
3
, 
2
, 
r ]
T = 5
O s p r o c e d i m e n t o s p a r a r e qu i s i ta r e l ib e r a r u m a u n i d a de d o r e c u r s o s ão
r e q u is i ra ( U ) l i be r a l U )
U = R [T ] ; T = T + I
V a m o s s u p o r q u e a s 5 u n ida de s te n ha m s ido f e qu i s i t a d a s (e a l o c a d a s ) s e m o c o r r ên c i a de
e r r o e q u e , e m s e g u i d a , 3 d e l a s te n ha m s id o l ibe r a d a s Su po n d o q u e a s u n i da d e s l ib e r a da s se ja m
a s d e n ú m e r o 3 , 1 e 4 , n e s ta o r de m , a e s t r u t u r a d e d a d o s q u e de s c r e v e o r e c u r s o fi c a Da n a
s e g u i n t e s i t u a ção
T = 3
I s to s ign i f i c a q u e , n o m o m e n to , e s tão di s po n ív e i s a s u n id a de s 3
, 
1 e 4 (po r ta n to , estão
a l o c a da s a s u n i d a de s 5 e 2) Su po r q u e , a go r a , do i s p r o c e s s o s e x e c u te m a s o pe r a çõe s " l ibe ra (5Y
"
e
"
r e q u i s i ta (K y" e q u e a s 4 o pe r a çMe s e n v o l v id a s s e j a m e x e c u t a d a s n a s e g u i n te o r de m
T = T + L (pa s s o l de l ibe r a (5) : T . 4 )
K = R [T ] (Pa s s o l de r e q u i s i t a (K ) : K . R [4 ]= 2 )
T = T 1 (pa s s o 2 de r e qu i s i ta (K ): T = 3)
R【T ] : = 5 (Pa s s o 2 de l ibe r a (5) : R [3 ] . 5)
O r e s u l t a do n e s te c a s o ser i
R - 【3
,
1
,
5
,
2
,
1】
T » 3
E te r á a c o n te c id o o s e gu in te : a u n ida de 2
, qu e e s t a v a s e n do u s a da po r u m p ro c e s
s o , te
i a
s ido a l o c a da p a r a o u t r o p r o c e s s o (o qu e n üo po de a c o n te c e r ) e a u n ida de 5 , l ibe ra da , f!s
: 
. 9
Scanned by CamScanner
Ca p f t u lo 4 0 Pr o b l e rn a da E x c lu s ao M ú t u a 4 3
o c u p a n do a 3 ' p o s i ç ão d o v e t o r R (lu g a r o n de e s t a v a a u n id a de 4 ) O f a to da u n ida de 5 o c u pa r o
lu g a r o n de e s ta v a a u n id a de 4
, 
f a z c o m q u e a u n id a de 4 de s a pa r e ç a do c o n j u n t o de u n ida de s
d i s po n ív e i s E m r e s u m o
, 
a u n id a de 2 e s t a r á a l o c a da pa r a do i s p r o c e s s o s a o m e s m o t e m po e
e s t a r ão d i s po n fv e i s a s u n i d a de s 3
, 
1 e 5 (a u n ida de 4 s u m iu do s i s t e m a )
O r e s u l ta do c o r r e to da e x e c u ção d a s o pe r a çõe s " l ib e r a (5) II r e qu i s i ta (K y ' po de r i a se r
q u a l q u e r u m do s d o i s s e g u i n t e s
T = 3 T = 3
N o p r i m e i r o c a s o te r i a s i d o a l o c a d a a u n i d a d e K = 5
, 
f i c a n do d i s p o n ív e i s a s u n i da d e s 3 , 1
e 4 N o s e gu n d o c a s o t e h a s i d o a l o c a d a a u n id a de K - 4
, 
f i c a n do d i s p o n í v e i s a s u n i da de s 3 , 1 e 5
E s t e e x e m p l o i l u s t r a o c o n c e i t o de c o n di ção d e c o r r ida (r a c e c o n d i t io n s e ção 2 2 ) ,
PO i s o r e s u l t a d o d a e x e c u ção é f u n ção d a s v e l o c i d a de s r e l a t i v a s d o s p r o c e s s o s (o u d a o r de m c o m
q u e o s p r o c e s s o s a c e s s a m o s d a do s c o m p a r t i l h a do s ) N a h i s t ó r i a d a c o m p u t a ção e x i s t e m d i v e r s o s
e x e m p l o s d e d e s a s t r e s d e v i d o s a e s s e t ip o d e e r r o O c a s o d a m áq u i n a de r a d i o t e r a p i a T he r a c 2 5
é u m e x e m p l o c l ás s i c o [L E V 9 3 ] U m a c o n d ição de c o r r i da f a z i a c o m q u e , às v e z e s , e s s a
m áq u i n a a d m i n i s t r a s s e d o s a ge n s m i l ha r e s de v e z e s m a i o r q u e a n o r m a l , r e s u l t a n d o n a m o r t e o u
e m s ér i o s d a n o s p a r a o s p a c i e n t e s
0 c o n c e i t o d e r e g i ã o c r : t i c a
O s t r e c ho s d o s p r o c e s s o s o n d e o s d a d o s c o m p a r t i l ha do s s ão a c e s s a d o s s ão d e n o m i n a d o s t r e c ì1o s
c r í t i c o s
, 
r e g i ô e s c r h i c a s o u s e ç ô e s c r h i c a s A m a n e i r a d e e l i m in a r a s c o n di çMe s d e c o r r i d a d e u m
p r o g r a m a c o n c o r r e n t e é s i m p l e s b a s t a g a r a n t i r a e x c l u s ão m ú t u a n a e x e c u ção d o s tr e c h o s
c r f t i c o s d o s p r o c e s s o s A s e g u i r s e r ão a p r e s e n t a d o s a l g o D t m o s q u e i m p l e m e n t a m e x c l u s îio m ú t u a
n a e x e c u ção d e r e g i õ e s c r f t i c a s de s i s te m a s c o n c o r r e n t e s
4
. 
2 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
O s a l g o D t m o s a p r e s e n t a do s a s e g u i r s ão v ál ido s pa r a o c a s o de 2 p r o c e s s o s So l u çMe s pa r a n
p r o c e s s o s s ão a p r e s e n ta d a s n a s e ção 4 3 A lg u n s do s a lgo r i t m o s a p r e s e n t a m e r r o s , o s q u a i s s äo
d e v i da m e n te a p o n t a d o s T a n t o f a z c o n s ide r a r o s p r o c e s s o s s e n do e x e c u ta do s po r u m ún ic o
p r o c e s s a d o r (e x e c u ção l o g i c a m e n te p a r a l e l a ) o u c o n s ide r a r c a da p r o c e s s o e x e c u ta do po r u m
p r o c e s s ad o r p r óp r i o (e x e c u çao fi s ic a m e n te pa r a le l a ) : s e h !i a lgu m p r o b le 1n a c o m o a lg o r i tm o ,
e s s e p r o b le m a s e m a n i f e s t a e m a m b o s o s c a s o s
Su pö e s e q u e o s pr a c e s s o s s e j a m c íc l l c o s , is t o , qu e e le s e n t r e m e s a i a m v ár i a s v e z e s
de s u a s s e çõe s c r f t i c a s T o d a s a s s o l u çö e s u s a m a téc n ic a de b rBsy l o o p 2
9 (o u bu sy w a i t ) pa r a f a z e r
29 U m bu s y l o o p u m a r i t u a ç=o n a qu a l u m pr o c e s s o f ic a u t i l iz a n do o pr o c e s sad o r de f o r m a c o n t fn u a (t e s t a n do u m a
c o n d içäo ) , s e m r e a l i z a r u a b a l ho ú t i l
Scanned by CamScanner
44 s i s t e m a s o pe r a c io n a i s c p r o - C o n c o
r r e n t e S S T o s c a n i , R S d e O l i v e i r a e A Si mi
u m p r o c e s s o e s pe r a r pe lo o u t r c» S o u t
i l i z a da s v a r ld v e is g lo ba is (c o m p a r t i l h a da s ) pa r a de c idi , i e
é po s s fv e l e n t r a r n a r e g i o c r í t ic a o u n o , 
e
, 
e m t o d a s o l u ção , a m b o s o s p r o c e s so s e x ec u 1am o
m e s m o c ód ig o (o u p r o to c o l o de a c e s s o ) 
o s a l go r i t m o s s ão e s p e c i f i c a do s u t i l i z a n
do a l in gu a ge m V a l e 4 N e s s a l in gu agm o
s :m b o l o ' " 1 " r e p r e s e n t a o o pe r a do r l óg i c o 
' h o t " (n a v e r da de , o c o m p i l a d o r a c e i ta a m bas al
r e p r e s e n t a çõe s 
"
.
"
e 
' h o e ' )
4 2 1 C i n c o t e n t a t i v a s d e s o l u ção
T o d a s a s c i n c o t e n t a t i v a s d e s o l u ção de s t a s e ção a p r e s e n t a m a l g u m 
t i po de e r r o C o m o o er r o é
a p o n t a d o n o p a r ág r a fo qu e s e gu e à a p r e s e n t a ção do a lg o
D t m o
, 
é a c o n s e l háv e l qu e o l e i to r te n te
e n c o n t r a r o e r r o a n t e s de l e r e s s e p a r ág r a f o E s t e s a l go r i t m o s f o r a m o r
i g i n a l m e n t e a p r e s e n tado s
n o a r t i g o c l ás s i c o d e D ij k s 【r a [D U 65 a ] 
T e n t a t i v a 1
V a r i á v e l g l o ba l e m u s o : b o o l e a n i n i t i a l f a l s e
A v a r i áv e l g l o b a l i n d i c a s e a l g u m a r e g i ão c r í t i c a e s t á e m u s o o u n i o
C ód i g o d e u m p r o c e s s o
l o o p
e x i t w he n r ¬ m u s o
e n d l o o p
e m u s o = t r u e
R E G IÃO C R ÍT IC A
e m u s o = f a l s e
A s o l u ção n ão é c o r r e t a , po i s o s p r o c e s s o s po de m c he ga r à c o n c l u s ão
"
s i m u l ta n e a m e
n te 
'
q u e a e n t r a da e s t á l i v r e (e m u s o = f a l se ) I s t o é , o s do i s p r o c e s s o s po de m l e r (te s ta
r ) o v alo r de
e m u s o a n t e s q u e e s s a v a r i áv e l s e ja fe i t a igu a l a 1r u e po r u m de l e s
p a r a o s p r ö x i m o s a lgo r i t m o s , s u p i$e s e qu e o s p r o c e s s o s te n ha m du a s v a r i áv e
i s l o c a is , e u e 
QB¢l l o
Pa r a o p r o c e s s o 1, e u = l e o u t r o = 2 ; pa r a o p r o c e s s o 2 , ¬ u - 2 e o u l r o a 1
o s c ód igo s do s p
ro ces
s o s
s ão igu a i s , - c a da p r o c e s s o u s a s u a s v a Dáv e i s pr i v a t i v a s e u e o u t r o
i
Scanned by CamScanner
-
4 0 Pr o b l e m a d a E x c lu süo M ú tu a 4 5
T e n t a t i v a 2
Va n Eáv e l g fo b a l v e z : i n te ge r i n i t i a l l
E s t a v a r i áv e l in d i c a d e q u e m é a v e z
, 
n a ho r a de e n t r a r n a r e g i ão c r í t ic a
Cód ig o d e u m p r o c e s s o
l o o p
e x i t w he n v e z = g u
e n d l o o p
R E G I Ã O C R ÍT I C A
v e z = ou t r o
E s t e a l g o D t m o g a r a n t e excl usî o m ú t u a , m a s o b r i g a a al t er nânci a n a e x e c u ç ão d a s r e g i õ e s
c D t i c a s (i s t o é
, p D m e i r o e n tr a P 1 , d e p o i s P2 , d e p o i s P l , e tc ) N ão é p o s s ív e l u m m e s m o p r o c e s s o
e n t r a r d u a s v e z e s c o n s e c u t i v a m e n t e Se P2 de s e j a r e n t r a r p r i m e i r o n a s u a r e g i ão c r í t i c a , e l e n ão
p o d e r á f a z ê l o , p o i s p 1 d e v e s e r o p r i m e i r o Se u m p r o c e s s o te r m i n a r , o o u t r o n ão p o
d e r á m a i s
e n t r a r n a s u a r e g i ão c r i t i c a N ão é a c e i táv e l q u e u m p r o c e s s o t r a n q u e a e n t r a d a d e o u tr o s e m
n e c e s s id a d e
T e n t a t i v a 3
Va r i á v e l g l o ba l q u e r a r r a y [2 ] o f bo o l e a n i n i t i a l f a l s e
S e q u e r t i ] é t r u e , i s t o i n d i c a q u e o p r o c e s s o & (IE { 1, 2 }) q u e r e n t r a r n a s u a r e g ião c r í t i c a
O b s e r v e q u e o v a l o r i n i c i a l e s p e c i f i c a do pa r a u
m a r r a y (v e t o r o u m a t r i z ) s e a p l i c a a t o d o s o s
e l e m e n t o s d e s s e a r r a y E s t a c o n v e n ção é a do t a
da n a l in gu a ge m V 4
C ód i g o d e u m p r o c e s s o
lo o p
e x i t w he n - qu e r to u t r o ]
e n d l o o p
q u e r te u ] : - t r u e
R EG I ÃO C R IT I C A
q u e r te u ] : e f a l s e
A s o l u ção n ão a s s e g u r a e x c l u s o m k t u a R e pe t e s e a qu i o m e s m o p r o b le m a d a te n t a t i v a
1
, po i s c a d a p r o c e s s o po d e c he g a r à c o n c lu s ão qu e o o u t r o n
ão qu e r e n t r a r e a s s i m e n t r a r e m
Scanned by CamScanner
4 6 s i s te m a s Ope r a c io n a i s e p r o s r eñ C o n c o n e n te S S T o s c a n i , R S d e O l i v e i r a 으九 S ml
s i m u l t a n e a m e n t e n a regi i o c r f t i c a Is s o a c o n te c e po r qu e e x i s te a po s s ib i l ida de de c ada pr oc e sr o
t e s t a r s e o o u t r o n o q u e r e n t r a r a n te s de u m de l e s m a r c a r a s u a i n t e n ção de e n t r a r
O pr óx i m o a lg o r i t m o (t e n ta t i v a 4 ) s o l u c i o n a e s s e p r o b l e m a f i tz e n do c o m qu e c ada
p r o c e s s o m a r q u e s u a i n te n ção de e n t r a r an te s de t e s t a r a i n te n ção do o u t r o
O B SE R V A ÇÃO I M PO RT A N T E
Se c a d a p r o c e s s o m a r c a s u a i n t e n ção de e n t r a r a n t e s de t e s t a r a in te n ção do o u t r o , m t in
c e r t a m e n t e
, 
s e u m p r o c e s s o c he g a à c o n c l u s ão q u e o o u t r o n ão q u e r e n t r a r é p o r qu e e s se m t r o
a i n d a n ão t e s t o u a i n t e n ção do p r i m e i r o (po i s o te s t e é r e a l i z a do d e p o i s de m a r c a r a in te n ção de
e n t r a r ) Po r t a n t o
, qu a n d o e s s e o u t r o p r o c e s s o f o r r e a l i z a r o t e s t e , c e r t a m e n t e , i r á e n c o n tr a r a
i n d i c a ção q u e o p a r c e i r o q u e r e n t r a r I s to i m p o s s i b i l i t a q u e o s d o i s p r o c e s s o s c he gu em
"
s i m u l t a n e a m e n t e " a c o n c l u s ão q u e o o u t r o n ão q u e r e n tr a r
T e n t a t i v a 4
V a r i á v e l g l o b a l q u e r a r r a y [2 ] o f b o o l e a n i n i t i a l f a l s e
É o m e s m o a l g o D t m o a n t e Do r , po r ém m a r c a n d o a i n t e n ção de e n t r a r , a n t e s d e t e s t a r a i n te n ção
d o o u t r o p r o c e s s o
C ód ig o d e u m p r o c e s s o
q u e r te u ] = t r u e
lo o p
e x i t w he n 1 q u e r to u t r o ]
e n d l o o p
R E G IÃO C R 9T IC A
q u e r te u ] : = f a l s e
C o m e s t e a lg o r i t m o a e x c l u s ão m ú t u a é g a r a n t i da
, 
m a s
, 
i n fe l i z m e n t e
, 
o s p r o c e ssas 
m
e n t r a r e m u m lo o p et er no I s t o po r qu e a m b o s o s p r o c e s s o s po de m m a r c a r
"
s i m u l t an e a+n en
te B
i n t e n ção de e n t r a r (a n te s qu e u m de le s c o n s ig a te s t a r , d e n t r o d o l o o p . s e o o u t r o qu e r en tr
ar ou
n ao ) N e s s e c a s o , de po i s d e e n t r a r e m n o lo o p , o s p r o c e s s o s n üo v ao s a i r m a is de lá
O p r ó x i m o a l g o r i t m o m e l ho r a e s t a t e n t a t i v a d e s o lu çao , po i s , de n t r o do l o o p , 
o pro c ess 
o
v e Df 1c a s e o o u t r o t a m bém q u e r e n t r a r e , e m c a s o a f i r m a t i v o
. 
Di a v e z pa r a o p a r ce i r o
Scanned by CamScanner
C a p ftu l o 4 0 Pr o b l e m a d a E x c l u s ao M ú tu a 47
T e n t a t i v a 5
Va r i áp e l g t o ba l q u e r a r r a y [2 ] o f b o o 1e a n i n i t i a l f a l s e
É s e m e l ha n t e a o a l g o D t m o a n t e r i o r
, p o r ém o p r o c e s s o dá a v e z p a r a o o u t r o n o c a s o d o o u t r o
qu e r e r e n t r a r
Cód i g o d e u m p r o c e s s o
i n fc i o q u e r [e u ] : = tr u e
i f q u e r to u t r o ] th e n
q u e r te u ] : - f a l s e
go t o in i c i o
R E G I O C R ÍT I C A
q u e r te u ] : = f a l s e
A e x c l u s ão m ú t u a c o n t i n u a g a r a n t i d a , m a s p o d e a c o n t e c e r d o s p r o c e s s o s f i c a r e m d a n d o a
v e z u m p a r a o o u t r o i n d e f i n i d a m e n te E m b o r a e s s a
"
s i n c r o n i z a ção " d o s p r o c e s s o s s e j a d i & c i l d e
a c o n t e c e r n a p r á t i c a , e l a n ão d e i x a d e s e r t e o r i c a m e n t e po s s í v e l
O a l go D t m o s e g u i n t e s o l u c i o n a de ' n i t i v a m e n t e o p r o b l e m a , u s a n d o u m a v a r i áv e l
a d i c i o n a l v e z p a r a r e s o l v e r a s s i tu a çõ e s d e e m p a te E s t a v a r i áv e l s ó é u s a d a q u a n d o o s d o i s
p r o c e s s o s q u e r e m e n t r a r s i m u l t a n e a m e n t e n a s r e g
i õ e s c r í t i c a s
4
. 
2
. 
2 So l u ção d e D e k k e r
Va r v e i s g l o ba i s q u e r a r r a y [2 ] o f b o o l e a n i n i t i a l f a l s e
v e z i n te g e r i n i t i a i 1
Es t a s o l u ção fo i p r o p o s t a pe l o m a te m
át i c o ho l a n dês T D e k k e r e d i s c u t id a po r D i jk s t r a
[D U 65 a ] T r a t a s e d a p r i m e i r a s o l u ç o c o m ple t a pa r a o p r o b le m a C o n f o r m e j i l r e fc Dda é
s i m i l a r a o a lg o D t m o a n t e r i o r A d i f e r e n qa e s
tá n o u s o d a v a r i £iv e l v e z , p a r a r e a l i z a r o de s e m pa t e
(t i e b r e a k) N o c a s o e m q u e o s do i s p r o c e s s o s e n t r a m n o b l o c o e n t r e c ha v e s . só u m 
de le s
(de c i d id o pe l o v a l o r d a v a r i áv e l v e z ) dá a v e z pa r a o o u t r o
C ód i g o d e u m p r o c e s s o
i n i c i o q u e r [e u ] : = t r u e
d e n o v o i f q u e r [o u t r o ] the n
i f v e z = g u the n go t o de n o v o
q u e r te u ] : = f a l s e
) ;
Scanned by CamScanner
4 8 Si s t e m a s O pe r a c i o n a i s e .im 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 l i r a e 
m j
lo o p
e x i t w he n v ¬ z = e u
e n dl o o p
go t o i n i c io
R EG IÃO C R FT ICA
q u e r te u ] : = f a l s e
v e z =o u t r o
0 a l g o D t m o s a t i s f a z t o d a s a s e x i gên c i a s p a r a a s o l u ç ão s e r c o n s i de r a d a c o r r e t a , qu a i squ e r
q u e s e j a m a s v e l o c i da d e s r e l a t i v a s d o s p r o c e s s o s Po r e x e m p l o , n ão a c o n t e c e de u m pr o c e sso
f i c a r et er nament e t e n t a n do e n t r a r n a s u a r e g i ão c r i t i c a e n qu a n t o o o u t r o , m a i s v e l o z , e n t r a e sai
r e p e t i d a m e n t e d a s u a r e g i ão c r í t i c a
4 2 3 So l u çã o d e P e t e r s o n
0 a l g o D t m o a n t e D o r f o i a p r e s e n t a d o p o r D e k k e r n a déc a d a d e 60 N a d éc a d a d e 80
, 
G p e t e r s o n
t o m o u m a i s s i m p l e s e s t a s o l u ção [PET 8 1] O a lg o r i t m o d e Pe t e r s o n é a p r e s e n t a d o a s e gu i r e m
d u a s v e r s õ e s q u e d i f e r e m a p e n a s n o s n o m e s d a s v a r iáv e i s u t i l i z a d a s O t r u q u e do a lgo r i tm o
c o n s i s t e n o s e gu i n t e : a o m a r c a r s u a i n t e n ção de e n t r a r
, 
o p r o c e s s o j á i n d i c a (p a r a o c a s o de ha v e r
e m p a t e ) q u e a v e z é do o u t r o
V e r s ão 1
A e x c l u s ão m ú t u a é g a r a n t i d a a t r a v és d o v e t o r q u e r Se há e m p a te , e n t ão é u s a d a a v a r i áv e l v e z ,
q u e d á a v e z p a r a o p f i m e i r o q u e c he g o u
Va r i á v e i s g l o ba i s q u e r a r r a y [2 ] o f bo o le a n i n i t i a l f a l s e
v e z : i n t e ge r
Cód ig o d e u m p r o c e s s o
q u e r te u ] : = t r u e
v e z = o u t r o
lo o p
e x i t w he n n q u e r to u 1r o ] o r v ¢ z = e u
e n d l o o p
R EG IÃO C R IT IC A
q u e r te u ] : - f a l s e
Scanned by CamScanner
ド
- 一
-
4 0 : T o b le m a d a E x c lu s äo M ú t u a 49
V e r s o 2
É o m e s m o a lg o r i t m o a n t e r i o r
, po M m c o m o u t r o s n o m e s de v a f i áv e i s , qu e i r ão f a c i l i t a r o
e n t e n d i m e n t o d a g e n e r a l i z a ção p a r a n p r o c e s s o s , a s e r d i s c u t id a n a se ção 4 3 4 N a
ge n e r a l i z a ção , i n t e r e s s a s ab e r q u a l f o i o ú l t i m o p r o c e s s o q u e c he g o u e n ão o p r i m e i r o N a v e r s ão
a s e gu i r , e m c a s o d e e m pa t e , f i c a t r a n c a do o úl t i m o qu e c he g o u (a n t e s , n e s s e c a s o , e n t r a v a o
p r i m e i r o q u e t i n h a c h e g a do o q u e é e qu i v a l e n te )
V a r i á v e i s g l o ba i s q u e r a m y [2 ] o f b o o l e a n i n i t i a l f a l s "
u l t im o : i n t e ge r
C ód i g o d e u mp r o c e s s o
q u e r [e u ] - t r u e
u l t i m o = e u
l o o p
e x i t w h e n 1 q u e r to u t r o ] o r u l t i m o ¢ e u
e n d l o o p
R E G I Ã O C R ÍT I C A
q u e r [e u ] - f a l s e
4
. 
2
. 
4 So l u çã o c o m i n s t r u çõe s 
¢ ¢t e s t a n d s e r )
O q u e c o m p l i c a o p r o b l e m a d a e x c l u s ão m
út u a é a po s s ib i l i d a d e d e u m p r o c e s s o pe r d e r a U C P
d e po i s d e t e s t a r o v a l o r de u m a v a r
i áv e l g l o b a l , m a s a n te s d e c o n s e gu i r a t r ib u i r n o v o v a l o r à
m e s m a O a l g o r i t m o d a t e n t a t i v a 1 (s e ção 4 2 1) , o m a i s s i m p l e s de to d o s , po d e r i a f u n c i o n a r
c o r r e t a m e n te s e e x i s t i s s e u m a i n s t r u ção c a pa z 
de te s t a r u m a v a r i £iv e l e a t r i b u i r n o v o v a l o r à
m e s m a s e m p o s s i b i l i da de d e i n te r r u pção
N e s te c a s o a s o pe r a çõ e s " t e s t a r e " a tDb u i e s e Da m
r e a l i z a da s d e fo r m a a t ô m i c a o u i n d i v i s ív e l
H o je e m d i a t o do s o s c o m pu ta do r e s po s s u e m i n s t r u çõ e s do t i p o 
" te s t a n d s e t " q u e . E m
u m a ún i c a i n s t r u ç ão de m áq u i n a (s e m p o s s ib i l ida de de i nt errupç[ O ) , te s ta m o v a l o r de u m a
v a r iá v e l e a tDb u e m n o v o v a l o r à m e s m a N o q u e s e g u e , v a m o s s u p o r a e x i s tên c ia d¢ u m a 
f u n ção
b o o l e a n a T S (X ) , q u e e x e c u t a o s e gu i n te c ód ig o , de f o r m a i n d i v i s :v e l
f u n c t i o n 7S(X b o o l e a n ) r et ur ns bo o le a n
TS = X
X = f a l s e
Scanned by CamScanner
5o Si s t e m a s O pe r a c io n a i s e Pr o g r a m a ç1o Co n c o r r e n te S S T o s c a n i , R e o l iv e i r a e S C9呼叫
a lgo D t m o u t i l i z a u n i a v a r i áv e l g l o b a l i sJ r e e pa r a c o n t r o l a r o a c ( s s o à r e g i ão c f i t ic a
A s e g u i r é m o s t r a d a a s o lu ção d o p r o bl e m a d a e x c l u s o m ú t u a u t i l i z a n do a fu n ção Ts O
Va r iá p e l g l o ba l i s e : bo o 1e a n i n i t ia l t r u e
C ód i go d e u m p r o c e s s o
l o o p
e x i t w he n Ts (i s j e e )
e n d l o o p
R E G IÃO C R IT IC A
is J r e e : = t r u e
D e v e s e r o b s e r v a d o q u e e s t a s o lu ção é v ál i d a p a r a q u a l q u e r n k m e r o d e p r o c e s s o s A s so lu ções
a n t e r i o r e s v a l i a m p a r a 2 p r o c e s s o s a pe n a s
4
. 
3 E x c l u s ã o m ú t u a c o m n p r o c e s s o s
A s e g u i r s ão a p r e s e n t a d a s 6 s o l u çõ e s pa r a o p r o b l e m a d a e x c l u s ão m ú t u a e n v o l v e n do m úl t iplos
p r o c e s s o s U m a s o l u ç ão p a r a n p r o c e s s o s é c o r r e t a s e a s s e g u r a o c u m p r i m e n to do s s e gu in tes
r e q u i s i t o s
I ) g a r a n t i a de e x c l u s ão m ú t u a
,
2 ) g a r a n t i a de p r o g r e s s o p a r a o s p r o c e s s o s
,
3) g a r a n t i a de te m p o d e e s pe r a l i m i t a do
O p r i m e i r o r e q u i s i t o é ób v io
, po i s é o o b je t i v o p r in c i p a l da s o l u ç o O se gu n do diz que
s e n ão há p r o c e s s o d e n t r o de r e g ião c r i t i c a e e x i s te m p r o c e s s o s d e s e j a n do e n t r a r , e n tão a pen as os
p r o c e s s o s q u e de s e ja m e n t r a r pa r t i c i pa m n a de c i s ão de q u e m e n t r a e e s s a de c isão nao ¢
po s te rg a d a in de f i n ida m e n te O te r c e i r o r e qu is i t o d i z q u e u m p r o c e s s o q u e de s e j a e n t r a r n a reg
iäo
c r f t i c a n ão de v e e s p e r a r in d e f i n id a m e n te po r s u a v e z ; i s to é
, qu a n do e x i s te a lgu m p
t o cess o
e s pe r a n d o pa r a e n t r a r , d e v e ha v e r u m l i m i te n o n k m e r o de v e z e s qu e o u t r o s pr o c e s so
s en tr am 
o
s a e m d e s u a s r e g iö e s c r f l i c a s
4
. 
3
. 
1 A l go r i t m o d e D ij k s t r a
D ij k s t r a a p r e s e n to u e s te a lg o r i tm o e m 1965 [D U 65b] 
Va r i á v e i s g to ba i s q u e r , de n t r o : a r r a y [n ] o f bo o le a n
v ¬ Z in te g e r
Scanned by CamScanner
Ca pf tu l o 4 0 ó b l e m a da E x c l u s ao M ú t u a 5 1
O s d o i s v e t o r e s s ilo i n i c i a l i z a d o s c o m ß zts e O s e l e m e n t o s qu e r tt】 e d e n l r o [ i ] sao a l t e r a do s
a pe n a s pe l o p r o c e s s o 1, l [ i B A v a r i áv e l v e z a s s u m e v a l o r e s e n t r e 1 e n e s e u v a l o r i n i c i a l é
i n e l e v a n t e C a d a p r o c e s s o u t i l i z a u m a v a Dáv e l l o c a l k
O c o m a n d o " fo r k = l t o n s t k . Ai E n dfo r ' n ão f a z pa r t e da l i n g u a ge m v a le 4 N e l e , a
s ig l a " s t " d e v e s e r e n te n d ida c o m o s u c h i f1a t (t a l u e ) E m s u a e x e c u ção , a v a r i áv e l k v a i a s s u m i r
o s v a l o r e s 1
, 
2
. , 
n
, 
s e n do de i x a d a de fo r a a i te r a ção c o r r e s p o n d e n te a k - i
Cód i g o d o p r o c e s s o i
que r w t r ue
i n i c i o l o o p
dent r oMf al se
i f 1 q u e r 【v e z】 t h e n v e z = i
e x i t w h e n v e z = i
e n d l o o p
deni r ow«r ue
f o r k = 1 t o n s t k # i
i f d e n l r o tk ] t h e n g o t o i n i c i o
e n d f o r
R E G IÃ O C R ÍT I C A
q u e r w f al se
dent r oMf al se
U m p r o c e s s o i s ó e n t r a n a r e g i ão c r i t i c a s e a pó s f a z e r o s e u d e n t r o [ i ] i g u a l a t r u e e le
e n c o n t r a t o d o s o s d e m a i s p r o c e s s o s c o m
" d e n t r o s " ig u a i s a j a ts e I s t o g a r a n t e e x c l u s ão m ú t u a
O r e q u i s i t o d e p r o g r e s s o é g a r a n t i d o pe la s e gu in t e p r o p r i e d a de : a pós u m p r o c e s s o i
r v e z = i
, 
n e n h u m o u t r o c o n s e g u i r á a tDbu i r s e u n úm e r o à v e z a n te s d a r e g i ão c r f t i c a s e r
e x e c u t a d a E x p l i c a n d o m e l ho r s e o pr o c e s s o v e z n
ão e s t á e n t r e o s qu e de s e ja m e n t ra r , e n tao o s
q u e de s e ja m e n t r a r v ão f a z e r v e z : = " e u " : a pós to da s a s a t r i bu i çõ e s à v a r i áv e l v ¬ z s e r e m n ea l i z a dw
e s s a v a r i áv e l v a i i n di c a r u m d o s p r o c e s s o s q u e de s e ja e n t r a r e e s s e v a l o r n ilo v a i s e r m a i s
a l te r a do T o do s o s p r o c e s s o s q u e d e s e ja v a m e n t r a r , c o m e x c e çao daqu e le i n d ic a do po r v e z , v äo
f a z e r s e u s " de n t r o s " i 吕 u a i s a j h ts e e fi c a r ão r e pe t i n do o c o m a n do lo o p
O r e q u i s i to
"
e s pe r a l i m i t a d a
"
n &o ga r a n t ido , po is , te o Dc a m e n te . u m p r o c e s s o po de
f i c a r i n de f i n id a m e n t e te n t a n do e n t r a r n a s u a r e g i o c r f t ic a , e n qu a n to o s o u t r o s e n t r a m ¢ s a e m
(c «m v e n ç a s e d i s s o ) 
Scanned by CamScanner
52 s i s t e m a s o pe r a c i o n a
i s e p r o g r a m a ç=o Co n -
S S T o s c a n i
, 
R s de o l i v e i r a e A s c t ìt 1ink
4 3 2 A l g o r l t ï n o d e E is e n b e r g 
e M c G u i r e
Es t e a l go Dt m o fo i pu b l ic a do e m 
1972 lE IS 72 ] 
v a r i d p e i s g l o ba isq u e r , d e n t r o a m y [n ] o f bo o
l e a n
v e z i n t e ge r
O s do i s v e t o r e s s ão in ic i a l i z a do s c o m Ja ls e O s v
a l o r e s de q u e r t i ] e d e n t r o E] são a l ter ados
a pe n a s pe l o p r o c e s s o i , 1 g A v a f i
áv e l v e z a s s u m e v a l o r e s e n t r e 1 e n e s e u v a lo r in ici al 
i r r e l e v a n t e C a d a p r o c e s s o u t i l i z a u m a v a r iáv e
l lo c a l k
Códi g o do p r o c e s s o i
quer w t r ue
in i c io demr o[ i ] =f al se
k = y e z
lo o p
i f - qu e r [k】 t he n k = (k m o d n )+ 1
e l s e k = y e z
e x i t w he n k - i
e n d lo o p
dent r oM t r ue
fo r k = l t o n s t k ¢ i
i f de n t r o tk] t he n go t o in i c i o
e n d fo r
/ * A q u i o p r o c e s s o i j á ga r a n t i u a e x c lu s ão m ú tu a ,
m a s v a i d a r u m a ú l t i m a c ha n c e a o p r o c e s s o v e z
i f v e z ¢ i a n d qu e r tv e z ] the n go to i n i c i o
v e z = i
R EG IÃO C R ÍT IC A
k - (v e z m o d n )+ l
l o o p
e x i t w he n qu e r tk]
k = (k m o d n )+ l
e n dlo o p
v e z = k
q u e r 【t] : e f a ls e
dent r ouþf al se
. 
J
Scanned by CamScanner
C a p f t u l o 4 0 Pr o b l e m a da E x c lu s äo M ú tu a 53
O a l g o D t m o é s i m i l a r a o d e D ij k s t r a
, po r ém c o r r ig i do e m r e l a ção a o p r o ble m a da e spe r a
山村 t a d a A e x c l u s ão m ú t u a é g a r a n t ida
, 
c o m o a n te s
, 
a t r a v és d o v e to r de n t r o
A ga r a n t i a de p r o g r e s s o é c o n s e g u i da da s e gu i n t e m a n e i r a o v a lo r de v e z é a l t e r ad o
a pe n a s q u a n do u m p r o c e s s o e n t r a n a regi \ o c r í t ic a (e
, 
m a i s ca r de
, qu a n do s a i ) : e n t ão , se n e n hu m
p r o c e s s o e s t á e n t r a n do o u s a i n do de s u a r e g i ão c r f t i c o v a l o r de v e z p e r m a n e c e c o n s ta n te
d e n t r e o s p r o c e s s o s qu e d e s e j a m e n t r a r
, 
o pD m e i r o n a o r d e n a ção c íc l i c a v e z , v e z + l . , n , 1. 2 . ,
v e z 1 é o q u e v a i c o n s e gu i r
A e s p e r a 山村 t a da é g a r a n t i da po r qu e q u a n do u m p r o c e s s o de i x a a s u a r e g ião c r i t i c a e l e
d e s i g n a c o m o s e u ú n i c o s u c e s s o r o pD m e i r o p r o c e s s o , de n t r e o s qu e d e s e j a m e n t r a r , n a o r de m
c íc l i c a v e z + l
. , 
n
, 
1
, 
2
. , 
v e z 1
, 
v e z ; i s to g a r a n t e q u e qu a l qu e r p r o c e s s o de s ej a n do e r 1tr a r
e s p e r e n o m áx i m o n 1 p r o c e s s o s e n t r a r a n t e s de l e C o n v ém o b s e r v a r q u e , s e n e n h u m p r o c e s s o
d e s e j a e n t r a r n a s u a r e g i ão c r i t i c a , o p r o c e s s o q u e s a i d a r e g i ão c D t i c a f a z v e z ig u a l a o s e u
p r ó p r i o n ú m e r o
P o r m o t i v o s d i dát i c o s
, 
o a lg o r i t m o a c i m a u s o u o s m e s m o s n o m e s d e v a r i áv e i s u s a d o s
pe l o a lg o r i t m o d e D ij k s t r a I s t o f a c i l i t a o s e u a te n d i m e n t o e d e i x a c l a r o o r e l a c i o n a m e n t o
e x i s t e n t e e n t r e o s d o i s a lg o D t m o s O a l g o r i t m o o r i g i n a l d e E i s e n b e r8 e M c G u i r e [E ïS 7 2 ] p o d e
s e r e n c o n t r a do n a m a i o D a d o s l i v r o s d e p r o g r a m a ção c o n c o r r e n t e e s i s t e m a s o p e r a c i o n a i s
4 3 3 A l g o r i t m o d e L a m p o r t
E s t e al gor i t mo é i n s p i r a d o n a t éc n i c a d e e s c a l o n a m e n t o c o m u m e n te u s a d a e m fe r r a ge n s , o n d e
c a d a c l i e n te q u e c he g a r e c e b e u m t i c k e t d e a t e n d i m e n t o O r i g i n a l m e n t e , o a l g o D t m o f o i
de s e n v o l v id o p a r a u m a m b i e n t e d i s t r i b u ído [L A M 74 ] 
D i f e r e n te m e n t e d o qu e a c o n t e c e n o c o m ér c i o , p o de a c o n te c e r d e do i s o u m a i s p r o c e s s o s
r e c e be r e m o m e s m o t i c k e t N o c a s o de e m p a t e , o p r o c e s s o de m e n o r ide n t i f ic a ç o (o m a i s v e l ho )
é a t e n d id o p r i m e i r o , i s t o é , s e P i e p j r e c e b e m o m e s m o t i c k e t e i< j e n t ão P i é a te n di do e m
pDm e i r o l u g a r
.
Va r iá v e i s g l o ba h p e g a n d o a r r a y [n ] o f bo o le a n
t i c ke t a m 1y [n ] o f in te ge r
O s v e t o r e s s ão i n i c i a l i z a do s c o m Ta ts e e z e r o , r e s pe c t i v a m e n te U t i l i z a s e a s e g u in t e
n o t a ç ão
 ( a,
 b) < (c, d) s i gn i fi ca que a< c ou , s e a= c , e n t i 1o b<d : e
, ' : ï ,
 ma x ( a>
 a2 . . A n ) 
 o
 me n o r nú me r o k tal que ka i pa r a l = l . . n ?
<'
.
-
f
Scanned by CamScanner
54 Si s t e m a s
-
o n a i s e Pr o g r a m a ç o C o n c o r r e n te S S T o s c a n i , R S d e O l i v e i r a e A
l Il i
'
Cód ig o d o p r o c e s s o i
Pe g a n d o w t r ue
ü c k e 1 w m a x w c ke a 1 
, 
ü c ke l w
. , 
ü c ke n D l
p e g a n d o w f al se
:o r j = \ t o n s t j + i
l o o p
e x i t w he n - p e g a n do [ì]
e n d l o o p
lo o p
e x i t w he n l i c ke l u] = 0 o r (t i c k e t t i ]
, 
i k (t i c ke l (ìJD
e n d lo o p
e n d f o r
R EG IÃ O C R ÍT I C A
ü c k e t w O
A n te s d e e n t r a r n a r e g i ão c r í t i c a
, 
o pr o c e s s o i c o m p a r a o s e u t i c k e t c o m o t i c k e t de c a da o u t r o
p r o c e s s o j e s s a c o m p a r a ção é fe i t a s ó a pó s i a dq u i l i r a c e r t e z a (n o p r i m e i r o l o o p t q u e o u ( l ) j j á
p e g o u o s e u t i c k e t ( i é
, j á fo i a t r ib u i d o u m v a l o r à l i c k e t 【ì】)
, 
o u (2) j a i n d a n ão i n i c i o u o p r o c e ss o
d e r e t i r a r u m t ic k e t (e n e s s e c a s o c e r t a m e n te j i r á pe g a r u m t i c k e t m a i o r q u e t ic ke 1ti ]) No
p r i m e i r o c a s o p o d e s e t e r q u a l q u e r r e l a ção e n t r e 1i c ke t [ i ] e t i c k e l 【ì ] (m a i o r
, 
m e n o r o u i gu a l ), m a s
c e r t a r n e n te o p a r (t i c k e l Ed】, i d) de u m d o s p r o c e s s o s s e f á e s t r i t a m e n t e m e n o r q u e o p a r do o u t r o
N e s s e c a s o
, 
o p r o c e s s o c o m o m a i o r p a r f i c a r á r e t i do n o s e g u n do l o o p a t é q u e o o u tr o e n t r e e s ai a
d a s u a r e g i ão c r í t i c a , g a r a n t i n do a e x c l u s ão m ú t u a Pa r a m o s t r a r qu e o " p r o g r e s s o " e a " e spe r a
l i m i t a d a " s ão g a r a n t ido s e q u e o a lg o r i t m o é j u s to (i s t o é
, 
a te n de i gu a l m e n te a to d o s )
, 
é s u f ic ie n te
, 
j ; å o bs e r v a r q u e o s p r o c e s s o s e n t r a m n a s s u a s r e g iMe s c r i t i c a s n a o r d e m FC FS ( " F i r s t Co m e Fir st
Se r v e d " )
T e o r i c a m e n te
, 
é po s s fv e l qu e m a i s de u m p r o c e s s o e n t r e n a r e g i ão c r i t i c a Is to po de
o c o r r e r q u a n d o o l i m i te de r e p r e s e n t ação de i n te i r o s é u l t r a pa s s a do n o c o m a n d o q u e o btém o
n úm e r o d o t i c k e t
, 
s e n do a t r i bu ído a u m p r o c e s s o u m n úm e r o m e n o r q u e o do pr o cess
oc o r r e n te m e n te n a r e g i ão c r f ti c a
4
. 
3
. 
4 A l go r i t m o d e P e t e r s o n
A g e n e r a l i z a ção de Pe t e r s o n pa r a n p r o c e s s o s [p ET Bl ] e n v o l v e a lg u n s n o v o s e le m e n to s em
r e l a ção à s o l u ção p a r a 2 p r o c e s s o s A idéi a b s ic a é qu e c a d a p r o c e s s o de v e pa s s a r po
r IB 1
e s t ág io s a n te s de po de r e n t r a r n a s u a r e g i o c M i c a U m p r o c e s s o a v a n ça u m e s tág i o s e m pr
e que
(a ) e l e est i n a f r e n te de to do s o s de m a i s (n i n g u ém e s t á e m u m e s t ág io m a io r o u ig u a l a o de le ) o
u
i l
Scanned by CamScanner
-
4 0 Pr o b le m a d a E x c l u s ão M ú tu a 55
c he g a o u t r o p r o c e s s o n o e s t ág i o e m q u e e l e e s t ü (e le de i x a de s e r o ú l t i m o n o s e u e s tág io
a m N
Vta r iu v e is g l o b a i s e s t a g i o : a r r a y [n ] o f i n t e ge r i n i t i a l 0
u t t i m o : a m y t n 1] o f i n te ge r
N o v e t o r e s t a g i o , o e l e m e n t o e s t a g io [ i ] , 1 [ i , i n d i c a o e s t ág i o a tu a l do p r o c e s s o i Po r t a n t o ,
c a d a e l e m e n t o c o r r e s p o n d e a u m p r o c e s s o (i n ic i a l m e n te
, 
t o d o s o s e l e m e n t o s e s tão z e r a d o s ) N o
v e t o r u l t i m o
, 
o e l e m e n t o u l l in 1o [ì] , l i an 1, i n d i c a q u a l é o ú l t i m o p r o c e s s o q u e c he go u a o
e s t ág i o j , p o r t a n t o c a d a e le m e n t o c o r r e s p o n d e a u m e s t ág i o
Cód i g o d o p r o c e s s o i
f o r j - 1 t o n 1 / * p e r c o r r e o s n l e s tág i o s * /
e s l a g i o [ i ] : = ì ; / * e s t ág i o a tu a l d e i * /
u h i m o [i ] : - i ; / * o ú l t i m o s o u e u » /
f o r k = l t o n s t k + i
l o o p
e x i t w h e n e s t a g i o [ i ]> e s ta g i o [k ] o r u h im o [ì] * i
e n d l o o p
e n d f o r
e n d f o r
R E G I Ã O C R ÍT I C A
e s ra g i o w O
E m c a d a e s tág i o o p r o c e s s o s e c o m p a r a c o m t o
d o s o s d e m a i s O p Fo c e s s o d e c i d e s e a v a n ç a
n e s s a s c o m p a r a çMe s a t r a v és do a l g o D t m o de 
2 p r o c e s s o s , m a s c o m u m a i n t e r p r e t a ção u m p o u c o
d i f e r e n t e A q u i o p r o c e s s o a v a n ç a q u a n d o e
le e s t á n u m e s t ág i o m a i s a d i a n t a d o (e m r e l a ç ão a o
o u t r o ) o u q u a n do e l e n ão é o úl t i m o n o e s tág io a t u a l Só a pó s t e r s u c e s s o n a c o m p a r a ç o c o m
to d o s o s de m a i s é q u e o p r o c e s s o a v a n ç a u m e s tág
io O c o m po r t a m e n to r e s u l t a n te ë o s e g u in t e o
p r o c e s s o i a v a n ç a u m e s t ág i o s e m p r e q
u e (a ) t o do s o s p r o c e s s o s n a s u a f r e n te s a e m de s u a s
r e g i ö e s c r i t i c a s o u (b ) o u t r o p r o c e s s o e n t r a n o s e u e s tág i o a t u a l (p i de i x a de s e r o úl t i m o )
E n q u a n t o u m p r o c e s s o e s t£i e x e c u t a n do (o u t e n ta n do e n t r a r ) n a r e g i o c r f t ic a . o s
e s t ág i o s f u n c i o n a m c o m o b a r r e i r a s (e m c a d a b a r r e i r a f ic a r e t ido o ú l t im o q u e l i l c he ga ) : o e s t
ágio
de i x a p a s s a r n o m áx i m o n 1 p r o c e s s o s , o e s t tig io 2 de i x a pa s s a r n o m
áx i m o n 2 e o ú l t i m o
d e i x a p a s s a r a pe n a s 1 p r o c e s s o Is t o g a r a n te a e x c l u s ko m ú tu a Pa r a 
s e c o n v e n c e r q u e o s o u t r o s
do i s r e q u i s i t o s t a m bém s ao s a t i s fe i to s b a s t a o b s e r v a r q u e u m p r o c e s s o s e 
b lo q u e i a s o m e n t e s e
a lg u m o u t r o e s t á n a s u a f r e n te ; c o m o u m p r o c e s so n üo f ic a in
de f i n id a m e n te n a s u a r e 吕 i iio c r f t ic a ,
i s t o g a r a n te q u e to do s o s p r o c e s s o s po s s a m a v a n ça r
4 1
Scanned by CamScanner
56 s i s t e m a s ® £e r a c io n a i s e p r o g- C o n c o r r e n te S S T o s c a n i , R S de O l i v e i r a e A S Ca r i s1im i
D e v e s e r o b s e r v a do q u e pa r a e n t r a r n a r e g i o c r : t i c a to do p r o c e s s o e x e c u t a O (n 2) v ez es
o a l g o r i t m o p a r a 2 p r o c e s s o s , m e s m o q u e s ó u m e s te j a de s ej a n do e n t r a r O a l go r i t m o a se gu ir
r e d u z o n ú m e r o de o pe r açõ e s pa r a O (n « n 1) qu a n do a c o m p e t i ção e n v o l v e a pe n a s m do s n
p r o c e s s o s
4 3
. 
5 A l g o r i t m o d e B l o c k e W o o
A s e g u i n t e c o n s t a t a ção p e r m i t e o 山村 z a r o a lg o D t m o de Pe t e r s o n [B L 0 90 ] Se o p r o c e s so e stá
n a f r e n t e d e t o do s o s de m a i s
, 
e n t ão e l e po de e n t r a r d i r e t a m e n te n a r e g i ão c r i t i c a (s e m pa s sa r
p e l o s r e s t a n t e s e s t ág i o s )
V a r iá v e i s g l o b a i s q u e r a r r a y [n ] o f i n t e ge r
u l t i 1n o a r r a y [n ] o f i n t e ge r
C a d a p r o c e s s o p o s s u i u m a v a r i áv e l l o c a l , de n o m i n a d a e s t a g i o , q u e i n d i c a o e s t ág i o a t u a l do
m e s m o O s e l e m e n t o s do v e t o r q u e r a s s u m e m a p e n a s o s v a l o r e s O e 1 0 s o m a tó r i o do s
e l e m e n t o s d e s s e v e t o r (> q u e r ) i n d i c a o n úm e r o de p r o c e s s o s q u e e s t ão t e n t a n d o e n t r a r n a r e g ião
c r f t ic a
C ód i g o d o p r o c e s s o i
e s t a 
 
io = 0
quer M l
r e pe a t
e s 1a g i o : = e s t a g i o + l ; / * e s tág i o a t u a l d e i * /
u b im o [e s l a g i o ] : - i : / * úl t i m o s o u e u + /
l o o p
e x i t w he n u t t in zo [e s t a g i o ]+ i o r e s l a g io - 2 q u e r
e n d l o o p
u n t i l u l l im o [e s 1a g i o ] = i ; / * e s ta g i o - 2 q u e r + /
R EG IÃ O C R IT IC A
q u e r w O
O p r o c ç s s o a v a n ç a u m e s t ág i o (s e m s e c o m p a r a r c o m o s de m a i s ) q u a n do c le de i x a dc sc
r o
ú l t i m o n o s ç u e s tág i o a t u a l M a i s do qu e i s s o
, 
o p r o c e s s o e n t r a d i r e t a m e n te n a re g ião c
r ft ica
q u a n d o s e u e s t ág io ig u a l a o n úm e r o de pr o c e s s o s q u e e s t o te n ta n do e n t r a r n a r eg i o 
c r ft ic a 
I s s o s i gn i f i c a q u e to do s o s d e m a i s p r o c e s s o s e s t o a t r a s a do s e m r e la çüo a e le (le m br e q u e 
c ada
e s t ág i o r e t m u m p r o c e s s o )
; : l%
Scanned by CamScanner
-
o 4 0 Pr o b l e m a d a E x c lu s ao M ú t u a 57
C o n s i d e r a n do q u e m p r o c e s s o s e s t ão c o m pe t i n do , a c o m p l e x id a de do a l g o r i t m o é
0 (n * m ) v i s t o q u e s ão p e r c o r r i d o s a pe n a s m e s t ág i o s e , e m c a d a e s t ág io , s lio v e r i f i c a do s o s
v a l o r e s d o s n e l e m e n t o s d o v e t o r q u e r
4 3
. 
6 A l g o r i t m o d e T o s c a n i
N e s t a s o l u ção , u m p r o c e s s o e x e c u t a n 1 v e z e s o a l go r i t m o de 2 p r o c e s s o s a n t e s d e e n t f a r n a
r e g i ão c r í t i c a T r a t a s e d e u m a g e n e r a l i z a ção n a t u r a l , p o i s n ão i n t r o d u z n o v o s e l e m e nt o s n a
s o l u ção o Dg i n a l d e 2 p r o c e s s o s N a r e a l ida de
, 
o m e s m o m ét o d o p o d e s e r u s a d o p a r a ge n e f a l i z a r
q u a l qu e r s o l u ção d e 2 p r o c e s s o s s e m a c r e s c e n t a r n o v o s e le m e n t o s n a g e n e r a l i z a ção
Va r i á v e i s g l o ba i s q u e r a r r a y [n , n ] o f b o o l e a n i n i t i a l f a l s e
u l t i m o : a r r a y tn , n ] o f i n t e ge r
O a m y q u e r é i n i c i a l i z a d o c o m Jat se e m t o d a s a s s u a s p o s i çõ e s N o a l g o D t m o q u e s e g u e , ü
r e p r e s e n t a m i n ( iD e » r e p r e s e n t a m a x ( i , D 
C ód i g o d o p r o c e s s o i
Eo r j - \ t o n s t j + i
q u e r t i j ] : = t r u e
u l t i m o l i i
, 
j j \ = i
l o o p
e x i t w he n - q u e r tì , i ] o r ul t i mo[ i i ì ] +i
e n d l o o p
e n d f o r
REGI O C R FT IC A
:o r j = 1 \ o n
q u e r [ iA - f a l s e
e n d fo r
N a c o m pe t iç ão d o s p r o c e s s o s i e j , o p r o c e s s o i a v i s a a o p r o c e s s o j qu e qu e r e n t r a r , u s a n do o
e l e m e n t o q u e r t i j ] e , r e c i p r o c a m e n te , o p r o c e s s o j a v i s a o p r o c e s s o l u s a n do o e le m n t o qu e r 【j , 
i )
p a r a o c a s o de e m p a t e n e s s a c o m pe t ição , u s a do o e
le m e n to u 1t im o [i id ] . o n de i i r e p r e s e n t a
m i n ( iD c J / r e p r e s e n t a m a x (tD Po r t a n t o , o a l go r i t m o u s a a pe n a s o t r i an 吕 u lo s u pe
r io r d a m a t r i z
u l t im o
O n ú m e r o d e o pe r a çõe s do a l g o r i t m o é 0 (n ) , po i s u m p r o c e s s o e x e c u t a n 1 v e z e s o
p r o t o c o l o de e n t r a d a n a r e g i ão c r f t i c a pa 】n 2 p r o c e
s s o s A idéi a d a Be n e r a l i z a çüo s i m ple s : c a d a
p r o c e s s o c o m pe te c o m t o d o s o s de m a i s pe
l o " d i r e i t o de e n t r a r n a r e g i o c r í t ic a Pa r a c o m pe t i r ,
Scanned by CamScanner
1
5 8 s i s t e m a s o pe r a c io n a is e Pr ogr a1 C o n c o r r e n te S s T o s c a n i , R S d e O l iy r a e A Si n i
c a d a p a r de p r o c e s s o s < i , j » , c o m i , u s a o a lg o r i t m o de d o i s p r o c e s s o s , c o m v a r iáv e i s ún ic a ¢
e x c l u s i v a s 3o do pa r N e s s a c o m pe t içño é de c i d ido q u e m p r o s s e gu e e q u e m f i c a r e t id o
A p r o v a de qu e o a l g o r i t m o s a t i s f a z a s c o n d içõ e s d e 
" Pr o g r e s s o " e de " e spm I i m i tadan
é d e i x a da c o m o e x e r c íc i o
4
. 
4 E X E R C I C l O S
E x e r c f c i o 4 1 U m e s p e c i a l i s t a e m p r o g r a m a ção c o n c o r r e n t e a p r e s e n t o u a s e g u in t e s o l u ção par a
o p r o b l e m a d a e x c l u s ão m ú t u a e n tr e d o i s p r o c e s s o s
Va r iá v e i s c o m p a r r i l ha d a s q u e r : a m y [2 ] o f bo o l e a n i n i t i a l f a l s e
v e z : i n t e g e r
P r o c e s s o 1 P r o c e s s o 2
q u e r [ 1] = t r u e q u e r [2 ] : = t r u e
l o o p l o o p
e x i t w h e n v e z = l ; e x i t w he n v e z = 2
i f . Qu e r t2 ] th e n v e z : = l i f - q u e r 11] th e n v e z : = 2
e n d l o o p : e n d l o o p
R E G I Ã O C R ÍT I C A ; R E G I O C R ÍT I C A
q u e r t 1 ] : = f a l s e ; q u e r t2 ] : = f a l s e
R e s po n d a ü u s t i f i c a n d o a r e s p o s t a )
(a ) Po d e h a v e r b l o q u e i o et er no d o s do i s p r o c e s s o s ?
(b ) O s do i s p r o c e s s o s p o d e m e s t a r s i m u l t a n e a m e n t e n a r e g i ão c r í t i c a ?
E x e r c í c i o 4 2 (So l u ção de H y m a n [H Y M 66 ] ) Ex p l iq u e s e a s e gu i n t e s o l u ção p a r a 2 pr o c e ssos
s a t i s fa z a s 3 c o n d i çõe s pa r a qu e u m a l g o r i t m o de e x c l u s ão m ú t u a s e ja c o n s i de r a do c o r r e t o
Va r iá v e is g to ba i s q u e r : a r r a y [2 ] o f bo o le a n i n i t i a l f a ls e
v e z : i n te ge r in i t ia l I
Cód i go d e u m p r o c e s s o
q u e r te u ] : = t r u e
l o o p
e x i t w he n v e z = ¬ u
3o M e s m o o s par e l < i , Js e < 1, k > u sa m c o n j u n t o s d i1ju n t o s de v R , i Av e i s
, 
s e þ B
A\ * ì\ ; / B $ ' \ :
= Ä
i ¬
Scanned by CamScanner
-
4 0 P r o b le m a d a E x c l u s ao M 立山 a 59
t i e x i t
 wh en · q u e r t o1 Bl r o ]
e n d l o o p
v e z = e u
e n d l o o p
R EG I O C R 9T I C A
q u e r te u ] : = f a l s e
E x e r c í c i o 4
. 
3 (So l u ç ão d e D o r a n & T ho m a s [D O R 8o ] ) C o m p a r e a s e g u i n t e s o l u ção c o m a
s o l u ç ão d e D e k k e r e d ig a s e e l a é c o n . E t a o u n ão
Có d i go d e u m p r o c e s s o
q u e r te u ] : - t r u e
i f q u e r 【o u l r o ] th e n
i f v e z = o u t r o t he n
q u e r te u ] : = f a l s e
l o o p
e x i t w he n v e z = e u
e n d l o o p
q u e r te u ] : = t r u e
R E G IÃ O C R ÍT I C A
q u e r te u ] : = f a l s e
v e z = o u t r o
E x e r c fc i o 4 4 C o n s id e r a n do o a lg o D t m o de D ij k s t r a , m o s t r e q u e o m e s m o n ão s a t i s f a z o
r eq u i s i t o de e s pe r a l i m i ta d a , i s t o é , m o s t r e qu e u m p
r o c e s s o po de f ic a r in de f in id a m e n te t e n t a n do
e n t r a r n a s u a r e g i ão c r f t i c a e n q u a n to o s o u t r o s e n t r a m e s a e m
E x e r c fc i o 4 5 R e s po n d a s e o a lg o r i t m o de D ij k s t r a pe r m i te qu e s e te n ha u m p r o c e s s o k de n t r o
da r e g ião c r f t i c a e a o m e s m o te m p o s e t e n ha v e z A
lc
E x e r c fc i o 4 6 A s e g u i r a p r e s e n t a d a a s o lu ção o r i g i n a l de Ei s e n be r g e M c G u i r e C o m pa r e a
s o l u ção c o m o a l g o r i t m o a p r e s e n ta d o n o te x t o
Va r id v e i s g l o ba l s ß a g : a m y [n ] o f (o u ir, q u e r , 1n )
v e z i n t e ge r
å$q
Scanned by CamScanner
60 s i s te m a s o pe r a c io ï 1a is - m a ç Co n c o r r e n te
S S T o sc a n i
, 
R S de O l iv e i r a g s 
m i
o s e le m e n to s do v e t o r J1a g s üo i n ic i a l i z a do s c o m o u t O v a l o r de ß a g [ i ] é a l te r a do a pen as pelo
p r o c e s s o i A v a r i áv e l v e z a s s u m e v a l o re s e n t r e 1 e n e s
e u v a lo r i n i c i a l é i r r e l e v a n te Cada
p r o c e s s o u t i l i z a u m a v a r iáv e l l o c a l k
Có dig o do p r o c e s s o i
i ni ci oßagw quer
k = y e z
l o o p
i f ß a g [k] = o u f t he n k - (k m o d n )+ l
e l s e k = v e z
e x i t w he n k - i
e n d l o o p
ß a g w i n
f o r k = l to n s t k # i
i f ß a g [k ] = i n t he n g o to in i c i o
e n d f o r
i f v e z ¢ i a n d ß a g [v e z ]+ o u l t he n go t o in i c i o
v e z = i
R E G IÃ O C R ÍT IC A
k = (v e z m o d n )+ l
l o o p
e x i t w he n ß a g [k ]¢ o u t
k = (k m o d n )+ l
e n d lo o p
v e z = k
ßa g w u ;
E x e r c fc i o 4 7 N o a lgo r i t m o de B lo c k & W o o po r q u e o c o m a n d o r e p e a l t e r m i n a po r
"
u n t i l u l1im o te s 1a g i o ] - i " e n ão po r " u n t i l e s l a g i o = Eq u e r " ?
E x e r c fc i o 4 8 Pr o v e qu e o a lg o r i t m o de T o s c a n i s a t i s f a z a s c o n diçð e s de 1 ' pr o g r esso
e de
"
e s pe r a l i m i t a d a
"
E x e r c fc l o 4 9 U s a n do al i n g u a g e m V 4
, p r o g r a m e o s d i v e r s o s a l go r i t m o s de e x c l u s ao m
otu a e
te s t e o f u n c i o n a m e n t o d o s m e s m o s
} / l
.^ 
@