Embed Size (px)
Citation preview
Conteúdo
Revisão de sistemas distribuídos Revisão de orientacão a objetos CORBA
– IDL– Conceitos e elementos do padrão– Servicos– Facilidades e domínios– Comparacão com DCOM e DCE
Introdução a Sistemas Distribuídos
Módulo 1
[C1,T1.1,T1.2,T1.3,T1.4] (40 p.)
Conteúdo
Caracterização de SD Exemplos de SD Objetivos de SD Conceitos de hardware em SD Conceitos de software em SD Histórico
Definição de SD
"Um sistema distribuído é uma coleção de computadores autônomos conectados por uma rede e equipados com um sistema de software distribuído." [C]
"Um sistema distribuído é uma coleção de computadores independentes que aparenta ao usuário ser um computador único." [T]
Outra definição de SD
"Você sabe que tem um sistema distribuído quando a falha de um computador do qual você nunca ouviu falar faz com que você pare completamente de trabalhar." [Leslie Lamport]
Avanços tecnológicos
Invenção de redes de computadores de alta velocidade (anos 70):– Rede local (Local Area Network - LAN)– Rede global (Wide Area Network - WAN)
Desenvolvimento de microprocessadores potentes (anos 80).
Estado da arte
É relativamente fácil agrupar um grande número de CPUs, conectando-as por uma rede de alta velocidade.
O software para sistemas distribuídos é completamente diferente do software para sistemas centralizados e está apenas começando a se desenvolver.
Exemplos de SD
Uma rede de estações de trabalho em uma universidade ou companhia
Uma rede de computadores em uma fábrica
Um grande banco com muitas agências, cada qual com um computadores e caixas automáticas
Exemplos de SD (continuação)
Sistema de reserva de passagens aéreas
Sistema de controle de estoque, vendas e entregas numa cadeia de lojas
Serviços da Internet: Netnews, WWW Sistemas de acesso a recursos de
multimídia e de conferência
Vantagens de SD sobre SC
Melhor relação custo/benefício Capacidade de processamento além dos
limites práticos de SC (velocidade da luz, aquecimento)
Maior domínio de aplicações Maior confiabilidade e disponibilidade Crescimento gradativo da capacidade de
processamento
Vantagens de SD sobre PCs independentes Compartilhamento de dados comuns
entre usuários Compartilhamento de recursos de
hardware e software Comunicação entre pessoas Flexibilidade na distribuição de tarefas
de acordo com as aplicações
Desvantagens de SD
Falta de software adequado Falhas e saturação da rede de
comunicação podem eliminar as vantagens de SD
Segurança pode ser comprometida: fácil acesso a dados e recursos reservados
Hardware em SD
F ra ca m e n teA cop la do
F o r te m e n teA cop la do
S e qu en t,E n co re
B ar ram en to
U ltracom p ute r,R P 3
C h av ea m e n to
M ultip ro cessa d ores(m e m ó ria com pa rti lha da)
E s taçõ ese m um a L A N
B arram en to
H ype rcub e ,T ran sp u te r
C h av ea m e n to
M ulticom p u ta d ores(m em ó r ia s sep a ra da s)
C o m p uta do resd istr ibu ído s e p ara le los
Software básico em SD
Acoplamentode hardware
Acoplamentode software
Sistemas operacionais derede
Fraco Fraco
Sistemas distribuídos«autênticos»
Fraco Forte
Sistemas timesharingpara multiprocessadores
Forte Forte
Sistemas operacionais de rede
Estações de trabalho conectadas por uma LAN
Cada estação tem seu próprio sistema operacional
Ferramentas para login remoto e cópia de arquivos entre estações
Servidores de arquivos e ferramentas para causar aparência de arquivo local
Sistemas distribuídos autênticos
A rede toda tem aparência de ser um único sistema timesharing: virtual uniprocessor, single-system image
Mecanismo global para comunicação entre processos
Gerenciamento de processos homogêneo
Sistema de arquivos homogêneo
Sistemas timesharing para multiprocessadores Fila única de processos prontos para
execução: melhor distribuição de carga CPUs especializadas em: executar
processos, controlar periféricos, executar sistema operacional (gerenciar a memória global)
Sistema de arquivos comporta-se de maneira semelhante a um SC
Comparação de SW para SD
SO de rede SOdistribuído
SO paramultiproc.
Parece um SC Não Sim Sim
Mesmo SO Não Sim Sim
Cópias de SO N N 1
Comunicação Arquivoscompartilhados
Mensagens Memóriacompartilhada
Protocoloscomuns
Sim Sim Não
Fila única deexecução
Não Não Sim
Características básicas de SD
Compartilhamento de recursos Extensibilidade (openness) Concorrência Escalabilidade (crescimento gradativo
suave) Tolerância a falhas Transparência
Compartilhamento de recursos
Componentes de hardware: discos, impressoras, ...
Componentes de software: arquivos, bancos de dados, ...
Modelos básicos:– Modelo cliente-servidor– Modelo baseado em objetos
Extensibilidade
Extensões de hardware: periféricos, memória, interfaces de comunicação, ...
Extensões de software: funções de SO, protocolos de comunicação, ...
Interfaces chaves são públicas (system calls)
Mecanismo uniforme de comunicação entre processos
Concorrência
Mais de um processo em execução a cada instante:– Atividades separadas de usuários– Independência de recursos– Localização de processos servidores em
computadores distintos Acesso concorrente a recursos
compartilhados requer sincronização
Escalabilidade
Quantidade de trabalho envolvido no processamento de qualquer requisição de acesso a um recurso compartilhado independe do tamanho da rede
Técnicas: replicação, caching, servidores múltiplos
Tolerância a falhas
Falhas de hardware e software (em CPUs e redes): programas param ou produzem resultados errados
Abordagens:– Redundância de hardware (Ex: banco de
dados replicado em diversos servidores)– Recuperação por software: manter dados
permanentes sempre consistentes
Transparência
Esconder do usuário e do programador de aplicações a separação de componenentes em um sistema distribuído, tal que este seja visto como um sistema centralizado
Formas de transparência: acesso, localização, concorrência, replicação, falha, migração, desempenho e escala
Transparência de acesso
Operações de acesso a objetos deinformação são idênticas para objetoslocais e remotos
Exemplo:Operação de envio de uma mensagemeletrônica especificando o destinatárioatravés de seu endereço Internet
Transparência de localização
Acesso a um objeto ocorre sem que sejanecessário o conhecimento de sualocalização
Exemplo:Operação de envio de uma mensagemeletrônica especificando o destinatárioatravés de seu endereço Internet
Outras formas de transparência
Concorrência: processos operam concorrentemente usando objetos de informação comuns sem interferência entre eles.
Replicação: várias instâncias de um objeto de informação são usadas sem requerer o conhecimento das réplicas pelos usuários e aplicações.
Falha: mascaramento de falhas de hardware e software. Migração: movimento de objetos de informação dentro do
sistema não afeta a operação de usuários e aplicações. Desempenho: reconfiguração do sistema para melhorar
desempenho conforme a carga varia. Escala: o sistema e as aplicações podem expandir em escala
sem requerer modificações na estrutura do sistema ou nos algoritmos das aplicações.
Metas de Projeto
Módulo 2
[C2,T1.5] (35 p.)
Propriedades críticas de um SD
Transparência Flexibilidade Confiabilidade Desempenho Escalabilidade
Transparência a paralelismo
Paralelismo: divisão de uma tarefa em sub-tarefas coordenadas e que são executadas simultaneamente em processadores distintos
Compilador, ambiente de execução e sistema operacional devem saber tirar vantagem do potencial paralelismo de um sistema distribuído sem mesmo que o programador saiba disso
Flexibilidade
Modelos de estrutura de SD:– Núcleo monolítico: inclui gerenciamento de
arquivos, diretórios e processos– Micro-núcleo:
• mecanismo para comunicação entre processos• gerenciamento básico de memória• gerenciamento de processos a baixo nível• operações de entrada/saído a baixo nível
Vantagens do micro-núcleo
Modularidade => Flexibilidade– serviços estão disponíveis a todos os
clientes, independentemente de localização
– serviços podem ser reparados sem causar parada total do sistema
– os próprios usuários podem adicionar novos serviços
Confiabilidade
Em teoria, como medir? Aspectos:
– disponibilidade: fração do tempo em que o sistema pode ser usado
– exatidão: replicação versus consistência– segurança: Como um servidor pode verificar a
origem de uma mensagem?– tolerância a falhas: replicação versus
desempenho
Desempenho
Métodos de medição:– tempo de resposta– número de tarefas por hora– taxa de utilização do sistema– taxa de utilização da rede
Fator crítico em SD: troca de mensagens
Granularidade de computação paralela
Escalabilidade
Evitar:– componentes centralizados (ex: um único
servidor de correio eletrônico para todos os usuários)
– tabelas centralizadas (ex: uma única lista telefônica on-line)
– algoritmos centralizados (ex: roteamento baseado em informação completa)
Algoritmos Distribuídos
Nenhuma máquina conhece o estado global
Decisões são baseadas somente em informação local
A parada de uma máquina não arruína o algoritmo
Não há qualquer suposição quanto a existência de tempo (relógio) global
Elementos básicos de um SD
Sistema de nomes Comunicação Estrutura de software Alocação de carga de trabalho Manutenção de consistência
Sistema de nomes
Nomes permitem que recursos sejam compartilhados
Nomes de recursos devem ser independendentes de sua localização
O esquema de nomes deve escalar bem Um sistema de interpretação de nomes
deve ser acessível por programa
Comunicação
O sucesso de um SD depende muito do desempenho/confiabilidade das técnicas de comunicação usadas em sua implementação
Dilema: otimizar implementação da comunicação e prover alto nível do modelo de programação dessa comunicação
Estrutura de software
Extensibilidade requer componenetes de software com interfaces bem definidas
Um serviço é um gerenciador de objetos de um certo tipo e sua interface é um conjunto de operações
Novos serviços devem interoperar com serviços existentes e não duplicar suas funções
Alocação de carga de trabalho
Otimização do uso de:– capacidade de processamento– capacidade de comunicação– recursos da rede em geral
Objetivo: bom desempenho
Manutenção de consistência
Consistência de atualização: atomicidade como meio de atualização instantânea de muitos elementos
Consistência de replicação: cópias de um mesmo recurso devem ser “idênticas”
Consistência de cache: modificações em um cliente devem ser propagadas ao gerenciador e aos demais clientes
Manutenção de consistência (continuação)
Consistência de falha: deve-se evitar falhas múltiplas (em cascata); isolamento de falhas
Consistência de relógio: relógios físicos (sincronização aproximada) e relógios lógicos (timestampings em mensagens)
Consistência de interface de usuário: atrasos devido a comunicação podem causar visão inconsistente de aplicações gráficas
Requisitos a nível de usuário
Funcionalidade: Que serviços esperar de um SD? Como migrar aplicações de um SC para um SD (adaptar SO, adaptar applicação, emulação de SO antigo)?
Reconfigurabilidade: substituição de máquinas que falham, rearranjo de carga, transferência de atividades e dados para minimizar comunicação
Requisitos a nível de usuário(continuação)
Qualidade de serviço:– desempenho– confiabilidade e disponibilidade– segurança
Comunicação emSistemas Distribuídos
Módulo 3[C4,C5,T2.3,T2.4,T2.5](120 p.)
Conteúdo
Elementos básicos de comunicação– Transmissão de dados– Endereçamento– Sincronismo– Enfileiramento (Bufferização)– Confiabilidade
Comunicação cliente-servidor Comunicação em grupo Chamada remota de procedimento
Transmissão de dados
Dados em programas são estruturados enquanto que mensagens carregam informação sequencial:
» Linearização/Restauração de dados Heterogeneidade na representação de dados
em computadores:
» Uso de um formato externo comum
» Inclusão de uma identificação de arquitetura na mensagem
Marshalling/Unmarshalling
Marshalling:– Linearização de uma coleção de itens de
dados estruturados– Tradução dos dados em formato externo
Unmarshalling:– Tradução do formato externo para o local– Restauração dos itens de dados de acordo
com sua estrutura
Endereçamento Esquemas:
– Endereçamento máquina.processo– Endereçamento máquina.id-local– Descoberta de endereço via broadcasting
(difusão)– Descoberta de endereço via um servidor de
nomes Problemas: transparência de localização,
sobrecarga, escalabilidade
Comunicação síncrona
Primitiva send é bloqueante: processo cliente aguarda enquanto o núcleo envia a mensagem para o processo servidor.
Primitiva receive é bloqueante: processo servidor aguarda até que o núcleo receba uma mensagem endereçada a aquele processo.
Comunicação assíncrona Primitiva send não é bloqueante: o processo
cliente aguarda somente enquanto a mensagem é copiada para o buffer do núcleo.
Primitiva receive pode ser:– bloqueante: o processo servidor aguarda
por uma mensagem.– não bloqueante: o processo servidor
simplesmente comunica o núcleo que espera receber uma mensagem.
Enfileiramento Situações:
– Send ocorre antes de Receive– Um cliente faz um Send enquanto o servidor
ainda atende a outro cliente Solução trivial: clientes devem insistir ... Solução pragmática: mailbox (uma fila de
mensagens controlada pelo núcleo):– mailbox criado a pedido do servidor– mensagens endereçadas ao mailbox
Confiabilidade
Mensagens se perdem, atrasam, duplicam. Abordagens:
– Send tem semântica não confiável: as aplicações devem garantir entrega de mensagens (ex: timeout)
– Mensagem de acknowledgement enviada pelo servidor (a nível de núcleo)
– Mensagem de acknowledgement implícita na resposta do servidor
Comunicação cliente-servidor
Cliente
Núcleo Núcleo
Rede
Requisição
RespostaServidor
Requisição/Resposta
1
2
3
4
5
6
7
Enlace
Físico
Pacotes em protocolo C-S
Código Tipo De Para Descrição
REQ Request C S O cliente deseja umserviço
REP Reply S C Resposta do servidor parao cliente
ACK Ackowledgment x y O pacote anterior chegou
AYA Are you alive? C S Investiga de o servidornão parou
IAA I am alive S C O servidor não parou
TA Try again S C O servidor está lotado
AU Address unknown S C Nenhum processo estáusando aquele endereço
Comunicação em grupo
ER R
R
R
R R
R R
E
R
Processo que envia mensagem
Processo que recebe mensagem
Tolerância a falhas baseada na replicação de serviços
Localização de objetos em serviços distribuídos
Melhor desempenho via replicação de dados
Múltipla atualização
Tipos de grupos Visibilidade:
– Aberto: um processo fora do grupo consegue enviar mensagens para o grupo todo
– Fechado: somente processos do grupo enviam mensagens para o grupo todo
Organização:– Peer: todos os processos tomam decisão– Hierárquico: decisão é centralizada
Endereçamento de grupo
Multicast: um processo envia uma mensagem simultânea e somente para os membros do grupo.
Broadcast: um processo envia uma mensagem para todas as máquinas e somente as que contêm um membro do grupo a assimila.
Unicast: um processo envia uma mensagem para todos os membros do grupo em série.
Modificações no grupo
Controle centralizado: servidor de grupo Controle descentralizado: acordo entre
os membros Operações:
– Entrada de um membro: atualizar estado– Saída de um membro: se involuntária (ex:
parada), todos os membros restantes devem notar sua saída.
Primitivas de comunicação
GroupSend: envia mensagem para todos os membros do grupo
GroupReceive: aguarda mensagem enviada a todo o grupo
GetReply: aguarda resposta de todos os membros do grupo após um GroupSend
Atomicidade
Uma mensagem enviada ao grupo deve ser recebida por todos os seus membros ou por nenhum deles.
Situação: o enviador pode parar enquanto está enviando a mensagem para o grupo.
Garantia de consistência do grupo Facilidade de programação
Ordenação de mensagens
Todas as mensagens enviadas a um grupo devem chegar a todos os processos na mesma ordem.
Abordagens:– Ordenação por tempo global– Ordenação por tempo consistente:
somente uma mensagem por vez é difundida
Chamada de Procedimentos Remotos (RPC)
Comunicação no modelo cliente-servidor é baseada em operações de entrada/saída: abstração fraca, sujeito a erros
Ideal: programar um SD como se fosse um SC
RPC objetiva permitir chamada de procedimento remoto como se fosse local, ocultando entrada/saída de mensagens
Visão geral
Um processo A chama um procedimento p de um processo B, entrando em estado de espera
O processo B passa a executar o procedimento p, e ao seu término faz um reply para o processo A
O processo A volta à sua execução normal após ter recebido o reply
Chamadas de procedimento
O procedimento chamador, que já tem suas variáveis locais empilhadas, empilha os parâmetros da chamada e o endereço de retorno
O procedimento chamado aloca sua variáveis locais
No retorno do procedimento chamado, os parâmetros e o endereço de retorno são desempilhados
Modos de parâmetros Valor: procedimento chamado recebe uma cópia
de uma variável conhecida do procedimento chamador
Referência: procedimento chamado recebe o endereço de uma variável conhecida do procedimento chamador
Cópia/Reescrita: procedimento chamador recebe uma cópia de uma variável conhecida do procedimento chamador e o valor desta cópia é reescrito na variável
Funções dos Stubs Client stub
– intercepta a chamada– empacota os parâmetros (marshalling)– envia mensagem de request ao servidor (através do núcleo)
Server stub– recebe a mensagem de request (através do núcleo)– desempacota os parâmetros (unmarshalling)– chama o procedimento, passando os parâmetros– empacota o resultado– envia mensagem de reply ao cliente (através do núcleo)
Client stub– recebe a mensagem de reply (através do núcleo)– desempacota o resultado– passa o resultado para o cliente
Falhas em RPC
O cliente não é capaz de localizar o servidor A mensagem de request do cliente para o
servidor é perdida A mensagem de reply do servidor para o
cliente é perdida O servidor pára após ter recebido a
mensagem de request O cliente pára após ter enviado a mensagem
de request
Falha do servidor Passos normais:
– recebe mensagem de request– executa procedimento– envia mensagem de reply
Falha pode ocorrer:– após a execução– antes da execução
Semânticas de chamada:– pelo menos um– no máximo um– exatamente um
Falha do cliente
O servidor torna-se um “órfão” Soluções:
– exterminação do servidor pela máquina do cliente– reencarnação do cliente: toda computação remota
é destruída– reencarnação suave do cliente: somentes as
computações remotas referentes aquele cliente são destruídas
– expiração: servidor estabele um timeout para confirmação
Sincronização em Sistemas Distribuídos
Módulo 4
[C10,C13,T3]
Conteúdo
Relógios lógicos Relógicos físicos Exclusão mútua Algoritmos de eleição
Eventos e relógios
A ordem de eventos que ocorrem em processos distintos pode ser crítica em uma aplicação distribuída (ex: make, protocolo de consistência de réplicas).
Em um sistema com n computadores, cada um dos n cristais terá uma frequência própria, fazendo com que os n relógios percam seu sincronismo gradualmente.
Relógios lógicos
Princípios:1. Somente processos que interagem precisam
sincronizar seus relógios.
2. Não é necessário que todos os processos observem um único tempo absoluto; eles somente precisam concordar com relação à ordem em que os eventos ocorrem.
» Ordenação parcial de eventos
» Ordenação causal potencial
Relógios lógicos (cont.) Relação acontece-antes ( -» ):
1. Sejam x e y eventos num mesmo processo tal que x ocorre antes de y. Então x -» y é verdadeiro.
2. Seja x o evento de uma mensagem ser enviada por um processo, e y o evento dessa mensagem ser recebida por outro processo. Então x -» y é verdadeiro.
3. Sejam x, y e z eventos tal que x -» y e y -» z. Então x -» z é verdadeiro.
Relógios lógicos (cont.)
Eventos ocorrendo em três processos:
p1
p2
p3
a b
c d
e f
m1
m2
TempoFísico
Os processos "a" e "e" são concorrentes: a || e
a -» b, c -» d, e -» f, b -» c, d -» f
a -» f
Relógios lógicos (cont.) Implementação: Cada processo p mantém seu próprio
relógio lógico (um contador, por software), Cp, usado para fazer timestamp de eventos. Cp(x) denota o timestamp do evento x no processo p, e C(x) denota o timestamp do evento x em qualquer processo.
LC1: Cp é incrementado antes de cada evento em p.
LC2: (a) Quando um processo p envia uma mensagem m, ele concatena a informação t=Cp a m, enviando (m,t).
(b) Quando um processo q recebe a mensagem (m,t), ele computa Cq := max(Cq, t) e aplica LC1 antes de fazer timestamp do evento de recebimento da mensagem.
Relógios lógicos (cont.) Ordenação total de eventos: dois eventos nunca
ocorrem exatamente no mesmo instante de tempo.
1. Se x ocorre antes de y no mesmo processo, então C(x) é menor que C(y).
2. Se x e y correspondem ao envio e ao recebimento de uma mensagem, então C(x) é menor que C(y).
3. Para todos os eventos x e y, C(x) é diferente de C(y).
Implementação: concatenar o número do processo ao timestamp.
Relógios físicos 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ógios físicos (cont.)
Algoritmo de Cristian:– A rede dispõe de um time server (receptor WWV)– Uma máquina cliente envia uma mensagem pedindo
a hora certa ao time server– Ao receber a mensagem resposta do time server, o
cliente adiciona o tempo médio de envio de mensagens à hora recebida. Esse tempo médio é calculado pelo próprio cliente considerando as horas de envio e recebimento das mensagens e ainda o tempo gasto pelo time server para processar o pedido.
Relógios físicos (cont.)
Algoritmo de Berkeley:– A rede não dispõe de uma máquina com um receptor
WWV– A rede dispõe de um time server que faz polling nas
outras máquinas a fim de obter a hora marcada por cada uma, fazer uma média entre essas horas e divulgar essa média para todas as máquinas.
NTC: Network Time Protocol– Sub-rede hierárquica de sincronização– Servidores primários (WWV) e secundários
Exclusão mútua Controle de acesso a regiões críticas Algoritmo centralizado:
– Um processo é eleito o coordenador– Os processos concorrentes devem requisitar permissão
de acesso ao coordenador– Um processo que termina de fazer acesso a uma região
crítica deve comunicar a liberação da região ao coordenador
– Processos que tentam entrar em uma região crítica ocupada devem aguardar em uma fila controlada pelo coordenador
Exclusão mútua (cont.) Algoritmo distribuído:
– Baseado em ordenação total de eventos e comunicação confiável em grupo (multicast ou broadcast).
– Um processo que deseja entrar em uma região crítica constrói uma mensagem com o nome da região, o número do processo e a hora, e a envia a todos os demais processos concorrentes.
– Um processo que recebe a mensagem:• Caso não esteja na região crítica e não intencione entrar nela,
retorna OK.• Caso já esteja na região crítica, não responde e enfileira a
requisição.• Caso também intencione entrar na região crítica, determina o
processo que tentou primeiro (comparando timestamps) e responde OK ou enfileira a requisição, apropriadamente.
Exclusão mútua (cont.)
Algoritmo de Token Ring:– Os processos são conectados por um anel e
numerados sequencialmente a partir de 0.– Na iniciação do anel, uma token é dada ao processo 0.– A token é passada do processo k para o processo k+1.– Ao receber a token, um processo pode retê-la ou passá-
la imediatamente para o próximo processo, dependendo se deseja ou não, respectivamente, entrar na região crítica. Enquanto o processo estiver na região crítica, a token fica retida, e somente ao sair da região crítica é repassada adiante.
Algoritmos de eleição
Eleição de um processo coordenador em algoritmos distribuídos
Algoritmo Bully:1. Um processo P envia uma mensagem ELECTION
para todos os processos de maior número.
2. Se nenhum processo responde, P vence a eleição e se torna o coordenador.
3. Se um dos processos responde este inicia sua participação na eleição a partir do passo 1. O trabalho de P está feito.
Algoritmos de eleição (cont.)
Algoritmo de Anel:– Um processo constrói uma mensagem ELECTION
contendo seu número e envia ao seu sucessor. Se o sucessor estiver parado, a mensagem é enviado ao sucessor do sucessor.
– O processo que recebe a mensagem insere seu próprio número na mensagem e passa para o seu sucessor.
– Quando a mensagem retorna ao processo que originou a eleição, este descobre quem é novo coordenador (o processo com número maior) e, em seguida, envia uma mensagem COORDINATOR comunicando o fato.
90
Tolerância a falhas
Módulo 5
[C11,C15,T4.5] (65 p.)
91
Conteúdo Falhas
– tipos– tempo médio até falhar– em processadores
Uso de redundância– tipos– replicação ativa– replicação primary backup
Consenso na presença de falhas
92
Falhas
Um sistema falha quando não funciona de acordo com sua especificação.
Falhas típicas:– hardware: processador, memória, dispositivo de E/S,
cabo, ...– software: erros de programação, erros de operação,
situações não previstas, ... Objetivo de tolerância a falhas: garantir que um sistema
continue a funcionar corretamente na presença de defeitos. Tolerância a falhas é necessária principalmente em
aplicações que requerem alta disponibilidade.
93
Tipos de falhas
Falha transiente: ocorre apenas uma vez; se a operação é repetida, a falha desaparece. Exemplo: falha numa transmissão usando micro-ondas porque algum objeto obstrui temporariamente.
Falha intermitente: ocorre de maneira aleatória e imprevisível. Exemplo: um conector com mau contato.
Falha permanente: ocorre sempre até que o componente seja substituído. Exemplo: um chip queimado, erros em software.
94
Tempo médio até falhar Exemplo:
– Um componente tem uma probabilidade p de falhar em um segundo.
– A probabilidade desse componente não falhar em k segundos consecutivos é
– O tempo estimado até esse componente falhe (mean time to failure) é
– Assim, se p = 0.001 então MTF = 1000 segundos.
95
Falhas em processadores
Tipos:– Fail-silent fault (ou Fail-stop fault): um
processador com falha pára e não responde a subsequentes requisições ou produz qualquer resultado.
– Byzantine fault: um processador com falha continua a operar, emitindo resultados errados, possivelmente em acordo com outros processadores com falha, causando a impressão de que estão todos funcionando normalmente.
96
Uso de redundância
Tipos de redundância:– Redundância de informação: bits extras são
adicionados para se recuperar de bits errados.
– Redundância de tempo: uma ação é executada e, se necessário, é executada novamente. (Útil para falhas transientes e intermitentes.)
– Redundância física: equipamento extra é adicionado para que o sistema como um todo tolere a falha de um ou outro componente. Exemplo: múltiplos processadores.
97
Uso de replicação ativa
Todos os processadores são usados o tempo todo como servidores (em paralelo) a fim de ocultar falhas completamente.
TMR: Triple Modular Redundancy Sistema tolerante a falhas no nível k: satisfaz sua
especificação mesmo se até k componenetes falharem simultaneamente:– fail-silent fault: requer k+1 componenetes – byzantine fault: requer 2k+1 componentes
Requisito: todas as requisições chegam nos servidores numa mesma ordem (atomic broadcast problem).
98
Uso de primary backup Apenas um processador (primary) é o servidor a cada
instante. Se este falhar, um outro processador (backup) é ativado para operar em seu lugar.
A substituição de um processador por outro não deve ser notada pelas aplicações; somente o sistema operacional do cliente deve notar.
Vantagens:– Mais simples: mensagens do cliente vão para apenas
um servidor (não é necessário ordenar mensagens).– Na prática, requer menos máquinas.
Desvantagem: não funciona se para Byzantine faults.
99
Consenso na presença de falhas
Exemplos: eleição de um coordenador, decisão quanto a fazer ou não commit de uma transação, divisão de tarefas.
Primeiro caso: processadores confiáveis, mas possíveis falhas de comunicação. Exemplo: two-army problem.
Consenso é impossível sem comunicação confiável! Segundo caso: comunicação confiável, mas possíveis
falhas de processadores. Exemplo: Byzantine generals problem.
Consenso é possível quando há m processadores confiáveis somente se houver 2m+1 processadores
confiáveis.
100
Transações Atômicas Distribuídas
Módulo 6
[C12,C13,C14,T3.4] (110 p.)
101
Conteúdo
Armazenamento em memória estável Primitivas de transação Propriedades de transações Transações encaixadas Implementação de transações
– Espaço de trabalho privado
– Log
– Protocolo de commit em duas fases Controle de concorrência
– Locking
– Controle otimista
– Timestamps
102
Transações em SD
Abstração em alto nível para ocultar:– uso de semáforos para controle de concorrência– prevenção de deadlocks– recuperação de falhas
Vantagem: programadores concentram-se nos algoritmos das aplicações.
Sinônimos: atomic transaction, transaction, atomic action.
103
Exemplo de transação
Um cliente, em um PC ligado por modem, faz transferência de fundos de uma conta bancária para outra, em dois passos:
(1) Saque(quantia, conta1)
(2) Deposite(quantia, conta2) Se a ligação telefônica cair entre os passos (1) e (2) o
dinheiro desaparece! Solução: passos (1) e (2) devem ocorrer como uma
transação atômica (como se fosse um único passo); se a ligação telefônia cair entre os passos (1) e (2), os efeitos do passo (1) devem ser cancelados.
104
Memória estável
Informação armazenada em RAM é perdida se faltar energia ou se a máquina falhar.
Informação armazenada em disco é perdida se a cabeça do disco falhar.
Informação armazenada em memória estável sobrevive a tudo, exceto enchentes, terremotos, ...
Implementação típica: disco replicado.
105
Primitivas de transação
BEGIN_TRANSACTION: marca o início da transação END_TRANSACTION: termina a transação e tenta
fazer o commit ABORT_TRANSACTION: destrói a transação;
restaura os valores anteriores (do início da transação)
READ: lê dados de um objeto (por exemplo, um arquivo)
WRITE: escreve dados em um objeto
106
Exemplos de primitivas
BEGIN_TRANSACTION
reserve São Paulo - Salvador
reserve Salvador - Brasília
reserve Brasília - São Paulo
END_TRANSACTION
BEGIN_TRANSACTION
reserve São Paulo - Salvador
reserve Salvador - Brasília
reserve Brasília - São Paulo => ABORT_TRANSACTION
107
Propriedades de transações:ACID
Atômica: para o mundo externo, a transação ocorre de forma indivisível.
Consistente: a transação não viola invariantes de sistema.
Isolada: transações concorrentes não interferem entre si (serializable).
Durável: os efeitos de uma transação terminada com commit são permanentes.
108
Isolamento ou serializabilidade
BEGIN_TRANSACTIONx = 0;x = x + 1;
END_TRANSACTION
BEGIN_TRANSACTIONx = 0;x = x + 2;
END_TRANSACTION
BEGIN_TRANSACTIONx = 0;x = x + 3;
END_TRANSACTION
109
Escalonamentos (schedules)
Escalon. 1 Escalon. 2 Escalon. 3
x = 0; x = 0; x = 0;x = x + 1; x = 0; x = 0;x = 0; x = x + 1; x = x + 1;x = x + 2; x = x + 2; x = 0;x = 0; x = 0; x = x + 2;x = x + 3; x = x + 3; x = x + 3;
Legal Legal Ilegal
110
Transações encaixadas
A transação top-level cria sub-transações que executam em paralelo, em processadores distintos: melhor desempenho e programação mais simples.
Se uma transação top-level abortar, então todas as suas sub-transações também devem abortar.
Uma sub-transação herda todos os objetos controlados pela transação top-level.
Uma sub-transação faz cópia local de todos os objetos herdados e só repassa os novos valores destes objetos à transação top-level em caso de commit da sub-transação.
111
Implementação de transações
Métodos de controle sobre modificações:– Espaço de trabalho privado– Log
Protocolo de commit em duas fases
112
Espaço de trabalho privado
Um processo que começa uma transação cria um espaço contendo cópias de todos os objetos manipulados pela transação.
Se ocorrer commit, a transação repassa os novos valores dos objetos para os seus originais.
Problema: alto custo! Otimização: shadow blocks
113
Log Writeahead log ou intentions list Os objetos originais são modificados durante a transação Antes de cada modificação, um registro é escrito em um
arquivo de log (em memória estável) Cada registro de log informa o valor anterior e o valor novo
de um objeto, além de informar que transação fez a modificação no objeto
Se ocorrer commit um registro apropriado é inserido no log Se ocorrer abort todas as operações efetuadas pela
transação são desfeitas com base no log, começando pelo último registro (rollback)
114
Log : exemplo
x = 0;y = 0;BEGIN_TRANSACION
x = x + 1;y = y + 2;x = y * y;
END_TRANSACION
Log
x = 0/1y = 0/2x = 1/4
115
Protocolo de commit em duas fases A ação de commit deve ser “instantânea” e indivisível Pode ser necessária a cooperação de muitos
processos, em máquinas distintas, cada qual com um conjunto de objetos envolvidos na transação
Um processo é designado como o coordenador (normalmente o próprio cliente que inicia a transação)
Os demais processos são designados como subordinados
Toda ação é registrada em log, armazenado em memória estável, para o caso de falha durante a transação.
116
O protocolo Fase 1:
– O coordenador registra “prepare” em log e envia a mensagem “prepare” para os subordinados
– Um subordinado registra “ready” / “abort” em log e envia a mensagem “ready” / “abort” para o coordenador
– O coordenador coleta todos as mensagens “ready” Fase 2:
– O coordenador registra a decisão em log e envia mensagem “commit” / “abort” para os subordinados
– Um subordinado registra “commit” / “abort” em log, toma a ação correspondente e envia mensagem “finished” ao coordenador
117
Controle de concorrência
Locking– Um gerente centralizado ou distribuído registra todos os locks e
rejeita pedidos de lock em objetos já alocados a outros processos– lock para escrita deve ser exclusivo, mas lock para leitura pode
ser compartilhado– Quanto menor a granularidade do lock maior a chance de
paralelismo, mas também maior é a chance de deadlock– Lock em duas fases:
• growing: todos os locks são adquiridos
• shrinking: todos os locks são liberados– Strict two-phase locking: a fase shrinking ocorre
“instantaneamente” (previne cascade aborts)
118
Controle de concorrência (cont.)
Controle otimista– Os objetos são modificados sem preocupação
com concorrência até o fim da transação
– Quando chegar o momento de commit, a transação verifica se outra transação modificou os mesmos objetos que ela tenha modificado
– Se não há conflito, então o commit é feito (repasse de objetos do espaço de trabalho privado), senão é feito um abort
119
Controle de concorrência (cont.)
Timestamps– Cada transação recebe um timestamp único em seu
início– Cada objeto no sistema tem um read timestamp e um
write timestamp, dizendo que transação fez a operação
– Se transações são “curtas” e “espaçadas” no tempo, normalmente, quando uma transação fizer acesso a um objeto, os timestamps do objeto serão mais velhos que o timestamp da transação. Caso contrário a transação está “atrasada” e deve ser abortada.
120
Sistemas de Nomes
Módulo 7
[C9] (30 p.)
121
Conteúdo Nomes em SD e seus tipos Binding Atributos de objetos Serviço de nomes Nomes hierárquicos Conceitos para implementação de um serviço de nomes Um exemplo teórico de serviço de nomes Resolução de nomes Servidores e navegação Estudo de caso: DNS
122
Nomes em sistemas distribuídos Nomes designam recursos:
– computadores
– serviços
– portas
– objetos de informação (ex: página WWW)
– usuários Nomes são necessários para:
– comunicar e compartilhar recursos
– requisitar um sistema agir sobre um recurso
– permitir comunicação entre usuários
123
Tipos de nomes Tipos básicos de nomes:
– nomes textuais: usados por humanos para reconhecer e memorizar nomes de recursos; nome legíveis
– identificadores de sistema: usados devido a eficiência no seu armazenamento e resolução por software; nomes não necessariamente legíveis
Escopos de nomes:– específico de um serviço: nome de um arquivo, número
de um processo– independente de serviços: nomes de usuários, endereço
e-mail, nomes de computadores, nomes de serviços
124
Exemplo: Sistema Amoeba
/users/smith/prog.c
Nome textual do arquivo
164997 9
2:60:8c:2:b0:5a
arquivo
Id Recurso (Id Porta, Id Espec. Serviço)
Endereço de redeServidor
125
Tipos de atributos de objetos
Valores primitivos, como números inteiros, strings, ... Nomes, os quais também devem ser resolvidos (ex:
um endereço Internet)
A resolução de um nome termina com um valor primitivo ou com um nome primitivo (nome que não pode mais ser traduzido, como por exemplo, um endereço Internet)
126
Serviço de nomes
Armazena um banco de dados de bindings entre um conjunto de nomes textuais e atributos de objetos que existem independentemente de serviços
Operações básicas de um serviço de nomes:– resolve: recupera os atributos de um objeto a
partir de um dado nome– bind: cria um binding entre um nome e um
conjunto de atributos– delete: destrói um binding– list: mostra os bindings existentes
127
Serviço de nomes: motivação
Unificação: permite que recursos gerenciados por servidores (ou serviços) distintos apareçam sob um mesmo esquema de nomes. Ex: arquivos locais e remotos em Unix com NFS aparecem sob a mesma
hierarquia de nomes. Integração: permite o compartilhamento de recursos
criados em espaços administrativos distintos. Ex: integração de dois conjuntos de usuários.
128
Serviço de nomes: requisitos
Gerenciar um número arbitrário de nomes e servir a um número arbitrário de organizações. Ex: gerenciar todos os cndereços eletrônicos do mundo.
Tempo de vida longo: resistir a mudanças nas organizações de nomes e nos componentes que implementam o serviço.
Alta disponibilidade Isolamento de falhas Tolerância a enganos (mistrust): não pode haver um
único componente considerado como “confiável” por todos os clientes do sistema.
129
Nome hierárquico
.cs.distrib.gene
componentes
Prefixo
Prefixo
130
Nomes: conceitos Espaço de nomes: conjunto de nomes válidos segundo
alguma convenção. Em um nome hierárquico, cada componente em um prefixo
define um diretório => escalabilidade Um espaço de nomes flat, isto é, sem organização
hierárquica de diretórios, depende de um gerenciamento central => não escala
Um alias é um sinônimo para um nome hierárquico, definido com o objetivo de facilitar a memorização do nome. Ex: Um alias para .cs.distrib.gene podia ser .gene; um alias para .cs.distrib.gene.parallel podia ser .gene.parallel
131
Nomes: conceitos (cont.) Nome puro: não incorpora qualquer informação sobre
configuração física, como a localização do objeto Nomes fisicamente particionados: têm o formato
NomeDeObjeto@NomeDeServidor. Vantagem: não é necessário descobrir o servidor para então descobrir o objeto. Desvantagem: qualquer alteração de servidor invalida nomes em cache, replicados
Nomes organizacionalmente particionados: refletem estrutura administrativa, como departamentos, divisões, ... Ex: .pucpr.ccet.di, .pucpr.ccet.ee, .pucpr.ccbs.med. Vantagem: administração decentralizada. Desvantagens: (1) sujeito a mudanças; (2) requer proteção contra “enganos”.
132
Nomes: conceitos (cont.)
Domínio de nomes: um espaço de nomes para o qual existe apenas uma autoridade administrativa para a atribuição de nomes dentro dele.
Dominíos podem ser encaixados: sub-domínios A autoridade responsável por um domínio delega
responsabilidades às autoridades de seus sub-domínios, tal que a autoridade responsável por cada sub-domínio tem autonomia para atribuição de nomes dentro do sub-domínio.
133
Armazenamento de atributos: um exemplo
Tipo Atributos
User login name, computador, telefone, ...Service address, versionComputer architecture, operating system, network addres,
ownerGroup name1, name2, ...Alias nameDirectory nameComponent1, nameComponent2, ...
134
Operações de um serviço de nomes: um exemplo
Bind (accessId: Permissions, name: Text, attr: Attributes)-> {Success, NotAllowed, AlreadyBound, NoDirectory}
Lookup (name: Text, type: Int, attr: Attributes)-> {Success, NotFound}
Unbind (accessId: Permissions, name: Text)-> {Success, NotFound, NotAllowed, DirectoryNotEmpty}
135
Resolução de nomes
Resolução de um nome: encontrar a entrada de um nome a fim de obter os atributos associados a este nome.
Contexto de nomes: uma abstração que mapeia um nome a um conjunto de atributos diretamente, ou que mapeia para outro contexto. Exemplo: diretórios em um nome hierárquico.
A resolução de um nome requer um contexto inicial; um processo iterativo percorre os contextos intermediários até se chegar ao contexto onde o nome está mapeado para atributos.
136
Servidores e navegação Um serviço de nomes pode ser implementado por um
conjunto de servidores; normalmente um servidor para cada diretório da hierarquia do espaço de nomes. Vantagens: autonomia, tolerância a falhas, escalabilidade.
Navegação: o processo de descobrir informação entre diversos servidores a fim de resolver um nome
Implementação típica: uso de user agents e cache– cada máquina possui um user agent (UA)– o cliente faz lookup de nomes através de seu UA– o UA resolve o máximo de prefixos usando seu cache– quando o servidor do diretório final é encontrado, o nome
é resolvido por aquele servidor
137
Estudo de caso: DNS
DNS: Domain Name System Armazena nomes de qualquer tipo de objeto; na
prática, nomes de computadores são mapeados para endereços IP
Objetivos: escalabilidade, autonomia das organizações, generalidade (qualquer tipo de objeto)
Nomenclatura própria:– domain: corresponde a domínio de nomes– domain name: corresponde a nome
Exemplos de nome: www.pucpr.br, newcastle.ac.uk
138
DNS (cont.) Domínios de topo:
– Por tipo de organização:• com : organizações comerciais
• edu : universidades e instituições de educação
• gov : agências do governo
• mil : organizações militares
• net : grandes centros de suporte a rede
• org : outras organizações
• int : organizações internacionais
– Por país:• us : United States
• uk : United Kingdom
• fr : France
139
DNS (cont.) Queries:
– Host name resolution: dado o nome de um computador, obtém-se o seu endereço IP. Este tipo de operação é usado pelo ftp. Exemplo: epsilon.ccet.pucpr
– Mail host location: software de correio eletrônico usa o DNS para resolver nomes em endereços IP de computadores que aceitam mail. Exemplo: [email protected]
– Reverse resolution– Host information– Well known services
140
DNS (cont.)
Servidores de nomes:– DNS usa uma rede de servidores– Uso intensivo de replicação e cache– Cada servidor armazena parte da base de dados
e informação sobre outros servidores– Uma zona é uma divisão lógica do espaço de
nomes, contendo informação sobre suas sub-zonas
– Cada servidor armazena dados referentes a uma ou mais zonas
![Transações Atômicas Distribuídas1 Alcides Calsavara [C12,C13,C14,T3.4] (110 p.)](https://img.document.onl/doc/110x75/552fc105497959413d8c037d/transacoes-atomicas-distribuidas1-alcides-calsavara-c12c13c14t34-110-p.jpg)
