4o_Semana_-_Controle_de_Concorrencia_I

Prévia do material em texto

Facili
conc
discu
houv
de 
trans
intro
conc
apre
méto
méto
ocas
trans
cent
uso 
intro
nota
adot
prob
aces
utiliz
tador: Prof. 
 
www.inf
 
Este 
corrência e
ussão, sã
vesse qua
anomalias
sações, já
oduzido. O
corrência, 
esenta vári
odos princ
odo é ac
sionados 
sações. A 
tralizados é
de pré-ord
8.1 IN
Esta s
oduz os cr
ação a ser 
tado nos ú
8.1.1 A
Todo 
blemas, ch
sso concor
perda 
acesso
perda 
Estas 
zam um b
Instituto F
Msc. Marcos
C
nf.puc‐rio.br/
capítulo d
em banco
ão listados
lquer cont
s de sinc
á incorpor
 critério fu
serializaçã
ios algoritm
cipais, blo
companhad
pelo méto
discussão
é apresent
denação co
NTRODUÇ
seção apr
ritérios bás
r usada no
ltimos cap
Anomalia
método 
amados d
rrente irres
da consist
o a dados 
de atualiza
anomalias
anco de d
M
Federal de Ed
Univ
Dis
s Vinicius Sad
CONTRO
/~casanova/L
discute e
os de dado
s vários p
trole de co
cronização
rando me
undamenta
ão, é o pró
mos para c
oqueio e
da de um
odo, que
o acerca d
tada em s
obre apena
ÇÃO 
resenta ex
sicos de c
o capítulo.
ítulos tamb
as de Sin
de contr
e anomalia
strito aos d
tência do b
inconsiste
ações 
s serão ilu
dados cent
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagin
LE DE C
LivroCasanov
em detalh
os distribu
problemas
oncorrência
o. Em se
ecanismos
al de corre
óximo ass
controle de
pré-orden
ma discus
possam
do uso de
eparado d
as o caso d
xemplos d
correção p
O modelo
bém é aqu
cronizaçã
role de c
as de sinc
dados. As 
banco 
ntes 
ustradas at
tralizado (
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
na 1 
CONCOR
va/ncap8.pd
he o pro
uídos. Inici
s que pod
a. Estes p
eguida, um
de cont
ção para a
unto. O co
e concorrê
nação. A
ssão sobr
impedir
e bloqueios
o caso dis
distribuído
e anomal
para contro
o de proce
ui revisto. 
ão 
concorrênc
cronização
principais 
través de
embora o
ologia do Par
sil 
II 
RÊNCIA 
df 
blema de
almente, p
deriam oc
problemas 
m modelo
trole de 
algoritmos 
orpo princi
ência, grup
apresenta
re problem
o término
s para ban
stribuído, e
. 
ias de sin
ole de con
essamento
cia deve 
o, que pod
anomalias
exemplos
fato de se
ra – IFPA 
e controle
para motiv
correr se 
são cham
o abstrato
integridad
de contro
pal do cap
pados em 
ação de 
mas adicio
o normal 
ncos de d
enquanto q
ncronizaçã
ncorrência
 de transa
evitar c
em resulta
s são: 
 informais
er centrali
e de 
var a 
não 
ados 
o de 
e, é 
le de 
pítulo 
dois 
cada 
onais, 
das 
ados 
que o 
ão, e 
a e a 
ações 
ertos 
ar do 
s que 
zado 
 
Facili
ou d
do b
sem
núm
COD
é un
CUR
C3. 
para
segu
ATR
(m,c
DE-T
CO
NMA
tador: Prof. 
distribuído 
banco são o
 
CURSO
mestre, onde
curso; 
 
TURM
mero de 
MATRIC
IGO). Há tr
C1. 
o COD
nico. 
C2. 
todo C
RSOS 
 
a cada curs
indicad
Consid
uinte forma
 
 
 
M
RICULE
c): 
 
COME
TRANSACAO
 
M1. 
LEIA a
DIGO=c; 
 
realmen
existir th
gin 
M2. 
ESCRE
 
ATR de t; M
Instituto F
Msc. Marcos
seja irrele
os seguint
OS[CODIGO
e 
NMATR in
MAS[MATR
CULA) estã
rês critérios
DIGO de cad
CODIGO usa
so c, NMATR
do em TURMA
dere agora
a: 
ECO-
O 
a tupla t d
if t 
nte 
hen 
be
EVA a tupla 
incr
3. 
M
Federal de Ed
Univ
Dis
s Vinicius Sad
evante par
tes: 
O,NOME,NM
ndica o núme
RICULA,C
ão matricu
s de consi
da curso 
ado em TUR
R contém o
AS. 
a três tra
de CURSOS
(m,c) em TU
remente de
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagin
ra esta dis
MATR] repre
ero de aluno
ODIGO] in
ulados em
stência pa
MAS deve e
o total de a
ansações 
S com 
URMAS; 
1 o campo
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
na 2 
scussão). O
esenta os c
os matricula
ndica que a
 que curs
