CONTROLE DISTRIBUÍDO
DE CONCORRÊNCIA
Dennis Williams e Wanderson de Lima
Roteiro










Introdução
Três problemas de concorrência
Teoria da Serializabilidade
Taxonomia dos mecanismos de controle de concorrência
Bloqueios
Algoritmos baseados em TO
Algoritmos otimistas
Gerenciamento de impasses
Controle de concorrência Relaxado
Conclusão
Introdução



Os SGBDs permitem que muitas transações tenham
acesso ao mesmo banco de dados ao mesmo tempo
Através da concorrência, é possível obter uma
melhor vazão do SGBD
É necessário um mecanismo para garantir o
isolamento das transações e a consistência do BD
Três problemas de concorrência

Atualização perdida
T1
T2
Read(X)
X=X-M
Tempo
Read(X)
X=X+M
Write(X)
Write(X)
O elemento X tem um
valor incorreto porque
sua atualização por T1
se perdeu
Três problemas de concorrência

Leitura Suja
T1
T2
Read(X)
Tempo
X=X-M
Write(X)
Read(X)
X=X+M
Write(X)
Rollback
A transação T1 falha e
deve voltar o valor de X
ao seu valor antigo,
porém T2 já leu o valor
incorreto de X
Três problemas de concorrência

Análise inconsistente
T1
T2
Soma=0
Read(A)
Soma=Soma+A
Read(X)
Tempo
X=X-N
Write(X)
Read(X)
Soma=Soma+X
Read(Y)
Soma=Soma+Y
Read(Y)
Y=Y+N
Write(Y)
T1 lê X depois de
subtrair de N e lê Y
depois de somar N,
portanto efetuou uma
análise inconsistente
Teoria da Serializabilidade

Um escalonamento S de n transações T1,T2,..,TN é
um ordenamento para as operações das transações
sujeito a restrição de que, para cada transação Ti
que participe em S, as operações de Ti em S devem
aparecer na mesma ordem que ocorrem em em Ti.
 As
operações de outras transações Tj podem se
intercalar com as operações de Ti em S

Se, em um escalonamento S, as operações de todas
as transações não estão intercaladas, então o
escalonamento é serial
Teoria da Serializabilidade


Considere as três transações a seguir:
T1:
T2:
T3:
Read(X)
Write(X)
Read(X)
Write(X)
Write(Y)
Read(Y)
Commit
Read(Z)
Read(Z)
Commit
Commit
O escalonamento S = {W2(X), W2(Y), R2(Z), C2,
R1(X), W1(X), C1, R3(X), R3(Y), R3(Z), C3} é serial
Teoria da Serializabilidade


Duas operações Oij(X) e Okl(X) estão em conflito se
tem acesso a mesma entidade de banco de dados
X e se uma das operações é uma operação de
gravação
Dois escalonamentos S1 e S2 definidos sobre o
mesmo conjunto de transações são ditos
equivalentes em conflito se, para cada par de
operações conflitantes Oij(X) e Okl(X) (i≠k) sempre
que Oij <1 Okl então Oij <2 Okl
Teoria da Serializabilidade

Considere os dois escalonamentos a seguir:

S = {W2(X), W2(Y), R2(Z), C2, R1(X), W1(X), C1, R3(X), R3(Y), R3(Z), C3}

S’ = {W2(X), R1(X), W1(X), C1, R3(X), W2(Y), R3(Y), R2(Z), C2, R3(Z), C3}
S
e S’ são equivalentes em conflito
Teoria da Serializabilidade


Um escalonamento é serializável se e somente se
ele é equivalente de conflitos com um
escalonamento serial
A principal função de um controle de concorrência é
gerar um escalonamento serializável para a
execução de transações pendentes
Teoria da Serializabilidade
O
escalonamento da execução da transação em cada
site é chamando escalonamento local
 Em BDD não replicados, se cada escalonamento local
for serializável, sua união (chamada escalonamento
global) é serializável, desde que as ordens de
serialização local sejam idênticas
 Se o BDD for replicado é possível que os
escalonamentos locais sejam serializáveis, mas a
consistência mútua do BD pode estar comprometida
Teoria da Serializabilidade

Considere dois sites e um item de dado (X) que é
duplicado em ambos os sites. Além disso, considere as
transações a seguir:
T1:
Read(X)
X=X+5
Write(X)
Commit


