Gestão de transacções
noções básicas
 modelo simples
 modelo elaborado
 recuperação
 marcas temporais

Gabriel David
FEUP - Rua dos Bragas, 4099 Porto Codex - PORTUGAL
Tel. 351-2-2041842 - Fax: 351-2-319280
Email: [email protected]
URL: http://www.fe.up.pt
1
Execução de programas
Execução série - um programa de cada vez
versus
Execução concorrente - vários programas partilham o CPU
Problema: garantir que os vários programas não
interferem de forma inesperada
Concorrência - 2
Programas e BD

Transacção



uma execução de um programa
podem coexistir várias transacções do mesmo programa
Interacção transacção/BD



transacção lê dados da BD para o seu espaço de trabalho
cálculos feitos no espaço de trabalho completamente isolados
transacção escreve resultados do espaço de trabalho para a BD
P1
P2
T1
T2
T3
BD
Concorrência - 3
Tipos de acesso

Programas executados em série


modelo na cabeça do programador
Acesso simultâneo para leitura e escrita


sistema de reservas - Programa: READ A; A=A+1; WRITE A;
Problema da actualização falhada: dois acessos diferentes reservarem o
mesmo lugar
A(BD) 5
T1:
READ A
T2:
5
A(T2)
5
5
6
6
A=A+1
READ A
A(T1)

5
WRITE A
A=A+1
WRITE A
5
6
6
6
5
5
6
6
6
Acesso simultâneo só para leitura


recenseamento
sem interferência
Concorrência - 4
Propriedades das transacções

SGBD deve manter as propriedades ACID





atomicidade - as operações da transacção efectivam-se na BD
ou todas ou nenhuma
consistência - transacção sozinha preserva consistência da BD
isolamento - as transacções apesar de concorrentes não
interferem; para cada par Tl - Tk o efeito final é o de executar Tl
e depois Tk, ou Tk e depois Tl
durabilidade - efeitos de uma transacção com sucesso
persistem na BD mesmo em caso de avarias no sistema
consistência


primariamente um problema do programador da transacção
SGBD pode verificar automaticamente regras de integridade
Concorrência - 5
Atomicidade


Importante também para manter a consistência
Operação Transferência bancária
T(valor, conta_origem, conta_destino)
1 READ conta_origem
2 conta_origem= conta_origem - valor
3 WRITE conta_origem
4 READ conta_ destino
5 conta_ destino = conta_ destino + valor
6 WRITE conta_ destino
 interrupção em 4 deixa BD inconsistente

Razões para quebra de atomicidade



avaria de hardware
erro de software
bloqueio em competição por recursos
Concorrência - 6
Bloqueios

Isolamento entre transacções




Gestor de bloqueios




dividir a BD em itens, recursos necessários para as transacções
item - unidade de dados, desde a BD à tabela, linha ou campo
controlo de acesso através do bloqueio de itens
regista, para cada item I, quais as transacções que estão a ler ou
escrever alguma parte de I
controla o acesso de uma segunda transacção, de acordo com
uma determinada política
granularidade dos itens condiciona peso da gestão de bloqueios;
transacção típica deve bloquear poucos itens
Bloqueio (lock)


é um privilégio de acesso a um item
primitiva de sincronização
Concorrência - 7
Gestão da concorrência

Controlar item com bloqueio




pedir bloqueio de A antes da leitura
outras transacções que tentem bloquear A esperam
desbloquear A depois da escrita
Reserva de lugar

Programa: LOCK A; READ A; A=A+1;
WRITE A; UNLOCK A;
A(BD) 5
5
5
5
T1:
READ A
A=A+1
WRITE A UNLOCK A
LOCK A
6
T2:
6
LOCK A
A(T1)
5
6
A(T2)
6
6
6 7
…
6
6 7

garante isolamento
Concorrência - 8
Problemas

Bloqueio activo (livelock)



T1 e T2 pedem bloqueio de A; T1 obtém; T3 pede bloqueio de A;
quando T1 desbloqueia, T3 é servido e T2 fica à espera…
hipótese de resolução: servir sempre o pedido mais antigo
Encravamento (deadlock)
T1: LOCK A; LOCK B; UNLOCK A; UNLOCK B;
T2: LOCK B; LOCK A; UNLOCK B; UNLOCK A;
 T1 bloqueia A e T2 bloqueia B; ambos ficam parados à espera