ara este ba
estar listado
alunos matr
sobre es
o 
ologia do Par
sil 
II 
Os esquem
cursos ofer
ados em cad
alunos (repr
sos (repre
anco de da
 em 
iculados em
ste banco,
ra – IFPA 
mas de rel
recidos em 
da particula
resentados 
esentados 
dos: 
m c, confor
, definidas
ação 
um 
ar 
pelo 
pelo 
rme 
s da 
 
Facili
CUR
nd. 
TRA
ANC
ELE(
): 
DE-
TRA
CO
CO
I
S
T
E
(
m
) 
DE-T
MAT
ante
tupl
TRA
cons
exist
form
tador: Prof. 
RSOS; 
FIM-DE-
ANSACAO 
 
 
C
C
(c
 
INICIO
ANSACAO 
 
C1. 
REMO
DIGO=c; 
 
C2. 
REMO
DIGO=c; FIM
 
 
L
 
COME
TRANSACAO
 
L1. 
LEIA 
TRICULA=m
 
 
L2. 
LEIA to
erior; 
 
liste tod
las lidas; FIM
ANSACAO 
É impo
sistência d
tência do 
ma, a trans
Instituto F
Msc. Marcos
REE
e
O-
OVA a tupla
OVA todas a
M-DE-TRANS
ECO-
O 
todas as 
; 
liste as tup
odas as tupl
das as 
M-DE-
ortante ob
do banco. 
curso c a
sação CAN
M
Federal de Ed
Univ
Dis
s Vinicius Sad
SCREVA a t
a de CUR
as tuplas de
SACAO 
tuplas de
plas lidas; 
las de CURS
bservar qu
De fato, a
ntes de ef
NCELE(c) re
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagin
upla t EM 
RSOS com 
TURMAS co
TURMAS
SOS tais que
ue cada um
a transação
fetivament
etira o curs
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
na 3 
om 
com 
e o CODIGO
ma destas
o MATRICUL
te matricul
so c de CU
ologia do Par
sil 
II 
O foi lido no
s transaçõ
LE(m,c) prim
lar m em 
URSOS e to
ra – IFPA 
o comando
ões preser
meiro verif
c. Da me
odos os al
o 
rva a 
fica a 
esma 
unos 
 
Facili
matr
exec
sincr
conc
a co
aos 
banc
Os v
seqü
trans
distin
LISTE(
dado
MATR
seqü
fato,
inicia
com
no e
tupla
CURS
cons
M3 f
trans
trans
que 
tador: Prof. 
riculados n
cutadas c
ronização 
Por s
correntes s
omandos q
comandos
co de dad
valores do
üência de
sação, ca
nguidos po
Assim 
indica 
(m), CANCE
Supon
os seja 
RICULE(82.3
üência de c
Esta s
 embora M
al e, porta
ando C1 e
estado fina
a (82.3827,I
SOS com C
sistência. A
fica sem a
Este 
sações qu
sação por 
Como 
o aluno 8
Instituto F
Msc. Marcos
neste curs
concorrent
poderão o
simplicidad
serão repr
que acess
s na defini
dos não 
os parâme
e rótulos. 
da uma d
or subscrito
a seqüênc
uma exe
ELE(c) e MA
nha que o c
consisten
3827,INF2045
comandos
seqüência 
M1 correta
nto, o alun
executado
al do banc
NF2045), se
ODIGO=INF
Além disto
ção pois o
é, então, 
ue leva 
si só prese
um outro
82.5694 está
M
Federal de Ed
Univ
Dis
s Vinicius Sad
so de TURM
temente, 
ocorrer. 
de, nos
resentadas
am o ban
ição das t
influenciam
etros das
Caso ha
das execu
os. 
cia 
M11 M21 M
ecução se
ATRICULE2(m
curso INF20
nte. Cons
5) e CAN
: 
viola o se
mente det
no cuja ma
 imediatam
co de dado
em que h
F2045. Isto 
o, embora
o curso INF2
um exe
a perda
erve consis
o exemplo
á inicialme
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagin
MAS. No e
sem ne
exemplos
s por seqü
co de dad
ransações
m a discu
transaçõe
aja mais
uções e o
M31 L1 L2 C
eqüencialm,c), nesta o
045 exista
sidere um
NCELE(INF20
M1 C1 C2
egundo crit
termine qu
atricula é
mente em 
os, a relaç
aja nenhu
constitui u
não produ
2045 não m
emplo de
de consis
stência. 
o de anom
ente matric
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
na 4 
entanto, se
enhum co
s que se
üências de
dos (os rót
s). Comand
ssão, sen
es são in
de uma
os rótulos
C1 C2 M12 
das tran
rdem. 
e que o es
ma exec
045), repre
2 M2 M3 
tério de co
ue o curso
82.3827 po
seguida re
ção assoc
uma tupla
ma violaçã
uza erro p
mais existe 
uma exe
stência do
malias de
culado no c
ologia do Par
sil 
II 
e estas tra
ontrole, a
e seguem
 rótulos co
tulos são 
dos que n
ndo, portan
dicados fo
execuçã
s correspo
M22 M32 
sações M
stado inicia
cução co
esentada 
onsistência
INF2045 ex
ode nele se
emove est
ciada a TUR
na relaçã
ão do segu
ropriamen
quando M
ecução c
o banco, 
sincroniza
curso INF20
ra – IFPA 
ansações fo
anomalias 
m, execu
orrespond
aqueles d
não acessa
nto, ignora
ora da pr
ão da me
ndentes s
MATRICULE 
al do banc
oncorrente 
pela seg
a do banco
xiste no es
e matricul
te curso. L
RMAS conte
ão associa
undo critér
te, o com
M3 é execut
oncorrente
embora 
ação, sup
045. Cons
orem 
de 
uções 
endo 
ados 
am o 
ados. 
ópria 
esma 
serão 
(m,c), 
co de 
de 
uinte 
o. De 
stado 
ar, o 
Logo, 
erá a 
da a 
rio de 
ando 
tado. 
e de 
cada 
onha 
idere 
 
Facili
uma
pela
indic
de L
o re
cons
inco
o cu
MATR
seqü
NMA
dois 
por 
valo
este
incre
perd
Seçã
seria
mes
ante
discu
conc
o ba
onde
obje
esqu
tador: Prof. 
a execução
 seguinte s
Neste 
ca que o a
L1, mas es
esultado a
sistência d
nsistentes 
Para c
urso INF204
RICULE (82.5
ência: M11 M
Esta e
ATR para o 
alunos. Is
M1, e não
r inicial de
 valor; m
ementá-lo. 
(O leito
da de cons
Isto co
ão 8.1.2 in
alizáveis, o
8.1.2 M
O est
mo mode
eriores. Es
ussão sob
A níve
ceitual glob
anco é des
e está arm
tos físicos
uemas int
Instituto F
Msc. Marcos
o concorre
seqüência
caso, o r
aluno 82.56
te curso nã
apresentad
do banco
por parte 
concluir es
45 exista i
5782,INF204
M12 M22 M
execução l
curso INF2
sto se deve
o o valor 
e NMATR p
as M31 e
or deve se
sistência do
ompleta a 
ntroduzirá 
onde estes
Modelage
udo de c
lo de SG
sta seção 
re controle
el lógico, 
bal consist
scrito por 
mazenado;
s. Os ma
ternos de
M
Federal de Ed
Univ
Dis
s Vinicius Sad
ente de LIS
: L1 C1 C2
resultado
694 está m
ão é listad
do por LI
o. Temos
da transaç
sta seqüên
inicialment
45) e MATRI
M32 M21 M31
eva a um
2045 reflete
e ao fato d
corrente d
para o cu
screve so
e convenc
o banco).
nossa disc
uma class
s problema
em do Sis
controle de
BD distrib
recorda 
e de conco
o banco
tindo de u
uma série
 cada esq
apeamento
efinem a
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagin
STE(82.5694
2 L2 
apresenta
matriculado
o por L2, p
ISTE não 
aqui um
ção LISTE. 
ncia de ex
te. Conside
CULE2(82.49
a perda d
e apenas a
de M3 incr
de NMATR.
rso INF204
obre o val
cer de que
cussão so
se de exec
s não ocor
stema 
e concorr
buído e de
os aspect
orrência. 
o de dado
m conjunto
e de esque
quema int
os do esq
forma d
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
na 5 
) e CANCE
ado por LIS
o no curso
pois foi ca
satisfaz a
a situaçã
xemplos, s
ere uma e
920,INF2045)
e atualizaç
a matrícula
rementar e
 Isto é, M
45; M31 e M
or criado 
e o último
bre anoma
cuções con
rrem. 
ência será
e transaçõ
tos do mo
os é des
o de objeto
emas inter
terno cons
quema co
de distrib
ologia do Par
sil 
II 
ELE(INF2045
STE é inco
o INF2045, c
ncelado po
ao segund
o de ace
suponha n
execução c
) representa
ção pois o
a de 82.578
e reescrev
M11 e M12 
M32 amba
por M32, 
exemplo t
alias de si
ncorrentes
á feito as
ões usado 
odelo rele
scrito por 
os lógicos
rnos, um 
siste de u
nceitual g
uição do 
ra – IFPA 
5) represen
onsistente 
como resu
or C1. Ou 
do critério
esso a d
novamente
concorrent
ada pela seg
o valor fina
82, e não a
ver o valor
lêem amb
s increme
em luga
também le
ncronizaçã
, chamada
ssumindo-s
 nos capí
evantes pa
um esqu
. A nível fí
para cada
um conjunt
global para
banco 
ntada 
pois 
ltado 
seja, 
o de 
ados 
e que 
te de 
guinte 
al de 
a dos 
r lido 
bas o 
ntam 
ar de 
eva à 
ão. A 
as de 
se o 
ítulos 
ara a 
uema 
ísico, 
a nó 
to de 
a os 
e a 
 
Facili
corre
pode
cópi
com
(GT)
proc
área
de d
Atua
traba
as c
pela
trans
seqü
um g
uma
está
em X
níve
físico
com
tador: Prof. 
espondênc
erão dete
as dos m
andos da 
A exec
) do nó on
cessa-se da
COMEÇ
a de trabal
coman
dados traz
alizações 
alho, não s
FIM-D
cópias de 
 transação
Supore
sação há u
Todas 
üências de
grupo de 
a seqüência
R(X) 
ação d
 no conjun
X para
W(X) 
ação d
X no banc
Assim
l lógico) p
os que ai
ando da L
Instituto F
Msc. Marcos
cia entre o
erminar qu
esmos da
LMD e os 
cução de u
nde foi sub
a seguinte
ÇO-DE-TRAN
ho para a 
ndos da LM
zendo-os 
sobre os 
se tornand
E-TRANSA
todos os 
o. Os valor
emos que
uma área d
as oper
e operaçõe
transações
a de ações
de leitura q
nto 
a a área de
de atualiza
co de dado
, a execuç
poderá ge
nda não e
LMD nunca
M
Federal de Ed
Univ
Dis
s Vinicius Sad
objetos físi
ue certos 
dos. Os o
objetos fís
uma transa
bmetida. A
e forma: 
NSAÇÃO: o
transação
MD: consu
para a á
objetos l
o visíveis d
AÇÃO: inv
objetos ló
res dos obj
e em cad
de trabalho
rações a 
es a nível 
s gera, em
s elementa
que recupe
e trabalho l
ação que e
s local. 
ção de um
rar várias
estão na 
a gerará a
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagin
icos e obje
conjuntos
objetos lóg
sicos atravé
ação é con
A nível lógi
o GT ao in
; 
ltas puras 
área de tr
lógicos sã
de imediat
voca o prot
gicos afet
jetos lógico
da nó pa
o da transa
nível lóg
físico. Mai
m cada nó
ares, que s
era os valo
ocal da tra
escreve os
m comando
ações do
área de tr
ções elem
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
na 6 
etos lógico
s de obje
gicos são
és de açõe
ntrolada pe
ico, a exec
nterceptar
acessam 
rabalho, s
ão mantid
to a outras
tocolo bifás
ados por 
os são obt
rticipando 
ação. 
gico são 
is precisam
ó onde o b
suporemos
ores dos o
ansação qu
s novos va
o da LMD
o tipo R(X)
rabalho da
mentares do
ologia do Par
sil 
II 
os. Estes 
etos físico
manipulad
es element
elo gerente
cução de 
este com
objetos lóg
se já lá n
as na pr
 transaçõe
sico para m
atualizaçõ
idos da áre
do proce
sempre t
mente, um
banco está
s serem de
objetos físi
ue gerou a
alores dos 
(que é um
) para rec
a transaçã
o tipo W(X
ra – IFPA 
mapeame
os armaze
dos atravé
tares. 
e de transa
uma trans
ando cria 
gicos do b
não estive
ópria área
es; 
modificar t
ões execut
ea de traba
essamento
traduzidas
a execuçã
á armazen
e dois tipos
cos cujo n
a ação; 
objetos fís
ma operaç
cuperar ob
ão. Porém
X) pois o b
entosenem 
és de 
ações 
ação 
uma 
anco 
erem. 
a de 
todas 
tadas 
alho. 
o da 
 em 
ão de 
nado, 
s: 
nome 
sicos 
ção a 
bjetos 
, um 
anco 
 
Facili
de d
ating
efeti
ress
Port
inter
mec
apen
físico
seqü
dado
pode
seqü
de d
esca
local
R(X)
Freq
sem
distr
por 
arma
pode
exec
tador: Prof. 
dados não
gir a segu
var alteraç
Há du
altar aqui: 
1. con
anto, um 
rcalação da
2. A s
canismos d
Como 
nas das se
os armaz
üências de
os locais. 
e, então, 
üência de 
dados do 
alonamento
l ao nó i p
) ou W(X) 
qüentemen
elhanteme
Como 
ribuído arm
dois conju
azenam có
Um es
eria ser 
L = { L
L1 = R1
L2 = R1
Ou se
cutadas no
Instituto F
Msc. Marcos
o é alterad
nda fase, 
ções nos b
as suposiç
ntrole de 
mecanism
as ações e
semântica
de controle
conseqüê
eqüências
zenados n
e operaçõ
Uma exec
ser abstra
ações ele
nó i que fo
o global p
para T. Usa
executada
nte escreve
ente para a
exemplos
mazenado 
untos de o
ópias dos m
scaloname
1, L2 }, ond
1(y1) R2(x1)
1(x2) W1(x2
eja, L1 rep
o primeiro n
M
Federal de Ed
Univ
Dis
s Vinicius Sad
do de ime
ações ele
bancos de 
ções impo
concorrên
mo de con
elementare
 das tran
e de conco
ência, o c
 de operaç
nos vários
ões R(X)
cução conc
aída por u
ementares
oram gera
ara T e a
aremos Ri
as a favor 
eremos Ri 
ações de a
s destes
em dois 
objetos físi
mesmos da
nto global 
de 
) W2(x1) W1
) W2(x2) 
resenta a 
nó: 
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagin
ediato. Ape
ementares
dados loca
ortantes pa
cia será 
ntrole de
es de difer
nsações n
orrência. 
controle d
ções de le
s bancos
e W(X) e
corrente E
um conjun
R(X) ou
adas em E
 seqüênci
