Baixe o app para aproveitar ainda mais
Prévia do material em texto
Scanned by CamScanner C a p f t u l o 7 SE M Á F O R O S E l m o r e n o L a le y e s t e l a d e a r a ñ a e n m i i n o r a n c i a l o e s p l i c o n o la l e m a e l h o m b r e Dc o n u n c a Ia t e m a e l q u e m a n d e pu e s la r u e m pe e l b i c h o g r a n d e y s ó l o e r1r i e d a a 1o s c h i c o s E s la le y c o m o Ia l l u v i a n u n c 1 p u e d e se r pa r e ja e l qu e l a a gu a n t a s e q u e j a pe r o e l a s u n t o e s s e n c i l l o l a le y e s c o m o e l c u c h i l lo n o o t i e n d e a q u i e n lo 11m e ja A s v a r i á v e i s ser nd/o r a s s ão v a r i áv e i s e s pe c i a i s q u e po de m s e r m a n i p u l a d a s a pe n a s a tr a v és de d u a s o pe r a çö e s , d e n o m i n a da s P e V [D IJ 6 5a ] Es t a s v a r i áv e i s lb r a m d e lì n id a s po r D ij k s m » Ä m a i s de 30 a n o s e , a o q u e t u do i n d i c a , c o n t i n u a r o s e n d o u s a d a s po r m u i t o s a n o s A s dc n o m i n a çö e s p c V s ão a s i n ic ia i s d a s pa la v r a s ho l a n de s a s P r o be r e n e Ve r ho g e r 1, q u e s i g n i f i c a m t e s t a r e in c r e m e n t a r , r e s pe c t i v a m e n t e Se n do S é u m a v a r i áv e l s e m áfo r a , a s o pe r a çõ e s P e V te m a s e g u i n te s e i n 1 n t ic a p (s) : e s pe r a a; é s se r ma i or qu e o e en t üo su b t rai I de S ; \ . ' ( ' ° ' V (S) : i nc r eme n t a S de 1 . n, 1 A s o pe r a ç öe s " te s t a r S e s u b t r a i r 1 ( s e S > O) " e " i n c r e m e n ta r S de 1 " s üo e x e c u t a da s de f o r m a m u t u a m e n te e x c l u s i v a , n o k e r n e l d o SO Se S = 1 e do i s p r o c e s s o s e x e c u t a m P (S) " s i m u l t a n e a m e n <e " , u m d o s p r o c e s ao s v a i f i c a r b lo qu e a d o Scanned by CamScanner 90 s i s t e m a s o pe r a c io n a i s e pr o s ra m a ® Co n c o n e n te S S T o s c a n i , R S de O1i v e i 1a c A . s . c a r j11i1ni p o de se fa z e r a n a lo g ia e n t r e u m a v a r iáv e l s e m áfo r a e u m v a so c o n te n do bo l itaB (bo l i n ha s de Bu de ) o v a lo r n u m r ic o do s e m á fo r o c o r r e s po n de a o n ú m e r o de bo l i t as den t r o do - u m a o pe r a ç o v conesponde a pô r u m a bo l i ta n o v a s o C a da o pe r a ção P te n ta r em o v er u m a bo l i t a se n e n hu m a e s tá d i s po n :v e l , e n tão a o pe r a ção b l o qu e i a 0 p r o c e s s o e 0 Co lo c a no n a f i l a de e s pe r a Qu a n do u m a bo l i t a é c o lo c a da n o v a s o (o pe r a ção V ) , e l a é r e m o v ida pe lo primei ro p r o c e s s o d a f i l a de e s pe n O qu a l p r o s s e gu e s u a e x e c u ção 7 . 1 I m p l e m e n t a çã o d e s e m áf o r o s n o k e n ze t d o SO p a r a i m p le m e n t a r u m a v a r iáv e l s e m áfo r a é n e c e s s áDo u t i l i z a r u m a v a r i áv e l i n t e i r a e u m a f i la de e s pe r a Se ja m c o u n t s e ß ta s , r e s pe c t i v a m e n t e , a v a r i áv e l i n te i r a e a f i l a de e s pe r a as s o c iada s a u m s e m á fo r o S U m a i m p l e m e n t a ção po s s ív e l p a r a a s o p e r a ç õ e s P e V , c o n s i de r a n do o ke m t 1 de SO d e s c r i t o n o c a p ít u l o 4 , s e r i a a s e g u i n t e Sa l v a e s t a do de a t u a l Sa l v a e s t a do d e a t u a l i f c o u n t s = o t he n i f ß ta s v a z i a t he n c o u n ts = c o u n 1 s + l i n s e r e a t u a l n a ß ta s e l s e { r e t i r a p d a j ì la s r e t i r a a t u a l d a R L i f p r i o r (p ) > p r i o r (a t u a l ) t he n i n s e r e a t u a l n a R L e l s e c o u n 1s = c o u n t s l at uat : P R e s t a u r a e s t a do d e a t u a l A T u 4 L / H e l s e i n s e r e p n a R L R e s ta u r a e s t a d o d e a t u a l 7 . 2 I m p l e m e n t a çã o d e s e m áf o r o s f o r a d o k e r n e l u m a s i m u l a ção d a s o pe r a çõ e s p e v u t i l i z a n do a s o pe r a çõe s b ás ic a s n Bu te x beg in " en d e bto c k / w a k ¬ u p é m o s t r a da a s e g u i r A v a r i áv e l s e m át o r a é i m p l e m e n t a d a pe l a s v a r i áv e i s g loba l s c o u n t s Do [ i po in t e g e r , e ß la s , do t i po qu e u e c a d a p r o c e s s o po s s u i u m a v a r i áv e l loc a l de n o m in a da b l o qu e a r , pa r a i n d ic a r s e o p r o c e s s o de v e s e b lo q u e a r o u n o P(S) bl o q u e a r = f a l s e m u t e x b t g in , i f c o u n l s = O t he n b l o q u e a r = t r u e in s e 饩 Am y s e /f , Jì la s ) V (S) m u l e x b eg i i r e m p l y w l a s ) t he n c o u n l s s c (i . = e l s e { p - nrst w1as) w a k ¬ u p (P ) m u t e x e n d e l s e c o u n ¢S e c o u n l s l m u ¢e x e n d i f b l o q u e a r the n bl o c k 团团 知心 凫 Scanned by CamScanner C 1p f t u lo 7 Se m áfo r o s 9 1 7 . 3 S l n c r o n i z a çõ e s b á s i c a s c o m o p e r a çõ e s P e V E s ta s e ç ão m o s t r a c o m o i m p le m e n t a r a s t rês s i n c r o n i z a çöe s bás i c a s u s a n do v a r i áv e i s s e m áfo r a s A p D m e i r a d e l a s , e x l u s ão m ú t u a , i m p l e m e n t a d a a t r a v és de u m semi f or o X c o m v a l o r i n i c i a l 1 O a c e s s o e x c l u s i v o a n r e g i ö e s c r í t i c a s s e ñ a i m p l e m e n t a do c o m o s e g u e X : s e m a p ho r e i n i t i a l 1 P l 丝 P(X ) P (X ) ; P(X ) R E G I O C R ÍT IC A R E G IÃO C R ÍT IC A ; R EG IÃO C R FT I C A O s e g u n d o t i p o d e s i n c r o n i z a ção , c a r a c t e r i z a d o p e l a o p e r a çõ e s b l o c k e w a k e u p (p ) é i w l e m e n t a d o a t r a v é s d e u m s e m áf o r o Y c o m v a l o r i n i c i a l z e r o Se a o p e r a ç îi o A d o p r o c e s s o P l d e v e s e r e x e c u t a d a a pó s a o p e r a ç ão B do p r o c e s s o P2 , e n t ão f a z s e o s e g u i n t e Y : s e m a p ho r e i n i t i a l 0 P (Y ) A B V (Y ) C o m o s e v ê , u m s e m á f o r o c o m v a l o r i n ic i a l z e r o po de s i m u l a r a s o pe r a çö e s b l o c k e w a k e u p (p ) D e f a to , po d e s e v e r a o pe r i1ção b l o c k c o m o s e fo s s e u m a o pe r a ç ão P s o b r e u m s e m áfo r o p r i v a t i v o d o p r o c e s s o , o q u a l é i n ic i a l i z a do c o m z e r o O s e m áf o r o p r i v a t i v o po t q u e s ó o p r o p Do p r o c e s s o po de e x e c u t a r o pe r a ç ão P (i s to é , b lo c k ) n e le Es s e s e n ü f o r o n ào p t e c i s a f i la de e s p e r a , & »i s a pe n a s s e u d o n o po de e s pe r a r n e le Su a i m p lc m ie n t a qüo , c o m o v i s t a n o e s t u do do k emet , f e i t a a t r a v s d e u m c o n t a do r (c a m p o s e m M n o r e 吕 i s i r o dc s c D t o r do W s s o A o pe r a ção w a k e u p (p ) é u m a o pe r a ç o V n o s e m á lb r o p r i v a r i v o do p m e c s s o c u j o n o m e p O t e r c e i r o t ipo de s i n c r o n i z a ç o , pa r a o c a s o dF do i l p r o c e s s o s , Ó i m p le m e n ta do a t r a v s de do i s s e m á f o r o s Y e Z , a m b o s i n i c i a l i z a do l c o m z e r o , c o n fo r m e 6 m o s t r a do a s e g u i r O c a s o de u m a ba r r e i r a p a r an p r o c e s s o s de i x a do c o m o e x c r c fc io Scanned by CamScanner 92 s i s t e m a s o pe r a c i o n a i s e p r o u - c o n c o m n t e . S S T o l c a n i , R s d e O 1i v e i r a eAS11i mi Y , Z : s e m a p ho r e in i t i a l 0 E . : E2 V (Z ) ; V (Y ) P (Y ) ; P (Z ) A B 7 . 4 P r o g r a m a s c l ás s i c o s A l i n g u a ge m V 4 i m p l e m e n t a s e m áf o r o s t a l c o m o e l e s f o r a m d e f in i d o s po r D ijk s tr a , se n do po s s i v e l d e c l a r a r a r r a y s de s e m áf o r o s c o m a t é d u a s d i m e n s õ e s E s t a s e ção a pr e se n ta p r o g r a m a s q u e p o de m s e r c o n s i de r a do s e x e m p lo s c l ás s i c o s d a p r o g r a m a ç ão c o n c o r r e n te T o do s e l e s e s t ão e s c r i t o s de a c o r d o c o m a s i n t a x e d e V 4 7 4 1 U m a l o c a d o r d e r e c u r s o O p r o b le m a c o n s i s t e e m i m ple m e n t a r u m c o n t r o la d o r p a r a u m r e c u r s o f o r m a d o p o r N u n idades A s e s t r u t u r a s d e d a d o s n e c e s s ár i a s e o s a l go r i t m o s j á f o r a m v i s t o s n a s s e çMe s 4 1 e 6 3 A s e g u i r , o c o n t r o l a d o r é i m p l e m e n t a d o p o r d o i s p r o c e d i m e n t o s , d e n o m i n a do s r e qu e s t e r e l e a s t r , e s c D to s d e a c o r d o c o m a s i n t a x e d e V 4 A m b o s o s p r o c e d i m e n t o s s ão d o t ip o s u br o t i n a Pa r a r e q u e s t o a r g u m e n t o U é d e s a i da e p a r a r e l e a s e o a r g u m e n t o U é de e n t r a d a v a r i á v e i s g l o b a is R a m y [5 ] o f i n te g e r ; % s u p õ E s e R i n i c i a l i z a do c o m [5 , 4 3 , 2 , l ] T in te ge r i n i t i a l 5 c o u n t e r s e m a pho r e i n i t i a i 5 m u 1e x s e m a pho r e i n i t i a l l p r o c e d u r e r e q u e s 1( U i n t e ge r ) p r o c e d u r e r e te a s e (U i n t e ge r ) P (c o u n t e r ) ; { P (n zu t e x ) P(m u t e x ) ; T = T+ l U - R IJT ; R [T1: = U T = T l ; V (n 1B4 l e R) V (m u l e x ) V (c o u n f e r ) A v a r i áv e l T o c o n ta d o r de u n id a de s d i s po n f v e i s e i n d i c a a po s içao de R qu e c o n t 1n l p r ó x i m a u n ida d e a s e r a lo c a da Es s a v a r i áv e l a s s u m e v a l o r e s e n t r e o e 5 o s e n 1áfo r o c Q u l 1l t r t r a n c a a s r e q u i s içö e s q u a n do T - o o v a l o r d o s e m áfo r o c o u n t e r (o s e u B B n úm e r o de bo l i tas " ) vai Scanned by CamScanner C a p f t u lo 7 Se m á fo r o s 9 3 s e r s e m p r e i g u a l a o v a l o r d c T Se o v a l o r d e u m s e m á f o r o p u d e s s e s e r l id o , a v a r i áv e l T n e m s e r i a n e c e s s ár i a O s e m & f o r o m u t e x g a r a n t e a c e s s o e x c l u s i v o ù v a r i á v e l T e a o v e t o r R 7 . 4 . 2 P r o d u t o r c o n s u m i d o r c o m b 1t l ï e r l i m i t a d o E s t e p r o b l e m a f o i p r o p o s t o p o r D ij k s t r a [D IJ 65 a ] e p o de s e r e n u n c i a d o c o m o s e g u e U m pa r d e p r o c e s s o s c o m p a r t i l h a u m b u jde r de N po s i çõ e s O p r i m e i r o p r o c e s s o , d e n o m i n a d o p r o d u t o r p a s s a a v id a a p r o d u z i r m e n s a g e n s e a c o l o c á la s n o b u jl e r O s e g u n d o p r o c e s s o , d e n o m i n a do c o n s u m id o r , p a s s a a v i d a a r e t i r a r m e n s a g e n s do bM e r (n a m e s m a o rd e m e m q u e e l a s f o r a m c o l o c a d a s ) e a c o n s u m í l a s A r e l a ç ão p r o d u t o r c o n s u n 1i d o r o c o r r e c o m u m e n t e e m s i s t e m a s c o n c o r r e n t e s e 0 p r o b l e m a s e r e s u m e e m a d m i n i s t r a r o b · q u e t e m t a m a n h o l i m i t a d o S e o b u ße r e s t á c h e i o , o p r o d u t o r d e v e s e b l o q u e a r , s e o b u w · e s t á v a z i o , o c o n s u m i d o r d e v e s e b l o q u e a r A s e g u i r é m o s t r a d a a p r o g r a m a ç ão d e s s e s i s t e m a c o m u m b e · d e 5 p o s iç õ e s e s u p o n d o q u e a s m e n s a g e n s s e j a m n ú m e r o s i n t e i r o s V a r i ii v e i s g l o b a i s b u jTe r a r r a y [5 ] o f i n t e g e r c /1e i o s : s e m a p h o r e i n i t i a l O ; / v a z i o s : s e m a p h o r e i n i t i a l 5 P r o c e s s o p r o d u t o r P r o c e s s o c o n s u m i d o r m s g , in : i n t e g e r ; m s g , o u r : i n t e g e r l o o p l o o p % p r o d u z m e n s a g e m m s g P (c h e i o s ) p ( v a z i o s ) ; o u l : = (o u l m o d 5 ) + l i n : = ( i n m o d 5 ) + l ; m s g : = buj Jr t our ] b u jde r t i n ] : = m s g ; V (v a z io s ) V (c h e i o s ) % c o n s o m e a m e n s a ge m n ts g e n d l o o p e n d l o o p O s e m á f o r o c h e i o s c o n t a o n ú m e r o d e b u o e r s c he io s e o s e m i iBo r o v a z io s c o n t a n k 1m r o de b u jûe r s v a z i o s C o n f o r m e j á tb i r et r i do , a s v a r iáv e i s i n t e i r a s q u e n ào s ao i n ic i a l i z a d a s te m s e u v a lo r i n ic i a l i g u a l a z e r o O b s e r v e q u e a s o l u ç ão n o s e p r e o c u p o u e m g i u a n t i r e x c l u s o m ú t u a n o a c e s s o a o b u ße r I s to p o r q u e o s d o i s p r o c e s s o s t r a b a l h a m c o m v a r i v e i s lo t a is in , o u t e n 1s g e , c e r t a m e n te . i r äo a c e s s a r s e m p r e po s i çö e s d i fe r e n t e s d o v e t o r g lo b a l b rd e r Scanned by CamScanner 94 s i s t e m a s o pe r a c i o n a i s e p r o 8r a m a çüo C o n c o r r e n te S S T o s c a n i , R S de O l r a s Cai mi 7 . 4 3 J a n t a r d o s H1ós o f o s T a m b m de v id o a D ij k s t r a [D IJ 65a ] , e s t e p r o b l e m a i lu s t r a a s s i t u a çõ e s de de a d lo c k e de po s te r g a ç o i n de f i n id a q u e po de m o c o r r e r e m s is te m a s n o s q u a i s p r o c e s s o s a dqu i r e m e l ibe r am re c u r s o s c o n t i n u a m e n t e E x i s t e m N f i l ó s o fo s qu e pa s s a m s u a s v id a s pe n s a n do e c o m e n d o C a da u m po s su i s eu lu g a r n u m a m e s a c i r c u l a r , e m c u jo c e n tr o há u m g r a n de p r a to de s p a g he t t i A f ig u r a 7 I i l u s t r a a s i t u a ç äo p a r a 5 fi ló s o fo s C o m o a m a s s a é m u i t o e s c o r r e g a d i a , e l a r e qu e r do i s g a r f o s pa r a scT c o m i d a N a m e s a e x i s t e m N g a r fo s , u m e n t r e c a d a do i s f i ló s o f o s , e o s ú n i c o s g a r fo s qu e u m f i ló s o fo p o de u s a r s ão o s do i s q u e the c o r r e s p o n de m (o d a s u a e s q u e rda e o d a s u a di r e i ta ) O p r o b l e m a c o n s i s t e e m s i m u la r o c o m po r t a m e n t o do s f i l ó s o fo s p r o c u r a n do e v i t a r s i t u a çMe s de d e a d l o c k (b lo q u e i o pe r m a n e n t e ) e de po s t e r g a ç ão i n de f i n i da (b l o q u e i o p o r t e m po i n de fi n ido ) D a d e f i n i ção d o p r o b le m a , te m s e q u e n u n c a d o i s f i lós o f o s a d j a c e n t e s po de r ão c o m e r a o s m o t e 呷 o e q u e , n o m áx i m o , N /2 f i l ó s o f o s po d e r ão e s t a r c o m e n d o de c a da v e z lìló so to 3 f i ló so fo * ' ' " ga r th 5 Fig u r a 7 1 A m e s a d o s 5 f i ló s o f o s N a s o l u ção a s e g u i r , i r e m o s n o s c o n c e n t r a r n o c a s o de 5 f i lós o f o s o s ga r fo s 53o r e p r e s e n ta d o s po r u m v e to r de s e m ál o r o s e é a do t a da a s e gu i n te r e g r a : t o do s o s 5 t ì l1\su to s pe g a m p r i m e i r o o s e u ga r f o da e squ e r da , de po i s o d a d i r e i t a , c o m e x c e ç o de u m de le s , q ue é do c o n t r a p o de s e r de m o n s t r a do f a c i l m e n te qu e e s t a s o lu ç o é l i v r e de de a d lo c ks 45 Fo i e sc o lhi do o f i ló s o fo 1 pa r a s e r o do c o n t r a A s e g u i r a p r e s e n t a do u m p r o g r a m a v 4 c o m p le to , n o l o r m a to a c e i to pe lo c o mlpi lado r N o pr o g r a m a , c a d a f i ló s o fo f a z 1o r e f e içöe s e m o r r e D a qu i pa r a a f r e n t e s e r á a do t a da a sc gu in t c c o n v e n çäo se m p r e q u e u m p r o g r a m a V 4 e s t i v e r c o m p le t o e 1e i n ic ia r á c o m 1 1v 4p r o g r a m " Bl o qu e - t e ¢x n e 1 te c a l o e qu e to d o 1 o 1 p ro c e l l o s pa 1 aa m a a dqu i r i r o 1 r e c u r so s n u m a m e s m a : sto d Scanned by CamScanner - 7 Se m á fo r o s 95 V 4 p r o g r a m g a ü b a m y [5 ] o f s e m a p ho r e i n i t l ; % a r r a y g l o ba l p r o c e du r e g e l F o r ks E i n t e ge r ) j i n t e g e r { j : = i 1 ; % j é o ga r f o d a e s qu e r da i f j O t he n Pg a ] b HM p g a M5 D e l s e p g a J b Æ pga] bUD p r o c e d u r e p u 1F o r k s ( i : i n t e g e r ) j i n t e g e r { j : = i 1 ; % j é o g a r f o d a e s qu e rd a i f j = O t h e n { v (g a r fo t l ] ) ; V (g a r f o t5 ] ) } e l s e W g a r f o uM Wgar f oi D p r o c e s s Jì l o s o fo ( i : - 1 t o 5 ) k i n t e g e r i n i t 10 w hu e k O d o ger For ks( i ì n l ; w r i t e ( ' f i l o s o fo ' ) ; w r i t e ( i ) ; w r i t e ( ' c o m e c o u a c o m e r ' ) put Forks( i ì n l w r i t e ( ' f i l o s o f o ' ) ; w r i t e ( i ) ; w r i t e ( ' pa r o u de c o m e r ' ) k = k l e n dp r o g r a m 7 . 4 . 4 p r o b l e m a d o b a r b e i r o d o r m i n h o c o T a m bém p r o po s t o p o r D ij k s t r a [D IJ 65 a ] , e s t e p r o b le m a i l u s t r a u m a o r g a n iz a ç o t i po c l i en t s e r v id o r , o n d e d i v e r s o s p r o c e s s o s c l ie n t e s u t i l i z a m o s s e r v iço s de u m p r o c e s s o s e r v ido r O s c l i e n te s po ó m d e s i s t i r d o s e r v iço e m f u n ç o d a " e s c a s s e z de r e c u r s o s " O p r o b le m a c o n s i s t e e m s i m u l a r o f u n c io n a m e n t o de u m a ba r bc a r i a c o m a s s e g u i n t e s c a r æ te r f s t i c a s A b a r be a r i a te m u m a s a l a de e s pe r a c o m N c a de i r a s c u m a c a de i r a de ba r bc a r Se n äo te m c l i e n te s à e s pe r a , o b a r be i r o s e n t a n u m a c a de i r a c do r m e Qu a n do c he g a u m c l ie n te , e lc a c o r da o b a r be i r o Se c he g a o u t r o c l i e n te e n q u a n t o o ba r be i r o e s tá t r abal hand e 1e o u o c u pa u m a c a de i r a e e s pe r a (s e te m a l 吕 u m a c ad e i r a d i s po n f v e l ) o u v a i e m bo r a (s e t o d a s a s c a de i r a s e s tao o c u p a d a i ) Scanned by CamScanner 96 Si s t e m a s o pe r a c i o n a i p r o 8r a m a ç* o C o n c o r r e n te S S T o s c a n i R S d e O I ra y s im i A s o lu ção a s e gu i r u s a 3 s e m áf o r o s : c l i e n l t s , ß l a e m u l e x O s e m áf o r o c l i e n t e s t r a n c a o b a r be i r o , s e n d o s u a s " bo l i t a s " p r o du z id a s pe lo s c l ie n te s q u e c he g a m O v a l o r de s s e se m áfo r o in d ic a o n ú m e r o d e c l ie n t e s à e s pe r a (e x c l u i n do o c l ie n t e n a c a de i r a do ba r be i r o , q u e n ão e s tá à e s p e r a ) O s e m áfo r o ß la t r a n c a o s c l ie n te s e i m p le m e n t a a f i l a d e e s pe r a O s e m l if o r o m u te x g a r a n te e x c l u s ão m ú t u a T a m bém é u s a da u m a v a r i áv e l i n t e i r a , c o u n t , q u e c o n t a o n úm r o de c l i e n t e s à e s pe r a O v a l o r de s t a v a r i áv e l é s e m p r e ig u a l a o " n ú m e r o d e b o l i t a s " do w m áfo r o c u e ñ s U m c l i e n t e qu e c he g a n a b a 1b e a r i a v e r i f i c a o n ú m e r o de c l ie n t e s à e s pe r a Se e sse n ú m e r o é m e n o r q u e o n ú m e r o d e c a d e i r a s , o c l i e n t e e s pe r a , c a s o c o n t r ár i o , e le v a i e m bo r a A s o l u ç ão é a p r e s e n t a d a a s e g u i r , c o n s ide r a n d o o n ú m e r o de c a d e i r a s n a s a l a d e e s pe r a i gu a l a 3 V a r i . i v e is g l o b a i s c t i e n t e s , ß ta : s e m a pho r e i n i t O m u l e x s e m a p ho r e i n i t l c o u n t : i n t e ge r i n i t i a l 0 P r o c e s s o b a r b e i r o P r o c e s s o c l i e n t e lo o p P (m u t e x ) P (c t ie n re s ) ; / * d o r m e se fo r o c a s o * / i f c o u n t < 3 P (m u l e x ) ; t he n { c o u n t : = c o u n t + l c o u n 1 : = c o u n t 1 ; V (c l i e n t e s ) ; / * a c o r d a o ba r be i r o # / V (ñ ta ) ; / · p e g a p r ó x i m o c l i e n t e * / V (m u t e x ) V (m u 1e x ) ; p w l a ) ; / * e s pe r a o ba r be ir o * / / * c o r t a o c a be lo * ' í » c o r t a o c a be lo * / e n d l o o p e l s e V (m u t e x ) I n i c i a l m e n t e , o ba r be i r o e x e c u t a a o pe r a ção p (c l i e n t e s ) , o n de f ic a b lo qu e a do (do r m in do ) a 【 a c he g a da de a lg u m c l ie n te Qu a n do c he g a u m c l ie n te , e le c o m e ça a dq u i r i n do a e x c lu são m ii t u a O u t r o c l ie n t e q u e c he ga r im e d i a t a m e n te a pó s , i r á s e blo q u e a r a té q u e o p r i m e in 1 l ibe re a e x c l u s ão m ú t u a D e n t r o d a r e g i o c r i t i c a , o c l ie n te v e r i f i c a s e o n ú m e r o de pe s s o a s il esp e ra é m e n o r OU ig u a l a o n úm e r o d e c a de i r a s Se ni o é , e le l ibe r a n Bu 1e x e v a i e m b o r a se n i c o r tar u c a be lo Se k m a lg u m a c ade i r a d i s po n ív e l , O c l ie n te in c r e m e n t a a v a r iáv e l « o u l Bl e e x ec u ta a o pe r ação V n o se m áfo r o c 1l e m e s s e o ba r be i r o e s tá d o r m i n do , e le a c o n la do ; c a s o contririo1 é a d c io n a da u m a " bo l i t a " n o s e m áfo r o c l ie n t e s A s e g u i r , o c l ie n te l ibe r a a e x c lu s üo m ot u a e e n ua n a f i la de e s pe r a O b a 1b e i r o a dqu i r e a e x c lu s o m út u a , de c r e m e n t a o n úm e r o de c l ie n te s , Pe 吕 a o p r i m e i r o da f i l a de e s pe r a e v a i f a z e r o c o r t e Scanned by CamScanner C a p f t u lo 7 Se m ai fo r o s 97 Qu a n do t e r m i n a o c o r t e de c a b e lo , o c l i e n t e de i x a a b a r be a Da e o b a r be i r o r e pe te o s e u l o o p o n d e t e n t a pe s a r u m p r ó x i m o c l ie n t e Se t e m c l i e n t e , o ba r be i r o f a z o u t r o c o r te Se n lio te m o b a r be i r o d o n n ie 7 4 . 5 P r o b l e m a d o s l e i t o r e se e s c r i t o r e s O p r o b l e m a d o s r e a d e r s a n d w r i t e r s [C O U 7 1] i l u s t r a o u t r a s i tu a ção c o m u m e m s i s te m a s de p r o c e s s o s c o n c o r r e n t e s E s t e p r o b l e m a s u r g e q u a n d o p r o c e s s o s e x e c u t a m o pe r a çõe s de l e i t u r a e d e a t u a l i z a ç ão s o b r e u m a r q u i v o g l o b a l (o u s o b r e u m a e s t r u t u r a d e d a d o s g l o b a l ) A s i n c r o n i z a ção d e v e s e r t a l q u e v ár i o s r e a d e r s (i s t o é , p r o c e s s o s l e i t o r e s , q u e n ão a l t e r a m a i n f o r m a ç ão ) p o s s a m u t i l i z a r o a r q u i v o s i m u l t a n e a m e n t e E n t r e t a n t o , qu a l q u e r p r o c e s s o w r i t e r de v e t e r a c e s s o e x c l u s i v o a o a r q u i v o Pr i o D d a d e p a r a o s l e i t o r e s A p D m e i r a s o l u ç åo g a r a n t e p r i o r i d a de pa r a o s p r o c e s s o s r e a d e r s S o u t i l i z a d a s d u a s v a r i áv e i s s e m áf o r a s , m u l e x e w , p a r a e x c lu s ão m ú t u a , e u m a v a r i áv e l in te i r a n r , p a r a c o n t a r o n ú m e r o d e p r o c e s s o s l e i t o r e s a t i v o s A s e g u i r s ão m o s t r a d o s o s c ó d i g o s q u e u m p r o c e s s o d e v e e x e c u t a r a n t e s e d e po i s d e u m a o p e r a ç ão R E A D o u W R I T E V a r i á v e is g l o b a i s n 1u t e x , w : s e m a p h o r e i n i t i a l l n r : i n t e g e r i n i t i a l 0 P r o c e s s o l e i t o r P (m u 1e x ) ; P r o c e s s o e s c r i t o r n r = n H l i f n r = l t he n P (w ) V (m u t e x ) ; P (w ) R E A D W R IT E P (m u 1e x ) ; V ( w ) n r = n r l i f n r = O t he n V (w ) V (m u t e x ) N o te q u e o p r i m e i r o r e a de r b lo q u e i a o p r o g r e s s o do s w r i te r s q u e c he s a 1n a pós e le . a t r a v s d o s e m á f o r o w E n q u a n t o h o u v e r r e a de r a t i v o , o s w Dte r s I 飞 c a r ko b lo q u e a do s P r i o r i d a d e p a r a o a e 1 c r i t o r e i A s o l u ç o s e g u i n te g a r a n t e p r i o Dd a de p a r a o s w r i te r s S o u t i l iz a da s a s s e 吕 u i n te s v a r i áv e i s a d ic io n a i s : u m a v a r i áv e l i n te i r a n w , p a r a c o n t a r o n úm e r o de p r o c e s s o s w r i te r s à e s pe r a (n w = a l s ig n i f i c a q u e u m p r o c e 1s o e s tá e 1 c r e v c n do e n e n hu m e s tü e s pe r a n do ) , e d u a s v a r iáv e i s Scanned by CamScanner 98 s i s t e m a i o pe - e pr o s r a m a çl o C o n c o r r e n t e S S T o 1 c a n i R S d e O l i v e i ra s s . c a r /* i1n i s e m * f o r a s , m e r O e n te n d i m e n to de s t a s o l u ç&o f a c i l i t a do q u a n d o s e o bs e r v a qu e a r o lu çao a n t e Do r 1 q u i 1e pe t id a I s t o , e s t a s o lu ç o a ppr i a s o lu ç ao a n te r i o r a u - t a da c o m u m no v o c ó d im o q u a i , n a v e n da de , u s a a m e s m a lóg i c a d a s o l u ç o a n t e r i o r E x p l i c a n d o m e lho r , an h er a o p r i m e i r o 1\e a d e r q u e b l o q u e a v a o s w r i t e r s , a g o r a é o p r i m e i r o w r i t e r q u e b lo qu e i a o s r e a der s (o s e r r 1i f o r o m de s e m pe n ha o pa pe l de m u t e x e o s e m áfo r o r de s e m pe n ha o p a pe l de w ) par a d e i x a r i s t o b e m c l a r o , o c ód i go a d i c i o n a d o é m o s t r a do e m n e g r i t o V a v e i s g l o b a is m u r e x , w : s e m a p ho r e i n i t i a l 1 n r : i n te ge r i n i t i a l 0 n w i n t e g e r ¡n i t i a l 0 n Æ l r s e m a p h o r e i n i t i a l 1 P r o c e s s o l e i t o r P r o c e s s o e s c r i t o r P (r ) P (m u l e x ) ; P (m x ) n r = n r + l ; n w = n w + 1 i r n r = I t h e n P ( w ) ; i f n w = l t h e n P (r ) V (m u l e x ) ; V (m x ) V (r ) P (w ) R E A D W R IT E P (m u l t x ) ; V (w ) n r = n r 1 ; P (n 1x ) i í n r = O [ he n V ( w ) ; n w = n w 1 V (m u 1r x ) ; i f n w = O t h e n V (r ) V (J?t x ) A r i go r , e s t a s o l u çäo n ão g a r a n te p r i o r i d a de a b s o l u t a p a r a o s w r i t e r s po r e x e np la c o n s ide r e a s i t u a ção e m q u e s e te n h a I O r e a de r s n a f i l a d o s e m áf o r o r c o m n w = 1 Im ag in e du e lo g o a pó s o w r i ce r a c a ba r s u a e sc r i t a e de c r e m e n t a r n w p a r a o , s u r j a u m n o v o w r i te r Este p r o c e s s o i r á e s pe r a r q u e o s I o r e a de r s r e a l i z e m s e u s a c e s s o s p a r a g a r a n t i r pDo r iJ a de abut a p a r a o s w r i te r s , ba s t a u s a r u m s e m áf o r o a d ic io n a l , m z i n i c i a l i z a d o c o m 1 , e c o la a r a s o pe r a \ N s P (m z ) e V (m z ) , r e s pe c t i v a m e n te , a n te s d e p ( r ) e de po i s d e v ( r ) , n o t ód ig u u o s N a de r s Dest i m a n e i r a . a f i l a do s e m áf o r o r pa s s a r á a te r n o m áx i m o u m p r o c e s s o m a de r 7 . 5 E X E R C FC l O S E x e r c f c i o 7 , 1 C o n s ide r e a e x c l u s ito m k t u a de d u a s r e g iö e s c r í t i c a s s e n do i m p le m e n ta da po r u m 1e m áf o r o i n ic i a l iz ad o c o m I E x p l iq u e p o r q u e , s e a s o pe r a çöe s p e v n o fo s se m a tön 1ic as , 1 e x c l u s üo m ú t u a po de r i a 1e r v io la da Scanned by CamScanner C a p f tu l o 7 Se m l i fo r o s 99 E x e r c fc i o 7 2 A s e ç ao 7 I m o s t r o u a i m p l e m e n t a çao d e s e m áfo r o s n o ke r n e l d o SO e a 1 e çao 7 2 m o s t r o u a i m p le m e n t a ção a t r a v s d a s o p e r a çðe s m u t e x be g in /e n d e b l o c * l w a ke u p A m b a s a s i m p le m e n t a çö e s r e f l e t e m a s e m ân t ic a a p r e s e n t a da n o i n fc io d e s te c a p ít u lo , o n d e o v a lo r de u m s e m á f o r o n u n c a n e g a t i v o R e f a ça a s i m p le m e n t a çö e s u t i l i z a n d o a s e m ân t i c a e q u i v a l e n t e a p r e s e n t a d a a s e g u i r C o n v e n ç a s e q u e a s e g u i n t e p r o p r i e d a d e é s e m p r e s a t i s fe i t a " n o c a s o de S s e r n e g a t i v o , o v a l o r a b s o l u t o de S é o n ú m e r o d e p r o c e s s o s b l o q u e a d o s n a s u a f i l a de e s pe r a - P (S) : S u b t rai 1 de S Se S < O e n t ão o p r o c e s s o é b l o q u e a d o e c o l o c a d o n a f i la de e s pe r a d e S 1 V (S ) : I n c r e m e n t a S d e 1 Se S < O e n t ão r e m o v e u m p r o c e s s o p d a f i l a d e e s p e r a e d e s b lo q u e i a p E x e r c í c i o 7 3 U m s e m á jb r o b i n á r i o é u m s e m áf o r o c u j o v a l o r p o d e s e r 0 o u 1 M o s t r e c o m o u m s e m á f o r o g e r a l p o d e s e r i m p l e m e n t a d o a p a r t i r d e s e m áf o r o s b i n ár i o s E x e r c í c i o 7 4 C o n s i d e r e a i n s t r u ção T S(X , L ) q u e e x e c u t a o s e g u i n t e c ó d i g o d e fo r m a i n d i v i s í v e l i f X t h e n g o t o L e l s e X : = t r u e m o s t r e c o m o i m p l e m e n t a r a s o p e r a çõ e s P e V s o b r e u m s e m áf o r o b i n ár i o u s a n d o a i n s t r u ção T S E x e r c íc i o 7 5 N as e ção 7 4 1 f o r a m a p r e s e n t a d o s o s p r o c e d i m e n t o s r e q u e s t ( U ) e r e l e a s e ( U ) p a r a a a l o c a ç ão d e u m r e c u r s o f o r m a d o p o r N u n id a de s idên t i c a s C o n s i d e r e a g o r a q u e s e te n h a N r e c u r s o s d i s t i n t o s , c a d a u m c o m u m a ú n i c a u n id a de U s a n do v a r i áv e i s s e m áf o r a s . c o n s t r u a o s p r o c e d i m e n t o s r e q u e s t (R) e r e l e a s e (R ) , o n de R é u m i n t e i r o (A go r a , o a r g u m e n t o d e r e q u e s t é d e e n t r a d a ) E x e r c : c i o 7 6 U s a n d o s e m áf o r o s , e s c r e v a u m p r o g r a m a c o m 6 p r o c e s s o s q u e s a t i s f a ça o g r a f o d e f l u x o de p r o c e s s o s d o e x e r c íc io 3 1 E x e r c :c i o 7 7 I m p l e m e n t e u m a s o l u ção pa r a o p r o b le m a do b u ßr r l i m i t a do , c o n s ide r a n do u m p r o c e s s o p r o d u t o r e v ár i o s c o n s u m id o r e s E x e r c fc l o 7 8 C o m o f i c a r i a a s o l u ção do p r o b l e m a do ba r be i r o d o r m i n ho c o s e a ba r bc a r i a t i v e s s e i n f i n i t a s c a d e i r a i n a s a l a de e s pe r a ( i s to , s e o s c l ie n te s n ilo s e i m po r t a s s e m de e s pe r a r ) E x e r c íc i o 7 . 9 G e n e r a l i z c o p r o b l e m a d o bB° be i r o d o r m in ho c o pa r a o c a s o de 3 ba r bc i r o s do r m i n ho c o s (c a d a u m c o m a s u a c a d e i r a de b a r be a r ) E x e r c íc i o 7 . 10 U s a n d o a s o pe r a çö c a b ás i c a s (m u l e x be g l n / e n d e blo c * l w a ke u p ) , r e s o l v a o s p r o b l e m a s d o bu ße r l i m i ta do , d o ba r be i r o d o r m i n ho c o , do s f i ló s o f o s e do s r e a d e n & w r i l e r r Scanned by CamScanner 1oo s i s t e m a s o pe r 1 c i o n a i s e p r o w 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 CariFi ïni E x e r c fc l o 7 1 1 M o s t r e c o m o p o de r i a s e r l e i t a a s i m u l a ç o de u m a b a r r e i r a c o m s e m áf o r o s E x e r c fd o 7 12 U s a n do a l i n g u a ge m V 4 e v a r i áv e i s s e m áf o r a s , e s c r e v a d o i s p r o gn m as c o n c o n i e n t e s f o r m a d o s po r 8 p r o c e s s o s p l , p2 . , p8 , o n de p i ( 1 [ i [ 8 ) i m p r i m e I O v e z e s o n k m e r o i N o p D m e i r o p r o g r a m a , o s p r o c e s s o s d e v e m e s t a r s i n c r o n i z a d o s d e a c o r do c o m o gr afo de n u x o d e p r o c e s s o s d a f i g u r a 3 1 (a ) N o s e g u n d o , o s p r o c e s s o s d e v e m e s t a r s i n c r o n iz ado s de a c o r d o c o m o g r a f o d a f i g u r a 3 1 (b ) E x e r c í c i o 7 13 (Re a d e r s & w r i t e r s e m B a n c o d e D a do s [B IC 8 1] ) C o n s i d e r e q u e u m a e s t r u tu ra de d a d o s p o s s a s e r c h a v e a d a ( l o c k e d ) de 3 m o d o s : S (s h a r e d ) , 1 (w r i t e i n t e n t i o n ) e X (e x c lBt s iv e ) M a i s d e u m c h a v e a m e n t o p o d e s e r a p l i c a d o , c o n f o r m e é m o s t r a d o n a t a b e l a a s e g u i r C ha v e a m e n t o c o r r e n t e S I X » ° . u j · N e gX N e ga N e g a N e g a O n d e " p e r m i t e " s ig n i f i c a q u e a e s t r u t u r a d e d a d o s a s s u m e o n o v o c ha v e a m e n t o e o pr o c e sso c o n t i n u a " n e g a " s i g n i f i c a q u e o p r o c e s s o f i c a b l o q u e a d o a té q u e a s u A r e q u i s ição po s s a se r a t e n d i d a Po r t a n t o , a e s t r u t u r a p o de : ( 1) n ão t e r n e n h u m c h a v e a m e n t o , (2 ) t e r u m o u m a is c h a v e a m e n t o s S , (3 ) t e r u m o u m a i s c h a v e a m e n t o s / , o u (4 ) t e r u m c h a v e a m e n t o X 46 S u p o n h a q u e u m n ú m e r o q u a lq u e r d e p r o c e s s o s po s s a a c e s s a r a e s t r u tu r a , a tr a v és da s e g u in t e s e q i)ên c \a c ha v e ia a e s t r u t u r a n o m o d o d e s e j a d o ; u s A a e s t r u t u r a ; de s c ha v e ia a e s t r u t u r a O s c h a v e a m e n t o s e d e s c h a v e a m e n t o s s ão e f e t u a d o s c o m o s s e g u i n t e s p r o c e d i m e n to s L S l o c k n o m o d o S L I l o c k n o m o d o / L X l o c k n o m o do X R S r e m o v e u m d o s lo c k s S R/ r e m o v e u m d o s l o c k s / RX r e m o v e o lo c k X (a ) U s a n d o s e m á f o r o s , e s c r e v a o c ód igo p a r a o s s e i s p r o c e d i m e n t o s a c i m a (b ) Su a s o l u ç ão po de o c a s io n a r po s (e rg a ç o i n d e Fi n ida de a lg u m p r o c e s s o ? Se s i m . M o s t re c o 111o a po s t e rg a ção i n d e f i n id a po de o c o r r e r O B S : O a c e s s o w r i 1e i n t e n t io n f a z s e n t id o q u a n do a s o pe r a çð e s d e a t u a l i z a ç o s o re a l iz adas e n i d u a s fa s e s [G I p 79 ] N a p r i m e i r a , de n o m i n a d a w r i t e i n t e n t i o n , a a t u a l i z a ç üo p r e pa r a da n Bo f 1* i c - n te r e a l i z a d a N a s e g u n d a , de n o m i n a d a w r i t e o u c o n 1n Bi t , a a t u a l iz a ç o re a l iz a da (a go r a c o m a c e s s o e x c l u s i v o ) 4o T a m b m po de e v e r o 1 i 1 tc m a c o m o u 【ï w * e n e r 1 l i z a çm do p r o b l e m a d o 1 r t a d t r s & w r i r e r ¥ O l B s 1 c M tu r1 I P ri s1en »t i po 1 de P_ o o T i d t ° o o w r l¢e r 1 c o o in t c n c io n a d o 1 Di v e r 1 o 1 r e a d e r r po de m a c e ss : km ¢a m o t e m po D i v e r 1 o 1 " i n t e n c io 1u d o 1 " t a m b¢m po de m M 1 s a pe n a 1 u m w r i t e r po de a c e s s a r de c ada v c z
Compartilhar