Buscar

4o_Semana_-_Controle_de_Concorrencia_II

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 20 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 20 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 20 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

Facili
qual
proto
mos
adia
distr
bloq
seja
trans
trans
mod
term
bloq
em 
prim
relaç
indu
resp
Logo
ação
de T
obje
tador: Prof. 
mas N
quer adiçã
ocolo não
traremos q
Uma im
nte, deixa
ribuídas. A
8.3.4 C
Mostra
ueio em d
, o problem
Record
sação é o 
sação. Sej
delada por
minem em E
Defina
Tj se 
ueio de Tj
De fat
particular,
meiro foram
ção sobre 
Consid
zida por L
Supon
pectivamen
o, existe u
Y. Pel
o Bi(x) de 
Tj terá qu
tos, uma a
Instituto F
Msc. Marcos
N não sati
ão de bloq
o são n
que são su
mplementa
ando para
Antes, poré
Correção
aremos ne
duas fases
ma de term
de que o b
ponto do 
ja E uma e
r um esc
E e que ela
a uma rela
e somente
. Provarem
to, como E
 induz um
m executad
T. 
dere agora
. Mostrare
nha que Ti
nte, tais q
um objeto 
la condiçã
Ti terá que
e precede
ação Li(Z) 
M
Federal de Ed
Univ
Dis
s Vinicius Sad
sfará ao p
queios / lib
necessárias
uficientes).
ação centr
a a Seção
ém, convém
o do Proto
sta seção
 é serializ
minação é
banco é ce
escalonam
execução c
calonamen
as sigam o
ção em T 
e se o po
mos que (1
E induz u
ma ordem
das pelas
a a relaçã
mos agora
i < Tj. Entã
ue Oi(X)
X 
ão 1 do p
e precede
er Oi(X).
de Ti tal q
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
protocolo 
berações.
s para s
ralizada de
o 8.4 a a
m provar a
ocolo de
que toda
ável, se to
é suposto r
entralizado
mento em 
concorrent
to L. Sup
o protocolo
tal que Ti
onto de blo
) é uma re
ma ordem
total para
transaçõe
ão de pre
a que (2) se
ão existem
e Oj(Y) c
protocolo d
r Oi(X) e,
Pelo proto
que x 
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 26 
de bloque
Logo as c
serializaçã
este proto
apresentaç
a correção
Bloqueio
execução
odas as tr
resolvido p
e que o p
que se dá
te de um c
ponha qu
o de bloque
oqueio de
elação de o
m total das
a o conjun
s. Esta últ
cedência 
e Ti < Tj e
m ações O
conflitam e
de bloquei
da mesma
ocolo de 
ologia do Par
sil 
II 
eio em dua
condições 
o (na se
colo será 
ção de im
o do protoc
o em Duas
o concorren
ransações 
por outros m
onto de bl
á a primeira
conjunto T
e todas 
eio em dua
e Ti preced
ordem tota
s ações da
nto das aç
tima, por s
por conflit
ntão Ti Tj 
Oi(X) e Oi(X
e Oi(X) p
io em dua
a forma, u
bloqueio 
ra – IFPA 
as fases, 
impostas 
eção seg
discutida 
mplementa
colo. 
s Fases 
nte seguin
terminam
métodos. 
oqueio de 
a ação L(x
T de transa
as transa
as fases. 
de o pont
l em T. 
as transaç
ções L(X)
sua vez, ge
to, <, sob
(X) de Ti e
precede O
as fases, 
uma ação 
/ liberação
para 
pelo 
uinte 
mais 
ações 
ndo o 
m. Ou 
uma 
x) da 
ações 
ações 
to de 
ções, 
 que 
era a 
bre T 
e T j, 
Oj(Y). 
uma 
Bj(x) 
o de 
 
Facili
bloq
do p
suce
pont
uma
exec
Bloq
em 
Assu
caso
seja
área
pont
term
toda
uma
bloq
são 
trans
bloq
até 
trans
capí
fato,
ante
tador: Prof. 
Z terá 
ueio de Ti
protocolo d
eder Bj(x). 
to de bloqu
Finalm
a relação 
cução E é 
8.3.5 U
queio em
Esta s
duas fa
umiremos 
o centraliz
, as modif
a de traba
to a trans
minar corre
as as mod
a implemen
1) as a
ueio B(x), 
2) se a
a) todo
bloqueado
b) apó
sação são 
3) se 
ueados sã
Note q
o final da
sação. Est
ítulos em q
 suponha 
es da trans
Instituto F
Msc. Marcos
que suce
Ti terá que 
de bloquei
Logo, po
ueio de Tj e
mente, com
de ordem
serializáve
Uma Imp
m Duas Fa
seção apre
ases que
que o m
ado é um
ficações a
alho até q
sação pod
etamente, 
ificações n
ntação pos
ações de 
para cada
a transação
os os obje
os antes q
ós a ação 
liberados.
a transa
ão liberado
que nesta 
a transaçã
ta impleme
que uma t
que a libe
sação term
M
Federal de Ed
Univ
Dis
s Vinicius Sad
eder Oi(X)
preceder o
o em dua
r transitivi
em L. Assi
mo, por (1),
m parcial. 
el, como se
lementaç
ases 
esenta um
e é com
modelo de
ma simplific
a serem ef
que a tran
derá canc
sendo g
no banco
ssível de bl
leitura R(x
a X ; 
o foi proce
etos que ti
ue a ação 
W(x) ser e
 
ação é ca
os. 
implemen
ão, ou sej
entação é
ransação 
eração de
minar. Se
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
e precede
ou coincid
as fases, o
dade, o p
m, Ti Tj . 
é uma rela
Logo pelo
e queria de
ção Centr
ma implem
mpletamen
processa
cação daq
fetuadas n
nsação co
celar, desc
erado ent
de dados
loqueio em
x) implicita
essada nor
iveram se
de atualiza
executada
ancelada, 
ntação os
ja, o pont
coerente c
pode ser c
objetos cu
a transaç
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 27 
er Bj(x). P
dir com Li(Z
o ponto de
ponto de b
ação de or
o Teorem
emonstrar.
ralizada d
entação d
nte transp
mento de 
uele desc
nos objetos
omplete o
cartando-s
ão uma 
de forma
m duas fase
mente ger
rmalmente
u valor mo
ação final 
, todos os
todos os
objetos sã
to de bloq
com o cen
cancelada
ujo valor fo
ção for can
ologia do Par
sil 
II 
or definiçã
Z). Mas, p
e bloqueio 
bloqueio de
rdem total, 
a 1 da S
 
do Protoc
do protoco
parente a
transaçõe
crito na Se
s são man
o processa
se as mo
ação W(x)
atômica. 
es seria 
ram uma a
: 
odificado p
seja execu
s objetos a
 objetos 
ão mantid
queio se d
nário previs
durante a
oi alterado
ncelada a
ra – IFPA 
ão, o pont
pela condiç
de Tj terá
e Ti prece
temos que
Seção 8.2
colo de 
lo de bloq
aos usuá
es adotad
eção 8.1.2
ntidas em 
amento. N
odificações
x) para ins
Neste cen
ação prévi
pela trans
utada. 
acessados 
que man
os bloque
dá ao fina
sto nos últ
a execução
 seja perm
pós libera
to de 
ção 2 
á que 
ede o 
e < é 
.4, a 
queio 
ários. 
o no 
2. Ou 
uma 
Neste 
s, ou 
stalar 
nário, 
ia de 
ação 
pela 
tinha 
ados 
al da 
timos 
o. De 
mitida 
r um 
 
Facili
obje
que 
tives
trans
cent
fase
banc
posi
corre
proto
será
proc
mod
exec
conf
trans
um a
distr
banc
do a
cent
bloq
uma
conc
do s
ser p
tador: Prof. 
to que alt
ser cance
ssem termi
sação pod
Isto co
tralizado. 
8.4 M
Esta s
s e algori
cos de dad
cionament
eção desta
ocolo de b
á omitido. 
Em to
cessadas 
dificações s
cute um co
firmar inte
sação, ou 
8.4.1 I
Por im
ambiente d
ribuída junt
co de dado
acesso ao
tralizado 
ueio/libera
a técnica d
corrência d
Os ped
eguinte es
1. um 
processada
Instituto F
Msc. Marcos
erou, toda
eladas tam
inado, e as
eria provo
onclui a dis
ÉTODOS
eção discu
itmos para
dos distribu
to da tabe
as impleme
bloqueio e
odas as i
conforme 
são armaz
omando FI
nsões é i
rejeitá-las,
Implemen
mplementaç
distribuído 
to com os 
os local, h
os objetos 
e geren
ação de o
de bloque
do banco d
didos de b
squema: 
bloqueio B
a localmen
M
Federal de Ed
Univ
Dis
s Vinicius Sad
as as outra
mbém e as
ssim recur
car cancel
scussão so
 BASEAD