i(X) ou Wi(
da transaç
(x1 ,..., xk 
atualização
conceitos,
nós. Os e
icos, D1 =
ados. 
para duas
1(x1) 
seguinte 
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
na 7 
enas quan
do tipo W
ais. 
ara contro
feito a ní
concorrên
rentes tran
não será 
de concorr
eitura/atua
de dado
executada
E de um c
nto L= { L
W(X) exe
E. O conju
a Li é cha
(X) para in
ção Ti em 
) em luga
o. 
 consider
esquemas
{ x1 ,y1 } e
s transaçõe
seqüência
ologia do Par
sil 
II 
ndo o pro
W(X) serão
ole de con
ível dos o
cia deverá
nsações em
levada em
rência dev
lização so
os locais, 
s contra 
conjunto T 
L1 ,..., Ln }
cutadas c
nto L é ch
mada do e
ndicar açõe
um escalo
r de Ri ( { 
re um ban
internos s
e D2 = { x2 
es T1 e T2 
a de açõe
ra – IFPA 
otocolo bifá
o geradas 
corrência 
objetos fís
á disciplin
m cada nó.
m conta p
verá depe
obre os ob
ou seja, 
os banco
de transa
}, onde L
contra o b
hamado de
escalonam
es elemen
onamento l
{ x1 ,..., xk }
nco de d
são model
}, onde x1
neste con
es element
ásico 
para 
a se 
sicos. 
nar a 
 
pelos 
ender 
bjetos 
das 
s de 
ações 
i é a 
anco 
e um 
mento 
tares 
local. 
} ), e 
ados 
ados 
1 e x2 
texto 
tares 
 
Facili
méto
esca
sobr
três 
siste
banc
corre
trans
tador: Prof. 
T1 lê o 
T2 lê o 
T2 escr
T1 escr
Para o
T1 lê o 
T1 escr
T1 escr
Tanto 
odos de c
alonamento
8.1.3 C
Esta s
re controle
classes d
ema e crité
Os crit
T1. 
Cada t
T2. 
Cada t
co de dado
etamente c
Os crit
G1. 
O sist
sações ace
G2. 
Instituto F
Msc. Marcos
objeto físi
objeto físi
reve no ob
reve no ob
o segundo 
objeto físi
reve no ob
reve no ob
a teoria d
controle d
os globais.
Critérios 
seção def
e de conco
distintas: c
érios espe
térios para
transação,
transação,
os; Estas 
cada trans
térios gené
tema deve
essando q
M
Federal de Ed
Univ
Dis
s Vinicius Sad
co y1 
co x1 
bjeto físico
bjeto físico
nó, L2 repr
co x2 
bjeto físico
bjeto físico
de correçã
de concorr
. 
de Corre
ine os crit
orrência. S
critérios p
ecíficos pa
 transaçõe
 quando e
, quando e
suposiçõe
ação. 
éricos do s
e funciona
ualquer ba
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagin
x1 
x1 
resenta a s
x2 
x1 
ão quanto
rência serã
eção 
térios de c
Serão cons
ara transa
ara os mé
es são sim
xecutada s
executada 
s afirmam
istema por
ar corretam
anco de da
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
na 8 
seguinte se
o estudo
ão basead
correção q
siderados
ações, crit
todos de c
ples: 
sozinha, se
sozinha, p
apenas q
r sua vez s
mente par
ados; 
ologia do Par
sil 
II 
eqüência: 
do comp
dos em pr
que guiarã
critérios p
térios gen
controle de
empre term
preserva c
que o usuá
serão os se
ra qualque
ra – IFPA 
portamento
ropriedade
ão a discu
pertencent
néricos pa
e concorrê
mina; 
consistênc
ário especi
eguintes: 
er conjunto
o dos 
es de 
ussão 
tes a 
ara o 
ncia. 
ia do 
ificou 
o de 
 
Facili
trans
inter
distr
trans
um 
dado
conc
físico
crité
das 
cont
bloq
segu
porm
inter
quan
uma
esta
dar u
ao e
discu
com
seja
tador: Prof. 
A resp
sações e 
A prim
ressados 
ribuídos pa
sações sã
particular 
os. Já a 
corrência 
os lidos e 
Esta d
rios de co
C1. 
Cada t
C2. 
Cada 
outras tran
O prim
trole de co
ueios mút
undo crité
menorizada
rferência". 
8.2 TE
A teor
ndo, em u
a delas é 
 proprieda
uma defini
entendime
utidos nas
Intuitiv
putacional
, a uma
Instituto F
Msc. Marcos
posta do 
dos valore
meira sup
em const
ara aplicaç
ão conheci
conjunto 
segunda 
devam tra
atualizado
discussão 
orreção im
transação 
transação 
nsações; 
meiro crité
oncorrência
uos, que p
ério, o m
a para e
Este será 
EORIA DA
ria da se
uma execu
executad
ade são ch
ição precis
ento da c
s seções se
vamente, 
lmente eq
a execuç
M
Federal de Ed
Univ
Dis
s Vinicius Sad
sistema d
es dos próp
osição jus
ruir SGBD
ções espe
idas "a pr
de transa
suposição
abalhar ap
os, conform
nos coloc
postos aos
submetida
deve ser 
ério é clar
a deverá p
possam im
mais impo
esclarecer 
o assunto 
A SERIAL
erialização
ução conc
da atomica
hamadas d
sa da noçã
correção d
eguintes d
uma exe
uivalente 
ção em 
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagin
deve ser
prios dados
stifica-se
DDs de us
cíficas. Lo
riori", ou q
ações ace
o sugere
penas com
me coment
ca em po
s métodos 
a ao sistem
executada
ro e resum
prover mei
mpedir o té
ortante de
o que 
da próxim
LIZAÇÃO
se propõ
corrente d
amente se
de serializ
ão de exec
dos métod
este capítu
ecução co
a uma ex
que as 
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
na 9 
independe
s armazen
com base
so genéric
ogo, não é
que o siste
essando u
que os m
m base n
tado no fin
sição de
de control
ma deve ev
a atomicam
me a idéia
ios para re
rmino norm
e todos,
significa 
ma seção. 
õe a cap
e um grup
em interfe
áveis. O o
cução seri
dos de co
ulo. 
oncorrente 
xecução se
transaçõ
ologia do Par
sil 
II 
ente do s
nados. 
e no fato
co, e não
é razoável 
ema seja d
um particu
métodos d
nos nome
nal da seçã
definir int
le de conc
ventualmen
mente, sem
a de que 
esolver pro
mal das tra
requer u
"execuçãopturar de 
po de tran
erência. Ex
objetivo de
alizável, q
ontrole de
é serial
erial das t
ões são 
ra – IFPA 
significado 
 de esta
o em siste
supor qu
dependent
ular banco
de controle
s dos ob
ão anterior
uitivament
orrência: 
nte termina
m interferê
o método
oblemas, c
ansações. 
ma discu
oatômica 
forma pre
nsações, 
xecuções 
esta seção 
que é esse
e concorrê
lizável se
transações
process
das 
rmos 
emas 
ue as 
te de 
o de 
e de 
bjetos 
r. 
te os 
ar. 
ência 
o de 
como 
Já o 
ussão 
sem 
ecisa 
cada 
com 
será 
encial 
ência 
e for 
s, ou 
sadas 
 
