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

Prévia do material em texto

Scanned by CamScanner
C a p f t u l o 14
D E A D L O C K S
El 1?Bo r e n o
Y s i o t r a o c a s i ó n pa y a m o s
p a r a qu e e s t o s e c o m p le t e
po r m u c h o qu e lo r e s pe t e
c a n t a r e m o s s i l e gu s t a
s o b r e l a s m u e r t e s i n ju s t a s
qu e a l gu n o s h o m b r e s c o m e t e n
Y a qu f pu es s e i ïo r e s m i o s
d i r é c o m o e n d e s pe d id a
qu e t o d a v f a a n d a n c o n v i d a
lo s h e r m a n o s de l d i j u n t o
qu e r e c u e r d a n e s t e a s u n t o
y a qu e l l a m u e r t e n o o l v id a n
Y e s m i s t e r i o t a n pr o ju n do
l o qu e e s t á po r s u c e d e r
qu e n o m e d e b o m e t e r
a e c h a r l a a q u í de a di v i n o
lo qu e de c i da e l de s t in o
d e s pu és lo ha b r án de sa be r
p o de s e d i z e r q u e a s s i t u a çõ e s de ad l o c k e n v o
l v e m a pe n a s do i s t i po s de e n t id a de s : p - s s o s e
r e c u r s o s Qu a lq u e r o u t r a e n t id a de po de s e r a b s t r a :da n o 
e s t u do de s t e p r o b le m a Po r t a n t o , a s
c o n c l u s öe s de i n t e r e s s e po de m s e r o b t id a s a t r a v és 
do e s t u do d e u m m o de lo s i m p l e s , d e s de q u e
e l e pe r m i t a r e p r e s e n t a r a s r e q u i s içö e s e a l o c a ç
ö e s de c a da p r o c e s s o e a d i s po n ib i l id a de de c a d a
r e c u r s o d o s i s te r n a
O s c o n c e i to s e a l g o r i t m o s a p r e s e n t a do s n e
s t e c a p :t u lo v a le m i n d i s t in t a m e n t e pa r a
s i s te m a s c e n t r a l i z a do s o u d i s t Db u fd o s D e s d e q u e s
e j a m c o n he c id a s a s r e q u i s içö e s e a lo c a çõ e s
d o s p r o c e s s o s e a d i s po n i b i l id a d e do s 
r e c u r s o s t a n t o f a z o s i s t e m a s e r c e n t r a
l i z a do o u
Scanned by CamScanner
188 s i s t e m a s O pe r a c i o n a i s e pT o g r a F a g 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 S Ca r i s s i m i
d i s t Db u ído N o c a s o d e u m s i s t e m a d i s t r i b u fd o , a c o
le t a e a m a n u te n ção d e s s e s d a do s é m a i s
d i f i c i l
, 
e v i d e n t e m e n t e
14 1 C o n c e i t o s i n i c i a i s
p a r a e s t u d a r a s p r o p r i e d a d e s de u m s i s t e m a e m r e l a ção a o p r o
b l e m a do s d e a d l o c k s
, 
é p r e c i so
c o n h e c e r 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 p r o c e s s o s e o s r e c u r s o s 
d e s s e s i s t e m a O s p r o c e s so s
p o d e m s e ]. v i s t o s c o m o a s e n t i d a d e s a t i v a s q u e p a s s a m s u
a s v i d a s r e q u i s i t a n d o , u s a n do e
l i b e r a n d o r e c u r s o s O s r e c u r s o s s o a s e n t i d a de s p a s s i v a s , q u e v ão s e r a
l o c a d a s (o c u pa da s )
,
u s a d a s e l i b e r a d a s du r a n te o f u n c i o n a m e n t o do s i s t e m a U m r e c u r s o p o de s e r c a r a c
t e r i z a do c o m o
s e g u e
U m r e c u r s o é q u a l q u e r e n t i d a de q u e p o d e o c a s i o n a r o b l o q u e
i o d e u m p r o c e s s o
O p r o c e s s o s e b l o q u e i a (p a s s a p a r a o e s t a do b l o q u e a d o ) q u a n d o r e q u i s i t a u m
r e c u r s o q u e n ão e s t á d i s p o n í v e l n o m o m e n t o d a r e q u i s iç ão
E x e m p l o s d e r e c u r s o s s ão o s d i s p o s i t i v o s d e E / S o s e s p a ço s d e m e m ó r
i a
, 
o d i r e i t o de
e n t r a r n u m a r e g i ão c D t i c a , o s s i n a i s d e c o m u n i c a ção , a s m e n s a g e n s , e t c D e v e s e r o b s e r v a
do qu e
u m a U C p n ão s a t i s f a z a def +ni çi o a c i m a (p o r t a n t o , n ão é u m r e c u r s o n a t e o r i a d o s d e a d l o c k s) ,
p o i s u m p r o c e s s o q u e e s t á à e s pe r a d a U C P n ão e s t á b l o q u e a
d o
, 
m a s s i m e s t á n o e s t a do r e a dy
N a v e r d a d e , a U C p é u m d i s p o s i t i v o e s p e c i a l qu e n ão é r e q u i s i t a d o e x p l i c i t a m e n t e p
e l o s
p r o c e s s o s e q u e é
" p r e e m p t a d o
"
a c a d a f i m de f a t i a d e t e m po U m p r o c e s s o s ó é c o l o c a d o n a f i la
d e e s p e r a d a U C P (r e a dy l i s t ) q u a n do e l e e s t á de p o s s e d e to d o s o s r e c u r s o s q u e n e c e s s i t a
O e x e m p l o c l ás s i c o d e s i t u a ção de d e a d lo c k e n v o l v e d o i s p r o c e s s o s P r e P2 e do
is
r e c u r s o s R r e R 2 , d a s e g u i n te m a n e i r a
P
, 
: Re q u i s i t a (R r ) ; Re qu i s i t a (R 2) ; I ib e r a (R 1 e R 2) ;
P2 : Re q u i s i t a (R z) ; Re q u i s i t a (R 1) ; I ib e r a (R 1 e R 2) ;
A s i t u a ção d e d e a d l o c k a c o n t e c e s e o s do i s p r o c e s s o s a dqu i r e m o p r i m e i r o r e c m o q
u c
n e c e s s i m N e s te c a s o , c a da p r o c e s so s e b l o q u e i a q u a n do r e q u i s i t a o s e g u n d o r e c u r s o P1 
f ic a à
e s p e r a d e R 2 (po r t a n to , p l f i c a de pe n de n do de p 2) e p 2 f ic a à e s p e r a de R , (de pe n de n do de 
P l ) 
c o m o n e n h u m do s p r o c e s s o s po d e s e r e x e c u t a do (n e n hu m v a i p a r a a r e a dy l is t ) , é i m po ss :v e
l
q u e R , o u R 2 v e n ha a s e r l ib e r a d o Po r t a n t o , e s s a e s pe r a v a i s e p r o l o n g a r p a r a t o do o s e m p
r e 
O té r m i n o d e u m p r o c e s s o p o r c o n d iç o de e r r o s ó o c o r r e q u a n do o p r o c e s s o e
x e c u ta
u m a o pe r a qão i l e g a l o u q u a n d o e le u l t r a p a s s a s e u l i m i t e d e t e m p o de e x e c u ç o S
Ó n e s sa s
c o n d i çõ e s o s i s t e m a o p e r a c i o n a l a bo r t a (m a t a ) u m p r o c e s s o N o e x e m p l o a c i m a , n e m P l n e r
r1 Pz
e x e c u t a m q u a l qu e r o pe r a ç o (v ál id a o u i n v ál id a ) , ta m p o u c o g a s t a m te m p o de U C P Po r t
a n to
Scanned by CamScanner
C a p f tu l o 14 D e a d l o c k s 1 89
e s te s p r o c e s s o s p e r m a n e c e r o i n de f i n id a m e n te o c u p a n d o a m e m ó r i a d o c o m p u t a d o r e o s de m a i s
r e c u r s o s a l o c a d o s a o s m e s m o s
G e n e r a l i z a n do o e x e m p l o a n te D o r t e m se a s e gu i n t e de f i n ição
U m c o n ju n t o d e N p r o c e s s o s e s t á e m de a d lo c k q u a n do c a d a u m do s N p r o c e s s o s
e s t á b l o q u e a do à e s p e r a de u m r e c u r s o qu e s o m e n te p o d e s e r l ibe r a d o p o r u m
d o s p r o c e s s o s d e s s e c o n j u n t o
É i m p o r t a n t e o b s e r v a r qu e v a i h a v e r u m a c a de i a f e c h a d a (c i c l o ) v i n c u l a n d o t o d o s o s N
p r o c e s s o s e m d e a d l o c k
, 
d o s e g u i n t e t ip o p l de p e n d e de p 2 , p 2 de pe n de d e P 3 . , PN I d e pe n d e d e
PN e PN d e pe n d e d e P 1 
14
. 
2 T i p o s d e r e c u r s o s
N o e s t u d o d o s d e a d l o c k s o s r e c u r s o s p o d e m s e r d e d o i s t i p o s : s e r i a tm e n t e r e 1Bs á v e i s e
c o n s u m f v e i s O s p D m e i r o s p o s s u e m v i d a pe r m a n e n t e e o s ú l t i m o s s ão c r i a d o s e co n s u m i d o s
d i n a m i c a m e n t e
14 2 1 R e c u r s o s s e r i a l m e n t e r e u s á v e is
U m r e c u r s o s e r i a tm e n l e r e u s á v e t (o u , s i m p l e s m e n t e , r e c u r s o r e u s á v e t ) é fo r m a d o p o r u m
n úm e r o f i x o d e u n i d a d e s i dên t i c a s , c a d a u n i d a de po de n do s e r u t i l i z a da de f o r m a i n d e pe n de n t e
p o r e x e m p l o , u m d i s c o m a g n ét i c o c u jo e s p a ço s e j a a l o c a d o n a b a s e d e c i l i n d r o s e q u e
te n h a 4 0 0 c i l i n d r o s
, p o d e s e r v i s t o c o m o u m r e c u r s o c o n s t i t u i d o p o r 4 00 u n id a de s Qu a n d o u m
p r o c e s s o r e q u i s i t a e s p a ç o e m d i s c o e l e r e c e be u m a q u a l qu e r d a s 4 00 u n i d a de s e x i s t e n t e s (u m a
q u e e s t i v e r d i s po n í v e l , o b v i a m e n te ) 
O u t r a s c a r a c t e r í s t i c a s de u m r e c u r s o r e u s áv e l s ão ( l ) c a d a u n i da de p o d e s e r a l o c a d a a
a pe n a s u m ún i c o p r o c e s s o de c a da v e z (2 ) a pó s s e r a l o c a d a , a u n ida de s ó p o d e s e r l ibe r a d a
(de v o l v i d a a o c o n j u n t o de u n id a de s d i s po n í v e i s ) pe l o p r óp r i o p r o c e s s o q u e a r e q u i s i t o u ( i s t o é a
u n id a d e n ão po de s e r c o n f i s c a d a p a r a s e r a l o c a d a t e m po r a r
i a m e n t e a o u t r o p r o c e s s o )
A de n o m i n a ção s e r i a l m e n t e r e u s áv e l v e m d o f a t o de u m a u n id a de po
d e r s e r r e u t i l i z a d a
a pó s s e r l i b e r a d a po r u m p r o c e s s o A s s i m , a s u n i d a de s po de m s e r u t
i l i z a d a s po r u n i a s ér i e de
p r o c e s s o s (u m d e c a da v e z ) E m u m de te r m i n a do i n s t a n t e , c a da u n i d a de e s t a r á n r 1 u s o ( i s to ,
a l o c a d a p a r a u m ú n i c o p r o c e s s o ) o u d is p o n tv e l
O u t r o s e x e m p l o s d e r e c u r s o s r e u s áv e i s s ão o s d i s p o s
i t i v o s de E/ S
, 
a m e m óDa p r i n c i pa l
do c o m p u t a d o r , o d i r e i t o d e e n t r a r n u m a r e g iüo c r ft i c a E tc
N o c a s o d a m e 1n ó r i a do c o m p u t a d o r ,
po d e s e t e r d o i s c a s o s Se a m e m ó r i a é d i v id i d a e m N b l o c o s de ig u a l t a m a n h o , t e m s e u m ún ic o
r e c u r s o f o r m a d o p o r N u n i d a d e s d e al ocaçi o N o c a s o d a m e m ó r i a s e r d
i v id id a e m M b l o c o s de
Scanned by CamScanner
190 S i s t e m a s Oci onai s e p r o g r a m a ção Co 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 SSSi mi
t a m a n ho s d i fe r e n t e s
, 
te m s e M r e c u r s o s d i s t i n to s , c a da u m c o m u m a ún ic a u n id a de V a le
o b s e r v a r qu e , s e o s i s t e m a de g e r ên c i a dc m e m ó r i a i m p le m e n t a s w a p p i n g , e n tão a m e m ó Da pa s s a
a s e r p r e e m p t áv e l e de i x a d e s e r u m r e c u r s o , n o s e n t i do q u e é u s a do n a t e o r i a d o s d e a d lo c k r
(d e i x a de s e e n v o l v e r e m de a d to c ks ) 
C o n v ém a i n d a o b s e r v a r qu e u m c o n j u n to de k u n i da de s idên t i c a s po de s e r r e p r e se n tado
de d u a s m a n e i r a s n i 1o e q u i v a l e n t e s : ( 1) c o m o u m ún i c o r e c u r s o c o n s t i t u ído p o r k u n i da de s , o u
(2 ) c o m o k r e c u r s o s d i s t i n t o s
, 
c a d a u m fo r m a d o p o r u m a ú n i c a u n id a de E s ta s du a s
r e p r e s e n t a ç õe s s ão c o m p l e t a m e n t e d i fe r e n te s S e o s r e c u r s o s s ão c o n t r o l a d o s po r s e m áf o r o s , po r
e x e m p l o , n o p r i m e i r o c a s o u s a s e u m s e m áf o r o c o m v a l o r i n i c i a l k , e n o s e g u n do , u s a m s e B
s e m áf o r o s
, 
t o d o s i n i c i a l i z a d o s c o m 1 N o p r i m e i r o c a s o , u m p r o c e s s o r e q u i s i t a q u a l qu e r das
u n i d a d e s e s ó f i c a b l o q u e a d o s e t o d a s j á e s tão a l o c a d a s ; n o s e g u n d o c a s o , o p r o c e s s o r e qu i s i ta
u m a d e t e r m i n a d a u n id a de e f i c a b l o qu e a do s e e s s a u n i d a d e e s p e c í f i c a n ão e s t á d i s p o n ív e l
14 2 2 R e c u r s o s c o n s u m : v e i s
U m r e c u r s o c o n s 1u ?1f v e l é f o r m a do p o r u m n ú m e r o v a r i áv e l d e u n i d a d e s , a s q u a i s s ão c r i a d a s e
c o n s u m i d a s d i n a m i c a m e n t e pe l o s p r o c e s s o s O s p r o c e s s o s q u e p r o d u z e m u n i d a de s s ão
d e n o m i n a d o s p r o d u t o r e s e o s qu e c o n s o m e m s ão de n o m i n a do s c o n s u m ido r e s
O s r e c u r s o s c o n s u m í v e i s s ão c a r a c te r í s t i c o s d o s s i s t e m a s o n d e p r o c e s s o s s e
i n t e r c o m u n i c a m a t r a v s d e m e n s a ge n s o u s i n a i s E m ge r a l , c a d a p r o c e s s o é p r o d u t o r d e a l gu m (s)
r e c u r s o (s ) e c o n s u m i d o r de o u t r o (s ) E x e m p l o s d e r e c u r s o s c o n s u m í v e i s s ão a s v a r i áv e i s
s e m áf o r a s
, 
a s c a i x a s p o s t a i s p a r a t r o c a de m e n s a g e n s , o s s i n a i s d e i n t e r r u p ção p r o d u z i do s pe lo
h a r d w a r e
, 
e t c
U m a v a r i áv e l s e m á fo r a S po de s e r v i s t a c o m o u m r e c u r s o c o n s u m :v e l o n de a o pe r a ç o
de c r i a ção d e u n id a d e é V (S) e a o p e r a ção de c o n s u m o é P (S) N o c a so d e u r n a c a i x a po s ta l , as
o pe r a çõ e s p a r a p r o d u ção e c o n s u m o de u n id a de s si o , r e s pe c t i v a m e n t e
, 
s e n d e r e c e i v e
N o c a s o d e u m a v a r i áv e l t i po c o n di ç o , c o n fo r m e f o i v i s t o n o e s t u d o de moni t or e o
r e c u r s o te m a c a r a c te Ds [ i c a a d i c io n a l de n ão a r m a z e n a r a s u n ida de s p r o d u z ida s a u n idade
p r o d u z id a p o r u m a o p e r a ç iio s íg n a t é c o n s u m i d a i m e d i a t a m e n te (p a r a de s b l o q u e a r u m pr o c e sso
q u e a n te s t i n h a e x e c u t a do u m a o pe r a ção w a i l ) o u E n täo de s a p a r e c e s e m de i x a r v e s t f8 io
V a l e o b s e r v a r q u e é po s s f v e l r e p r e s e n t a r r e c u r s o s r e u s v e i s c o m o r e c u r s o s c o n s u m f v c i s
p o r e x e m p l o , u m r e c u r s o r e u s áv e l c o m k u n ida de s po d e s e r s i m u la d o po r u m a c a i x a po s t
a l
i n i c i a l i z a d a c o m k m e n s a ge n s N e s te c a s o
, 
a o pe r a ç o de r e q u i s içüo s e r i a r e c e i v e e a o pe r a ção 
dc
l i b e r a ção s e r i a s e n d Pa r a o c o n r to fu n c io n a m e n to d o s i s t e m a
, 
a s o pe r a çöe s de c o n su m o 
e
p r o d u ção d e v e r i a m s e r u s a d a s a o s p a r e s , i s to , pa r a c a d a o pe r a ção de c o n s u m o (r e qu i s içäo dc
u n i d a de )
, 
d e v e r i a s e r e x e c u ta da , d e n t r o de u m t e m po f i n i to
, 
u m a c o r r e s po n de n te o pe r a ç o 
de
p r o d u çã o (l ib e r a ção d a u n i d a de a n te r i o r m e n te r e c e b ida )
Scanned by CamScanner
Ca pf t u lo 14 De a d lo c k s 19 1
Se t o d o s o s p r o c e s s o s f o r e m p r o d u t o r e s de to d o s o s r e c u r s o s
, 
e n t ão s ó ha v e r á d e a d l o c k
q u a n do l o d o s o s p r o c e s s o s e s t i v e r e m b l o q u e a d o s , po i s s e pe lo m e n o s u m e s t i v e r n ã o b l o q u e a d o
e s te p o d e p r o d u z i r u n id a d e s s u f i c i e n te s p a r a de s b lo q u e a r t o d o s o s de m a i s p o r t a n t o , s ó f a z
s e n t ido e s tu d a r o p r o b l e m a q u a n d o o c o n j u n t o d e pr o d u t o r e s de c a d a r e c u r s o é u m s u bc o n j u n t o
p r ó pDo d o c o n j u n t o d e p r o c e s s o s d o s i s t e m a
P o r o u t r o l a d o
, p a r a e s t u d a r o p r o b l e m a do s d e a d lo c ks é n e c e s s ár i o c o n he c e r q u e m s ão
o s p r o du t o r e s d e c a d a r e c u r s o c o n s u m í v e l C o n f o r m e r e f e r i do a n t e r i o r m e n te
, 
é n e c e s s ár i o
c o n he c e r o r e l a c i o n a m e n t o c o m p le t o e n t r e o s p r o c e s s o s e o s r e c u r s o s d o s i s t e m a , e a i n f o r m a ç ão
m a i s i m po r t a n t e s o b r e u m r e c u r s o c o n s u m í v e l d i z r e s p e i t o a q u e m p o de l i be r a r (p r o d u z i r )
u n i d a d e s de s s e r e c u r s o
N a s s e çöe s s e gu i n t e s o p r o b le m a do s de a d lo c k s s e r á e s t u d a do c o n s i de r a n do a pe n a s
r e c u r s o s r e u s áv e i s R e c u r s o s c o n s u m f v e i s s e r ão t r a ta do s n a s e ção 14 10
14 3 C o n d i ç õ e s n e c e s s á r i a s p a r a o c o r r ên c i a d e d e a d l o c k
So m e n t e o c o r r e d e a d l o c k n o s s i s t e m a s e m q u e a s s e g u i n t e s t r ês c o n d içõ e s s ão p o s s í v e i s
 q u a n d o um pr oc e s s o qu e já tem um r ec u r s o po d e r eq u i si tar ou t ro r ec l i r so
q u a n do o s r e c u r s o s a l o c a do s a u m p r o c e s s o n ão p o d e m s e r c o n f i s c a d o s (p r e e m p t a d o s )
p a r a s e r e m a l o c a do s te m p o r a r i a m e n t e a o u t r o p r o c e s s o i s t o é , q u a n d o u m r e c u r s o R
a l o c a d o a u m p r o c e s s o p só p o d e s e r l i b e r a d o a t r a v és de u m a o pe r a ç ão ( t i p o
r e l e a s e (R )) e x e c u t a d a pe l o p r óp r i o p r o c e s s o p
q u a n d o é p o s s í v e l a fo r m a ção de u m c i c l o (c a de i a f e c h a d a ) n o qu a l c a d a p r o c e s s o
e s t á b l o q u e a do à e s pe r a d e r e c u r s o s q u e e s t ão a l o c a do s p a r a o u t r o s p r o c e s s o s do
m e s m o c i c l o
Qu a l q u e r da s c o n d içö e s a c i m a q u e s e j a e l i m i n ad a f a z c o m q u e s i t u a çMe s d e d e a d l o c k
n ão p o s s a m o c o r r e r A p r i m e i r a c o n d ição é e l i m i n a d a s e , p a r a c a da p r o c e s s o , t o d o s o s r e c u r s m
n e c e s s ár i o s s ão r e q u i s i t a do s a n te s do i n íc i o d a s u a e x e c u ç o (a l o c a çäo e s tát ic a ) D e s s a m a n e i r a
o s p r o c e s s o s s ó i n i c i a m a e x e c u ção c o m t o d o s o s r e c u r s o s a lo c a d o s e , p o r t a n t o , n ao f a z e m n o v a s
r e q u i s i çöe s d u r a n t e s u a s e x e c u çõe s In fe l i z m e n te , a a p l i c a ção de s t a r e g r a r e s t r i n g e ba s t a n te o
c o m p a r t i l h a m e n t o de r e c u r s o s
A s e g u n da c o n d iç o e l i m i n a da q u a n do o s p r o c e s s o s s e d is pðe m a r e c e be r o s e g u i n t e
t r a t a m e n t o (q u e , de f a t o , i m p le m e n t a o c o n f is c o , po r m c o m a pa r t i c i pa çao do p r o c e s s o
c o n f i s c a do ) : pe r m i t id o r e q u i s i t ar e l ibe r a r r e c u r s o s d u r a n te a e x e c u çao (a l o c a çäo d i n am i c a ) ,
m a s s e m p r e q u e u m r e c u r s o r e q u i s i t a d o e n o há u n ida de s d i s po n f v e i s . o p r o c e s s o o b Dg a do a
de v o l v e r ( l ib e r a r ) t o d o s o s r e c u r s o s q u e e le po s s u i pa r a e n t o r e q u i s i t a r t u do c o le t i v a m e n te
(r e q u i s i t a t o d o s o s r e c u r s o s de v o l v i d o s , m a i s o r e c u r s o c a u s a do r do b l o q u e i o ) Po r t a n to ,
Scanned by CamScanner
192 s i s t e m a s o pç r a c io n a i s e p r o s r a
m a çao c o n c o r r e n t e
S S T o s e R S d e O l i v e i r a e A S Ca r i s s i m i
r e q u i s i t a r u m r e c u r s o n ão d i s po n
l v e l e q u i v a l e a l ib e r a r 
t o d o s o s r e c u r s o s p o s s u íd o s e fi c a r
b l o q u e a do I n f e l i z m e n t e , a m a i o r
i a d o s r e c u r s o s n ão p o d e m s
e r l i b e r a d o s t e m p o r a r i a m e n te
d u r a n t e s u a s u t i l i z a çö e s
A t e r c e i r a c o n d i ção (f o r m a ção de c ic l o s ) é e l i m i n a da s e o s r e c
u r s o s s ão h i e r a r qu i z a do s e
o s p r o c e s s o s f a z e m a s r e q u i s i çõe s se m p r e n a o r
de m c r e s c e n te d a h i e r a r q u i a E s t a r e gr a de
c o m p a r t i l ha m e n t o p o d e s e r i m p le m e n t a da , po r e x e m p
l o
, 
n u m e r a n do o s r e c u r s o s de 1 a n (o n de n
é o n ú m e r o t o t a l d e r e c u r s o s )
, 
e o bDg a n do o s p r o c e s s o s a j a m a i s r e q u i s i t a r e m u m r e c u r s o de
o r d e m m e n o r o u i g u a l a o r e c u r s o de m a i s a l ta o rde m j á a l o c a do A s s i m , s e u m p r o c e s s o
n e c e s s i t a
, po r e x e m p l o , o r e c u r s o 5 n o i n fc i o de s u a e x e c u ção e 
o r e c u r s o 2 n o f i m de s u a
e x e c u ç ão , e l e é o b r i g a d o a r e q u i s i ta r p r i m e i r o o r e c u r s o 2 p a r a d e p o
i s r e q u i s i t a r o r e c u r s o 5
75
E s t a r e g r a é b a s t a n t e u t i l i z a d a n a p r át i c a p o r q u e n ão r e s t r i n g e t a n t o o c o m p a r
t i l h a m e n t o de
r e c u r s o s
N a s e ção 14 4 é m o s t r a do c o m o a s t r ês r e g r a s a c i m a f o r a m u t i l i z a d a s n a a l o c a ção de
r e c u r s o s d o O S/ 3 60 d a I B M
, 
u m s i s t e m a o p e r a c i o n a l m u l t i p r o g r a m a d o t i p o b a t c h m u i t o p o p u l a r
n a d éc a d a d e 7 0 E s t e f o i o p r i m e i r o SO c o m e r c i a l p r o g r a m a d o d e f o r m a a g a r a n t i r a n ão
o c o r r ên c i a d e d e a d to c ks
A f o r m a ç ão d e c i c l o s t a m b ém p o d e s e r e v i t a da a p a r t i r d a hi e r a r q u i z a ç ão d o s p r o c e s s o s
(a o i n v é s d o s r e c u r s o s ) e e s s a M e r a r q u i z a ção p o d e s e r e s t a be l e c i d a a t r a v és d a i d e n t i f i c a ção
(n ú m e r o ú n i c o ) q u e c a d a p r o c e s s o p o s s u i n o s i s te m a V a m o s r e f e r i r p o r i dp a i de n t i f i c aç ão ún i c a
do p r o c e s s o p e v a m o s s u po r qu e idp < id q s i gn i f i c a q u e a p D o r i da d e d e p é m a i o r q u e a de q (o s
p r o c e s s o s m a i s v e l ho s têm p r e fe r ên c i a ) A s du a s téc n i c a s s e gu i n t e s s ão c o m u m e n te u s a d a s pa r a
e v i t a r a f o r m a ção d e c i c l o s
h b ,
T éc n i c a w a u d i e (m a i s v e l ho e s pe r a , m a i s n o v o m o r r e ) Se m p r e q u e o c o r r e u mc o n n i t o , is to
é
, 
s e m p r e q u e u m p r o c e s s o p r e qu i s i t a u m r e c u r s o q u e e s t á a l o c a d o p a r a u m p r o c e s s o q , o SO
u s a a s e g u i n te r e g r a
Se id p < id q (p é m a i s v e lho ) , e n t ìi o p é c o l o c a d o n a f i l a de e s pe r a d o r e c u r s o
C a s o c o n (í ár i o (P m a i s n o v o )
, p l i be r a o s s e u s r e c u r s o s e m o r r e (m a i s t a rd e , p s e rá
r e i n ic i a l i z a do e n e s s a o c a s i ão e l e r e c e be r á a m e s m a ide n t i f i c a ç o id p) 
* T c n i c a w o u n d y a i r (m a i s v e l ho de s t r ó i
, 
m a i s n o v o e s pe r a ) Se m p r e q u e u m p r o c e s s o P
r e q u i s i t a u m r e c u r s o q u e e s tá a lo c a do pa r a u m p r o c e s s o q , o SO u s a a s e g u i n t e r e 吕 r a
Se idp < ldq (P m a i s v e l h o ) , e n tao q de s t r u :d o
, 
s e n do l i be r a do s o s s e u s r e c u r s o s(m a i s t a r de
, q s e r á r e i n ic i a l i z a do e r e c e be r á a m e s m a ide n t i n c a ç ao idq ) 
C a s o c o n t r ár i o (P m a i s n o v o )
, p é c o l o c a d o n a f i l a de e s pe r a d o r e c u r s o
?s N e s t e e x e m p lo e s t á a l c * u po r qu e o 1 r e c u r ao 1 5 e 2 1üo n e c e s s ár i o s a o m e s m o te m po po i s s e a s s i m n äo fo s s e 
Or e c u r s o 5 po de r i a Be r r e qu i s i t a do e l ibe r ad o pa r a d e po i 1 o r e c u r s o 2 s e r r e qu i s i t a d o
Scanned by CamScanner
Ca pí t u lo 14 D e a d lo c k s 19 3
A s t éc n i c a s s ão s e m e l ha n te s e
, 
e m a m b a s
, 
o p r o c e s s o m a i s v e l h o é o f a v o r e c ido I s t o é
,
e m a m b a s a c o n te c e a l ib e r a ção d o s r e c u r s o s p o r p a r t e do p r o c e s s o m a i s n o v o (de m e n o r
p r i o r i d a d e ) A s m a n e i r a s pe l a s q u a i s s e e v i t a m o s c ic l o s s ão di f e r e n te s : n o pr i m e i r o c a s o , u m
p r o c e s s o m a i s n o v o n u n c a f i c a à e s pe r a de u m m a i s v e l ho e , n o s e g u n do , é u m p r o c e s s o m a i s
v e lh o q u e n u n c a f i c a à e s pe r a d e u m m a i s n o v o
E m b o r a h a ja m s e m e l h a n ça s , e x i s te u m a g r a n de d i f e r e n ç a e n t r e o s do i s m t o d o s N o
pDm e i r o , a l ib e r a ç ão é " c o n s c i e n t e " , f e i t a pe l o p r ópDo p r o c e s s o de m e n o r p r i o Dda de , c o r n o s e
e l e c e de s s e o s s e u s r e c u r s o s e l o go a pó s s e s u i c i da s s e N o s e g u n do c a s o , o p r o c e s s o m a i s v e l ho
u s a a f o r ç a b r u t a " e d e s t r ö i o p r o c e s s o m a i s n o v o , c o n f i s c a n do o s s e u s r e c u r s o s (p o r i s t o a
s e gu n d a t éc n i c a é c o n s i de r a d a p r e m p t i v a ) 
A p r i m e i r a t éc n i c a é s i m i l a r àq u e l a u s a d a p a r a i m p l e m e n t a r o c o n f i s c o de r e c u r s o s c o m
a p a r t i c i p a ç ão d o p r o c e s s o q u e p o s s u i o r e c u r s o , de s c r i t a a n t e Do r m e n t e Só q u e a g o r a a l ib e r a ç o
de r e c u r s o s a c o n t e c e a p e n a s q u a n d o o p r o c e s s o q u e e s tá r e q u i s i t a n d o é m a i s
" f r a c o " (m e n o s
pDo r i t ár i o ) q u e o p r o c e s s o p a r a o q u a l o r e c u r s o e s t á a l o c a d o
14
. 
4 U m s i s t e m a l i v r e d e d e a d l o c k s
É d i d át i c o e s t u d a r a m a n e i r a p e l a q u a l o s p r o je t i s t a s d o s i s t e m a o pe r a c i o n a l O S / 3 60 e l i 1n i n a r a m
a po s s ib i l i d a d e d e d e a d to c k s [H A V 68] I s t o fo i c o n s e gu ido a t r a v és d a ló g i c a d a p r o g r a m a ç ão
u t i l i z a d a n a c o n s t r u ç ão d o s i s t e m a o p e r a c i o n a l , o n de f o r a m u s a d a s a s 3 téc n
i c a s d e a l o c a ç ão
a p r e s e n t a d a s n a s e ç ão a n t e r i o r
A i dé i a o Dg i n a l d o s p r o je t i s t a s d o O S/ 360 e r a o r g a n i z a r o s i s t e m a o pe r a c i o n a l n a fo r m a
de v ár i o s p r o c e s s o s q u e c o m pe t iD a m q u a s e s e m 
r e s t r i çõ e s pe l o s r e c u r s o s d o c o m p u t a do r , a f i m
de e f e t u a r e m u m g r a n d e n ú m e r o de t a r e f a s e m p a r a
l e l o I n f e l i z m e n te , a e v o l u ç o d o p r o je t o
m o s t r o u s e r m u i t o c o m u m a o c o r r ên c i a de v ár i o s 
t i p o s de de a d l o c ks e n t r e o s p r o c e s s o s
c o m pe t i t i v o s I s t o l e v o u o s p r o je t i s t a s a de te r m i n a r e m u m a po l ít i c a de a l o c a ç o de r e c u r s o s be m
m a i s r e s t D t i v a
, 
m a s l i v r e d e d e a d lo c k s E n t ão , a a lo c a ção 
de r e c u r s o s p a】n c a d a p r o g r a m a p a s s u u
a s e r fe i t a p o r u m p r o c e s s o d o s i s t e m a , de n o
m i n a do IN IT IA T O R
p a r a q u e a s o l u ç ão a do t a d a s e j a m e lho r e n te n d i d a , s e r á e x p
l i c a do a s e 吕 u i r o
f u n c i o n a m e n t o b ás i c o d o s i s t e m a o pe r a c i o n a l O s t r ês r e c
u r s o s n e c e s s ár i o s pa r a a c x e c u qào de
u m p r o g r a m a s ao
W d h po s M v o s d e U S ,
(2 ) m e m ó r i a
,
(3 ) a r q u i v o s
O s u s u ár i o s s u b m e t i a m s e u s pr o g r a m a s a t r a
v s de c a r tò e s pe r fu r a do s e , pa r a ga n h a r
te m p o , e r a n o r m a l q u e u m ún i c o
" de c k de c a r t õe s
"
c o n t i v e s s e v ár i o s p r o g r a m a s p a 】& s e r e m
Scanned by CamScanner
19 4 s i s t e m a s o pe r a c i o n a i s c P r o g r a m a ç* o C o n c o n . 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 
l im i
e x e c u t a d o s e m s e q i l ên c i a C a d a
" d e c k " f o r m a v a u m " j o b " (o p r i m e i r o c a r t ão c o n t in ha a
i de n t i f i c a ç iío d o u s u o ) e c a d a p r o g r a m a d a s e q üên c i a e r a u m " s te p " d e s s e j o b O s j o bs a se r e m
e x e c u t a d o s e r a m l id o s e c o l o c a d o s e m v ár i a s f i l a s d e e n t r a d a , e m d i s c o m a g n ét i c o E r a f tm ção do
I N H A T O R s e l e c i o n a r u m j o b e r e a l i z a r a s s e g u i n t e s o p e r a çõ e s p a r a c a d a s t e p do j o b
s e l e c i o n a do
(a ) a d qu i r i r o s r e c u r s o s n e c e s s ár i o s p a r a a e x e c u ção do s t ep ,
(b ) d i s p a r a r o s t e p c o m o u m p r o c e s s o (t a s k) s o b o c o n t r o l e d o SU P E R V I SO R e
(c ) a p ó s a e x e c u ção do s l ep , e x e c u t a r a s r o t i n a s r e sp o n s áv e i s p e l o f e c h a m e n t o do s l ep
(r o t i n a s d o T E R M IN A T O R )
M u l t i p r o g r a m a ção (m u l t i ìo bE n g ) e r a c o n s e gu id a d i s p a r a n d o v ár i a s c óp ias do
I N I T I A T O R c o m o p r o c e s s o s i n d e p e n d e n t e s ; c a d a c óp i a e r a r e s po n s áv e l p e l a e x e c u ção de u m a
s e q ü ên c i a d e j o b s
, 
s t e p p o r s t e p D e s t a m a n e i r a , v ár i o s s t ep s d e j o b s d i s t i n t o s e r a m e x e c u tado s
e m p a r a l e l o C o m o c a d a I N IT I A T O R e r a r e s p o n s áv e l p e l a a q u i s i ç ão d e t r ês t i p o s d e r e c u r so s
p a r a o s s t e p sd o j o b s o b s e u c o n t r o l e , e r a m u i t o p r o v áv e l a o c o r r ên c i a d e d e a d l o c ks e n tr e o s
v ár i o s I N IT I A T O R s
D e a d l o c ks p o d i a m o c o r r e r t a n t o d e n t r o de u m a c l a s s e d e r e c u r s o s (po r e x e m pl o , u m
IN IT I A T O R p o d i a t e r o b t i d o u m d i s p o s i t i v o de E / S D r e e s t a r r e q u i s i t a n d o u m o u t r o d i s po s i t i v o
D z , e n q u a n to o u t r o IN IT I A T O R q u e j á t i n h a o b t i d o D 2 e s t a v a r e q u i s i t a n d o D l ) c o m o e m u m a
c o m b i n a çã o d e c l a s s e s (po r e x e m p l o , u m I N IT I A T O R p o d i a t e r o b t i d o u m a r q u i v o A e e s tar
r e q u i s i t a n d o u m d i s p o s i t i v o D , e n qu a n t o u m o u t r o I N I T IA T O R q u e j á t i n h a o b t i d o o d ispo s i ti v o
D e s t a v a r e q u i s i t a n d o o a r q u i v o A )
A s e g u i r s e r á de s c r i t o c o m o c a d a c l a s s e d e r e c u r s o s f o i a l o c a d a de m o do a e v i tar
d e a d to c k s e
, p o s te r i o r m e n t e , s e r á d e s c r i t o c o m o f o i f e i t a a a l o c a ção c o m b i n a d a d a s t r ês c la sse
s
A n t e s
, p o r ém . c o n v ém r e c a p i t u l a r a s t r s r e g r a s d e c o m p o r t a m e n t o qu e , i n d i v idu a l m e n te , 
s o
s u f i c i e n te s p a r a e l i m i n a r a po s s i b i l i d a de de d e a d to c k e m qu a l qu e r s i s te m a
o s r e c u r s o s s ão r e q u i s i ta d o s c o l e t i v a m e n t e
, 
o u
a n t e s d e u m n o v o r e c u r s o s e r r e qu i s i t a d o
, 
t o d o s o s r e c u r s o s p o s s u fdo s s ão 
l ibe r ado's
p a r a s e r e m s o l i c i t a do s c o l e t i v a m e n te j u n t o c o m o n o v o r e c u r s o r e qu e r ido . o u
o s r e c u r s o s s ão r e q u i s i t a d o s s e m p r e d e a c o r d o c o m u m a o r de m p r e s ta be
le c ida 
14
. 
4
. 
1 A l o c a çã o d e d l s p o s l t i v o s d e E /S
N ão h a v e r i a d e a d l o c k s e t o do s o s d i s po s i t i v o s n e c e s s £lr i o s à e x e c u çao de u m j o b fo s se m a
loc ados
n o i n fc i o d o p r i m e i r o s t ep e l ibe r a do s n o f in a l do ú l t i m o s t ep d o Jo b p o r ém , pa r a 
u 1e lho r a 
r o
c o m p a r t i l ha m e n t o
, 
e s t a a lo c a çäo c o le t i v a f o i a d o ta da a pe n a s a n f v e l de s t ep A 
de c i s ão fo
i : ao
f i nal d e u m s t e p , l i b e r a r t o d o s o s d i s p o s i t i v o s a lo c a do s (m e s m o o s q u e c o n t in u a s s e m a 
se f t1s
ado s
Scanned by CamScanner
Cap lh 1l o 14
D e a d lo c k s 195
n o p r óx i m o s t ep ) e r e q u i s i t a r c o le t i v a m e n te t o d o s o s d i s po s i t i v o s n e c e s s ár i o s a o p r ó x i m o s l e p
p o de Da o c o r r e r d e a d l o c k s e o IN IT I A T O R l ib e r a s s e s ó o s d i s po s i t i v o s q u e n ão f o s s e m
n e c e s s áf i o s a o p r ó x i m o s t ep (a v e Df ic a ção é de i x a da c o m o e x e r c íc i o ) C o n v ém o b s e r v a r q u e , e m
ge r a l , o s d i s po s i t
i v o s d e E /S p o de m s e r l i b e r a d o s
, 
s e m m u i to p r o b l e m a , n o i n t e r v a l o de t e r r 1plo
c o m p r e e n d i d o e n t r e o f i m de u m p r o g r a m a e o i n íc i o do p r o g r a m a s e g u i n te
14 4 2 A l o c a çã o d e m e m ó r i a
U m a s o l u ção s e r i a a l o c a r p a r a t o d o o j o b u m a r e g i ão s u fi c i e n t e p a r a o m a i o r d o s s t e p s d e s s e j o b
Es s a p o s s ív e l s o lu ção f o i a b a n d o n a d a p a r a e v i t a r de s p e r d íc i o de m e m ó r i a , p r e f e r i n d o s e o b t e r
r e giõ e s d i f e r e n t e s p a r a c a d a j o b s t ep A o f i n a l de c a d a s t ep , a r e g i ão u t i l i z a d a e r a l ib e r a d a p m
e m s e g u i d a , s e r r e q u i s i t a d a u m a o u t r a r e g i ão p a r a o n o v o s l ep
14 4 3 A l o c a çã o d e a r q u i v o s
N a m a i o r p a r t e d a s v e z e s , o s a r q u i v o s u s a do s e r a m l o c a i s a o s j o bs (p o r e x e m p l o , a r q u i v o s d e
t r a b a l h o ) o u e n t ão a r qu i v o s d e b ib l i o t e c a , a c e s s a do s n a m o d a l i d a d e " 1e r s o m e n t e
" C o n t u d o
a l g u m a s a p l i c a çõ e s p o d i a m f a z e r a t u a l i z a çMe s e m a r q u i v o s g l o b a i s
P a r a p e r m i t i r c o m p u t a ç õ e s n a s q u a i s o s r e g i s t r o s d e u m a r q u i v o g l o b a l e r a m l i d o s n o
p r i m e i r o s t e p , p a r a s e r e m p r o c e s s a d o s n o s s t ep s s e g u i n t e s , p a r a f i n a l m e n t e s e r e m r e g r a v a
d o s n o
úl t i m o s l e p , f o i a d o t a d a a p o l í t i c a d e a l o c a r c o l e t i v a m e n te , a n t e s d o i n íc i o d o p r i m e i r o s t ep , t o d o s
o s a r q u i v o s g l o b a i s u t i l i z a d o s p e l o s j o b A a l o c a ção e r a p a r a t o d o o j o b , m e s m o qu e a pe n a s u m
do s s t e p s fo s s e u t i l i z a r o a r qu i v o O u s u ár i o e r a o b r i g a d o a 
d e c l a r a r o s n o m e s d o s a r q u i v o s
gl o b a i s u t i l i z a d o s E v i d e n t e m e n t e , a p e r d a q u e s e t i n h a n o c o m p a r t i l h a m e n t o de a r qu i v o s g l o b a i s
e r a p e qu e n a c o m p a r a d a c o m a pe r d a q u e s e te r i a s e e s te e s qu e m a 
f o s s e u t i l i z a d o p a r a o s
d i s po s i t i v o s d e E /S (p o i s e r a m r a r o s o s c a s o s de j o bs qu e c o m pe t i a m p e l o u s o d e a r q u i v o s
g l o ba i s )
14 4 4 A l o c a çã o c o m b i n a d a d o s r e c u r s o s
A té a qu i a s a l o c a çõ e s de d i s po s i t i v o s (D I SP) , r e giõ e s da m e m ó r i a (M EM ) e a r q u i v o s (A R Q)
f o r a m c o n s ide r a d a s d e m o d o i n d i v id u a l c o m r e l a ção a o p r o b l e m a do s de a d l o c ks A g o r a . S e
c o n s ide r a da a a l o c a ção d o s t r ês t i po s de r e c u r s o , e m c o n j u n t o
C o m o o s a r q u i v o s e r a m a l o c a do s p a r a to da a v
ida do j o b e o s de m a is r e c u r s o s s o m e n te
Pa r a u m s l e p , o s a r q u i v o s f o r a m e s c o l h id o s pa r a s e r e m a
l o c a d o s e m p r i n w i r o l u g a r A r a z zto
d i s s o é s i m p le s e p o d e s e r pe r c e b ida c o n s ide r a n do a s c o n s
e q l lên c i a s de a lo c a r , po r e x e m p lo , o s
d i spo s i t i v o s de E /s p a r a o p Dm e i r o s l ep e e n t ii o o s a r qu i v o
s pa r a o j o b in te i r o Re s u l t a Da . N e s s e
c a s o
, qu e p a r a o p r i m e i r o s t ep a o r de m de a l o c a ção se r i a 
D ISP >A R Q e p a r a o s s t e p s s e gu i n te s a
o r de m s e r i a r e v e r t i d a p a r a A R Q >D Is p (qu e r d i z e r , u m IN IT IA T O
R t r a t a n do d o p Dm e i r o s t e p
de u m j o b r e q u i s i t a r i a n a o r d e m D I s p } A RQ e n q u a n to o u t r o , t r a t a n do de u m s l ep m a i s à f r e n te ,j á te n do a l o c a d o o s a r q u i v o s , iDa r e q u i s i t a r s ó d i s po s i t i v o s , r e s u l ta n do n a o r d e m A RQ } D ISp )
Scanned by CamScanner
196 s i s t e m a s o pe r a c i on a i s e p r o g r a m a çñ 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 s a r iss im i
C r i a v a m s e
, 
d e s s a m a n e i r a
, 
c o n d içð e s p a r a o c o r r n c i a de d e a d to c ks R a c i o c fn io a n álo go fo i
a p l ic a do e m r e l a ção à r e q u i s i ção d c e s p a ço d c m e m ó r i a a n t e s d a r e q u i s i ção de a r q u i v o s Che go u 
s e e n tão à c o n c l u s o q u e a o r d e m d a s r e qu i s içõ e s d e v i a s e r A R Q > {D ISP , M E M } Re stav a
a pe n a s d e c i d i r e m q u e o r d e m s e r i a m r e q u i s i ta d o s o s d i s p o s i t i v o s e a m e m ó r i a
U m a d a s de c i s õ e s do s p r o j e t i s t a s , r e l a t i v a m e n te a a l o c a ç ão d e m e m ó r i a , e r a a de
a p r o v e i t a r a p r óp r i a r e g i ão a ] o c a da p a r a a execuçi o de u m s t e p , p a r a e x e c u t a r o IN IT IA T OR
(c o m o o I N IT IA T O R o c u pa v a 132 K , i s t o s i g n i f i c a v a q u e o t a m a n h o m ín i m o d e u m a r e gi o er a
132 K ) D u a s ár e a s d a m e m ó r i a e r a m f u n da m e n t a i s n o e s q u e m a q u e p e r m i t i u a t in gi r e sse
o b j e t i v o : a á r e a d i n âm i c a (d yn a m i c a r e a ) , o r g a n i z a d a n a fo r m a d e u m p o o l de r egiões
d i s po n í v e i s q u e p o d i a m s e r u s a d a s t a n t o pa r a e x e c u t a r j o b s t ep s c o m o p a r a e x e c u t a r c e r ta s tm b
do s i s t e m a (t a i s c o m o in p u t r e a d e r s e o u tp u t w r i t e r s , r e s p o n s áv e i s p e l a p a r t e de s p o o l in g do OS),
e u m a ár e a f i x a
, 
d e n o m i n a d a t i n k p a c k á r e a (L PA ) , o n de r e s i d i a m r o t i n a s f r e qü e n te m e n te
u s a d a s
, 
s e l e c i o n a d a s d a b ib l i o t e c a d o s i s t e m a
U m d o s e s qu e m a s e x p e r i m e n t a d o s c o n s i s t i u e m m a n te r n a L P A u m a p e qu e n a r o t in a
c o m a s f u n ç õ e s d e l i b e r a r a r e g i ão u s a d a p e lo s t e p a n t e r i o r e s e u I N IT IA T O R , a l o c a r u m a n o v a
r e g i ão p a r a a e x e c u ção d o n o v o s l e p , d i s p a r a r o n o v o s l e p c o m o u m a t a s k s o b o c o n t r o le do
S U PE R V I SO R (n a r e g i ão a l o c a d a ) , e s p e r a r o tér m i n o d a t a s k e , f i n a l m e n t e , c a 】r e g a r e e x e c u tar
(n a r e g i ão a l o c a d a ) a s r o t i n a s r e s p o n s áv e i s pe l o tér m i n o d o s t e p a t u a l (f e c h a m e n t o de a r qu i v o s ,
l i b e r a ç ão d e d i s p o s i t i v o s , e t c ) e p e la p r e p a r a ção p a r a e x e c u ç ão d o n o v o s t e p O & u x o g r am a da
f i g u r a 14 1 i l u s t r a e s te e s q u e m a
TLR E A D IN ÃM I CA ÁR E A F I X A
【ロロニ西门匡证 si i ív c ij 4
L ibe r a u qw
l ijm m e m ór ia
FIg u r a 14 1 U m e s q u e m a p a r a a lo c a ç a o d e r e c u r s o s
Scanned by CamScanner
C a p f t u lo 14 D e a d l o c k s 
19 7
O e s q u e m a p a r e c e s a t i s fa z e r a c o n d iç o d e s e m p r e s e r s e g u i d a a m e s m a o r d e m n a
a ] o c a ç äo d e r e c u r s o s : p r i m e i r o s ão a l o c a do s o s a r q u i v o s p a r a o j o b i n t e i r o
, 
d e p o i s s ão a l o c a d o s
,
p a r a c a da s t e p , o s d i s p o s i t i v o s d e E /S e a r e g i ão d e m e m ó r i a
, 
n e s ta o r de m E n t r e t a n t o
, 
i s t o n ão é
t o ta l m e n t e v e r d a d e i r o e d e a d to c k s p o d e m a c o n te c e r O t r e c h o de p r o g r a m a a s e g u i r m o s t r a c o m o
o s r e c u r s o s s ão a l o c a d o s e l i b e r a do s d u r a n te a execuçi o d o s s t ep s de u m j o b , f a c i l i t a n d o a
v e r i f i c a ç ão d e q u e a o r d e m A R Q >D I Sp M E M n ão é s e m p r e o b e de c i d a
r e q u i s i t a (M E M ) / * m e m ó r i a p a r a o I N IT I A T O R * /
k »o p
s e l e c i o n a j o b
r e q u i s i t a (A R Q)
l o o p
s e l e c io n a s t e p
r e q u i s i t a (D I SP)
l ib e r a (M E M )
r e q u i s i t a (M E M )
e x e c u t a s t ep
l i b e r a (D i s P )
e x i t w h e n ú l t i m o s t e p
e n d l o o p
l i b e r a (A R Q)
e n d l o o p
C o n s i d e r a n d o r l - A R Q
, 
r 2 - D I S P
, 
r 3 = M E M t e m s e q u e j á n o i n fc i o a o r d e n a ç ão r l , r 2
r 3 n ão é o b e d e c i d a
, p o i s o p r o c e s s o e s t á d e p o s s e do r e c u r s o r 3 e r e q u i s i t a o r e c u r s o r l D e p o i s , o
p r o c e s s o p r o s s e g u e d a s e g u i n t e m a n e i r a r e q r 2 , l i b r 3 , r e q r 3 , l i b r 2 r e q r 2 , l i b r 3 . , r e q r 2 , l i b
r 3
, 
r e q r 3 , l ib r 2 , l i b r l , r e q r l ,
A s o l u ç ão d e f i n i t i v a u s a d a p e l o s p r o je t i s t a s do O S/ 360 e s t á r e p r e s e n t a d a n o f l u x o g r a m a
d a f i g u r a 14 2 0 s e g u i n te t r e c h o de p r o g r a m a f a c i l i t a a v e D f i c a ç ão de q u e a o r d e m r l - A R Q ,
r 2 - M E M
, 
r 3 = D I Sp é s e m p r e o b e de c id a A go r a a s r e q u i s i çMe s e l i b e r a çõe s p a s s a m a o c o r r e r n a
o r de m r e q r 2 , l i b r 2 , r e q r l , r e q r 2 , r e q r 3 , l ib r 3 , l ib r 2 , r e q r 2 , r e q r 3 . , l ib r 3 l ib r l l i b r 2 , r e q
r l
, 
r e q r 2 , r e q r 3 .
r e q u i s i t a (M E M ) / * m e m ó r i a p a r a o I N IT I A T O R * /
lo o p
s e l e c i o n a j o b
l o o p
s e l e c i o n a s t e p
l i b e r a (M E M )
I f I ° s t e p t he n r e q u i s i t a (A R Q)
r e q u i s i t a (M E M )
r e q u i s i t a (D I S P)
e x e c u t a s l e p
l i b e r a (D IS P)
e x i t w he n ú l t i m o s rep
e n d lo o p
l i b e r a (A R Q)
e n d l o o p
Scanned by CamScanner
19 8 s i s t e m a s O pe r a c io n a i s e p r o g r a 1n a ç=o 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 Sssi mj
A p e s a r d e s e t e r o p r o c e s s o de e x e c u çko p a s s a n
do de u m a r e g i ão de m e m ó r i a p a r a o u t r a
,
e n v o l v e n d o v ár i o s p r o g r a m a s d i s t i n to s , t u do p o de s e r v i s t o c
o m o u m ú n i c o p r o c e s s o c íc l i c o qu e
r e pe t e a s s e g u i n te s a çMe s : e x e c u t a a s r o t i n a s qu e f a z e m 
a a l o c a ção do s r e c u r s o s n e c e s s ár i o s pa r a
o s t e p , e x e c u t a o p r o g r a m a c o r r e s po n de n te a o s t ep , e x e c u
t a a s r o t in a s r e s p o n s áv e i s pe l a l ibe r ação
d o s r ec u r s o s
, 
f a z a s e l e ção do p r ó x i m o s t ep , e tc I s to é , o I N IT IA
T O R s e c o m p o r t a c o m o u m
p r o c e s s o e n v e l o pe q u e , r e pe t i t i v a m e n te , o b t ém r e c u r s o s p a r a o p r
ó x i m o s t e p , e x e c u t a o pr o gr m
c o r r e s p o n d e n t e a o s t ep e l ib e r a o s r e c u r s o s a l o c a do s A de n o m i n a ção
"
e n v e l o p e
" de r i v a do f a to
d o p r o c e s s o e n v e l o p a r (e n c a p s u l a r ) o p r o g r a m a c o r r e s po n de n te a o s t e p e e x e c u t á l o c o m o se e le
fi z e s s e p a r t e d o p r óp r i o p r o c e s s o
A D 1N M I CA ÁR EA F I
-
B k t «
L i be r a m e m óDa j
i s i t a d i s- !
pbeEos M v5&
Fig u r a14 2 E s q u e m a d e f in i t i v o , l iv r e d e d e a d l o c k s
14
. 
5 A t i t u d e s p e r a n t e o s d e a dl o c k s
Qu a t r o a t i t u de s po de m s e r t o m a da s e m r e la ção a o p r o b l e m a do s de a d1o c ks
( 1) n ão f a z e r a b s o l u t a m e n te n a da , i s to é , de ix a r qu e o c o r r a m d ¬ a d l o c ks e , qu a n
do Isso
a c o n te c e r , f a z e r o 1 ' r e se t 
" do s i s te m a
(2 ) p r o g r a m a r o s i s te m a de t a l m a n e i r a qu e s i t u a çöe s de de a d lo c k n o po s s a r n o
c o r f e r
(3) de i x a r o s i s te m a l i v r e e m r e l a ção a o u s o de r e c u r s o s , m a s de te c t a r a s s i tu aç
õe s de
deadl ock
Scanned by CamScanner
C a p f t u l o 14 D e a d lo c k s 199
(4 ) u t i l i z a r u m a l o c a do r d c r e c u r s o s i n te l ig e n te q u e e v i t e d i n a m i c a m e n t e a o c o r r ên c i a
d e d e a d lo c ks
N o p r i m e i r o c a s o , a d e t e c ção de de a d to c ks é v i s u a l e h á o r i s c o d e s e f a z e r
"
r e s e t
"
e m
s i t u a çMe s e m q u e a p e n a s a p a r e n t e m e n te o s i s t e m a e s t á e m tl e a d l o c k
N o s e g u n d o c a s o o s p r o c e s s o s a d o t a m r e g r a s d e c o m p o r t a m e n t o q u e e l im i n a m a s
c o n d i çõ e s n e c e s s ár i a s p a r a d e a d l o c k E s t a e s t r a tégi a fo i u s a d a n o s i s t e m a O S/ 3 60 , c o n f o r m e
v i s t o n a seçi o a n t e D o r 7 6
N o t e r c e i r o c a s o é n e c e s s ár i o u t i l i z a r u m a l g o r i t m o p a r a d e t e c ç ão d e d e a d l o c k s
N a
p r ó x i m a s e ção s e r á v i s t o u m a l g o r i t m o c o m p l e t o p a r a e s s e f 1m U m a v e z d e t e c t a d o o d e a d lo c k ,
e m g e r a l o s i s t e m a t e m q u e s e r r e i n i c i a l i z a d o So m e n t e s e o s p r o c e s s o s n i o d e p e n
d e m u n s d o s
o u t r o s (n ã o c o o p e r a m n a r e a l i z a ção d e u m a t a r e f a ) é q u e t a l v e z a l g u n s d e l e s p o s s a m c o n t i n u a r
s u a s e x e c u ç Me s N o c a s o d a n e c e s s i d a de d e e l i m i n a r p r o c e s s o s , d e v e m s e r e s c o
l h i d o s o s
p r o c e s s o s d e m e n o r p r i o r i d a d e o u a q u e l e s p a r a o s q u a i s f a l t a m a i s t e m p o p a r a o 
t ér m i n o d a
e x e c u ç ã o
N o q u a r t o c a s o o a l o c a d o r d e r e c u r s o s d e v e , d i n a m ic a m e n t e , p r e v e r e e v
i t a r s i t u a çõ e s d e
d e a d lo c k U m a l g o r i t m o p a r a p r e v e n ção d i n âm i c a d e d e a d to c ks s e r á v i s t o n a s e ç
ão 14 8
14 6 0 m o d e l o d e H o l t
H o l t fo i o p r i m e i r o a f o r m a l i z a r a n o ç ão de d e a
d l o c k [H O L 7 2 ] N o s e u m o d e l o o s e s t a d o s d e
u m s i s t e m a s ão r e p r e s e n t a do s p o r g r a f o s d i Dg i d o s q u e m o s
t r a m o r e l a c i o n a m e n t o e n t r e
p r o c e s s o s e r e c u r s o s O s g r a f o s t êm 
d o i s t i p o s d e n o d o s : q u a d r a d o s , q u e r e p r e s e n t a m p r o c e s s o s
e c i r c u n f e r ên c i a s , q u e r e p r e s e n t a m r e c u r s o s Po r e x e m p
l o
, 
o g r a f o d a f i g u r a 14 3 r e p r e s e n t a u m
e s ta do de u m s i s te m a c o m 2 p r o c e s s o s e 2 r e c u r s o s
a l o c a u i s i çüo
ズ ー し
R 2
F Ig u r a 14 3 G r a fo d e e s t a d o n o m o
d e l o d e Ho l t
76 D e v e s e r o b s e r v a d o qu c n a q u e le s i s t e m a , e m b o r a n äo pu
de s s e o c o r r e r d e a d l o c k e n t r e o s p r o c e s s o s d o SO ( i s to ¢ ,
e n t r e o s IN i T I A T o R s )
, 
n a da e r a ga r a n t i do (n e m de te c t a do ) e 1n r e l a çao a o s p r o c e s s o s do s u s u
ó i o s (o s u s u ár io s
p o d i a m c f i a r p r o c e s s o s u s a n do , po r e x e m pl o A i 
fa c i l ida d e s d e m u 1t i l a s ki n g da l i n gu a 吕 e m PU I )
Scanned by CamScanner
2 00 S i s t e m a s O pe r a c i o n a i s e Pr o g>a 1n a ç o C o n c o r n 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 Ssi Tni
O s g r a f o s s ão b ip a r t id o s , p o i s n £io e x i s te m a r e s t a s l ig a n d o n o d o s d o m e s m o t ipo(r e c u r s o c o m r e c u r s o o u p r o c e s s o c o m p r o c e s s o ) O s n o d o s r e c u r s o s t êm i n t e r n a m e n t e p e qu e n a s
m a r c a s q u e r e p tr s e n t a m a s u n i d a de s e x i s te n t e s N o e x e m p l o a n te r io r , R I t e m u m a u n ida de e R2
t e m d u a s u n id a d e s U n i a a r e s t a d i r i g id a de u m a u n id a d e d e u m r e c u r s o p a r a u m p r o c e s s o in d i c a
q u e a u n i d a d e e s t á a l o c a d a p a r a o p r o c e s s o U n i a a r e s t a d i r ig i da d e u m p r o c e s s o p a r a u m r e c u r so
i n d i c a qu e o p r o c e s s o e s t á r e qu i s i t a n d o u m a u n id a de (q u a l q u e r ) de s s e r e c u r s o N o e s t ado
r e p r e s e n t a d o a c i m a u m a d a s u n i d a de s d e R 2 e s t á d i s po n í v e l e a o u t r a e s t á a l o c a d a p a r a P2 
N o r e s t a n t e d e s t e c a p í t u l o , o p r o b l e m a d o s d e a d l o c k s é e s t u d a d o a t r a v és d o m o d e l o de
H o l t N o s a l g o r i t m o s q u e s e r ão a p r e s e n t a d o s é i m p o r t a n t e q u e s e te n h a b e m c l a r o o s i g n i fi c ado
d e p r o c e s s o b l o q u e a d o I s t o é d a d o u m g r a fo q u e r e p r e s e n t a u m e s t a do d o s i s t e m a é
n e c e s s á r i o s a b e r i d e n t i f i c a r q u a i s p r o c e s s o s e s t o (e q u a i s n ão e s tão ) b l o q u e a d o s n e s s e e s ta do
T a l v e z s e j a m a i s f ác i l e n t e n d e r o s ig n i f i c a d o de " b l o q u e a d o a p a r t i r d o e n t e n d i m e n t o de " n
b l o q u e a d o
U m p r o c e s s o e s t á n ã o b l o q u e a d o q u a n d o e l e n o e s t á r e q u i s i t a n d o r e c u r s o s o u
q u a n d o e x i s t e m r e c u r s o s d i s p o n í v e i s s u f+c i e n t e s pa r a a te n d e r (c o m p l e t a m e n t e ) o s e u
p e d id o
* U m p r o c e s s o e s t b l o q u e a d o q u a n d o e l e e s t il r e q u i s i t a n d o r e c u r s o s e t o d o s o s
r e c u r s o s r e q u i s i t a d o s n ão e s t ì:o s i m u l t a n e a m e n t e d i s p o n í v e i s
N o e x e m p l o a n t e r i o r P 1 e s tá n ão b l o q u e a d o e P2 e s t á b l o q u e a d o
O B SE R V A ÇÃ O IM P O R T A N T E
Se u m p r o c e s s o e s t á r e q u i s i t a n do v ár i o s r e c u r s o s s i m u l t a n e a m e n te e a l g u m n ìio e s t i l d i s po n ív e l ,
e n t ão o p r o c e s s o f i c a b l o q u e a do s e m r e c e be r n e n h u m r e c u r s o A r e g r a é : " o u o p r o c e s s o é
a t e n d i d o d e f o r m a c o m p le ta (s e há d i s po n ib i l i da de ) o u e n tão e l e n o r e c e b e n a da e f ic a
b l o q u e a d o
"
14 1 D e t e c ç ã o d e d e a d l o c k
Qu a n d o e x i s t e m p r o c e s s o s e m d e a d l o c k n u m e s t a do d o s i s t e m a
, 
d iz s e q u e o s i s te 1n a e s tá e m
e s t a d o d e d e a d l o c k O a lg o r i t m o p a r a d e t e c ção de de a d l o c k po de s e r f a c i l m e n te e n te n d idopo r
q l i e m c o n c o r d a c o m a s s e g u i n te s c o n s ide r a çõe s Se e x is te de a dl o c k
, 
é po r cl u e e x i s te m p r o c e s s
o s
d e f i n i t i v a m e n t e b l o q u e a d o s , q u e v ão pe r m a n e c e r b l o qu e a do s pa r a s e m p r e , i n de pe n de n tc m e n
t e
d o q u e f a ç a m o s p r o c e s s o s n ão b l o q u e a d o s I s t o é
, pa r a qu a lq u e r c o m p o r t a m e n t o q u e se po s
s a
i m a g i n a r p a r a o s i s t e m a , e s s e s p r o c e s s o s v ao pe r m a n e c e r b l o q u e a do s I s t o e q u i v a l e a d i z e r q
u c
n i o e x i s t e n e n h u m a m a n e i r a de a l o c a r o s r e c u r s o s d i s po n : v e i s
, 
de m o d o a de sb lo qu e ar o s
p r o c e s s o s e m d e a d l o c k N e m m e s m o a s o pe r a çõe s m a i s f a v o r áv e i s q u e po de m s e r c o n c e b
ida s
v ão s e r s u f i c i e n t e s p a r a d e s m a n c ha r a c a de i a de p r o c e s s o s q u e e s tão e m de a d l o c k
Scanned by CamScanner
C a p fF 1l o 14 D e a d l o c k s 20 1
Po i s o a l g o r i t m o d e d e t e c ç ão c o n s i s te s i m p l e s m e n te e m v e r i f i c a r o q u e a c o n t e c e s e o s
p r o c e s s o s s e c o r n p o r t a m d a m e l ho r m a n e i r a p o s s : v e l , c o n f o r m e é e x p l i c a do a se g u i r O
c o m p o r t a m e n t o m a i s f a v o r á v e l q u e po de s e r c o n c e bid o é o s e g u i n t e C a da p r o c e s so n
b l o q u e a d o r e c e b e o s r e c u r s o s qu e e s t á r e qu i s i t a n do e , e m s e g u i da , t e r m i n a s u a e x e c u ção O
tér m i n o d a e x e c u ç ão (e c o n s e q ü e n t e l i be r a ç ão do s r e c u r s o s ) p o de de s b l o q u e a r n o v o s p r o c e s s o s ,
o s q u a i s r e p e t e m e s s e p r o c e d i m e n t o fa v o r áv e l Se , de s s a m a n e i r a , to d o s o s p r o c e s s o s fo r e m
c o n c l u íd o s , é p o r q u e n ão e x i s t e d e a d to c k n o e s t a do o r i g i n a l Se , m e s m o c o m e s t e
c o m p o r t a m e n t o , a l g u n s p r o c e s s o s p e r m a n e c e r e m b l o q u e a d o s , é p o r q u e e s s e s p r o c e s s o s e s t ão e m
d e a d lo c k
N o c a s o d o m o d e l o d e H o l t
, 
a s i m u l a ção d a s o pe r a çMe s m a i s f a v o r á v e i s c o n s i s t e e m
pe r c o r r e r o g r a f o d e e s t a do e e l i m i n a r , s u c e s s i v a m e n t e , a s a r e s t a s c o r r e s po n d e n t e s a o s p r o c e s s o s
n ão b l o q u e a d o s A r e m o ç ão d e a r e s t a s po d e d e s blo q u e a r n o v o s p r o c e s s o s , o s q u a i s po d e m 
t e r
,
e n t ão
, 
s u a s a r e s t a s e l i m i n a d a s Se t o d a s a s a r e s t a s f o r e m e l i m i n a d a s (i é , s e t o d o s o s p r o c e s s o s
fo r e m d e s b l o q u e a d o s ) é p o r q u e n ão e x i s t e d e a d lo c k n o e s t a d o o r i g i n a l
p a r a e x e m p l i f i c a r , s e r á c o n s i d e r a d o o s i s t e m a r e p r e s e n t a d o n a f i g u r a 1
4 4
, 
o q u a l é
f o r m a d o p o r 3 p r o c e s s o s e 3 r e c u r s o s D e s ej a s e s a be r s e o e s t a d o c a r a c t e r i z a d o p e l o g r a fo (a ) é
u m e s t a d o d e d e a d l o c k o u n ão N e s s e e s ta d o , o ún i c o p r o c e s s o n ão b l o q u e a d o é P2 E l i 1 n i n a n
s e a s a r e s t a s d e p 2 , o g r a f o f i c a r e d u z i do àq u e le m o s t r a d o e m (b ) N o e s t a d o c o r r e s po n de n t e a
(b )
, 
p l c o n t i n u a b l o q u e a d o m a s p 3 j á n ão e s t á m a i s b l o q u e a d o E l i m i n a n d o s e a s a r e s t a s d e P 3 , o
g r a f o r e d u z s e a o m o s t r a d o e m (c ) N o e s t a d o (c ) , P 1 n ão e s t á m a i s b l o q u e a do e s u a s a r e s t a s
po d e m s e r r e m o v i d a s , o r i g i n a n d o u m g r a f o s e m 
a r e s t a s P o r t a n t o , o e s t a d o o r i g i n a l d a ' g i 1r a (a )
n ão é u m e s t a do d e d e a d l o c k
回 回
F Ig u r a 14 4 o p e r a ç ö e * d e r e
d u ç 1 o e m u m g r i to d · m ta
d o
Scanned by CamScanner
20 2 s i s t e 1n a s ® l e r a c i o n a i s e p r o g r a m a ç 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 S Ca r i ss i m i
H o l t de n o m i n a a s o pe r a çã e s d e e l i m in a ç ão 
d a s a f e s t a s d o s p r o c e s s o s n ão b l o q u e a do s de
o p e r a çö e s d e r e d u çä o Se to d a s a s a r e
s t a s s o e l i m i n a d a s d i z s e q
u e 0 g r a f o é c o m p te t a n ze m e
r e d u t l v t l E x i s te s i t u a ç ão de d e a d l o c k e m u m e
s t a d o s e e s o m e n t e s e 0 g r a
f o c o r r e s po n de n te a
e s s e e s t a d o n ão é c o n q»le t a m e n t e r e d u t ív e l
O s p r o c e s s o s c u j a s a f e s t a s n ão p u de r e m se r
e l i m i n a d a s e s t a r ão e m d e a d l o c k
D u r a n t e a s o pe r a çõ e s de r e du ção po de s e t e r 
m a i s d e u m c a n d id a t o p a r a a e s c o
l h a (m a is
d e u m p r o c e s s o n ìi o b l o q u e a do ) N e s s e c a s o a e s c o l ha é i n d
i fe r e n t e : q u a l q u e r q u e s e j a a o r de m
v a i s e c h e g a r a o m e s m o r e s u l t a d o f i n a l A j u s t i f i c a t i v a é s i m p l e s : q
u a l q u e r q u e s e j a o p r o c e s s o
e s c o l h i d o
, 
o s o u t r o s c a n d i d a t o s c o n t i n u a r ão p o de n do t e f s u a s 
a r e s t a s r e m o v i d a s , Po i s , a pós u m a
r e d u ç ão , o n o v o e s t a do o b t i d o é s e m p r e m a i s f a v o r
áv e l p a r a c o n t i n u a r a s r e
d u çõ e s (a s r e d u çõe s
a n t i g a s c o n t i n u a m a s e r p o s s ív e i s e n o v a s r e du çõe s p
o de m s e t o m a r p o s s ív e i s ) 
E x i s t e m d i v e r s a s m a n e i r a s de r e p r e s e n t a r o s g r a f o s 
de e s t a do n o c o m p u t a d o r (m a tr i z e s ,
l i s t a s
, 
e t c ) U m a f o r m a p a f t i c u l a n n e n t e a de q u a d a é m o s t r a d a a s e g u
i r
, 
j u n t a m e n t e c o m o
a l g o r i t m o p a r a de t e c ção de d e a d l o c k s
A l g o r i t m o p a r a d e t e c t a r d e a d l o c k
O a l g o r i t m o a s e g u i r d e t e r m i n a s e e x i s t e o u n
ão de a d l o c k e m u m d e t e r m i n a d o e s t a d o Se e
x i s te
d e a d l o c k , o a l g o r i t m o i n d i c a q u a i s p r o c e s s o s e s
t ão e m d e a d lo c k O s i s t e m a é f o r m a d o p o r n
p r o c e s s o s e m r e c u r s o s C a da r e c u
r s o é fo r m a do p o r u m n ú m e r o f i x o d e u n i d a d e s e o s p r
o c e s s os
p o de m r e q u i s i t a r v ár i a s u n
i d a de s de v ár i o s r e c u r s o s de u m a s ó v e z
E s t r u t u r a s d e d a d o s
R = [ r
,
'
2
'
1n 
]
ヘ
a
l l 
a
12 
a
, 
b
l l 
b
12 
b
. . .
A =
a
2 1 
a
22 
a
21n 
B · 
b
2 1 
b
22 
b
2 . . .
a
n 1 
a
n 2 L 
b
n 1 
b
n 1 
b 
m 1J
D . [ d
, 
d
, 
d
. . 
] ( dj = r j E . U )
i = B
o n de
* R o v e t o r q u e in d i c a o n úm e r o de u n i d a de s de c a d a u m do s m r e c u r s o s
Scanned by CamScanner
C a pfn 1lo 14 D e a d lo ck s 20 3
* A é a m a t r i z q u e i n d i c a a a l o c a ção d e r e c u r s o s (a l ì é o n ú m e r o d e u n id a d e s d o r e c u r so
j a l o c a d a s a o p r o c e s s o i )
 B é a ma t r i z q u e i nd i ca a s r e q u i si çMes de r ec u r s o s ( bB í
 é o n ú me r o de u n i da d e s do
r e c u r s o j r e q u i s i t a d a s pe l o p r o c e s s o i ) e
* D é o v e t o r q u e d e s c r e v e a d i s po n ib i l i d a de a t u a l de r e c u r s o s
P a r a o s i s t e m a c o n s id e r a do n a f i gu r a 14 4 (a ) , o e s t a d o s e Da r e p r e s e n t a do d a s e g u i n te
m a n e i r a
R 2 3 l
A · = b B = = / 1
D = 【0 1 0 】
A l g o r i t m o
D a d a s a s m a t r i z e s A , B e D q u e d e s c r e v e m o e s t a do d o s i s te m a , o 
a l g o D t m o v e r i f i c a s e e x i s t e o u
n ão s i t u a ç ão d e d e a d l o c k n e s s e e s t a do
É u t i l i z a do u m v e t o r a u x i l i a r W c o m m e l e m e n t o s , p a r a
i n d i c a r a d i s p o n i b i l i d a d e d e r e c u r s o s a c a
d a m o m e n to São a do t a d a s a s s e g u i n t e s c o n v e n çMe s
 A i
 : r ep r es e n t a a l