ute implem
a deteção 
uídos. As 
ela de bloq
entações s
em duas f
mplementa
descrito 
zenadas em
IM-DE-TRA
invocado 
, canceland
ntação Bá
ção básica
entendere
dados. M
haverá tam
locais. E
ciada po
bjetos. De
eios, nada 
distribuído, 
bloqueio/libB(x) é cria
nte, para c
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
as transaçõ
suas mod
rsivamente
amentos e
obre o pro
DOS EM B
mentações
de bloqu
implement
queios ao
segue dire
fases para
ações ass
na Seção
m uma áre
ANSAÇÃO
para insta
do a transa
ásica 
a do protoc
emos aque
ais precisa
mbém uma
Esta tabela
or uma 
esta forma
mais é n
exceto de
beração sã
ado imedia
ada x X; 
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 28 
ões que le
dificações 
e. Ou seja,
em cascata
otocolo de 
BLOQUEIO
do protoc
eios mútu
tações dife
longo da
etamente d
a o caso c
sume-se q
o 8.1.2. E
ea de traba
O, quando 
alar as mo
ação. 
colo de blo
ela em que
amente, pa
 tabela de
a é implem
cópia lo
a, se os S
necessário
eteção de b
o gerados
tamente a
ologia do Par
sil 
II 
eram aque
desfeitas, 
 o cancela
a de outras
bloqueio 
OS - PAR
olo de blo
uos em um
erirão esse
rede. O 
da prova d
centralizad
que as tr
Em particu
alho até qu
o protocol
odificações
oqueio em 
e a tabela 
ara cada n
e bloqueios
mentada c
ocal do 
SGBDs loc
o fazer pa
bloqueios m
s automatic
antes de um
ra – IFPA 
ele valor te
mesmo q
amento de 
s transaçõe
em duas f
RTE II 
queio em 
m ambient
encialment
argumento
de correçã
do e, port
ransações 
ular, todas
ue a trans
o bifásico 
s criadas 
duas fase
de bloque
nó onde há
s para con
como no 
protocolo 
cais já usa
ra control
mútuos. 
camente de
ma leitura 
eriam 
ue já 
uma 
es. 
fases 
duas 
te de 
te no 
o de 
ão do 
anto, 
são 
s as 
ação 
para 
pela 
s em 
ios é 
á um 
ntrole 
caso 
de 
avam 
e de 
entro 
R(X) 
 
Facili
PRE
obje
PRE
não 
insta
ou a
dos 
trans
conh
repre
proc
para
cópi
exist
conc
por 
são 
men
idéia
tal fo
dado
daqu
parti
do s
loca
corre
tador: Prof. 
2. um 
EPARE_SE
to x que re
3. uma
EPARE_SE
foram mo
4. um
aladas no 
após o nó 
objetos q
sação; 
É inte
hecimento 
esentam 
cessador d
a que toda
a, o novo 
tência de 
corrência. 
8.4.2 I
A impl
bloquear t
escassos 
nsagens, p
a é simple
orma que 
os. Para c
uela partiç
ição, a cóp
Os ped
eguinte es
1. An
lmente em
X é 
espondent
Instituto F
Msc. Marcos
bloqueio 
E ser receb
eside local
a liberação
E ser receb
dificados p
a liberaçã
banco, ca
ter recebi
ue residem
eressante 
da existê
cópias d
de comand
as as cópia
valor será
cópias to
Implemen
ementação
todas as c
e é vantaj
pode-se op
s. Suponh
os objeto
cada partiç
ção. Ante
pia primári
didos de b
squema: 
tes de u
m i, uma me
enviada 
te à x. O 
M
Federal de Ed
Univ
Dis
s Vinicius Sad
B(x) é c
bida na pr
lmente e c
o L(X) é c
bida na pr
pela transa
ão L(X) é
aso o nó te
do uma m
m localme
observar
ência de c
do mesm
dos da LM
as sejam a
á enviado d
orna-se tr
ntação po
o distribuíd
cópias de u
joso econo
ptar pela
hamos que
s em cada
ção, desig
s de ace
a correspo
bloqueio/lib
uma ação
ensagem p
ao nó
nó j tenta
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
riado imed
rimeira fas
cujo valor fo
criada ime
imeira fas
ação; 
 criada a
enha rece
mensagem 
ente e cuj
que a i
cópias. Se
o dado
MD e ao g
atualizada
durante o
ransparent
or Cópias
da de certa
um mesmo
omizá- los
implemen
e os objeto
a partição
gne um ob
ssar qualq
ondente de
beração sã
o Rk(X) d
para bloqu
j que
 bloquear
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 29 
diatamente
e do proto
oi modifica
ediatament
e do p loc
após as m
bido uma
CANCELE
os valores
implement
e porventu
em nós 
erente de 
s. Para ca
protocolo
e ao mec
s Primária
a forma de
o objeto ló
em troca
tação usa
os físicos e
 represent
bjeto físico
quer objet
everá ser b
o gerados
da transaç
uear cada
mantém
xp para T
ologia do Par
sil 
II 
e após um
ocolo bifás
ado pela tra
te após um
calmente e
modificaçõe
mensagem
E, onde X
s foram mo
tação acim
ura os obj
diferente
transaçõe
ada nó on
bifásico. A
canismo d
as 
esperdiça 
ógico. Se r
de um ma
ando cópia
estejam pa
tem cópias
o como a 
to físico e
bloqueada.
 automatic
ção Tk se
objeto x 
a cópia 
Tk e, após 
ra – IFPA 
ma mensa
sico, para 
ansação; 
ma mensa
e cujos va
es terem 
m CONFIR
X é o conj
odificados 
ma não 
jetos x1 ,.
es, caberá
es provide
de reside 
Assim send
de controle
recursos lo
recursos lo
aior tráfeg
as primária
articionado
s dos mes
cópia prim
em uma 
. 
camente de
er proces
primária
obter suce
agem 
cada 
agem 
lores 
sido 
RME, 
junto 
pela 
toma 
.., xk 
á ao 
nciar 
uma 
do, a 
e de 
ocais 
ocais 
go de 
as. A 
os de 
smos 
mária 
dada 
entro 
sada 
a xp 
esso, 
 
Facili
envi
até q
PRE
cópi
cada
prim
trans
PRE
o co
valo
insta
ou a
toda
mod
loca
Poré
ser 
tráfe
obje
para
cont
reso
mes
bloq
em l
defin
tamb
bloq
nece
tador: Prof. 
a uma me
que todas 
2. um 
EPARE_SE
a x cujo v
a objeto 
mária xp co
sação, não
3. uma
EPARE_SE
onjunto de
res não fo
4. um
aladas no 
após o nó t
as as cóp
dificados pe
Note q
l em cad
ém, para s
enviada a
ego maior n
A últim
tos físicos
a cada pág
tém a cóp
olver este 
mo nó e
ueio hiera
ugar de pá
nido na arq
8.4.3 I
Em a
bém é dis
ueios mút
essário co
Instituto F
Msc. Marcos
ensagem a
as cópias
bloqueio 
E ser rece
valor foi m
tem que 
orresponde
o havendo 
a liberação
E ser receb
e todas a
ram modifi
a liberaçã
banco, ca
ter recebid
pias primá
ela transaç
que, ao b
a nó tend
se ler a c
o nó j (ex
na rede ap
ma observ
s for peque
gina a ser
ia primária
problema 
m uma s
arquizado. 
áginas. De
quitetura d
Implemen
mbas as 
stribuída a
tuos mais 
onsultar to
M
Federal de Ed
Univ
Dis
s Vinicius Sad
ao nó i co
s tenham s
B(x) é c
bida na pr
modificado
ser igual
ente a x
necessida
o L(X) é c
bida na pr
as cópias 
icados pela
ão L(X) é
aso o nó te
do uma me
rias que
ção; 
bloquear a
de a dimin
cópia arma
xceto se i=
penas para
vação adq
ena. Por e
r lida uma
a daquela
seria agr
só mensa
Por exem
e qualquer
o sistema.
ntação po
implemen
ao longo 
difícil pois
odos os 
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
onfirmando
ido bloque
riado imed
rimeira fas
pela tran
mente alt
será aut
ade de bloq
criada ime
rimeira fas
primárias 
a transaçã
 criada a
enha rece
ensagem C
residem l
apenas a
nuir pois
azenada e
=j ). Porta
a controle d
quire maio
exemplo, s
mensagem
página, o
rupar vário
gem. Um
mplo, segm
r forma, o c
 
or Bloque
ntações a
da rede. 
s, para se 
nós em 
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 30 
o o bloque
eadas. 
diatamente
se do proto
sação (co
teradas pe
tomaticam
queá-la ex
ediatament
se do proto
que resid
ão; 
após as m
bido uma
CANCELE,
ocalmente
cópia prim
menos bl
em i, uma 
anto, esta 
de concorr
or peso s
se os obje
m teria qu
que é ina
os pedido
a segund
mentos inte
conceito de
eio Centra
nteriores, 
Esta opç
construir 
que uma
ologia do Par
sil 
II 
io. A ação
e após um
ocolo bifás
omo todas 
ela transa
mente bloq
xplicitamen
teapós um
ocolo bifás
dem localm
modificaçõe
mensagem
onde X é
e e cujos 
mária, o p
oqueios s
mensagem
implement
ência. 
se a gran
etos físicos
e ser envi
aceitável. U
s de bloq
a solução
eiros seria
e "cópia" d
alizado 
a tabela 
ção torna 
o grafo d
a parte d
ra – IFPA 
o Rk(X) es
ma mensa
sico, para 
as cópia
ação, a c
queada pa
nte); 
ma mensa
sico, onde
mente e c
es terem 
m CONFIR
é o conjunt
valores fo
processam
são realiza
m extra de
tação gera
nularidade 
s são pág
ada ao nó
Uma form
queio para
o seria ad
am bloque
deve estar 
de bloqu
a deteção
e espera, 
a tabela 
spera 
agem 
cada 
s de 
cópia 
ara a 
agem 
e X é 
cujos 
sido 
RME, 
to de 
oram 
mento 
ados. 
everá 
a um 
dos 
ginas, 
ó que 
a de 
a um 
dotar 
ados 
bem 
ueios 
o de 
será 
está 
 