Facili
seqü
prec
que 
com
exec
um 
arma
conj
dado
tador: Prof. 
üencialmen
cisamente 
são exe
putacional
8.2.1 E
Em te
cutadas se
escalonam
transaç
as ope
preced
o mesm
Diremo
Como 
azenado e
untos de o
D2 = {
os. Um es
S = { S
S1 = R
S2 = R
Como 
N = { N
N1 = R
N2 = R
e 
N' = { N
Instituto F
Msc. Marcos
nte, uma 
este conc
cuções se
lmente equ
Execuçõe
ermos sim
eqüencialm
mento glob
1. para 
ções Ti e T
erações de
 
2. para c
dem as op
mo é verda
os ainda q
exemplo
em dois n
objetos físic
{ x2 }. Su
calonamen
S1, S2 }, ond
1(y1) W1(x1
1(x2) W1(x2
exemplos 
N1, N2 }, on
R1(y1) R2(x1
R1(x2) W1(x2
N1', N2' }, o
M
Federal de Ed
Univ
Dis
s Vinicius Sad
após a
ceito intuit
eriais e q
uivalentes.
es Seriais
ples, uma
mente. Ou
bal L é se
cada esc
T j em T, o
e T j, ou vic
cada par d
perações d
ade para to
ue L é um 
o, consid
nós cujos 
cos, D1 = { 
ponha qu
nto serial s
de 
) R2(x1) W
2) W2(x2) 
de escalo
de 
) W2(x1) W
2) W2(x2) 
onde 
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
outra, em
tivo é nec
quando du
. 
s 
a execução
seja, uma
rial se e s
calonament
ou todas a
ce-versa; 
de transaç
de Tj em um
odos os ou
escalonam
dere um
esquemas
{ x1 ,y1 } e 
e x1 e x2 
seria : 
W2(x1) 
namentos 
W1(x1) 
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 10 
m alguma
cessário d
uas execu
o é seria
a execução
somente se
to local d
as operaçõ
ções Ti e T
m escalona
utros escal
mento seria
banco
s internos 
armazene
não seriai
ologia do Par
sil 
II 
 ordem. 
definir dois
uções são
l se as tr
o E de T 
e 
de L, para
ões de Ti p
Tj, se as op
amento loc
lonamento
al neste ca
de dado
são mode
em cópias
s teríamos
ra – IFPA 
Para form
s conceito
o consider
ransações
modelada
a cada pa
recedem t
perações d
cal de L, e
os locais de
aso. 
os distrib
elados por 
s dos mes
s: 
mular 
os: o 
radas 
são 
a por 
ar de 
todas 
de Ti 
então 
e L. 
buído 
dois 
smos 
 
Facili
seria
exec
ante
atom
de 
cons
banc
trans
banc
pres
inco
cada
atua
exec
exec
com
forem
de d
exec
duas
obje
Li e n
tador: Prof. 
N1' = R
N2' = W
O prim
ais, enquan
O mé
cuções se
eriormente.
micamente 
També
sincroniza
sistência e
co for con
sação em
co for con
serva cons
nsistentes
a transação
alização é p
8.2.2 E
Passe
cuções se
cuções E
putacional
m satisfeit
dados: 
1. E e 
2. cada
Mais 
cução de T
s ações el
to físico a
X Y. D
não há ne
Instituto F
Msc. Marcos
R1(y1) R2(x1
W2(x2) R1(x
meiro exem
nto o segu
étodo de 
eriais, é o
. Não há
sem inter
ém deve e
ação não 
e termina 
nsistente, 
m S també
nsistente, o
sistência. 
 em S po
o é proces
perdida em
Equivalên
mos agor
erem com
E e E' d
lmente eq
tas, supond
E' produze
a transaçã
precisame
T modelad
lementares
rmazenad
Diremos qu
enhuma op
M
Federal de Ed
Univ
Dis
s Vinicius Sad
1) W2(x1) W
x2) W1(x2) 
mplo viola
ndo exem
controle
bviamente
á dúvidas
rferência d
estar claro
ocorrem.
se execu
o estado
ém será c
o estado f
Pela mes
is o faz d
ssada após
m S. 
ncia de E
ra para o 
mputaciona
de um m
uivalentes
do que E
em o mesm
ão em T lê 
ente, seja
da por um 
s em algu
o em um 
ue R(X) lê
peração W(
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
W1(x1) 
a a primei
plo viola a
de conco
e correto d
s de que
e outras s
o que em
Por supo
tada sozin
do banco
consistente
final també
sma razão
de um est
s o término
Execuçõe
problema
almente e
mesmo c
s se e som
e E' come
mo estado 
os mesmo
T um c
escalonam
m escalon
nó i tal qu
x de W(Y
W(Z) entre W
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 11 
ra condiçã
 segunda c
orrência t
dentro dos
e cada t
se este mé
uma exec
osição, ca
nha. Logo
 após a e
e. Assim,
ém o será
o, nenhum
ado consis
o da anteri
s 
a de defin
equivalente
conjunto T
mente se
eçam no m
final do ba
os dados e
conjunto d
mento glob
namento lo
ue x 
Y) em Li se
W(Y) e R(X
ologia do Par
sil 
II 
ão para es
condição. 
trivial, qu
s critérios
ransação 
étodo é se
cução seria
ada transa
, se o es
execução 
se o est
á, o que s
ma transa
stente. Fin
or, obviam
nir o que 
es. Intuitiv
T de tra
as seguin
mesmo es
anco de da
em E e E'. 
de transaç
bal L. Sejam
ocal Li de 
e W(Y) pre
X) em Li tal 
ra – IFPA 
scaloname
e só pe
 estabelec
é execu
eguido. 
al S anom
ação pres
stado inicia
da :f/i/- é
tado inicia
significa qu
ação lê d
nalmente, c
mente nenh
significa 
vamente, 
ansações 
ntes condi
stado do b
ados; 
ções e E
m R(X) e 
L. Seja x
ecede R(X
que x 
entos 
rmite 
cidos 
utada 
malias 
serva 
al do 
ésima 
al do 
ue S 
ados 
como 
huma 
duas 
duas 
são 
ições 
anco 
E um 
W(Y) 
x um 
X) em 
 
Facili
nenh
atua
imag
trans
Seja
E e 
trans
esca
proc
leitu
tador: Prof. 
Z. Seja
X. Dire
hum W(Y).
Y. Dire
W(Y) 
alização em
Y. Est
ginássemo
sação fina
Sejam
am L= { L1
E'. Direm
[1,n]: 
1. Lj e 
sação oco
2. para
X, R(X
3. para
Y, W(Y
em Lj s
4. para
X 
Y, R(X
Lj se e 
Direm
alonamento
Intuitiv
cessada da
ra lêem o
Instituto F
Msc. Marcos
a y 
emos que 
. Similarme
emos que 
cria o valo
m Li tal que
tas duas ú
os uma tra
l que "lê" o
 E e E' d
1 ,..., Ln } e 
os que E 
Lj' contém
orrem na m
a cada obj
X) lê o valo
a cada obj
Y) cria o va
se e somen
a cada R(X
X) lê x de W
somente s
mos ainda 
os equivalen
vamente, 
a mesma f
os mesmo
M
Federal de Ed
Univ
Dis
s Vinicius Sad
R(X) lê o
ente, seja
or final de
e z 
últimas no
ansação in
o estado fi
duas exec
L' = { L'1 
e E' são e
m as mesm
mesma orde
eto físico x
or inicial de
eto físico x
alor final d
nte se o fa
X) em Lj, pa
W(Y) em 
se o faz em
que L
ntes. 
esta def
forma em 
os valores
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
valor inici
z 
e z em Li 
oções pode
nicial que "
nal produz
cuções pa
,..., L'n } es
equivalent
mas ações
em relativa
x, para cad
e x em Lj s
x, para cad
de x 
az em Lj' ; 
ara cada W
m Lj'. 
e L'
finição ga
ambas as
s. Além di
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 12 
ial de y em
se W(Y)
eriam ser
"cria" o es
zido por E.
ra um con
scaloname
tes se e so
elementa
a em amba
da R(X) em
se e somen
da W(Y) e
W(Y) em Lj
são 
arante qu
s execuçõe
isto, oest
ologia do Par
sil 
II 
m Li se R(X
é a última
reduzidas
stado inicia
njunto T d
entos glob
omente, pa
res, e as a
as. 
m Lj tal que
nte se o faz
m Lj tal qu
j, para cada
ue cada 
es pois as
tado final 
ra – IFPA 
(X) não lê 
a operaçã
s à primeir
al de E, e 
de transaç
ais model
ra todo j 
ações de 
e x 
z em Lj' ; 
e x 
a x 
transaçã
 operaçõe
do banco
y de 
o de 
ra se 
uma 
ções. 
ando 
cada 
o é 
es de 
o de 
 
Facili
dado
mes
um e
exec
refor
exec
que 
em 
seria
elas 
ques
exec
das 
equi
conc
cent
físico
seqü
segu
tador: Prof. 
os é o me
ma operaç
8.2.3 E
Seja E
escalonam
cução seria
Portan
rmulado co
toda ex
Um mé
cuções ser
nenhuma 
execuçõe
alizáveis s
herdam, 
stão em t
cuções ser
transaçõ
valentes, a
O rest
ceito de 
tralizado c
os D = { 
üenciais ge
L1 = R1
L2 = R2
Há ape
S12 = R
S21 = R
Exemp
uintes esca
E1 = R
Instituto F
Msc. Marcos
esmo, pois
ção de atu
Execuçõe
E uma exec
mento L. E 
al. Diremo
nto, o crit
omo: C2'. 
xecução d
étodo de c
rializáveis 
anomalia 
s seriais 
são comp
então, es
termos de
riais são "n
ões. Porta
a proprieda
to desta se
serializaç
cujo esque
x, y }. C
eram, resp
1(X) W1(X) 
2(y) W2(X).
enas dois p
R1(X) W1(X
R2(y) W2(X
plo. Além 
alonament
1(X) R2(y) 
M
Federal de Ed
Univ
Dis
s Vinicius Sad
s o valor f
alização e
es Seriali
cução para
é serializá
s também
tério C2 d
e um conju
controle de
das transa
de sincro
tais anom
putacionalm
sta proprie
e anomalia
naturalmen
anto, ger
ade de cor
eção apre
ção. Cons
ema interno
Considere
pectivamen
. 
possíveis e
X) R2(y) W2
X) R1(X) W1
de S12 e
tos também
W1(X) W2(
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
final de ca
m ambas a
izáveis 
a um conju
ável se e 
que L é u
da Seção
unto de tra
e concorrê
ações. Co
nização ap
malias nã
mente equ
edade. Se
as de sinc
nte correta
ando ape
rreção é m
senta uma
sidere inic
o é mode
duas tran
nte, as seq
escalonam
2(X) 
1(X). 
S21, que
m são seria
(X) 
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 13 
ada objeto
as execuçõ
unto T de t
somente s
m escalon
o 8.1.1.3 
ansações T
ência deve
m isto o m
parecerá.
o ocorrem
uivalentes
e o leitor 
cronização
as" do pon
enas exe
mantida. 
a série de
cialmente 
lado por u
sações, T
üências de
mentos seri
são obvia
alizáveis:
ologia do Par
sil 
II 
 físico foi 
ões. 
transações
se for equ
namento se
pode ser 
T deverá s
rá então p
método est
A justifica
m; como 
às exec
preferir n
o, basta a
nto de vista
ecuções q
exemplos
um ban
um conjun
T1 e T2, cu
e ações ele
iais neste c
amente se
ra – IFPA 
produzido
s modelada
ivalente a 
erializável.
precisam
er serializá
permitir ap
tará garan
tiva é sim
as execu
cuções se
não analis
rgumentar
a da exec
que lhes 
s envolven
co de d
nto de ob
ujas execu
ementares
caso: 
erializáveis
 pela 
a por 
uma 
 
mente 
ável. 
enas 
tindo 
mples: 
uções 
eriais, 
sar a 
r que 
cução 
são 
ndo o 
ados 
bjetos 
uções 
s: 
s, os 
 
Facili
y em
R1 (x
esca
distr
mod
mes
com
esca
seria
sem
inter
apar
a or
tador: Prof. 
E2 = R2
Ambos
m S12, pod
x), obtend
alonamento
Como 
ribuído ar
delados po
D1 = { 
mos dados
L= {L1,
L1 = R2
L2 = W
que é 
pletamente
Como 
N = {N
N1 = R
N2 = R
e 
N' = {N
N1' = R
N2' = W
No p
alonamento
al. Não é p
 alterar a
ressante p
recem na 
rdem das 
Instituto F
Msc. Marcos
2(y) R1(X) 
s são equ
demos com
o E2. O le
os serializá
um segun
rmazenado
or dois con
x1, y1 } e D
s. Um exe
,L2}, onde 
2(x1) R1(y1)
W2(x2) R1(x2
equivalen
e antes de
exemplos 
1,N2}, onde
R1(y1) R2(x1
R1(x2) W1(x2
N1',N2'}, ond
R2(x1) W2(x
W2(x2) R1(x
primeiro e
o local N1
possível, in
a computa
pois N1' 
ordem troc
ações sem
M
Federal de Ed
Univ
Dis
s Vinicius Sad
W1(X) W2(
ivalentes
mutar esta
eitor deve
áveis além
ndo exemp
o em do
njuntos de
D2 = { x2 }.
mplo de um
) W2(x1) W1
) W1(x2) 
nte ao esc
e T1 ser pro
de escalo
e 
) W1(x1) W
2) W2(x2) 
de 
x1) R1(y1) W
x2) W1(x2) 
exemplo,
1 já não o
ntuitivamen
ação expr
e N2' são
cada em c
m alterar
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
(X). 
a S12 pois
a ação com
se conven
m de S12 e S
lo, conside
ois nós
e objetos fí
Suponha
m escalona
1(x1) 
calonamen
ocessada.
namentos 
W2(x1) 
W1(x1) 
N não
o torna eq
nte, trazer
ressa por
o por si
cada um.
a computa
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 14 
s, como R
m W1(x) ob
ncer que e
S21. 
ere novam
cujos es
ísicos, 
que x1 e x
amento se
nte serial e
 
não serial
é seriali
quivalente
R2(x1) par
N1. O s
só seria
Além disto
ação final.
ologia do Par
sil 
II 
R2(y) lê o v
btendo E1,
estes são 
mente um b
squemas 
x2 armazen
erializável s
em que T
izáveis ter
izável po
a algum e
ra junto de
egundo e
is, mas a
o, não é p
 Este exe
ra – IFPA 
valor inicia
, e depois 
os dois ún
banco de d
internos 
am cópias
seria 
2 é execu
ríamos 
ois o pr
escalonam
e W2(x1) em
exemplo, N
as transa
possível al
emplo ilust
al de 
com 
nicos 
ados 
são 
s dos 
utada 
óprio 
mento 
m N1 
N', é 
ações 
lterar 
tra o 
 
Facili
fato 
todo
pode
ante
um 
conc
esca
(mai
nece
segu
T. S
Lk co
dela
pois
exec
e W
obvi
para
de a
poss
de d
oper
em L
Oi e
estiv
prec
esca
oper
relaç
mais
distin
tador: Prof. 
de que 
os os esca
erá não o s
A car
erior captu
ambiente 
corrência. 
alonamento
is precisam
8.2.4 U
Nesta 
essária) pa
uintes para
Seja T
eja Lk um 
onflitam se
s é uma o
, se a su
cução pod
W(X). Supo
amente nã
X que 
a '... W(X) 
atualização
sivelmente
dados. Um
rações de 
Lk (denota
e Oj conflit
ver em jogo
De po
cede por co
alonamento
rações de 
ção de pre
s de uma d
nguí-las. 
Instituto F
Msc. Marcos
serializaçã
alonamento
ser. 
acterizaçã
ra correta
concorren
Na verda
o é serializ
mente, NP-
Uma Con
seção se
ara garan
a provar a 
T um conju
escalonam
e e somen
operação d
ua ordem
erá ser m
onha que 
ão lê o valo
foi criado 
... R(X) ...
o para xX
e (mas não
m cenário 
atualizaçã
ado por Oi 
tam. Quan
o, subscrito
osse desta
onflito T j e
o local Lk 
Ti e Tj res
ecedência 
destas rela
M
Federal de Ed
Univ
Dis
s Vinicius Sad
ão não p
os locais s
ão de exe
mente o c
nte, mas a
ade é po
zável é, pr
-Completo
ndição Su
erá aprese
tir serializa
correção d
unto de tra
mento loca
nte se elas
de atualizaç
 relativa
odificado.
Lk seja d
or de x 
por W(X). 
' e entre W
X, R(X) pa
o necessa
semelhant
ão. Definir
< Oj) se e
ndo mais d
os serão u
a relação 
em L (deno
de L e op
spectivame
por conflit
ações estiv
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
ode ser 
sejam ser
ecuções s
conceito de
ainda não
ossível pr
rovavelme
). 
uficiente p
entada um
ação. Esta
de métodos
ansações e
al de L. D
s agem so
ção. Opera
for altera
Considere
da forma
Se a ordem
W(X) e R(X
ssará ago
riamente) 
te poden
emos aind
e somente
de uma re
usados par
entre açõ
otado por T
perações O
ente e Oi <
to para T i
verem em j
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 15 
detetada 
ializáveis,
serializáve
e atomicid
o leva a m
rovar que
nte, comp
para Seria
ma condiç
a condição
s de contro
e L um es
uas ações
bre um me
ações con
ada em L
e, por exem
'... R(X) 
m das ope
X) não hou
ora a ler o
alterando 
naturalmen
da que Oi 
e se Oi oco
elação de 
ra distinguí
ões eleme
Ti < T j) se
Oi e Oj em
< Oj. A rela
nduzida po
jogo, subs
ologia do Par
sil 
II 
localmente
o escalon
eis dada 
dade das t
métodos d
apenas 
utacionalm
alização 
ção suficie
o será usa
ole de conc
calonamen
s elementa
esmo obje
flitantes sã
Lk, o resu
mplo, as o
... W(X) .
erações for
uver uma o
o valor cri
o estado 
te ser cria
precede c
orre antes 
precedênc
í-las. 
entares, d
e e soment
m Lk tais qu
ação < ser
or L. Nova
scritos serã
ra – IFPA 
e: mesmo 
namento g
pela defin
transações
de controle
testar se
mente intra
ente (mas 
da nas se
corrência. 
nto global 
ares Oi e 
to físico e 
ão importa
ultado fina
operações 
...'. Logo 
r trocada e
outra oper
ado por W
final do b
ado para 
com conflit
de Oj em 
cia por co
iremos qu
te se exist
ue Oi e Oj
rá chamad
amente qu
ão usados 
que 
global 
nição 
s em 
e de 
e um 
atável 
não 
eções 
para 
Oj de 
uma 
antes 
al da 
R(X) 
R(X) 
m Lk 
ração 
W(X), 
anco 
duas 
to Oj 
Lk e 
onflito 
ue Ti 
ir um 
j são 
da de 
ando 
para 
 
Facili
uma
Se a
relaç
exec
prec
parc
de T
segu
todo
conj
mod
T ind
que 
F, o
trans
Assi
elem
resp
com
uma
Oi d
prec
são 
esca
exec
do q
cons
hipó
tador: Prof. 
Podem
TEOR
a execução
a relação 
ção de ord
Demos
Provar
cução E d
cedência p
cial, então 
T. 
BASE:
ue trivialme
o conjunto 
unto de 
delada por 
duzida por
Seja T
Tj <L Ti. Co
onde Ti é 
sações em
m, cada e
mentares d
peitando a 
 a relação
a ação ele
e Ti em L
cede algum
equivalent
Constr
alonamento
cução do c
que n. Alé
strução, G
tese de ind
Instituto F
Msc. Marcos
mos, então
EMA 1: S
o de T mo
de prece
dem parci
stração 
remos que
de T mode
por conflito
E é seriali
: Suponha 
ente. PASS
de transa
transaçõe
um escal
r L seja um
Ti uma tran
onstrua um
inicialme
m T são ex
scaloname
de Ti no 
sua ordem
o <M. Além
mentar Oj
Lk tais que
ma ação e
tes. 
rua agora 
o global 
conjunto de
m disto, a
G é uma s
dução, pod
M
Federal de Ed
Univ
Dis
s Vinicius Sad
, mostrar o
Seja T = {
odelada po
dência po
al, então 
e, para to
elada por u
o para T
izável. A p
que T ten
SO DE IN
ções com 
s com ca
lonamento
ma relação 
sação em
ma execuçã
nte execu
xecutadas 
ento local 
escanolam
m relativa)
m disto, co
j de algum
e Oj <L Oi. 
elementar O
G retirand
representa
e transaçõ
a relação <
ubseqüênc
demos ent
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
o seguinte:
T1 ,..., Tm
or um esca
or conflito
E é seriali
odo conju
um escalo
induzida 
prova será
ha apenas
DUÇÃO: S
cardinalid
ardinalidad
o global L.
de ordem 
T tal que
ão F de T,
utada seqü
concorren
Mk de F é
mento loc
). Por cons
mo não e
ma transaçã
Ou seja,
Oi de Ti em
o as ações
ando G. 
es U = T -
<N é um su
cia de E.
ão conclui
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 16 
: 
m } um conj
alonament
para T i
zável. 
nto T de
namento g
por L for
por induç
s uma tran
Suponha q
dade meno
de n e E
 Suponha
parcial. 
para nenh
, modelada
üencialme
ntemente e
obtido traz
al Lk de
strução, a
existe Tj ta
ão Tj em T
nenhuma
m Lk confli
s elementa
Teremos 
{ Ti }, que 
ubconjunto
Logo, <N 
r que G é 
ologia do Par
sil 
II 
junto de t
to global L
nduzida p
 transaçõ
global L, s
uma rela
ção sobre a
sação. En
que o resu
or do que 
E uma ex
 que a re
huma trans
a por um e
nte e dep
exatament
zendo-se t
L para a
relação <
al que Tj <
T, e uma a
a ação ele
ita com Oi
ares de Ti 
então qu
tem cardin
o da relaçã
também é
serializáve
ra – IFPA 
ransações
L = { L1 ,...
por L for 
ões, para 
e a relaçã
ção de or
a cardinali
tão o resu
ltado vale 
n. Seja T
xecução d
elação <L s
sação T j te
escalonam
pois as o
te como e
todas as a
a esquerd
<L coincide 
L Ti, não e
ação eleme
ementar Oj
i Assim, E
de F. Seja
ue G é 
nalidade m
ão <L pois
é acíclica. 
el. 
s e E 
.,Ln }. 
uma 
toda 
ão de 
rdem 
dade 
ltado 
para 
T um 
de T 
sobre 
emos 
mento 
utras 
m E. 
ações 
a (e 
com 
existe 
entar 
Oj que 
E' e E 
a N o 
uma 
menor 
s, por 
Pela 
 
Facili
exec
outra
fato 
e F 
seria
nece
cent
trans
outro
a ex
escr
segu
para
seria
em 
bloq
méto
cham
méto
bem
bloq
tador: Prof. 
Seja 
cução seria
as transaç
de SG e 
eram equ
alizável. 
Para v
essária, c
tralizado: 
L = R1
Como 
sações ind
o lado, L é
S = R1
pois os
xecução d
reve sobre 
Os mé
uem garan
a as transa
alizáveis. 
8.3 M
Esta s
um ambie
ueios e tra
odo de us
mado de b
odo é prov
8.3.1 P
Nesta 
m como as
ueados. 
Instituto F
Msc. Marcos
SG uma 
al SF das 
ções em T 
G serem e
ivalentes. 
ver que a
considere 
(x) W2(x) W
T1 < T2 <
duzida por
é equivalen
(x) W1(x) W
s valores d
e T3, nem
eles. 
étodos de 
ntirão que 
ações em 
ÉTODOS
seção disc
ente centr
atamento d
so de blo
bloqueio e
vada. 
Protocolo
seção um
s questões
M
Federal de Ed
Univ
Dis
s Vinicius Sad
execução
transaçõe
na mesma
equivalent
Logo, SF
a condição
o seguint
W1(x) W3(x
< T1, a re
r L não é
nte ao seg
W2(x) W3(x
de x atual
m para o e
controle d
a relação
processam
 BASEAD
cute o uso 
ralizado. I
de bloque
oqueios pa
m duas fa
o de Bloq
 protocolo
s de tipos
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
o serial e
es em T pr
a ordem q
tes, SF e F
e E são e
o apresen
te escalon
x) 
elação de
é uma rela
uinte esca
x) 
izados por
stado fina
e concorrê
< é semp
mento e, a
DOS EM B
de bloque
nicialmente
ios mútuos
ara atingir
ases, é ap
queio de O
de bloque
s de bloq
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 17 
equivalente
rocessando
ue em SG
F serão en
equivalente
ntada no
namento e
precedênc
ação de o
lonamento
r T1 e T2 n
l do banco
ência desc
pre uma re
assim, que
BLOQUEIO
eios para 
e os prob
s são abo
r apenas 
presentado
Objetos 
eio/liberaçã
ueio e gra
ologia do Par
sil 
II 
e a G. C
o Ti prime
G. Por con
ntão equiv
es, o que 
teorema a
em um ba
cia por co
ordem par
o serial: 
ão contrib
o de dado
critos nas 
elação de 
 todas as e
OS - PAR
controle d
blemas de
rdados. E
execuções
o. Por fim, 
ão de obje
anularidad
ra – IFPA 
Construa 
iro e depo
nstrução e 
valentes. M
prova que
anterior nã
anco de d
onflito par
rcial. Mas,
uem nem 
s já que W
seções qu
ordem pa
execuções
RTE I 
e concorrê
e gerência
m seguida
s serializá
a correçã
etos é disc
de dos ob
uma 
ois as 
pelo 
Mas E 
e E é 
ão é 
ados 
ra as 
, por 
para 
W3(x) 
ue se 
arcial 
s são 
ência 
a de 
a, um 
áveis, 
ão do 
cutido 
bjetos 
 
Facili
obje
exemobje
elem
outra
simp
um c
elem
cent
esca
uma
trans
tador: Prof. 
Consid
tos a sere
mplo). Sup
to só pode
bloque
permit
livre 
não pe
Neste 
mentares a
(que co
B(x) 
bloque
L(X) 
libere t
Note q
as ações 
ples, confo
Para a
conjunto d
mentares R
tralizado. 
alonamento
Estas 
a tabela de
 
X é o n
T é o n
F é u
sações qu
Instituto F
Msc. Marcos
deremos i
em bloque
ponha aind
e estar em 
eado 
e acesso a
ermite aces
caso é 
ao nosso re
ontém até 
eie o objeto
todos os o
que B(x) 
elementar
orme verem
acomodar 
de transaç
R(X), W(X)
Esta se
o. 
ações são
e bloqueios
nome de u
nome da tr
uma fila d
e esperam
M
Federal de Ed
Univ
Dis
s Vinicius Sad
nicialment
ados são
da que só
dois estad
ao objeto a
sso ao obj
necessár
epertório 
o moment
o cujo nom
objetos cujo
afeta ape
res. Esta o
mos. 
estas nov
ções será r
), B(x) ou L
eqüência
o passadas
s, modelad
m objeto 
ransação q
e espera
m a liberaçã
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
e o caso
de uma m
há um mo
dos: 
apenas pel
eto por ne
rio introdu
to apenas
me é x; 
os nomes e
enas um
opção torn
vas ações
representa
L(X) proce
continua
s para o g
da como um
que corrent
para x c
ão de x 
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 18 
mais sim
mesma cla
odo de blo
la transaçã
nhuma tra
uzir apen
R(X) e W(X
estão em X
único obje
na o tratam
s elementa
ada agora p
essadas co
rá a s
gerente de
ma coleção
temente bl
contendo 
ologia do Par
sil 
II 
mples em 
sse (págin
queio, ou 
ão que det
nsação. 
as duas 
(X)): 
X; 
eto, difere
mento de b
ares, uma
pela seqüê
ontra o ba
er cham
e bloqueios
o de triplas
loqueia x 
os nomes
ra – IFPA 
que todo
nas físicas
seja, que 
ém o bloqu
novas a
entemente 
bloqueios 
a execuçã
ência de a
anco de d
mada de 
s, que ma
s (x,T,F) on
s de toda
os os 
s, por 
cada 
ueio; 
ações 
das 
mais 
o de 
ações 
ados 
um 
ntém 
nde: 
s as 
 
Facili
cheg
com
gara
atrav
indic
atrav
cujo 
para
enco
liber
prim
cont
cont
lega
e um
proc
nos 
assu
inco
tador: Prof. 
Supore
gar-primeir
 prioridad
antir que u
A noç
vés de um
ca a fila va
1) Inici
2) Ao 
vés da aç
primeiro e
a) se n
a T, acresc
b) caso
ontrada. 
3) Ao 
rar os obje
X, pes
meiros elem
a) se 
trário, seja 
i) se a 
ii) se a
trole de x 
para T
Diz-se
l se e som
ma ação e
cessada de
referirmos
umindo que
O pro
rporando-s
Instituto F
Msc. Marcos
emos que 
ro-a-sair. E
de, por e
ma transa
ção de um
m protocol
zia): 
ialmente a
receber so
ção B(x), p
elemento s
nenhuma t
centando a
o contrário
receber s
etos em X, 
squise a t
mentos seja
nenhuma 
(x,T,F) a t
fila F estiv
a fila F não
T', substitui
 que uma
