Controle de Concorrência em Sistemas Distribuídos Aluno: Fabiano Costa Teixeira Disciplina: Sistemas Distribuídos Professor: Dr. Marcos José Santana

Controle de Concorrência em Sistemas Distribuídos

Aluno: Fabiano Costa Teixeira

Disciplina: Sistemas Distribuídos

Professor: Dr. Marcos José Santana

2Controle de Concorrência em Sistemas Distribuídos

Roteiro

IntroduçãoTransaçõesLocksControle Otimista de ConcorrênciaControle de Concorrência por

TimestampsConclusão


Introdução

Um servidor pode permitir acesso concorrenteProcessosThreads

Se o projeto não for bem feito, as ações dos clientes podem interferir umas nas outras

Essas interferências podem resultar em resultados incorretos dos objetos


Transações

Foram originadas nos SGBD’sPodem ser utilizadas em servidores

transacionais de ArquivosPropriedades ACID:

AtomicidadeConsistência IsolamentoDurabilidade


Transações

Uma maneira para garantir o isolamento é realizar as transações de forma serial

Essa solução é inaceitávelServidores compartilham recursos entre

diversos clientes Interatividade do sistema

Os servidores precisam maximizar a concorrência!!!!!


Transações: Lost Update

Transação T

x = b.getSaldo();

b.setSaldo(x * 1,1);

Transação U

x = b.getSaldo();


b

saldo = 200

x = b.getSaldo()x = b.getSaldo()b.setSaldo(x * 1,1);


x = 0 x = 0x = 200 x = 200

220

Perdido

240


Transações: Retrievals Problem

Transação V

a.retira(100);

b.deposita(100);

Transação W

total = a.getSaldo();

total = total + b.getSaldo();

a

saldo = 200100

b

saldo = 200300

a.retira(100);

total = a.getSaldo();total = total + b.getSaldo();

b.deposita(100);

total = 0total = 100total = 300total = 300


Transações: Equivalência Serial

Quando as transações são executadas serialmente não há problemas

Se transações concorrentes tiverem suas operações intercaladas de forma que o resultado final seja o mesmo que alguma das combinações seriais, essa intercalação é SERIALMENTE EQUIVALENTE!

Protocolos de controle de concorrência se baseiam nesse princípio



Um mesmo objeto pode ser requisitado por operações de transações diferentes

É dito que um par de operações é conflitante quando o resultado depende da ordem que elas aparecem na execução

Operações de transações diferentes

Conflito?

Read Read Não

Read Write Sim

Write Read Sim



É possível definir a ordem das operações conflitantes

“Para que duas transações possuam equivalência serial, é necessário e suficiente que todos os pares de operações conflitantes sejam

executados na mesma ordem”

Transação T Transação U

x = read(i);

write(i, 10);

write(j, 20);

y = read(j);

write(j, 30);

z = read(i);

Não há equivalência serial:T acessa i antes de UU acessa j antes de T


Locks

Um mecanismo que faz com que duas transações concorrentes sejam serialmente equivalentes

Quando ocorre um conflito de operações, o objeto acessado é “bloqueado”

Outro cliente deve aguardar até que o objeto seja “liberado” para poder acessá-lo


Locks Simplesmente bloquear um objeto e liberá-lo

logo após o uso não garante a equivalência serial


x = b.read(); (lock b)y = b.read(); (wait b)

b.write(x-10);

y = b.read(); (lock b)

y = y + c.read(); (lock c)

c.write(x+10); x = c.read(); (lock c)

unlock(b)

unlock(c)

unlock (b)

unlock (c)


Locks: Two Phase Locking

Garante a equivalência serialDepois que a transação libera um lock

ela não pode adquirir mais nenhumA transação é dividida em duas fases:

Crescimento: Os locks são adquiridosEncolhimento: Os locks são liberados

O encolhimento ocorre após a execução de um commit ou rollback


Locks: Compatibilidade de Operações

Se duas transações acessam o mesmo objeto somente para leitura não há riscos de inconsistência

Um mecanismo simples que observa uma operação read da mesma maneira que uma operação write reduz a concorrência mais que o necessário



É interessante que seja possível ter diversas transações lendo um objeto ou somente uma alterando-o

Mecanismo referenciado como “many reades / single writer”

São utilizados dois tipos de locks:Read LocksWrite Locks



Lock existente

Lock solicitado

read write

none OK OK

read OK wait

write wait wait


Locks: Promoção

Uma mesma transação pode efetuar operações de leitura e escrita em um mesmo objeto

Quando realizada uma leitura, um read lock é atribuído ao objeto

Se for solicitada uma leitura é feita uma promoção para write lock

Um write lock não pode virar um read lock


Locks: Deadlocks

O uso de locks pode levar a uma situação de deadlock


Operações Locks Operações Locks

a.deposito(100);

b.saque(100);

write lock a

Aguarda U

b.deposito(100);

a.saque(100);

write lock b

Aguarda T


Locks: Deadlocks

É possível representar as “esperas” através de um grafo dirigido

Os vértices representam as transaçõesAs arestas representam a espera de

uma transação Tx por uma transação Ty

Um circuito encontrado no grafo indica a existência de um DeadLock

T U

espera por

espera por


Locks: Deadlocks

Uma vez que um Deadlock é detectado, para resolvê-lo é preciso abortar uma das transações envolvidas

É necessário decidir qa respeito de qual transação abortar:Número de ciclos dos quais ela faz parteTimeout


Controle Otimista de Concorrência

Parte do princípio de que a possibilidade de haver duas transações em conflito é baixa

A transação prossegue sem solicitar locks

Escritas realizadas em cópias tentativasLeituras realizadas diretamente nos

objetos


Controle Otimista de Concorrência

Quando é solicitado o encerramento da transação é verificado se há conflitos