Facili
arma
los e
atrae
coor
obje
coor
impl
será
a fac
bloq
ser f
prob
outro
conc
loca
vuln
perd
as tr
novo
ser r
banc
impl
sem
caso
obse
em 
pode
Uma
trans
dois 
foi s
que 
d < d
tador: Prof. 
azenada. S
e resolvê-lo
ente. 
Na im
rdenador d
to que for 
rdenador, 
ementação
á omitida. 
Esta im
cilidade de
ueios resid
feita localm
blemas da 
os. Prime
corrência é
lizada na 
erável a fa
dida ou o n
ransações 
o nó coord
reiniciado. 
co de d
ementação
8.4.4 T
O trat
elhante ao
o centraliz
ervação ad
que a tra
erão receb
a solução c
sação, ond
nós não 
submetida.
uma trans
d'. 
Instituto F
Msc. Marcos
Se bloquei
os rapidam
mplementa
da rede pa
acessado,
que resp
o é bastan
mplementa
e deteção/
de em um 
mente. Por
implement
eiro, o tr
é canaliza
rede. Se
alhas envo
ó coorden
correntes 
denador de
Isto signif
dados dis
o. 
Tratamen
tamento d
o caso ce
zado tam
dicional se
ansação fo
ber a mesm
consagrad
de n é o n
têm o me
 Uma tran
sação que 
M
Federal de Ed
Univ
Dis
s Vinicius Sad
os mútuos
mente, uma
ação por 
ara conter
, uma men
ponderá e
nte semelh
ação oferec
/resolução 
único nó. A
r outro lado
tação base
ráfego ad
ado para o
egundo, e
olvendo o n
ador por a
terão que 
everá ser 
fica que vá
stribuído 
nto de Blo
de bloque
ntralizado.
mbém se
e refere à
oi submeti
ma priorida
a consiste
úmero do
esmo núme
nsação qu
recebeu o
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
s são muito
a terceira 
bloqueio 
r toda a ta
nsagem de
então ao 
hante à d
ce como va
de bloque
Assim, a c
o, esta imp
eada em c
icional de
o nó coord
e mais g
nó coorden
algum motiv
ser cance
completad
árias das v
simplesme
oqueios M
eios mútuo
. As técnic
aplicam 
geração d
da. Como
ade em nós
e em adota
nó onde
ero) e d é
ue recebeu
o par (n',d')
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 31 
o frequente
implement
centraliz
abela de b
 bloqueio d
nó que 
o bloqueio
antagem, c
eios mútuo
construção 
plementaçã
ópias prim
e mensag
denador, g
rave, a i
nador. Se 
vo não pud
eladas e um
do antes do
vantagens
ente perd
Mútuos n
os no ca
cas preve
ao caso
de prioridad
o há vário
s diferente
ar o par (n
ela foi sub
é a data/ho
u o par (n
) se e som
ologia do Par
sil 
II 
es e é nec
tação alter
zado, eleg
bloqueios. 
deverá ser
solicitou o
o por cópi
conforme j
os pois tod
do grafo d
ão apresen
márias, acre
gens para
gerando um
implement
a tabela d
der ser con
m protocolo
o processa
s advindas 
dem o s
o Caso D
aso distrib
ntivas disc
o distribu
des atravé
os nós, du
es dentro d
,d) como a
bmetida (a
ora em qu
n,d) terá p
ente se n 
ra – IFPA 
cessário de
rnativa torn
ge-se um
Para qua
r enviada a
o bloqueio
as primári
já mencion
da a tabel
de espera 
nta os mes
escidos de
a controle
ma sobrec
tação é m
e bloqueio
ntactado, t
o de eleiçã
amento no
do uso de
sentido n
Distribuíd
buído é m
cutidas pa
ído. A ú
és da data/
uas transa
deste esqu
a prioridad
assume-se
ue a trans
rioridade m
< n' ou n =
etetá-
na-se 
m nó 
lquer 
ao nó 
o. A 
ias e 
nado, 
la de 
pode 
smos 
e dois 
e de 
carga 
muito 
os for 
todas 
ão do 
ormal 
e um 
nesta 
o 
muito 
ara o 
única 
/hora 
ações 
ema. 
de da 
e que 
ação 
maior 
= n' e 
 
Facili
impl
mere
loca
Natu
com
mútu
impl
local
bloq
cham
bloq
subg
bloq
nó i
loca
entã
com
o nó
que 
se in
árvo
mes
mun
esta
cons
loca
subg
filhos
subg
nós 
seu 
tador: Prof. 
Já a d
ementação
ece comen
l de blo
uralmente 
pleto o sej
uos apena
ementar d
Seja N
l a N ao
ueios res
maremos 
queio mútu
grafo de e
ueio mútu
A imp
i que con
l a i e en
ão o grafo
o no caso 
O méto
ó central e
chamarem
nicialmente
ore (para p
mo munic
nicipais em
dual e ass
strói o sub
l, e tenta d
grafo para 
s, e após c
grafos e te
da subárv
pai e assim
8.5 M
Instituto F
Msc. Marcos
deteção/re
o básica 
ntários esp
oqueios g
cada um d
ja. Em out
as localme
eteção de
N um con
o subgraf
sidentes 
de grafo 
uo local a
espera loca
o gerado p
lementaçã
tém uma 
nviá-lo par
o de espe
centraliza
odo anterio
e cujas folh
mos de algo
e que os n
propósitos 
cípio são 
m um mes
sim por di
bgrafo de e
detetar e re
o seu pai
construir o
nta deteta
ore cuja ra
m por dian
ÉTODOS
M
Federal de Ed
Univ
Dis
s Vinicius Sad
esolução d
ou pela im
peciais. O
gera apen
destes sub
tros termos
ente. O re
 bloqueios
njunto de
fo do gra
em nós
de espe
a N a um
al a N. Ch
por um cic
ão mais si
tabela de
ra um nó
era global,
do. 
or na verd
has são os
oritmo hier
nós da red
 do algori
todos filh
mo estado
iante. Peri
espera loc
esolver blo
i. Um nó i
o seu próp
r bloqueios
aiz é n; em
te até a ra
 BASEAD
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
de bloquei
mplementa
O problema
nas um
bgrafos po
s, não é p
esto desta
s mútuos n
nós. Cha
afo de es
pertencen
era global
m bloqueio
hamaremo
clo do grafo
mples con
e bloqueios
central de
 detetand
ade induz 
s outros n
rárquico, g
de estejam
itmo apen
hos de um
o são por 
iodicament
cal a f, ba
oqueios mú
nterior n, 
rio subgraf
s mútuos l
m seguida, 
iz. 
DOS EM P
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 32 
os mútuos
ação atrav
a básico e
subgrafo
oderá ser a
ossível faz
a seção d
neste caso
maremos
spera indu
ntes a N
l. Similarm
o mútuo g
os de bloq
o de esper
nsistiria em
s construi
esignado.
o e resolv
uma árvo
nós. Uma s
generaliza 
 logicamen
as). Por e
m mesmo
sua vez 
te (e sincr
seando-se
útuos locai
ao recebe
fo local, fa
ocais a N, 
envia o su
PRÉ-ORD
ologia do Par
sil 
II 
s, quando
vés de cóp
stá em qu
do grafo
acíclico se
zer deteçã
discute du
. 
de subgra
uzido pela
N. Ao g
mente, ch
gerado po
queio mútu
ra global. 
m, periodic
r o subgr
O nó cen
vendo blo
re de altur
segunda im
esta obser
nte organiz
exemplo, o
o nó mun
filhos de 
ronamente
e na tabela
s a f; em s
er os subg
az a união 
onde N é 
ubgrafo co
ENAÇÃO
ra – IFPA 
o se opta 
pias primá
ue cada ta
o de esp
em que o g
ão de bloqu
uas formas
rafo de es
as tabelas
rafo com
hamaremos
r um ciclo
uo global a
camente, 
afo de es
ntral const
queios mú
ra 2, cuja r
mplementa
rvação. Su
zados em 
os nós de
nicipal, os 
um mesm
e), cada fo
a de bloqu
seguida en
rafos dos 
de todos eo conjunto
onsolidado 
O 
pela 
árias, 
abela 
pera. 
grafo 
ueios 
s de 
spera 
s de 
pleto 
s de 
o no 
a um 
cada 
spera 
ruiria 
útuos 
raiz é 
ação, 
upõe-
uma 
e um 
nós 
o nó 
olha f 
ueios 
nvia o 
seus 
estes 
o dos 
para 
 
