Sistemas Distribuídos Introdução a Sistemas Distribuídos 30/8/[email protected] São Paulo, 2011 Universidade Paulista (UNIP) Conceitos

Sistemas DistribuídosSistemas DistribuídosIn

trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os

27/04/23 [email protected] 1

São Paulo, 2011São Paulo, 2011

Universidade Paulista (UNIP)Universidade Paulista (UNIP)

Conceitos Fundamentais e Convenções de Conceitos Fundamentais e Convenções de NotaçãoNotação

Prof. MSc. Vladimir CameloProf. MSc. Vladimir [email protected]

mailto:[email protected]

http://www3.unip.br/


trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


É normalmente muito mais conveniente tratar com processos ao invés

de processadores:

Um sistema distribuído é composto por N processos que

executam em M processadores diferentes.

Processadores são conectados por canais (vias) de comunicação

o que possibilita a troca de informações entre estes

processadores.

Notações formaisNotações formais



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


A evolução do sistema é modelada por uma seqüência de eventos ep

Um evento modifica o estado de p (processo)

A história H é uma seqüência de tuplas (registros) contendo um

evento ep e o estado de p após ep

Uma execução (run) é um conjunto ordenado de eventos descrito por

uma história

Notações formaisNotações formais



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Safety (Segurança)

Garantir que problemas não aconteçam e caso venham acontecer

não devem acarretar em problemas para o sistema.

Liveliness (Vivacidade)

Garantir que o sistema estará sempre ativo

Timeliness (Tempo de envio)

Adicionar requisitos de tempo real às propriedades de liveliness

Propriedades desejáveis em um sistema distribuídoPropriedades desejáveis em um sistema distribuído



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


O primeiro componente da comunicação na rede é a nomeação dos

sistemas na rede.

Endereços são úteis para localizar componentes em um sistema

distribuído;

Nomes, além de serem mais fáceis de serem lembrados:

São independentes do protocolo de comunicação e da localização

do componente;

Podem ter seu significado mudado ao longo do tempo sem

interferir na localização do componente.

Nomes e endereçosNomes e endereços



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Nome são convenientes para uso humano, mas os computadores

preferem números, por velocidade e simplicidade.

Para traduzir nomes em endereços físicos é preciso um tradutor

(Domain Name SystemDNS).

Nomes “puros” vs “impuros”

Níveis de abstração

[email protected] é um nome ou um endereço?

Nomes e endereçosNomes e endereços




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Serviços de nomes traduzem nomes em endereços:

Propriedades básicas:

Binding (Ligação)

Associa um nome a um endereço

Lookup (pesquisa binária)

Recupera (resolve) um endereço a partir de um nome

Unbinding (Desassociar)

Desassocia um nome a um endereço liberando este endereço

para que o mesmo possa ser associado a outro nome.

Mapeamento de NomesMapeamento de Nomes



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Mecanismo básico de interação em sistemas distribuídos:

Endereçamento;

Protocolo de comunicação;

Formato das mensagens; e

Confiabilidade.

Troca de mensagensTroca de mensagens



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Troca de mensagensTroca de mensagens



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Os principais serviços disponibilizados por uma plataforma de grupos são:

Filiação:

Visões:

Propriedades

Exatidão

Consistência

Multicast:

Confiabilidade

Ordenação

Comunicação em grupoComunicação em grupo



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Multicasting – tipo de comunicação que possibilita a transmissão para

um número de receptores ou nós, com um endereço em cada

mensagem para indicar o nó desejado a ser acessado.

Serviço de transporte:

Roteamento;

Tolerância a omissões;

Controle de fluxos

Ordenação;

Gerência de filiação (incluindo recuperação de falhas)

Principais componentes de um MulticastPrincipais componentes de um Multicast



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


As técnicas de sincronização são importantes pois freqüentemente os

sistemas distribuídos precisam realizar tarefas que necessitam de um

comportamento sincronizado.

Em sistemas com uma única CPU, problemas tais como regiões

críticas, exclusões mútuas e outros problemas de sincronização são

geralmente resolvidos utilizando métodos tais como semáforos e

monitores.

Em sistemas distribuídos esses métodos não podem ser utilizados

pois os vários processadores não compartilham o mesmo espaço de

endereçamento.

SincroniaSincronia



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Sincronismo em sistemas distribuídos é mais complicado do que nos

