Equivalência Serial

Transações Concorrentes

Transações Inconsistentes

• Transações Inconsistentes podem existir, porque ocorrem operações conflitantes.

Equivalência Serial

• Dizemos que duas transações diferentes têm o mesmo efeito, quando as operações de leitura retornam os mesmos valores, e as variáveis compartilhadas têm, no final, o mesmo valor.

Equivalência Serial

• O uso de equivalência serial como um critério para execução concorrente correta de transações, impede a ocorrência de atualizações perdidas (“lost updates”) e recuperações inconsistentes (“inconsistent retrievals).

Operações Conflitantes

• Quando dizemos que duas operações estão em conflito, queremos dizer que seus efeitos combinados dependem da ordem em que elas são executadas.

Operações Conflitantes

• Considere duas operações read em uma transação T e write em uma transação U.

• A operação read acessa e lê o valor de uma variável e write altera esse valor.

• O efeito de uma operação se refere ao valor de uma variável configurada por uma operação de escrita e ao resultado retornado de uma operação de leitura.

Operações Conflitantes

• Para quaisquer duas transações é possível determinar a ordem dos pares de operações conflitantes, nas variáveis acessadas por ambas.

• A equivalência serial pode ser definida em termos de conflitos de operações.

Operações Conflitantes

• Pares de operações são conflitantes, se seus efeitos combinados depende da ordem na qual a operações no par são executados.

• Considerando um par de operações read e write, a operação read acessa o valor de uma variável e write muda seu valor.

Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems:

Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005

Read and write operation conflict rules

Operations of differenttransactions

Conflict Reason

read read No Because the effect of a pair of read operations

does not depend on the order in which they are

executed.

read write Yes Because the effect of a read and a write operationdepends on the order of their execution.

write write Yes Because the effect of a pair of write operations

depends on the order of their execution.

Operações Conflitantes

• O efeito de um operação refere-se ao valor de um objeto estabelecido por uma operação write e o resultado retornado por uma operação read.

• As regras de conflito para as operações read e write são dadas no slide que segue:

Operações Conflitantes

• Para quaisquer par de transações T e U, é possível determinar a ordem de pares de operações conflitantes sobre variáveis acessadas por ambas as transações.

• Um exemplo, a seguir.

Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems:

Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005

(Figura 10) Uma non-serially equivalent intercalação de operações de transações T e U

Transaction T: Transaction U:

x = read(i)write(i, 10)

y = read(j)write(j, 30)

write(j, 20)z = read (i)

Operações Conflitantes

• Equivalência serial pode ser definida em termos de conflitos de operações como segue:

“Para duas transações serem equivalentes serialmente, é necessário e suficiente que todos os pares de operações conflitantes das duas transações sejam executados na mesma ordem, sobre todos as variáveis que as transações acessam”.

Intercalação Não-Serialmente Equivalente de operações de Transações T e U

• Considere a figura em (Figura 10), com as transações T e U definidas.

• Então considere a intercalação de suas execuções como em (Figura 10).

• Note que cada acesso de transação às variáveis i e j é serializado com respeito a um outro.

Intercalação Não-Serialmente Equivalente de operações de Transações T e U

• Porque T faz todos os seus acessos a i antes de U fazer, e U faz todos os seus acessos a j antes de T fazer.

• Porém, a ordem não é serialmente equivalente, porque os pares de operações conflitantes não são feitos na mesma ordem em ambas as variáveis compartilhadas i e j.

Ordem Serialmente Equivalente de operações de Transações T e U

• Ordens serialmente equivalentes requerem uma das seguintes condições:

– T acessa i antes de U e T acessa j antes de U. ou

– U acessa i antes de T e U acessa j antes de T.

Outro Exemplo

• Sejam as transações T e U como no slide seguinte:

Operações em T e U

T Ui := 3x := 3i := 10----------------------------------- j := 5 (*) y := 5 j := 30 (*)-----------------------------------j := 20 (*)----------------------------------- z := 10-----------------------------------

T Ui := 3x := 3i := 10----------------------------------j := 20 (*)----------------------------------

j := 5 y := 5 j := 30----------------------------------- z := 10 -----------------------------------

Implementando a correta concorrência

Locks e Bloqueio

Locks

• É um mecanismo de sincronização de processos/threads (transações podem implementar processos/threads), em que processos/threads (transações, por exemplo) devem ser programados de modo que seus efeitos sobre os dados compartilhados sejam equivalentes serialmente.