Facili
banc
e em
às 
trans
segu
proto
que 
trans
conc
o p
conf
em E
que 
sobr
trans
difer
de s
é im
proto
em d
exec
seria
se a
exec
pass
orde
não 
da i
banc
tador: Prof. 
Esta s
cos de dad
m seguida v
8.5.1 P
Como 
transações
sações. M
uinte forma
1. Cad
ocolo, únic
2. Em 
garante q
sações sã
A cor
corrente de
protocolo d
flito sobre 
E na ordem
a senha d
re o conjun
sações), o
O prot
rente do p
serialização
mposta "a 
ocolo de p
duas fases
cução con
alizável e q
as transaçõ
cução conc
sa como 
em em qu
é imposta
intercalaçã
cos locais. 
Instituto F
Msc. Marcos
seção disc
dos distribu
várias imp
Protocolo
o nome in
s, e dev
Mais prec
a: 
da transaç
ca ao longo
cada nó 
que as aç
o process
rreção de
e um conj
de pré-or
T induzid
m de senh
de Tj. Logo
nto das tra
o que impli
tocolo de 
protocolo d
o das trans
posteriori
pré-ordena
s, recordem
ncorrente 
que a exe
ões em or
corrente E
se as tr
e atingira
a "a prior
ão mais o
M
Federal de Ed
Univ
Dis
s Vinicius Sad
cute contro
uídos. Inic
lementaçõ
o de Pré-O
ndica, nes
ve ser res
isamente,
ção ao ser
o da rede, 
há um me
ções conf
adas em o
ste protoc
unto T de
rdenação.
a por E. C
a, temos q
o, < é nec
ansações 
ica que E
pré-orden
de bloquei
sações é i
". Esta o
ação. Para
mos que a 
E seguind
ecução ser
rdem dos
E, os usuá
ransações
m os seu
ri", depend
ou menos
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
ole de con
cialmente o
ões discutid
Ordenaçã
te protoco
speitada
o protoc
r iniciada 
de forma t
ecanismo
flitantes (v
ordem de 
colo é im
transaçõe
Seja :f/lt
Como as a
que se Ti <
cessariame
(pois as s
é serializá
nação age
o em duas
imposta "a
bservação
compreen
prova de c
do o bloq
rial S equiv
seus pont
rios do sis
fossem
us pontos 
dendo da p
 fortuita d
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 33 
ncorrência 
o protocolo
das. 
ão 
olo uma or
pela exec
colo de p
recebe um
transparen
de contro
veja Seção
senha. 
mediata. S
es. Suponh
t/ a relaç
ações con
< Tj então a
ente uma r
senhas imp
ável. 
e então d
s fases po
a priori", en
o está cla
ndê-la mel
correção d
queio em
valente a 
tos de bloq
stema tem
executada
de bloque
própria din
das ações
ologia do Par
sil 
II 
por pré-o
o genérico 
rdem é imp
cução co
pré-ordena
ma senha 
nte aos usu
ole de con
o 8.2.4) 
Seja E u
ha que E 
ção de pr
nflitantes s
a senha de
relação de
põe uma o
e forma c
ois, no prim
nquanto qu
ra no que
lhor no cas
deste indic
duas fas
E é obtida
queio (em
a ilusão d
as seqüe
eio. Porém
nâmica das
s element
ra – IFPA 
ordenação 
é apresen
posta "a p
ncorrente 
ção opera
ou númer
uários. 
corrência 
geradas p
uma exec
tenha seg
recedência
são execut
e Ti é meno
e ordem pa
ordem tota
completam
meiro, a or
ue no seg
e concern
so de bloq
a-nos que 
ses é sem
a processa
 E). Assim
de que tud
ncialmente
m, esta or
s transaçõ
ares sobr
para 
ntado 
priori" 
das 
a da 
ro de 
local 
pelas 
cução 
guido 
a por 
tadas 
or do 
arcial 
al às 
mente 
rdem 
undo 
e ao 
queio 
toda 
mpre 
ando-
m, na 
do se 
e na 
rdem 
ões e 
e os 
 
Facili
orde
orga
para
sem
seria
vário
(isto
harm
sem
porta
alter
na s
de s
mes
pode
trans
cons
as a
estra
são 
entre
tador: Prof. 
É inte
enação e 
anizados) e
a ser atend
 interrupçã
ais. O cas
os pedidos
 é, o p
monizar to
pre a ilus
anto, não r
As pr
rnativas do
8.5.2 I
Na imp
eção ante
A impl
senhas ao
mo núme
eremos us
sação se o
A imp
struir um m
ações con
atégia pod
mantidas d
R_sen
senha 
W_sen
senha 
O me
elaçament
1) se a
Instituto F
Msc. Marcos
eressante f
uma disc
em que o c
dido. Se h
ão, a situa
o interess
s de vário
próprio pro
odo o trab
ão de que
reclame do
róximas s
o protocolo
Implemen
plementaçã
rior. 
ementação
o longo da
ero de sen
sar como 
originou e d
lementaçã
mecanismo
nflitantes 
deria ser us
duas variá
nha(x) 
da última 
nha(x) 
da última 
ecanismo 
to das açõe
a operação
M
Federal de Ed
Univ
Dis
s Vinicius Sad
fazer tamb
ciplina às 
cliente, ao 
houver ape
ação se tor
ante acon
os clientes
otocolo d
balho de t
e foi atend
o aparente
subseções
o de pré-o
ntação Bá
ão básica,
o do prime
a rede sej
nha. Para
senha o p
d é a data/
ão do seg
o de contr
são proce
sada neste
veis: 
operação 
operação 
de con
es elemen
o é uma lei
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
bém uma a
vezes us
chegar, a
enas um e
rna equiva
tece quan
ao mesm
de pré-ord
tal forma 
dido antes
e caos reina
desta s
rdenação e
ásica 
 o protoco
eiro passo
a tal que
a tal, conf
par (n,d) o
/hora em q
undo pass
role de co
essadas e
e caso. Pa
R(X) que a
W(X) que 
ntrole de 
tares em u
itura R(X) c
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 34 
analogia e
sada em 
panha um
empregado
alente a pe
ndo vários
mo tempo.
denação)
que o clie
s do cliente
ante). 
seção dis
em um am
lo opera ex
do protoc
duas tran
forme disc
onde n é 
que a trans
so é bem
oncorrência
em ordem
ara cada o
acessou o 
acessou o
concorrê
um dado nó
com núme
ologia do Par
sil 
II 
entre o pro
estabelec
a senha e 
o e o clien
ermitir apen
empregad
 A discipl
deve ne
ente com 
e com sen
cutirão im
mbiente dist
xatamente
colo exige 
nsações n
cutido na 
o número 
sação foi su
mais difíc
a local qu
 de senh
objeto físic
objeto 
o objeto 
ência que
ó seria o s
ero de senh
ra – IFPA 
otocolo de
cimentos (
aguarda a
te for aten
nas execu
dos atende
ina de se
ecessariam
senha i t
nha j, se i<
mplementa
tribuído. 
e como des
que a ger
não receba
Seção 8
do nó on
ubmetida. 
cil pois re
ue garanta
ha. A seg
co x do sist
e control
seguinte: 
ha s então
 pré-
(bem 
a vez 
ndido 
ções 
em a 
nhas 
mente 
enha 
<j (e, 
ações 
scrito 
ração 
am o 
.4.4., 
nde a 
equer 
 que 
uinte 
tema 
a o 
: 
 
Facili
entã
X. 
para
ante
orde
e m
esca
que 
esta
atua
R_se
se q
das 
para
Supo
solu
diret
que 
tador: Prof. 
a) faça
X. 
b) se w
X. 
c) caso
2) se 
ão: a) faça 
X. b) fa
c) se m
a cada x 
X. d) c
As tran
es. 
Esta i
em de senh
odelada p
alonamento
Oi conflita
s ações co
alização). C
enha(x) < 
ueria dem
Há trê
variáveis 
a confirmar
Para o
onhamos, 
ção cons
tamente na
X ape
a ação R(
Instituto F
Msc. Marcos
a w igual a
w<s, então
o contrário
a operaçã
r igual ao 
aça w igua
max(r,w)<s
caso contrá
nsações re
implement
ha. De fato
por um es
o local de 
a com Oj. 
onflitam). S
Como Oi p
sj. Logo, O
onstrar. O 
ês problem
R_senha 
r intensões
o primeiro
inicialmen
iste em a
a página x
enas para 
(X) ou W(X
M
Federal de Ed
Univ
Dis
s Vinicius Sad
o maior W
o processe
o, rejeite a 
ão é uma
maior valo
alao maior
s, então pro
ário, rejeite
einiciadas 
tação corr
o, seja E u
calonamen
L com se
Seja x um
Suponha q
precede Oj
Oi e Oj for
caso em q
mas ainda
e W_senh
s, e proble
o destes
nte, que o
armazenar
x. Esta solu
obter o v
X) venha a
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
W_senha(x)
a leitura e
leitura e re
atualizaçã
or de R_sen
r valor de W
ocesse a a
e a atualiza
recebem u
retamente 
uma execu
nto global 
enhas si e 
m objeto ac
ue Oi é um
j, temos c
ram proces
que Oi é u
com esta
ha, relacio
emas de te
problemas
s objetos
r as vari
ução força
valor de R
a ser rejeit
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 35 
 para os o