sistemas centralizados pois há a necessidade de utilizar algoritmos

distribuídos.

Não é possível, ou desejável, coletar todas as informações sobre o

sistema em um único lugar e deixar que um único processo analise

as informações e tome uma decisão.

SincroniaSincronia



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Em geral, nos algoritmos distribuídos:

As informações relevantes devem estar espalhadas nas várias

máquinas;

Os processos tomam decisões baseadas somente em

informações locais;

Deve ser evitado um único ponto de falha no sistema que paralise

todo o sistema;

Caso contrário, torna o sistema não confiável

SincroniaSincronia



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os



Não existe um “clock” comum ou um único tempo global

Obter um acordo de tempo não é um trivial em um sistema

distribuído.

Para alguns algoritmos, o que importa é a consistência interna

Relógios conhecidos como relógios lógicos

SincroniaSincronia



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os



Outros algoritmos possuem a restrição de que os relógios devem

não somente ser os mesmos, mas também o tempo real não

pode divergir de mais de uma certa quantidade.

Relógios conhecidos como relógios físicos.

SincroniaSincronia



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Sincronia:

Envio de mensagens:

blocking (Negado) non-blocking (Não-Negado);

Iteração:

same-time (Mesmo-Tempo) different-time (Tempo-

Diferente);

hardware clock-driven (Relógio-Controlado);

limite superior para execução de ações.

SincroniaSincronia



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Primitiva bloqueante Vs não-bloqueantesPrimitiva bloqueante Vs não-bloqueantes



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Assíncrono:

sem limites de tempo para ações.

Síncrono:

ações têm limites de tempo conhecidos.

Parcialmente síncrono:

ações têm limites de tempo para acontecer, mas estes são

desconhecidos e/ou válidos somente parte do tempo.

Graus de SincroniaGraus de Sincronia



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Nos sistemas distribuídos assíncronos não existe nenhuma restrição

em relação aos atrasos de escalonamento e de transmissão de

mensagens;

Falhas arbitrárias afetam o sistema;

Resultado de impossibilidade de Fischer, Lynch e Patterson (FLP,

FLP85):

Não há como obter acordo, mesmo que só um processo falhe e

mesmo que a semântica seja crash (travamento, situação onde o

programa trava e com isso há a necessidade de religar o computador (boot));

Esse modelo assíncrono serve para alguma coisa?

Sistemas distribuídos assíncronosSistemas distribuídos assíncronos



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Principais características de um sistema distribuído síncrono:

Atrasos máximos conhecidos para escalonamento (), para

transmissão de mensagens () e drift (desvio) dos relógios locais

().

Sistemas construídos assumindo esse modelo são:

menos portáveis;

menos seguros.

Sistemas distribuídos síncronoSistemas distribuídos síncrono



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Estes tipos de sistemas apresentam algum grau de sincronismo;

Os dois tipos de sincronismos utilizados neste tipo de sistema são:

Sincronismo no tempo:

Sistemas que não são sempre assíncronos;

Sincronismo no espaço:

Sistemas que não são completamente assíncronos;

Sistemas distribuídos parcialmente assíncronosSistemas distribuídos parcialmente assíncronos



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Qual o melhor tipo de sincronismo para utilizar em um sistema

distribuído, ou melhor, qual deve ser escolhido:

Assíncrono:

Fácil de implementar, mas pouco útil.

Síncrono:

Muito poderoso, mas conflita com escala, abertura,

interatividade, bom uso dos recursos;

Utilizado em sistemas embarcados.

Qual deve ser escolhidoQual deve ser escolhido



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Qual o melhor tipo de sincronismo para utilizar em um sistema

distribuído, ou melhor, qual deve ser escolhido:

Parcialmente síncrono:

Muito usado em computação de uso geral;

Semântica tipicamente não é claramente definida.

Qual deve ser escolhidoQual deve ser escolhido



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Fundamental para que se possa raciocinar sobre sistemas

distribuídos;

Tipos de ordenação das mensagens:

Multicasts não ordenados;

Multicasts ordenados em Fifo;

Multicasts ordenados por causalidade;

Multicasts totalmente ordenados.

OrdenaçãoOrdenação



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Multicast não ordenada:

Não são dadas garantias quanto à ordem na qual as mensagens

recebidas são entregues aos diferentes processos

Ordenação de mensagensOrdenação de mensagens



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Multicast ordenada em FIFO: entre quaisquer dois processos, as

