1

CONTROLE DE CONCORRÊNCIA

• Exigência de consistência de transações que executem isoladamente.

• A execução simultânea de transações, pode ocasionar problemas mesmo que a exigência anterior seja mantida caso não exista controle de concorrência. Estes problemas são denominados Anomalias de Sincronismo.

2

Anomalias de Sincronismo

Perda de Consistência. Acesso a dados inconsistentes. Perda de atualizações. Exemplos:Considere os seguintes esquemas.

CURSOS [ Código, Nome, NumMatr ]TURMAS [Código, Matricula]

3

Critérios de Consistência

C1 - O código de cada curso é único.

C2 -Todo o código existente em Turmas deve estar presente em Cursos.

C3 -O atributo NumMatr presente em Turmas indica o número de alunos matriculados em cada curso,

4

Transações

Matricule (m,c)Início_Trans

M1 LER t de Cursos onde Código = c;Se existe t então

M2 GRAVE a tupla (m,c) em Turmas;

NumMatr = NumMatr + 1; M3 GRAVE t em Cursos;

Fim seFim_Trans.

5

TransaçõesCancele (c) Início_TransC1 Delete t de Cursos onde Código = c;C2 Delete as tuplas de Turmas onde Código= c;

Fim_Trans.

Liste (m) Início_TransL1 LER as tuplas de Turmas onde Matricula= m;

Liste tuplas lidas;L2 LER as tuplas de Cursos onde o código seja igual aos

códigos lidos anteriormente ; Liste tuplas;

Fim_Trans.

OBS: As transações preservam consistência de forma isolada ou com mecanismos de controle.

6

Exemplos

Considere a seguinte seqüência de operações: M11 M21 M31 L1 L2 C1 C2 M12 M22 M32

Esta seqüência determina uma execução serial.EXEMPLO 1:Supondo a existência inicial de um determinado curso e a seguinte execução de comandos:

M1 C1 C2 M2 M3

Nota-se que execução viola o 2o critério de consistência caso o cursoCancelado seja o mesmo que o matriculado.

7

Exemplos

EXEMPLO 2:

Suponha que na relação Turmas exista um certo aluno matriculado em uma determinada disciplina. Considere uma execução concorrente a seguir:

L1 C1 C2 L2

A transação Liste é inconsistente caso a transação Cancele exclua o curso listado

8

EXEMPLO 3:Considere que um determinado curso esteja cadastrado na relação Curso. Suponha a execução concorrente que segue:

M11 M12 M22 M32 M21 M31

Esta execução causa uma inconsistência no BD, pois como o valor lido pelas 2 transações é o mesmo a ação do comando M31 sobrepõe com o mesmo valor incrementado o atributo NumMatr produzido pela transação 2.

9

Escalonadores

Notação:READ(Q) Lê o conteúdo do item Q para a

variável q do programa.WRITE(Q) Grava o valor de q no item Q.

10

SeriaisConsidere as seguintes transações e as possíveis execuções seqüenciais :T0 : Read (A) T1 : Read (A)

A: A-50 x: A * 0.1 Write (A) A: A – x Read (B) Write (A) B: B + 50 Read (B) Write (B) B: B +x Write (B)

Valores A B

Iniciais 1000 2000

T0 T1 855 2145

T1 T0 850 2150

11

Não-SeriaisT0 T1

Read (A) A: A-50

Read (A)x: A

* 0.1A: A

– x

Write (A) Read (B)

Write (A)Read (B) B: B + 50 Write (B)

B: B +x Write (B)

Valores A BIniciais 1000 2000T0 T1 950 2100

12

Não-Seriais T0 T1

Read (A) A: A-50Write (A)

Read (A)

x: A * 0.1

A: A – xWrite

(A) Read (B) B: B + 50 Write (B)

Read (B) B: B +x Write (B)

Valores A BIniciais 1000 2000T0 T1 855 2145

13

Conclusões: Seriais e Não-Seriais

• O número de escalonadores seriais válidos é n!, onde n é o número de transações a serem executadas.

• O número de escalonadores não-seriais válidos é possivelmente maior que n! .

• Nem sempre um escalonador não serial, concorrente, produz um resultado correto

14

