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

Prévia do material em texto

Scanned by CamScanner
ì J:
C a p f t u l o 3
E SP E C I F I C A Ç; O
D A C O N C O R R ÊN C I A
M a r f fn F i e r r o E1 m o r e n o
Y y a q u e a l m u n d o v i n i s t e s Y a y úda m e i n ge n i o m fo
c o n e l s i n o d e c a n t a r p a r a ga n a r e s t a a pu e s t a
n o t e v a y a s a t u r bar m u c h o e l c o n t e s t a r m e c u e s t a
n o t e a gr a n de s n i t e a c h iqu e s pe r o d e bo c o n t e s t a r
e s p r e c i s o qu e m e e sp l i qu e s v o y a d e c i r l e e n r e s pu e s t a
c u ál e s e l c a n t o d e l m a r c u ál e s e l c a n to d e B m a r
Cu a n d o l a t o r m e n t a b r a m a
.
e l - q u e t o d o Io e n c i e m
c a n t a de u n m o d o qu e a t e r r a
c o m o s i e l m u n do t e m b l a r a
p a r e c e qu e se qu e j a t a
d e qu e lo e s t r ec h e 1a t ie n a
E s te c a pí tu l o f a z u m a i n t r o du ção à p r o g r a m a ção c o n c o r r e n te , m o s t r a n do a s fo r m a s pe l a s q u a i s a
c o n c o tT ên c i a d a e x e c u ção po de s e r e s pe c i f i c a da I n ic i a lm e n te , s o m o s t r a da s du a s m a n e i r a s de
e s pe c i f i c a r o r de n a ção (i s t o é , o r de m de e x e c u ç i io ) p a r a u m c o n ju n to d e p r o c e s s o s A s e gu i r . s äo
a p r e s e n ta d a s a s f o r m a s u s u a i s de e s pe c i f ic a r a c k a çao de p r o c e s s o s e , f i n a lm e n te . säo
a p r e se n t a d o s e x e m p lo s d e p r o g r a m a s c o n c o r r e n t e s
O s m e c a n i s m o s p a r a e s pe c i fi c a r c o n c o n ¬ n c ia (i s t o 6 , pa r a c r ia r e te r m i n a r pr o c e s s o s )
de v e m p o de r e x p r e s s a r r e l a çõ e s de p r e c e dên c ia a r b i t r ár i a s e n t r e o s p r o c e s s o s
Scanned by CamScanner
24 s i s t e m a s o pe r a c i o n a i s e p f o g r a m a ç=o Co n c o
r r e E S S T o s c an i , R S de O l i v e i r a e A ST aDr 1i m j
3
. 
1 R e l a ç õ e s d e p r e c e d ên c i a e n t r e p r o c e
s s o s
A s r e l a çõ e s de p r e c e dên c ia e n t r e p r o c e s s o s po de m 
s e r e s pe c i f i c a d a s a t r a v és de u m gr a f o a c ic l ic o
d iDg id o , de n o m i n a do g n ub de ß u x o de p r o c e s s o s N e s s
e g r a fo , c a da a r c o r e p r e s e n t a a e x ec u ção
de u m p r o c e s s o 
1T A f igu r a 3 1 m o s t r a do i s g r a f o s q
u e s e r ão u s a do s a d i a n te pa r a i l u s t r ar o s
m e c a n i s m o s p a r a c Da ção e 
p
(a) (b )
F i g u r a 3 1 G r a fo s d e f l u x o d e p r o c e s s o s
3
. 
2 F u n çõ e s S e P
A s f u n çõ e s s e p t a m b ém p e r m i t e m e s p e c
i f i c a r r e l a çõ e s d e p r e c e dên c i a e n t r e o s p r a c e s s o
s A
f u n ção S(p , q ) c o m p õe o s p r o c e s s o s p e q e m s ér ie e a 
f u n ção P(p , q ) c o m pMe o s p r o c e s s o s P e q
e m p a r a l e lo , c o n f o r m e m o s t r a 
a fi g u r a 3 2
S(p , q)
P(p , q)
FIg u r a 3 2 Co m p o s lçû o s ä r le e pa r a le lo de p r o c e s s o s
E m g e r a l , u m g r a fo de f lu x o de p r o c e s s o s po de s e r e x p r e s s o po r 
m a i s de u rn a c x p
ï \essBo
m a te m át i c a , j á q u e P{p , q ) é e q u i v a le n te a P(q , p) U m a r e c e i t a s i m p le s pa r a o b te
r a e x pre s
s1o
c o r r e s p o n de n t e a u m g r a fo é a p r e s e n t a da a s e g u i r
Es ta r e c e i t a di m in u i a pr o ba b i l ida
de de e r ro
s
n a e spe c i f i c ação
Æ q Ba 1qu c r g r a f o d i r i g ido e s c m c i c lo s po de s e r i n te r p r e t a do c o m o u m gr a f o de f l u x o de p
r o c es s o s 
ãî 
Scanned by CamScanner
d
C a p f tu l o 3 E s pe c i l i c a çao d a C o n c o r r en c ia 25
E s p e c i f i c a ç o a t r a v s d e f u n çð e s S e P
Pa r a c o n s t n 1i r a e x p r e s s ão c o n r s po n de n te u m g r a Fo da do a t r a v és de u m a f i g u r a , c o n s ide r a s e a
f i g u r a d e d e n t r o p a r a fo r a , f a z e n do a e s p e c i f ic a ção pa s s o a pa s s o , c o n fo r m e é e x e m p l i f i c a do a
s e g u i r , pa r a o g r a fo d a f ig u r a 3 1 (a )
P a s s o 1 : P (p4 , p5)
Pa s s o 2 : S(p 3 , P (p4 , p5))
P a s s o 3 P(p 2 , S(p 3 , P (p4 , p5 )))
Pa s s o 4 : P(P(p 2 , S(p3 , P(p4 , p5 ))) , p6 )
P a s s o 5 : S(p l , P (P(p2 , S(p3 , P (p4 , p5 ))) , póD
Pa s s o 6 : P (p 7 , p 8)
P a s s o 7 : S (S(p 1, P (P (p 2 , S(p 3 , P(p 4 , p 5 ))) , p óD , P (p7 , p 8))
O b s e r v a ç i i o
Qu a l q u e r q u e s e j a a e x p r e s s ão m a te m át i c a q u e e s p e c i f iqu e u m g r a f o d e f lu x o d e p r o c e s s o s , e s s a
e x p r e s s ão t e r á n a s u a p a r t e m a i s i nt er na a s u be x p r e s s ão S (p , q) o u P (p , q ) (n ão há o u t r a o pç i i o )
C o n c e i t o d e g r a fo p r o p r i a m e n t e a n i n h a d o
S e u m g r a f o d e f l u x o d e p r o c e s s o s p o d e s e r e x p r e s s o a t r a v és d a c o m p o s i ção d a s f u n çõ e s S e P ,
e l e é d i t o g r a fo p r o p r i a m e n t e a n i n h a d o
Po d e s e c o n s t a t a r q u e o g r a f o d a f i gu r a 3 1 (b ) n ão é p r o p r i a m e n t e a n i n h a d o P a r a i s s o
,
b a s t a t e n t a r c o n s t r u i r a e x p r e s s ão m a t e m át i c a d e s s e g r a fo , p a s s o a p a s s o , s e g u i n do a r e c e i t a
a p r e s e n t a d a a n t e r i o r m e n t e Já d e p a r t i d a , a p a r t e m a i s i nt er na do g r a f o n ão p o de s e r e x p r e s s a E l a
n ão t e m a f o r m a S (p , q ) n e m P (p , q ) I s t o é , s e Da e r r a d o i n i c i a r a e s p e c i f i c a ção de s s e g r a f o c o m
s i p s , p 6) , o u S(p4 , p6 ) , o u P (p4 , p 5 ) (o q u e v iDa de p o i s d i s s o ?) Po r t a n t o , e s s e g r a f o n o 
p r o p r i a m e n t e a n i r 1h a do
3
. 
3 C o m a n d o s c o b e g i n l c o e n d
A s p D1T1i t i v a s c o b e g in e c o e n d , de n o m i n a da s o r i g i n a l m e n te p a r be g i n e p a r e n d po r D ij k s t r a
[D U 6 5a ] , e x p l ic i t a m u m c o n ju n to de t r e c ho s de c ód igo pa r a s e r e m e x e c u ta do s
c o n c o r r e n te m e n te É u t i l i z a da a s e gu in te s in t a x e
c o be g in C t C2 C n c o e n d
o n d e c a da C i u m s e g m e n t o de c ód ig o a u tön o m o Qu a n do a e x e c u çüo c he g a a o c o be g in , s ão
c D a d o s n pr o c e s s o s i n de pe n de n te s pa r a e x e c u ta r o s s e gm e n to s de c ód igo e s pe c i f i c ado s A
e x e c u çäo d o c o m a n do c o be g in / c o e n d te r m in a qu a n do to do s o s n pr o c e s s o s te r m i n a m s u as
Scanned by CamScanner
/
26 Si s t e m a s O pe r a c i o n a is e p r o g r a m a çao Co n c o r r e n t e S S T o s c a n i , R S de O l i v e i r a e A S Car i l sim i
e x e c u çöe s Qu a n do i s s o o c o m
, 
a e x e c u çko p r o s s e gu e n o c o m a n do s e g u in t e a o c o e n d A f i gu r a
3 3 i l u s t r a e s t a c o n s t r u ç o
C t
F i g u r a 3 3 Co n s t r u ç ã o c o be g i n C 1 l C2 1 I C n c o e n d
0 o p e r a d o r " " i n d i c a " e x e c u ção e m sér i e
"
e te m p r e c e dên c i a (p r i o r id a de ) s o br e o
o p e r a d o r " I" Po r e x e m p l o , o c ód ig o
co be g in p l I p2 ; p3 c o e n d
s i g n i f i c a P (p l , S (p2 , p3D Su a r e p r e s e n t a ção g r áfi c a é m o s t r ada n a f ig u r a 3 4 A l i ás , a c o n s t r u ção
s i n t á t i c a c o b e g i n l c o e n d n e m a d m i te o u t r o s ign i f i c a d o p a r a a e x p r e s s ão a c i m a (i s t o é , n ão a 山村 te
q u e o
" r ' p o s s a te r p r e c e dên c i a s o b r e o 
"
;
" )
, p o i s a s i n t a x e o b r i g a q u e a o u t r a i n te r p r e ta ção
po s s :v e l s e ja e x p r e s s a c o m o c o be g in p 1 p2 c o e n d p 3
P
F ig u r a 3 4 c o be g in p 1 l p 2 p3 c o e n d
o c ód igo c o r r e s po n de n te a o n u x o de e x e c u ção e s pe c i f i c a do n a f igu r a 3 I (a ) ó m o s tr ado
a s e g u i r
p l
c o be g in
p3
c o beg in j : U *
p4 p5
c o e n d
リカ 孛
31
p2
Scanned by CamScanner
a p f tul o 3- s p ec i f1ca ç ão da Co n c o r r enc i a 2 7
p6
c o e n d
c o be g in
p 7 p 8
c o e n d
P o de s e p r o v a r q u e a c o n s t r u ção c o be g in / c o e n d p e r m i t e r e p r e s e n t a r a pe n a s g r a fo s
p r o p D a m e n t e a n i n h a d o s Po r e x e m p l o , o g r a f o da f i g u r a 3 1 (b ) n ão p o de s e r e x p r e s s o u t i l i z a n do
e s s a c o n s t r u ção A p r o v a p o d e s e r f e i t a m o s t r a n d o q u e a s o p e r a çõe s c o be g i n / c o e n d e
" " po de m
s e r e x p r e s s a s a t r a v és d a s f u n çõ e s S e p , 
l a 
e i s t o é de i x a do c o m o e x e r c íc io
3
. 
4 P r i m i t i v a s j o r k
, j o i n e q u i l
A s o p e r a ç õe s l a r k , j o in e q u i t f o r a m d e f i n i d a s p o r C o n w a y e m 1963 iC O N 63] . Te n d o s i d o
i m p l e m e n t a d a s e m d i v e r s o s SO s e l i n g u a ge n s de p r o g r a m a ção E l a s s ão m a i s g e r a i s q u e a s
p D m i t i v a s c o b e g in / c o e n d , p o i s p e r m i te m d e s c r e v e r qu a l qu e r g r a f o de & u x o d e p r o c e s s o s
A e x e c u ç ão d a i n s t r u ç ão Tio r k × p o r u m p r o c e s s o p f a z c o m q u e u m n o v o p r o c e s s o q s e j a
c Da do e i n i c i e s u a e x e c u ção n a i n s t r u ção c o m r ó t u l o x A p a r t i r d a í , o s p r o c e s s o s p e q s ão
e x e c u t a d o s e m s i m u l t ân e o (f i gu r a 3 5 (a )) Se u m p r o c e s s o p e x e c u t a u m a i n s t r u ção q u i t , e l e
t e r m i n a (f i g u la 3 5 ( b A i n s t r u ç+i o j o in ¢ w t e m a s e g u i n t e s e m ân t i c a
1 : = t 1
i f 1= O t he n g o t o w e l s e n o t h in g
s e n d o q u e d u r a n t e a e x e c u ção do t r e c ho de l i m i ta do pe l a s l i n ha s t r a c e ja da s n e n hu m o u t r o
p r o c e s s o po de a c e s s a r a v a r i áv e l 1 (i s t o é , a o pe r a ção e n t r e a s l in ha s é e x e c u t a da de fo n n a1
a t ô m i c a o u in d i v i s :v e l ) O b s e r v e q u e , s e o v a l o r r e s u l t a n te de t é d i f e r e n te de z e m e n t ão n a da
a c o n t e c e
, 
i s to é
, 
o p r o c e s s o q u e e x e c u to u o j o i n p r o s s e gu e s u a e x e c u ç o n o r m a1l m e n te A f ig u r a
3 5 (c ) i l u s t r a a s i t u aç o de t r es p r o c e s s o s qu e e x e c u t a m a s c q t lên c i a ' Jo in B, w , q u i e ' c o m l = 3
(qu a n d o c he g a o te r c e i r o p r o c e s s o , s u a e x e c u çao é de s v ia da pa r a o r ö tu lo w ) 
1s D e s s a m a n e i r a e s t a r e m o s p r o v a n d o qu e qu a lqu e r N a fo e x p r e s s o a t r a v es de r o be « 1n l r o e n d e " ta m bém po de s e r
c x p - a t r a v s da s c o m po s i çö e 1 de S e P
Scanned by CamScanner
2 8 S i s t e m a s - e p g - C o n c o r r e n te S S T o s c a n i R S de O 1i v e i w 1 e A S 1r i m j
X : 
q t4i1 
W
Fi g u r a 3 5 O pe r a ç õ e s fo r k , lo in e q u i t
O g r a f o da f i g u r a 3 1 (b ) po d e s e r r e p r e s e n t a d o pe l o s e g u i n t e p r o g r a m a
t l =2 t2
-
3
p 1 ; f o r k a 2 : f o r k a 5 f o r k a 7 q u i t
a 2 p2 ; fo r k a 3 f o r k a 4 ; q u i t
a 3 : p 3 ; j o i n t2 , a 8 q u i t
a 4 : p4 j o i n t 0 a 6 q u i t
a 5 p 5 ; j o i n t 1 A 6 ; qu i t
a 6 p6 ; j o i n 12 , a 8 qu i t
a 7 p7 ; j o i n t2 , a 8 q u i t
a 8 p 8 ; qu i t
A l g u m a s v e z e s , u m g r a fo n ão p r o p r i a m e n t e a n i n h a d o p o de s e r t r a n s f o r m a do e m
p r o p r i a m e n te a n i n h a do , d e s d e q u e u m o u m a i s p r o c e s s o s s e j a m f o r ça d o s a e s p e r a r p o r e x e m pl o ,
o g r a f o d a f i g u r a 3 1 (b) t o m a s e p r o p r i a m e n t e a n i n h a do q u a n do s e a t r a s a o i n íc i o de p6 a té o
tér m i n o d e p3 e p7 I n f e l i z m e n te , e s s a tr a n s fo r m a ção n e m s e m p r e é po s s f v e l El a n ão po de se r
a p l i c a da q u a n do o s p r o c e s s o s e n v o l v i do s p r e c is a m e s t a r a t i v o s a o m e s m o te m po (po r e x e m pta
q u a n do p 3 e p7 p r e c i s a m s e c o m u n i c a r c o m p6)
A o pção po r m e c a n i s m o s t ipo c o be g in / c o e n d a o in v és de m e c a n i s m o s m a i s ge r a is t ipo
r uj oi n / qu i t é j u s t i f ic a da pe la im po r t ân c i a de s e f o rç a r u m a m a i o r e s t r u t u r a ç o par a o s
pr o g r a m a s c o n c o r r e n t e s (o pe r a çõe s To rk , j o in e qu i t po de m to m a r o s p r o g r a m a s c o n fu so s1
p r i n c ip a l m e n te q u a n do e s t a s o pe r a çõe s s ão u s a das de n t r o de lo o p s o u de o u t r a s e s t r u tu ra s 
de
c o n t r o l e ) p e r de s e n o po de r de r e p r e s e n t a ç o do s m e c a n i s m o s
, 
m a s ga n ha se n a c la r e z a 
da
s e m ân t ic a do s p r o g r a m a s
ï 1 3
: å
Scanned by CamScanner
C a p i t u lo 3 E s pe c i f i c a çäo d a C o n c o r r en c ia 29
3
. 
4
. 
1 F o r k n o s i s t e m a U n i x
O s i s t e m a o p e r a c i o n a l U n i x i K E R 84
, 
B A C 86 ] u s a u m a s im p l i f i c a ç ão d a o p e r a çäo j zrr k , a q u a l
c Da u m a c ó p i a i d ên t i c a d o p r o c e s s o q u e e x e c u ta e s t a o p e r a ção Po r e x e m p lo , o c o m a n d o
id = f o r ko
c D a u m j ì l ho i d ên t i c o a o p r o c e s s o q u e e x e c l 1t o u a o pe r a ção O p r o c e s s o f i l ho r e c e b e c ó p i a s da s
v a r i áv e i s d o p r o c e s s o p a i (c ó p i a s p r i v a t i v a s )
, 
b e m c o m o d o s d e s c r i t o r e s de a r q u i v o s O s v a l o f e s
i n i c i a i s d a s v a r i áv e i s d o f i l h o s ão i g u a i s a o s v a l o r e s d a s v a r i áv e i s c o r r e s p o n d e n t e s d o p a i n o
m o m e n t o d a e x e c u ç ão d a f u n ção To r k A ú n i c a d i f e r e n ça i n i c i a l e n t r e o p a i e o f i l h o é o v a l o r da
v a r i áv e l id
, q u e é O p a r a o f i l h o e é o v a l o r de r et or no d a f u n ção f o r k p a r a o p a i O v a l o r de
r et or no é o n ú m e r o d e i d e n t i f i c a ç ão d o p r o c e s s o c r i a d o , r e f e r i do p o r p id (p r o c e s s ide n t w c a t i o n )
I s t o p e r m i t e q u e o s p r o c e s s o s p r o s s i g a m d e a c o r d o c o m s u a s i d e n t i d a de s N o r m a l m e n te , o
c o m a n d o s e g u i n t e a o j b r kt e m a s e g u i n t e f o r m a
i f id = O
th e n c p r o c e s s a m e n t o d o l i 1h o \
e l s e { p r o c e s s a 1n e n t o d o p a i }
U m d o s p r o c e s s o s , p o r e x e m p l o o f+l h o , p o d e
"
s o b r e p o r
'
u m n o v o c ó d i g o s o b r e s i ,
a t r a v és d a o p e r a ção e x e c , a q u a l e s pe c i f i c a u m n o v o p r o g r a m a p a r a s e r e x e c u t a d o (n o v o
s e g m e n t o d e c ód i g o e d e d a do s p a r a o p r o c e s s o )
3 4
. 
2 0 c o n c e i t o d e t l i r e a d
V a m o s i m a g i n a r q u e a f u n ção Jb rk c r i e l l m f i l ho q u e e x e c u te o m e s m o c ód ig o d o p a i , i r la s ,
d i fe r e n te m e n t e do q u e o c o r r e n o U n i x , v a m o s s u po r qu e o pa i e o f i l h o c o m pa r t i l he m o m e s m o
e s p a ço d e e n de r e ça m e n to ( i s t o é , q u e e l e s u t i l i z e m a s m e s m a s e ún i c a s v a Dáv e i s , o s m e s m o s
r e g i s t r o s d e s c D t o r e s d e a r q u i v o s , e tc ) N e s t e c a s o , v a i ha v e r m u i to p o u c a d i f e r e n ç a e n t r e o pa i c
o f i lho I s t o 
, 
o s r e g i s t r o s d e s c r i to r e s de s s e s p r o c e s s o s v ao s e r p r a t i c a m e n te ig u a i s I s to pe r m i te
s i m p l i f i c a r o s i s t e m a d a s e g u i n t e m a n e i r a p a i e f i l ho pa s s a m a s e r e m d e s c D to s po r u m m e s
(ún ic o ) r e g i s t r o d e s c r i to r e c a d a u m p a s s a a u t i l i z a r u m m i n i de s c D t o r pnópr i a pa r a c o n te r o s
a t Db u u »s e m q u e d i f e r e m
A u t i l i z a ção de u m ú n i c o r e g i s t r o de s c r i t o r f a c i l i ta o c ha v e a m e n to da e x e c u ç o de u m
p r o c e s s o p a 】a o o u t r o
19 
e po d e s e d i z e r q u e o s p r o c e s s o s f i c a m 
"
m a i s le v e s " Sao e s s e s p r o c e s s o s
1 '
m a i s le v e s " q u e s o de n o m i n a do s t h r e a d s T o d a s a s t h r e a d s d e u m p r o c e s s o s üo de s c r i ta s po r
u m n 】e s m o (ú n i c o ) r e g i s t r o d e s c r i t o r , q u e o r e g i s t r o de s c r i t o r do p r o ç e s s o qu e c o n t m e s s a s
t h r e a d s
; / 
n N a*» ¢ n e c c s l är i o m u d a r d e r e g is t r o de ac r i t o r , o q u e o r i吕in a m e n o s t l v e r h r a d 35 T . . 
% ; ? ?
Scanned by CamScanner
30 Si s t e m a s O pe r a c i o n a i s - C o n c o r r e n t e S S T o sc a n i , R S de Ol i v e i r a e A SSSi mi
Po r s e u t ur no
, 
c a d a I /Br e a d po s s u i u m m i n i de s c r i t o r e u m a p i l ha O m i n i de s c r i to r 
u s a do p a r a s a l v a r o s v a l o r e s do s r e g i s t r a do r e s da UC P (PC , PSW , e t c ) e a p i l ha é u s a da pa r a as
c ha m a da s e r et or nos de p r o c e d i m e n t o s
U m p r o c e s s o c o m v ár i a s th r e a ds p o de s e r v i s t o c o m o u m p r o g r a m a c o m v ár i a s l in has
o u n u x o s de e x e c u ç ão (c o m o s e t i v e s s e v ár i o s p r o g r a m c o u n t e r s ) D e f a to , a t r a d u ção l i te r a l de
t h r e a d é " l in h a ' o u " f l u x o " p o de s e d i z e r qu e o qu e m e l ho r d i s t i n g u e u m a th r e a d de u m
Pr o c e s s o é o a t r ib u t o e s p a ç o d e e n d e r e ça m e n t o T o d a s a s 1 h r e a de u m p r o c e s s o t r ab a l ha m n o
m e s m o e s p a ço d e e n d e r e ça m e n t o , qu e é a m e m ó r i a lóg i c a do " p r o c e s s o h o s p e de i f o
" Qu a n do s e
t e m u m c o n ju n t o de p r o c e s s o s
, 
c a d a p r o c e s s o (r a b a l h a n u m e s p a ço d e e n de r e ça m e n t o p r óp r i o
V a l e r e s s a l t a r q u e a f u n ção j o r k do U n i x c Da u m n o v o p r o c e s s o (n ão u m a l l i r e a d) , po is
p a i e f i l h o p o s s u e m e s p a ço s d e e n d e r e ç a m e n to di s t i n t o s N ão há c o m p a r t i l h a m e n t o d e v a r i áv e i s ,
e m l»o r a s e ju n u t i l i z a d o s o s m e s m o s n o m e s p a r a a s m e s m a s
3 4 3 F o r k
, 
i n e q u i t n a l i n g u a g e m V 4
N a l i n g u a g e m V 4 , a i m p l e m e n t a ção d o c o m a n d o Jo r k a p r e s e n t a s e m ân t i c a s i m i l a r à do U n i x
(s e ç ão 3 4 1) , p o r ém c o m u m a g r a n d e d i f e r e n ç a , o j o r k c r i a u m a t h r e a d e n ão u m p r o c e s s o A s
t h r e a d s m ãe e f i l ha s ão id ên t i c a s e c o m p a r t i l h a m t o d a s a s v a r i áv e i s d o p r o c e s s o o u l a s k?
o 
e m qu e
s ão d e f i n i d a s (é j u s t a m e n te n e s s e c o m p a r t i l ha m e n t o qu e e s tá a d i fe r e n ç a p a r a o U n i x )
T a l c o m o o c o r r e n o U n i x
, 
o Jo r k é u m a f u n ção q u e r e to m a a i d e n t i f i c a ç ão ú n i c a da
t l l r e a d c D a d a e a c D a ç ão s e di a tr a v és de u m c o m a n d o de a t r i b u i ção d o t i p o
id : = fo r k o
p o r ém
, 
d i fe r e n te m e n t e d o qu e o c o r r e n o U n i x
, 
n o s i s te m a V a l e 4 a v a r i áv e l id é g lo ba l
(i s to é , é c o m p a r t i lha d a po r m ãe e f i l ha ) A s l l i r e a ds m ãe e f i l ha e x e c u t a m e m p a r a l e l o a pa r t i r do
c o m a r1d o q u e s e gu e a e s s a a t r i b u ição El a s i r ão s e d i s t in gu i r a t r a v és d e u m a v a r i áv e l d e n o m i n ada
m y s e l F 
2 1 0 v a l o r de s s a v a r i áv e l é s e m p r e a id e n t i f ic ação ún ic a de q u e m a r e f e r e (po de s e r t h r w d
o u p r o c e s s o ) T ip i c a m e n te , o u s o da f u n ção Tü r k s e gu e o s e g u i n te m o de l o (o b s e r v e q u e sd a
t h r e a d fi l ha e n c o n t r a a v a r i áv e l g lo ba l id ig u a l a o s e u m ys e lD
id Þ f or ko
\f id = m ys e lf t h e n \ p r o c e s s a n 1e n t o da j i lha \
e l s e { p r o c e s s a m e n t o da m a e }
I o A l i n gu ag e m V 4 i m p le m e n ta o c o n c e i to d e I t ¢ek c o i n s i n ta x e e se m an t i c a in s pi r a da s n a l in 吕 u se m A D A c o n fo m e
se r á v i s t o n o c a p í tu lo 12 B a s i c a m e n te u l T1a Iu ï k d u m b lo c o qu e c o n tëm i nt ernament e vavci s pm c c d i m e n to s e
u m a t h r e a d in i c i a l
, 
d e n o m i n a d a m a in A t r a v es de c o m a n d o s j i J r * , a th r e a d
po de m ra m bëm u s a r o c o ma n do Ju rk , o r i g i n a n d o a s s im u m a e s t r u tu r a de ûn o r ü n a I t u * N a r a i z da ar v o r e
i e m pr e a t h r ea d t m t i n a qu a l , po de s e d i z e r , e a ú l t i m a a n c e s t r a 】 de t o d a s as thr e a d r da t a s t
l 1 T u do s e pa s s a c o m o s e c a da pr o c e s s o o u i h r e a t l t i v e s s e u m a v a r i 4v e l l o c a l , d e n o m i n a da m y s e u c o n ten do o
n ú m e r o (in i c o dc s 1e p r o c e s s o o u t h r e a d Na v e rd a de M y # r (f e u m a ¢u n çüo pr i rn i t i v a qu e c o n s u l ta o r e 吕 i s tr o des a i lo r
do p r o c e 1 s o o u t h r e a d par a o b t e r o n k m e r o de 1 u a c a ï t c i r a de i de n dd a de e r e t o m a e s se n k m e m
Scanned by CamScanner
Ca pf t u l o 3 ' "SEi f i caçao d a C o n c o r r en c i a 3 1
Pa r a c r i a r p r o c e s s o s (n o t l zr e a ds ) d i n a m i c a m e n te
, 
a l in g u a ge m V4 o f e r e c e o c o m a n do
n e w q u e s e r á a p r e s e n t a d o n a s e ção q u e s e g u e E n q u a n t o o c o m a n do To rk c Da u m a t h r e a d fi lha
, 
o
c o m a n do n e w c r i a u m p r o c e s s o f i lh o
0 c o m a n d o j o i n ( id ) p e r m i te qu e u m p r o c e s s o o u 1h r e a d p e s pe r e pe l o tér m i n o do
d e s c e n d e n t e i m e d i a t o (f i l ho o u f i l h a ) ide n t i f i c a do po r id Se o a r g u m e n t o id n ão i de n t i f i c a u m
p r o c e s s o o u t h r e a d
, 
o u s e id n ão c o r r e s p o n de a u m d e s c e n de n te i m e d ia t o d e P , e n tão o c o r r e u m
e r r o de e x e c u ção C o n v ém o b s e r v a r q u e e s t a i m p le m e n t a ção d i f e r e d o c o m a n d o j o in o r i g i n a l
d e f i n id o p o r C o n w a y iC O N 6 3 ]
, 
o n de n ão há b l o q u e i o d o e x e c u t o r d o j o in
O a r g u m e n t o d e j o i n p o d e s e r t a m bém a p a l a v r a r e s e r v a d a a n y , q u e s i g n i f i c a o d e s e jo d e
e s p e r a r p e l o t ér m i n o d e q u a l q u e r u m d o s d e s c e n de n t e s i m e d i a to s N e s s e c a s o , n o r et or no da
pD m i t i v a , a v a r i áv e l a n y 
22 
v a i c o n t e r a i de n t i d a de do f i lho o u f i l ha c u j a e x e c u ção te r m i n o u
O u t r a p e c u l i a r i d a d e d a p r i m i t i v a j o in (id ) é qu e e l a p o de s e r u s a d a c o m o f u n ção o u c o m o
s u b r o t i n a U s a d a c o m o f u n ç o , e l a o b tém (r e t o m a ) o v a l o r q t t e o f+l h o o u f i l h a id e s p e c i f 1 c o u n o
c o m a n d o q u i t , a o m o r r e r , c o n f o r m e é e x p l i c a d o a s e g u i r
0 ú l t i m o c o m a n d o d o c o n j u n t o é o q u i t , q u e m a t a o s e u e x e c u t o r P o de m s e r u s a d a s a s
f o r m a s q u i t o u q u i t (X ) N o s e g u n do c a s o , o a r g u m e n t o X é u m v a l o r q u e o p r o c e s s o o u 1l i r e a d
i n f o r m a a o s e u g e n i t o r , a o m o r r e r Se d e s e j a r pe ga r e s s e v a l o r , o g e n i t o r u s a r á a p D m i t i v a j o i n ,
c o m o f u n ç ão
2 3 A p r o pó s i t o , u m q u i t s e m a r g u m e n t o e q u i v a l e a u m q u i t (0 )
3
. 
5 C r i a çã o e s t á t i c a e c r i a çã o d i n âm i c a d e p r o c e s s o s
O s p r o c e s s o s d e u m p r o g r a m a c o n c o r r e n te p o de m s e r c Da d o s 
de f o r m a e s tá t i c a o u d i n âm i c a N o
p Dm e i r o c a s o , o p r o g r a m a c o n tém a de c l a r a ção 
de u m c o n ju n t o f+x o d e p r o c e s s o s , o s q u a i s s o
a t i v a d o s s i m u l t a n e a m e n t e , n o i n i c i o d a e x e c u ção d o p r o g r a m a N o s e g u n do c a s o . o s p r o c e s s o s
s ão c r i a do s d i n a m i c a m e n t e , d u r a n te a e x e c u ção , a t r a v és de i n s t r u çõ e s e s pe c i a i s p a r a e s s e f i m
3
. 
5
. 
1 C r i a ção e s t á t i c a
N o c a s o da c r ia ç i lo e s tá t ic a , o s p r o c e s s o s s o 
de c la r a do s e x p l ic i t a m e n t e 
24 
n o p r o g r a m a f o n t e e
v ào e x i s t i r d e s de o i n íc i o da e x e c u ção do p r o g r a m a c o n c o r r e n t e N o r m a l m e n t e , a s 
l i n gu a ge n s de
p r o g r a m a ção pe r m i t e m e s pe c i f ic a r e s s e s p r o c e s s o s 
de d u a s m a n e i r a s : c o m o p r o c e s s o s
in d iv idu a is o u c o m o a r r a y de p r o c e s s o s
Bz Se m e lha n t e m e n t c a o qu e o c o r r e c o m m y s e u , tu do s e pa i s a co m o i e c a da pr o c e s s o 
o u i h r e a ¢l t i v e sse u m a v ar i t1v c l
lo c a l
, 
d c n o m i ï 1a da a n y 
aa N o c a s o de i e r u i a da c o m o eu b r o l in a a pr i m i t i v a j o 1n (1d) de 1c o m idc r a o w lo r in fo r m a do pe lo de sc e n de n te id
14 A decl anaçäo e . p l f r i ¢a c o m i r t e e m de f i n i r , pa r a c a da pro ce 1s o , in d iv idu a lm e n te , a s s u a s v a r iáv e is Io c a i s e o se u
1e w n t o de c t}d i go
Scanned by CamScanner
3 2 s i s t e m a s Ð i e r a c i o n a i s e Pr o g r a 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 SSi mi ,
E s p e c i& c a ç o d e p r o c e s s o s In d i v i d u a ls
N e s t e c a s o
, 
c a d a p r o c e s s o é e s pe c i f ic a d o de fo r m a i n d i v id u a l , c o n
fo r m e e x e m p l i f ì c a do a s e gu i r
V 4 p r o g r a m
p r o c e s s p 1
k i n t e ge r i n i t 0
w hi l e k < 10 d o
wnt e 1 L
k = k+ l
p r o c e s s P 2
k i n t e g e r i n i t 0
w h i l e k < 10 do
w r i t e (2 )
k = k+ 1
e n dp r o g r a m
O p r o g r a r n a d e f i n e 2 p r o c e s s o s , d e n o m i n a d o s P l e P 2 , q u e n ão c o m p a r t i l h a m v a r i áv e i s (n ão
e x i s te m v a r i áv e i s g l o b a i s n o p r o g r a m a ) C a d a p r o c e s s o u t i l i z a u m a v a r i áv e l l o c a l , d e n o m i n a d a k
O p r i m e i r o i m p r i m e I O v e z e s o n ú m e r o l e o s e g u n do , e m p a r a l e l o
, 
i m pD m e 10 v e z e s o n ú m e r o
2 0 r e s u l t a d o d a e x e c u ç ão p o d e s e r q u a l q u e r s e qü ên c i a d e t a m a n h o 2 0
, 
e n v o l v e n d o I O v e z e s o
n ú m e r o I e I O v e z e s o n úm e r o 2
, 
e m b a r a lha d o s T e o r i c a m e n t e
, 
s ão p o s s f v e i s 2 0 !/ ( 10 ! · 10 !)
r e s u l t a d o s d i fe r e n t e s 25
A r r a y d e p r o c e s s o s
N e s te c a s o
, 
u m a ún ic a de c l a r a ção e s pe c i f i c a u m g r u po de p r o c e s s o s s e m e l h a n t e s
, qu c s e
d i s t i n g u e m (i n ic i a l m e n te ) a pe n a s pe lo v a ] o r de u m a v a r i áv e l l o c a l i n te i r a
, qu e é e s pe c i f ic a da n o
c a be ç a l h o d o p r o c e s s o 
26
, 
c o n f o r m e é i l u s t r a do a s e g u i r , c o n s i d e r a n do o m e s m o e x e m p l o a n te r io r
V 4 p r o g r a m
p r o c e s s P (i : = 1 to 2)
k i n te g e r i n i t 0
w h i l e k < 10 d o
wr üei h
k = k+ 1
25 c o m b in a《ö e s dc u m a 1叫醒 n c i a de 2o e s c a n in ho 1
, 
e s c o lh ido s 1o a 1o
/ ( ì
26 N a de t i n i çäo de u m p r o c e s s o , s e o n o 1n e do p r o c e s so e s e gu ido de " ( v« r : = « l o « By , o n de K t ¢ & s l o- t a n t e s i n t e i r a s
, 
is t o s ig n i ti c a qu e v ao e x i s t i r K r K I + l i n s tan c ia 1 (c lo n ¢ 1) de s s e pr o c e s s o Ca da c lo n e te r a u rn av a r iáv e l i n t e ir a l o c a l De n o m i n a da Va r
, qu e l e ra in lc i a l i z ad a c o m u m v a lo r d is t in t o e n t r e K r c « B 
Scanned by CamScanner
C a p í tu l o 3 E s pe c i f1c a ção d a C o n c o r r en c ia 33
e n d p r o g r a m
Pa r a o pD m e i r o p r o c e s s o , a s u a v a r i áv e l l o c a l i v a l e 1 e p a r a o s e g u n do , a s u a v a r i áv e l l o c a l i
v a l e 2 E s t e p r o g r a m a é e q u i v a l e n te a o a n t e D o r
3 5 2 C r i a çã o d i n âm i c a
O s r n e c a n \s m o s c o
po i s o s p r o c e s s o s (o u t h r e a d s ) s ão c r i a d o s s o m e n te q u a n d o i n s t r u çõ e s e s p e c i a i s s ão e x e c u ta d a s 27
3 5 3 C r i a ç ã o d i n â m i c a c o m d e c l a r a ção e x p l f c i t a
T a mbém é p o s s f v e l u i a r d in a m i c a m e n t e p r o c e s s o s q u e s ão d e c l a r a d o s e x p l i c i t a m e n t e P a r a i s s o
o u s u ár i o E x p l i c i t a u m m o d e l o (t e 1n p ta t e ) d e p r o c e s s o , q u e é u t i l i z a do p a r a c r i a r c ó p i a s (c l o n e s )
d o p r o c e s s o d u r a n t e a e x e c u ç o N a l i n g u a g e m V a le 4 a d e f i n i ção d e u m m o d e l o é r e a l i z a d a
a t r a v és d a e s p e c i f i c a ção p r o c e s s 1pe , c o n f o r m e é i lu s t r a do a s e g u i r , c o n s i d e r a n d o o m e s m o
e x e m p l o a n t e k o r
2 s
V 4 p r o g r a m
p r o c e s s t y p e P ( i : i n t e ge r )
k i n t e g e r i n i t 0
w h i l e k < 10 d o
wr h e M
k = k + l
pr o c e s s q q n o me
n e w p ó n e w P 2
e n dp r o g r a m
p a r a c r i a r e x e m p l a r e s de u m m o de l o é u t i l i z a do o c o m a n do n e w , o qu a l pe r m i te pa s s a r
p a r âm e t r o s pa r a o p r o c e s s o c r i a do A p r i m i t i v a n e w po de s e r u s a
d a c o m o f u n ção o u c o m o
s u b r o t i n a u s a d a c o m o f u n ção e la r e t o m a a i de n t i f ic a ção i nt er na (p id) do p r o c e s s o c r i a da
3
. 
6 E x e m p l o s d e p r o g r a m a s c o n c o r r e n t e s
E s t a s e ç ão a p r e s e n t a p r o g r a m a s s im p le s qu e i lu s tr a m c a r a c te r f s t ic a s i m po r t a n te s do s p r o g r a m a s
c o n c o r r e n te s
, 
t a i l c o r m » c o m pa r t i lha m e n to de c ód igo e i m pr e v i s ib i l ida de de o r de m de e x e c u çüo
» p o r e x e m p lo , s c 1 e x c c u çao n ao
" pa l l a " po r u m a d e te r m in ada in s t r u çao To r t , e n t ao a i h r w ld c o n e spo n de n t e n ao e
c r i
» O1 r e s u l ta do s po s a fv e i r pa r a e s te p r o g r a m a sao o s m e s m o s do s do is e x e m plo s a n t eDo r e s
1
Scanned by CamScanner
34 s is t e m a s o pe r a
c io n a i s c pg gr a m n çl 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 S
. 
c ar i 1Bim i
(o u de e s c a l o n a n 1e n t o ) T r a t a m s e de p r
o g r a m a s V a l e 4 c o
m p l e t o s , q u e p o d e m s e r e x ec u t ado 1 n o
a m b i e n t e v 4 d i r e t a m e n te , s e m q
u a lq u e r m o d i f i c a ção
T a l c o m o j á v e m s e n d o f e i to , u sada a
s e gu in te n o t a ção p a r a m e l ho r a r 
a le g ib i l i da de do t e x t o 
o s n o m e s d o s e l e m e n t o s de c l a r ado l em
u m p r o 8 r a m a (v a r i áv e i s , p r o c e d i m e n t o s , e tc ) s
ão a p r e s e n t a do s e m i t ál
i c o
3
. 
6
. 
1 C o m p a r t i l h a m e n t o d e : 
u m p r o c e d i m e n t o
O m e s m o p r o g r a m a q u e fo i u t i l i z a do n a s e ção 
3 5 p a r a d i s t i n g u i r a s d i f e r e n te s m a n e i r a s de
e s pe c i f i c a r (e c r i a r ) p r o c e s s o s é r e e s c r i to pa r a i l u s t r a r o c o m pa r t
i l ha m e n t o d e u m pr o c e d im e n to
V 4p r o g r a m
p r o c e d u r e i m p r i m e (i : in te g e r )
k i n t e g e r i n i t 0
w h i l e k < 10 do
wnt ei h
k = k+ l
pr o c e s s P 1 i m p r i m e ( \ )
pr o c e s s P2 im p r i m e (2)
e n dp r o g r a m
C a d a p r o c e s s o c ha m a im p r i m e f or necendo o m o a r g u m e n t o o n ú m e r o a s e f i m pr esso
C o m o n o s e x e m p l o s a n te r i o r e s , o r e s u l t a d o da e x e c u ção de s s e p r o g r a m a é i m p r e v i s fv e l , sendo
po s s í v e i s ( te o k c a m e n te ) C£ r e s u l t a do s d i s t in t o s
O b s e r v a ç o s o b r e a s v a r i ¢iv e is d e u m p r o c e d i 1n e n t o
N o e x e 呷 l o a c i m e x i s te m du a s e x e c u çöe s c o n c o r r e n te s do p r o c e d im e n t o im p r im e . 
um a
e fe t u a da po r P / e o u tr a po r P2 C a da u m a de s s a s e x e c u çMe s u t i l i z a v a r i áv e i s i (a r gu n 1en to ) e 
t
(v a r i áv e l l o c a l do p r o c e d i m e n to ) A Observaç\o i m po r t a n te é q u e c a d a p r o c e s s o u t i l iz a cóp
ias
i n de pe n de n te s de s s a s v a r i áv e i s O c ód igo do p r o c e di m e n to é c o m p a r t i l ha do pe lo s do i s psso 
s1
m a s o s d a do s (v a r i áv e i s i e k ) s ão pDv a t i v o s de c a d a p r o c e s s o I s to 
, 
c a d a p r o c e sso t
r aba lha
so br e u m c o n j u n to de da do s s e p a r a do
N ão se po de e s q u e c e r qu e l n a c ha m a da de u m p r o c e d i r n e n t o , o s a r 吕 u m c
n tos e 
l s
v a r i áv e is lo c a i s de s se p r o c e d i m e n to s o a lo c a do s n a p i lha d o pr o c e s s o c ha m a do r c
o B+1o c
adi
Pr o c e s s o t r a b a lha c o m u m a p i lha própDa
, a e x e c u çäo de u m p r o c e s so n äo in te r f
br e c o i n
e x e c u çäo d o o u t r o N a p r o g r a m a çüo c o n c o r r e n te 
 s e m p r e a s s i m , to do pr o c ,
' " = da u to m a t ic a m e n te r e e n l r áv e 1 (o u p u r o ) Is t o s i 吕 n i f i c a qu e o m e s m o c ódig o po de s e r c x e
cu
') » "
Scanned by CamScanner
ó p l t u l o 3 E s p e c i f i c a çä o d a C o n c o r r en c ia 35
s i m u l t a n e a m e n t e p o r v ár i o s p r o c e s s o s s e m q u e ha j a q u a lq u e r i n te r f e r ên c i a e n t r e e le s C a da
p r o c e s s o u t i l i z a u m c o n j u n t o s e p a r a do de pa r âm e t r o s e de v a r i áv e i s lo c a i s
3 6
. 
2 C o m p a r t i l h a m e n t o d e u m a v a r i áv e l
O Pr o g r a m a a s e g u i r i m p l e m e n t a u m s i s te m a c o n c o r r e n te o n de d o i s p r o c e s s o s c o m p a r t i l ha m u m a
v a D áv e l g l o b a l S C a d a p r o c e s s o i n c r e m e n ta S de u m a u n i d a d e
, 
100 v e z e s
V 4 p r o g r a m
S : i n t e ge r i n i t o
p r o c e s s p 1
k i n t e g e r i n i t 0
1 o o p
S = S+ l
k : = k+ 1
e x i t w he n k = 10 0
e n d l o o p
n l ; w r i te ( ' p 1 ' ) ; t a b (2 ) ; w r i t e (S)
p r o c e s s p z
k i n t e g e r i n i t 0
l o o p
S = S+ 1
k = k + l ; \
e x i t w he n k = 100
e n d l o o p
n l ; w r i te ( ' p2 ' ) ; t a b (2 ) ; w D te (S)
e n dp r o g r a m
E s s e p r o g r a m a p o de s e r e s c r i to de f o r m a m a i s c o n c i s a u t i l i z a n do o s c o n c e i to s de a r r a y
de p r o c e s s o s o u d e m o d e l o (1e m p ta 1e ) d e p r o c e s s o , o qu e é de i x a d o c o m o e x e r c fc io
C o m o S é i n i c i a l i z a d a c o m z e r o , i s t o s ig n i f i c a qu e o v a l o r f i n a l de S d e v e (o u de v e Da )
s e r 200 C o n t u d o
, 
o r e s u l t a d o f i n a l (ú l t i m o v a l o r a t r i bu :d o à v a r i áv e l S) po d e r á s e r q u a lq u e r v a l o r
e n t r e 2 e 20 0 (c e r t i f i q u e s e d i s to ) , e e s s e r e s u l t a d o i r á v a r ia r de u m a e x e c u çüo pa r a o u t r a
E s t e p r o g r a m a u t i l i z a o s c o m a n d o s l o o p , n l e 1a b (K ) , o s qu a i s s ào a p r e s e n t a do s a s e gu i r
Scanned by CamScanner
36 s i s t e m a s Operaci onai s e p r o gr a m a çüo Co 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 Sr si mi
0 c o m a n d o l o o p
0 c o m a n do to o p i m B»le m e n t a u m c ic lo in f in i t o N o s e
u i n te ri o r , o c o m a n do " e x i t w he n < c o n d» "
s ign i f i c a qu e o c i c lo a c a b a (i s to é , qu e a e x e c u ção v a i pa r a o c o m a n do s e gu in te a o e n dlo o p)
q u a n do a c o n d i ção < c o n d> é v e r d a de i r a Es te c o m
a n do p o de s u b s t i t u i r t o do s o s de n 】a i ,
c o m a n d o s i t e r a t i v o s (w h i l e
, 
r ep e a t , To r , e tc ) , c o m a v a n t a g e m de , e m ge r a l , t o m a r o s pr o gr a ïnas
m a i s c l a r o s
0 c o n 1a n d o n l
0 c o m a n d o n l ( ' h e w l i n e " ) f a z c o m gu e a p r ó x i m a i m p r e s s ão s e j a fe i t a e m u m a n o v a l in ha
0 c o m a n d o t a b m
E s te c o m a n do e s c r e v e K e s p a ço s e m b r a n c o n o t e f m i n a l do u s u áD o , s e n do ú t
i l p a r a f o r m a tar a
i m p r e s s ão d e r e s u l ta do s
0 c o n 1 a n d o w r i te (X )
E s te c o m a n d o e s c r e v e o v a l o r de X n o t e r m i n a l d o u s u ár i o O a r g u m e n t o X p o d e s e r u m a
c o n s t a n t e
, 
u m a v a r i áv e l
, 
u m e l e m e n t o de a r r a y o u u m s t r in g e n t r e a pó s t r o f e s
I n i c i a l i z a çã o d e v a r i l i v e i s
E m V 4
, 
a s v a r i áv e i s n ão e x p l i c i t a m e n t e i n i c i a l i z a da s , p o s s u e m v a l o r i n i c i a l z e r o , s e i n te i r a s , o u
Ta l s e , s e b o o l e a n a s
A c l áu s u l a i n i t ia l (o u in i t ) de v e s e r s e g u id a de u m ún i c o v a l o r in i c i a l Se e s t a c l áu su la é
u s a d a n a de c l a 】a ção de u m a l i s t a de i de n t i f i c a do r e s , e n tão to d o s o s i de n t i f ic a do r e s da l ista
r e c e b e m e s s e v a l o r i n i c i a l Se a c l áu s u l a é u s a da n a de c l a r a ção de u m a r r a y , to do s o s e le m en to s
do a r r a y r e c e b e m e s s e ún ic o v a l o r e sp e c i f i c a do
3
. 
6
. 
3 C r i a çã o d i n âm i c a d e t ll r e a ds
O e x e m p l o a s e g u i r i l u s t r a a c Da ção d in âm ic a de t l ï r e a d s O p r o g r a m a ga r a n te a o rde
n açäo
e spe c i f i c a d a r l o g r a fo de f l u x o de p r o c e s
a
S 0 S 
:
. 
b 
I 
X 
2 
p3 
p 
5
Scanned by CamScanner
Ca p ft u l o 3 E s pe c i f1c a çäo d a C o n c o r r en c ia 37
V 4 p r o g r a m
p r o c e s s p
k2
, 
k4 : i n te g e r
k2 : = f o r k
i f m y s e l f - k2 the n {n l ; w D te ( ' p2 ' ) ; u i t }
n l ; w r i te ( ' p l ' )
k4 = fo r k
i f m y s e l f - k4 t he n {n l ; w r i t e ( ' p4 ) ; q u i t }
n l ; w r i t e c p3 ' )
j o i n (k2 )
j o i n (k4 )
n l ; w r i t e ( ' p5 ' )
e n d p r o g r a m
N e s t e p r o g r a m a , a t h r e a d i n i c i a l do p r o c e s s o P de s e m p e n h a o p a p e l d o s p r o c e s s o s p l ,
p 3 e p 5 d o g r a f o I n i c i a l m e n t e , o p r o g r a m a p o de r á i m p r i m i r o s s t r i n g s p l
'
o u
' p2
'
,
i n d i f e r e n t e m e n t e A p ó s ' p l ' t e r s i do i m p r e s s o , p o de r ão s e r i m p r e s s o s
'
p 3
'
o u
' p 4 Só a pó s ' p 3 ' ,
' p 4 1 e ' p 2
' t e r e m s i d o i m p r e s s o s é q u e s e r á i m p r e s s o o s t r i n g
'
p5
'
3
. 
6
. 
4 C r i a çã o d i n â m i c a d e p r o c e s s o s
O e x e m p l o a s e g u i r i l u s t r a a c D ação d in âm i c a de p r o c e s s o s a t r a v és do p r o b l e m a c l ás s i c o da t o r r e
de H a n ó i
, 
d e s c D to a s e g u i r T e m s e 3 t o r r e s (p i l h a s ) e n d i s c o s d e t a m a n h o s d i fe r e n te s
I n i c i a l m e n t e o s n d i s c o s e s t ão e m p i l h a d o s n a t o r r e 1, n a o r d e m c e r t a (m a i o r n a b a s e , m e n o r n o
t o p o ) O p r o b l e m a c o n s i s t e e m m o v i m e n t a r t o do s o s d i s c o s p a r a u m a de t e r m i n a d a t o r r e , s e m qu e
n u n c a u m d i s c o m a i o r f i q u e s o b r e u m d i s c o m e n o r O s d i s c o s de v e m s e r t r a n s po r t a do s de u m e m
u m e a t e r c e i r a to r r e p o d e s e r u s a d a c o m f » in t e r m e d iár i a n e s s a s m o v i m e n t a çõe s
O p r o g r a m a i n i c ia c o m o p r o c e s s o P c r i a n do u m f i l ho (e s c r a v o ) H a n o i pa r a m o v i m e n t a r
3 d i s c o s da t o r r e I p a r a a to r r e 2 , u s a n do a t o r r e 3 c o m o i nt er medi \ r i a Pa r a m o v i m e n t a r n d i s c o s
d e a p a r a b , u s a n do c c o m o t o r r e in te r m e d iár i a , u m e s c r a v o H a n o i f a z o s e g u in te Se n - 1 (s ó
t e m u m d i s c o p a r a m o v i n 1e n t a r ) , e n tão o t r a b a l ho é f ác i l e d i re to o e s c r a v o 1n o v i m e n t a o ún ic o
d i s c o d e a p a r a b (e m o s t r a e s s a m o v i m e n t a çao ) C a s o c o n t r úr i o , o e s c r a v o c r i a u m e s c r a v o 1
p a r a m o v i m e n t a r n 1 d i s c o s de a pa r a c , u s a n do b c o m o to r r e i n te r m e d i li r i a , Qu a n do e s se se r v iço
 c o n c l u :do (e sc r a v o 1 te r m i n a o s e u t r ab a l ho ) , o e s c r a v o o r i g in a l m o v i m e n t a o d i s c o qu e l he
s o b r o u (q u e o m a i o r ) de a p a r a b (m o s t r a e s s a m o v i m e n t a çao ) e c Da u m e s c r a v o 2 pa r a
c o n c l u i r o s e r v i ç o , qu e m o v i m e n t a r n l d i s c o s de c pa r l b u s a n do iB c o m o t o r r e i n te r m e d i & i a
Scanned by CamScanner
+
38 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 çl o Co 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 S tn i
V 4pn »g r a m
p r o c e s s t ype H a 11o l (n , a , b , a i n t e ge r )
i d
, 
m in t e ge r
i f n = 1
t he n { n l : w r i te (a ) ; w Dt e ( ' > ' ) ; w r i te (b ) }
e l s e ( m = n l
id = n e w H a n o i (m
, 
a
, 
c
, 
b ) ; j o i n (id )
n l ; w r i t e (a ) ; w r i te ( ' > ' ) : w r i t e (b )
id = n e w H a n o i (m
, 
c
, 
b
, 
a ) ; j o i n (id )
p r o c e s s P n e w H a n o i (3 , 1, 2 , 3 )
e n dp r o g r a m
O r e s u l t a do d a e x e c u ção de s t e p r o g r a m a s e r á a o r de m e m q u e o s d i s c o s de v e r ão se r
m o v i m e n t a d o s (m o v i m e n t o p o r m o v i m e n t o , u m d i s c o p o r v e z )
3
. 
7 E X E R C I C l O S
E x e r c i c i o 3 1 M o s t r e q u e a s c o n s t r u çMe s c o b e g in / c o e n d e " ; " p o d e m s e r e x p r e s s a s a t r a v és das
f u n çõ e s S e P
E x e r c íc i o 3 2 U s a n d o a s p r i m i t i v a s To r k , j o i n e q u i t d e fi n i d a s p o r C o n w a y , e s pe c i f iqu e a
: ' " Æ s o s p
l
, p2 . , p o ' " ê . c i ' ' " t r a d.
E x e r c fc 1o 3
. 
3 E s pe c i fi qu e o g r a fo do e x e r c fc i o a n te r i o r
, 
u t i l i z a n do a s p r i rTri t i v a s To r k, j o in 
e
qu h da Hn g u a ge m V 4
E x e r c fc i o 3A (a ) O g r a fo d a s e ç o 3 6 3 6 p r o pr i a m e n te a n in ha do ? (Ju s t i f i q u e ) 
(b ) O g r a fo do e x e r c íc io 3 2 é p r o p r i a m e n te a n in ha do ' B ¡ u s ( i f i qu e ) 
E x e r c fc i o 3 5 u m p r o g r a i r ra do r w d i s s e qu e d ig i to u e e x e c u t o u o p r o g r a m a da s e gäo 
3 6 3 ¢
q u e f o r a m e s c r i t a s n o v fde o do s eu t e r m i n a l a s se s u in te s l i n ha s I s to po de r e a l m e n te a c o n
tec er ?
Scanned by CamScanner
Ca p i t u lo 3 Es pe c i t i c a çao da C o n c o r r en c ia 39
Li n h a s i m p r e s s a s
Wn ha e m br anco
p4 p3
p5
E x e r c fc i o 3 6 R e e s c r e v a o p r o g r a m a da s e ção 3 6 2 u t i l i z a n do (a ) a r r a y de p r o c e s s o s
(b ) m o d e l o (re m p ta t e ) de p r o c e s s o (c ) u m p r o c e d i m e n t o qu e i n c r e m e n t e 10 0 v e z e s a v a r i áv e l S
E x e r c íc i o 3 7 N o p r o g r a m a e x e m p l o da s e ção 3 6 2 , s e r i a p o s s ív e l a i m p r e s s ão da s l i n h a s a
s e g u i r , n e s t a o r d e m ? (Ju s t i f i qu e a r e s p o s t a )
h n h a L p l
l i n h a 2 : p2 100
E x e r c íc i o 3 8 C o n s i d e r a n d o a i n d a a e x e c u ç ão d o p r o g r a m a d a s e ção 3 6 2 , m o s t r e u m a o r de m
d e e x e c u ç ão p a r a o s p r o c e s s o s q u e f a ça c o m q u e o v a l o r f in a l de S (ú l t i m o v a l o r a t r i b u íd o à
v a r i áv e l S ) s e j a 2
E x e r c íc i o 3 9 N o p r o g r a m a d a t o r r e d e H a n ó i , s e ção 3 6 4 , o m o d e l o d e p r o c e s s o p r e c i s a
e s p e r a r p e l o t ér m i n o d o e s c r a v o 2 ? l i s t o é , n a s e q ü ên c i a
" id = n e w H a n o i (m
, 
c
, 
b
, 
a ) ; j o i n (i d y ' , o
c o m a n d o " j o i n ( idy ' é r e a l m e n t e n e c e s s ár i o ?) Se a c h a r q u e n ão , t e s t e o p r o g r a m a s e m e s s e j o i n
p a r a o c a s o d e 4 d i s c o s e c o n f i r a o r e s u l t a d o d a e x e c u ç ão
E x e r c : c i o 3 10 A s e g u i n t e c o d i f i c a ção p a r a o p r o g r a m a d a t o r r e de H a n ó i é c o m t a ? O q u e
a c o n t e c e D a s e o c o m a n d o do p r o c e s s o P f o s s e
"
n e w H a n o i ( 1
, 
1
, 
2
, 
3 7" ?
V 4 p r o g r a m
p r o c e s s t yp e H a n o i (n , a , b , c i n t e g e r )
id
, 
m i n t e g e r
i f n - 2
t he n { n l ; w r i t e (a ) ; w r i t e ( ' > ' ) : w r i te (c )
n l : w r i t e (a ) : w r i t e ( ' > ' ) ; w r i te (b )
n l ; w r i te (c ) ; w r i te ( ' > ') : w r i t e (b)
e l s e { m = n l
id = n e w H a n o i (m
, 
a
, 
c
, 
b) : j o in (id )
n l ; w r i te (a ) ; w r i te ( ' > ' ) : w r i te (b )
id = n e w H a n o i (m , c , b , a ) ; j o in (ld )
p r o c e s s P n e w 村a n o i(3 , l , 2 , 3)
e n dp r o g r a m
W 
p l
Scanned by CamScanner
U i f 
:h
.
i
.
' $ï : !
/ .^ & '
G c i iB i r .Bl 1
: t 5 r
4/ Ë
, 
þ
i # 1.$: : / t
:?ì · y b / <
A/ Yf >ï Bt ! /È-( $/ >/ ' 4?
( . j ¢j U: } : å> A l ï y 1
M a r t fn F i e r r o El 1n o r e n o
T o da t u s a b idu r f a No ga 1o pe qu e ha y a u j e r o s
, t ' Tf t
ha s de m o s t r a r e s t a v e z
. 
Ià .
Ie d ij o a u n gu a po u n pr u de n t e
¢- s ó lo qu e e s tës le c o n t e s t o hu m i lde m e n t e
e n v a c a c o n a lgún 1a n l o i ï , la n o c he po r c a n to t i e n e : 
1a n o c he t ie n e s u c a n t o p e s e s r u ido s qu e u n o s ie n te
y m e ha s de de c i r c u ál e s Rin s a be r de dó n de v ie n e n ;
So n lo a s e c r e to s m i s t e r i o s
: 
qu e 1a i t in ie b lu e sc o n de n
a o n lo s e c o s qu e r e s po n de n
a la v o z d e l qu e da u n * Dt o
c o m o tm l a m e n to i n f i n i to 
4j /JU $ : qu e v ie n e n o 1d de dón de$, i î T