% Sistemas Distribuídos % Lista3 % Aluno: Marcos Seefelder de Assis Araujo
1.
- Processo que chama e processo que executa função estão em máquinas diferentes, acarretando em espaços de endereçamento e ambiente computacional distintos o que pode significar, por exemplo, em representação de dados de maneiras distintas (Little Endian, Big Endian);
- Falhas de rede e das máquinas envolvidas.
Extra: Little Endian vs. Big Endian
Sistemas representam vetores de bytes de maneiras diferentes. Considerando que temos uma word (32 bits) representada em hexadecimal por 0A0B0C0D:
- Big Endian (MSB primeiro): Vai representar na memória (m[]) como m[0] = 0A; m[1] = 0B; m[2] = 0C; m[3] = 0D;
- Little Endian (LSB primeiro): Vai representar na memória (m[]) como m[0] = 0D; m[1] = 0C; m[2] = 0B; m[3] = 0A;
2.
- Cliente faz chamada de função para servidor de RPC e espera (bloqueante) mensagem de aceitação;
- Servidor de RPC recebe chamada de função e envia mensagem de aceitação para cliente. Servidor passa a executar procedimento local...;
- Cliente recebe aceitação, a chamada de função retorna mas ainda não há resultado. Cliente continua sua execução...;
- Ao terminar o procedimento, servidor envia resultado ao cliente via RPC;
- Mensagem de resultado gera uma interrupção no cliente, que por sua vez envia o reconhecimento de que recebeu a mensagem ao servidor.
Extra: Marshalling, Unmarshalling e Stubs
Para evitar problemas por divergências nas representações de dados entre os participantes de um sistema de RPC, é feito o marshalling de mensagens a serem enviadas, convertendo a mensagem para uma representção de comum acordo entre os participantes. Ao receber uma mensagem, é feito o unmarshalling da mesma.
Tanto o marshalling quanto o unmarshalling são feitos pelos stubs, que são trechos de código fornecidos pelas biblioecas de RPC e tornam o envio e recebimento de chamadas e retornos de RPC transparentes aos usuários.
3.
A sincronização de relógio resolve o problema da odenação global de eventos para as máquinas cujos relógios foram sincronizados. Um exemplo de situação gerada por esse problema de ordenação em Sistemas Distribuídos é:
- Dois usuários compartilam um diretório no Dropbox;
- O usuário 1 envia a versão v1 de um documento e seu computador marca 12:00 no momento do envio;
- O usuário 2 envia a versão v2 do mesmo documento 5 minutos depois, mas o relógio do computador dele está 1 hora atrasado em marca 11:05 na hora do envio;
- A versão mais recente para o Dropbox fica como v1.
Caso os relógios dos usuários estivessem sincronizados no exemplo anterior, o problema não ocorreria.
4.
A sincronização de relógios tem dois problemas principais: Qual é a hora certa e como fazer a sincronização.
O problema da hora certa é resolvido utilizando padrões internacionais e protocolos para definir uma hora certa para todos, sendo UTC (Universal Time Coordinated) o padrão utilizado atualmente. O mesmo é baseado em dois componentes: o TAI (International Atomic Time), e combina os tempos de cerca de 400 relógios atômicos de alta precisão espalhados pelo mundo, e o UT1 que é referente à rotação da Terra.
Já o método de sincronização atual para computadores é o Network Time Protocol (NTC) que utiliza UTC como referência. O sistema funciona como uma hierarquia de servidores que vão da maior pra menor precisão. Nesse sistema, clientes solicitam a hora periodicamente a três ou mais servidores e determina sua hora utilizando uma média com filtros (para a remoção de outliers) dos valores obtidos. A hora não é alterada imediatamente, para evitar saltos temporais e a volta no tempo. O que ocorre é que ataxa de progressão do relógio é ajustada para que o relógio local se ajuste suavemente para UTC.
5.
Considerando dois computadores A e B, B quer usar o relógio de A como referência para a sincronização:
-
B envia uma solicitação em
$T1$ (tempo registrado em B) para A, guardadndo o valor de$T1$ ; -
A recebe a solicitação em
$T2$ , processa a mesma e envia a resposta em$T3$ para B, mandando na mensagem os valores de$T2$ e$T3$ (tempos registrados em A); -
B recebe a resposta em
$T4$ (tempo registrado em B); - Assumindo que o retardo de ida é igual ao de volta, B calcula o mesmo como
$d = ((T_4 - T_1) - (T_3 - T_2))/2$ e ajusta seu relógio para$T_3 + d$ .
Dessa maneira, B é sincronizado a A.
6.
O Network Time Protocol (NTP) funciona para sincronizar relógios com o padrão UTC e é estrutuado com uma hierarquia de servidores e clientes. No topo da hierarquia estão os computadores com relógios de maior precisão. Descendo na hierarquia, a precisão diminui.
Um determinado computador em um nível da hierarquia solicita a hora periódicamente para três ou mais servidores de uma hierarquia superior. Ele faz então uma filtragem dos resultados, para remover outliers, tira uma média e ajusta sua taxa de progressão para se ajustar suavemente ao horário padrão.
7.
- Relações
$x \rightarrow y$ :$a \rightarrow r$ $h \rightarrow b$ $i \rightarrow n$ $s \rightarrow j$ $c \rightarrow o$ $d \rightarrow t$ $k \rightarrow e$ $p \rightarrow f$ $u \rightarrow l$ $g \rightarrow q$
- Uma relação
$x \parallel y$ :$p \parallel u$
- Relações no conjunto
$E = {b,k,n,u}$ :$b \parallel k$ $b \parallel n$ -
$b \rightarrow u$ :$b \rightarrow c$ ,$c \rightarrow d$ ,$d \rightarrow t$ ,$t \rightarrow u$ $k \parallel n$ $k \parallel u$ $n \parallel u$
- Relógios de Lamport para cada evento:
- L(a) = 1
- L(b) = 2
- L(c) = 3
- L(d) = 4
- L(e) = 6
- L(f) = 10
- L(g) = 11
- L(h) = 1
- L(i) = 3
- L(j) = 4
- L(k) = 5
- L(l) = 8
- L(m) = 1
- L(n) = 4
- L(o) = 8
- L(p) = 9
- L(q) = 12
- L(r) = 2
- L(s) = 3
- L(t) = 5
- L(u) = 7
- Relógios de vetor:
- V(a) = [1,0,0,0]
- V(b) = [2,1,0,0]
- V(c) = [3,1,0,0]
- V(d) = [4,1,0,0]
- V(e) = [5,5,1,2]
- V(f) = [6,5,5,4]
- V(g) = [7,5,5,4]
- V(h) = [0,1,0,0]
- V(i) = [0,3,1,0]
- V(j) = [1,4,1,2]
- V(k) = [1,5,1,2]
- V(l) = [4,6,1,5]
- V(m) = [0,0,1,0]
- V(n) = [0,3,2,0]
- V(o) = [4,3,4,4]
- V(p) = [4,3,5,4]
- V(q) = [7,5,6,4]
- V(r) = [1,0,0,1]
- V(s) = [1,0,0,2]
- V(t) = [4,1,0,3]
- V(u) = [4,1,0,5]
- Exemplo onde para eventos
$x$ e$y$ ,$L(x) < L(y)$ e$V(y) < V(x)$ : Não existe, pois o relógio de vetor não discorda de lamport na ordenação. - Se
$L(x) < L(y)$ : Nada pode ser concluído; - Se
$V(x) < V(y)$ : Podemos concluir que$x \rightarrow y$
8.
Questão feita à mão no final do documento.
9.
Vantagem: Para um sistema com filas FIFO e sem prioridade o algoritmo é correto (garante o acesso exclusivo) e justo com a troca de apenas três mensagens por acesso à região crítica;
Desvantagem: O algoritmo tem um ponto unico de falha, que é o coordenador da exclusão mútua. Caso o mesmo falhe de alguma maneira, o sistema falha junto.
10.
É interessante que um nó conheça seus dois próximos vizinhos pois no caso de falha de um nó o anel não será quebrado, pois o nó que se conectava com o que falhou só precisa pular o mesmo. Para o caso de falhas de mais vizinhos, seria vantajoso conhecer mais do uqe dois vizinhos.
11.
ACID é a sigla que representa o conjunto de propriedades que um sistema transacional deve apresentar. O significado de suas letras é:
"A" de Atomicity: Uma transação ou é aplicada por inteiro ou é abortada por inteiro sem modificar o estado global;
"C" de Consistency: Toda transação preserva as propriedades do estado global;
"I" de Isolation: Ao ler ou escrever dados, transação executa como se fosse a única no sistema (transações ocorrem uma depois da outra);
"D" de Durability: Ao concluir uma transação (commit), sistema passa a ter um novo estado global que permanece (independente de interferências externas, como falta de energia ou falhas de equipamentos).
12.
Com a implementação pode ocorrer um deadlock. Imaginemos que dois clientes transferencia(a, b, v)
e transferencia(a, b, v)
respectivamente:
-
$C_1$ fazacquire(a)
e passa porse (retirada(a, v) >= 0)
; - Enquanto isso
$C_2$ fazacquire(b)
e passa porse (retirada(b, v) >= 0)
; -
$C_1$ vai ficar esperando peloacquire(b)
e$C_2$ vai ficar esperando peloacquire(a)
, para sempre.
Eu resolveria o código fazendo os dois acquire()
juntos, usando alguma ordenação global:
transferencia(c1, c2, v) {
acquire(min(c1, c2))
acquire(max(c1, c2))
se (retirada(c1, v) >= 0)
deposito(c2, v)
release(c1)
release(c2)
retorna 0
release(c1)
release(c2)
retorna -1
}
13.
Two Phase Locking (2PL):
Mecanismo que serve para controle de concorrência e para a garantia de atomicidade. Faz o uso de dois tipos de lock para cada objeto, read lock (permitem outros read locks simultâneos, mas não um write lock) e write lock (não permite nenhum tipo de lock simultâneo).
Como o nome sugere, são realizadas duas fases:
- Expanding, na qual os locks são adquiridos
- Shrinking, na qual os locks são liberados
E tem duas variações:
- Strict Two Phase Locking: Na qual na fase de Shrinking os write locks são liberados apenas no final da transação, mas os read locks podem ser liberados no decorrer da mesma;
- Strong Strict Two Phase Locking: Na qual na fase de Shrinking, tando os read quanto os write locks são liberados apenas no final da transação.
14.
Two Phase Commit (2PC): O algoritmo de 2PL não serve para casos distribuídos, pois considera que o estado global está "centralizado". O 2PC é um protocolo usado para fazer Commit atômico em sistemas de estado global distribuído.
O protocolo tem duas fases:
- Preparar e votar:
- Coordenador que quer realizar transação (coordenador) envia as subtransações adequadas aos demais processos (participantes);
- Cada processo executa 2PL para adquirir os locks necessários para a subtransação;
- Cada processo responde ao coordenador se pode ou não executar a transação
- Executar:
- Coordenador recebe todas as respostas e envia:
- commit se todas forem positivas
- abort se houver alguma negativa
- Participantes recebem a mensagem:
- caso seja commit, efetuam a transação, liberam os locks e retornam um OK
- caso seja abort, abortam a transação, liberam os locks e retornam um ok
- Coordenador recebe todas as respostas e envia:
15.
O protocolo 2PC não evita deadlocks, basta imaginar um caso em que ocorra a dependência cíclica dos locks levando os participantes a não poderem votar por estarem aguardando locks (ex.: transf(a, b, v)
e transf(b, a, v)
).
Para lidar com deadlocks é definido um timeout para a espera por locks, que se estourado gera uma resposta negativa ao coordenador. Um coordenaor tenta então realiza a transação repetidamente, porém também é imposto um limite à essa repetição a fim de evitar livelocks.
16.
- Se participante falha em INIT: O coordenador dá timeout esperando a resposta e envia um abort;
- Se participante falha em READY: Transação continua normalmente. Ao se recuperar do erro, participante decobre se foi commit ou abort e efetua ou não a transação;
- Se coordenador falha em WAIT: Caso algum outro participante já tenha recebido a ordem de commit ou abort, participantes copiam. Se estiverem todos em estado READY, não tem como decidir o que fazer e aguardam de forma bloqueante, eperando a recuperação do coordenador.
17.
read-write: ocorre quando a leitura e escrita no mesmo dado ocorrem em instâncias diferentes em processos diferentes e a leitura retorna um valor que já está desatualizado devido À escrita recente;
write-write: dois ou mais processos tentam escrever no mesmo dado ao mesmo tempo e o mesmo fica com um valor diferente nas instâncias sendo indefinido qual o valor certo.
18.
-
1: P2: R(x,0)
$\rightarrow$ P1: W(x,1)$\rightarrow$ P2: R(x,1) -
3: P1: W(x,1)
$\rightarrow$ P3: R(x,1)$\rightarrow$ P2: W(x,2)$\rightarrow$ P3: R(x,2) -
4: P2: W(x,2)
$\rightarrow$ P3: R(x,2)$\rightarrow$ P1: W(x,1)$\rightarrow$ P3: R(x,1) -
6: P4 (tudo)
$\rightarrow$ P1 (tudo)$\rightarrow$ P3 (tudo)$\rightarrow$ P2 (tudo)
19.
Confiabilidade (reliability) diz respeito à duração de tempo pela qual um sistema funciona antes de falhar. Disponibilidade (availability) diz respeito à fração de tempo pela qual sistema está operacional.
Um sistema pode ter um MTTF (Mean Time To Failure) de 10 anos (alta confiabilidade) e um MTTR (Mean Time To Repair) de 8 anos (baixa disponibilidade).
20.
Para um componente, temos disponibilidade de aproximadamente 99.85%. Utilizando a fórmula
onde
21.
- Depende. Se não ocorrer nenhuma falha na mesma coluna, para cada nível haverá sempre uma maioria funcionando e o resultado será correto. Porém, se ocorrer de duas das falhas ocorrerem na mesma coluna (dois votadores ou dois componentes), o sistema falha.
- O sistema falha, pois no próximo nível apenas um componente funcionará corretamente e o resultado no nível não terá maioria.
22.
Pois as mesmas são imprevisíveis e não são fáceis de se detectar. Uma falha bizantina pode passar despercebida, pois os resultados continuam sendo gerados, porém de maneira errada, podendo tornar incorreto o funcionamento do sistema do qual faz parte. Já uma crash failure, o componente que falhou para de interferir no sistema, pois simplesmente para de funcionar.
23.
Se um particiante recebe uma mensagem