mente se 
elementar 
epois que 
s a um esc
e é legal. 
otocolo b
se modalid
M
Federal de Ed
Univ
Dis
s Vinicius Sad
as filas de
Esta políti
exemplo.
ação não fi
m objeto
lo de bloq
a tabela de 
olicitação p
pesquise a
seja x: 
ripla for en
a tripla (x,T
o, acrescen
solicitação
para cada
abela de 
am x, T: 
tripla for e
tripla enco
ver vazia, r
o estiver v
ndo a tripla
a execução
obedece a
de uma t
x for bloqu
calonamen
ásico de
dades (ou
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
e espera s
ca poderia
Porém, q
ica eternam
estar bloq
queio e libe
objetos bl
para bloqu
a tabela de
ncontrada (
T, ) à tabela
nte T ao fin
da transa
a x 
bloqueios 
encontrada
ntrada: 
retire a trip
vazia, ou s
a (x,T,F) n
o (e o es
ao protoco
transação
ueado par
nto com bl
bloqueio
modos) d
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 19 
eguem a p
a ser alte
qualquer p
mente na f
queado ou
eração de 
oqueados 
uear o obje
e bloqueio
(ou seja, s
a. 
nal da fila d
ação T atr
procurand
a, ignore a
pla da tabe
seja, se for
a tabela d
calonamen
lo de bloq
Ti que ac
a Ti. De ag
oqueios, e
o/liberação
iferentes d
ologia do Par
sil 
II 
política est
erada, ado
política ad
fila de esp
u livre é 
objetos d
está vazia
eto x para 
os procura
se x está liv
de espera 
avés da a
do uma tr
a liberação
la, liberand
r da forma
e bloqueio
nto que a 
ueio/libera
cessa um 
gora em d
estaremos 
 pode s
de bloquei
ra – IFPA 
trita primei
otando-se 
dotada de
pera. 
implemen
definido co
a. 
 a transaç
ando uma 
vre), bloqu
para x na 
ação L(X) 
ipla cujos 
o de x. b) 
do x. 
a T'.F', pas
os por (x,T'
represent
ação de ob
objeto x 
diante, qu
implicitam
ser melho
io. Uma o
iro-a-
filas 
everá 
ntada 
omo ( 
ção T 
tripla 
ueie x 
tripla 
para 
dois 
caso 
sse o 
',F'). 
ta) é 
bjetos 
só é 
ando 
mente 
orado 
pção 
 
Facili
seria
sign
parti
bloq
trans
mod
indic
não 
simp
sem
matr
conf
x em
x em
trans
Assi
parti
a ún
expr
são 
de b
que,
orga
y, d
tador: Prof. 
a adotar 
ifica que 
ilhadamen
ueiam o o
bloque
sação que
livre: n
Uma 
dalidades 
cando qua
o podem f
A just
ples. Duas
 perigo de
riz de com
flitará com
m modo ex
m qualquer
Cabe o
sações dif
m, se um
ilhada e de
nica transaç
O prot
ressa pelas
omitidas n
Um se
bloqueio/lib
 em lug
anizados s
diremos qu
Instituto F
Msc. Marcos
duas mo
agora um
te: permit
bjeto partil
eado exclu
e o bloque
não permite
forma m
de bloque
ndo duas 
fazer: 
d
ificativa p
s ou mais
e conflito, 
mpatibilidad
 qualquer 
xclusivo, n
r modo (en
observar q
ferentes, e
ma transaçã
esejar bloq
ção que no
tocolo de 
s modalida
neste texto
egundo me
beração c
gar de o
sob forma 
ue x cobr
M
Federal de Ed
Univ
Dis
s Vinicius Sad
odalidades
m objeto 
te acesso
hadament
usivamente
ia exclusiv
e acesso a
mais prec
eio seria a
transaçõe
 
partilh
exclusi
ara as m
s transaçõe
bloquean
des). Por 
outra tran
não permiti
ntradas 'NÃ
que a matr
e não se
ão já man
queá-lo na
o momento
bloqueio/l
ades de bl
. 
elhoramen
criando-se
objetos de
de uma fl
re y. Por 
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
de bloqu
poderá es
ao objet
te; 
e: permite
vamente; 
ao objeto p
cisa de
através de
s podem b
p
d
h S
i N
modalidades
es poderã
do-o em m
outro lad
sação que
indo que n
ÃO' na mat
riz de com
aplica a a
ntém um o
a modalida
o mantém 
iberação d
oqueio. As
nto pode a
uma hie
e uma ú
loresta. Se
exemplo, 
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 20 
ueio, part
star em t
to por tod
e acesso
por nenhum
definir a
e uma ma
bloquear o
partilh
SIM 
NÃO 
s de bloq
o ler o ob
modo part
o, se uma
e acesse x
nenhuma o
triz de com
mpatibilidad
ações de
objeto x bl
ade exclus
x bloquead
deverá en
s modificaç
ainda ser i
rarquia de
única clas
e um obje
considere
ologia do Par
sil 
II 
tilhado e 
três estad
das as tr
ao objeto
ma transaç
a compa
atriz de co
o mesmo d
exclu
NÃO
NÃO
queio acim
bjeto x sim
ilhado (en
a transaçã
x. Logo d
outra trans
mpatibilidad
desse refe
uma mes
loqueado 
siva, poder
do. 
tão incorp
ções, por s
ncorporad
e objetos.
sse, os o
eto x for u
e objetos 
ra – IFPA 
exclusivo. 
os: bloqu
ransações 
o apenas 
ção; 
tibilidade 
ompatibilid
dado e qu
usi
O 
O 
ma definid
multaneam
trada 'SIM
ão atualiz
everá bloq
sação bloq
des). 
ere a açõe
sma transa
na modali
rá fazê-lo s
porar a po
serem sim
o ao proto
. Suponha
objetos s
um ancestr
de três t
Isto 
eado 
que 
pela 
das 
dades 
ando 
as é 
ente, 
M' na 
a X, 
quear 
queie 
es de 
ação. 
dade 
se for 
olítica 
mples, 
ocolo 
amos 
ejam 
ral de 
tipos: 
 
Facili
segm
pági
nenh
bloq
todo
bloq
pági
prop
gerê
diga
bloq
hiera
bloq
mes
nece
trans
dete
trans
Dest
de b
G=(N
bloq
tal q
tador: Prof. 
mentos, pá
nas e cad
Dentro
hum dos 
uear/libera
os os obj
ueado se 
nas estive
A just
porciona e
ência da 
mos, 90%
uearia o 
arquizados
ueios em
ma tarefa
essidade). 
Com is
8.3.2 T
8.3.2.
O uso
sações a 
erminado 
sações Ti 0
ta forma, 
bloqueio m
Bloque
N,A) para 
N é o
ueando ob
A é o 
ue Ti ocorr
Instituto F
Msc. Marcos
áginas e 
a página s
o deste es
objetos q
ar um ob
eto que 
nenhuma
erem bloqu
tificativa p
em termos
tabela de
% das 1
segment
s seriam n
m objetos 
a (embora 
sto encerra
Tratamen
1 Caracte
o de bloq
não term
ponto da 
0 ,Ti 1 ,..., T
nenhuma 
mútuo. A se
eios mútuo
o estado c
o conjunto
bjetos quan
conjunto d
re em F (o
M
Federal de Ed
Univ
Dis
s Vinicius Sad
palavras.
será pai de
quema, um
que x cob
bjeto x, i
x cobre.
a de suas
eadas. 
para este
s de mem
e bloqueio
000 pág
o inteiro.
ecessárias
hierarquiz
100 pági
a-se a disc
nto de Blo
erização d
queios, se
minarem. 
execuçã
Ti m-1, Ti 0 t
destas tra
eqüência é 
os são car
corrente da
o de tran
nto nas fila
de arcos (
ou seja, Ti e
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
Um segm
e todas as 
ma transaç
bre estive
mplicitame
Por exem
páginas e
tipo de
mória ocup
os. Por e
inas de
Sem o
s 900 entra
zados, ap
nas fosse
cussão pre
oqueios M
e Bloquei
em preocu
Mais pre
o concorr
tal que Ti j
ansações
chamada 
acterizado
a tabela de
nsações q
as de espe
Ti, Tj ) tais
espera por
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 21 
mento será
suas palav
ção pode 
r bloquea
ente estar
mplo, um
e nenhum
bloqueio
pada e tem
exemplo, e
um segm
uso de 
adas na ta
penas um
em implicita
liminar sob
Mútuos 
os Mútuo
upações a
ecisamente
rente crie
espera po
terminará
de seqüên
os definind
e bloqueios
ue ocorre
era; 
s que há u
Tj liberar o
ologia do Par
sil 
II 
á pai de t
vras. 
bloquear u
do. Uma 
rá bloque
 segment
a das pal
está na 
mpo adici
em lugar 
mento, um
bloqueios
abela de b
ma entrada
amente blo
bre bloque
s 
adicionais, 
e, é poss
e-se uma 
or Ti j+1 (so
e tem-se 
ncia de imp
o-se o dig
s TB da se
em na tab
uma tripla (
o objeto x)
ra – IFPA 
todas as 
um objeto 
transação
eando/liber
to poderá
avras de 
economia 
onal gasto
de bloqu
ma trans
s em ob
bloqueios. 
a cumprir
oqueadas 
eios. 
poderá 
sível que 
seqüência
ma módulo
uma situ
passe. 
grafo de es
guinte form
bela TB 
(x,Tj ,F) em
. 
suas 
x se 
o ao 
ando 
á ser 
suas 
que 
o na 
uear, 
ação 
bjetos 
Com 
ria a 
sem 
levar 
em 
a de 
o m). 
ação 
spera 
ma: 
tanto 
m TB 
 
Facili
G fo
de G
mútu
segu
em d
um p
simp
form
sere
ciclo
mom
obje
mes
even
reini
foi s
antig
um o
usad
cont
seria
cada
ação
A ún
exig
tador: Prof. 
É fácil 
oi construí
G represen
As du
uos, deteç
uintes. 
8.3.2.2
O trata
deixar as 
processo in
Para 
plesmente 
 
Para 
ma. Se há 
em retirada
o de G, é 
mento. Ca
tos que bl
ma transa
ntualmente
ciar, não a
submetida 
ga sempre 
8.3.2.3
A form
objeto sem
do em ce
trole de 
alizáveis. 
Uma o
a transação
o indivisíve
nica vantag
e que todo
Instituto F
Msc. Marcos
observar 
do se e s
nta uma s
uas forma
ção/resolu
2 Detecçã
amento de
transaçõe
ndependen
detetar a
constroi o
resolver b
ciclos em
as de G o
seleciona
ada transa
loqueava. 
ação não 
e terminar
a transação
por últim
termina. 
3 Prevenç
ma mais si
mpre que a
ertos caso
concorrên
outra forma
o bloqueie
el, que é ex
gem deste
os os obje
M
Federal de Ed
Univ
Dis
s Vinicius Sad
que bloqu
somente se
seqüência
as básica
ução e pr
ão / Resol
e bloqueios
es processa
nte P para
a existênc
 grafo de e
bloqueios
 G, transa
o novo gra
da a trans
ação selec
Cuidado d
seja reinic
r. Uma té
o que cons
o. Assim
ção de Blo
mples de
a transação
os, é tota
ncia pois 
a de preve
e todos os o
xecutada a
e esquema
etos que u
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
ueios mútu
e G for ac
de impass
s para t
revenção, 
ução de B
s mútuos
arem norm
 detectar /
cia de bl
espera G, 
mútuos,
ações são
afo se torn
sação que
cionada é 
deve ser to
ciada repe
écnica pa
sumiu men
o sistema
oqueios M
evitar bloq
o pedir nov
almente in
permite 
enir bloque
objetos qu
antes da tr
a é a sua 
ma transa
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 22 
uos não oc
cíclico. Ca
se. 
tratar o p
serão dis
Bloqueios
por detecç
malmente e
resolver b
oqueios m
testando s
o process
seleciona
ne acíclico
e consumiu
reiniciada
omado, no
etidamente
ra se evi
nos recurs
a garantiria
Mútuos 
queios mú
vo bloquei
satisfatório
a criaçã
eios mútuo
e irá acess
ransação a
aparente 
ação irá ac
ologia do Par
sil 
II 
correm no 
aso contrá
problema 
scutidas n
 Mútuos 
ção / reso
e, periodic
bloqueios m
mútuos, o
se G é acíc
so P age
das de tal
. Usualme
u menos r
a, liberand
o entanto, 
e, o que a
itar esta 
os, mas a 
a que a tr
útuos cons
o. Este m
o do pont
ão de ex
os consiste
sar através
acessar o p
simplicidad
cessar seja
ra – IFPA 
ponto em
ário, cada 
de bloqu
nas subse
olução con
camente, in
mútuos. 
o process
clico ou nã
e da seg
l forma qu
ente para 
recursos a
do primeiro
para que 
a impediri
situação 
transação
ransação 
siste em lib
método, em
to de vist
xecuções 
e em exigir
s de uma ú
primeiro ob
de. Porém
am conhec
m que 
ciclo 
ueios 
eções 
nsiste 
niciar 
so P 
o. 
uinte 
ue ao 
cada 
até o 
o os 
uma 
a de 
seria 
o que 
mais 
berar 
mbora 
a de 
não 
r que 
única 
bjeto. 
m, ele 
cidos 
 
Facili
inicia
bloq
para
para
trans
mod
prob
perc
ação
conc
um o
Se T
de x
bloq
trans
de p
irão 
espe
Há v
reini
recu
trans
se e
Vers
maio
cons
have
trans
pree
outra
prior
pode
seria
trans
tador: Prof. 
almente, o
uear mais
a sua imple
a permitir o
sação (em
dificação n
blemas de 
ceber este 
o elementa
Um te
corrência, 
objeto x, q
Ti e Tj pass
x. Caso con
ueio é sem
sação Tj q
preemptivo
O test
ser criado
era, isto si
vários teste
ciar Ti ao
ursos. Dois
sações, se
e somente 
são preem
or do que T
Estes 
sidere a ve
eria uma t
sação só e
emptiva, o 
a com prio
No en
ridades às 
erá ser con
a definir a
sação foi 
Instituto F
Msc. Marcos
oque nem
s objetos d
ementação
o bloqueio 
m lugar de
ecessária 
bloqueio m
fato. Foi j
ar que bloq
erceiro mé
seria o se
ue está pr
sarem pelo
ntrário Ti o
mpre a esc
ue detém 
. 
te escolhid
os ao adic
gnifica que
es possíve
o solicitar 
s testes m
eriam :ol at
se T j tiver
ptiva: deix
Ti; caso co
testes ga
ersão não- 
transação 
espera por
raciocínio 
oridade ma
ntanto, co
transaçõe
ntinuamen
a prioridad
submetida
M
Federal de Ed
Univ
Dis
s Vinicius Sad
m sempre
do que o n
o que o pro
de vários 
e apenas 
não é fác
mútuo. (O l
justamente
queasse ap
étodo, sati
eguinte. Qu
esentemen
o teste, Ti 
ou T j são 
colhida, o m
o bloqueio
do deverá 
ionar Ti à 
e a adição
eis com es
o bloque
mais razo
tomic. Ver
r prioridade
e Ti esper
ontrário can
arantem a
preemptiv
com prior
r outra com
é o mesm
ior. 
omo não 
es, o teste 
te cancela
de de um
a. A trans
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
e é possív
necessário
otocolo de 
objetos a
um de ca
cil de impl
leitor deve
e por este 
penas um o
isfatório d
uando uma
nte bloque
poderá en
cancelada
método é c
o é sempre
sempre g
fila de es
o do arco (
ta propried
io, que g
áveis, bas
rsão não-p
e menor do
rar por T j s
ncele T j. 
a ausência
va. Se hou
ridade ma
m prioridad
mo, exceto 
há restriç
não garan
ada. Um es
ma transaç
sação com
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 23 
vel, e que
o. Além dis
bloqueio/l
o mesmo 
ada vez, 
ementar e
rá tentar m
problema
objeto). 
o ponto d
a transaçã
eado para T
ntão ser ad
as. Se a tra
chamado d
e a escolhi
garantir qu
pera de x.
(Ti,Tj) ao g
dade. O m
eraria um
seados em
preemptiva
o que Ti; c
se e some
a de bloq
vesse um 
aior do que
de menor)
que uma 
ções sobre
nte que um
squema qu
ção como 
m menor d
ologia do Par
sil 
II 
e quase s
sto, este e
iberação s
tempo par
como ant
e poderá l
modificar o 
 que decid
de vista d
ão Ti pede
Tj, um test
dicionada à
ansação T
de não-pre
da, o méto
e bloqueio
. Em termo
grafo não 
ais simple
 desperdí
m priorida
: deixe Ti 
caso contrá
ente se T j 
ueios mú
ciclo no gr
e ela mes
). Para o c
transação
e a forma
ma transaç
ue evitaria 
a data/ho
data/hora 
ra – IFPA 
sempre le
esquema e
seja modifi
ra uma me
teriormente
evar mesm
protocolo 
dimos por 
de controle
 para bloq
te é execu
à fila de es
Ti que solic
eemptivo.. 
odo é cham
os mútuos
os do graf
irá criar ci
es seria sem
ício grande
ades dada
esperar po
ário cance
tiver priori
tuos. De 
rafo de esp
sma (pois 
caso da ve
o só espera
a de ass
ão termine
este prob
ora em qu
é conside
va a 
exige 
cado 
esma 
e). A 
mo a 
para 
uma 
e de 
quear 
tado. 
spera 
cita o 
Se a 
mado 
s não 
fo de 
iclos. 
mpre 
e de 
s às 
or T j 
le Ti. 
dade 
fato, 
pera, 
uma 
ersão 
a por 
ociar 
e: ela 
lema 
ue a 
erada 
 
Facili
com
que 
rece
gara
gara
sem
torna
vão 
trans
para
trans
gara
prec
que 
norm
de c
exec
da c
trans
este
seria
Por 
qual
tador: Prof. 
o a de ma
duas trans
eberá uma 
Este e
ante que 
antem que
pre termin
ará a trans
terminand
Técnic
sação já te
a instalar a
sação não
antir que, a
cisa. Assim
não partic
malmente. 
8.3.3 P
Consid
controle de
cução conc
1) toda
2) E é 
No ca
criação de
sação, o q
 problema