e faça R_se
einicie a tra
ão W(X) c
nha(x) par
W_senha(x
atualização
ação e rein
um número
processa
ução segui
L. Sejam
sj. Supon
cessado p
ma leitura (
omo resul
ssadas em
ma atualiz
a impleme
onamento c
rminação.
s, duas s
físicos se
áveis R_s
a o protoco
R_senha(x)
tada. Se a
ologia do Par
sil 
II 
bjetos x 
enha(x) = s
ansação. 
com núme
ra os objeto
x) para os 
o, e faça W
nicie a tran
o de senha
 ações c
indo esta i
m Oi e Oj 
nha que O
por Oi e Oj
(logo Oj te
tado dos t
m ordem d
ação é aná
entação: a
com o pro
soluções s
ejam págin
senha(x) 
olo a ler ca
) e W_sen
a percenta
ra – IFPA 
s, para cad
ro de sen
os x 
objetos x 
W_senha(x)
sação. 
a maior do
conflitantes
implement
ações em
Oi precede 
j (x existe 
m que ser 
testes que
e senha, c
álogo. 
rmazenam
otocolo bifá
são suger
nas. A prim
e W_senh
ada página
nha(x), me
agem de a
da x 
nha s 
) = s, 
o que 
s em 
tação 
m um 
Oj e 
pois 
uma 
e si < 
como 
mento 
ásico 
ridas. 
meira 
ha(x) 
a x 
esmo 
ações 
 
Facili
rejei
os a
proc
tabe
W_s
adic
sem
simp
mais
estru
usad
usad
é lid
leitu
simp
sele
sem
é ex
adic
orde
Assi
se o
um 
tador: Prof. 
tadas for 
acessos à
cessamento
Uma s
ela à parte
senha(x) e
ional seria
 acessar 
plesmente 
s elaborado
Mais 
uturas de d
R_tabe
contém
dos W_tab
contém
dos R_max
maior v
W_ma
maior v
As tab
do, um par
ra. Se j
plesmente 
cionado d
pre o par 
xpurgado d
No ent
ional, pois
enação. P
m, ao expu
A impl
obter o va
par (x,r) e
Instituto F
Msc. Marcos
baixa, este
às página
o das açõe
segunda so
e um cert
e "esquec
a economi
as próp
esquecer 
o. 
precisame
dados: 
ela 
m pares (x
ela 
m pares (x
x 
valor de R
ax 
valor de W
belas são 
r (x,s) é a
á houver
substituíd
de acordo 
que foi ref
da tabela, 
tanto, o pa
s a senha
Para conto
urgar (y,t),
lementaçã
alor de R_
em R_tabe
M
Federal de Ed
Univ
Dis
s Vinicius Sad
e custo ad
as são d
es. 
olução par
to número
cer" os va
zada e os
prias pág
valores d
ente, a so
x,R_senha
x,W_senha
R_senha(x)
W_senha(x)
gerenciada
dicionado
r um pa
do por s.
com algu
ferenciado
dando luga
ar (y,t) não 
a t de y
ornar este
 faz-se R_
o do proto
_senha(x),
ela, r é to
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
dicional se
e qualque
ra o prime
o de valo
alores ma
s valores d
inas. Nat
de senha, 
olução pr
a(x)) para
a(x)) para 
 que foi ex
) que foi ex
as da seg
a R_tabe
ar (x,s') 
Se R_tab
uma polític
o pela últim
ar a (x,s).
pode ser a
é neces
 problem
_max := ma
ocolo é m
pesquisa-
omado com
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 36 
rá pequen
er forma 
iro problem
res das v
ais antigos
das variáv
turalmente
o que for
roposta ba
os objeto
os objeto
xpurgado d
xpurgado d
guinte form
la, onde s
em R_tab
bela estive
ca como,
ma vez há
abandonad
sária para
a, a variá
ax(R_max,
odificada d
-se a R_ta
mo o valo
ologia do Par
sil 
II 
no no côm
necessári
ma seria m
variáveis 
. Desta fo
veis estaria
 que nã
rça a usar
aseia-se 
os x mais 
os x mais
de R_tabel
de W_tabe
ma. Quand
s é a senh
bela inicia
er cheia, u
por exem
 mais tem
do sem qu
a o proto
ável R_m
,t) . 
da seguint
abela prim
or de R_s
ra – IFPA 
puto total, 
os ao pr
manter em 
R_senha(
orma, mem
am dispon
ão é pos
r um esqu
nas segu
 recentem
 recentem
a 
ela 
do um obje
ha da açã
almente, 
um par (y
plo, selec
mpo. O par
ualquer cui
ocolo de 
ax é man
te forma. 
eiro. Se e
senha(x). C
pois 
óprio 
uma 
(x) e 
mória 
níveis 
ssível 
uema 
uintes 
mente 
mente 
eto x 
ão de 
s' é 
y,t) é 
ionar 
r (y,t) 
dado 
pré-
ntida. 
Para 
existir 
Caso 
 
Facili
cont
verd
trata
gara
Poré
W_m
suge
arma
proto
men
proc
trans
são 
atrav
exec
vota
PRE
tal, o
faze
PRE
rece
terá 
que 
proc
e p
W_s
o va
tador: Prof. 
trário, tom
dadeiro de 
amento de 
Assim 
antirão que
ém, algum
max são u
erida aqui 
azenar R_
Passe
ocolo bifás
Sabem
nsagens de
cessamento
sação dev
enviadas 
vés de açõ
cutadas. P
r SIM o
EPARE_SE
o mecanis
r os teste
EPARE_SE
ebida, e nã
Além d
que gara
nenhuma
cessar PRE
processar 
senha(x) pa
, para 
X, qua
lor correto
X. Com
, para 
Instituto F
Msc. Marcos
ma-se R_m
R_senha(
W_senha(
sendo, o
e ações c
mas ações 
uma estima
representa
_senha e W
mos agor
sico. 
mos que 
e PREPA
o da trans
ve ser ace
em segu
ões de atu
Portanto, a
ou NÃO)
E chegar e
smo de co
es necessá
E (que dev
o ao proce
disto, uma
antir que W
a ação R
EPARE_S
W(X). E
ara 
todo x 
ando PREP
o depois de
m W_senh
todo x 
M
Federal de Ed
Univ
Dis
s Vinicius Sad
max como
(x) neste s
(x) é seme
os testes 
conflitantes
serão rej
ativa cons
a então um
W_senha ou
ra para o s
durante
RE_SE sã
sação. Des
eita ou can
uida para
ualização W
a decisão
 deverá
e não quan
ntrole de c
ários à ac
verá vir co
essar W(X)
 vez que u
W(X) será
R(Y) ou W
SE poderá
Esta regr
PARE_SE
e processa
ha(x) = 
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
o valor d
segundo ca
elhante. 
aplicados
s são pro
jeitadas de
ervativa d
m balanço
u reiniciar 
segundo p
a primei
ão enviad
sta forma o
ncelada. S
que os n
W(X), que
de aceitar
ser tom
ndo W(X) 
concorrênc
ceitação d
om o núm
). 
um nó vot
á necessar
W(Z) que 
ser execu
ra pode
for aceito,
ar W(X), pa
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 37 
de R_sen
aso é men
s na imple
ocessadas
esnecessa
e R_senh
entre gas
transações
problema, 
ira fase
as para c
o protocolo
Se aceita, 
nós atualiz
necessari
r ou rejeit
mada qua
for efetiva
cia local d
de W(X) q
mero de se
ou SIM ac
riamente e
invalide
utada entre
ser impl
 e atualiza
ara todo x
ologia do Par
sil 
II 
nha(x). Not
nor ou igua
ementação
em orde
ariamente 
a e W_sen
star menos
s com mai
o relacion
do proto
cada nó p
o bifásico 
mensagen
zem o ba
riamente te
ar W(X) (
ndo a m
amente pro
deve ser m
quando a 
enha e o c
ceitando a 
executada
a decisã
e receber 
lementada
ando-se W_
ra – IFPA 
te que o 
al a R_ma
o corretam
em de se
pois R_m
nha. A sol
s memória 
s freqüênc
amento co
ocolo bifá
participante
determina 
ns CONFI
nco de d
er&aoi. que
implicando
mensagemocessada. 
modificado 
mensagem
conjunto X
transação
. Isto sign
ão tomada
PREPARE
a mudand
W_senha(x) 
valor 
ax. O 
mente 
enha. 
max e 
ução 
para 
cia. 
om o 
ásico, 
e do 
se a 
IRME 
ados 
e ser 
o em 
m de 
Para 
para 
m de 
X) for 
o, ele 
nifica 
a ao 
E_SE 
do-se 
para 
 
Facili
form
que 
conf
e W
luga
solu
açõe
cont
reini
ocor
a ou
trans
repe
com
qual
toda
Ti irá
senh
prefe
sua 
seçã
subm
Exis
de t
seqü
Ti j+1
esta
Note
erros
exist
mútu
reini
com
tador: Prof. 
X, toda
ma de imple
a regra
ações co
flitem com
W(X). Tais 
r de serem
ções pode
es. 
Finalm
texto desta
iciada cicl
rrem quan
utra ação c
sação Ti c
etida com a
A solu
 uma nov
quer outra
as as açõe
á necessar
ha de Ti 
erível apen
chance d
ão, isto s
metida. 
A polít
te a possi
al forma a
üência de 
1 (soma m
s transaçõ
e que esta
s de sincr
te uma for
uo se form
ciar tran
pletamente
Instituto F
Msc. Marcos
as as açõe
ementar 
a seria co
m número
m W(X) se
ações fica
m rejeitada
erão ser c
mente é n
a impleme
licamente. 
do uma a
com que c
com uma 
a mesma s
ução para 
va senha t
a transaçã
es de Ti pa
riamente t
possua 
nas increm
e terminar
significa ad
tica de aum
ibilidade d
a causar o
transaçõe
módulo m).
ões, corre
a é a contr
ronização 
rma simple
mar: basta
sações. 
e o problem
M
Federal de Ed
Univ
Dis
s Vinicius Sad
es que con
mbinar blo
o de senh
ejam proce
ariam bloq
as como n
ombinadas
ecessário 
entação um
De fato,
ação chego
conflita. A
senha ma
senha fatal
este prob
tal que sej
o process
assarão pe
erminar. N
esta prop
mentar a se
r. Dentro d
diantar o 
mento de s
o process
o reinício
s Ti 0 ,Ti 1
. Se o au
-se o risc
ra-partida d
é basead
es de min
a randomi
Este esq
ma de rein
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
nflitam com
oqueios co
ha maior d
essadas in
queadas at
na solução
s usando 
examinar
ma transaç
 neste p
ou "atrasa
única form
aior do qu
mente ser
blema con
ja garantid
ada conco
elos testes 
No entanto
priedade e
enha de T
do método
relógio lo
senha aind
amento de
mútuo de
 ,..., Ti m-1
umento da
o de se r
de bloqueio
da no rein
nimizar a c
zar o inc
quema si
nício cíclico
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 38 
m W(X) ser
om as senh
do que a
ndevidame
té que W(
o anterior.
mudança 
r o proble
ção Ti pod
protocolo,
ada", por a
ma de corr
ue a ante
rá reiniciad
nsiste em
damente m
orrentemen
do protoc
, como não
em um a
Ti. suficient
o de gerar
ocal do nó
da tem um
e várias tr
todas ela
,Ti 0 tal qu
a senha fo
repetir a s
o mútuo qu
nício de t
chance de
remento d
imples na
o, mas o to
ologia do Par
sil 
II 
rão rejeitad
has de tal 
senha de
nte entre 
W(X) fosse e
Na verda
de senha 
ema de te
derá não t
erros de 
assim dize
rigir um er
rior (se a 
da novame
reiniciar a
maior do q
nte com T
colo o que
o é simple
ambiente 
emente pa
r senhas p
ó onde a 
outro fator
ransações 
as. Ou sej
ue Ti j forç
or o mesm
situação in
uando a fo
transações
uma situa
dado às s
aturalment
orna pouco
ra – IFPA 
das. Uma o
forma a e
e W(X) e 
PREPARE
executada
de, estas 
para bloq
erminação
terminar s
sincroniz
er, com rel
rro é reinic
transação
nte). 
a transaçã
ue a senh
Ti. Desta fo
e significa 
es impor q
distribuído
ara aumen
proposto n
 transaçã
r determin
sincroniza
a, cria-se 
ça o reiníci
mo para t
ndefinidam
orma de co
s. No ent
ação de rei
senhas qu
te não 
o provável.
outra 
evitar 
que 
E_SE 
a, em 
duas 
quear 
. No 
e for 
zação 
ação 
ciar a 
o for 
ão Ti 
ha de 
orma, 
que 
que a 
o, é 
ntar a 
nesta 
o foi 
ante. 
ar-se 
uma 
io de 
todas 
ente. 
orrigir 
anto, 
início 
ando 
evita 
 
 
Facili
dest
senh
nunc
cont
simp
lógic
emb
açõe
para
man
loca
envi
as fi
cont
com
toda
conf
impl
impl
outro
esco
não 
relac
ocor
tador: Prof. 
8.5.3 I
Uma s
ta feita be
ha, quer e
ca seja r
trole de co
plicidade. P
co, ou seja
bora possa
es element
Nesta 
a cada ge
ntidas duas
R_fila(
l enviados 
W_fila
ados por g
Exige-
las R_fila(
trole de co
1. espe
2. es
pletamente
A pro
as as açõe
flitam o são
Fazend
ementação
ementação
o lado, im
olha de um
(daí o nom
O pro
cionamento
rre nesta 
Instituto F
Msc. Marcos
Implemen
segunda fo
em simples
elas conflit
rejeitada. 
oncorrênci
Por esta ra
a, a nível 
a ser conv
tares como
implemen
erente de 
s filas: 
(g) fila con
por gvpar
(g)vfila co
g para o nó
se que um
g) e W_fila
ncorrência
ere até que
scolha o 
e. 
ova de cor
es são pro
o. Logo, ca
do uma b
o conser
o básica, 
mplicitamen
m comando
me de impl
oblema le
o com o 
implemen
M
Federal de Ed
Univ
Dis
s Vinicius Sad
ntação Co
orma de i
s, seria pro
tem ou nã
Como nã
ia pode s
azão esta
dos subco
vertida par
o todas as 
ntação, em
transaçõe
ntendo os 
ra o nó i; 
ntendo os 
ó i; 
m gerente d
a(g) em or
a procederi
e todas as
subcoma
rreção des
ocessadas
aímos no c
breve com
rvativa é
nunca fo
nte bloque
o se deu n
lementaçã
evantado
protocolo 
tação, sen
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
onservat
implement
ocessar a
ão, mas d
ão há ne
ser feito a
será a ún
omandos
ra atuar a
outras. 
m cada nó 
es g que 
subcoma
subcoma
de transaç
rdem de se
ia da segu
s filas conte
ando com
sta implem
em ordem
caso geral
mparação
 mais
orça trans
eia transaç
na ordem
o conserva
na impl
bifásico p
ndo resolv
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 39 
iva 
tar o proto
s ações lo
de tal form
cessidade 
a nível lóg
ica implem
atuando s
a nível físi
i onde o 
envia su
ndos que 
ndos que 
ções g env
enha. Loca
inte forma
enham alg
m menor 
mentação 
m de senh
 do métod
com a im
simples 
sações a
ções pois
correta, q
ativa). 
lementaçã
para confi
vido de fo
ologia do Par
sil 
II 
ocolo de p
ocalmente 
ma que u
de detet
gico ou fís
mentação d
sobre os o
co, ou sej
banco é 
ubcomando
apenas lê
modificam
vie os subc
almente, o 
: 
um coman
senha 
é muito s
ha, em pa
o de pré-o
mplementa
e, ao
serem re
sempre g
uer ele ge
o anterio
rmar inten
orma sem
ra – IFPA 
pré-ordena
em ordem
uma trans
tar conflito
sico com 
descrita a 
objetos lóg
ja, a nível
armazena
os para i 
êem do b
m o banco 
comandos 
mecanism
ndo; 
e proces
simples. C
rticular as
ordenação.
ação básic
contrário 
einiciadas. 
garante q
ere conflito
or acerca
nsões tam
melhante. A
ação, 
m de 
sação 
os, o 
igual 
nível 
gicos, 
l das 
ado e 
são 
anco 
local 
para 
mo de 
sse-o 
Como 
s que 
 
ca, a 
da 
Por 
ue a 
os ou 
a do 
mbém 
Além 
 
Facili
dest
caus
simp
com
perio
com
trans
do n
subm
adic
arma
prop
pode
maio
nenh
não 
Natu
decis
men
é re
obje
Uma
man
Qua
prec
força
com
dado
obje
tador: Prof. 
te, a imple
sa problem
O prot
plesmente 
ando para
Para 
odicamente
unicam in
sações (q
nó onde a 
metida). 
Esta s
ional entr
azenado, 
porções. Pa
erá enviar 
or do que
hum subco
precisa s
uralmente, 
são, caso 
nor do que8.5.4 I
Nas d
ejeitada se
to que ela
a forma d
nter uma s
nto maior 
cisa estar d
a do meca
Consid
 todas as 
os serão e
R_seq
to x. 
Instituto F
Msc. Marcos
ementação 
mas de com
tocolo, co
porque 
a i, o que p
resolver e
e enviar m
ndicando 
ue no esq
transação
solução, p
re os ger
que pode
ara solucio
uma men
e a sua c
omando co
ser repetid
deverá 
g tenha n
n. 
Implemen
uas imple
empre que
a deveria 
de minimiz
série histó
a série, m
disponível.
nismo de c
deremos in
versões d
então man
q(x) seqüên
M
Federal de Ed
Univ
Dis
s Vinicius Sad
gera um
municação.
onforme de
um geren
pode bloqu
este probl
mensagens
a senha
quema des
o se origino
por sua v
rentes de
e se torn
onar este ú
nsagem de
corrente in
om senha m
da até qu
haver um
necessidad
ntação Ba
mentações
e chegar a
ter lido já
zar o rein
rica com
maior é a
. Por outro
controle de
nicialmente
de cada ob
ntidas para
ncia de to
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
tipo difere
. 
escrito, po
nte de tra
uear transa
lema os 
s de cont
corrente
sta seção
ou e d é a
vez, cria 
e transaçõ
nar proibi
último prob
e controle 
ndicando q
menor do 
ue as sen
m mecanis
de de envia
aseada e
s até agor
atrasada,
á tiver sid
nício de t
todas as
 chance d
o lado, mai
e concorrê
e o caso
bjeto é ma
a cada obj
odas as se
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 40 
ente de pr
ode ficar
ansações
ações inde
gerentes 
trole a tod
e que pre
é o par (n
a data/hora
a necess
ões e nó
tiva em 
blema, um 
a um nó i
que não p
que n. Est
nhas dada
smo adicio
ar a i um 
m Versõe
ra discutid
ou seja,
do substitu
transações
versões d
do valor q
ior é o des
ncia. 
extremo e
antida. As
eto x: 
enhas das 
ologia do Par
sil 
II 
roblema d
paralizado
nunca m
efinidament
de transa
dos os nó
etendem 
n,d), onde 
a em que 
sidade de
ós onde o
uma rede
gerente d
i contendo
pretende m
ta mensag
as por g c
onal para 
subcoman
es Múltip
das, uma a
sempre q
uído por u
s por este
do valor de
que uma a
sperdício d
em que a 
seguintes
ações de
ra – IFPA 
e terminaç
o em um 
manda nen
te. 
ações dev
s com qu
dar às 
n é o núm
a transaçã
e comunic
o banco 
e de gra
e transaçõ
o uma sen
mandar pa
em de con
cheguem 
revogar 
ndo com s
las 
ação de le
ue o valo
um mais n
e motivo 
e cada ob
ação de le
de memória
série hist
s estrutura
e leitura pa
ção e 
nó i 
nhum 
verão 
e se 
suas 
mero 
ão foi 
cação 
está 
ndes 
ões g 
nha n 
ara i 
ntrole 
a n. 
esta 
enha 
eitura 
or do 
novo. 
seria 
bjeto. 
eitura 
a por 
tórica 
as de 
ara o 
 
Facili
repre
vers
conc
Vers
inse
cada
a atu
em 
Para
trans
de 
mom
r=12
da a
por 
corre
senh
tador: Prof. 
Versõe
esentadas
ão V de x.
De p
corrência l
1) Sup
X, esc
soes(x) me
a) V se
rida em R_
2) Sup
a x 
X, seja
a) se e
X e ex
ualização; 
b) caso
Versoes(x)
X. 
Como 
a efeitos d
sação rep
dados co
mento R_se
R_seq
Versoe
Supon
2. Como te
ação ter c
uma trans
eta, fornec
ha r=12 é i
Instituto F
Msc. Marcos
es(x) seqü
s por pares
 