mensagens são entregues em ordem;

Camada de comunicação é forçada a entregar as mensagens que

chegam do mesmo processo na mesma ordem em que elas foram

enviadas.

Causal: se envio(m) envio(n), então

entrega(m) entrega(n)

Total: Quaisquer duas mensagens entregues a quaisquer dois

processos são entregues na mesma ordem

Fundamental para replicação ativa




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Entrega de mensagens de modo que a potencial causalidade entre

mensagens diferentes seja preservada;

Se m1 precede uma outra mensagem m2 por causalidade,

independentemente de terem sido enviadas por processos diferentes,

camada de aplicação sempre entregará m2 após ter recebido e

entregado m1;

Utilização de relógios vetoriais.




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Multicast confiável com entrega totalmente ordenada

Significa que as mensagens devem ser entregues na mesma

ordem a todos os membros do grupo

Entregas podem ser dos tipos não ordenada, ordenada em Fifo ou

ordenada por causalidade




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


O tempo em um sistema distribuído tem um papel crucial na

ordenação de eventos.

Os 2 principais uso do tempo em um sistemas distribuídos, são:

Gravar e observar a localização de eventos na linha do tempo.

seqüenciamento de eventos que formam um estado global

para os processos.

Forçar o futuro posicionamento de eventos na linha do tempo

Sincronização dos processos em execução.

Tempo em um sistema distribuídoTempo em um sistema distribuído



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


O que é tempo real?

Função monotônicamonotônica, contínua e crescente;

O que é 1 segundo?

Várias definições:

Divisor de um dia solar

Relógios atômicos;

Tempo e relógiosTempo e relógios



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Funções monotônicas são definidas como aquelas cuja qualidade do

resultado aumenta (ou pelo menos não diminui) na medida em que o

tempo de execução da função aumenta.

Tem a forma de um laço onde cada iteração refina um pouco mais o

resultado até então obtido.

Algoritmos deste tipo podem ser encontrados nas áreas de cálculo

numérico, estimativa probabilista, pesquisa heurística e ordenação

de dados.

Função MonotônicaFunção Monotônica



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Por exemplo, algoritmos de inteligência artificial utilizados em vídeo-

game podem ser programados desta forma.

Este tipo de função faz com que o escalonador tenha que decidir

quanto tempo de processador cada parte opcional deve receber.

É a forma de programação que fornece maior flexibilidade ao

escalonador, pois qualquer tempo extra de processador que a função

recebe melhora o resultado.

Função MonotônicaFunção Monotônica



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


A linha do tempo

Timestamps (Uma hora é uma seqüência de caracteres,

indicando a data e / ou tempo em que um determinado evento

ocorreu. No do Unix? É a contagem, em segundos, desde o dia 1

de janeiro de 1970 00:00:00 GMT);

Duração de intervalos;

Timers e relógios.

Tempo e relógiosTempo e relógios



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


GMT: Greenwich Mean Time;

BIH: Bureau Internacional de l’Heure;

TAI: International Atomic Time;

UTC: Universal Coordinated Time;

NIST: National Institute of Standard Time;

WWV: estação de rádio de ondas curtas;

GEOS: Geostationary Environment Operational Satellite

Relógio físicoRelógio físico



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


O hardware (rf) implementa uma função monotônica discreta e

crescente que mapeia o tempo real t em um tempo de relógio rf(t)

Imperfeições de relógios físicos:

Granularidade (g)

Taxa de desvio (r)

Relógios locais físicosRelógios locais físicos



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Granularidade:

Relógios físicos avançam em ticks (tk)

g = rf(tk+1) – rf(tk)

Taxa de desvio:

Dependendo da qualidade do relógio e das condições do

ambiente (ex. temperatura)

0 ≤ 1-r ≤ (rf(ttk+1) – rf(ttk))/g ≤ 1+r para 0 ≤ ttk ≤ ttk+1

Propriedade de um relógio físicoPropriedade de um relógio físico



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Prover timestamps para eventos locais;

Medir durações locais;

Definir timeouts (tempo de espera);

Medir durações de atraso round-trip (Curva-erro);

Para que serve um relógio local?Para que serve um relógio local?



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Um relógio global é construído por meio da sincronização de

relógios locais:

Cada processo p cria um relógio virtual (rvp) a partir do seu

relógio local (rfp);