Locks

• Se for sabido que cada uma de várias threads (transações) tem o mesmo efeito correto quando executada sozinha, então podemos inferir que, se essas threads (transações) forem executadas uma por vez, em alguma ordem, o efeito combinado também será correto.

Locks

• Uma intercalação das operações das threads (transações) em que o efeito combinado é igual ao que seria se as threads (transações) tivessem sido executadas uma por vez, em alguma ordem, é uma intercalação equivalente serialmente.

Locks

• Quando dizemos que duas threads (transações) distintas tem o mesmo efeito, queremos dizer que as operações de leitura sobre variáveis de instâncias de objetos (por exemplo, contas bancárias) retornam os mesmos valores e que essas variáveis de instância de objetos tem os mesmos valores finais.

Locks

• O uso de equivalência serial como critério para execução concorrente correta evita a ocorrência de atualizações perdidas ou recuperações inconsistentes.

• Um exemplo simples de mecanismos para disposição em série, é o caso de locks (travas) exclusivos.

Locks

• Nesse esquema, um servidor tenta impedir o acesso (travar) a qualquer objeto que esteja para ser usado por qualquer operação de uma thread (ou transação) de um cliente do servidor.

Locks

• Se um cliente solicitar acesso a um objeto que já está bloqueado (travado) devido a uma thread de outro cliente, o pedido será suspenso e o cliente deverá esperar até que o objeto seja destravado.

Locks

• A equivalência serial exige:

“que todas os acessos de uma transação a uma variável em particular, sejam dispostos em série com relação aos acessos feitos por outras transações”.

Locks

• Todos os pares de operações conflitantes de duas transações devem ser executados na mesma ordem.

• Para garantir isso, uma transação não pode solicitar novos locks após ter liberado um.

Locks (Travas)

• Um exemplo simples de mecanismo para a disposição das transações em série, é o uso de locks (travas) exclusivos.

• Nesse esquema, um Lock tenta impedir o acesso (travar) a qualquer dado que esteja para ser usado por qualquer operação da transação de um cliente.

Locks

• Se um cliente solicitar o acesso a um dado que já está travado devido a transação de outro cliente, o pedido será suspenso e o cliente querendo acessar, deverá esperar até que o objeto seja destravado.

Locks em Java

import java.util.concurrent.locks.Lock;import java.util.concurrent.locks.ReentrantLock;import java.util.concurrent.locks.Condition;

...

// Criação de um objeto acessLock da classe Lock para// controlar a sincronização de algum objeto// compartilhado.Private Lock acessLock = new ReentrantLock;

Locks em Java// Condições para controlar a leitura e a escrita.private Condition podeEscrever = acessLock.newCondition();private Condition podeLer = acessLock.newCondition();

...// Escreve valor no objeto compartilhado ...// Para travar o objeto compartilhado, quando o método// set() for chamado ...

public void set( ... ) {

accessLock.lock(); // chama o método lock e bloqueia (trava) o objeto compartilhado. Esse método esperará até que a trava esteja disponível.

...

// Se o objeto estiver sem condição de escrita ...podeEscrever.await(); // Espera uma condição ocorrer

...

Locks em Java// Sinaliza a thread que está esperando para fazer uma

leitura.

podeLer.signal(); // avisa que uma condição ocorreu ...

...

finally{accessLock.unlock; // destrava o objeto compartilhado.}

} // fim do método set.

Locks em Java

// Ler valor no objeto compartilhado ...// Para travar o objeto compartilhado, quando o método// get() for chamado.

public void get() {

accessLock.lock() // chama o método lock e bloqueia (trava) o objeto compartilhado. Esse método esperará até que a trava esteja disponível.

...

// Se o objeto estiver sem condição de ser lido...podeLer.await(); // Espera uma condição ocorrer

...

Locks em Java// Sinaliza a thread que está esperando para fazer uma// leitura.

podeEscrever.signal(); // avisa que uma condição ocorreu

...

finally{accessLock.unlock; // destrava o objeto compartilhado.}

} // fim do método get.

Locks em Java

• Execute os exemplos Deitel 23.11 e 23.12, aproveitando os códigos em 23.6 (interface Buffer), 23.7 (Producer) e 23.8 (Consumer), para o Relacionamento Producer-Consumer com sincronização usando Locks.

• Ou o exemplo no link Locks Explícitos e Variáveis de Condição