posse des
ocal passa
ponha que 
colha o pa
enor do que
erá então o
_seq(x) na
ponha que
a t(x) a me
existe algu
xiste algum
o contrário
x), onde V é
este prot
do exempl
resente o 
m apenas
eq(x) e Ve
q(x) = (5,8,
es(x) = ((4
nha que o 
emos que 
hegada ba
sação com
cendo-lhe a
nserida em
M
Federal de Ed
Univ
Dis
s Vinicius Sad
üência con
s da forma
stas estr
a a ser o 
a ação é u
ar (s,V) em
e r. 
o valor de
a posição c
 a ação é
enor senha
m x 
ma senha r
o, process
é o valor d
tocolo é m
o é conve
instante e
s um obj
rsoes(x) se
15,...,92) 
,V1), (10,V
protocolo 
10 < r < 2
astante "at
m senha 1
a versão c
m R_seq(x)
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
ntendo tod
a (s,V), ond
ruturas, o
seguinte:
uma leitura
m Versoes
x usado no
correta. 
é uma atua
a em Verso
r em R_se
se a atualiz
e x dado p
mais sofist
eniente ima
em que fo
eto físico
ejam: 
V2), (20,V3)
receba um
20, o valor
trasada" (a
100), é po
corrente no
x) criando-s
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 41 
das as ver
de s é a se
o mecan
a R(X) com
s(x) tal que
o processa
alização W
oes(x) mai
q(x) tal qu
zação, cria
por W(X), p
ticado, co
aginar que
oi submetid
 x. Supo