Os relógios virtuais são criados de forma a estarem

sincronizados;

São resincronizados de tempos em tempos de modo que

possam manter a consistência. Esta tarefa é realizada pelo

sistema distribuído.

Relógios globaisRelógios globais



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Convergência (d): quão próximo os relógios estão sincronizados logo

após uma resincronização;

Precisão (p): quão próximos os relógios se mantêm sincronizados

entre si em qualquer tempo (sincronização interna dos relógio

locais);

Exatidão (a): quão próximos os relógios estão sincronizados em

relação a uma linha de tempo absoluta de referência (sincronização

externa);

Taxa (r): é a taxa instantânea de desvio.

Propriedades de um relógio globalPropriedades de um relógio global



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Sistemas envolvendo múltiplos processos são programados mais

facilmente utilizando regiões críticas;

Quando um processo deve ler ou atualizar estruturas de dados

compartilhadas, ele tenta primeiro garantir a exclusão mútua para

acesso à região crítica;

Em um sistema centralizado, isso é facilmente conseguido por meio

de semáforos ou monitores;

Em sistemas distribuídos impor a exclusão mútua exige um cuidado

maior.

Exclusão mútuaExclusão mútua



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Semáforo S: variável não-negativa inteira que só pode se modificada

pelos procedimentos up() (em atividade) e down() (inativo)

down(S)

se S > 0: decremente S

senão: bloqueia esperando up(S)

up(S)

se há alguém bloqueado: desbloqueie

senão: incremente S




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


A exclusão mútua trabalha com técnicas distintas:

Técnica centralizada;

Técnica totalmente distribuída;

Técnica Token Ring.




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Técnica centralizada:

Um processo é eleito como coordenador;

Quando um processo precisa entrar numa região crítica, este

envia uma mensagem request ao coordenador informando qual a

região crítica e requisitando a permissão;

Se nenhum outro processo está na região crítica, o coordenador

envia uma mensagem reply garantindo permissão;

Quando uma mensagem resposta chega, o processo entra na

região crítica.




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Técnica totalmente distribuída:

Um processo é eleito como coordenador;

O algoritmo centralizado tem o problema de uma falha no

coordenador inviabilizar o mecanismo;

No algoritmo distribuído, quando um processo entra na região

crítica, ele constrói uma mensagem contendo o nome da região

crítica, o número do processo e o tempo corrente e envia essa

mensagem para todos os processos, inclusive ele próprio;




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os



Quando um processo recebe uma mensagem de requisição de

outro processo:

Se o receptor não está na região crítica e não quer entrar, ele

envia de volta uma mensagem de OK;

Se o receptor já está na região crítica, ele não responde e

coloca a requisição na fila;




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os



Se o receptor quer entrar na região crítica mas ainda não

conseguiu, ele compara o tempo da mensagem (timestamp)

que chegou com o timestamp da mensagem que ele enviou.

A que tiver timestamp menor vence;

Se a mensagem que chegou é menor, o receptor envia

uma mensagem OK para o processo emissor;

Se a sua mensagem é a que possui o timestamp menor,

o receptor coloca na fila a mensagem request e não

responde ao emissor




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Técnica Token Ring:

Neste algoritmo, é construído um anel lógico por software no qual

a cada processo é atribuído uma posição no anel;

Quando o anel é inicializado, o processo 0 ganha o token, o qual

circula no anel (passa do processo k para o processo k + 1);

Quando o processo ganha o token ele verifica se ele quer entrar

na região, realiza seu trabalho e, ao deixar a região, passa o

token para o elemento seguinte do anel;

Não é permitido entrar numa segunda região crítica com o

mesmo token;




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Técnica Token Ring:

Se o processo não quer entrar na região crítica, ele simplesmente

passa o token;

Como conseqüência, quando nenhum processo quer entrar na

região crítica, o token fica circulando no anel;




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Problemas:

Se o token é perdido ele precisa ser regenerado.

A detecção de um token perdido é difícil;

Se um processo falha também ocorrem problemas e a solução é

fazer com que o processo que recebe o token confirme o

recebimento.

O processo que falhou pode ser retirado do anel e o token enviado

para o processo seguinte.

Este procedimento requer que todos os processo saibam da

configuração do anel.




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Necessário para coordenar processos e evitar “colisões”;

Servidor de lock:

Interessados em entrar na região crítica mandam mensagem