que o outro desbloqueie
 hipótese 1: obrigar a transacção a pedir todos os bloqueios de
uma vez e o gestor concede todos ou nenhum
 hipótese 2: atribuir uma ordem aos itens e os pedidos de
bloqueio serem feitos por essa ordem
 hipótese 3: não prevenir; SGBD verifica se há encravamento e
aborta uma das transacções
Concorrência - 9
Escalonamento

Escalonamento de um conjunto de transacções



ordem de execução dos passos elementares das várias transacções
T1: READ A; A=A-10; WRITE A; READ B; B=B+10; WRITE B;
T2: READ B; B=B-20; WRITE B; READ C; C=C+20; WRITE C;
T1
READ A
A=A-10
WRITE A
READ B
B=B+10
WRITE B
T2
T2
READ B
T1
READ A
A=A-10
A=A-10
WRITE A
WRITE A
B=B-20
WRITE B
READ B
READ B
WRITE B
READ C
B=B+10
B=B+10
READ C
C=C+20
WRITE B
WRITE C
 (B=B-10)
T2
READ B
B=B-20
READ B
B=B-20
WRITE B
READ C
C=C+20
WRITE C
 (B=B-10)
T1
READ A
WRITE B
C=C+20
WRITE C
 (B=B+10)
Concorrência - 10
Seriabilidade

Escalonamento série (caso )


Escalonamento serializável (caso )


efeito equivalente a um qualquer escalonamento série
Escalonamento não serializável (caso )


todos os passos de cada transacção executados consecutivamente
a evitar (!), mas sem olhar para expressões calculadas, apenas
para a sequência de operações e bloqueios
Escalonador





parte do SGBD que arbitra conflitos entre transacções
recebe informação do gestor de bloqueios
evita bloqueio activo, encravamento e não seriabilidade
fica facilitado se as transacções seguirem protocolos adequados
escalonamento legal se não violar bloqueios
Concorrência - 11
Modelo simples

Assume-se que bloquear implica ler e desbloquear
escrever


modelo simples é não fatal: pode impedir escalonamentos
serializáveis, mas não aceita não serializáveis
Teste de seriabilidade de um escalonamento




criar um grafo dirigido cujos nós são as transacções
para cada passo Tk: UNLOCK Am, se existir a seguir um passo
Tl: LOCK Am, desenhar um arco de Tk para Tl.
escalonamento serializável se não houver ciclos no grafo
as setas indicam a ordem de um escalonamento série
equivalente (ordenação topológica)
Concorrência - 12
Teste de seriabilidade

Não serializável

T2 deve correr antes de T1 e vice-versa
T1
LOCK A
T2
T3
LOCK B
LOCK C
UNLOCK B
T2
T1
LOCK B
UNLOCK A
LOCK A
UNLOCK C
UNLOCK A
T3
LOCK A
LOCK C
UNLOCK B
UNLOCK C
UNLOCK A
Concorrência - 13
Bloqueio em duas fases

Problema: garantir a seriabilidade





combinação escalonador + protocolo
protocolo de bloqueio em duas fases: todos os bloqueios (1ª
fase) são pedidos antes de todos os desbloqueamentos (2ª fase)
trabalho do escalonador: basta conceder o bloqueio se estiver
disponível e suspender ou abortar a transacção caso não esteja,
isto é, só se verifica a legalidade da transacção
garante-se que qualquer escalonamento legal é serializável
um escalonamento série correspondente é o dado pela ordem
dos pontos de bloqueio das várias transacções
• ponto de bloqueio é o instante em que ocorre o último bloqueio;
considera-se que todo o processamento ocorre nesse instante,
antes de começar a desbloquear

verificar coerência com grafo de seriabilidade
• T2 (pág anterior) não respeita bloqueio em duas fases
Concorrência - 14
Contra-exemplo

T1 não é de duas fases   não serializável



T1: LOCK A; UNLOCK A; LOCK B; UNLOCK B
T2: LOCK A; LOCK B; UNLOCK A; UNLOCK B
T1
T2
LOCK A
…
UNLOCK A
T1
LOCK A
LOCK B
UNLOCK A
UNLOCK B
T2
LOCK B
UNLOCK B

conclusão: bloqueio em duas fases é óptimo
Concorrência - 15