alização. 
O uso 
exemplo, c
1) bloq
2) liber
Este p
quer inter
Instituto F
Msc. Marcos
aior priorid
sações nã
prioridade
esquema, 
toda tran
e a transaç
na e que 
sação mai
o). 
cas preem
enha sido 
as modifiçã
o poderá 
ao atingir e
m, não esp
cipa de ne
Protocolo
dere agora
e concorrê
corrente E
as as trans
serializáve
aso do uso 
e bloqueio
que já foi d
a como r
de bloque
considere 
queie cada
re cada ob
protocolo é
rcalação d
M
Federal de Ed
Univ
Dis
s Vinicius Sad
dade ou a 
ão são sub
e única. 
acoplado
sação se
ção mais 
toda tran
s velha at
mptivas re
confirmad
ãoes produ
ser cance
esta fase, 
perará por 
nhuma se
o de Bloq
a o proble
ência corr
E permitida
sações inic
el. 
de bloque
os mútuos
discutido n
resolvido,
eios por si 
o seguinte
a objeto an
bjeto imedi
é obviame
das ações 
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
transação
bmetidas n
 com qua
mpre term
velha (de
sação, em
tiva no sist
equerem 
da, ou seja
uzidas pela
elada. Pa
a transaçã
nenhuma 
qüência de
queio em
ema de usa
reto, ou s
a pelo méto
ciadas em 
eios, violaç
s ou do c
a seção a
concentra
só não é 
e protocolo
tes de ace
atamente a
ente incor
das trans
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 24 
o mais vel
o mesmo 
alquer um
mina. De 
 mais alta
m um esp
tema (pois
um cuida
a, caso um
a transaçã
ra evitar 
ão detenha
outra tran
e impasse
Duas Fas
ar bloqueio
seja, que
odo 
E terminam
ções da pr
cancelame
anterior. C
ando a at
suficiente
: 
essá-lo; 
após aces
rreto pois
sações. Pa
ologia do Par
sil 
II 
ha do sist
instante, c
m dos test
fato, amb
a prioridad
aço finito 
s as mais 
ado adicio
ma decisão
ão no banc
este prob
a todos os
sação, o q
e e, portan
ses 
os para cr
garanta q
m; 
imeira con
nto repeti
onsiderare
tenção no
para ating
sá-lo. 
permitiria 
ara transfo
ra – IFPA 
tema. Sup
cada trans
tes anteri
bos os te
de) no sis
de tempo
velhas sem
onal. Cas
o já foi tom
co de dado
blema, dev
s bloqueios
que implica
to, irá term
riar um mé
que, para 
ndição resu
do da me
emos, port
o problema
gir serializa
a criação
ormar qua
ondo 
ação 
ores, 
estes 
tema 
o, se 
mpre 
so a 
mada 
os, a 
ve-se 
s que 
a em 
minar 
étodo 
toda 
ultam 
esma 
anto, 
a de 
ação. 
o de 
lquer 
 
Facili
esca
proto
entre
em 
segu
segu
liber
bloq
há u
grad
grad
do p
esca
mod
fase
duas
bloq
proto
bloq
tador: Prof. 
alonamento
ocolo, bas
e as ações
Aprese
bloqueios 
uinte. O p
uinte forma
1) Cad
rar todos o
2) Um
uear outro
O nom
uma prim
dualmente 
dualmente 
primeiro obj
Adotan
alonamento
delando um
s seria: 
O esca
s fases: 
M = B
Note q
ueá-lo ant
ocolo. Note
Como 
ueios e lib
N = R1
Este e
S = R1
Instituto F
Msc. Marcos
o sem blo
sta envolve
s Bi(x1) ,...,
entaremos
que gara
protocolo 
a: 
da transaç
os objetos 
a vez que
os objetos 
me deste p
eira fase 
bloqueado
liberados. 
bjeto da tra
ndo a 
os com a
ma execuç
L = B1(x) R
alonament
1(x) R1(x) B
que, em M
tes de W1
e ainda qu
último ex
berações): 
(x) W2(x) W
scaloname
(x) W1(x) W
M
Federal de Ed
Univ
Dis
s Vinicius Sad
oqueios e
er cada aç
 Bi(xk) e Li(
s nesta se
ante seriali
chama-se
ão deverá
que bloque
e uma tran
daí em dia
protocolo a
em que
os e uma
O ponto d
nsação é c
representa
s ações R
ção que s
R1(x) B2(y)
o abaixo, p
B2(y) R2(y)
M, a tran
1(x), o qu
e L é seria
xemplo, c
W1(x) W3(x
ento é seri
W2(x) W3(x
Governo 
Ministério da
ducação, Ciê
versidade Ab
ciplina: Banc
dala Barreto
Pagina
m um es
ção de lei
( x1 ,..., xk )
ção um e
zação, cu
 bloqueio
á bloquear
eou até ter
nsação lib
ante. 
advém do
os objeto
segunda f
do escalon
chamado d
ação de
R(X), W(X)
satisfazao
R2(y)W1(x
por sua ve
) L1(x) B2(x
sação T1 
e constitu
alizável, ma
considere 
x) 
alizável po
x) 
Federal 
a Educação
ncia e Tecno
berta do Bra
co de Dados 
 
a 25 
calonamen
itura ou at
) . 
exemplo de
uja correçã
em duas
cada obje
rminar; 
berar um o
fato de qu
os que a
fase em q
namento e
de ponto d
uma e
X), B(x) e L
o protocol
x) L1(x) B2(
ez, viola o p
x) L2(y) W2(
libera x 
i uma vio
as não F.
o seguint
or ser equiv
ologia do Par
sil 
II 
nto satisfa
tualização 
e um prot
ão é prov
s fases e 
eto antes d
objeto, não
ue, para ca
transação
ue todos o
em que se 
de bloqueio
execução 
L(X), um e
o de bloq
x) L2(y) W2
protocolo d
(x) L2(x) B1
após R1(
lação da 
te escalon
valente a 
ra – IFPA 
azendo a 
Oi( x1 ,...
ocolo bas
vada na s
é definid
de acessá
o mais po
ada transa
o precisa 
os objetos
dá a liber
o da transa
através 
escalonam
queio em 
2(x) L2(x) 
de bloquei
1(x) W1(x) 
(x), voltand
condição 
namento 
este 
, xk ) 
eado 
eção 
o da 
á-lo e 
oderá 
ação, 
são 
s são 
ração 
ação. 
de 
mento 
duas 
o em 
L1(x) 
do à 
2 do 
(sem