LOCK para o servidor;

O servidor só responde com LOCK-GRANTED para um processo;

Processo envia UNLOCK ao sair da região.

Servidor é ponto único de falhas e possível gargalo de performance;

Falha no cliente também é problema.

Exclusão mútua via servidor de LockExclusão mútua via servidor de Lock



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


O que é um DeadLock?O que é um DeadLock?

É uma falha e não um erro.É uma falha e não um erro.

Falha: possibilita a recuperação do sistema e recuperação de Falha: possibilita a recuperação do sistema e recuperação de

seu estado anterior;seu estado anterior;

Erro: gera uma parada no sistema impossibilitando muitas Erro: gera uma parada no sistema impossibilitando muitas

vezes sua recuperação;vezes sua recuperação;

Ocorre quando mais de um usuário alteram o mesmo registro ao Ocorre quando mais de um usuário alteram o mesmo registro ao

mesmo tempo.mesmo tempo.

DeadlockDeadlock



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Um Deadlock ocorre quando um processo fica esperando por outro;Um Deadlock ocorre quando um processo fica esperando por outro;

Para resolver problemas com Deadlock é necessário ter:Para resolver problemas com Deadlock é necessário ter:

Exclusão mútua, espera circular, obtém-e-espera, não-Exclusão mútua, espera circular, obtém-e-espera, não-

preempção, etc;preempção, etc;

Tudo o que se conhece sobre Deadlock em sistemas concorrentes Tudo o que se conhece sobre Deadlock em sistemas concorrentes

vale para sistemas distribuídos, com a complicação de que não se vale para sistemas distribuídos, com a complicação de que não se

tem uma visão global do sistema.tem uma visão global do sistema.

DeadlockDeadlock



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Como garantir que alguma propriedade sistêmica do sistema é

válida? Ou seja, como garantir que (ou checar se) a execução do

sistema é consistente e apresenta os resultados esperados?

Para checar, pode-se parar o sistema e montar um estado global:

Isto é um processo dispendioso;

Protocolos de snapshot (versões de teste - cópia) distribuído são

uma solução bem mais eficiente para o problema.

ConsistênciaConsistência



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Um conjunto de participantes é denominado Visão;

É fundamental que cada mensagem seja entregue a todos os seus

destinatários na mesma visão;

Muitas vezes é importante saber quais processos constituem o

sistema como um todo;

Por exemplo, rank e size viabilizam a computação determinística

de uma propriedade por todos os processos;

Acordo sobre participantesAcordo sobre participantes



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Como aumentar a nossa intuição para resolver problemas?

Por meio da utilização de modelos que possibilitam escolher a melhor

forma de implementação de um sistema distribuído;

Os dois principais modelos utilizados são:

Experimentação

Modelagem e análise

Modelos para sistemas distribuídosModelos para sistemas distribuídos



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Experimentação

Abordagem prática baseada no acúmulo de informação;

Pode ser usada para construir coisas similares a outras já

construídas.

A experimentação direta pode ser muito cara e algumas vezes

impraticável ou mesmo consumir muito recurso.




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Modelagem e análise

Abordagem teórica baseada na simplificação do objeto de estudo

(“mundo real”);

Seguida de análise - matemática ou lógica - para inferir

propriedades básicas do sistema e possibilitar atingir os

resultados esperados.




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


A modelagem oferece um controle muito maior sobre o sistema a ser

construído, já que esta se baseia em modelo matemáticos;

A modelagem só é útil se o modelo caracteriza o objeto de estudo de

forma apropriada;

A experimentação é muito importante para validar modelos.

Modelagem Vs ExperimentaçãoModelagem Vs Experimentação



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Para que um modelo possa ser considerado bom é preciso observar

as seguintes características:

Preciso:

A análise do modelo deve levar a conclusões verdadeiras

sobre o objeto de estudo.

Como identificar um bom modeloComo identificar um bom modelo



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Para que um modelo possa ser considerado bom é preciso observar

as seguintes características:

Tratável:

Um modelo que não permite a execução de uma análise é

inútil;

Em um modelo tratável, as regras que governam o

comportamento dos atributos do modelo são normalmente

definidas através de fórmulas matemáticas ou lógicas

Como identificar um bom modeloComo identificar um bom modelo



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


A simulação é considerada uma alternativa à experimentação pois

possibilita que sejam obtidos resultado muito próximos dos resultado