T2:
Read(X)
X = X * 10
Write(X)
Commit
S1 = {R1(X), W1(X), C1, R2(X), W2(X), C2}
S2 = {R2(X), W2(X), C2, R1(X), W1(X), C1}
Os dois escalonamentos são
seriais. Se X=1, então S1 gera
como saída 60 e S2 gera como
saída 15 e a consistência mútua
dos dois BDs é violada
Teoria da Serializabilidade

Os escalonamentos que podem manter a
consistência mútua são chamados serializáveis de
cópia única e atendem às seguintes condições:
 Cada
escalonamento local deve ser serializável
 Duas operações conflitantes devem estar na mesma
ordem relativa em todos os escalonamentos locais em
que elas aparecem juntas
Taxonomia dos mecanismos de controle de
concorrência
Taxonomia dos mecanismos de controle de
concorrência




Algoritmos pessimistas sincronizam a execução
concorrente mais cedo em seu ciclo de execução
A visão pessimista é a de que muitas transações
entrarão em conflito entre si
Algoritmos otimistas atrasam a sincronização das
transações até seu término
A visão otimista é a de que não haverá um número
muito de transações que entram em conflito entre si
Bloqueios

A ideia de bloqueio é que quando uma transação
necessita de uma garantia que um objeto no qual
está interessada não mudará de algum modo
enquanto a transação estiver ativa, então a
transação adquire um bloqueio sobre o objeto
Bloqueios

Bloqueio de modo múltiplo
 Tipos
de bloqueio
 Bloqueio
de leitura(rl – read lock)
 Bloqueio de gravação(wl – write lock)

Operações
 read_lock(x)
 write_lock(x)
 unlock(x)
Bloqueios

Regras:
 Se
uma transação A mantiver um bloqueio de
gravação sobre uma unidade de bloqueio X, então
uma solicitação de bloqueio de uma transação distinta
B sobre X será negada
 Se uma transação A mantiver um bloqueio de leitura
sobre uma unidade de bloqueio X, então:
 Uma
solicitação de uma transação distinta B de bloqueio de
gravação sobre X será negada
 Uma solicitação de uma transação distinta B de bloqueio de
leitura sobre X será concedida
Bloqueios

As regras podem ser resumidas por meio de uma
matriz de compatibilidade de tipos de bloqueio
 Dois
modos de bloqueios são compatíveis se duas
transações que acessam o mesmo item de dados
podem obter esses bloqueios sobre esse item de dados
ao mesmo tempo
RLi(X)
WLi(X)
RLi(X)
COMPATÍVEL
NÃO COMPATÍVEL
WLi(X)
NÃO COMPATÍVEL
NÃO COMPATÍVEL
Bloqueios

Protocolo de acesso a dados
 Uma
transação que deseja ler um item de bloqueio X
tem de adquirir um bloqueio de leitura sobre X
 Uma transação que deseja gravar um item de bloqueio
X deve adquirir um bloqueio de gravação sobre X
Bloqueios


O SGBD deve se encarregar de gerenciar os
bloqueios. Assim, o usuário não precisa especificar
quando e como os dados devem ser bloqueados
Em sistemas baseados em bloqueio, o escalonador
é um gerenciador de bloqueio e ele se comunica
com o gerenciador de transação para estabelecer
ou não o bloqueio e passar a operação ao
processador de dados
Bloqueios

Considere as duas transações e um escalonamento
gerado pelo bloqueio descrito anteriormente:
T1:
Read(X)
X=X+1
Write(X)
Read(Y)
Y=Y-1
Write(Y)
Commit
T2:
Read(X)
X=X*2
Write(X)
Read(Y)
Y=Y+2
Write(Y)
Commit
Se X=50 e Y=20, então S gera
como saída X=102 e Y=38 se
T1 for executada antes de T2 e
X=101 e Y=39 se T2 for
executada antes de T1
S = {wl1(X), R1(X), W1(X), lr1(X), wl2(X), R2(X), W2(X), lr2(X), wl2(Y), R2(Y), W2(Y),
lr2(Y), C2, wl1(Y), R1(Y), W1(Y), lr1(Y), C1} S não é um escalonamento
serializável
Bloqueios


Como as operações de bloqueio e liberação não
são coordenadas, ele pode gerar escalonamentos
não serializáveis
Para garantir a serializabilidade é necessário usar
o bloqueio de duas fases ou 2PL(two-phase locking)
A
regra do bloqueio de duas fases é que nenhum
bloqueio deve ser adquirido pela transação após ela
liberar um de seus bloqueios
Bloqueios

As duas fases do 2PL são:
 Fase
de crescimento ou expansão
 Fase de contração ou encolhimento

Pode sofrer deadlock ou rollback em cascata
Bloqueios

