Buscar

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

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 12 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 12 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 12 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

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

Outros materiais