de um sistema real sem a necessidade de arcar com o custo de

construí-lo e observar assim se este será viável ou não para

construção;

SimulaçãoSimulação



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


A simulação também é considerada uma alternativa à modelagem

pois possibilita analisar situações que não podem ser modeladas de

forma tratável/representativa tradicionalmente.

SimulaçãoSimulação



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Viabilidade:

Que classes de problemas podem ser resolvidos utilizando este

modelo;

Se será viável a construção do sistema distribuído com base no

modelo proposto.

Custo:

Para as classes que podem ser resolvidas, quão cara (em termos

de recursos, tempo de processamento, etc.) uma solução será;

Ambas as respostas têm valor prático e teórico;

Quais respostas um bom modelo pode disponibilizarQuais respostas um bom modelo pode disponibilizar



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Os atributos mais importantes em um sistema distribuído são:

Sincronismo entre os processos:

Sistemas Síncronos

Sistemas Assíncronos;

Atributos importantes de um sistema distribuídoAtributos importantes de um sistema distribuído



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Os atributos mais importantes em um sistema distribuído são:

Semântica de falha dos componentes:

Parada (failstop);

Crash (falha de um componente ou erro em um programa

durante sua execução);

Omissão;

Desempenho;

Arbitrária;

Restrições obtidas por meio de autenticação.

Atributos importantes de um sistema distribuídoAtributos importantes de um sistema distribuído



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Uma outra abordagem é definir o sincronismo extra necessário em

termos de propriedades que precisam ser satisfeitas em um sistema

distribuído, por exemplo;

Classes de detectores

Abrangência: que falhas são ou podem ser detectadas pelo

sistema distribuído;

Exatidão: que erros podem acontecer durante o processo de

execução de um sistema distribuído.

Detectores de falhas não confiáveisDetectores de falhas não confiáveis



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Uma outra abordagem é definir o sincronismo extra necessário em

termos de propriedades que precisam ser satisfeitas em um sistema

distribuído, por exemplo;

Sincronismo no tempo

Global Stabilization Time

Sincronismo no espaço

Wormholes (tradução livre – buraco de verme: é um atalho

hipotético que liga duas regiões no espaço tempo).

Detectores de falhas não confiáveisDetectores de falhas não confiáveis



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Para a escolha de um modelo a ser utilizado é preciso:

Observar as características do ambiente de execução do sistema

distribuído, como por exemplo:

Tipos dos componentes a serem utilizados para sua

construção;

Qualidade dos componentes utilizados;

Controle sobre o ambiente em que o sistema distribuído será

construído.

Como escolher um modeloComo escolher um modelo



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Para a escolha de um modelo a ser utilizado é preciso:

Requisitos da aplicação a ser construída:

Aplicações críticas.

Usar uma coleção de modelos:

Processadores com semântica de falha controlada;

Canais confiáveis.

Como escolher um modeloComo escolher um modelo



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Estratégias:

Recuperação do erro: O sistema deve possuir mecanismos que

garantam o avanço ou recuo no estado do sistema para um

estado consistente;

Compensação: O sistema deve atuar em outros componentes

para equilibrar o estado do sistema de modo a funcionar

normalmente.

Estratégias e políticasEstratégias e políticas



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Políticas:

Transações atómicas distribuídas;

Replicação ativa/passiva.

Estratégias e políticasEstratégias e políticas



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Ativa: Ativa: todos os componentes funcionam e quando algum falta os todos os componentes funcionam e quando algum falta os

outros devem substituir este componente de maneira que o sistema outros devem substituir este componente de maneira que o sistema

como um todo não seja penalizado.como um todo não seja penalizado.

ReplicaçãoReplicação



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Passiva:Passiva: neste modelo exsite um componente principal e secundário neste modelo exsite um componente principal e secundário

que imita o principal, na falta do componente principal o secundário que imita o principal, na falta do componente principal o secundário

assume o seu papel possibilitando a continuidade dos serviços do assume o seu papel possibilitando a continuidade dos serviços do

sistema.sistema.




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Passiva:Passiva:

Propriedades básicas:Propriedades básicas:

1 e somente um servidor principal (denominado como 1 e somente um servidor principal (denominado como

Master);Master);

Qualquer cliente apenas conhece a identidade de um único Qualquer cliente apenas conhece a identidade de um único

servidor (Master);servidor (Master);