Bloqueio de duas fases com rollback em cascata
Se T5 for abortada depois do
passo read(A) da transação T7
ocasiona o rollback em cascata
de T6 e T7
Bloqueios

Bloqueio de duas fases sofrendo deadlock
T3 já mantém um bloqueio de
gravação sobre B e T4 solicita
um bloqueio de leitura sobre B.
Analogamente, T4 já mantém um
um bloqueio de leitura sobre B e
T3 está solicitando um bloqueio
de gravação sobre A
Bloqueios

Bloqueio de duas fases estrito
 Libera
todos os bloqueios juntos quando a transação
termina(consolida ou aborta)
 Evita rollbacks em cascata, mas pode sofrer deadlock
Bloqueios

Refinamento no bloqueio de duas fases
 Conversão
de bloqueio de leitura para escrita
 Chamado
de promoção ou upgrade
 Só pode ocorrer durante a fase de crescimento
 Conversão
 Chamado
de bloqueio de escrita para leitura
de rebaixamento ou downgrade
 Só pode ocorrer durante a fase de contração
Bloqueios

Considere o escalonamento abaixo:
S
= {W1(X), R2(X), R3(Y), W1(Y)}
 S não é permitido pelo 2PL, pois T1 precisaria obter
um bloqueio de gravação sobre Y depois de liberar
seu bloqueio de gravação sobre X
 Portanto, o 2PL ele não permite obter todos os
escalonamentos que são serializáveis de conflito
Bloqueios

2PL centralizado
 Um
dos sites é designado como site primário é ele
responsável pelo armazenamento das tabelas de
bloqueio para todo o banco de dados, assim como
concessão de bloqueios as transações
 Os gerenciadores de transação dos outros sites se
comunicam com o gerenciamento de bloqueio
centralizado
 Gargalo em torno do site central, menor confiabilidade
devido a falha no site central
Bloqueios

2PL centralizado
Bloqueios
 2PL
de cópia primária
 Uma
das cópias(se houver várias) é escolhida como cópia
primária e essa cópia tem de ser bloqueada para
propósito de acessar essa unidade específica
 Por exemplo, se a unidade de bloqueio X é replicada nos
sites 1,2,3 e 1 é o site primário para X, a transação deve
obter bloqueio em 1 para poder acessar uma cópia de x
 Se x não tiver cópia, então a responsabilidade pelo
gerenciamento de bloqueio fica entre diversos sites
 Em relação ao 2PL centralizado, a única mudança é que os
locais de cópias primárias têm de ser definidas para cada
item de dados, antes de se enviar uma solicitação de
bloqueio ou desbloqueio ao gerenciador de bloqueio
Bloqueios
 2PL
A
distribuído
tarefa de gerenciamento de bloqueio é compartilhada
por todos os sites de uma rede
 Cada escalonador local é responsável pelas unidades de
bloqueio locais a esse site
 Em relação ao 2PL centralizado, a primeira mudança é que
as solicitações de bloqueios são solicitadas aos
gerenciadores de bloqueio de todos os sites participantes
 A segunda mudança é que as operações são repassadas
pelos gerenciadores de bloqueio participantes
Bloqueios

2PL distribuído
Algoritmos Baseados em TO



Algoritmos que tentam não manter a
serializabilidade baseada em exclusão mútua.
Atribuição de um timbre de hora (timestamp) ts(Ti)
a cada transação Ti.
Timbre de Hora:
 Identificador
de cada transação de forma exclusiva.
 Propriedades: exclusividade e caráter monotônico.
Algoritmos Baseados em TO

Atribuição de timbres de hora:
 Uso
de contadores globais.
 Uso de contadores locais.
 Identificação


por: <contador local, identificador de site>.
Clock do sistema.
Regra de TO:
 “Dada
duas operações conflitantes Oij e Okl, que
pertencem respectivamente às transações Ti e Tk, Oij só
será executada antes de Okl se e somente se ts(Ti) <
ts(Tk)”.
Algoritmos Baseados em TO



Um escalonador que impõe a regra de TO verifica
cada nova operação que chega.
Pode existir uma situação em que as operações
chegam ao escalonador numa sequência
desordenada.
Atribuir a cada item de dados dois timbres de
hora:
 Leitura
(rts(x))
 Gravação (wts(x))
Algoritmos Baseados em TO

Algoritmo Básico de TO:


O gerenciador de transações fica no aguardo
Se aparece uma operação do BD, verifica se:

Está no início de uma transação


É leitura/escrita


Envia a operação ao escalonador.
Se a operação foi rejeitada pelo escalonador:


