Objetos Distribuídos Alcides Calsavara PUC-PR Mestrado em Informática Aplicada...

Objetos Distribuídos

Alcides Calsavara

PUC-PR

Mestrado em Informática Aplicada

alcides@epsilon.pucpr.br

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: alcides@newcastle.ac.uk

– 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