Conclusões: Seriais e Não-Seriais

• Um resultado correto é obtido por escalonadores concorrentes sempre que o resultado obtido seja igual ao produzido por um escalonador serial.

• Quando o resultado de um par de operações é o mesmo ,independente da ordem em que são executadas, diz-se que elas são comutáveis.

• As operações relevantes nos escalonadores são as de leitura e gravação.

15

Escalonadores com conflito de Seriabilidade

Diz-se que duas operações são conflitantes se elas operam sobre o mesmo item de dados, sendo que no mínimo uma delas é uma gravação, e são emitidas por diferentes transações.

Esquematicamente, considerando a última conclusão (slide anterior), usaremos a seguinte notação :

• Ri(x) - para operação de leitura do item x realizada pela transação i.

• Wi(x) - para operação de gravação do item x realizada pela transação i.

16

Escalonadores com Seriabilidade de conflito

Se Ii precede Ij e são instruções diferentes e não

conflitantes então pode-se trocar a ordem entre elas gerando-se assim um novo escalonador que diferem apenas na ordem destas operações.Exemplo :

E5 : Ri(x), Rj(x),Wj(y), Wi(x) E6 : Rj(x),Wj(y), Ri(x), Wi(x)

Escalonadores serializáveis em conflito

Dois escalonadores são equivalentes, se para cada par de operações conflitantes Ii e Ij tal que Ii precede Ij em En

então no escalonador Em esta precedência será mantida.

17

Contra Exemplo

Dois escalonadores podem produzir o mesmo resultado e não serem equivalentes em conflito.

P. ex: T0 : READ(A ) T1 : READ(B )A: A-50 B: B-10WRITE (A) WRITE (B)READ(B) READ(A)

B: B +50 A: A +10

WRITE (B) WRITE (A)

E8 : R0(A) W0(A) R1(B) W1(B) R0(B) W0(B) R1(A) W1(A)

E9 : R0(A) W0(A) R0(B) W0(B) R1(B) W1(B) R1(A) W1(A)

Valores INICIAIS : A = 1000 B= 2000FINAIS : A = 960 B= 2040

18

Escalonadores Equivalentes em Visão

Dois escalonadores E e E’, possuindo as mesmas transações, são ditos equivalentes em visão se obedecerem as seguintes condições:

1.Para cada item Q, se a transação Ti lê o valor produzido por Tj no escalonador E então no escalonador E’ precisa também ocorrer o mesmo;

2.Para cada item Q, se a transação Ti lê o valor inicial de Q no escalonador E então no escalonador E’ precisa também ler o valor inicial de Q;

3.Para cada item Q, a operação de gravação final de cada item deve ser praticado pela mesma transação em ambos escalonadores.

Exemplos : Serial(S1) e Serial(S2) não equivalentes. Serial(S1) e E4 são equivalentes

Um escalonador E é serializável em visão se ele for equivalente em visão a um escalonador serial

19

Exemplos:

EX: E9: R2(Q) W3(Q) W2(Q) W4(Q)

E9 Serial <T2,T3,T4>Todo escalonador serializável em conflito é serializável em visão mas a recíproca não é verdadeira.

Ex: E9

OBS: as gravações executadas por T3 e T4 no escalonador E9 são denominadas cegas pois não realizam nenhuma leitura anterior. Estas aparecem em escalonadores serializáveis em visão que não sejam serializáveis em conflito

20

Verificando a seriabilidade de conflito

Seja E um escalonador. Construímos um grafo de precedência de E. Este grafo consiste em um par G= (V,A), onde v é o conjunto de vértices e A um conjunto de arestas.

Vértices representam transações presentes em EArestas consistem precedências onde ocorre um das três situações:

Ti executa W(Q) antes que Tj execute R(Q)Ti executa R(Q) antes que Tj execute W(Q)Ti executa W(Q) antes que Tj execute W(Q)Se a aresta Ti Tj existe no grafo de precedência ,isto implica que em qualquer escalonador serializável E’ equivalente a E, Ti precisa aparecer antes de Tj.

21

Exemplos

T0 T1

T1 T0

T0 T1

Ti

TJ TK

Tn

Ordens parciais obtidas do grafo de precedência:

Ti Tj Tk Tn