i nh a i da ma t ri z A (al oc a ç ão de r ec u r s o s pa r a o pr oc e s s o i )
 B i
 : r ep r es e n t a a l
i nh a i da ma t ri z B ( rec u r s o s r eq u i si tad o s pe l o pr oc e s s o i )
 V e t or X [ ve t or Y s i gn i f i ca qu e t od o el eme n t
o
 de X é me n o r ou i gu a l ao el emn t o
c o r r e s p o n d e n t e de Y
O a lg o D t m o a s e g u i r p r o c u
r a a s l i n h a s c o r r e s po n de n t e s a o s p r o c e s s o s n ão b
lo q u e a dw
m a r c a e s s a s l i n ha s e l i be r a o s r e c u r s o s a
l o c a d o s a e s s e s p r o c e s s o s (n o i n i c io , t o d a s a s l i n h a s e s t il o
de s m a r c a d a s )
W Fa z e r W D
(2 ) E n q u a r 1t o e x i s t i r l i n ha i n ão m a r e a
da t a 1 q u e B i W . f a z e r
W : = w + A i e m a r c a r a l i n
ha i
E x i s t i r á d e a d to c k s e n o f i n a l d o a
lg o r i t m o e x i s t i m m 
l i n ha s n o m a n a d a s O c o n ju n t o de
p r o c e s s o s e m d e a d l o c k c o r r e s po n d e r á a o 
c o n j u n t o de l i n ha s n o m a r c a d a s
0 d e s e m p e n ho d o a l g o D t m o p
o de s e r m e l ho r a d o - a
n do s e i n ic i a l m e n te a s l in ha s i
p a r a a s q u a i s A i - 0 0 s p r o c e s s o s c
o r r e s po n de n te s a e s s a s 
l i n h a s n ão t e m r e c u r s o s a l o c a do s e ,
Scanned by CamScanner
204 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 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 S C a r i s s i m i
po r t a n t o , n ão p o d e m e s t a r e m d e a d l o c
k (n o f a z e m pa r t e d e q u a l q u e r c i c l o ) E s s e s p r o c e s s o s
t a m b ém n ão (êm r e c u r s o s p a r a d e v o l v e r n o p a s s o 2 
do a lg o r i t m o
o t e m p o m áx i m o d e e x e c u ção d o a lg o r
i t m o é p r o po r c i o n a l a n
2
* m
, p o i s , n a p i o r da s
h i pó t e s e s , a m a r c a ção d a s l i n h a s s e r á f e i t a n
a o r d e m n , n 1, n 2 . , 1 e n v o l v e n d o (n + n 12
p e s q u i s a s , e p a r a c a d a l i n h a pe s q u i s a d a s e r ão e x a
m i n a do s m r e c u r s o s
14
. 
8 p r e v e n ç ã o d i n â m i c a d e d e a d to c k
A s e g u i r s e r á m o s t r a d o c o m o u m a l o c a do r de r e c u r s o s p o de e
v i t a r a o c o r r ên c i a d e d e a d to c lw de
f o r m a d i n âm i c a
, 
d u r a n t e a e x e c u ção do s i s t e m a
p a r a e v i t a r s i t u a çõ e s de d e a d to c k , o a lo c a do r p r e c i s a c o
n he c e r
, 
a l ém d a s a lo c a çõe s ,
r e q u i s i ç õ e s e d i s p o n ib i l i d a d e s d o s r e c u r s o s , t a m bém a s po s
s í v e i s r e q u i s iç õ e s f u t u r a s do s
p r o c e s s o s C o n h e c e n d o o m á x i m o de r e c u r s o s q u e c a d a p r o c e s
s o p o d e r e q u i s i t a r (e m ge r a l o SO
t e m e s s a i n f o r m a ç ã o ) , o a l o c a d o r p o d e s a be r , a p a r t i r de u m e s t a do , q u a l é o p i o r e s t a d o q u e po
de
s e r a t i n g i d o n o f u t u r o
p a r a g a r a n t i r a n ão o c o r r ên c i a d e d e a d l o c ks , o a l o c a d o r e x e c u t a o a
l g o r i t m o a p r e s e n t a do
a s e g u i r , c o n he c i do c o m o a l g o D t m o d o b a n q u e i r o O a l g o D t m o s
i m u l a o q u e a c o n t e c e r i a n a p io r
s i t u a ç ão f u t
A l g o r i t m o d o b a n q u e i r o
A s s e g u i n t e s a çMe s s ão e x e c u t a d a s c a da v e z q u e u m r e c u r s o é r e q u i s i t a d o
( I ) s u põ e o a t e n d i m e n t o d a r e qu i s i ção
(2 ) s u põ e , a s e g u i r , q u e to d o s o s p r o c e s s o s n ão b l o q u e a d o s (i n c l u s i v e o qu e t e v e a s u a
r e q u i s iç ão a t e n d id a ) r e q u i s i t e m o m áx i m o d e r e c u r s o s q u e a i n d a po d e m r e q u i s i t ar
(3) a p l ic a o a lg o r i t m o de d e te c ção de de a d to c k s o b r e e s t a si t uaçi o h i po téci c a (q u e é a
p i o r q u e p o de o c o r r e r n o f u t u r o )
(4 ) s e e s t a s i t u a ç ão n o é de de a dlo c k , e n t r e g a r e a l m e n t e o s r e c u r s o s r e q u is i ta do s
o Dg i n a l m e n te ; c a s o c o n t r ár i o , n o e n t r e g a o s r e c u r s o s e b lo q u e i a o p r o c e s s o
O a lg o r i t m o é a p l i c a do po r o c a s i o da s r e q u i s içMe s q u e po de m s e r a te n d ida s (q u a n do u
n i a
r e q u i s iç ão n ão p o de s e r a t e n d i d a o p r o c e s s o é b l o q u e a d o , s i m p le s m e n te ) O a lo c a do r , pa r a e
v i tar
p o s s :v e i s s i t u a çö e s f u t u r a s d e de a dl o c k , po d e , po r t a n t o , n o a te n d e r a r e q u i s iç o d e u m p
r o c e s s 
o
,
r r le s m o t e n d o r e c u r s o s d i s po n :v e i s p a r a i s s o I s t o é , pa r a s e ga r a n t i r c o n t r a po s s ív e i s 
(t a l v e z
i m p r o v áv e i s ) d e a d l o c ks o a l o c a d o r r e s t r i n g e o c o m pa r t i l ha m e n t o d e r e c u r s o s
o a lg o r i t m o é c o n he c id o c o m o
"
a l g o r i t m o do b a n q u e i r o " po r te r s id o a p r e s e n
ta do po f
D ij k s t r a [D I J 65 a ] c o m o u m a s o l u ç ão pa r a o s e g u i n t e p r o b l e m a " u m b a n q u e i r o t e m u m c a p
i t a l
Scanned by CamScanner
C lo 14 D e a d l o c k s 205
de K n o r i n s (m o e d a ho l a n d e s a ) e u m de t e r m i n a do c o n j u n t o d e c l i e n te s c o n f i áv e i s (i s t o é , q u e
ho n r a r ão s e u s c o m p r o m i s s o s d e n t r o d e u m t e m po f i n i t o ) C a d a c l i e n t e te m u m l i m i t e d e c r éd i to ,
o q u a l n ão u l t r a p a s s a K C o n t u d o , a s o m a d o s l i m i t e s do s v á r i o s c l i e n t e s po d e u l t r a p a s s a r K
T o do c l i e n t e c o n c o r d a e m e s pe r a r o te m p o q u e f o r n e c e s s ár i o (c o n t a n t o q u e s e j a f i n i t o ) p a r a
r e c e be r s e u e m p r é s t i m o O p r o b le m a d o b a n q u e i r o é a te n de r s e u s c l ie n te s d e m od o a s a t i s f a z e r
s e m p r e s e u s p e d id o s d e empst i mos "
Pa r a i l u s t r a r o a l g o r i t m o d o b a n qu e i r o , a f igu r a 14 5 m o s t r a a l g u n s e s t a do s p o s s ív e i s
p a r a u m s i s t e m a c o m 2 p r o c e s s o s e u m r e c u r s o de 3 u n i d a d e s O g r a f o (a ) m o s t r a , a t r a v és d e
a r e s t a s t r a c e j a d a s
, 
a s r e q u i s i çõ e s m áx i m a s q u e p o d e m s e r f e i t a s (p l p o d e r e q u i s i t a r n o m áx i m o 2
u n id a de s d e R
, 
e P2 p o d e r e qu i s i t a r n o m áx i m o 3 u n i d a de s d e R ) N a l i n g u a g e m d e D ij k s t r a , e s s e
s i s t e m a p o d e s e r v i s t o c o m o u m B a n c o c o m d o i s c l ie n t e s e u m c a p i t a l d e 3 f l o r i n s , s e n d o q u e o
pD m e i r o c l i e n t e po s s u i c r éd i t o d e 2 f l o r i n s e o s e g u n do p o s s u i c r éd i t o d e 3 f l o r i n s
Su p o r q u e t e n h a s i d o a t i n g i d o o e s t a do (b ) d u r a n te a e x e c u ç ão e q u e , a s e g u i r , P2
r e q u i s i t e m a i s u m a u n i d a d e de R , c o n f o r m e é m o s t r a d o n o g r a f o (c ) A a p l i c a ç ão d o a l g o r i t m o
a c i m a i n d i c a r á q u e a u n i d a d e n ão d e v e s e r e n t r e g u e a P2 I s t o p o rq u e o p i o r e s t a d o q l l e p o d e s e r
a t i n g id o n o f u t u r o , n o c a s o d a u n i d a de s e r e n t r e g u e , é u m e s t a do de d e a d l o c k , c o n fo r m e é
m o s t r a d o n o g r a f o (d ) N e s t e c a s o o s i s t e m a f+c a r á n o e s t a d o (c ) , o n de P2 e s t á b l o q u e a do , m e s m o
te n do u n i d a d e p a r a a t e n d e r o s e u p e d i do N o g r a fo (d ) , a s a r e s t a s m a r c a d a s c o m u m p o n t o s ão a s
a r e s t
F Ig u r a 14 5 A lg o r i t m o d o 
b a n q u o l r o
A n e c e s s i d a d e d e e x e c u t a r o a l g o r i t m o a c i m a (o q u a l u t i l
i z a o a lg o r i t m o de de t e c ç o de
d e a d l o c ks c o m o s u b r o t i n a ) t o d a v e z q u e a c o n t e c e u m a r e q u i s i ç o 
d e r e c u r s o i n v i a b i l i z a a
p r e v e n ção d i n âm i c a d e d e a d to c ks , n a p r á t i c a , po i s 
i s t o i n t r o d u z u m o v e r h e a d m u i t o g r a n de n o
Scanned by CamScanner
206 S i s t e m a s O pe r a c i o n a i s e p r o gr a 1n a ç l o 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 s s i m i
SO N a r e a l i d a de
, 
a s i t u a ção é p i o r , p o i s o a lg o r i t m o t a m b m p r e c i s a s e r e x e c u t a do po r o c a s ião
d a s 1i b e r a çõ e s d e n ec u r s o s q u a n d o e x i s t e m p r o c e s s o s b lo q u e a do s (p a r a v e r s e o s r e c u r s o s r e c ém
l i b e r a d o s p o d e m s e r e n t r e g u e s o u n ão a a l g u m p r o c e s s o ) 
14
. 
9 C a s o s e s p e c i a i s
A té a qu i o p r o b l e m a d o s d e a d l o c fc s f o i e s t u d a d o le v a n do e m c o n t a a s c o n d içõ e s m a i s ge r a i s
p o s s f v e i s I s t o é , f o r a m c o n s i d e r a do s r e c u r s o s f o r m a d o s p o r v ár i a s u n i d a d e s e p r o c e s s o s qu e
p o d i a m r e q u i s i t a r v ár i a s u n i d a d e s de d i v e r s o s r e c u r s o s de u m a s ó v e z E s t a s e ção m o s t r a qu e o
p r o b l e m a p o d e s e r s i m p l i f 1c a d o q u a n d o a l g u m a s r e s tr i çõ e s s ão i n t r o d u z i d a s n o s i s t e m a
N o s d o i s c a s o s e s p e c i a i s a s e g u i r , a d e t e c ção d e d e a d to c k s s e r e s u m e a p r o c u r a r
e s t r u t u r a s e s p e c i a i s (s u b g r a f o s ) n o g r a f o de e s t a d o d o s i s t e m a , s e m a n e c e s s i d a de d e d i s t i n gu i r o s
n o d o s q u e r e p r e s e n t a m r e c u r s o s d o s n o d o s qu e r e p r e s e n t a m p r o c e s s o s P a s s a s e a t r a b a l h a r c o m
u m ú n i c o t i p o d e n o d o , p o r t a n t o
1 4 9 1 R e c u r s o s s i m p l e s
Qu a n d o o s r e c u r s o s s ão c o n s t i t u íd o s p o r u m a ú n i c a u n i d a de (r e c u r s o s s i m p l e s ) , a p r e s e n ça d e u m
c i c l o n o g r a f o d e e s t a do p a s s a a s e r c o n d i ção n e c e s s ár i a e s u f i c i e n t e p a r a a e x i s tên c i a de
d e a d lo c k N e s t e c a s o , a d e t e c ção d e d e a d l o c k f i c a s i m p l i f+c a d a p a r a a d e t e c ç ão d e u m c i c l o n o
g r a f o d e e s t a d o O a l g o D t m o p a r a de t e c t a r c i c l o s e m u m g r a f o d i r i g i d o é a p r e s e n t a d o a s e g u i r
Se j a G = < N , A > u m g r a fo d iDg i d o , o n d e N é o c o n j u n t o d e n o d o s e A é o c o n j u n t o de
a r e s t a s (o u a r c o s ) d o g r a f o O c o n j u n t o P (x ) d e n o d o s a t i n g ív e i s a p a r t i r de u m n o d o x , p o de s e r
d e f i n id o
, 
r e c u r s i v a m e n te , d a s e g u i n te m a n e i r a
P (x ) = { y tq (x , y ) ¬ A } U { z tq (y , z ) E A & y ¬ P (x ) }
U m g r a fo p o s s u i u m c i c l o s e e x i s t e a lg u m n o d o x ¬ N , t a l q u e x ¬ p (x )
A l g o r i t r 11o p a r a d e t e c çã o d e c i c l o
O a l g o D t m o e l i m i n a , s u c e s s i v a m e n te , a s a r e s t a s d i r ig id a s a s u m ido u r o s Se t o d a s a s a r e s ta s sao
e l i m i n a da s
, 
e n täo o g r a f o o r i g i n a l n o po s s u i c i c lo s N o a lgo r i t m o , w i é o n ú m e r o de a r e s t a s q
u e
s a e m d o n o do i
( 1) S : = { i t q w i - O} / * c o n j u n t o de s u m ido u r o s * /
(2 ) Pa r a c a d a e le m e n to i E S fa ça
(2 1) Pa r a c a da e l e m e n t o j tq (j , i ) E A f a ça
Scanned by CamScanner
Ca pf t u lo 14 D e a d l o c k s 207
(2 1 2 ) s e w j - O e n t ão I' a ç a S : = S u {j }
(3 ) C ic l o : = (S # N )
N o c a s o d o g r a f o e s t a r r e p r e s e n t a do po r s u a m a t r i z d e a d ja c ên c i a M , o s s u m i d o u r o s s ão
o s n o d o s i p a r a o s q u a i s M i - O
, 
i s t o é
, p a r a o s qu a i s a l i n h a c o r r e s po n de n te de M é n u l a
E l i m i n a r o s a r c o s d iDg i d o s p a r a o n o d o i s ig n i f i c a z e r a r a c o l u n a i d a m a t f i z M
14 9 2 R e q u i s i çä o s i m p l e s e a l o c a çã o i m e d i a t a
Qu a n do o s p r o c e s s o s s ão o b r i g a do s a r e qu i s i t a r a pe n a s u m a u n i d a d e d e r e c u r s o d e c a d a v e z e ,
a l ém d i s s o
, 
a s u n i d a d e s s ão a l o c a d a s i m e di a t a m e n t e (s e d i s p o n f v e i s ) , e n t ão a p r e s e n ça d e u m
kn o t n o g r a f o d e e s t a d o (v e r d e f i n i ção a b a i x o ) p a s s a a s e r c o n d i ção n e c e s s ár i a e s u f i c i e n t e p a r a a
e x i s tên c i a d e d e a d l o c k (N ão é e x i g i d o q u e o s r e c u r s o s s ej a m c o n s t i t u íd o s p o r u m a ún i c a
u n ida de )
U m k n o t e m u m g r a f o d i r i g i d o < N , A > é u m s u b c o n ju n t o m a x i m a l d e n o d o s K t a l q u e
p a r a t o d o x E K , P (x ) = K I s t o é , d e n t r o d o kn o t t o d o n o do é a t i n g :v e l a p a r t i r de q u a l qu e r