Envia a operação e seu timbre de hora ao escalonador do site.
É abort/commit


Atribui um timbre de hora à transação.
Aborta a transação, reinicia e atribui um novo timbre de hora a ele.
Se a operação foi realizada com sucesso, informar ao usuário.
Algoritmos Baseados em TO

Algoritmo do Escalonador:
O escalonador fica no aguardo
 Armazena os valores de rts(x) e wts(x) iniciais.
 Se aparece uma operação, verifica se:


É leitura, verifica se ts(T) > rts(x):


É escrita, verifica se ts(T) > wts(x) e se ts(T) > wts(x):



Envia ao processador de dados.
Atribui rts(x) <= ts(T) e wts(x) <= ts(T).
É commit:


Envia ao processador de dados e atribui rts(x) <= ts(T).
Envia ao processador de dados.
É abort:



Identifica os itens de dados acessados por T.
Redefine os valores inicias de rts(x) e wts(x).
Envia ao processador de dados.
Algoritmos Baseados em TO




O escalonador garante que a transação pode ser
executada em outra oportunidade, caso tenha sido
rejeitada anteriormente.
Isso pode ocorrer muitas vezes.
Podem ocorrer em sites que estão desativados há
muito tempo.
Pode-se usar contadores sincronizados ou clocks
como alternativas.
Algoritmos Baseados em TO

Algoritmos de TO Conservadores:
 Usados
para reduzir essas probabilidades de
reinicializações.
 Atrasam as operações até que nenhuma das operações
do escalonador tenham um timbre de hora menor do
que o da transação.
 Abordagem:
 Cada
escalonador possui uma fila para cada gerenciador
de transações do sistema.
 O escalonador de um site i pode armazenar operações que
recebe do gerenciador de transações do site j.
Algoritmos Baseados em TO

Algoritmos de TO Conservadores:
Algoritmos Baseados em TO

Algoritmos de TO Conservadores:
 Esse
esquema reduz o número de reinicializações, mas
não garante a eliminação delas.
 Existem algoritmos extremamente conservadores que só
admitem uma operação no processador de dados se
em todas as filas de cada escalonador houvesse ao
menos uma operação.
Algoritmos Baseados em TO

Algoritmo de TO de várias versões:
 Cada
operação de gravação cria uma versão do item
de dados.
 Cada versão do item de dados é marcada pelo timbre
de hora da transação que a cria.
 Ele processa cada transação em um estado do banco
de dados.
Algoritmos Otimistas

Algoritmos pessimistas:

Algoritmos otimistas:
Algoritmos Otimistas



Nos algoritmos otimistas, os timbres de hora estão
associados apenas as transações e não a itens de
dados.
Os timbres de hora são atribuídos no início da
validação.
O algoritmo que será discutido foi proposto em
[Kung e Robinson, 1981] e estendido para SGBD's
distribuídos [Ceri e Owicki, 1982].
Algoritmos Otimistas

Cada transação é subdividida em várias subtransações.


Seja Tij uma subtransação de Ti executada no site j.
A validação local de Tij é feita de acordo com as regras a
seguir, que são mutuamente exclusivas:

Se todas as transações Tk tal que ts(Tk) < ts(Tij) tiverem
completado a fase de gravação antes de Tij iniciar sua fase
leitura:


Se houver qualquer transação Tk tal que ts(Tk) < ts(Tij) que
complete a fase de gravação antes de Tij concluir sua fase
leitura:


A validação terá sucesso porque estarão em ordem sequencial.
A validação terá sucesso se ws(Tk)^rs(Tij) = 0.
Se houver qualquer transação Tk tal que ts(Tk) < ts(Tij) que
complete a fase de leitura antes de Tij concluir sua fase leitura:

A validação terá sucesso se ws(Tk)^rs(Tij) = 0 e ws(Tk)^ws(Tij) = 0
Algoritmos Otimistas
Algoritmos Otimistas


É preciso assegurar a consistência global, para
garantir a regra de consistência mútua.
Não há um algoritmo otimista para isso.
A
transação é validada em termos globais se todas as
transações a precedem numa ordem terminam.
Algoritmos Otimistas

Vantagens:
 Quando
os conflitos são raros, o algoritmo otimista
comporta-se melhor que o algoritmo de bloqueio.
 Possibilitam alto nível de concorrência.

Desvantagens:
 Alto
custo de armazenamento.
 Uma transação pode falhar repetidamente na
validação.
Gerenciamento de Impasses



Ocorrem em situações de exclusão mútua ao acesso
de recursos compartilhados. E as transações podem
esperar em bloqueios.
É uma situação permanente.
WFG (Wait for Graph).
 Grafo