Ti Tk Tj Tn

22

Verificando a seriabilidade em visões

Considere o escalonador E9 : R2(Q) W3(Q) W2(Q) W4(Q)

T2 T3

T4 Não serializável em conflito mas, serializável em visão ao escalonador

<T2,T3,T4>.

Isto ocorre porque aresta T3 T2 não deveria existir no grafo haja visto que os valores produzidos por T2 e T3 não são usados por outra transação e T4 produz o valor final. As instruções W(Q) produzidas por T2 e T3 são denominadas inúteis. Assim o esquema de grafo de conflito não serve para a verificação da seriabilidade em visão.

23

Protocolos Baseados em Bloqueio

Idéia Básica Quando um transação acessa um item de dados deve antes bloqueá-lo, caso este já esteja bloqueado por outra transação deve esperar até

que o item seja liberado Modos de Bloqueio

Compartilhado lock-s LS Exclusivo lock-x LX

24

Regras de Compatibilidade

1. Compartilhado Quando o item desejado não esta

bloqueado por nenhuma transação ou esta bloqueado em modo compartilhado.

2. ExclusivoSomente quando o item desejado não esta bloqueado

25

Transações Bem Formadas

Aquelas que sempre bloqueiam o item de dados em modo compartilhado antes de lê-lo e sempre bloqueiam em modo exclusivo antes de gravá-lo

Duas transações estão em conflito se elas desejam bloquear o mesmo item de dados em modos incompatíveis.

26

ExemplosT7: Lock-x (B)

Read (B)B: B-50Write (B)Unlock (B)Lock –x (A)Read (A)A: A + 50Write (A) Unlock (A)

T8: Lock-s (A)Read (A)Unlock (A)Lock-s (B) Read (B)Unlock (B)Display (A + B)

Seja E14:

LX7 (B) R7(B) W7 (B) UL7 (B) LS8 (A) R8 (A) UL8 (A) LS8 (B) R8 (B) UL8 (B) LX7 (A) R7 (A) W7 (A) UL7 (A)

Inconsistente T8 lê A e B produzindo como resultado 250

Valores Iniciais: A=100 B=200

27

ExemploT9: Lock-x (B)

Read (B)B: B-50Write (B)Lock–x (A)Read (A)A: A + 50Write (A) Unlock (B)Unlock (A)

T10: Lock-s (A)Read (A)Lock-s (B) Read (B)Display (A+B)Unlock (A)Unlock (B)

Seja E15: LX9 (B) R9(B) W9 (B) LS10 (A) R10 (A) LS10 (B) LX9 (A) .......

Impasse

28

Protocolo de Bloqueio Bifásico (2PL)

A execução concorrente de transações é correta se observada as seguintes regras:

1.Transações bem formadas2.Regras de compatibilidade de

bloqueio são obedecidas 3.Cada transação após liberar um

bloqueio não solicita um novo bloqueio

A condição 3 pode ser expressa dizendo que as transações são Bifasicamente Bloqueadas

29

Fases do ProtocoloTodas as transações devem obedecer as

seguintes fases:

Primeira Fase – Crescimento Durante a qual obtém seus bloqueios,mas

não libera bloqueio algum.

Segunda Fase – Retração Na qual os bloqueios são liberados mas

nenhum bloqueio pode ser requeridoEX: T9 e T10 são 2PL C-Ex: T7 e T8

30

Seriabilidade e Isolamento O 2PL garante a seriabilidade de transações

A propriedade de isolamento só é alcançada caso todos os bloqueios exclusivos sejam até mantidos até a confirmação (commit). Tal como o esquema abaixo:

Begin TransactionAquisição de bloqueios antes de ler ou gravar

CommitLibera bloqueios

OBS: A vulnerabilidade do 2PL a impasses continua

31

Tratamento de Impasses Situação Métodos

Algoritmo de Prevenção Algoritmo de Detecção e de Tratamento

PrevençãoPré- Declaração – bloquear todos os itens

Um item fica bloqueado por tempo excessivo Um item muito acessado pode causar

postergação indefinida

32

Detecção de Impasses Grafo Wait-for

T5 T6 T8 Sem impasse

T7

T5 T6 Com impasse

T7