1 servidor não primário quando recebe mensagens de 1 servidor não primário quando recebe mensagens de

clientes ignora as solicitações realizadas.clientes ignora as solicitações realizadas.




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Passiva:Passiva: neste modelo exsite um componente principal e secundário neste modelo exsite um componente principal e secundário

que imita o principal, na falta do componente principal o secundário que imita o principal, na falta do componente principal o secundário

assume o seu papel possibilitando a continuidade dos serviços do assume o seu papel possibilitando a continuidade dos serviços do

sistema.sistema.




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Passiva:Passiva:

Principais problemas:Principais problemas:

Detectar quando o servidor primério parou;Detectar quando o servidor primério parou;

Garantir a coerência do estado do servidor secundário com o Garantir a coerência do estado do servidor secundário com o

servidor primério.servidor primério.




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Garantir que aplicações que manipulam estruturas de dados

persistentes tenham:

A possibilidade de recuperação de estados errados – em caso de

falhas graves;

A sincronizam das suas ações de forma consistente com outras

transações que utilizam os mesmos dados;

Transações - objetivosTransações - objetivos



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Atomicidade - uma transação ou se executa na sua totalidade ou não

se executa;

Consistência - cada transação deve, a partir de um estado inicial

válido e caso se execute completamente, atingir um novo estado

válido para continuar seu processo de execução;

Transações - propriedadesTransações - propriedades



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Seriabilidade (Isolation) - se diversas transações se executarem em

paralelo sobre os mesmos objetos, o resultado é como se as

transações se executassem em série numa determinada ordem;

Persistência (Durability) - os resultados de uma transação confirmada

permanecem depois desta acabar e podem sobreviver ao conjunto de

falhas dos mecanismos de armazenamento de maneira que possam

recuperar seu estado em caso de falhas.

Transações - propriedadesTransações - propriedades



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Localização - dados sobre os quais a transação se realiza estão

todos no mesmo local físico (servidor principal) ou repartidas por

vários sistemas possibilitando em caso de falhas a recuperação

destas informações;

Duração - transações destinadas a atualizações interativas (on-line) e

aquelas que irão ser executadas sobre grandes volumes de

informação, de forma não interativa (off-line);

Estrutura - a uma transação apenas pode corresponder a um único

fio de execução ou existirem múltiplos fluxos de execução no interior

de uma transação.

Transações - classificaçãoTransações - classificação



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Aborto explícito da transação:

Explicitamente desencadeada pelo programa em caso de falhas

graves no sistema;

Falha de paragem do sistema:

Perdeu-se o conteúdo da memória volátil impossibilitando o

progresso no processo de execução.

Transações – Topologia de falhasTransações – Topologia de falhas



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Falha nos sistemas de armazenamento persistente:

É necessário implementar uma memória estável que garanta a

redundância da informação e que permita recuperar a que tenha

sido eventualmente destruída.

Falha na comunicação:

normalmente considera-se que são faltas temporárias e que é

possível recuperá-las, repetindo as mensagens;

partição física da rede, resultante de uma máquina, encaminhador

ou linha falharem e isolarem duas partes da rede.

Transações – Topologia de falhasTransações – Topologia de falhas



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Necessidade de sincronização das operações de leitura e escrita

deriva da propriedade de isolamento entre os componentes

participantes no sistema distribuído;

É necessário controlar a forma como os valores das variáveis são

vistas em outras transações, pois estas não poderão acender a

valores parciais, uma vez que a transação pode ainda abortar a

operação;

Transações – SincronizaçãoTransações – Sincronização



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


A sincronização do acesso a variáveis partilhadas é o problema

clássico de sincronização dos leitores/escritores em sistemas

distribuídos;

A execução de um conjunto de transações pode ser descrita por meio

de uma história que explicite a ordem relativa de execução das

operações das transações.

Transações – SincronizaçãoTransações – Sincronização



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


São Paulo, 2011São Paulo, 2011

Universidade Paulista (UNIP)Universidade Paulista (UNIP)

Conceitos Fundamentais e Convenções de Conceitos Fundamentais e Convenções de NotaçãoNotação

Prof. MSc. Vladimir CameloProf. MSc. Vladimir [email protected]



Documents

Sistemas Distribuídos Introdução a Sistemas Distribuídos 30/8/[email protected] São Paulo, 2011 Universidade Paulista (UNIP) Conceitos