, ..., (100,V
ma ação de
lido de x s
a versão
ossível enc
o instante
se R_seq(x
ologia do Par
sil 
II 
rsões já c
enha da aç
ismo de 
m senha r. 
e s é a m
amento de
W(X) com 
or do que 
ue w < r t(x
ando um n
para cada x
onvém dar
e a senha
da. Consid
onha que 
V20)) 
e leitura R
será V2. O
corrente d
caixar a a
em que fo
x) = (5,8,12
ra – IFPA 
criadas pa
ção que cr
controle 
Para cada
aior senha
 R(X). b) r 
senha w. 
s. 
x), então re
novo par (
x 
r um exem
a dada a 
dere um b
em um 
R(x) com s
Ou seja, ap
de x foi c
ação na or
oi submetid
2,15,...,92)
ra x, 
riou a 
de 
a x 
a em 
r será 
Para 
ejeite 
(w,V) 
mplo. 
uma 
anco 
dado 
enha 
pesar 
riada 
rdem 
da. A 
). 
 
Facili
W(x)
Obs
proc
uma
proto
senh
proc
Logo
se a
há a
que 
açõe
pala
nece
mem
todo
form
criad
impl
oper
do p
Qua
se a
pode
para
relac
send
conc
com
torna
tador: Prof. 
Supon
) com sen
erve R_se
cessada (s
a ação com
ocolo acei
ha 7, que d
cessada d
o, W(x) te
a menor se
alguma sen
ser rejeita
Esta i
es de leitu
vras, o 
essariamen
mória adici
os os objet
ma de torna
das dent
ementação
racoes de 
próprio ba
ndo a tab
a entrada 
er-se-ia dim
a o sistema
Por f
cionamento
do resolvid
8.6 CO
Nas s
corrência e
entários i
a mais ade
Instituto F
Msc. Marcos
nha agora 
nha w=7. E
eq(x) e V
segundo e
m senha 4
itasse a a
deveria en
epois de 
em que se
enha em V
nha em R
ada. 
mplementa
ura e dimin
volume d
nte menor
onal nece
tos não é 
ar esta imp
tro de 
o básica. 
leitura) m
nco de da
ela ficar c
mais antig
minuir o vo
a. 
fim, lemb
o com o
dos da mes
OMPARA
seções a
e várias i
ndicando 
equada. 
M
Federal de Ed
Univ
Dis
s Vinicius Sad
que o p
Esta ação
Versoes(x).
elemento d
4 (primeiro
ação W(x)
tão ter sid
R(Y), qu
er rejeitada
Versoes(x)
R_seq(x) e
ação tem 
nuir a reje
de transa
r que o d
essária a t
possível n
plementaçã
um esqu
Haveria
mantendo u
ados arma
completame
ga. Assim,
olume de tr
bramos q
o protocolo
sma forma 
AÇÃO ENT
anteriores, 
mplementa
em que 
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
protocolo r
terá que
. Uma lei
de R_seq
o elemento
estaria c
do lida por
uando dev
a. Este fat
, t=10 nes
ntre s=7 e
a propried
eição de a
ações rein
da impleme
orna proib
em razoáv
ão atraent
uema se
uma tabe
um certo n
azenando
ente ocupa
 a um cus
ransações
que os
o bifásico 
que antes
TRE OS M
dois mé
ações fora
situações 
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 42 
receba um
ser rejeita
itura R(Y)
(x)) e leu
o da seqü
criando um
R(Y). Ou
eria ter s
to pode se
ste caso, m
e t=10, r=dade intere
ações de
niciadas n
entação b
bitiva: man
vel para um
te seria m
melhante
ela de ver
número de
a última
ada, espa
sto adicion
s reiniciada
problema
persistem
s. 
MÉTODOS
étodos bá
am discut
uma ou o
ologia do Par
sil 
II 
ma ação d
ada pela s
com sen
a versão
üência Ver
ma nova v
seja, a aç
sido proce
er detetado
maior do q
8 neste c
essante de
atualizaçã
nesta imp
básica. Por
nter todas 
m banco d
anter as ú
àquele 
rsões (e 
e versões 
versão de
ço é obtid
nal de mem
as, com be
as de t
m nesta im
S 
ásicos de
idas. Esta
outra impl
ra – IFPA 
de atualiz
seguinte ra
nha r=8 já
o V1 criada
rsoes(x)). S
versão V1' 
ção W(X) 
essada a
o pesquisa
ue w=7. C
caso, W(x)
e nunca rej
ão. Em o
plementaçã
r outro lad
as versõe
de dados. 
últimas ver
sugerido 
de senhas
recentes, 
e cada ob
do expurga
mória razo
enefício pos
terminação
mplementa
e controle
a seção r
lementaçã
zação 
azão. 
á foi 
a por 
Se o 
com 
seria 
ntes. 
ando-
Como 
 terá 
jeitar 
utras 
ão é 
do, a 
es de 
Uma 
rsões 
na 
s de 
além 
bjeto. 
ando-
oável, 
sitivo 
o e 
ação, 
e de 
eúne 
o se 
 
Facili
impl
orde
vária
adia
dive
oqu
ré-
Or
cont
difer
O te
à po
aces
proc
siste
banc
tador: Prof. 
A Ta
ementaçõe
enação, co
É extr
as implem
ntar algu
rsas altern
TABELA
 
 
 
I
ção 
 
 
 
 
 
 
Bl
ueio 
a 
as
al
 
 
 
 
 
