Aula 13 - 26/9/2001

Continuação de Escalonamento Distribuído e início de Sistemas de Arquivos Distribuídos

• Algoritmos de Escalonamento Global (continuação da aula passada)
1. Pontos de Utilização
2. Grafos
3. Sondas
4. Filas de Escalonamento
5. Aprendizado Estocástico
• É uma heurística onde o sistema tenta aprender com a sua história recente; ele tenta determinar qual é a melhor ação a ser tomada baseada no resultado das ações passadas.
• Por exemplo
• determinar inicialmente probabilidades iguais de envio de processos para cada nó.
• se o nó escolhido estava relativamente livre, ele envia uma resposta aprovando a escolha e a sua probabilidade aumenta;
• o oposto ocorre se o nó estava muito carregado
• Pode-se também usar uma espécie de autômato onde cada estado representa um estado global do sistema (baseado na carga nos nós do sistema).
• Em cada estado do autômato, tem-se um vetor de probabilidades para cada nó.
• Monitora-se o estado do sistema periodicamente e determina-se em qual estado do autômato se está.
• Algoritmo de Kunz (1991):
• todas máquinas enviam periodicamente informações sobre o seu estado para um nó central
• se uma máquina está ociosa, ela nunca manda processos prá fora
• se uma máquina está sobrecarregada, o sistema nunca manda processos externos para ela
• carga é avaliada baseado em 1) uso da UCP, 2) uso de memória e 3) E/S
• ele realizou experimentos com diferentes formas de avaliar a carga; em ordem do melhor para o pior:
1. comprimento da fila de processos prontos
2. freqüência de chamadas ao sistema
3. freqüência de mudanças de contexto
4. tempo ocioso da UCP
5. quantidade de memória livre
6. porcentagem de uso da UCP em períodos de 1 minuto
• a diferença no tempo de resposta médio do pior para o melhor foi só 32%
• ele fez experimentos com combinações de critérios mas eles não mostraram nenhum ganho
• usa o autômato descrito acima;
• nós enviam o seu estado para o nó central a cada 8 segundos
• o vetor de probabilidades é usado para se escolher estocasticamente o nó para a execução de cada processo.

Escalonamento Local em Sistemas Distribuídos

• Tanenbaum, seção 4.4
• Normalmente, escalonamento local é independente do global e usa o escalonador do SO local.
• Mas isso pode ser inapropriado se 2 processos em nós diferentes trocam muitas mensagens
• exemplo: Fig 4.20a Tanenbaum, pag. 210.
• Escalonamento Conjunto (co-scheduling) Ousterhout (1982):
• processadores são divididos em fatias de tempo globais
• um broadcast avisa quando se passou de uma fatia para a seguinte
• Fig. 4.20b  Tanenbaum, pag. 210. Exemplo: executar grupo de 4 processos que se comunicam.

• Capítulo 7 do Galli, seções 4.3 e 4.4 do Tanenbaum e capítulo 7 e 8 do Sinha.

Sistemas de Arquivos Distribuídos

O sistema de arquivos é um dos subsistemas mais importantes em SOs

Oferece uma visão abstrata de dispositivos de armazenamento secundário (discos, fitas, etc.)

• No princípio, as estações eram isoladas e era necessário dar um rsh para se conectar a outras máquinas e obter acesso aos arquivos
• Insatisfeitos com isso criaram os primeiros sistemas de arquivos distribuídos através do comando rcp maquina:caminho
• modelo de transferência completa (upload/download)
• Tanenbaum Fig. 5.1a, pag. 247
• funcionou muito bem por muito tempo (até meados/final da década de 80)
• desvantagens
• o usuário é responsável por saber onde cada arquivo está guardado;
• o programa continha o nome do servidor onde os arquivos estão guardados
• pouca flexibilidade
• Depois, criou-se o modelo de acesso remoto a arquivos:
• o serviço de arquivos oferece operações (e.g. open, read, write, close) para acesso a arquivos remotos
• Tanenbaum Fig. 5.1b, pag. 247
• os caminhos para os arquivos assumem a forma /servidor/pathname

• é necessário algum esquema para mapear o espaço de nomes do sistema de arquivos aos diversos servidores
• normalmente se usa um espaço de nomes hierarquico e se associa diferentes pedaços da hierarquia a diferentes servidores
• Na verdade, existem 3 modelos de nomes em um sistema de arquivos distribuídos:
1. nome da máquina + caminho (e.g., /maquina/pathname ou maquina:pathname)
2. montando sistemas de arquivos remotos na hierarquia local de sistemas de arquivos
3. um espaço de nomes global único comum a todas as máquinas do sistema
• transparência de plataforma do cliente e do servidor
• é necessário definir um protocolo padrão de comunicação independente da plataforma

• o que acontece quando 2 ou mais usuários (processos) acessam o mesmo arquivo ao mesmo tempo?
• o que acontece se temos uma seqüência rápida de leituras e escritas em um arquivo? qual valor é lido pela leitura?
• Em um sistema centralizado UNIX, um read sempre devolve o valor escrito pelo último write
• Em sistemas distribuídos há 4 tipos de semântica mais comuns:
• semântica UNIX (toda operação em um arquivo é visível imediatamente por todos nós)
• semântica de sessão
• uma sessão é aberta com open e fechada com close
• mudanças não são visíveis a outros processos até que a sessão seja fechada
• arquivos imutáveis
• facilita compartilhamento e replicação
• transações
• init, abort, commit transaction
• mudanças possuem a propriedade de tudo ou nada
• mudanças só são visíveis após um commit é feito

Referências

• Tanenbaum, seção 5.1; Galli, seção 8.2 (incompleto); Silberschatz 5a ed., cap. 17; monografia sobre SAD na página de leituras recomendadas.