Sistemas Distribuídos - Notas De Aula
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Sistemas Distribuídos - Notas De Aula as PDF for free.
More details
- Words: 15,373
- Pages: 46
Notas de aula - Sistemas Distribuídos e de Redes
Ricardo Jurczyk Pinheiro - Faculdades Paraíso Versão atual: 16/03/07
Sumário 1 Sistemas com várias UCPs: Hardware 1.1
1.2
Questões atuais . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.1.2
Soluções propostas . . . . . . . . . . . . . . . . . . . . . . . .
4
Arquitetura de máquinas paralelas
1.2.2
. . . . . . . . . . . . . . . . . . .
4
Multiprocessador . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2.1.1
SMP (Multiprocessamento Simétrico)
5
1.2.1.2
NUMA (Acesso Não-Uniforme à Memória)
. . . . . . . . . . . . .
Multicomputador . . . . . . . . . . . . . . . . . . . . . . . . .
Comparativo entre os sistemas
. . . . . . . . . . . . . . . . . . . . .
2 Sistemas com várias UCPs: Software 2.1 2.2
2.3
2.4
2.5
6 7 7
8
De nição de Sistema Operacional . . . . . . . . . . . . . . . . . . . .
8
2.1.1
. . . . . . . . . .
8
. . . . . . . . . . . . . . . . . . . .
8
Funções comuns aos sistemas operacionais.
Sistema Operacional Tradicional 2.2.1
Características
2.2.2
Objetivos
. . . . . . . . . . . . . . . . . . . . . . . . . .
9
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
Sistema Operacional de Rede
. . . . . . . . . . . . . . . . . . . . . .
9
. . . . . . . . . . . . . . . . . . . . . . . . . .
10
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.3.1
Características
2.3.2
Objetivos
Sistema Operacional Distribuído
. . . . . . . . . . . . . . . . . . . .
10
2.4.1
De nições . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.4.2
Características
2.4.3
Objetivos
2.4.4
Vantagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.4.5
Desvantagens . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
. . . . . . . . . . . . . . . . . . . . . . . . . .
11
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
Questões de projeto de um sistema distribuído 2.5.1
Transparência
2.5.2
Flexibilidade
2.5.3
Con abilidade
2.5.4
Desempenho
2.5.5
Escalabilidade
2.5.1.1
2.5.4.1 2.6
4
1.1.1
1.2.1
1.3
4
Problemas e soluções . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
12
. . . . . . . . . . . . . . . . . . . . . . . . . .
12
Tipos de transparência
. . . . . . . . . . . . . . . .
12
. . . . . . . . . . . . . . . . . . . . . . . . . . .
12
. . . . . . . . . . . . . . . . . . . . . . . . . .
13
. . . . . . . . . . . . . . . . . . . . . . . . . . .
13
Métricas para medir desempenho:
. . . . . . . . . .
13
. . . . . . . . . . . . . . . . . . . . . . . . . .
13
Resumo comparativo . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3 Comunicação em sistemas distribuídos
15
3.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2
Protocolos em camadas
. . . . . . . . . . . . . . . . . . . . . . . . .
15 15
3.3
Modelo cliente-servidor . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.3.1
Vantagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
3.3.2
Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
1
3.4
3.3.3
Endereçamento
. . . . . . . . . . . . . . . . . . . . . . . . .
17
3.3.4
Primitivas de troca de mensagens . . . . . . . . . . . . . . . .
17
3.6
Síncronas e assíncronas (bloqueadas e não-bloqueadas) 18
3.3.4.2
Uso de buer . . . . . . . . . . . . . . . . . . . . . .
3.3.4.3
Con áveis e não-con áveis
19
Chamada remota a procedimento . . . . . . . . . . . . . . . . . . . .
20
Problemas com a chamada remota a procedimento . . . . . .
21
3.4.1.1
Espaços de endereçamento diferentes . . . . . . . . .
21
3.4.1.2
Passagem de ponteiros . . . . . . . . . . . . . . . . .
21
3.4.1.3
Negação de serviço . . . . . . . . . . . . . . . . . . .
21
Comunicação em Grupo . . . . . . . . . . . . . . . . . . . . . . . . .
23
3.5.1
Introdução
23
3.5.2
Tipos de grupos
3.5.3
Controle dos membros do grupo
3.5.4
Ordenação de mensagens
3.5.5
Escalabilidade na comunicação grupal
Resumo
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
4.2
4.3
4.4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
26
. . . . . . . . . . . . . . . . . . . . . . . . .
26
4.1.1
Relógios lógicos . . . . . . . . . . . . . . . . . . . . . . . . . .
26
4.1.2
Algoritmos para sincronização de relógios
. . . . . . . . . . .
28
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
4.2.1
Algoritmo centralizado . . . . . . . . . . . . . . . . . . . . . .
28
4.2.2
Algoritmo descentralizado . . . . . . . . . . . . . . . . . . . .
28
4.2.2.1
. . . . . . . . . . . . . . . . . . . . . . . .
29
. . . . . . . . . . . . . . . . . . . . . . . . . . .
29
Exclusão Mútua
Exemplo
4.2.3
Uso de token
4.2.4
Comparação entre os algoritmos
. . . . . . . . . . . . . . . .
5.2
30
Algoritmos eletivos . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
4.3.1
O algoritmo do ditador
30
4.3.2
. . . . . . . . . . . . . . . . . . . . .
O algoritmo em anel . . . . . . . . . . . . . . . . . . . . . . .
31
Deadlocks em sistemas distribuídos . . . . . . . . . . . . . . . . . . .
31
4.4.1
Detecção de deadlocks . . . . . . . . . . . . . . . . . . . . . .
32
4.4.1.1
Algoritmo centralizado
32
4.4.1.2
Algoritmo descentralizado . . . . . . . . . . . . . . .
Prevenção de deadlocks
Resumo
. . . . . . . . . . . . . . . .
32
. . . . . . . . . . . . . . . . . . . . .
32
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
5 Processos em sistemas distribuídos 5.1
24 25
Relógios e sincronização
4.4.2 4.5
23 24
. . . . . . . . . . . . .
4 Sincronização em sistemas distribuídos 4.1
18
. . . . . . . . . . . . . .
3.4.1
3.5
3.3.4.1
34
Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
5.1.1
Organizações de threads dentro de um processo . . . . . . . .
34
5.1.2
Threads e chamadas remotas a procedimentos . . . . . . . . .
34
Alocação do processador . . . . . . . . . . . . . . . . . . . . . . . . .
35
5.2.1
Modelos de alocação . . . . . . . . . . . . . . . . . . . . . . .
35
5.2.2
Alguns aspectos
. . . . . . . . . . . . . . . . . . . . . . . . .
36
5.2.3
Alguns exemplos
. . . . . . . . . . . . . . . . . . . . . . . . .
36
5.3
Escalonamento
5.4
Resumo
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
2
6 Sistemas de arquivos distribuídos 6.1
O projeto 6.1.1
O serviço de arquivos
6.1.2
O servidor de diretórios
6.1.3 6.2
38
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38 38
. . . . . . . . . . . . . . . . . . . . .
39
6.1.2.1
Identi cação transparente . . . . . . . . . . . . . . .
39
6.1.2.2
Identi cação em dois níveis . . . . . . . . . . . . . .
39
Compartilhamento de arquivos
. . . . . . . . . . . . . . . . .
40
Implementação de um sistema de arquivos . . . . . . . . . . . . . . .
40
6.2.1
Utilização de arquivos
40
6.2.2
Estrutura do sistema . . . . . . . . . . . . . . . . . . . . . . .
41
6.2.3
Armazenamento em cache . . . . . . . . . . . . . . . . . . . .
41
6.2.4
Replicação
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
6.3
Tendências
6.4
Resumo
3
Capítulo 1
Sistemas com várias UCPs: Hardware 1.1 Problemas e soluções 1.1.1 Questões atuais •
Limite físico para as UCPs tradicionais (Lei de Moore);
•
Tecnologia cada vez mais cara;
•
Necessidade de mais processamento para resolução de problemas computacionalmente caros;
•
A rede é o computador (Scott McNealy, CEO Sun Microsystems);
•
Técnicas de software mais avançadas.
1.1.2 Soluções propostas •
Miniaturização de componentes;
•
Uso de UCPs em paralelo;
•
UCPs com mais de um núcleo de processamento na mesma pastilha;
•
Desenvolvimento de software que aproveitem arquiteturas com mais de uma UCP.
1.2 Arquitetura de máquinas paralelas Sistemas distribuídos consistem de várias CPUs interconectadas.
No entanto, há
várias formas diferentes no qual esse hardware pode estar organizado. Classi cação segundo Flynn:
SISD - máquina tradicional; SIMD - processadores matriciais; MISD - não existe; MIMD - vários processadores interconectados. Subclassi cados em: 4
1.2.1 Multiprocessador •
Sistema fortemente acoplado;
•
Várias UCPs acessam a mesma memória;
•
Memória compartilhada;
•
A comunicação se dá através de um barramento de comunicação.
1.2.1.1 SMP (Multiprocessamento Simétrico) Tipos de barramento Único: •
Comercialmente, até 64 UCPs;
•
Somente uma unidade funcional usa o barramento por vez;
•
Arquitetura simples, econômica e exível;
•
Uso de memórias cache em cada UCP, o que acelera a performance, mas traz novos problemas, como a coerência do cache.
5
Cruzado comutado: •
Matriz de interconexão;
•
Uso de comutadores;
•
Mais de uma UCP pode comunicar-se com uma memória simultaneamente;
•
Custo eleva-se:
n
processadores
= n2 comutadores.
Rede Ômega: •
Menos comutadores:
•
Latência para acesso à memória.
n
processadores
=
(n . log2 n) comutadores. 2
1.2.1.2 NUMA (Acesso Não-Uniforme à Memória) •
Tempo de acesso à memória depende da localização física da UCP.
•
Conjuntos de UCPs e memória, interligados num barramento comum.
•
Desempenho satisfatório - minimizar diálogo com a memória remota.
•
Expansibilidade maior, mais fácil para montar e manter.
6
1.2.2 Multicomputador Sistema fracamente acoplado;
•
Cada UCP acessa a sua memória;
•
Memória única, para cada nó do sistema;
•
A comunicação se dá através de um meio de comunicação (rede);
•
Principal gargalo: Troca de mensagens.
1.3 Comparativo entre os sistemas Características
Sistemas fortemente acoplados
Sistemas fracamente acoplados
Memória
Centralizada
Espalhada
Comunicação entre UCPs
Rápida
Lenta
Arquitetura
Complexa
Simples
Número de UCPs
Dezenas
Ilimitado
Escalabilidade
Baixa
Alta
Administração
Simples
Complexa
Custo
Maior
Menor
Segurança
Centralizada
Distribuída
7
Capítulo 2
Sistemas com várias UCPs: Software 2.1 De nição de Sistema Operacional Silberchatz:
Um sistema operacional é um programa que age como um interme-
diário entre o usuário do computador e o hardware. O propósito de um S.O. é prover um ambiente no qual um usuário possa executar programas de forma conveniente e e ciente.
2.1.1 Funções comuns aos sistemas operacionais. •
Execução de programas;
•
Operações de E/S;
•
Manipulação do sistema de arquivos;
•
Comunicação;
•
Detecção de erros;
•
Alocação de Recursos;
•
Proteção.
2.2 Sistema Operacional Tradicional 1. Sistema operacional centralizado 2. Aplicado a sistemas convencionais 3. Recursos centralizados 4. Arquiteturas mono ou multi-processadas (multiprocessador) 5. Sistemas multi-tarefas e multi-usuários
8
2.2.1 Características •
Compartilhamento de recursos
•
Todos os recursos são acessíveis internamente
•
Comunicação entre processos via memória compartilhada ou através de facilidades providas pelo núcleo do sistema
2.2.2 Objetivos •
Virtualizar os recursos do hardware
•
Gerenciar uso dos recursos locais
•
Sincronizar atividades
2.3 Sistema Operacional de Rede Uma coleção de S.O de computadores conectados a uma rede incorporando módulos para prover acesso a recursos remotos. Com isso tem-se uma implementação barata, porém, exige que o usuário conheça a localização dos recursos requisitados
Silberchatz:
Os usuários sabem da existência de várias máquinas, podem abrir
sessões em várias máquinas e transferir dados entre elas.
9
2.3.1 Características •
Implementação relativamente simples
•
SOs incorporam módulos para acessar recursos remotos
•
Coleção de sistemas operacionais distintos
•
Comunicação entre sistemas através de protocolos
•
O usuário deve conhecer a localização dos recursos
•
Os recursos pertencem a computadores especí cos
2.3.2 Objetivos •
Disponibilidade de recursos através de um meio em comum.
•
Gestão centralizada dos recursos.
•
Economia de gastos.
Exemplos:
Compartilhamento de impressoras e arquivos Web; espaço em disco;
e-mail; serviços de autenticação.
2.4 Sistema Operacional Distribuído Entende-se por ambiente distribuído como um conjunto de processadores interligados por uma rede de interconexão e sem memória compartilhada. A ausência de memória compartilhada obriga a uma interação entre processadores de uma forma distinta do ambiente centralizado: ao invés de variáveis ou arquivos compartilhados utiliza-se troca de mensagens.
10
2.4.1 De nições Tanenbaum:
Um sistema distribuído é uma coleção de computadores independen-
tes que parecem ao usuário como um único computador.
Silberchatz:
Os usuários não precisam saber da existência de várias máquinas, os
recursos remotos são usados da mesma forma que os recursos locais.
Lamport:
Um sistema distribuído é aquele em que eu não posso fazer meu traba-
lho, pois uma máquina que eu nem conheço, não sei onde está, e nunca ouvi falar encontra-se fora do ar.
2.4.2 Características •
Construção de um ambiente computacional virtual
•
Localização dos recursos é abstraída
•
Localização do processamento é abstraída
•
Mecanismos transparentes de distribuição, replicação e tolerância a faltas
2.4.3 Objetivos O SO distribuído deve:
•
Controlar a alocação de recursos para tornar seu uso e ciente
•
Prover um ambiente de computação virtual de alto nível
•
Esconder a distribuição dos recursos e do processamento
2.4.4 Vantagens 1.
Economia:
Aproveitar recursos ociosos; É mais barato ter vários processa-
dores interconectados do que um supercomputador; 2.
Distribuição inerente:
algumas aplicações são distribuídas por natureza; 11
3.
Tolerância a falhas:
em caso de falha de uma máquina, o sistema pode
sobreviver, mesmo com desempenho degradado; 4.
Crescimento incremental:
o poder computacional pode ser aumentado
através da inclusão de novos equipamentos; 5.
Flexibilidade:
Maior exibilidade na alocação dos recursos, permitindo que
usuários compartilhem dados, processamento e dispositivos.
2.4.5 Desvantagens 1.
Aplicações mais complexas:
Pouco software de alto nível disponível para
sistemas distribuídos; 2.
Segurança:
Necessidade de construir mecanismos para controle de acesso às
informações; 3.
Dependência da rede:
Falhas, capacidade de tráfego insu ciente.
2.5 Questões de projeto de um sistema distribuído 2.5.1 Transparência De nição:
Tem o objetivo de fornecer aos usuários uma imagem única e abstrata
do sistema computacional.
2.5.1.1 Tipos de transparência Localização: os usuários não sabem onde os recursos estão localizados. Migração: os recursos podem se mover sem alterar seus nomes. Replicação: os usuários não sabem quantas cópias de um recurso existem. Concorrência: múltiplos usuários podem compartilhar um recurso automaticamente.
Paralelismo:
atividades podem ocorrer em paralelo sem que o usuário saiba (falta
muito ainda para ser atingido).
2.5.2 Flexibilidade O sistema é exível quando a inserção de novos módulos é uma tarefa simples. No caso de sistemas operacionais distribuídos, o kernel deve ser exível a ponto de tornar essa tarefa o menos custosa. Uma das propostas é o uso de
microkernel.
O microkernel implementa poucas funções, fornecendo em princípio quatro serviços básicos:
•
Mecanismo de comunicação entre processos
•
Algum tipo de gerência de memória
•
Uma pequena parte do escalonamento e gerência de baixo nível de processos
•
Estrada e saída de baixo nível
O uso de microkernel pode ser uma opção interessante, pois a inserção de módulos, no nível do usuário, é uma tarefa mais simples do que em um kernel do tipo monolítico. 12
2.5.3 Con abilidade Alguns aspectos da con abilidade são:
•
Disponibilidade:
Fração do tempo em que o sistema pode ser usado plena-
mente.
•
Segurança:
Proteção contra acessos não-autorizados a espaços de memória,
arquivos e demais recursos.
•
Tolerância a falhas:
A quanti cação de quanto as falhas podem ser contor-
nadas, a m de que o sistema continue em funcionamento, mesmo quando há problemas.
2.5.4 Desempenho Pode-se considerar como se fosse sinônimo de velocidade.
2.5.4.1 Métricas para medir desempenho: •
Tempo de resposta
•
Número de tarefas / tempo
•
Utilização do sistema
•
Quantidade consumida da capacidade da rede
2.5.5 Escalabilidade Suporta o aumento dos recursos e usuários mantendo um desempenho satisfatório. Os sistemas distribuídos precisariam se adaptar a possibilidade de termos ambientes com centenas ou milhares de processadores. Para isso, deve-se evitar:
•
Componentes centralizados:
Por exemplo, um único servidor de email
para todos os usuários.
• •
Tabelas centralizadas: Por exemplo, uma única relação on-line de telefones. Algoritmos centralizados: Por exemplo, roteamento de mensagens baseado em informações completas.
Ou seja, tudo que é centralizado deve ser evitado, sob pena de criar uma sobrecarga desnecessária no sistema. Deve-se usar algoritmos descentralizados, que possuem as seguintes características:
•
Nenhuma máquina possui informações completas sobre o estado do sistema.
•
Máquinas tomam decisões baseadas apenas nas informações disponíveis localmente.
2.6 Resumo comparativo Quadro classi cando os tipos de sistemas operacionais, seus serviços e objetivos.
13
Gerência de
Gerência de processos
Centralizado
recursos
Memória, Dispositivos
Virtualização
Serviços
Tipo
Objetivos
Acesso Remoto
S.O. de Rede
Compartilhamento
Troca de informações
de recursos
Visão global dos recurS. O. Distribuído
sos
Uni car tudo numa
Uso do poder compu-
visão global
tacional Centralizado
Gerência de
Gerência de processos Memória, Dispositivos
recursos Virtualização
Quadro comparativo dos sistemas operacionais quanto à características relativas a multiprocessamento: S.O.
Tradicional
Rede
Distribuído
Aparência
Um processador
Vários
Um processador
virtual Tipo de Sistema
processadores Único
Vários
Iguais
1
N (1 para cada
N (1 para cada
máquina)
máquina)
Operacional instalado Cópias do Sistema Operacional Comunicação
Memória
Arquivos
Trocas de
entre processos
compartilhada
compartilhados
mensagens
14
Capítulo 3
Comunicação em sistemas distribuídos 3.1 Introdução A grande diferença entre um sistema distribuído e um sistema tradicional é a implementação da comunicação entre processos.
•
Sistemas tradicionais supõem a pré-existência de memória compartilhada facilita o uso de meios como semáforos.
•
Sistemas distribuídos - não há compartilhamento entre os nós - necessidade de repensar a comunicação entre processos em bases novas.
•
Uso do modelo OSI para implementar a comunicação - uso de protocolos.
•
Troca de mensagens - opção pelo uso da RPC (chamada remota de procedimento) - simples e e ciente.
3.2 Protocolos em camadas •
Uso de protocolos - regras que de nem como a comunicação se dará
•
Modelo OSI - 7 camadas (aplicação, apresentação, sessão, transporte, rede, enlace e físico).
•
Protocolos orientados à conexão - Transmissor e receptor acertam previamente como será feita a troca de mensagens - aperto de mãos.
•
Protocolos não-orientados à conexão - o transmissor simplesmente envia a mensagem, sem ter certeza de que terá um receptor do outro lado.
3.3 Modelo cliente-servidor •
Cabeçalho das mensagens traz informação de todas as camadas do modelo OSI - gera sobrecarga na transmissão.
•
Processos-servidores - Processos que cooperam entre si, que fornecem recursos a processos usuários, os processos-clientes.
15
•
Modelo para comunicação num sistema distribuído - baseado num protocolo não-orientado a conexão:
solicitação/resposta.
O cliente faz uma solicita-
ção, e o servidor envia uma resposta.
3.3.1 Vantagens Simplicidade:
não há a sobrecarga de informação gerada por várias camadas de
comunicação. A comunicação é direta.
E ciência:
A pilha de protocolos é muito reduzida, tornando a comunicação me-
nos passível de falhas. Não há necessidade de roteamento e transporte, por exemplo.
3.3.2 Exemplo 1. Dois processos, um servidor e um cliente. 2. Informações a serem comuns a ambos: (a) Tamanho do nome de arquivo. (b) Quantidade de dados que podem ser transmitidos de cada vez. (c) Endereço do servidor de arquivos 3. Tipos de operação: (a) Criar arquivo (b) Ler parte do arquivo (c) Escrever parte do arquivo (d) Apagar arquivo 4. Códigos de erro: (a) Ok (b) Operação desconhecida (c) Erro em parâmetro (d) Erro em E/S 5. Formato da mensagem: (a) Quem envia (b) Quem recebe (c) Operação a ser feita (d) Quantos bytes 16
(e) Onde começa a mexer no arquivo (posição) (f ) Código de erro (g) Nome do arquivo (h) Dados a serem lidos ou escritos Com esse conjunto de informações, temos um protocolo bem simples, mas que possibilita a troca de mensagens entre processos-servidores e processos-clientes.
3.3.3 Endereçamento Como identi car o processo-cliente? Em que máquina ele estará? 1. A primeira opção é mudar o número do processo, acrescentando também o número da máquina que o hospeda. Exemplo: Processo 123 na máquina 45:
45.123,
ou
123@45.
Nem sempre funciona: Se uma máquina que hospeda um
processo estiver fora do ar, será preciso atualizar em todos os nós qual foi a máquina que recebeu aquele processo que estava rodando na máquina que parou de funcionar.
número único para endereçamento do processo, independente da máquina ao qual o processo está. Só que de-
2. Uma segunda opção é colocar um
verá existir um processo servidor que dará os endereços aos processos. E isso deverá ser centralizado. Num sistema distribuído, não funciona bem. 3. A terceira opção é o número do processo ser sorteado ao acaso dentro de uma quantidade de números possíveis muito grande.
Por exemplo, o espaço dos
números inteiros de 64 bits, na base binária. Logo, serão
264 possibilidades,
e
a chance de dois processos pegarem o mesmo número será muito remota. Aí temos um problema: Como o processo saberá com quem ele deverá se comunicar? Uma opção é que, a cada processo criado, seja enviado um pacote em broadcast para todos os outros nós do sistema, para que eles saibam o endereço do novo processo. Dessa forma também, o nó retorna o seu endereço também para o transmissor, e ele forma uma tabela de endereços, tornando-se um
vidor de nomes.
ser-
O problema é que o uso de broadcasts gera tráfego extra
na rede. 4. Uma última opção é usar um hardware especial, que captura aleatoriamente o endereço de cada nó com o qual foi estabelecida uma conexão, e o número do processo com o qual foi feita a interação. Daí, quando o processo solicitar uma comunicação, o próprio hardware vai fazer a tradução
endereo de rede.
nmero de processo →
O problema é que é necessário um hardware especial para
isso. Como visto, qualquer implementação tem vantagens e problemas, cabe ao desenvolvedor escolher e aproveitar da melhor maneira possível.
3.3.4 Primitivas de troca de mensagens As primitivas de troca de mensagens são os comandos usados para estabelecimento da comunicação com outro processo, e a efetiva troca da mensagem.
17
3.3.4.1 Síncronas e assíncronas (bloqueadas e não-bloqueadas) •
Uma primitiva bloqueada (ou síncrona ) trava o processo que está enviando a mensagem, até que a operação esteja concluída.
•
Uma primitiva não-bloqueada (ou assíncrona ) devolve o controle ao processo antes mesmo do envio da mensagem. Ou seja, ao mesmo tempo em que uma mensagem é enviada, o processo pode estar trabalhando em paralelo.
Ambas implementações existem em vários sistemas, cabe ao usuário usar qual convém mais. A segunda tem a vantagem da velocidade, mas uma grave desvantagem: o transmissor não pode modi car o buer enquanto a mensagem não foi enviada, além de não saber quando a transmissão foi encerrada.
3.3.4.2 Uso de buer Ambas as implementações realizadas acima pressupõem que o receptor responde à requisição
depois do transmissor faz o início do envio da mensagem. O problema antes do receptor estar pronto para receber
ocorre quando o transmissor faz o envio a mensagem.
Logo, todas as implementações descritas acima são do tipo 18
sem buer.
Existem algumas propostas de soluções para tal problema: 1. Descartar a mensagem. Logo, um cliente só recebe a mensagem se o servidor já a tiver enviado. Embora seja muito fácil ser implementada, um cliente pode ter que repetir várias vezes a requisição, o que gera um considerável atraso. 2. O uso de buer permite que a mensagem que armazenada, para que quando ela for solicitada, será prontamente entregue. Dá-se um prazo para que essa mensagem seja resgatada no buer, e se esse prazo estourar, a mensagem é descartada. Cada mensagem que entrar no nó, com um endereço referente a um processo, é colocado num buer, e aguarda ser resgatada. Funciona melhor do que a implementação anterior, mas requer uma gerência dos buers, e devese lembrar que os buers tem um tamanho
nito de espaço em memória para
armazenamento. Uma maneira é evitar que um processo mande mensagem se o buer que irá recebê-la estiver lotado.
3.3.4.3 Con áveis e não-con áveis Nas condições ideais, toda mensagem enviada chega no destinatário.
E, se não
chegar? Como veri car isso? 1. A primeira maneira é deixar essa preocupação, da con abilidade da comunicação, por conta do usuário. Admitir que o envio não é 100% con ável, e deixar que o usuário pense numa maneira de fazer com que o envio seja con ável. 2. A segunda maneira é o envio de uma mensagem de con rmação do recebimento da mensagem original. Logo, o kernel do nó receptor envia para o kernel do nó transmissor a con rmação da chegada da mensagem, e segue em frente. 3. Uma terceira maneira é não enviar a con rmação, mas deixar que a resposta seja a con rmação do envio da mensagem original. e enquanto não chegar a con rmação, nada feito.
Bloqueia-se o cliente, Simples, mas não há a
con rmação do recebimento da resposta (servidor para o cliente). 4. Por último, uma maneira de garantir a con abilidade é juntar as duas últimas implementações: No momento em que uma solicitação chegar, dispara-se um 19
contador de tempo.
Se o servidor aprontar a resposta a tempo, a própria
resposta será a con rmação. Se não, envia-se a con rmação, e posteriormente a resposta. Dessa forma, no melhor caso teremos 2 mensagens trocadas. No pior caso, serão 3 mensagens sendo trocadas.
3.4 Chamada remota a procedimento Apesar da implementação do modelo cliente-servidor, descrito acima, ser simples, ele carece de um erro sério:
entender que
em operações de entrada e saída.
toda
comunicação será feita baseada
O problema é que, a intenção de um sistema
distribuído é parecer com um sistema centralizado (para os usuários), e usar toda comunicação para realizar operações de entrada e saída, acaba sendo problemático. Como resolver tal problema?
A proposta é que existisse um meio de comu-
nicação, para que um programa chamasse um procedimento localizado em outra máquina.
A, na máquina 1 chama um procedimento B , que está 2, A é congelado, e B é executado. Os dados que são necessários são A para B na forma de parâmetros, e o resultado volta para A como re-
Logo, quando
na máquina levados de
sultado da execução. Tudo isso é transparente ao programador, e esse procedimento é a
chamada remota a procedimento, ou RPC.
O grande segredo da RPC é que ela deve ser parecida ao máximo com uma chamada local, a um processo localizado na mesma máquina.
Ou seja, para o
desenvolvedor, ela é completamente transparente.
O stub (do cliente ou do servidor) é a parte do processo que envolve o empacotamento e desempacotamento, de parâmetros e resultados. Logo, os stubs, junto com o kernel, fazem o trabalho da comunicação entre máquinas. Uma chamada remota a procedimento é realizada executando os seguintes passos: 1. O procedimento do cliente chama o stub do cliente da maneira usual. 2. O stub do cliente faz uma requisição ao kernel do cliente. 3. O kernel do cliente manda uma mensagem ao kernel do servidor. 4. O kernel do servidor entrega a mensagem ao stub do servidor. 5. O stub do servidor desempacota os parâmetros e chama o servidor. 6. O servidor faz o seu trabalho e retorna o resultado para o próprio stub. 7. O stub do servidor empacota o resultado, coloca numa mensagem e faz uma requisição ao kernel do servidor.
20
8. O kernel do servidor envia a mensagem ao kernel do cliente. 9. O kernel do cliente entrega a mensagem ao stub do cliente. 10. O stub do cliente desempacota os resultados e repassa ao cliente.
3.4.1 Problemas com a chamada remota a procedimento Apesar da idéia ser simples, há alguns problemas:
3.4.1.1 Espaços de endereçamento diferentes O processo
A
e o procedimento
B
estão em máquinas diferentes, com
espaços de endereçamento diferentes. A passagem de parâmetros e de resultados pode ser complicada, caso as máquinas sejam diferentes (hardware diferente). Um dos problemas que temos quando ao espaço de endereçamento é a questão do uso dos formatos little endian (adotado pela Intel, por exemplo), e big endian (adotado pela Sun, por exemplo).
Basicamente, é a ordem de numeração dos bits dentro
de um byte. Logo, o little endian usa da direita para a esquerda, e o big endian, da esquerda para a direita. Há a necessidade de haver essa tradução, sob pena de nada funcionar. Uma maneira é fazer essa tradução, quando estamos comunicando servidor e cliente. Só que essa tradução ocorre
sempre, mesmo que o servidor e o
cliente tenham o mesmo formato.
3.4.1.2 Passagem de ponteiros E passagem de ponteiros, e de parâmetros por referência? Como caria? Na questão da passagem de ponteiros, uma alternativa seria bloquear, impedir a passagem de ponteiros.
Não seria desejável que isso acontecesse, logo pensou-se
em uma nova alternativa: Passar o conteúdo apontado pelo ponteiro, também, na mensagem.
Isso gera trabalho extra para o servidor (criando um novo ponteiro
para a mensagem que veio do cliente para o servidor), mas resolve o problema para estruturas simples. Se tivermos uma estrutura de dados mais complexa (como um grafo), aí é necessário mais malabarismos para obter o resultado desejado.
3.4.1.3 Negação de serviço E se houver uma falha no sistema? Primeiro, precisamos ver quais são as possibilidades de falhas que temos no sistema, e elas são: 1. O cliente não consegue achar o servidor. 2. A mensagem no sentido cliente→servidor se perdeu. 3. A mensagem no sentido servidor
→cliente
se perdeu.
4. O servidor sai do ar logo após ter recebido uma solicitação de serviço. 5. O cliente sai do ar logo após ter enviado uma solicitação de serviço. Vamos ver cada caso.
21
O cliente não consegue achar o servidor
Nesse caso, teremos que ter um
mecanismo para buscar o servidor, e retornar alguma informação se ele está fora do ar. O servidor pode não existir, ou não ser compatível com aquele cliente. Daí, o mecanismo deve checar isso. Mas o mecanismo que checa a existência do servidor pode gerar uma
exceção.
Algumas linguagens de programação tem maneiras de facilitar o trabalho do programador, para ter rotinas que tratem tais exceções. Infelizmente, não é a via de regra, e em muitas, o programador tem que prever aonde a exceção vai ocorrer no código. Nesse caso, da não-existência do servidor, o cliente terá que procurar outro servidor que o responda.
A mensagem no sentido cliente→servidor se perdeu
Aqui é simples: Basta
o cliente ter um temporizador, e disparar quando a mensagem for enviada. Se não chegar nenhuma mensagem avisando do recebimento por parte do servidor até o temporizador zerar, envia-se a mensagem de novo.
A mensagem no sentido servidor →cliente se perdeu
Aqui, a solução mais
óbvia seria a mesma do segundo caso. Mas isso acarreta um problema: O servidor não conseguiu mandar a mensagem.
O cliente, não recebendo a resposta, envia
novamente um pedido ao servidor, e o mesmo vai ter que processar duas requisições. Como tratar? Uma maneira simples é numerar as requisições feitas ao kernel do servidor. Se ele controlar esse número, poderá distinguir entre um pedido original e uma retransmissão, evitando que a mesma tarefa seja resolvida duas (ou mais) vezes.
O servidor sai do ar logo após ter recebido uma solicitação de serviço Existem duas situações diferentes aqui: 1. O servidor recebe a requisição, executa e sai do ar, sem enviar a resposta. 2. O servidor recebe a requisição e sai do ar, sem nem executar. Algumas soluções propostas são: 1. O cliente espera o servidor voltar ao ar. 2. O cliente faz uma nova ligação com outro servidor, e faça a operação novamente. 3. O cliente deve desistir e reportar o problema. 4. O cliente não tem nenhuma garantia de que vai ter resposta. Logo, nenhuma das soluções propostas acima é minimamente interessante. Algumas são fáceis de serem implementadas, outras são simples de entender, mas nenhuma é razoavelmente boa. Logo, o desenvolvedor escolhe uma e usa-a. E torce para que os servidores não caiam.
O cliente sai do ar logo após ter enviado uma solicitação de serviço Caiu o cliente. O processamento feito pelo servidor ca então órfão. Como resolver? Existem quatro propostas de solução: 1. Antes que o cliente mande a mensagem, o conteúdo é salvo em disco, num arquivo temporário. Caso o cliente caia, o servidor aguarda o retorno dele, que pega o arquivo, e os processamentos órfãos são eliminados.
22
2. O cliente saiu do ar e reiniciou.
Quando ele volta, manda uma mensagem
para toda a rede anunciando o seu retorno, para que os processamentos órfãos relacionados a ele, e que sejam anteriores ao atual estágio, sejam eliminados. 3. Uma outra maneira, aproveitando a idéia acima, é que, quando chega a mensagem do cliente solicitando o descarte, o servidor veri ca se o proprietário está disponível. Se não estiver, ele descarta o processamento. 4. Na última maneira, uma fatia de tempo
T
é dada para cada chamada remota,
para que ela possa trabalhar. Se não der tempo para concluir, ela deve solicitar mais uma fatia de tempo. Mas, se houver uma queda, o servidor espera pela
T.
passagem de uma fatia de tempo
Assim, todos os procedimentos órfãos
terão sido eliminados. Na prática, nenhuma das maneiras anteriores é a desejável.
Eliminar um pro-
cessamento órfão pode trazer problemas para o sistema como um todo, pois suas conseqüências são imprevisíveis.
3.5 Comunicação em Grupo Vimos até aqui, para a situação entre um cliente e um servidor, ou seja, dois processos interagindo entre si. Mas existem circunstâncias em que vários processos estão envolvidos, não apenas dois. O nosso objetivo aqui é pensar como podemos, numa só operação, atingir vários receptores.
Exemplo:
Vários servidores gerenciam um sistema de arquivos único, tolerante a
falhas. Nesse caso, é bom que o cliente repasse a sua mensagem a todos os servidores. Mesmo se um estiver fora do ar, os outros receberão e a solicitação será realizada mesmo assim.
3.5.1 Introdução Um
grupo é um conjunto de processos que agem juntos, de uma maneira especi -
cada pelo sistema ou por um usuário. Os grupos são dinâmicos, e processos podem entrar ou sair de grupos facilmente. A idéia é que o conceito de grupo seja uma abstração de conjuntos de processos, para que seja mais fácil para o transmissor enviar a mensagem. Logo, ele só precisa disparar uma mensagem para um grupo. Em termos físicos, depende principalmente de hardware. Por exemplo, um endereço de rede especí co para o grupo permitiria o cliente enviar uma mensagem a
multicasting). broadcasting,
esse endereço, e todos os servidores associados recebê-la (
Em redes que não temos multicasting, a solução é apelar para o que consiste em disparar a mensagem para
todas
as máquinas da rede.
Caso a
mensagem não seja de interesse da máquina que a recebeu, ela é descartada. Queira ou não, essa alternativa acaba acarretando uma sobrecarga desnecessária na rede. Em último caso, o sistema pode usar o
unicasting, que é basicamente o trans-
missor enviando a mensagem para cada membro do grupo. É uma alternativa cara computacionalmente, e deve ser evitada.
3.5.2 Tipos de grupos 1. Grupo fechado: Somente membros do grupo podem enviar mensagens para o grupo. São mais usados em processamento paralelo.
23
2. Grupo aberto: Qualquer cliente pode enviar mensagens para o grupo. A noção de servidores replicados é útil para grupos abertos. 3. Grupo igualitário: Todos os processos são iguais. São simétricos, e mesmo que um processo falhe, o sistema continua rodando. Em compensação, a tomada de decisão é mais complicada. 4. Grupo hierárquico: Há um processo que funciona como coordenador. A tomada de decisão é simples e rápida, mas quando o coordenador falha, todo o grupo falha.
3.5.3 Controle dos membros do grupo Uma maneira de controlar a existência dos grupos é implementando um
de grupos.
servidor
Ele seria o responsável por criar e remover grupos, incluir e remover
membros, entre outras coisas. Só tem um problema: Se o servidor de grupos cair, perde-se a gerência dos grupos. Quando ele voltar ao ar, tudo terá que ser refeito do zero. A outra maneira seria a gerência dos grupos sendo feita de forma
distribuída.
Logo, um processo que quiser entrar num grupo, faz a solicitação aos membros do grupo, e eles aceitam-o ou não.
Quando um processo quiser sair, ele envia uma
mensagem de até logo aos demais membros, e assim sai do grupo. Há ainda três problemas a serem lidados, em qualquer uma das implementações: 1. Se um membro sai do ar, ele efetivamente sai do grupo.
Só que os outros
membros descobrirão pelo método empírico, tentando enviar-lhe mensagens e não obtendo resposta. Logo, só depois que todos souberem da queda daquele membro, é que ele será removido do grupo. 2. A partir do momento em que um membro entra no grupo, ele precisa receber todas as mensagens enviadas para esse grupo.
Logo, a entrada dele no
grupo deve ser imediata, sob pena de ter perda de informação, e atrapalhar o processamento. Da mesma forma, um processo sai do grupo, e ele não deve mais receber mensagens relativas ao grupo que ele se retirou. Uma maneira de resolver seria o envio de uma mensagem de apresentação do novo membro ao grupo, ou uma mensagem de despedida, quando ele estiver saindo do grupo. 3. Se um grande número de membros sair do ar, podemos ter problemas para o funcionamento dos grupos, visto que a maior parte dos membros estão fora
de combate . Logo, quando os membros começarem a voltar, os membros restantes vão aceitando-os para o grupo. Mas apenas um deve ter essa tarefa, de reconstruir o grupo. E se dois ou mais processos tentarem simultaneamente?
3.5.4 Ordenação de mensagens Para termos a comunicação global de uma forma simples de usar, ela deve obedecer a duas propriedades: 1. Atender a solicitação do
broadcast atômico, que basicamente é:
Ou todos
os membros do grupo recebem a mensagem, ou nenhum recebe. 2. Atender a ordem de chegada das mensagens, para evitar atropelos. Uma maneira simples e e ciente é fazer com que as mensagens sejam expedidas na mesma ordem em que foram enviadas. Logo, toda mensagem interna do grupo é enviada a todos os membros do grupo. Assim, todos recebem-na, e temos o que foi convencionado chamar
ordenação em tempo global. 24
3.5.5 Escalabilidade na comunicação grupal Muitos algoritmos funcionam bem em sistemas distribuídos montados em cima de redes locais, com poucos nós. Mas, e como caria a comunicação se expandirmos o sistema distribuído, englobando centenas ou milhares de componentes?
E se
forem várias redes locais interligadas? Pior, e se essas redes estiverem espalhadas geogra camente?
Por exemplo, temos uma mensagem em multicast saindo da rede 2.
Quando
chega nos gateways G1 e G3, eles vão copiar a mensagem e colocar nas redes 1 e 4. Quando chegar nos gateways G2 e G4, irão copiar para a rede 3, duas vezes. Se extrapolarmos para vários gateways e redes interligadas, teremos um crescimento exponencial de mensagens inúteis vagando pelas redes, gerando congestionamento e atrapalhando o tráfego das mensagens realmente úteis. Vemos então que é necessário um algoritmo mais so sticado para evitar essa situação.
3.6 Resumo 1. A diferença básica entre os sistemas operacionais tradicionais e os distribuídos consiste na importância em que a comunicação tem entre os sistemas distribuídos. 2. Adota-se um modelo cliente-servidor de protocolos, bem mais simples, para ganhar em performance na rede, em detrimento de protocolos que geram mais tráfego e informações redundantes. 3. A chamada remota a procedimentos é uma abstração mais elaborada, em que ca transparente a comunicação entre o cliente e o servidor. 4. Apesar dela ser uma proposta muito interessante, também tem problemas, como: (a) Variáveis globais, ponteiros e estruturas de dados complexas são difíceis de serem usados e passados. (b) A localização do servidor deve estar bem de nida. (c) Os clientes e os servidores podem falhar, independente uns dos outros. 5. As chamadas remotas limitam a comunicação a um cliente e um servidor. Há várias situações onde deverá ocorrer a comunicação global, entre grupos de processos. 6. Há diversas de nições de grupos, e situações desejáveis, como o broadcast atômico e a ordenação das mensagens. 7. O problema da escalabilidade deve ser lembrado, principalmente expandindo o sistema para uma quantidade grande de nós, dispersos geogra camente.
25
Capítulo 4
Sincronização em sistemas distribuídos Em sistemas com um processador, os problemas ligados a regiões críticas, exclusão mútua e outras questões sobre sincronização são resolvidas com o uso de semáforos e monitores. Mas, em sistemas distribuídos, é inviável, pois pressupõe a existência de memória compartilhada, o que não ocorre aqui. Veremos então os mesmos problemas anteriores, agora em sistemas distribuídos, e alguns novos.
4.1 Relógios e sincronização Algoritmos distribuídos trazem as seguintes características: 1. As informações relevantes estão espalhadas entre as máquinas; 2. As decisões que os processos tomam estão baseadas apenas em informações locais; 3. Deve-se evitar falhas; 4. Não existe um relógio global. Os três primeiros tópicos dizem respeito à impossibilidade de coletar informações globalmente.
O sistema é esparso e distribuído, e deve-se evitar a todo custo a
centralização. A nal, se a máquina que centraliza um recurso pára, os seus clientes também param.
O último também é importante, já que o tempo é um conceito
ambíguo. Existem diferenças entre os relógios físicos dos computadores que compõem o sistema distribuído. Por exemplo, podemos ter situações onde o resultado é gerado num servidor, num dado instante, e esse instante para o cliente ainda não ocorreu. Isso é o que queremos evitar.
4.1.1 Relógios lógicos Os relógios do computador (na verdade
temporizadores) são fundamentais para
a sincronização entre processos. Eles são feitos de cristais de quartzo, que oscilam numa frequência bem de nida. Mas, num sistema distribuído, com vários nós de origens diferentes, não temos a garantia de que os cristais oscilarão exatamente na mesma frequência. ocorrerão discrepâncias (o que é chamado
26
Sempre
escorregamento do clock), por vezes
mínimas, mas acumulativas. Logo, depois de um intervalo de tempo razoavelmente longo, essas discrepâncias serão visivelmente perceptíveis. Uma solução seria sincronizar os relógios, para termos um tempo único. Isso é possível, e existem algoritmos para isso.
A idéia inicial é que o sincronismo não
precisa ser absoluto. O que vale é que, entre dois ou mais processos que interagem entre si, eles estejam sincronizados. Isso é o que chamamos de Os relógios reais são os
relógios físicos.
relógios lógicos.
Impõe-se uma restrição, para evitar que
haja uma discrepância muito grande entre os relógios, lógicos e físicos. Para sincronizar, usa-se a relação Isso é o que chamamos
a → b,
que quer dizer a acontece antes de b .
acontecimento-anterioridade.
Para ocorrer essa relação,
deve-se ter que: 1. Se a e b são eventos no mesmo processo, e se a ocorre antes de b, então
a→b
é verdadeira. 2. Se a é o evento de uma mensagem enviada por um processo, e b é o evento da mesma mensagem recebida por um outro processo, então
a→b
também é
verdadeira. A relação é transitiva: se
a → b,
e
b → c,
então
processos que não se comunicam, então eles são
a → c.
Se os eventos ocorrem em
concorrentes,
e com isso, nada
pode ser dito a respeito. No m das contas, o que temos é que, se
a → b,
então
C(a) < C(b). A idéia do algoritmo é que o evento carrega o valor do relógio por onde passou anteriormente.
Temos os processos 0, 1 e 2, e os eventos A, B, C e D. No lado esquerdo, a situação ocorre sem haver a sincronização entre os relógios.
Logo, o processo 0
recebe o evento D, só que o relógio local no processo 1 marca 48, e no processo 0, 42.
No lado direito, os relógios são corrigidos, como podemos ver: O processo 0
adianta o relógio para o valor 49, o que é seguinte ao valor quando o evento D saiu do processo 1. No caso do evento C, onde os dois relógios estão marcando o mesmo tempo, uma opção é colocar ambos com uma pequena diferença. Logo, o processo 2 marcaria 40, e o processo 1 marcaria 40,1, ou 41, como está marcando. Dessa forma, temos uma maneira de atribuir tempos a todos os eventos em um sistema distribuído, mas sujeita às seguintes condições: 1. Se a ocorrer antes de b no mesmo processo, então
C(a) < C(b).
2. Se a e b são o envio e o recebimento de uma mensagem, então então
C(b). 3. Sendo a e b diferentes, também teremos
27
C(a) 6= C(b).
C(a) <
4.1.2 Algoritmos para sincronização de relógios Existem diversos
servidores de hora disponíveis na Internet, que se comunicam
através do protocolo NTP (Network Time Protocol), que usa o protocolo de transporte UDP para estabelecer a conexão. Os algoritmos para sincronização de relógios são usados para sincronizar os relógios do sistema distribuído com os servidores de hora disponíveis localmente ou via Internet. Mas, se nenhum nó do sistema distribuído tem como acertar a hora, o jeito é cada nó cuidar do seu próprio tempo, e todas as máquinas se falam para manter a menor discrepância possível entre os seus relógios. Existem alguns algoritmos propostos, onde o servidor de hora é passivo (responde requisições de hora) ou ativo (envia mensagens às máquinas para que elas acertem a hora), centralizados (um servidor de hora) ou descentralizados (várias máquinas espalhadas), entre outras variações.
4.2 Exclusão Mútua As exclusões mútuas ocorrem quando dois ou mais processos concorrentes disputam para entrar (condição de disputa) numa região crítica, e usa-se semáforos (ou monitores) para garantir a exclusão mútua. Veremos como isso funciona num sistema distribuído.
4.2.1 Algoritmo centralizado A idéia aqui é simular a metodologia para um sistema com um processador apenas. Logo, teremos um servidor de exclusões mútuas. Esse servidor autoriza ou não cada um dos processos concorrentes a entrarem nas suas regiões críticas, e com isso temos justiça (ninguém espera inde nidamente), e a garantia da exclusão mútua ocorrer. Como desvantagens, temos o servidor, que se sair do ar, compromete todo o sistema, e também traz problemas quanto à performance, se tivermos apenas um servidor num sistema distribuído muito esparso.
4.2.2 Algoritmo descentralizado Aqui, colocamos todos os eventos do sistema em ordem cronológica de ocorrência. Eventos novos são colocados no m da la, e quando um quer entrar na sua região crítica, cria uma mensagem dizendo o nome da região que quer entrar; número e tempo corrente. O processo que quiser entrar, manda a todos os outros processos essa mensagem. Os processos que recebem podem reagir de três maneiras: 1. Se não tem problema, responde
ok.
2. Se estiver usando a região crítica, não responde ainda. 3. Se quiser entrar também na região crítica, compara-se o tempo vindo da mensagem com o tempo da sua própria mensagem, solicitando o uso da região crítica. (a) Se o tempo desse processo for menor, ele responde
ok.
(b) Se o tempo desse processo for maior, ele coloca a requisição numa la, e não responde ainda.
28
4.2.2.1 Exemplo 1. São 3 processos (0, 1 e 2). 2. O processo 0 envia a todos uma mensagem com tempo 10 e o processo 2 envia a todos uma mensagem com tempo 15. 3. O processo 1 não pretende entrar na região crítica, logo ele manda OK para os outros 2. 4. O processo 2 percebe que a prioridade é do processo 0, e manda OK. 5. O processo 0 coloca a requisição do processo 2 na la dele, e entra na região crítica. 6. Quando o processo 0 sai da região crítica, repassa ao processo 2 uma mensagem de OK, permitindo que este entre na região crítica. Em caso de con ito, ganha o processo que enviou a mensagem com o menor tempo armazenado. Dessa maneira, não temos starvation nem deadlock, o que é bom. Em compensação, todo processo é um ponto de falha: Se ele não responder a uma das mensagens, isso bloqueia os outros processos subsequentes.
Além disso,
teremos muito mais tráfego na rede, já que todos os processos participam de todas as decisões. Uma maneira para evitar o silêncio de um processo é solicitar um aviso de recebimento por parte dele. Se não chegar o aviso, é porque o processo tem algum problema, e os outros podem descartá-lo. Outro problema é que a comunicação é grupal. Logo, cada processo tem que ter a lista dos membros do grupo, e sempre atualizada. Isso demanda mais tráfego. Na prática, esse algoritmo acaba sendo mais lento e complexo do que o algoritmo centralizado, e ainda mais sujeito a problemas no caso de grupos grandes de processos.
4.2.3 Uso de token Uma abordagem completamente diferente é o uso do token ( cha). A idéia é simples: O grupo de processos é arranjado num anel lógico, e no início da execução, o primeiro processo recebe um token ( cha). Essa cha é passada via mensagem para o outro elemento do anel, e assim por diante.
O processo que detém o token pode entrar em uma região crítica, fazer tudo o que precisa ser feito, e depois sair. O mesmo não pode usar o token para entrar numa segunda região crítica, apenas uma de cada vez. Isso faz evitar a ocorrência
29
de starvation, já que, no pior dos casos, um processo terá que esperar todos os outros entrarem e saírem para ele poder entrar. Alguns problemas possíveis são: 1. A perda do token - Caso o token seja perdido, será necessário regenerá-lo, o que é complicado de ser detectado. 2. A parada repentina de um processo - Um processo não repassa o token, e nem entra na região crítica, logo pára todo o anel. Uma maneira de contornar é exigir que o processo que recebeu o token envie um aviso de recebimento. Se esse aviso não tiver sido emitido e recebido, é porque o processo está com problemas. O processo anterior repassa o token ao processo posterior ao processo morto, e ele é removido do anel.
4.2.4 Comparação entre os algoritmos O algoritmo centralizado é o mais simples e e ciente de todos, já que envia e recebe poucas mensagens. Mas tem o problema (sério) da centralização. O algoritmo da passagem de token gera uma quantidade de mensagens imprevisível. Se todos os membros do anel quiserem entrar na região crítica, serão duas mensagens. Mas nem todos podem querer entrar. O tempo de atraso entre o processo que pede para entrar na região crítica e efetivamente entra na mesma também varia. No algoritmo centralizado, é o tempo de
2
mensagens (o pedido e a liberação para entrar).
No algoritmo distribuído,
todos tem que receber o pedido e a liberação, com exceção do próprio.
n processos, serão 2(n−1) mensagens. varia, de 0 a n − 1mensagens.
tivermos isso
Logo, se
No algoritmo de passagem de token,
Abaixo temos uma tabela que resume essas informações. Mensagens por Algoritmo
entrada/saída da região crítica
3
Centralizado Descentralizado Passagem de token
Retardo antes da entrada (em tempos de mensagens) 2
2(n − 1)
Problemas
2(n − 1)
Coordenador fora do ar Qualquer processo fora do ar Perda do token,
1 a ∞
0 a n−1
queda de um processo
Mas num sistema tolerante a falhas, nenhum desses algoritmos é recomendado, a não ser que a perda de processos seja algo improvável.
4.3 Algoritmos eletivos Outro tipo de algoritmo que é usado para sincronização em sistemas distribuídos é o
algoritmo eletivo, onde um processo coordenador é eleito entre todos os outros
processos para administrar o acesso à região crítica. Abaixo temos alguns deles:
4.3.1 O algoritmo do ditador Quando um processo percebe que o coordenador não está respondendo às solicitações, ele começa uma
eleição, que funciona da seguinte maneira:
30
1. P envia uma mensagem solicitando o início da eleição a todos os processos com número de identi cação maior do que o dele próprio. (a) Se ninguém responder, P é o novo coordenador. (b) Se alguém responder, ele é o novo coordenador. 2. Envia-se uma mensagem para todos os membros do grupo, avisando quem é o novo coordenador.
4.3.2 O algoritmo em anel Esse algoritmo aqui constrói-se um anel lógico, só que sem um token a ser passado. Aqui, todos os processos conhecem quem é o seu antecessor e o seu sucessor. Se um dos processos descon a que o coordenador está inativo, ele manda uma mensagem para o seu sucessor, carregando um pedido de eleição, e o seu número de identi cação.
O sucessor acrescenta o seu próprio número de identi cação, e
repassa a informação à frente. Eventualmente, o processo que primeiro enviou o pedido de eleição recebe a sua mensagem de volta, já que ela traz o seu próprio número de identi cação. Caso um segundo processo também envie um pedido de eleição, torna-se o novo coordenador aquele cujo número de identi cação seja o maior. Feito isto, ele dispara uma nova mensagem no anel, anunciando quem é o novo coordenador, que circula todo o anel. Depois da segunda mensagem, todos voltam ao trabalho. Apesar da circulação de mensagens (num anel com
n
processos, teremos
2n
mensagens), o gasto extra de banda é efetivamente pequeno.
4.4 Deadlocks em sistemas distribuídos O problema de um deadlock num sistema distribuído é muito parecido com o problema num sistema centralizado (um processador), embora sejam mais difíceis de detectar ou evitar. Temos dois tipos de deadlocks: 1. Deadlocks ocorridos na comunicação entre processos - O processo A tenta enviar uma mensagem ao processo B, que tenta enviar uma mensagem ao processo C, que está tentando enviar uma mensagem ao processo A. 2. Deadlocks ocorridos quando os recursos são alocados - Vários processos estão disputando o acesso exclusivo a dispositivos de E/S, arquivos, qualquer tipo de recurso. Existem quatro estratégias para lidar com deadlocks: 1. Ignora os deadlocks ocorridos. 2. Deixa ocorrer o deadlock, detecta a ocorrência e e tenta recuperar. 3. Previne a ocorrência de deadlocks, fazendo com que a estrutura não possa ser quebrada. 4. Evita a ocorrência de deadlocks com uma política de alocação de recursos bem cuidadosa.
31
Nos sistemas distribuídos, os métodos 1 e 2 são populares, principalmente porque evitar o deadlock num sistema distribuído é muito difícil. A prevenção (método 3) é complexo de ser implementado, e o método 4 é inviável, pois para ser bem-sucedido, é necessário saber quais recursos cada processo irá precisar, por antecipação. E essa informação quase nunca está disponível.
4.4.1 Detecção de deadlocks 4.4.1.1 Algoritmo centralizado Um coordenador mantém um mapa geral de todos os processos e recursos de todo o sistema distribuído, e se for necessário, ele elimina um processo para evitar o deadlock. Nesse caso, é necessário que o coordenador receba o mapa de processos e recursos de cada máquina, para poder montar o mapa geral. Isso pode ser feito de várias maneiras (alterações feitas são submetidas ao coordenador, envio periódico das alterações, ou o pedido do coordenador pelas alterações).
Todas são caras
computacionalmente, e nem sempre funcionam bem. Pode ocorrer o que chamamos de um
falso deadlock,
que é o coordenador
eliminar alguns processos que não estavam gerando um deadlock.
Uma maneira
de evitar é usar o algoritmo que discutimos na seção 4.1.1, para o fornecimento do tempo global.
4.4.1.2 Algoritmo descentralizado Aqui, os processos tem permissão de pedir a alocação de vários recursos de cada vez, ao invés de um de cada vez. Assim, a fase de crescimento do algoritmo pode ser acelerada. Um processo que quer um recurso local requisita-o.
Agora, um processo que
mensagem de sondagem para outro processo, para ver se o recurso está disponível. quer um recurso que está numa outra máquina, tem que enviar uma
Quando chega no destino, o receptor vê se ele está aguardando por recursos de algum processo. Se estiver, ele atualiza a mensagem, com os seus próprios dados, e a mensagem é repassada para o processo responsável pelo bloqueio do transmissor da mensagem. Se a mensagem for retransmitida, e voltar ao processo de origem, é um deadlock. Uma maneira de desfazer é eliminando o processo que pede o recurso, mas aí todos podem acabar encerrando, e temos um problema ainda maior do que o deadlock. Outra maneira é colocar a identidade do processo no nal da mensagem, e se gerar um deadlock, todo o ciclo estará registrado na mensagem. Quem originou a mensagem solicita o m do processo com número de identi cação mais alto, para quebrar o deadlock. Mesmo assim, os métodos não são e cientes.
4.4.2 Prevenção de deadlocks O sistema tem que ser projetado com cuidado, para que a ocorrência de deadlocks seja impossível. Logo, o projeto de um sistema assim também é quase impossível. Algumas das maneiras pensadas são:
•
Cada processo só pode usar um recurso de cada vez;
•
Os processos só podem pedir o uso de recursos novos depois de liberarem todos que estão usando;
32
•
Os processos devem pedir todos os recursos que vão usar antes de entrar em execução;
•
Os recursos são numerados, e cada processo não pode solicitar um recurso com número de identi cação menor do que o daquele que ele detém a posse.
Mas, na prática, todos esses métodos causam problemas, pois demanda que os processos trabalhem de forma estritamente ordenada. Em um sistema distribuído, pode-se prevenir a ocorrência de deadlocks usando um método, que descrevemos abaixo: No momento em que se estabelece uma transação (ou seja, um processo faz uso de um recurso, entrando na região crítica), coloca-se uma etiqueta nessa transação marcando o tempo global daquele instante. Graças ao algoritmo descrito na seção 4.1.1, duas transações não terão o mesmo tempo global, e mesmo que tenham, o número de identi cação será o critério de desempate. Quando um processo está prestes a ser bloqueado, esperando por um recurso que outro processo estiver usando, procura-se ver qual é o mais velho. Somente os processos mais jovens (com o tempo global maior do que o processo em execução) podem car esperando. Logo, dessa maneira, as etiquetas sempre estarão em ordem decrescente, impedindo que se formem ciclos, e em consequência, deadlocks.
4.5 Resumo 1. Inicialmente vimos o algoritmo para sincronizar processos entre si, sem a necessidade de usar fontes externas de tempo. Esse algoritmo, como vimos, é muito útil. Vimos também o uso de relógios físicos para sincronizar os processos. 2. Na exclusão mútua, temos três algoritmos, cada um com vantagens e desvantagens: (a) O centralizado mantém todas as informações em um único ponto. (b) O distribuído tem as informações espalhadas por todos os pontos, realizando os cálculos em paralelo. (c) A passagem do token passa o controle por cada uma das máquinas ao longo de um anel lógico. 3. Muitos algoritmos requerem que um processo seja o coordenador. Logo, vimos duas maneiras de se eleger um coordenador:
O algoritmo do ditador e o
algoritmo do anel. 4. Vimos o problema dos deadlocks, agora em sistemas distribuídos, e vimos como funcionam alguns algoritmos para detecção e prevenção de deadlocks.
33
Capítulo 5
Processos em sistemas distribuídos Os processos são nosso alvo de estudo nesse capítulo, e em particular, veremos como os sistemas operacionais administram vários processadores, e fazem o balanceamento de carga entre eles, além do escalonamento e a alocação.
5.1 Threads Na maioria dos sistemas operacionais tradicionais, cada processo tem um espaço de endereçamento e um único thread. Mas há sistemas que permitem a existência de mais de um thread (sistemas multithread) compartilhando um único espaço de endereçamento. Conhecemos a de nição, e como tudo funciona.
5.1.1 Organizações de threads dentro de um processo Os processos devem ter um buer que coleta as requisições feitas aos threads. A partir desse buer, temos três tipos de organizações internas: 1. Modelo do dispatcher: Há um thread, o
dispatcher, que repassa o conteúdo
do buer a cada thread do processo, para que ele trate aquela requisição. 2. Modelo do time: Cada thread vai até o buer, pega uma requisição e a executa. Não há o dispatcher aqui. 3. Modelo do pipeline: O primeiro thread pega a requisição, processa e repassa-a para o próximo. E assim vai, até o m.
5.1.2 Threads e chamadas remotas a procedimentos Estudamos as chamadas remotas a procedimentos na seção 3.4, e agora, como podemos implementá-las, de forma a aproveitar o recurso dos threads? Foi observado que, mesmo em um sistema distribuído, muitas chamadas remotas a procedimentos eram feitas entre processos que estão operando dentro da mesma máquina. Ora, empacotar os parâmetros e desempacotar do outro lado, e também o caminho de volta... É ine ciente. A idéia é fazer com que um thread, dentro de um processo, possa chamar um outro thread em um outro processo numa mesma máquina, de uma forma muito mais e ciente.Vejamos:
34
1. O thread que age como servidor é inicializado, e ele copia para o kernel a sua interface.
Essa interface de ne quais procedimentos poderão ser chamados,
parâmetros, etc. 2. O thread que é o cliente, então, quando for inicializado, importa a mesma interface do kernel, e informa ao kernel que em algum momento irá comunicarse com o servidor. 3. O kernel então, ca sabendo que haverá comunicação entre eles, em algum momento, e prepara um meio de processar essa chamada futura. 4. No momento em que ocorre a chamada, o kernel apenas troca um pedaço do espaço de endereçamento do cliente (que contém os dados a serem passados) com um pedaço do espaço de endereçamento do servidor, e dispara-o. Assim, não é necessário o empacotamento de parâmetros, e nem cópia dos mesmos, processando-os muito mais rápido. No nal das contas, temos economia de tempo substancial.
5.2 Alocação do processador Um sistema distribuído é composto por diversos processadores, que podem estar organizados como um conjunto de estações de trabalho, um armário de processadores, ou algo que seja um misto dos dois. Mas, em todos os casos, é preciso um algoritmo que decida quem vai ser executado aonde. Se usarmos um
modelo com estações de trabalho, esse algoritmo só poderá
executar alguma coisa se a estação estiver ociosa. E, no momento em que a estação for usada, o processo que estiver lá sendo executado deve ser suspenso e transferido para outra máquina, para dar continuidade. Se usarmos o modelo do armário de processadores, para cada processo a ser executado, será necessária uma decisão, para qual processador o processo será enviado. Veremos então alguns modelos e algoritmos para resolver o problema da alocação de processadores.
5.2.1 Modelos de alocação Podemos dividir os modelos de alocação em
estratégias migratórias.
estratégias não-migratórias, e em
As estratégias não-migratórias de nem que, de nido onde o processo será executado, lá ele será executado, até o m. Não há possibilidade do processo ser levado para ser executado em outro processador. As estratégias migratórias permitem que o processo seja remanejado para outro processador, mesmo que ele já esteja em execução. As estratégias migratórias permitem um melhor balanceamento de carga, mas são mais complexas. O objetivo nal é e
minimizar o tempo de resposta.
maximizar a utilização do processador,
Vários algoritmos foram propostos ao longo dos tempos:
•
Algoritmos determinísticos - Bons quando a carga de trabalho é previsível.
•
Algoritmos heurísticos - Bons quando a carga de trabalho é imprevisível.
•
Algoritmos centralizados - Agrupamento da decisão num lugar é melhor para decidir, mas é pouco robusto.
35
•
Algoritmos distribuídos - Descentralização da decisão reparte o problema entre várias máquinas. É mais robusto, mas mais lento.
•
Algoritmos ótimos - Aqueles que são os melhores possíveis para a alocação.
•
Algoritmos subótimos - Os que são aceitáveis para o seu propósito.
•
Algoritmos locais - Usado para alocar a execução de um processo na sua própria máquina de origem, caso a carga esteja baixa.
•
Algoritmos globais - Usado para avaliar onde é o melhor lugar para alocar a execução de um processo, em todo o sistema.
•
Algoritmos iniciados pelo transmissor - O transmissor deve começar a busca por uma nova máquina, para executar aquele processo.
•
Algoritmos iniciados pelo receptor - O receptor deve começar a busca por uma nova máquina, para executar aquele processo.
5.2.2 Alguns aspectos 1. Supõe-se que cada máquina sabe qual é a sua carga de trabalho, e ser capaz de informar às outras qual é o seu estado. Essa medida não é absolutamente trivial, e tem que ser única para todo o sistema distribuído. 2. E como tratar a sobrecarga gerada no sistema, justamente por esse processo, de coleta de informações? 3. Qual a complexidade desse algoritmo? Estudos comprovam que algoritmos so sticados dão um ganho razoável, mas impõem a penalidade de gerarem muita sobrecarga. Logo, algoritmos simples podem trazer ganhos mais interessantes. 4. A estabilidade do algoritmo, onde máquinas diferentes rodam seus algoritmos de maneira assíncrona. Logo, uma máquina pode achar que a outra está com folga, mas na verdade é a informação que está defasada.
5.2.3 Alguns exemplos 1. Um algoritmo determinístico baseado na teoria dos grafos - O sistema é representado como um grafo ponderado, e a idéia é dividir todo o grafo em subgrafos, um para cada processador, e com isso, procurar a divisão que minimize o tráfego na rede. Ou seja, o que queremos é montar grupos de processos que interajam muito entre si, e pouco com outros grupos de processos. É um algoritmo complexo, e precisa de informações normalmente não-disponíveis no momento da necessidade. 2. Um algoritmo centralizado - Um processo coordenador tem uma tabela de utilização, que é atualizada de tempos em tempos. Com base nisso, a carga é repassada para cada máquina, de forma justa e equilibrada.
É um algo-
ritmo simples, mas em sistemas muito grandes não funciona bem, visto que há gargalos e pouca robustez. 3. Um algoritmo hierárquico - Montar toda a estrutura logicamente numa hierarquia, com grupos de máquinas submissas a uma máquina, que por sua vez está submissa a outra, e por aí vai. Se uma dessas máquinas gerentes falhar, promove-se alguém para o cargo.
É robusto e funciona bem, mas o
fato das requisições serem geradas randomicamente podem atrapalhar o seu funcionamento. 36
4. Um algoritmo heurístico distribuído - Quando um processo é criado, a máquina de origem sonda as outras máquinas, para saber qual delas tem carga abaixo de um limite pré-estabelecido. Se não achar, procura de novo, até encontrar, ou então executar esse processo na máquina hospedeira.
Muitas vezes esse
processo de escolha usa teoria das las. 5. Um algoritmo leiloeiro - Aqui, processos são compradores de tempo, e os processadores, os vendedores de tempo. Há um mercado, de compra e venda de tempo, e o processo, que cria um processo- lho, vai e escolhe o processador que oferece as melhores condições.
Basicamente, temos um micro-modelo
econômico...
5.3 Escalonamento Cada processador faz o seu escalonamento local, assumindo que há vários processos para rodar nele, sem se preocupar com o que os outros estão fazendo. Funciona bem em alguns casos, exceto quando temos um grupo de processos altamente interativos e e relacionados entre si rodando em diferentes processadores. Nesse caso, é bom garantir que processos que interagem muito entre si estejam sendo executados simultaneamente, pois numa situação de tempo compartilhado, entre vários processadores, uma troca de mensagens pode car muito demorada. Uma idéia é colocar todos os processos que se encaixam nessa situação rodando
na mesma fatia de tempo.
Combinando essa característica com o algoritmo hie-
rárquico para alocação do processador (visto na seção 5.2.3), podemos ter resultados interessantes, com cada processo supervisor montando uma tabela de alocação, e coordenando esse escalonamento.
5.4 Resumo 1. Threads são uma realidade em sistemas operacionais, distribuídos ou não. 2. Os threads e as chamadas remotas a procedimento, juntos, podem gerar resultados muito interessantes. 3. Os modelos de organização de processadores basicamente são: 4. Estações de trabalho - cada usuário com sua estação, processos são executados prioritariamente na sua máquina. 5. Armários de processadores - todo processamento é compartilhado, com processadores sendo alocados dinamicamente aos usuários. 6. Mistos - união dos dois modelos anteriores. 7. Dado um conjunto de processadores, podemos atribuir processadores a processos, de várias formas. Temos diversos algoritmos que dizem como a coisa pode funcionar. 8. O escalonamento local funciona bem, mas em situações com muita troca de mensagens, pode ser interessante o rearranjo dos processos, como um
escalonamento.
37
co-
Capítulo 6
Sistemas de arquivos distribuídos Um sistema de arquivos é o componente-chave para qualquer sistema operacional, ainda mais um sistema distribuído. A nal, ele armazena programas e dados, tornando-os disponíveis quando é necessário. O
serviço de arquivos
é a especi cação daquilo que o sistema de arquivos
oferece, ou seja, a interface entre o sistema de arquivos com os cliente. Já o
de arquivos é um processo que roda em alguma máquina do sistema, implementar o serviço de arquivos.
servidor
e ajuda a
Um sistema bem implementado permite que
tudo funcione bem, de forma transparente ao usuário.
6.1 O projeto O serviço de arquivos e o servidor de diretórios são as duas partes fundamentais e distintas do sistema de arquivos.
6.1.1 O serviço de arquivos Um
arquivo é uma sequência de bytes, e o sistema operacional não tem responsabiatributos,
lidade sobre o signi cado dessa sequência de bytes. O arquivo pode ter
que são informações a respeito do arquivo, mas não dentro dele. Logo, o proprietário do arquivo, seu nome, tamanho, data de criação, direitos de acesso a ele, tudo isso são atributos. As primitivas do serviço de arquivos permite que modi quemos algumas dessas características, mas não todas. A proteção é de nida da mesma maneira em que em sistemas com um único processador: Com listas de controle de acesso e listas de capacidade. Cada arquivo tem um conjunto de capacidades que pode ser de nido pelo seu proprietário. As listas de controle de acesso são usadas para de nir quem pode fazer o quê com aquele arquivo. Os serviços de arquivos podem ser divididos em dois modelos de acesso:
Local:
O arquivo, quando lido, é copiado do servidor para o cliente, e lá ele sofre
as devidas alterações para depois ser recolocado no servidor. O modelo aqui é bem simples, e funciona bem. Mas o cliente tem que ceder um espaço razoável na memória, com o objetivo de manter nela os arquivos, temporariamente.
Remoto:
O serviço de arquivos fornece várias operações que podem ser realiza-
das, remotamente, no servidor. O arquivo não deixa o servidor, mas sofre as modi cações necessárias à distância.
38
6.1.2 O servidor de diretórios O serviço de diretórios de ne como serão os nomes de arquivos e diretórios: Tamanho, uso de caracteres especiais, espaços em branco, extensão, etc.
Também
de nem a criação de diretórios e subdiretórios, montando o que conhecemos como
sistema de arquivos hierárquico.
um
É possível a criação de ligações ou ponteiros para um diretório qualquer, mesmo em sistemas esparsos. Essas ligações permitem que o sistema seja organizado segundo um grafo arbitrário, disperso entre os servidores, o que é uma estrutura muito mais poderosa, mas ao mesmo tempo, mais complexa. Um problema ocorre se for eliminada a ligação de um diretório para outro. Teremos diretórios órfãos, perdidos entre os servidores. O problema também ocorre em sistemas centralizados, diga-se de passagem. Mas nos sistemas distribuídos, é muito mais sério: Você não pode simplesmente parar
toda a atividade dos arquivos,
para simplesmente procurar por diretórios órfãos. Uma questão importante é que: nem todas as máquinas tem a mesma visão da hierarquia de diretório. Uma parte da árvore pode estar num servidor, e outra parte, em outra máquina. Ou então a ligação entre a raiz e o diretório não ser a mesma nos clientes (tipo, um diretório está vinculado à raiz numa máquina, e a um outro diretório na outra máquina). A idéia da
montagem remota é usada para
organizar a observação do sistema, por parte dos clientes.
6.1.2.1 Identi cação transparente O principal problema com a identi cação do caminho para alcançar um diretório é que ele não é totalmente transparente, que é o desejável. Se queremos que o sistema seja
transparente quanto à localização, não devemos ter nada no caminho que
identi que o servidor onde o arquivo está sicamente armazenado. Imagine a situação, de um servidor com pouco espaço livre, e outro com muito. Um arquivo muito grande que iria ser salvo no primeiro servidor, poderia ser remanejado para o segundo, por causa da necessidade. Mas se o nome do servidor estiver atrelado ao caminho, ele terá que ser mudado, e todos os outros processos que farão uso desse arquivo, precisarão saber disso. Resumidamente, existem três maneiras de identi car arquivos e diretórios num sistema distribuído: 1. Nome da máquina ao lado do caminho. 2. Montagem dos sistemas de arquivos remotos na hierarquia de arquivos locais. 3. Um único espaço de nomes que devem ser os mesmos em todas as máquinas. Os dois primeiros casos são simples de serem implementados, enquanto que o terceiro caso é difícil de ser feito, mas necessário se o objetivo é fazer com que o sistema distribuído aja como se fosse um único computador.
6.1.2.2 Identi cação em dois níveis Os arquivos tem nomes simbólicos, para serem usados pelas pessoas, e nomes binários, que são usados pelo sistema em si. Os usuários preferem os nomes simbólicos, por motivos óbvios. estabelece-se uma
O sistema trabalha melhor com nomes binários, e
ligação simbólica entre eles.
Pode-se usar essa idéia para arquivos espalhados entre máquinas, onde na tabela de nomes binários, está salvo a localização física do arquivo, em que servidor ele se encontra. A ligação simbólica então, funciona como um caminho para um arquivo.
39
Uma característica interessante, para implementar a
tolerância a falhas,
é
ter o mesmo arquivo replicado em vários servidores, e a tabela de nomes binários referenciar todos os servidores onde aquele arquivo se encontra. No momento do acesso, acessa-se o servidor mais próximo, mas caso haja falhas, o dado ainda está disponível, por causa da redundância.
6.1.3 Compartilhamento de arquivos Quando dois ou mais usuários compartilham o mesmo arquivo, é preciso de nir as operações de leitura e escrita para evitar problemas.
Um bom exemplo é o que
ocorre quando uma operação de escrita é realizada, e logo depois uma operação de leitura. Essa leitura retorna o resultado da operação anterior, ou seja, a operação de escrita. Para que isso ocorra corretamente, mesmo num sistema com vários usuários, é
ordenação absoluta no tempo de todas as operações, para que sempre o valor mais recente retorne ao usuário. obrigatório uma
Num sistema distribuído, obter essa organização é fácil se tivermos somente um sistema de arquivos, centralizado, e sem cache de disco. Tudo o que os clientes fazem, são executados no servidor. A performance é pobre, mas pode ser melhorada com o uso de cópias locais dos arquivos, nos clientes, e atualizações dos mesmos, de tempos em tempos. Uma maneira de manter o servidor atualizado é enviar as mudanças nos arquivos que estão no cache, o que é bem menos do que enviar os arquivos como um todo.
Ou então, outra opção é exibilizar a regra: podemos fazer com que as mudanças num arquivo só estão disponíveis a todos os usuários quando o usuário que fez as modi cações fechou o arquivo. Dessa forma, não precisaremos atualizar o arquivo a todo instante, apenas quando ele for fechado pelo usuário em questão. Alguns propõem uma terceira via, a dos
arquivos imutáveis:
Os arquivos não
podem ser escritos e/ou apagados, somente criados ou lidos. Isso não é lá muito viável, portanto uma quarta opção é o uso de
transações indivisíveis:
Quando
o processo quer acessar um arquivo, ele envia um comando solicitando-o, e depois somente ele pode alterar o arquivo, até o seu fechamento.
6.2 Implementação de um sistema de arquivos Antes de criar um novo sistema de arquivos, é importante pensar vários aspectos, que vamos ver abaixo.
6.2.1 Utilização de arquivos Antes de criar um sistema de arquivos, é preciso ter uma boa idéia de como ele será usado, de maneira a ter certeza de que as operações serão feitas com e ciência. Na tabela abaixo, temos algumas observações sobre a utilização de arquivos: A maioria dos arquivos são pequenos (menores do que 10 Kb). A leitura é bem mais comum do que a escrita. Leituras e escritas são feitas seqüencialmente. A maioria dos arquivos tem um tempo de vida muito pequeno. Não é comum os arquivos serem compartilhados. Os processos usam poucos arquivos, em geral. Existem tipos de arquivos diferentes, com propriedades diferentes.
40
Mas ainda há dúvidas se essas observações variam de acordo com o ambiente onde o sistema operacional é empregado:
Numa indústria, no escritório de uma
empresa, num banco... Isso tudo acima pode mudar. Mas, para uma aproximação inicial, é razoável que as seis observações acima sejam plausíveis.
6.2.2 Estrutura do sistema Analisando algumas formas de organização interna de arquivos e diretórios, algumas perguntas que vem são: 1.
Os clientes e os servidores são diferentes?
Resposta:
Depende do sistema de arquivos empregado. O NFS (Network File Sys-
tem), criado pela Sun e amplamente utilizado, não faz essa distinção. Apenas ocorre a exportação de diretórios selecionados, de modo que outras máquinas podem acessá-los. Mas existem outros que a distinção é clara. 2.
Como estruturar os serviços de arquivos e de diretórios?
Resposta:
Uma maneira é combinar os dois serviços numa coisa só. Outra opção
é mantê-los separados. Assim, abrindo um arquivo, consulta-se o servidor de diretórios, fazendo o mapeamento do nome simbólico no nome binário, para assim acessar o arquivo. A vantagem de separá-los é dar mais exibilidade ao conjunto, mas torna-se mais cara computacionalmente, quando há a necessidade de fazer várias buscas pelos caminhos dos arquivos (pode-se diminuir o tempo gasto usando um cache). 3.
É preciso que os servidores de diretório e de arquivos mantenham informações de estado dos clientes?
Resposta:
Alguns acham que não deve haver informações de estado nos servidores.
Ou seja: Faz-se a requisição a um servidor, processa ela, envia a resposta e depois... Esquece. Outros acham que deve-se manter informações de estado nos servidores. Abaixo vamos ver vantagens e desvantagens:
•
Os servidores que não guardam informações são mais tolerantes a falhas, não precisam guardar tabelas com informações dos clientes, e não tem problemas quando um cliente pára de funcionar.
•
Os servidores que guardam informações tem desempenho maior, pode bloquear acesso a arquivos (caso seja necessário), pode fazer a leitura antecipada de arquivos que serão chamados posteriormente.
6.2.3 Armazenamento em cache Existem quatro lugares onde um arquivo pode estar: 1. No disco do servidor; 2. Na memória principal do servidor; 3. No disco do cliente; 4. Na memória principal do cliente.
41
O lugar mais apropriado é
o disco do servidor,
que tem muito espaço, está
disponível para todos os clientes, e evita problemas de consistência. Mas o mesmo é lento, e o acesso a ele tem que passar pela memória principal do servidor, depois para o disco do cliente, e nalmente a memória principal do cliente. Uma maneira de diminuir o tempo gasto é usar o
cache do servidor.
Assim,
um arquivo que é muito acessado, está no cache, e não terá que ser lido do disco. Mas, para manter o cache cheio, é preciso um algoritmo que decida quem deve car no cache. Ainda temos o problema do tráfego na rede, mas pode ser resolvido se tivermos um cache no cliente. Esse algoritmo tem que resolver dois problemas: 1. O que é gerenciado pelo cache, arquivos inteiros ou blocos de disco? 2. O que fazer, quando o cache encher, e for preciso remover arquivos dela? Agora, se usamos cache para acelerar o desempenho do sistema de arquivos (distribuído ou não), como podemos garantir a
Exemplo:
consistência do cache?
Num servidor, temos um arquivo, A1. Ele foi lido, logo está no cache
de dois clientes. Ambos zeram alterações em A1. Um terceiro cliente pede acesso a A1. O que ele vai ler? Se a consistência não for garantida, a versão original de A1, e não as versões alteradas pelos dois clientes, anteriormente. Existem quatro métodos para garantirmos a consistência do cache, que iremos resumir na tabela abaixo: Método
Como funciona O arquivo é alterado no cache
Write through
Escrita retardada
e
Só ajuda no tráfego de
no sistema de arquivos do
leitura. Na escrita, a
servidor.
velocidade é a mesma.
O arquivo é alterado no cache,
Maior desempenho, mas
mas só é alterado no sistema de
quem mais precisar do
arquivos do servidor de tempos
arquivo, pode receber
em tempos.
uma versão antiga.
O arquivo é alterado no cache e Write on close
Comentários
só quando é fechado, no sistema de arquivos do servidor.
Demora para ter o arquivo alterado.
O servidor de arquivos mantém
Problemas no controle do
Controle
o controle de tudo que está
crescimento do sistema, e
centralizado
acontecendo com os arquivos.
é menos robusto.
6.2.4 Replicação O interesse na replicação de arquivos por um sistema distribuído é claro:
•
Aumenta a con abilidade;
•
Tolerância a falhas;
•
Carga de trabalho dividida por vários servidores.
Existem três maneiras de fazer a replicação: 1. Replicação explícita: O arquivo é copiado na hora para o servidor, e para os outros servidores. 2. Replicação retardada: O arquivo é copiado para o servidor, e posteriormente os outros são atualizados. 42
3. Replicação em grupo: O arquivo é gravado no grupo de servidores, simultaneamente. Nos casos 1 e 2, é obrigatório eleger um servidor principal, para que ele receba a atualização e possa replicar o arquivo, o que não é muito robusto. Pode-se usar um algoritmo eletivo, para fazer a troca do servidor principal, de tempos em tempos.
6.3 Tendências Muita coisa está mudando na informática, e isso re etirá na área de sistemas de arquivos distribuídos. Abaixo vão algumas: 1. Hardware novo - O hardware velho está cada vez mais barato, o que torna mais atrativo montar sistemas distribuídos, com mais máquinas por um preço menor. Com o avanço da tecnologia, pode-se pensar em estruturas de rede mais rápidas (anéis de bra ótica, por exemplo) interligando os servidores de arquivos.
Dessa forma, pode-se dispensar o cache nos clientes, visto que o
gargalo da rede será muito menor, e muito melhor aguentar a baixa latência dos servidores do que usar uma implementação complexa (e cara) para o cache. 2. Escalabilidade - Algoritmos que funcionam bem com 100 máquinas podem não funcionar bem com 10.000.
Os sistemas de arquivos centralizados não
respondem bem ao aumento dos número de máquinas: Se para acessar um arquivo qualquer, todo mundo precisa falar com um servidor, ele será um grande gargalo no sistema. Transmissões em broadcast devem ser evitadas a todo custo, e a estrutura em árvore de diretórios, única, com um sistema de arquivos distribuído, tende a fazer com que o caminho seja cada vez maior. 3. Redes de longa distância - Os sistemas distribuídos tem sido pensados inicialmente em cima de redes locais. E quando tivermos redes que abranjam todo um país, por exemplo? Como resolver o problema da latência, numa rede com uma extensão tão grande como essa? 4. Usuários móveis - Portabilidade e mobilidade são palavras de ordem hoje em dia, com o crescimento da Internet. Como manter os usuários conectados às suas bases de dados, mesmo quando estando em trânsito? Qualquer solução deve ser baseada no cache: O usuário leva os seus arquivos, e enquanto não tiver um acesso próximo, atualiza-os. No momento em que estiver ao alcance, ocorre a atualização na base de dados. Mas, e se o tempo de desconexão for de horas, ou dias, como será a consistência do cache? 5. Tolerância a falhas - Os sistemas atuais não são tolerantes a falhas, salvo raras exceções.
Para termos redundância propriamente dita, é necessário investi-
mento em hardware (fontes redundantes, matrizes de HDs ligados em RAID, sistemas hot-swap, etc) e redundância em software, principalmente dos dados. A replicação de arquivos será fundamental para os futuros sistemas, e a capacidade de funcionar mesmo com parte dos dados fora do alcance, é importante para termos um sistema realmente tolerante a falhas.
6.4 Resumo •
O centro de qualquer sistema distribuído é o seu sistema de arquivos.
•
Qual é o modelo de um sistema e que tipo de funcionalidade é oferecida?
43
•
A natureza de um arquivo não muda, seja ele hospedado num sistema centralizado ou distribuído.
•
Compartilhamento de arquivos é um assunto importante e complexo.
•
A implementação demanda várias decisões, se o sistema deve guardar as informações de estado ou não, se e como deve ser implementado a cache, e como deve acontecer a replicação de arquivos. Cada uma dessas decisões tem conseqüências muito fortes.
•
Finalmente, vemos algumas tendências que estão se tornando pontos importantes no projeto de sistemas de arquivos distribuídos, como os avanços na tecnologia, escalabilidade, redes de longa distância, usuários móveis e a tolerância a falhas.
44
Referências Bibliográ cas [1] Sistemas Operacionais Modernos - Andrew S. Tanenbaum - Editora LTC - 1a edição. [2] Sistemas Operacionais: Conceitos e Aplicações - Abraham Silberschatz, Peter Galvin e Greg Gagne - Editora Campus - 7a edição. [3] Arquitetura de Sistemas Operacionais - Francis B. Machado e Luiz Paulo Maia - LTC Editora - 3a edição. [4] Introdução à Organização de Computadores - Mário Monteiro - LTC Editora 4a edição. [4] Wikipédia: Wikipédia (em português)
45
http://pt.wikipedia.org
Ricardo Jurczyk Pinheiro - Faculdades Paraíso Versão atual: 16/03/07
Sumário 1 Sistemas com várias UCPs: Hardware 1.1
1.2
Questões atuais . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.1.2
Soluções propostas . . . . . . . . . . . . . . . . . . . . . . . .
4
Arquitetura de máquinas paralelas
1.2.2
. . . . . . . . . . . . . . . . . . .
4
Multiprocessador . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2.1.1
SMP (Multiprocessamento Simétrico)
5
1.2.1.2
NUMA (Acesso Não-Uniforme à Memória)
. . . . . . . . . . . . .
Multicomputador . . . . . . . . . . . . . . . . . . . . . . . . .
Comparativo entre os sistemas
. . . . . . . . . . . . . . . . . . . . .
2 Sistemas com várias UCPs: Software 2.1 2.2
2.3
2.4
2.5
6 7 7
8
De nição de Sistema Operacional . . . . . . . . . . . . . . . . . . . .
8
2.1.1
. . . . . . . . . .
8
. . . . . . . . . . . . . . . . . . . .
8
Funções comuns aos sistemas operacionais.
Sistema Operacional Tradicional 2.2.1
Características
2.2.2
Objetivos
. . . . . . . . . . . . . . . . . . . . . . . . . .
9
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
Sistema Operacional de Rede
. . . . . . . . . . . . . . . . . . . . . .
9
. . . . . . . . . . . . . . . . . . . . . . . . . .
10
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.3.1
Características
2.3.2
Objetivos
Sistema Operacional Distribuído
. . . . . . . . . . . . . . . . . . . .
10
2.4.1
De nições . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.4.2
Características
2.4.3
Objetivos
2.4.4
Vantagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.4.5
Desvantagens . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
. . . . . . . . . . . . . . . . . . . . . . . . . .
11
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
Questões de projeto de um sistema distribuído 2.5.1
Transparência
2.5.2
Flexibilidade
2.5.3
Con abilidade
2.5.4
Desempenho
2.5.5
Escalabilidade
2.5.1.1
2.5.4.1 2.6
4
1.1.1
1.2.1
1.3
4
Problemas e soluções . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
12
. . . . . . . . . . . . . . . . . . . . . . . . . .
12
Tipos de transparência
. . . . . . . . . . . . . . . .
12
. . . . . . . . . . . . . . . . . . . . . . . . . . .
12
. . . . . . . . . . . . . . . . . . . . . . . . . .
13
. . . . . . . . . . . . . . . . . . . . . . . . . . .
13
Métricas para medir desempenho:
. . . . . . . . . .
13
. . . . . . . . . . . . . . . . . . . . . . . . . .
13
Resumo comparativo . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3 Comunicação em sistemas distribuídos
15
3.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2
Protocolos em camadas
. . . . . . . . . . . . . . . . . . . . . . . . .
15 15
3.3
Modelo cliente-servidor . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.3.1
Vantagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
3.3.2
Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
1
3.4
3.3.3
Endereçamento
. . . . . . . . . . . . . . . . . . . . . . . . .
17
3.3.4
Primitivas de troca de mensagens . . . . . . . . . . . . . . . .
17
3.6
Síncronas e assíncronas (bloqueadas e não-bloqueadas) 18
3.3.4.2
Uso de buer . . . . . . . . . . . . . . . . . . . . . .
3.3.4.3
Con áveis e não-con áveis
19
Chamada remota a procedimento . . . . . . . . . . . . . . . . . . . .
20
Problemas com a chamada remota a procedimento . . . . . .
21
3.4.1.1
Espaços de endereçamento diferentes . . . . . . . . .
21
3.4.1.2
Passagem de ponteiros . . . . . . . . . . . . . . . . .
21
3.4.1.3
Negação de serviço . . . . . . . . . . . . . . . . . . .
21
Comunicação em Grupo . . . . . . . . . . . . . . . . . . . . . . . . .
23
3.5.1
Introdução
23
3.5.2
Tipos de grupos
3.5.3
Controle dos membros do grupo
3.5.4
Ordenação de mensagens
3.5.5
Escalabilidade na comunicação grupal
Resumo
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
4.2
4.3
4.4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
26
. . . . . . . . . . . . . . . . . . . . . . . . .
26
4.1.1
Relógios lógicos . . . . . . . . . . . . . . . . . . . . . . . . . .
26
4.1.2
Algoritmos para sincronização de relógios
. . . . . . . . . . .
28
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
4.2.1
Algoritmo centralizado . . . . . . . . . . . . . . . . . . . . . .
28
4.2.2
Algoritmo descentralizado . . . . . . . . . . . . . . . . . . . .
28
4.2.2.1
. . . . . . . . . . . . . . . . . . . . . . . .
29
. . . . . . . . . . . . . . . . . . . . . . . . . . .
29
Exclusão Mútua
Exemplo
4.2.3
Uso de token
4.2.4
Comparação entre os algoritmos
. . . . . . . . . . . . . . . .
5.2
30
Algoritmos eletivos . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
4.3.1
O algoritmo do ditador
30
4.3.2
. . . . . . . . . . . . . . . . . . . . .
O algoritmo em anel . . . . . . . . . . . . . . . . . . . . . . .
31
Deadlocks em sistemas distribuídos . . . . . . . . . . . . . . . . . . .
31
4.4.1
Detecção de deadlocks . . . . . . . . . . . . . . . . . . . . . .
32
4.4.1.1
Algoritmo centralizado
32
4.4.1.2
Algoritmo descentralizado . . . . . . . . . . . . . . .
Prevenção de deadlocks
Resumo
. . . . . . . . . . . . . . . .
32
. . . . . . . . . . . . . . . . . . . . .
32
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
5 Processos em sistemas distribuídos 5.1
24 25
Relógios e sincronização
4.4.2 4.5
23 24
. . . . . . . . . . . . .
4 Sincronização em sistemas distribuídos 4.1
18
. . . . . . . . . . . . . .
3.4.1
3.5
3.3.4.1
34
Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
5.1.1
Organizações de threads dentro de um processo . . . . . . . .
34
5.1.2
Threads e chamadas remotas a procedimentos . . . . . . . . .
34
Alocação do processador . . . . . . . . . . . . . . . . . . . . . . . . .
35
5.2.1
Modelos de alocação . . . . . . . . . . . . . . . . . . . . . . .
35
5.2.2
Alguns aspectos
. . . . . . . . . . . . . . . . . . . . . . . . .
36
5.2.3
Alguns exemplos
. . . . . . . . . . . . . . . . . . . . . . . . .
36
5.3
Escalonamento
5.4
Resumo
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
2
6 Sistemas de arquivos distribuídos 6.1
O projeto 6.1.1
O serviço de arquivos
6.1.2
O servidor de diretórios
6.1.3 6.2
38
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38 38
. . . . . . . . . . . . . . . . . . . . .
39
6.1.2.1
Identi cação transparente . . . . . . . . . . . . . . .
39
6.1.2.2
Identi cação em dois níveis . . . . . . . . . . . . . .
39
Compartilhamento de arquivos
. . . . . . . . . . . . . . . . .
40
Implementação de um sistema de arquivos . . . . . . . . . . . . . . .
40
6.2.1
Utilização de arquivos
40
6.2.2
Estrutura do sistema . . . . . . . . . . . . . . . . . . . . . . .
41
6.2.3
Armazenamento em cache . . . . . . . . . . . . . . . . . . . .
41
6.2.4
Replicação
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
6.3
Tendências
6.4
Resumo
3
Capítulo 1
Sistemas com várias UCPs: Hardware 1.1 Problemas e soluções 1.1.1 Questões atuais •
Limite físico para as UCPs tradicionais (Lei de Moore);
•
Tecnologia cada vez mais cara;
•
Necessidade de mais processamento para resolução de problemas computacionalmente caros;
•
A rede é o computador (Scott McNealy, CEO Sun Microsystems);
•
Técnicas de software mais avançadas.
1.1.2 Soluções propostas •
Miniaturização de componentes;
•
Uso de UCPs em paralelo;
•
UCPs com mais de um núcleo de processamento na mesma pastilha;
•
Desenvolvimento de software que aproveitem arquiteturas com mais de uma UCP.
1.2 Arquitetura de máquinas paralelas Sistemas distribuídos consistem de várias CPUs interconectadas.
No entanto, há
várias formas diferentes no qual esse hardware pode estar organizado. Classi cação segundo Flynn:
SISD - máquina tradicional; SIMD - processadores matriciais; MISD - não existe; MIMD - vários processadores interconectados. Subclassi cados em: 4
1.2.1 Multiprocessador •
Sistema fortemente acoplado;
•
Várias UCPs acessam a mesma memória;
•
Memória compartilhada;
•
A comunicação se dá através de um barramento de comunicação.
1.2.1.1 SMP (Multiprocessamento Simétrico) Tipos de barramento Único: •
Comercialmente, até 64 UCPs;
•
Somente uma unidade funcional usa o barramento por vez;
•
Arquitetura simples, econômica e exível;
•
Uso de memórias cache em cada UCP, o que acelera a performance, mas traz novos problemas, como a coerência do cache.
5
Cruzado comutado: •
Matriz de interconexão;
•
Uso de comutadores;
•
Mais de uma UCP pode comunicar-se com uma memória simultaneamente;
•
Custo eleva-se:
n
processadores
= n2 comutadores.
Rede Ômega: •
Menos comutadores:
•
Latência para acesso à memória.
n
processadores
=
(n . log2 n) comutadores. 2
1.2.1.2 NUMA (Acesso Não-Uniforme à Memória) •
Tempo de acesso à memória depende da localização física da UCP.
•
Conjuntos de UCPs e memória, interligados num barramento comum.
•
Desempenho satisfatório - minimizar diálogo com a memória remota.
•
Expansibilidade maior, mais fácil para montar e manter.
6
1.2.2 Multicomputador Sistema fracamente acoplado;
•
Cada UCP acessa a sua memória;
•
Memória única, para cada nó do sistema;
•
A comunicação se dá através de um meio de comunicação (rede);
•
Principal gargalo: Troca de mensagens.
1.3 Comparativo entre os sistemas Características
Sistemas fortemente acoplados
Sistemas fracamente acoplados
Memória
Centralizada
Espalhada
Comunicação entre UCPs
Rápida
Lenta
Arquitetura
Complexa
Simples
Número de UCPs
Dezenas
Ilimitado
Escalabilidade
Baixa
Alta
Administração
Simples
Complexa
Custo
Maior
Menor
Segurança
Centralizada
Distribuída
7
Capítulo 2
Sistemas com várias UCPs: Software 2.1 De nição de Sistema Operacional Silberchatz:
Um sistema operacional é um programa que age como um interme-
diário entre o usuário do computador e o hardware. O propósito de um S.O. é prover um ambiente no qual um usuário possa executar programas de forma conveniente e e ciente.
2.1.1 Funções comuns aos sistemas operacionais. •
Execução de programas;
•
Operações de E/S;
•
Manipulação do sistema de arquivos;
•
Comunicação;
•
Detecção de erros;
•
Alocação de Recursos;
•
Proteção.
2.2 Sistema Operacional Tradicional 1. Sistema operacional centralizado 2. Aplicado a sistemas convencionais 3. Recursos centralizados 4. Arquiteturas mono ou multi-processadas (multiprocessador) 5. Sistemas multi-tarefas e multi-usuários
8
2.2.1 Características •
Compartilhamento de recursos
•
Todos os recursos são acessíveis internamente
•
Comunicação entre processos via memória compartilhada ou através de facilidades providas pelo núcleo do sistema
2.2.2 Objetivos •
Virtualizar os recursos do hardware
•
Gerenciar uso dos recursos locais
•
Sincronizar atividades
2.3 Sistema Operacional de Rede Uma coleção de S.O de computadores conectados a uma rede incorporando módulos para prover acesso a recursos remotos. Com isso tem-se uma implementação barata, porém, exige que o usuário conheça a localização dos recursos requisitados
Silberchatz:
Os usuários sabem da existência de várias máquinas, podem abrir
sessões em várias máquinas e transferir dados entre elas.
9
2.3.1 Características •
Implementação relativamente simples
•
SOs incorporam módulos para acessar recursos remotos
•
Coleção de sistemas operacionais distintos
•
Comunicação entre sistemas através de protocolos
•
O usuário deve conhecer a localização dos recursos
•
Os recursos pertencem a computadores especí cos
2.3.2 Objetivos •
Disponibilidade de recursos através de um meio em comum.
•
Gestão centralizada dos recursos.
•
Economia de gastos.
Exemplos:
Compartilhamento de impressoras e arquivos Web; espaço em disco;
e-mail; serviços de autenticação.
2.4 Sistema Operacional Distribuído Entende-se por ambiente distribuído como um conjunto de processadores interligados por uma rede de interconexão e sem memória compartilhada. A ausência de memória compartilhada obriga a uma interação entre processadores de uma forma distinta do ambiente centralizado: ao invés de variáveis ou arquivos compartilhados utiliza-se troca de mensagens.
10
2.4.1 De nições Tanenbaum:
Um sistema distribuído é uma coleção de computadores independen-
tes que parecem ao usuário como um único computador.
Silberchatz:
Os usuários não precisam saber da existência de várias máquinas, os
recursos remotos são usados da mesma forma que os recursos locais.
Lamport:
Um sistema distribuído é aquele em que eu não posso fazer meu traba-
lho, pois uma máquina que eu nem conheço, não sei onde está, e nunca ouvi falar encontra-se fora do ar.
2.4.2 Características •
Construção de um ambiente computacional virtual
•
Localização dos recursos é abstraída
•
Localização do processamento é abstraída
•
Mecanismos transparentes de distribuição, replicação e tolerância a faltas
2.4.3 Objetivos O SO distribuído deve:
•
Controlar a alocação de recursos para tornar seu uso e ciente
•
Prover um ambiente de computação virtual de alto nível
•
Esconder a distribuição dos recursos e do processamento
2.4.4 Vantagens 1.
Economia:
Aproveitar recursos ociosos; É mais barato ter vários processa-
dores interconectados do que um supercomputador; 2.
Distribuição inerente:
algumas aplicações são distribuídas por natureza; 11
3.
Tolerância a falhas:
em caso de falha de uma máquina, o sistema pode
sobreviver, mesmo com desempenho degradado; 4.
Crescimento incremental:
o poder computacional pode ser aumentado
através da inclusão de novos equipamentos; 5.
Flexibilidade:
Maior exibilidade na alocação dos recursos, permitindo que
usuários compartilhem dados, processamento e dispositivos.
2.4.5 Desvantagens 1.
Aplicações mais complexas:
Pouco software de alto nível disponível para
sistemas distribuídos; 2.
Segurança:
Necessidade de construir mecanismos para controle de acesso às
informações; 3.
Dependência da rede:
Falhas, capacidade de tráfego insu ciente.
2.5 Questões de projeto de um sistema distribuído 2.5.1 Transparência De nição:
Tem o objetivo de fornecer aos usuários uma imagem única e abstrata
do sistema computacional.
2.5.1.1 Tipos de transparência Localização: os usuários não sabem onde os recursos estão localizados. Migração: os recursos podem se mover sem alterar seus nomes. Replicação: os usuários não sabem quantas cópias de um recurso existem. Concorrência: múltiplos usuários podem compartilhar um recurso automaticamente.
Paralelismo:
atividades podem ocorrer em paralelo sem que o usuário saiba (falta
muito ainda para ser atingido).
2.5.2 Flexibilidade O sistema é exível quando a inserção de novos módulos é uma tarefa simples. No caso de sistemas operacionais distribuídos, o kernel deve ser exível a ponto de tornar essa tarefa o menos custosa. Uma das propostas é o uso de
microkernel.
O microkernel implementa poucas funções, fornecendo em princípio quatro serviços básicos:
•
Mecanismo de comunicação entre processos
•
Algum tipo de gerência de memória
•
Uma pequena parte do escalonamento e gerência de baixo nível de processos
•
Estrada e saída de baixo nível
O uso de microkernel pode ser uma opção interessante, pois a inserção de módulos, no nível do usuário, é uma tarefa mais simples do que em um kernel do tipo monolítico. 12
2.5.3 Con abilidade Alguns aspectos da con abilidade são:
•
Disponibilidade:
Fração do tempo em que o sistema pode ser usado plena-
mente.
•
Segurança:
Proteção contra acessos não-autorizados a espaços de memória,
arquivos e demais recursos.
•
Tolerância a falhas:
A quanti cação de quanto as falhas podem ser contor-
nadas, a m de que o sistema continue em funcionamento, mesmo quando há problemas.
2.5.4 Desempenho Pode-se considerar como se fosse sinônimo de velocidade.
2.5.4.1 Métricas para medir desempenho: •
Tempo de resposta
•
Número de tarefas / tempo
•
Utilização do sistema
•
Quantidade consumida da capacidade da rede
2.5.5 Escalabilidade Suporta o aumento dos recursos e usuários mantendo um desempenho satisfatório. Os sistemas distribuídos precisariam se adaptar a possibilidade de termos ambientes com centenas ou milhares de processadores. Para isso, deve-se evitar:
•
Componentes centralizados:
Por exemplo, um único servidor de email
para todos os usuários.
• •
Tabelas centralizadas: Por exemplo, uma única relação on-line de telefones. Algoritmos centralizados: Por exemplo, roteamento de mensagens baseado em informações completas.
Ou seja, tudo que é centralizado deve ser evitado, sob pena de criar uma sobrecarga desnecessária no sistema. Deve-se usar algoritmos descentralizados, que possuem as seguintes características:
•
Nenhuma máquina possui informações completas sobre o estado do sistema.
•
Máquinas tomam decisões baseadas apenas nas informações disponíveis localmente.
2.6 Resumo comparativo Quadro classi cando os tipos de sistemas operacionais, seus serviços e objetivos.
13
Gerência de
Gerência de processos
Centralizado
recursos
Memória, Dispositivos
Virtualização
Serviços
Tipo
Objetivos
Acesso Remoto
S.O. de Rede
Compartilhamento
Troca de informações
de recursos
Visão global dos recurS. O. Distribuído
sos
Uni car tudo numa
Uso do poder compu-
visão global
tacional Centralizado
Gerência de
Gerência de processos Memória, Dispositivos
recursos Virtualização
Quadro comparativo dos sistemas operacionais quanto à características relativas a multiprocessamento: S.O.
Tradicional
Rede
Distribuído
Aparência
Um processador
Vários
Um processador
virtual Tipo de Sistema
processadores Único
Vários
Iguais
1
N (1 para cada
N (1 para cada
máquina)
máquina)
Operacional instalado Cópias do Sistema Operacional Comunicação
Memória
Arquivos
Trocas de
entre processos
compartilhada
compartilhados
mensagens
14
Capítulo 3
Comunicação em sistemas distribuídos 3.1 Introdução A grande diferença entre um sistema distribuído e um sistema tradicional é a implementação da comunicação entre processos.
•
Sistemas tradicionais supõem a pré-existência de memória compartilhada facilita o uso de meios como semáforos.
•
Sistemas distribuídos - não há compartilhamento entre os nós - necessidade de repensar a comunicação entre processos em bases novas.
•
Uso do modelo OSI para implementar a comunicação - uso de protocolos.
•
Troca de mensagens - opção pelo uso da RPC (chamada remota de procedimento) - simples e e ciente.
3.2 Protocolos em camadas •
Uso de protocolos - regras que de nem como a comunicação se dará
•
Modelo OSI - 7 camadas (aplicação, apresentação, sessão, transporte, rede, enlace e físico).
•
Protocolos orientados à conexão - Transmissor e receptor acertam previamente como será feita a troca de mensagens - aperto de mãos.
•
Protocolos não-orientados à conexão - o transmissor simplesmente envia a mensagem, sem ter certeza de que terá um receptor do outro lado.
3.3 Modelo cliente-servidor •
Cabeçalho das mensagens traz informação de todas as camadas do modelo OSI - gera sobrecarga na transmissão.
•
Processos-servidores - Processos que cooperam entre si, que fornecem recursos a processos usuários, os processos-clientes.
15
•
Modelo para comunicação num sistema distribuído - baseado num protocolo não-orientado a conexão:
solicitação/resposta.
O cliente faz uma solicita-
ção, e o servidor envia uma resposta.
3.3.1 Vantagens Simplicidade:
não há a sobrecarga de informação gerada por várias camadas de
comunicação. A comunicação é direta.
E ciência:
A pilha de protocolos é muito reduzida, tornando a comunicação me-
nos passível de falhas. Não há necessidade de roteamento e transporte, por exemplo.
3.3.2 Exemplo 1. Dois processos, um servidor e um cliente. 2. Informações a serem comuns a ambos: (a) Tamanho do nome de arquivo. (b) Quantidade de dados que podem ser transmitidos de cada vez. (c) Endereço do servidor de arquivos 3. Tipos de operação: (a) Criar arquivo (b) Ler parte do arquivo (c) Escrever parte do arquivo (d) Apagar arquivo 4. Códigos de erro: (a) Ok (b) Operação desconhecida (c) Erro em parâmetro (d) Erro em E/S 5. Formato da mensagem: (a) Quem envia (b) Quem recebe (c) Operação a ser feita (d) Quantos bytes 16
(e) Onde começa a mexer no arquivo (posição) (f ) Código de erro (g) Nome do arquivo (h) Dados a serem lidos ou escritos Com esse conjunto de informações, temos um protocolo bem simples, mas que possibilita a troca de mensagens entre processos-servidores e processos-clientes.
3.3.3 Endereçamento Como identi car o processo-cliente? Em que máquina ele estará? 1. A primeira opção é mudar o número do processo, acrescentando também o número da máquina que o hospeda. Exemplo: Processo 123 na máquina 45:
45.123,
ou
123@45.
Nem sempre funciona: Se uma máquina que hospeda um
processo estiver fora do ar, será preciso atualizar em todos os nós qual foi a máquina que recebeu aquele processo que estava rodando na máquina que parou de funcionar.
número único para endereçamento do processo, independente da máquina ao qual o processo está. Só que de-
2. Uma segunda opção é colocar um
verá existir um processo servidor que dará os endereços aos processos. E isso deverá ser centralizado. Num sistema distribuído, não funciona bem. 3. A terceira opção é o número do processo ser sorteado ao acaso dentro de uma quantidade de números possíveis muito grande.
Por exemplo, o espaço dos
números inteiros de 64 bits, na base binária. Logo, serão
264 possibilidades,
e
a chance de dois processos pegarem o mesmo número será muito remota. Aí temos um problema: Como o processo saberá com quem ele deverá se comunicar? Uma opção é que, a cada processo criado, seja enviado um pacote em broadcast para todos os outros nós do sistema, para que eles saibam o endereço do novo processo. Dessa forma também, o nó retorna o seu endereço também para o transmissor, e ele forma uma tabela de endereços, tornando-se um
vidor de nomes.
ser-
O problema é que o uso de broadcasts gera tráfego extra
na rede. 4. Uma última opção é usar um hardware especial, que captura aleatoriamente o endereço de cada nó com o qual foi estabelecida uma conexão, e o número do processo com o qual foi feita a interação. Daí, quando o processo solicitar uma comunicação, o próprio hardware vai fazer a tradução
endereo de rede.
nmero de processo →
O problema é que é necessário um hardware especial para
isso. Como visto, qualquer implementação tem vantagens e problemas, cabe ao desenvolvedor escolher e aproveitar da melhor maneira possível.
3.3.4 Primitivas de troca de mensagens As primitivas de troca de mensagens são os comandos usados para estabelecimento da comunicação com outro processo, e a efetiva troca da mensagem.
17
3.3.4.1 Síncronas e assíncronas (bloqueadas e não-bloqueadas) •
Uma primitiva bloqueada (ou síncrona ) trava o processo que está enviando a mensagem, até que a operação esteja concluída.
•
Uma primitiva não-bloqueada (ou assíncrona ) devolve o controle ao processo antes mesmo do envio da mensagem. Ou seja, ao mesmo tempo em que uma mensagem é enviada, o processo pode estar trabalhando em paralelo.
Ambas implementações existem em vários sistemas, cabe ao usuário usar qual convém mais. A segunda tem a vantagem da velocidade, mas uma grave desvantagem: o transmissor não pode modi car o buer enquanto a mensagem não foi enviada, além de não saber quando a transmissão foi encerrada.
3.3.4.2 Uso de buer Ambas as implementações realizadas acima pressupõem que o receptor responde à requisição
depois do transmissor faz o início do envio da mensagem. O problema antes do receptor estar pronto para receber
ocorre quando o transmissor faz o envio a mensagem.
Logo, todas as implementações descritas acima são do tipo 18
sem buer.
Existem algumas propostas de soluções para tal problema: 1. Descartar a mensagem. Logo, um cliente só recebe a mensagem se o servidor já a tiver enviado. Embora seja muito fácil ser implementada, um cliente pode ter que repetir várias vezes a requisição, o que gera um considerável atraso. 2. O uso de buer permite que a mensagem que armazenada, para que quando ela for solicitada, será prontamente entregue. Dá-se um prazo para que essa mensagem seja resgatada no buer, e se esse prazo estourar, a mensagem é descartada. Cada mensagem que entrar no nó, com um endereço referente a um processo, é colocado num buer, e aguarda ser resgatada. Funciona melhor do que a implementação anterior, mas requer uma gerência dos buers, e devese lembrar que os buers tem um tamanho
nito de espaço em memória para
armazenamento. Uma maneira é evitar que um processo mande mensagem se o buer que irá recebê-la estiver lotado.
3.3.4.3 Con áveis e não-con áveis Nas condições ideais, toda mensagem enviada chega no destinatário.
E, se não
chegar? Como veri car isso? 1. A primeira maneira é deixar essa preocupação, da con abilidade da comunicação, por conta do usuário. Admitir que o envio não é 100% con ável, e deixar que o usuário pense numa maneira de fazer com que o envio seja con ável. 2. A segunda maneira é o envio de uma mensagem de con rmação do recebimento da mensagem original. Logo, o kernel do nó receptor envia para o kernel do nó transmissor a con rmação da chegada da mensagem, e segue em frente. 3. Uma terceira maneira é não enviar a con rmação, mas deixar que a resposta seja a con rmação do envio da mensagem original. e enquanto não chegar a con rmação, nada feito.
Bloqueia-se o cliente, Simples, mas não há a
con rmação do recebimento da resposta (servidor para o cliente). 4. Por último, uma maneira de garantir a con abilidade é juntar as duas últimas implementações: No momento em que uma solicitação chegar, dispara-se um 19
contador de tempo.
Se o servidor aprontar a resposta a tempo, a própria
resposta será a con rmação. Se não, envia-se a con rmação, e posteriormente a resposta. Dessa forma, no melhor caso teremos 2 mensagens trocadas. No pior caso, serão 3 mensagens sendo trocadas.
3.4 Chamada remota a procedimento Apesar da implementação do modelo cliente-servidor, descrito acima, ser simples, ele carece de um erro sério:
entender que
em operações de entrada e saída.
toda
comunicação será feita baseada
O problema é que, a intenção de um sistema
distribuído é parecer com um sistema centralizado (para os usuários), e usar toda comunicação para realizar operações de entrada e saída, acaba sendo problemático. Como resolver tal problema?
A proposta é que existisse um meio de comu-
nicação, para que um programa chamasse um procedimento localizado em outra máquina.
A, na máquina 1 chama um procedimento B , que está 2, A é congelado, e B é executado. Os dados que são necessários são A para B na forma de parâmetros, e o resultado volta para A como re-
Logo, quando
na máquina levados de
sultado da execução. Tudo isso é transparente ao programador, e esse procedimento é a
chamada remota a procedimento, ou RPC.
O grande segredo da RPC é que ela deve ser parecida ao máximo com uma chamada local, a um processo localizado na mesma máquina.
Ou seja, para o
desenvolvedor, ela é completamente transparente.
O stub (do cliente ou do servidor) é a parte do processo que envolve o empacotamento e desempacotamento, de parâmetros e resultados. Logo, os stubs, junto com o kernel, fazem o trabalho da comunicação entre máquinas. Uma chamada remota a procedimento é realizada executando os seguintes passos: 1. O procedimento do cliente chama o stub do cliente da maneira usual. 2. O stub do cliente faz uma requisição ao kernel do cliente. 3. O kernel do cliente manda uma mensagem ao kernel do servidor. 4. O kernel do servidor entrega a mensagem ao stub do servidor. 5. O stub do servidor desempacota os parâmetros e chama o servidor. 6. O servidor faz o seu trabalho e retorna o resultado para o próprio stub. 7. O stub do servidor empacota o resultado, coloca numa mensagem e faz uma requisição ao kernel do servidor.
20
8. O kernel do servidor envia a mensagem ao kernel do cliente. 9. O kernel do cliente entrega a mensagem ao stub do cliente. 10. O stub do cliente desempacota os resultados e repassa ao cliente.
3.4.1 Problemas com a chamada remota a procedimento Apesar da idéia ser simples, há alguns problemas:
3.4.1.1 Espaços de endereçamento diferentes O processo
A
e o procedimento
B
estão em máquinas diferentes, com
espaços de endereçamento diferentes. A passagem de parâmetros e de resultados pode ser complicada, caso as máquinas sejam diferentes (hardware diferente). Um dos problemas que temos quando ao espaço de endereçamento é a questão do uso dos formatos little endian (adotado pela Intel, por exemplo), e big endian (adotado pela Sun, por exemplo).
Basicamente, é a ordem de numeração dos bits dentro
de um byte. Logo, o little endian usa da direita para a esquerda, e o big endian, da esquerda para a direita. Há a necessidade de haver essa tradução, sob pena de nada funcionar. Uma maneira é fazer essa tradução, quando estamos comunicando servidor e cliente. Só que essa tradução ocorre
sempre, mesmo que o servidor e o
cliente tenham o mesmo formato.
3.4.1.2 Passagem de ponteiros E passagem de ponteiros, e de parâmetros por referência? Como caria? Na questão da passagem de ponteiros, uma alternativa seria bloquear, impedir a passagem de ponteiros.
Não seria desejável que isso acontecesse, logo pensou-se
em uma nova alternativa: Passar o conteúdo apontado pelo ponteiro, também, na mensagem.
Isso gera trabalho extra para o servidor (criando um novo ponteiro
para a mensagem que veio do cliente para o servidor), mas resolve o problema para estruturas simples. Se tivermos uma estrutura de dados mais complexa (como um grafo), aí é necessário mais malabarismos para obter o resultado desejado.
3.4.1.3 Negação de serviço E se houver uma falha no sistema? Primeiro, precisamos ver quais são as possibilidades de falhas que temos no sistema, e elas são: 1. O cliente não consegue achar o servidor. 2. A mensagem no sentido cliente→servidor se perdeu. 3. A mensagem no sentido servidor
→cliente
se perdeu.
4. O servidor sai do ar logo após ter recebido uma solicitação de serviço. 5. O cliente sai do ar logo após ter enviado uma solicitação de serviço. Vamos ver cada caso.
21
O cliente não consegue achar o servidor
Nesse caso, teremos que ter um
mecanismo para buscar o servidor, e retornar alguma informação se ele está fora do ar. O servidor pode não existir, ou não ser compatível com aquele cliente. Daí, o mecanismo deve checar isso. Mas o mecanismo que checa a existência do servidor pode gerar uma
exceção.
Algumas linguagens de programação tem maneiras de facilitar o trabalho do programador, para ter rotinas que tratem tais exceções. Infelizmente, não é a via de regra, e em muitas, o programador tem que prever aonde a exceção vai ocorrer no código. Nesse caso, da não-existência do servidor, o cliente terá que procurar outro servidor que o responda.
A mensagem no sentido cliente→servidor se perdeu
Aqui é simples: Basta
o cliente ter um temporizador, e disparar quando a mensagem for enviada. Se não chegar nenhuma mensagem avisando do recebimento por parte do servidor até o temporizador zerar, envia-se a mensagem de novo.
A mensagem no sentido servidor →cliente se perdeu
Aqui, a solução mais
óbvia seria a mesma do segundo caso. Mas isso acarreta um problema: O servidor não conseguiu mandar a mensagem.
O cliente, não recebendo a resposta, envia
novamente um pedido ao servidor, e o mesmo vai ter que processar duas requisições. Como tratar? Uma maneira simples é numerar as requisições feitas ao kernel do servidor. Se ele controlar esse número, poderá distinguir entre um pedido original e uma retransmissão, evitando que a mesma tarefa seja resolvida duas (ou mais) vezes.
O servidor sai do ar logo após ter recebido uma solicitação de serviço Existem duas situações diferentes aqui: 1. O servidor recebe a requisição, executa e sai do ar, sem enviar a resposta. 2. O servidor recebe a requisição e sai do ar, sem nem executar. Algumas soluções propostas são: 1. O cliente espera o servidor voltar ao ar. 2. O cliente faz uma nova ligação com outro servidor, e faça a operação novamente. 3. O cliente deve desistir e reportar o problema. 4. O cliente não tem nenhuma garantia de que vai ter resposta. Logo, nenhuma das soluções propostas acima é minimamente interessante. Algumas são fáceis de serem implementadas, outras são simples de entender, mas nenhuma é razoavelmente boa. Logo, o desenvolvedor escolhe uma e usa-a. E torce para que os servidores não caiam.
O cliente sai do ar logo após ter enviado uma solicitação de serviço Caiu o cliente. O processamento feito pelo servidor ca então órfão. Como resolver? Existem quatro propostas de solução: 1. Antes que o cliente mande a mensagem, o conteúdo é salvo em disco, num arquivo temporário. Caso o cliente caia, o servidor aguarda o retorno dele, que pega o arquivo, e os processamentos órfãos são eliminados.
22
2. O cliente saiu do ar e reiniciou.
Quando ele volta, manda uma mensagem
para toda a rede anunciando o seu retorno, para que os processamentos órfãos relacionados a ele, e que sejam anteriores ao atual estágio, sejam eliminados. 3. Uma outra maneira, aproveitando a idéia acima, é que, quando chega a mensagem do cliente solicitando o descarte, o servidor veri ca se o proprietário está disponível. Se não estiver, ele descarta o processamento. 4. Na última maneira, uma fatia de tempo
T
é dada para cada chamada remota,
para que ela possa trabalhar. Se não der tempo para concluir, ela deve solicitar mais uma fatia de tempo. Mas, se houver uma queda, o servidor espera pela
T.
passagem de uma fatia de tempo
Assim, todos os procedimentos órfãos
terão sido eliminados. Na prática, nenhuma das maneiras anteriores é a desejável.
Eliminar um pro-
cessamento órfão pode trazer problemas para o sistema como um todo, pois suas conseqüências são imprevisíveis.
3.5 Comunicação em Grupo Vimos até aqui, para a situação entre um cliente e um servidor, ou seja, dois processos interagindo entre si. Mas existem circunstâncias em que vários processos estão envolvidos, não apenas dois. O nosso objetivo aqui é pensar como podemos, numa só operação, atingir vários receptores.
Exemplo:
Vários servidores gerenciam um sistema de arquivos único, tolerante a
falhas. Nesse caso, é bom que o cliente repasse a sua mensagem a todos os servidores. Mesmo se um estiver fora do ar, os outros receberão e a solicitação será realizada mesmo assim.
3.5.1 Introdução Um
grupo é um conjunto de processos que agem juntos, de uma maneira especi -
cada pelo sistema ou por um usuário. Os grupos são dinâmicos, e processos podem entrar ou sair de grupos facilmente. A idéia é que o conceito de grupo seja uma abstração de conjuntos de processos, para que seja mais fácil para o transmissor enviar a mensagem. Logo, ele só precisa disparar uma mensagem para um grupo. Em termos físicos, depende principalmente de hardware. Por exemplo, um endereço de rede especí co para o grupo permitiria o cliente enviar uma mensagem a
multicasting). broadcasting,
esse endereço, e todos os servidores associados recebê-la (
Em redes que não temos multicasting, a solução é apelar para o que consiste em disparar a mensagem para
todas
as máquinas da rede.
Caso a
mensagem não seja de interesse da máquina que a recebeu, ela é descartada. Queira ou não, essa alternativa acaba acarretando uma sobrecarga desnecessária na rede. Em último caso, o sistema pode usar o
unicasting, que é basicamente o trans-
missor enviando a mensagem para cada membro do grupo. É uma alternativa cara computacionalmente, e deve ser evitada.
3.5.2 Tipos de grupos 1. Grupo fechado: Somente membros do grupo podem enviar mensagens para o grupo. São mais usados em processamento paralelo.
23
2. Grupo aberto: Qualquer cliente pode enviar mensagens para o grupo. A noção de servidores replicados é útil para grupos abertos. 3. Grupo igualitário: Todos os processos são iguais. São simétricos, e mesmo que um processo falhe, o sistema continua rodando. Em compensação, a tomada de decisão é mais complicada. 4. Grupo hierárquico: Há um processo que funciona como coordenador. A tomada de decisão é simples e rápida, mas quando o coordenador falha, todo o grupo falha.
3.5.3 Controle dos membros do grupo Uma maneira de controlar a existência dos grupos é implementando um
de grupos.
servidor
Ele seria o responsável por criar e remover grupos, incluir e remover
membros, entre outras coisas. Só tem um problema: Se o servidor de grupos cair, perde-se a gerência dos grupos. Quando ele voltar ao ar, tudo terá que ser refeito do zero. A outra maneira seria a gerência dos grupos sendo feita de forma
distribuída.
Logo, um processo que quiser entrar num grupo, faz a solicitação aos membros do grupo, e eles aceitam-o ou não.
Quando um processo quiser sair, ele envia uma
mensagem de até logo aos demais membros, e assim sai do grupo. Há ainda três problemas a serem lidados, em qualquer uma das implementações: 1. Se um membro sai do ar, ele efetivamente sai do grupo.
Só que os outros
membros descobrirão pelo método empírico, tentando enviar-lhe mensagens e não obtendo resposta. Logo, só depois que todos souberem da queda daquele membro, é que ele será removido do grupo. 2. A partir do momento em que um membro entra no grupo, ele precisa receber todas as mensagens enviadas para esse grupo.
Logo, a entrada dele no
grupo deve ser imediata, sob pena de ter perda de informação, e atrapalhar o processamento. Da mesma forma, um processo sai do grupo, e ele não deve mais receber mensagens relativas ao grupo que ele se retirou. Uma maneira de resolver seria o envio de uma mensagem de apresentação do novo membro ao grupo, ou uma mensagem de despedida, quando ele estiver saindo do grupo. 3. Se um grande número de membros sair do ar, podemos ter problemas para o funcionamento dos grupos, visto que a maior parte dos membros estão fora
de combate . Logo, quando os membros começarem a voltar, os membros restantes vão aceitando-os para o grupo. Mas apenas um deve ter essa tarefa, de reconstruir o grupo. E se dois ou mais processos tentarem simultaneamente?
3.5.4 Ordenação de mensagens Para termos a comunicação global de uma forma simples de usar, ela deve obedecer a duas propriedades: 1. Atender a solicitação do
broadcast atômico, que basicamente é:
Ou todos
os membros do grupo recebem a mensagem, ou nenhum recebe. 2. Atender a ordem de chegada das mensagens, para evitar atropelos. Uma maneira simples e e ciente é fazer com que as mensagens sejam expedidas na mesma ordem em que foram enviadas. Logo, toda mensagem interna do grupo é enviada a todos os membros do grupo. Assim, todos recebem-na, e temos o que foi convencionado chamar
ordenação em tempo global. 24
3.5.5 Escalabilidade na comunicação grupal Muitos algoritmos funcionam bem em sistemas distribuídos montados em cima de redes locais, com poucos nós. Mas, e como caria a comunicação se expandirmos o sistema distribuído, englobando centenas ou milhares de componentes?
E se
forem várias redes locais interligadas? Pior, e se essas redes estiverem espalhadas geogra camente?
Por exemplo, temos uma mensagem em multicast saindo da rede 2.
Quando
chega nos gateways G1 e G3, eles vão copiar a mensagem e colocar nas redes 1 e 4. Quando chegar nos gateways G2 e G4, irão copiar para a rede 3, duas vezes. Se extrapolarmos para vários gateways e redes interligadas, teremos um crescimento exponencial de mensagens inúteis vagando pelas redes, gerando congestionamento e atrapalhando o tráfego das mensagens realmente úteis. Vemos então que é necessário um algoritmo mais so sticado para evitar essa situação.
3.6 Resumo 1. A diferença básica entre os sistemas operacionais tradicionais e os distribuídos consiste na importância em que a comunicação tem entre os sistemas distribuídos. 2. Adota-se um modelo cliente-servidor de protocolos, bem mais simples, para ganhar em performance na rede, em detrimento de protocolos que geram mais tráfego e informações redundantes. 3. A chamada remota a procedimentos é uma abstração mais elaborada, em que ca transparente a comunicação entre o cliente e o servidor. 4. Apesar dela ser uma proposta muito interessante, também tem problemas, como: (a) Variáveis globais, ponteiros e estruturas de dados complexas são difíceis de serem usados e passados. (b) A localização do servidor deve estar bem de nida. (c) Os clientes e os servidores podem falhar, independente uns dos outros. 5. As chamadas remotas limitam a comunicação a um cliente e um servidor. Há várias situações onde deverá ocorrer a comunicação global, entre grupos de processos. 6. Há diversas de nições de grupos, e situações desejáveis, como o broadcast atômico e a ordenação das mensagens. 7. O problema da escalabilidade deve ser lembrado, principalmente expandindo o sistema para uma quantidade grande de nós, dispersos geogra camente.
25
Capítulo 4
Sincronização em sistemas distribuídos Em sistemas com um processador, os problemas ligados a regiões críticas, exclusão mútua e outras questões sobre sincronização são resolvidas com o uso de semáforos e monitores. Mas, em sistemas distribuídos, é inviável, pois pressupõe a existência de memória compartilhada, o que não ocorre aqui. Veremos então os mesmos problemas anteriores, agora em sistemas distribuídos, e alguns novos.
4.1 Relógios e sincronização Algoritmos distribuídos trazem as seguintes características: 1. As informações relevantes estão espalhadas entre as máquinas; 2. As decisões que os processos tomam estão baseadas apenas em informações locais; 3. Deve-se evitar falhas; 4. Não existe um relógio global. Os três primeiros tópicos dizem respeito à impossibilidade de coletar informações globalmente.
O sistema é esparso e distribuído, e deve-se evitar a todo custo a
centralização. A nal, se a máquina que centraliza um recurso pára, os seus clientes também param.
O último também é importante, já que o tempo é um conceito
ambíguo. Existem diferenças entre os relógios físicos dos computadores que compõem o sistema distribuído. Por exemplo, podemos ter situações onde o resultado é gerado num servidor, num dado instante, e esse instante para o cliente ainda não ocorreu. Isso é o que queremos evitar.
4.1.1 Relógios lógicos Os relógios do computador (na verdade
temporizadores) são fundamentais para
a sincronização entre processos. Eles são feitos de cristais de quartzo, que oscilam numa frequência bem de nida. Mas, num sistema distribuído, com vários nós de origens diferentes, não temos a garantia de que os cristais oscilarão exatamente na mesma frequência. ocorrerão discrepâncias (o que é chamado
26
Sempre
escorregamento do clock), por vezes
mínimas, mas acumulativas. Logo, depois de um intervalo de tempo razoavelmente longo, essas discrepâncias serão visivelmente perceptíveis. Uma solução seria sincronizar os relógios, para termos um tempo único. Isso é possível, e existem algoritmos para isso.
A idéia inicial é que o sincronismo não
precisa ser absoluto. O que vale é que, entre dois ou mais processos que interagem entre si, eles estejam sincronizados. Isso é o que chamamos de Os relógios reais são os
relógios físicos.
relógios lógicos.
Impõe-se uma restrição, para evitar que
haja uma discrepância muito grande entre os relógios, lógicos e físicos. Para sincronizar, usa-se a relação Isso é o que chamamos
a → b,
que quer dizer a acontece antes de b .
acontecimento-anterioridade.
Para ocorrer essa relação,
deve-se ter que: 1. Se a e b são eventos no mesmo processo, e se a ocorre antes de b, então
a→b
é verdadeira. 2. Se a é o evento de uma mensagem enviada por um processo, e b é o evento da mesma mensagem recebida por um outro processo, então
a→b
também é
verdadeira. A relação é transitiva: se
a → b,
e
b → c,
então
processos que não se comunicam, então eles são
a → c.
Se os eventos ocorrem em
concorrentes,
e com isso, nada
pode ser dito a respeito. No m das contas, o que temos é que, se
a → b,
então
C(a) < C(b). A idéia do algoritmo é que o evento carrega o valor do relógio por onde passou anteriormente.
Temos os processos 0, 1 e 2, e os eventos A, B, C e D. No lado esquerdo, a situação ocorre sem haver a sincronização entre os relógios.
Logo, o processo 0
recebe o evento D, só que o relógio local no processo 1 marca 48, e no processo 0, 42.
No lado direito, os relógios são corrigidos, como podemos ver: O processo 0
adianta o relógio para o valor 49, o que é seguinte ao valor quando o evento D saiu do processo 1. No caso do evento C, onde os dois relógios estão marcando o mesmo tempo, uma opção é colocar ambos com uma pequena diferença. Logo, o processo 2 marcaria 40, e o processo 1 marcaria 40,1, ou 41, como está marcando. Dessa forma, temos uma maneira de atribuir tempos a todos os eventos em um sistema distribuído, mas sujeita às seguintes condições: 1. Se a ocorrer antes de b no mesmo processo, então
C(a) < C(b).
2. Se a e b são o envio e o recebimento de uma mensagem, então então
C(b). 3. Sendo a e b diferentes, também teremos
27
C(a) 6= C(b).
C(a) <
4.1.2 Algoritmos para sincronização de relógios Existem diversos
servidores de hora disponíveis na Internet, que se comunicam
através do protocolo NTP (Network Time Protocol), que usa o protocolo de transporte UDP para estabelecer a conexão. Os algoritmos para sincronização de relógios são usados para sincronizar os relógios do sistema distribuído com os servidores de hora disponíveis localmente ou via Internet. Mas, se nenhum nó do sistema distribuído tem como acertar a hora, o jeito é cada nó cuidar do seu próprio tempo, e todas as máquinas se falam para manter a menor discrepância possível entre os seus relógios. Existem alguns algoritmos propostos, onde o servidor de hora é passivo (responde requisições de hora) ou ativo (envia mensagens às máquinas para que elas acertem a hora), centralizados (um servidor de hora) ou descentralizados (várias máquinas espalhadas), entre outras variações.
4.2 Exclusão Mútua As exclusões mútuas ocorrem quando dois ou mais processos concorrentes disputam para entrar (condição de disputa) numa região crítica, e usa-se semáforos (ou monitores) para garantir a exclusão mútua. Veremos como isso funciona num sistema distribuído.
4.2.1 Algoritmo centralizado A idéia aqui é simular a metodologia para um sistema com um processador apenas. Logo, teremos um servidor de exclusões mútuas. Esse servidor autoriza ou não cada um dos processos concorrentes a entrarem nas suas regiões críticas, e com isso temos justiça (ninguém espera inde nidamente), e a garantia da exclusão mútua ocorrer. Como desvantagens, temos o servidor, que se sair do ar, compromete todo o sistema, e também traz problemas quanto à performance, se tivermos apenas um servidor num sistema distribuído muito esparso.
4.2.2 Algoritmo descentralizado Aqui, colocamos todos os eventos do sistema em ordem cronológica de ocorrência. Eventos novos são colocados no m da la, e quando um quer entrar na sua região crítica, cria uma mensagem dizendo o nome da região que quer entrar; número e tempo corrente. O processo que quiser entrar, manda a todos os outros processos essa mensagem. Os processos que recebem podem reagir de três maneiras: 1. Se não tem problema, responde
ok.
2. Se estiver usando a região crítica, não responde ainda. 3. Se quiser entrar também na região crítica, compara-se o tempo vindo da mensagem com o tempo da sua própria mensagem, solicitando o uso da região crítica. (a) Se o tempo desse processo for menor, ele responde
ok.
(b) Se o tempo desse processo for maior, ele coloca a requisição numa la, e não responde ainda.
28
4.2.2.1 Exemplo 1. São 3 processos (0, 1 e 2). 2. O processo 0 envia a todos uma mensagem com tempo 10 e o processo 2 envia a todos uma mensagem com tempo 15. 3. O processo 1 não pretende entrar na região crítica, logo ele manda OK para os outros 2. 4. O processo 2 percebe que a prioridade é do processo 0, e manda OK. 5. O processo 0 coloca a requisição do processo 2 na la dele, e entra na região crítica. 6. Quando o processo 0 sai da região crítica, repassa ao processo 2 uma mensagem de OK, permitindo que este entre na região crítica. Em caso de con ito, ganha o processo que enviou a mensagem com o menor tempo armazenado. Dessa maneira, não temos starvation nem deadlock, o que é bom. Em compensação, todo processo é um ponto de falha: Se ele não responder a uma das mensagens, isso bloqueia os outros processos subsequentes.
Além disso,
teremos muito mais tráfego na rede, já que todos os processos participam de todas as decisões. Uma maneira para evitar o silêncio de um processo é solicitar um aviso de recebimento por parte dele. Se não chegar o aviso, é porque o processo tem algum problema, e os outros podem descartá-lo. Outro problema é que a comunicação é grupal. Logo, cada processo tem que ter a lista dos membros do grupo, e sempre atualizada. Isso demanda mais tráfego. Na prática, esse algoritmo acaba sendo mais lento e complexo do que o algoritmo centralizado, e ainda mais sujeito a problemas no caso de grupos grandes de processos.
4.2.3 Uso de token Uma abordagem completamente diferente é o uso do token ( cha). A idéia é simples: O grupo de processos é arranjado num anel lógico, e no início da execução, o primeiro processo recebe um token ( cha). Essa cha é passada via mensagem para o outro elemento do anel, e assim por diante.
O processo que detém o token pode entrar em uma região crítica, fazer tudo o que precisa ser feito, e depois sair. O mesmo não pode usar o token para entrar numa segunda região crítica, apenas uma de cada vez. Isso faz evitar a ocorrência
29
de starvation, já que, no pior dos casos, um processo terá que esperar todos os outros entrarem e saírem para ele poder entrar. Alguns problemas possíveis são: 1. A perda do token - Caso o token seja perdido, será necessário regenerá-lo, o que é complicado de ser detectado. 2. A parada repentina de um processo - Um processo não repassa o token, e nem entra na região crítica, logo pára todo o anel. Uma maneira de contornar é exigir que o processo que recebeu o token envie um aviso de recebimento. Se esse aviso não tiver sido emitido e recebido, é porque o processo está com problemas. O processo anterior repassa o token ao processo posterior ao processo morto, e ele é removido do anel.
4.2.4 Comparação entre os algoritmos O algoritmo centralizado é o mais simples e e ciente de todos, já que envia e recebe poucas mensagens. Mas tem o problema (sério) da centralização. O algoritmo da passagem de token gera uma quantidade de mensagens imprevisível. Se todos os membros do anel quiserem entrar na região crítica, serão duas mensagens. Mas nem todos podem querer entrar. O tempo de atraso entre o processo que pede para entrar na região crítica e efetivamente entra na mesma também varia. No algoritmo centralizado, é o tempo de
2
mensagens (o pedido e a liberação para entrar).
No algoritmo distribuído,
todos tem que receber o pedido e a liberação, com exceção do próprio.
n processos, serão 2(n−1) mensagens. varia, de 0 a n − 1mensagens.
tivermos isso
Logo, se
No algoritmo de passagem de token,
Abaixo temos uma tabela que resume essas informações. Mensagens por Algoritmo
entrada/saída da região crítica
3
Centralizado Descentralizado Passagem de token
Retardo antes da entrada (em tempos de mensagens) 2
2(n − 1)
Problemas
2(n − 1)
Coordenador fora do ar Qualquer processo fora do ar Perda do token,
1 a ∞
0 a n−1
queda de um processo
Mas num sistema tolerante a falhas, nenhum desses algoritmos é recomendado, a não ser que a perda de processos seja algo improvável.
4.3 Algoritmos eletivos Outro tipo de algoritmo que é usado para sincronização em sistemas distribuídos é o
algoritmo eletivo, onde um processo coordenador é eleito entre todos os outros
processos para administrar o acesso à região crítica. Abaixo temos alguns deles:
4.3.1 O algoritmo do ditador Quando um processo percebe que o coordenador não está respondendo às solicitações, ele começa uma
eleição, que funciona da seguinte maneira:
30
1. P envia uma mensagem solicitando o início da eleição a todos os processos com número de identi cação maior do que o dele próprio. (a) Se ninguém responder, P é o novo coordenador. (b) Se alguém responder, ele é o novo coordenador. 2. Envia-se uma mensagem para todos os membros do grupo, avisando quem é o novo coordenador.
4.3.2 O algoritmo em anel Esse algoritmo aqui constrói-se um anel lógico, só que sem um token a ser passado. Aqui, todos os processos conhecem quem é o seu antecessor e o seu sucessor. Se um dos processos descon a que o coordenador está inativo, ele manda uma mensagem para o seu sucessor, carregando um pedido de eleição, e o seu número de identi cação.
O sucessor acrescenta o seu próprio número de identi cação, e
repassa a informação à frente. Eventualmente, o processo que primeiro enviou o pedido de eleição recebe a sua mensagem de volta, já que ela traz o seu próprio número de identi cação. Caso um segundo processo também envie um pedido de eleição, torna-se o novo coordenador aquele cujo número de identi cação seja o maior. Feito isto, ele dispara uma nova mensagem no anel, anunciando quem é o novo coordenador, que circula todo o anel. Depois da segunda mensagem, todos voltam ao trabalho. Apesar da circulação de mensagens (num anel com
n
processos, teremos
2n
mensagens), o gasto extra de banda é efetivamente pequeno.
4.4 Deadlocks em sistemas distribuídos O problema de um deadlock num sistema distribuído é muito parecido com o problema num sistema centralizado (um processador), embora sejam mais difíceis de detectar ou evitar. Temos dois tipos de deadlocks: 1. Deadlocks ocorridos na comunicação entre processos - O processo A tenta enviar uma mensagem ao processo B, que tenta enviar uma mensagem ao processo C, que está tentando enviar uma mensagem ao processo A. 2. Deadlocks ocorridos quando os recursos são alocados - Vários processos estão disputando o acesso exclusivo a dispositivos de E/S, arquivos, qualquer tipo de recurso. Existem quatro estratégias para lidar com deadlocks: 1. Ignora os deadlocks ocorridos. 2. Deixa ocorrer o deadlock, detecta a ocorrência e e tenta recuperar. 3. Previne a ocorrência de deadlocks, fazendo com que a estrutura não possa ser quebrada. 4. Evita a ocorrência de deadlocks com uma política de alocação de recursos bem cuidadosa.
31
Nos sistemas distribuídos, os métodos 1 e 2 são populares, principalmente porque evitar o deadlock num sistema distribuído é muito difícil. A prevenção (método 3) é complexo de ser implementado, e o método 4 é inviável, pois para ser bem-sucedido, é necessário saber quais recursos cada processo irá precisar, por antecipação. E essa informação quase nunca está disponível.
4.4.1 Detecção de deadlocks 4.4.1.1 Algoritmo centralizado Um coordenador mantém um mapa geral de todos os processos e recursos de todo o sistema distribuído, e se for necessário, ele elimina um processo para evitar o deadlock. Nesse caso, é necessário que o coordenador receba o mapa de processos e recursos de cada máquina, para poder montar o mapa geral. Isso pode ser feito de várias maneiras (alterações feitas são submetidas ao coordenador, envio periódico das alterações, ou o pedido do coordenador pelas alterações).
Todas são caras
computacionalmente, e nem sempre funcionam bem. Pode ocorrer o que chamamos de um
falso deadlock,
que é o coordenador
eliminar alguns processos que não estavam gerando um deadlock.
Uma maneira
de evitar é usar o algoritmo que discutimos na seção 4.1.1, para o fornecimento do tempo global.
4.4.1.2 Algoritmo descentralizado Aqui, os processos tem permissão de pedir a alocação de vários recursos de cada vez, ao invés de um de cada vez. Assim, a fase de crescimento do algoritmo pode ser acelerada. Um processo que quer um recurso local requisita-o.
Agora, um processo que
mensagem de sondagem para outro processo, para ver se o recurso está disponível. quer um recurso que está numa outra máquina, tem que enviar uma
Quando chega no destino, o receptor vê se ele está aguardando por recursos de algum processo. Se estiver, ele atualiza a mensagem, com os seus próprios dados, e a mensagem é repassada para o processo responsável pelo bloqueio do transmissor da mensagem. Se a mensagem for retransmitida, e voltar ao processo de origem, é um deadlock. Uma maneira de desfazer é eliminando o processo que pede o recurso, mas aí todos podem acabar encerrando, e temos um problema ainda maior do que o deadlock. Outra maneira é colocar a identidade do processo no nal da mensagem, e se gerar um deadlock, todo o ciclo estará registrado na mensagem. Quem originou a mensagem solicita o m do processo com número de identi cação mais alto, para quebrar o deadlock. Mesmo assim, os métodos não são e cientes.
4.4.2 Prevenção de deadlocks O sistema tem que ser projetado com cuidado, para que a ocorrência de deadlocks seja impossível. Logo, o projeto de um sistema assim também é quase impossível. Algumas das maneiras pensadas são:
•
Cada processo só pode usar um recurso de cada vez;
•
Os processos só podem pedir o uso de recursos novos depois de liberarem todos que estão usando;
32
•
Os processos devem pedir todos os recursos que vão usar antes de entrar em execução;
•
Os recursos são numerados, e cada processo não pode solicitar um recurso com número de identi cação menor do que o daquele que ele detém a posse.
Mas, na prática, todos esses métodos causam problemas, pois demanda que os processos trabalhem de forma estritamente ordenada. Em um sistema distribuído, pode-se prevenir a ocorrência de deadlocks usando um método, que descrevemos abaixo: No momento em que se estabelece uma transação (ou seja, um processo faz uso de um recurso, entrando na região crítica), coloca-se uma etiqueta nessa transação marcando o tempo global daquele instante. Graças ao algoritmo descrito na seção 4.1.1, duas transações não terão o mesmo tempo global, e mesmo que tenham, o número de identi cação será o critério de desempate. Quando um processo está prestes a ser bloqueado, esperando por um recurso que outro processo estiver usando, procura-se ver qual é o mais velho. Somente os processos mais jovens (com o tempo global maior do que o processo em execução) podem car esperando. Logo, dessa maneira, as etiquetas sempre estarão em ordem decrescente, impedindo que se formem ciclos, e em consequência, deadlocks.
4.5 Resumo 1. Inicialmente vimos o algoritmo para sincronizar processos entre si, sem a necessidade de usar fontes externas de tempo. Esse algoritmo, como vimos, é muito útil. Vimos também o uso de relógios físicos para sincronizar os processos. 2. Na exclusão mútua, temos três algoritmos, cada um com vantagens e desvantagens: (a) O centralizado mantém todas as informações em um único ponto. (b) O distribuído tem as informações espalhadas por todos os pontos, realizando os cálculos em paralelo. (c) A passagem do token passa o controle por cada uma das máquinas ao longo de um anel lógico. 3. Muitos algoritmos requerem que um processo seja o coordenador. Logo, vimos duas maneiras de se eleger um coordenador:
O algoritmo do ditador e o
algoritmo do anel. 4. Vimos o problema dos deadlocks, agora em sistemas distribuídos, e vimos como funcionam alguns algoritmos para detecção e prevenção de deadlocks.
33
Capítulo 5
Processos em sistemas distribuídos Os processos são nosso alvo de estudo nesse capítulo, e em particular, veremos como os sistemas operacionais administram vários processadores, e fazem o balanceamento de carga entre eles, além do escalonamento e a alocação.
5.1 Threads Na maioria dos sistemas operacionais tradicionais, cada processo tem um espaço de endereçamento e um único thread. Mas há sistemas que permitem a existência de mais de um thread (sistemas multithread) compartilhando um único espaço de endereçamento. Conhecemos a de nição, e como tudo funciona.
5.1.1 Organizações de threads dentro de um processo Os processos devem ter um buer que coleta as requisições feitas aos threads. A partir desse buer, temos três tipos de organizações internas: 1. Modelo do dispatcher: Há um thread, o
dispatcher, que repassa o conteúdo
do buer a cada thread do processo, para que ele trate aquela requisição. 2. Modelo do time: Cada thread vai até o buer, pega uma requisição e a executa. Não há o dispatcher aqui. 3. Modelo do pipeline: O primeiro thread pega a requisição, processa e repassa-a para o próximo. E assim vai, até o m.
5.1.2 Threads e chamadas remotas a procedimentos Estudamos as chamadas remotas a procedimentos na seção 3.4, e agora, como podemos implementá-las, de forma a aproveitar o recurso dos threads? Foi observado que, mesmo em um sistema distribuído, muitas chamadas remotas a procedimentos eram feitas entre processos que estão operando dentro da mesma máquina. Ora, empacotar os parâmetros e desempacotar do outro lado, e também o caminho de volta... É ine ciente. A idéia é fazer com que um thread, dentro de um processo, possa chamar um outro thread em um outro processo numa mesma máquina, de uma forma muito mais e ciente.Vejamos:
34
1. O thread que age como servidor é inicializado, e ele copia para o kernel a sua interface.
Essa interface de ne quais procedimentos poderão ser chamados,
parâmetros, etc. 2. O thread que é o cliente, então, quando for inicializado, importa a mesma interface do kernel, e informa ao kernel que em algum momento irá comunicarse com o servidor. 3. O kernel então, ca sabendo que haverá comunicação entre eles, em algum momento, e prepara um meio de processar essa chamada futura. 4. No momento em que ocorre a chamada, o kernel apenas troca um pedaço do espaço de endereçamento do cliente (que contém os dados a serem passados) com um pedaço do espaço de endereçamento do servidor, e dispara-o. Assim, não é necessário o empacotamento de parâmetros, e nem cópia dos mesmos, processando-os muito mais rápido. No nal das contas, temos economia de tempo substancial.
5.2 Alocação do processador Um sistema distribuído é composto por diversos processadores, que podem estar organizados como um conjunto de estações de trabalho, um armário de processadores, ou algo que seja um misto dos dois. Mas, em todos os casos, é preciso um algoritmo que decida quem vai ser executado aonde. Se usarmos um
modelo com estações de trabalho, esse algoritmo só poderá
executar alguma coisa se a estação estiver ociosa. E, no momento em que a estação for usada, o processo que estiver lá sendo executado deve ser suspenso e transferido para outra máquina, para dar continuidade. Se usarmos o modelo do armário de processadores, para cada processo a ser executado, será necessária uma decisão, para qual processador o processo será enviado. Veremos então alguns modelos e algoritmos para resolver o problema da alocação de processadores.
5.2.1 Modelos de alocação Podemos dividir os modelos de alocação em
estratégias migratórias.
estratégias não-migratórias, e em
As estratégias não-migratórias de nem que, de nido onde o processo será executado, lá ele será executado, até o m. Não há possibilidade do processo ser levado para ser executado em outro processador. As estratégias migratórias permitem que o processo seja remanejado para outro processador, mesmo que ele já esteja em execução. As estratégias migratórias permitem um melhor balanceamento de carga, mas são mais complexas. O objetivo nal é e
minimizar o tempo de resposta.
maximizar a utilização do processador,
Vários algoritmos foram propostos ao longo dos tempos:
•
Algoritmos determinísticos - Bons quando a carga de trabalho é previsível.
•
Algoritmos heurísticos - Bons quando a carga de trabalho é imprevisível.
•
Algoritmos centralizados - Agrupamento da decisão num lugar é melhor para decidir, mas é pouco robusto.
35
•
Algoritmos distribuídos - Descentralização da decisão reparte o problema entre várias máquinas. É mais robusto, mas mais lento.
•
Algoritmos ótimos - Aqueles que são os melhores possíveis para a alocação.
•
Algoritmos subótimos - Os que são aceitáveis para o seu propósito.
•
Algoritmos locais - Usado para alocar a execução de um processo na sua própria máquina de origem, caso a carga esteja baixa.
•
Algoritmos globais - Usado para avaliar onde é o melhor lugar para alocar a execução de um processo, em todo o sistema.
•
Algoritmos iniciados pelo transmissor - O transmissor deve começar a busca por uma nova máquina, para executar aquele processo.
•
Algoritmos iniciados pelo receptor - O receptor deve começar a busca por uma nova máquina, para executar aquele processo.
5.2.2 Alguns aspectos 1. Supõe-se que cada máquina sabe qual é a sua carga de trabalho, e ser capaz de informar às outras qual é o seu estado. Essa medida não é absolutamente trivial, e tem que ser única para todo o sistema distribuído. 2. E como tratar a sobrecarga gerada no sistema, justamente por esse processo, de coleta de informações? 3. Qual a complexidade desse algoritmo? Estudos comprovam que algoritmos so sticados dão um ganho razoável, mas impõem a penalidade de gerarem muita sobrecarga. Logo, algoritmos simples podem trazer ganhos mais interessantes. 4. A estabilidade do algoritmo, onde máquinas diferentes rodam seus algoritmos de maneira assíncrona. Logo, uma máquina pode achar que a outra está com folga, mas na verdade é a informação que está defasada.
5.2.3 Alguns exemplos 1. Um algoritmo determinístico baseado na teoria dos grafos - O sistema é representado como um grafo ponderado, e a idéia é dividir todo o grafo em subgrafos, um para cada processador, e com isso, procurar a divisão que minimize o tráfego na rede. Ou seja, o que queremos é montar grupos de processos que interajam muito entre si, e pouco com outros grupos de processos. É um algoritmo complexo, e precisa de informações normalmente não-disponíveis no momento da necessidade. 2. Um algoritmo centralizado - Um processo coordenador tem uma tabela de utilização, que é atualizada de tempos em tempos. Com base nisso, a carga é repassada para cada máquina, de forma justa e equilibrada.
É um algo-
ritmo simples, mas em sistemas muito grandes não funciona bem, visto que há gargalos e pouca robustez. 3. Um algoritmo hierárquico - Montar toda a estrutura logicamente numa hierarquia, com grupos de máquinas submissas a uma máquina, que por sua vez está submissa a outra, e por aí vai. Se uma dessas máquinas gerentes falhar, promove-se alguém para o cargo.
É robusto e funciona bem, mas o
fato das requisições serem geradas randomicamente podem atrapalhar o seu funcionamento. 36
4. Um algoritmo heurístico distribuído - Quando um processo é criado, a máquina de origem sonda as outras máquinas, para saber qual delas tem carga abaixo de um limite pré-estabelecido. Se não achar, procura de novo, até encontrar, ou então executar esse processo na máquina hospedeira.
Muitas vezes esse
processo de escolha usa teoria das las. 5. Um algoritmo leiloeiro - Aqui, processos são compradores de tempo, e os processadores, os vendedores de tempo. Há um mercado, de compra e venda de tempo, e o processo, que cria um processo- lho, vai e escolhe o processador que oferece as melhores condições.
Basicamente, temos um micro-modelo
econômico...
5.3 Escalonamento Cada processador faz o seu escalonamento local, assumindo que há vários processos para rodar nele, sem se preocupar com o que os outros estão fazendo. Funciona bem em alguns casos, exceto quando temos um grupo de processos altamente interativos e e relacionados entre si rodando em diferentes processadores. Nesse caso, é bom garantir que processos que interagem muito entre si estejam sendo executados simultaneamente, pois numa situação de tempo compartilhado, entre vários processadores, uma troca de mensagens pode car muito demorada. Uma idéia é colocar todos os processos que se encaixam nessa situação rodando
na mesma fatia de tempo.
Combinando essa característica com o algoritmo hie-
rárquico para alocação do processador (visto na seção 5.2.3), podemos ter resultados interessantes, com cada processo supervisor montando uma tabela de alocação, e coordenando esse escalonamento.
5.4 Resumo 1. Threads são uma realidade em sistemas operacionais, distribuídos ou não. 2. Os threads e as chamadas remotas a procedimento, juntos, podem gerar resultados muito interessantes. 3. Os modelos de organização de processadores basicamente são: 4. Estações de trabalho - cada usuário com sua estação, processos são executados prioritariamente na sua máquina. 5. Armários de processadores - todo processamento é compartilhado, com processadores sendo alocados dinamicamente aos usuários. 6. Mistos - união dos dois modelos anteriores. 7. Dado um conjunto de processadores, podemos atribuir processadores a processos, de várias formas. Temos diversos algoritmos que dizem como a coisa pode funcionar. 8. O escalonamento local funciona bem, mas em situações com muita troca de mensagens, pode ser interessante o rearranjo dos processos, como um
escalonamento.
37
co-
Capítulo 6
Sistemas de arquivos distribuídos Um sistema de arquivos é o componente-chave para qualquer sistema operacional, ainda mais um sistema distribuído. A nal, ele armazena programas e dados, tornando-os disponíveis quando é necessário. O
serviço de arquivos
é a especi cação daquilo que o sistema de arquivos
oferece, ou seja, a interface entre o sistema de arquivos com os cliente. Já o
de arquivos é um processo que roda em alguma máquina do sistema, implementar o serviço de arquivos.
servidor
e ajuda a
Um sistema bem implementado permite que
tudo funcione bem, de forma transparente ao usuário.
6.1 O projeto O serviço de arquivos e o servidor de diretórios são as duas partes fundamentais e distintas do sistema de arquivos.
6.1.1 O serviço de arquivos Um
arquivo é uma sequência de bytes, e o sistema operacional não tem responsabiatributos,
lidade sobre o signi cado dessa sequência de bytes. O arquivo pode ter
que são informações a respeito do arquivo, mas não dentro dele. Logo, o proprietário do arquivo, seu nome, tamanho, data de criação, direitos de acesso a ele, tudo isso são atributos. As primitivas do serviço de arquivos permite que modi quemos algumas dessas características, mas não todas. A proteção é de nida da mesma maneira em que em sistemas com um único processador: Com listas de controle de acesso e listas de capacidade. Cada arquivo tem um conjunto de capacidades que pode ser de nido pelo seu proprietário. As listas de controle de acesso são usadas para de nir quem pode fazer o quê com aquele arquivo. Os serviços de arquivos podem ser divididos em dois modelos de acesso:
Local:
O arquivo, quando lido, é copiado do servidor para o cliente, e lá ele sofre
as devidas alterações para depois ser recolocado no servidor. O modelo aqui é bem simples, e funciona bem. Mas o cliente tem que ceder um espaço razoável na memória, com o objetivo de manter nela os arquivos, temporariamente.
Remoto:
O serviço de arquivos fornece várias operações que podem ser realiza-
das, remotamente, no servidor. O arquivo não deixa o servidor, mas sofre as modi cações necessárias à distância.
38
6.1.2 O servidor de diretórios O serviço de diretórios de ne como serão os nomes de arquivos e diretórios: Tamanho, uso de caracteres especiais, espaços em branco, extensão, etc.
Também
de nem a criação de diretórios e subdiretórios, montando o que conhecemos como
sistema de arquivos hierárquico.
um
É possível a criação de ligações ou ponteiros para um diretório qualquer, mesmo em sistemas esparsos. Essas ligações permitem que o sistema seja organizado segundo um grafo arbitrário, disperso entre os servidores, o que é uma estrutura muito mais poderosa, mas ao mesmo tempo, mais complexa. Um problema ocorre se for eliminada a ligação de um diretório para outro. Teremos diretórios órfãos, perdidos entre os servidores. O problema também ocorre em sistemas centralizados, diga-se de passagem. Mas nos sistemas distribuídos, é muito mais sério: Você não pode simplesmente parar
toda a atividade dos arquivos,
para simplesmente procurar por diretórios órfãos. Uma questão importante é que: nem todas as máquinas tem a mesma visão da hierarquia de diretório. Uma parte da árvore pode estar num servidor, e outra parte, em outra máquina. Ou então a ligação entre a raiz e o diretório não ser a mesma nos clientes (tipo, um diretório está vinculado à raiz numa máquina, e a um outro diretório na outra máquina). A idéia da
montagem remota é usada para
organizar a observação do sistema, por parte dos clientes.
6.1.2.1 Identi cação transparente O principal problema com a identi cação do caminho para alcançar um diretório é que ele não é totalmente transparente, que é o desejável. Se queremos que o sistema seja
transparente quanto à localização, não devemos ter nada no caminho que
identi que o servidor onde o arquivo está sicamente armazenado. Imagine a situação, de um servidor com pouco espaço livre, e outro com muito. Um arquivo muito grande que iria ser salvo no primeiro servidor, poderia ser remanejado para o segundo, por causa da necessidade. Mas se o nome do servidor estiver atrelado ao caminho, ele terá que ser mudado, e todos os outros processos que farão uso desse arquivo, precisarão saber disso. Resumidamente, existem três maneiras de identi car arquivos e diretórios num sistema distribuído: 1. Nome da máquina ao lado do caminho. 2. Montagem dos sistemas de arquivos remotos na hierarquia de arquivos locais. 3. Um único espaço de nomes que devem ser os mesmos em todas as máquinas. Os dois primeiros casos são simples de serem implementados, enquanto que o terceiro caso é difícil de ser feito, mas necessário se o objetivo é fazer com que o sistema distribuído aja como se fosse um único computador.
6.1.2.2 Identi cação em dois níveis Os arquivos tem nomes simbólicos, para serem usados pelas pessoas, e nomes binários, que são usados pelo sistema em si. Os usuários preferem os nomes simbólicos, por motivos óbvios. estabelece-se uma
O sistema trabalha melhor com nomes binários, e
ligação simbólica entre eles.
Pode-se usar essa idéia para arquivos espalhados entre máquinas, onde na tabela de nomes binários, está salvo a localização física do arquivo, em que servidor ele se encontra. A ligação simbólica então, funciona como um caminho para um arquivo.
39
Uma característica interessante, para implementar a
tolerância a falhas,
é
ter o mesmo arquivo replicado em vários servidores, e a tabela de nomes binários referenciar todos os servidores onde aquele arquivo se encontra. No momento do acesso, acessa-se o servidor mais próximo, mas caso haja falhas, o dado ainda está disponível, por causa da redundância.
6.1.3 Compartilhamento de arquivos Quando dois ou mais usuários compartilham o mesmo arquivo, é preciso de nir as operações de leitura e escrita para evitar problemas.
Um bom exemplo é o que
ocorre quando uma operação de escrita é realizada, e logo depois uma operação de leitura. Essa leitura retorna o resultado da operação anterior, ou seja, a operação de escrita. Para que isso ocorra corretamente, mesmo num sistema com vários usuários, é
ordenação absoluta no tempo de todas as operações, para que sempre o valor mais recente retorne ao usuário. obrigatório uma
Num sistema distribuído, obter essa organização é fácil se tivermos somente um sistema de arquivos, centralizado, e sem cache de disco. Tudo o que os clientes fazem, são executados no servidor. A performance é pobre, mas pode ser melhorada com o uso de cópias locais dos arquivos, nos clientes, e atualizações dos mesmos, de tempos em tempos. Uma maneira de manter o servidor atualizado é enviar as mudanças nos arquivos que estão no cache, o que é bem menos do que enviar os arquivos como um todo.
Ou então, outra opção é exibilizar a regra: podemos fazer com que as mudanças num arquivo só estão disponíveis a todos os usuários quando o usuário que fez as modi cações fechou o arquivo. Dessa forma, não precisaremos atualizar o arquivo a todo instante, apenas quando ele for fechado pelo usuário em questão. Alguns propõem uma terceira via, a dos
arquivos imutáveis:
Os arquivos não
podem ser escritos e/ou apagados, somente criados ou lidos. Isso não é lá muito viável, portanto uma quarta opção é o uso de
transações indivisíveis:
Quando
o processo quer acessar um arquivo, ele envia um comando solicitando-o, e depois somente ele pode alterar o arquivo, até o seu fechamento.
6.2 Implementação de um sistema de arquivos Antes de criar um novo sistema de arquivos, é importante pensar vários aspectos, que vamos ver abaixo.
6.2.1 Utilização de arquivos Antes de criar um sistema de arquivos, é preciso ter uma boa idéia de como ele será usado, de maneira a ter certeza de que as operações serão feitas com e ciência. Na tabela abaixo, temos algumas observações sobre a utilização de arquivos: A maioria dos arquivos são pequenos (menores do que 10 Kb). A leitura é bem mais comum do que a escrita. Leituras e escritas são feitas seqüencialmente. A maioria dos arquivos tem um tempo de vida muito pequeno. Não é comum os arquivos serem compartilhados. Os processos usam poucos arquivos, em geral. Existem tipos de arquivos diferentes, com propriedades diferentes.
40
Mas ainda há dúvidas se essas observações variam de acordo com o ambiente onde o sistema operacional é empregado:
Numa indústria, no escritório de uma
empresa, num banco... Isso tudo acima pode mudar. Mas, para uma aproximação inicial, é razoável que as seis observações acima sejam plausíveis.
6.2.2 Estrutura do sistema Analisando algumas formas de organização interna de arquivos e diretórios, algumas perguntas que vem são: 1.
Os clientes e os servidores são diferentes?
Resposta:
Depende do sistema de arquivos empregado. O NFS (Network File Sys-
tem), criado pela Sun e amplamente utilizado, não faz essa distinção. Apenas ocorre a exportação de diretórios selecionados, de modo que outras máquinas podem acessá-los. Mas existem outros que a distinção é clara. 2.
Como estruturar os serviços de arquivos e de diretórios?
Resposta:
Uma maneira é combinar os dois serviços numa coisa só. Outra opção
é mantê-los separados. Assim, abrindo um arquivo, consulta-se o servidor de diretórios, fazendo o mapeamento do nome simbólico no nome binário, para assim acessar o arquivo. A vantagem de separá-los é dar mais exibilidade ao conjunto, mas torna-se mais cara computacionalmente, quando há a necessidade de fazer várias buscas pelos caminhos dos arquivos (pode-se diminuir o tempo gasto usando um cache). 3.
É preciso que os servidores de diretório e de arquivos mantenham informações de estado dos clientes?
Resposta:
Alguns acham que não deve haver informações de estado nos servidores.
Ou seja: Faz-se a requisição a um servidor, processa ela, envia a resposta e depois... Esquece. Outros acham que deve-se manter informações de estado nos servidores. Abaixo vamos ver vantagens e desvantagens:
•
Os servidores que não guardam informações são mais tolerantes a falhas, não precisam guardar tabelas com informações dos clientes, e não tem problemas quando um cliente pára de funcionar.
•
Os servidores que guardam informações tem desempenho maior, pode bloquear acesso a arquivos (caso seja necessário), pode fazer a leitura antecipada de arquivos que serão chamados posteriormente.
6.2.3 Armazenamento em cache Existem quatro lugares onde um arquivo pode estar: 1. No disco do servidor; 2. Na memória principal do servidor; 3. No disco do cliente; 4. Na memória principal do cliente.
41
O lugar mais apropriado é
o disco do servidor,
que tem muito espaço, está
disponível para todos os clientes, e evita problemas de consistência. Mas o mesmo é lento, e o acesso a ele tem que passar pela memória principal do servidor, depois para o disco do cliente, e nalmente a memória principal do cliente. Uma maneira de diminuir o tempo gasto é usar o
cache do servidor.
Assim,
um arquivo que é muito acessado, está no cache, e não terá que ser lido do disco. Mas, para manter o cache cheio, é preciso um algoritmo que decida quem deve car no cache. Ainda temos o problema do tráfego na rede, mas pode ser resolvido se tivermos um cache no cliente. Esse algoritmo tem que resolver dois problemas: 1. O que é gerenciado pelo cache, arquivos inteiros ou blocos de disco? 2. O que fazer, quando o cache encher, e for preciso remover arquivos dela? Agora, se usamos cache para acelerar o desempenho do sistema de arquivos (distribuído ou não), como podemos garantir a
Exemplo:
consistência do cache?
Num servidor, temos um arquivo, A1. Ele foi lido, logo está no cache
de dois clientes. Ambos zeram alterações em A1. Um terceiro cliente pede acesso a A1. O que ele vai ler? Se a consistência não for garantida, a versão original de A1, e não as versões alteradas pelos dois clientes, anteriormente. Existem quatro métodos para garantirmos a consistência do cache, que iremos resumir na tabela abaixo: Método
Como funciona O arquivo é alterado no cache
Write through
Escrita retardada
e
Só ajuda no tráfego de
no sistema de arquivos do
leitura. Na escrita, a
servidor.
velocidade é a mesma.
O arquivo é alterado no cache,
Maior desempenho, mas
mas só é alterado no sistema de
quem mais precisar do
arquivos do servidor de tempos
arquivo, pode receber
em tempos.
uma versão antiga.
O arquivo é alterado no cache e Write on close
Comentários
só quando é fechado, no sistema de arquivos do servidor.
Demora para ter o arquivo alterado.
O servidor de arquivos mantém
Problemas no controle do
Controle
o controle de tudo que está
crescimento do sistema, e
centralizado
acontecendo com os arquivos.
é menos robusto.
6.2.4 Replicação O interesse na replicação de arquivos por um sistema distribuído é claro:
•
Aumenta a con abilidade;
•
Tolerância a falhas;
•
Carga de trabalho dividida por vários servidores.
Existem três maneiras de fazer a replicação: 1. Replicação explícita: O arquivo é copiado na hora para o servidor, e para os outros servidores. 2. Replicação retardada: O arquivo é copiado para o servidor, e posteriormente os outros são atualizados. 42
3. Replicação em grupo: O arquivo é gravado no grupo de servidores, simultaneamente. Nos casos 1 e 2, é obrigatório eleger um servidor principal, para que ele receba a atualização e possa replicar o arquivo, o que não é muito robusto. Pode-se usar um algoritmo eletivo, para fazer a troca do servidor principal, de tempos em tempos.
6.3 Tendências Muita coisa está mudando na informática, e isso re etirá na área de sistemas de arquivos distribuídos. Abaixo vão algumas: 1. Hardware novo - O hardware velho está cada vez mais barato, o que torna mais atrativo montar sistemas distribuídos, com mais máquinas por um preço menor. Com o avanço da tecnologia, pode-se pensar em estruturas de rede mais rápidas (anéis de bra ótica, por exemplo) interligando os servidores de arquivos.
Dessa forma, pode-se dispensar o cache nos clientes, visto que o
gargalo da rede será muito menor, e muito melhor aguentar a baixa latência dos servidores do que usar uma implementação complexa (e cara) para o cache. 2. Escalabilidade - Algoritmos que funcionam bem com 100 máquinas podem não funcionar bem com 10.000.
Os sistemas de arquivos centralizados não
respondem bem ao aumento dos número de máquinas: Se para acessar um arquivo qualquer, todo mundo precisa falar com um servidor, ele será um grande gargalo no sistema. Transmissões em broadcast devem ser evitadas a todo custo, e a estrutura em árvore de diretórios, única, com um sistema de arquivos distribuído, tende a fazer com que o caminho seja cada vez maior. 3. Redes de longa distância - Os sistemas distribuídos tem sido pensados inicialmente em cima de redes locais. E quando tivermos redes que abranjam todo um país, por exemplo? Como resolver o problema da latência, numa rede com uma extensão tão grande como essa? 4. Usuários móveis - Portabilidade e mobilidade são palavras de ordem hoje em dia, com o crescimento da Internet. Como manter os usuários conectados às suas bases de dados, mesmo quando estando em trânsito? Qualquer solução deve ser baseada no cache: O usuário leva os seus arquivos, e enquanto não tiver um acesso próximo, atualiza-os. No momento em que estiver ao alcance, ocorre a atualização na base de dados. Mas, e se o tempo de desconexão for de horas, ou dias, como será a consistência do cache? 5. Tolerância a falhas - Os sistemas atuais não são tolerantes a falhas, salvo raras exceções.
Para termos redundância propriamente dita, é necessário investi-
mento em hardware (fontes redundantes, matrizes de HDs ligados em RAID, sistemas hot-swap, etc) e redundância em software, principalmente dos dados. A replicação de arquivos será fundamental para os futuros sistemas, e a capacidade de funcionar mesmo com parte dos dados fora do alcance, é importante para termos um sistema realmente tolerante a falhas.
6.4 Resumo •
O centro de qualquer sistema distribuído é o seu sistema de arquivos.
•
Qual é o modelo de um sistema e que tipo de funcionalidade é oferecida?
43
•
A natureza de um arquivo não muda, seja ele hospedado num sistema centralizado ou distribuído.
•
Compartilhamento de arquivos é um assunto importante e complexo.
•
A implementação demanda várias decisões, se o sistema deve guardar as informações de estado ou não, se e como deve ser implementado a cache, e como deve acontecer a replicação de arquivos. Cada uma dessas decisões tem conseqüências muito fortes.
•
Finalmente, vemos algumas tendências que estão se tornando pontos importantes no projeto de sistemas de arquivos distribuídos, como os avanços na tecnologia, escalabilidade, redes de longa distância, usuários móveis e a tolerância a falhas.
44
Referências Bibliográ cas [1] Sistemas Operacionais Modernos - Andrew S. Tanenbaum - Editora LTC - 1a edição. [2] Sistemas Operacionais: Conceitos e Aplicações - Abraham Silberschatz, Peter Galvin e Greg Gagne - Editora Campus - 7a edição. [3] Arquitetura de Sistemas Operacionais - Francis B. Machado e Luiz Paulo Maia - LTC Editora - 3a edição. [4] Introdução à Organização de Computadores - Mário Monteiro - LTC Editora 4a edição. [4] Wikipédia: Wikipédia (em português)
45
http://pt.wikipedia.org
Related Documents
Notas De Aula
November 2019 9
Notas Aula - Html
November 2019 17
Notas De Aula De Produto Vetorial
July 2020 8
Notas De Aula Revisao De Algebra Vetorial
April 2020 8
Aula 2 - Sistemas Livres
November 2019 26
Notas De Aula Introducao Dos Circuitos Eletricos
April 2020 4More Documents from ""
Redes Parte 3 - Tratamento Do Sinal
December 2019 9