P
- 
rdenação 
a 
er
es
Inicialm
trole de c
rentes, das
empo de re
opulação 
ssados p
cessamento
ema - núm
cos locais,
Instituto F
Msc. Marcos
abela 8.
es dos p
nsiderando
remamente
mentações 
ns comen
nativas. 
A 8.1 - RESU
Implementa
 
 
Bási
 
Cópi
s 
Prim
 
 
Cent
lizada 
 
 
Bási
 
 
Cons
rvativa 
 
Vers
s 
Múlt
mente, con
concorrênc
s quais o 
esposta da
de transaç
para leitu
o e de se
mero de ob
, grau de 
M
Federal de Ed
Univ
Dis
s Vinicius Sad
.1 resum
protocolos
o apenas b
e difícil c
sugeridas
ntários qu
UMO DAS C
DE C
a
rutura
c abela de 
bloqueios 
distribuída
i
m
de bloquei
para cópias
primárias
tr bela de 
bloqueios 
centralizad
c istas de 
senhas 
s s de 
subcomand
sõ
ti
istas de 
senhas e 
versõesnvém lemb
cia pode 
tempo de 
as transaçõ
ções - tax
ra e at
erviço de e
bjetos do b
multiprogr
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
me as
de bloq
bancos de 
comparar
s neste c
ue, embor
CARACTERÍS
CONCORRÊ
Est
a de 
D
ns
t
a
ão s
nece
tabela 
os 
s 
a bl
cópi
prim
ta
da
a bl
em u
coor
l
ão s
nece
fila
dos 
ara 
bloq
eter
l
ão s
nece
brar que a 
ser avali
resposta 
ões é influe
xa média
tualização,
entrada/sa
banco de
ramação,
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 43 
principais
queio em 
dados dis
efetivamen
capítulo. P
ra simples
STICAS DOS
ÊNCIA 
í
Me
sagens 
Adi
n
são 
essárias 
par
oquear 
ias 
márias
par
oquear 
um nó 
rdenador
n
são 
essárias 
p
evitar 
queios 
nos
n
são 
essárias 
performan
ada atrav
das transa
enciado po
de chega
, taxa m
ída - e po
dados, alo
topologia
ologia do Par
sil 
II 
s caracte
duas fas
stribuídos. 
nte a per
Por outro 
s, ajudam
S MÉTODOS
Caract
ti
Existência
cópias 
nã
reconhece 
re
ce 
nã
reconhece 
nã
reconhece 
nã
reconhece 
nã
reconhece 
nce de um 
vés de vá
ações será
or parâme
ada, núme
média de
or parâmet
ocação do
do sistem
ra – IFPA 
erísticas 
ses e de 
rformance 
lado, pod
m a avalia
S DE CONTR
a de 
lem
ão 
ios mú
difícei
detect
conhe
os mú
de 
ão 
ios mú
de 
ão 
o cícli
mútuo
ão 
s etern
ão 
cio cíc
mútuo
mecanism
árias med
á aqui utiliz
etros intríns
ero de ob
e serviço 
tros do pró
os objetos
a, etc. No
das 
pré-
das 
de-se 
ar as 
ROLE 
Prob
mas 
Term
bloque
útuos 
is de 
tar
bloquei
útuos difíceis 
detectar
bloque
útuos fáceis 
detectar
reiníci
ico e 
o, 
de fácil
bloqueio
nos 
reiní
clico e 
o, 
de fácilmo de 
didas 
zado. 
sicos 
bjetos 
de 
óprio 
s nos 
o que 
b
m
 
Facili
conc
segu
méd
temp
temp
veze
mec
conf
conf
guia
Um 
conf
conf
um 
vast
sign
de b
traba
cont
perc
custo
conf
o vo
pré-o
múlt
um 
tador: Prof. 
cerne esp
uintes parâ
custo a
dio de men
custo 
po médio d
custo 
po médio 
es que a tra
Usarem
canismo de
pessim
flitantes 
otimist
flitantes 
Não é
r a intuiçã
indicador
flitantes qu
flitos será 
banco de 
a gama de
ifica algo 
bloqueios m
alho útil do
Consid
trole de 
centagem d
o de reso
flitos é rein
lume de tr
Com e
ordenação
tiplas. A im
volume de
Instituto F
Msc. Marcos
ecificamen
âmetros tor
adicional d
nsagens pa
adicional 
de process
adicional 
que uma 
ansação é
mos estes 
e controle d
mista:carac
ta: caract
é muito cla
ão, o que 
r aceito c
ue está ab
muito baix
dados de
e aplicaçõe
acima de 
mútuos e 
o sistema d
deremos in
concorrên
de conflito
olver conf
niciar trans
ansações 
estas carac
o, a imple
mplementa
e mensage
M
Federal de Ed
Univ
Dis
s Vinicius Sad
nte a mec
rnam-se im
de comuni
assadas ap
de proces
samento ga
de proce
transação
é reiniciada
três parâm
de concorr
cterizado 
terizado p
aro, e não
significa
considera
baixo de 5
xa quando
e tamanho
es. Por ou
10%. Se
reinícios d
decairá con
nicialmente
cia para 
os é alta, 
flitos. Com
sações, de
reiniciadas
cterísticas 
ementação
ção conse
ens adicio
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
canismos
mportantes
icação, qu
penas para
ssamento 
asto apena
essamento
o passa blo
a; 
metros com
rência a do
por uma
por uma
o há muito
"baixa per
como ba
5%. Se co
o as transa
o médio, e
utro lado, u
a freqüên
de transaç
nsideravel
e o problem
um cen
o objetivo
mo a form
eve-se esco
s. 
temos dua
o conserva
ervativa nu
onais subs
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 44 
de contro
s: 
ue pode se
a fins de co
local, que
as em cont
o das tran
oqueada, o
mo indicati
ois cenário
elevada
baixa p
os experim
rcentagem
aixa uma
onsiderarm
ação aces
este limite 
uma alta p
ncia exced
ções poder
mente. 
ma de esc
nário pes
básico ne
ma mais d
olher um m
as impleme
ativa e aq
unca reinic
tancial e
ologia do Par
sil 
II 
ole de co
er estimad
ontrole de 
e pode se
trole de co
nsações, 
ou pelo nú
ivo da ade
os extremos
percentag
percentage
mentos dis
 de ações
percentag
mos que a 
ssam pouc
será satis
percentage
der este lim
rá ser tão 
colher um 
ssimista.
este caso s
dispendios
mecanismo
entações d
quela utiliz
cia transaç
implicitam
ra – IFPA 
ncorrência
o pelo núm
concorrên
er medido 
oncorrência
estimado 
mero méd
equação de
s: 
em de a
em de a
sponíveis 
s conflitan
gem de a
freqüênci
cos objetos
sfeito por 
em de con
mite, o vo
elevado q
mecanism
Dado qu
será dimin
sa de res
o que mini
do protoco
zando ver
ções, mas 
mente bloq
a, os 
mero 
ncia; 
pelo 
a; 
pelo 
io de 
e um 
ações 
ações 
para 
ntes". 
ações 
a de 
s em 
uma 
nflitos 
olume 
que o 
mo de 
e anuir o 
olver 
imize 
lo de 
rsões 
gera 
queia 
 
Facili
trans
pode
mais
duas
pess
cent
mútu
adeq
orde
senh
proto
impl
com
nest
impl
capí
tador: Prof. 
sações co
e-se optar 
s memória
s fases, ap
simista blo
tralizada é
uos. 
Para u
quada, ex
enação po
ha, quer e
ocolo de 
ementaçõe
porta mel
te cenário. 
Isto c
ementaçõe
ítulo para m
 
Instituto F
Msc. Marcos
om freqüê
pela impl
a em troca
penas a ce
oqueios m
é a única
um cenári
xceto a i
ois força 
elas conflit
pré-orden
es do proto
hor em te
conclui a
es. O leito
maiores de
M
Federal de Ed
Univ
Dis
s Vinicius Sad
ência. Se
lementaçã
a. Das im
entralizada
mútuos se
a que per
o otimista
mplementa
as operaç
tem ou nã
ação, é a
ocolo de b
ermos de 
a nossa
or interess
etalhes. 
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
e estas c
o utilizand
plementaç
a poderá s
erão muito
rmite fácil
a, qualque
ação con
ções a se
ão. A imp
a mais ind
bloqueio em
mensage
breve c
sado deve
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 45 
característ
do versões
ções do pr
ser adequa
o frequent
deteção/
r impleme
servativa
erem proc
plementaçã
dicada ne
m duas fas
ens adicion
comparaçã
erá consul
ologia do Par
sil 
II 
icas forem
s múltiplas
rotocolo d
ada, pois e
tes e a i
/resolução 
entação é,
do proto
cessadas 
ão básica,
este cenár
ses, a bás
nais, send
ão entre 
tar as refe
ra – IFPA 
m inaceitá
s, gastando
e bloqueio
em um ce
implement
de bloqu
, em princ
ocolo de 
em ordem
, dentre a
rio. Quant
sica é a qu
do interess
as dive
erências d
áveis, 
o- se 
o em 
nário 
tação 
ueios 
cípio, 
pré-
m de 
as do 
o às 
ue se 
sante 
ersas 
deste

Outros materiais