orientado que representa o relacionamento
entre as transações.
 Os nós desse grafo representam as relações
concorrentes do sistema.
Gerenciamento de Impasses

Formação de um WFG é mais complicada em
sistemas distribuídos.
 LWFG
e GWFG.
Gerenciamento de Impasses

Métodos para tratamento de Impasses:
 Prevenção
 Anulação
 Detecção
e Resolução de Impasses
Gerenciamento de Impasses

Prevenção:
O
gerenciador de transações verifica da possibilidade
de um impasse por uma transação.
 Para executar essa verificação é preciso que os itens
de dados sejam declarados previamente.
 Vantagens:
 Redução
de sobrecarga na avaliação de uma transação.
 Útil para sistemas que não desfazem processos.
 Desvantagens:
É
difícil saber com exatidão quais itens de dados serão
acessados por uma transação.
Gerenciamento de Impasses

Anulação:
 São
métodos mais adequados que a prevenção.
 Envolve técnicas de controle de concorrência ou exigem
que os escalonadores detectem a possibilidade do
impasse.
 A forma mais simples de resolver impasses: ordenar os
recursos e insistir que cada processo solicite acesso aos
recursos nessa ordem.
 Unidades de bloqueio são ordenadas.
 Pode haver ordenação local ou global.
Gerenciamento de Impasses

Anulação:
 Uma
abordagem é utilizar timbres de hora.
 Se a transação Ti é negada, então o gerenciador de
bloqueio não força Ti a esperar. Mas aplica um teste
de prevenção na transação que solicita (Ti) e na
transação que mantém bloqueio (Tj).
 Se
aprovada Ti, espera por Tj, senão será abortada.
Gerenciamento de Impasses

Detecção e Resolução de Impasses:
É
feita pela seleção de transações que serão
abortadas para romper os ciclos GWFG.
 É preciso avaliar alguns fatores:
A
quantidade de esforço investido na transação.
 O custo de abortar uma transação.
 A quantidade de esforço necessária para concluir a
execução da transação.
 O número de ciclos que contém a transação.
Gerenciamento de Impasses

Detecção e Resolução de Impasses:
 Detecção
Centralizada:
 Um
site é o responsável por detectar os impasses para
todo o sistema.
 Cada site envia seu LWFG ao detector de impasses, que
forma os GWFG e procura os ciclos nesse grafo.
 Comunicação x atraso.
 Detecção
 Os
Hierárquica:
sites são dispostos em níveis.
 Cada site envia seu LWFG ao nível superior, até o nó raiz.
Gerenciamento de Impasses

Detecção e Resolução de Impasses:
 Detecção
 Cada
Distribuída:
site será responsável por detectar os impasses. No
entanto, cada um deles comunica os WFG locais.
 Como cada site recebe os ciclos de impasses potenciais de
outros sites, as arestas responsáveis são adicionadas aos
WFG locais.
 As arestas representam que as transações locais estão
esperando por transações remotas e vice-versa.
 Ciclos envolvendo as arestas externas deverão ser
comunicadas aos outros detectores de impasses.
Gerenciamento de Impasses

Detecção e Resolução de Impasses:
Controle de Concorrência Relaxado

Algoritmos que não usam da serializabilidade como
critério de correção.
 Escalonamento
não serializável
 Transações Aninhadas
Controle de Concorrência Relaxado

Escalonamento não serializável:
 Utilizado
em casos onde o escalonamento é restrito
para certas aplicações.
 Baseia-se no uso da observação intuitiva.
 Atomicidade Semântica Relativa:
 Agrupar
transações em classes, baseado em suas etapas.
 As transações de mesma classe são compatíveis e podem
ser intercaladas.
Controle de Concorrência Relaxado

Transações Aninhadas:
 Fechadas:
O
controle de concorrência de transações aninhadas é muito
similar a da baseada em bloqueios.
 As transações aninhadas "relaxam" a durabilidade e o
isolamento.
 Abertas:
 Os
bloqueios mantidos por uma subtransação são liberados
logo que ela se consolida ou aborta.
Conclusão




O mecanismo distribuído do controle de
concorrência de um SGBD distribuído deve garantir
a consistência do banco.
Os algoritmos de controle de concorrência visam
tornar o SGBD distribuído em uma ferramenta
confiável em um ambiente não confiável.
No geral, os algoritmos de controle de concorrência
são de difícil implementação na prática.
O estudo de desempenho dos algoritmos estudados
é algo que carece de maiores aprofundamentos.