Baixe o app para aproveitar ainda mais
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
Compartilhar