Se houver conflito uma transação é abortada e deve ser reiniciada

Cada transação possui três fases:TrabalhoValidaçãoAtualização


Controle Otimista: Validação de Transações

São mantidos os grupos de objetos lidos e objetos alterados por uma transação

Na validação é verificada a existência de conflitos entre as operações das transações concorrentes

Tv Ti Regra

write

read

write

read

write

write

1

2

3

Ti não pode ler objetos escritos por Tv

Tv não pode ler objetos escritos por Ti

Ti não pode escrever objetos escritos por Tv e

Tv não pode escrever objetos escritos por Ti


Controle Otimista: Validação de Transações

Cada transação que entra na fase de validação recebe, sequencialmente, um número identificador

Duas formas de validaçãoBackward ValidationForward Validation


Controle Otimista: Backward Validation

A transação validada é comparada com aquelas que foram iniciadas antes do começo de sua fase de validação e que já foram efetivadas

Transação Tv é compara-da com as transações T2

e T3.

Quais serão as transa-ções a serem compara-das?


Controle Otimista: Backward Validation

É necessário realizar a validação apenas da regra 2

Se a regra não for obedecida é necessário abortar a transação sob validação

É necessário manter o conjunto de objetos escritos de uma transação até que todas aquelas que possuem sobreposição a ela sejam validadas


Controle Otimista: Forward Validation

A transação validada é comparada com aquelas em atividade

É necessário realizar a validação apenas da regra 1

Transações read-only sempre passam pela validação

Transações em conflito estão ativas, flexibilizando a escolha de “qual abortar”


Controle por Timestamp

Toda transação, no momento de sua criação, recebe um timestamp

O timestamp define a posição da transação

Cada transação que aplica uma operação de write possui uma versão “tentativa” do objeto



As versões tentativas devem ser efetivadas na ordem dos timestamps das transações

T1 T2 T3 T4

OBJ

OBJ OBJ OBJ OBJ

OBJ

OBJ Tentativa

Efetiva



A versão efetiva do objeto possui um write timeStamp

Cada versão tentativa possui:write timestampConjunto de read Timestamp



Operações write:Mantidas na versão tentativa até o commitExecutada no momento do closeTransactionCliente não precisa aguardar

Operações read:Direcionadas para a versão com maior

Timestamp que seja <= que a transaçãoPrecisa aguardar pelas transações

anteriores



Não ocorre DeadlockRegra para a escrita d um objeto D por

uma transação Tc:

if (Tc >= Maior read timestamp de D && Tc > write timestamp da versão efetiva Executa o write na versão tentativa Tcelse Aborta a transação Tc


Controle por Timestamp: Exemplo de Escrita

OBJ T2 OBJ T3

Exemplo 1:

OBJ T1 OBJ T2

Exemplo 2:

OBJ T3

OBJ T1 OBJ T4

Exemplo 3:

OBJ T4OBJ T3

OBJ T4

Exemplo 4:

OBJ T3

OBJ T3

OBJ

OBJ Tentativa

Efetiva


Controle por Timestamp: Leitura

A leitura de um objeto deve ser realizada seguindo os Timestamps. Sendo a regra:

if (Tc >= Maior write timestamp da versão efetiva de D){ let Dselected = D com maior write timestamp <= Tc

if (Dselected é uma versão efetiva) Executa read sobre a versão Dselected

else Aguarda até que a transação que gerou Dselected seja efetivada ou abortada e reaplica a regra de leitura}else Aborta a transação Tc


Controle por Timestamp: Leitura

T2

Exemplo 1:

T2 T4

Exemplo 2:

T1

Exemplo 3:

T2

T4

Exemplo 4:

T3Seleciona

T3

Seleciona

T3Seleciona

Efetua leitura!

Efetua leitura!

Aguarda commit ou rollback!!

T3

OBJ

OBJ Tentativa

Efetiva


Controle por TimeStamps

O commit deve ser feito na ordem dos timestamps

Se for necessário aguardar por transações anteriores o cliente não precisa aguardar

Necessidade de armazenar as cópias tentativas pertencentes a transações efetivas em meios persistentes


Multiversion Timestamp

Para um mesmo objeto é mantida uma lista das versões efetivas

Semelhante a um históricoOperações de read que chegam

“atrasadas” não precisam ser abortadasDa mesma forma que no sistema básico

de timestamps, as operações de escrita são realizadas em versões tentativas



Toda versão efetiva possui dois Timestamps:Da transação que a gravouMaior Timestamp de leitura

Operações de leitura são sempre aceitas, mas podem precisar aguardar

Cuidado com as transações de escrita que afetariam uma leitura já realizada



Operações de escrita de transações diferentes não são conflitantes

Regra de escrita:

if (read timestamp of DmaxEarlier <= Tc{ executa o write na versão tentativa com w-ts Tc

}else Aborta a transação Tc


T3


r,w

r,w Tentativa

Efetiva

?,T1 ? ,T3 ?,T2

read

write

T3,T2

T5

read

T5 ,T3

T4

write



Maior uso de espaço em discoTransações read-only sempre são

realizadasRazoável nível de concorrênciaInexistência de Deadlocks


Conclusão

Diversos mecanismos para o controle de concorrência

Diferença entre o grau de concorrênciaSerialização estática ou dinâmicaTransações somente leituraDeadlocksDecisão de qual transação abortar



Referência Bibliográfica

Coulouris, G., Dollimore, J., Kindberg, T.:

“Distributed Systems: Concepts and Design”

Addison-Wesley, páginas.: 465-510, 2001

Documents

Controle de Concorrência em Sistemas Distribuídos Aluno: Fabiano Costa Teixeira Disciplina: Sistemas Distribuídos Professor: Dr. Marcos José Santana