Sistemas Operacionais
DCE131 - 2008/1

| Bibliografia | Plano de Curso | Aulas | Listas | Provas | TP1 | TP2 | TP3 | TP Extra | Notas |

Bibliografia básica:

• Livro texto: Sistemas operacionais: projeto e implementação. TANENBAUM, A. S.; WOODHULL, A.S.  2^a Ed. Porto Alegre: Ed. Bookman, 2000.

Leitura adicional:

• Sistemas Operacionais. Conceitos e Aplicações. SILBERSCHATZ, A; GALVIN, P e GAGNE, G. Rio de Janeiro: Editora Campus, 2000.

Plano de curso:

• download.

Programação e Download de Aulas:

Listas de Exercícios:

• As listas serão disponibilizadas neste site com uma semana de antecedência para as provas e elas deverão ser entregues no dia da prova. O adiamento na entrega por no máximo uma aula acarreta na perda de 50% do valor da lista de exercícios.
  • Lista 1 (download);
  • Lista 2 (download);
  • Lista 3 (download);

Matéria das Provas:

• Prova 1:
  • Introdução e Sistema de Arquivos;
• Prova 2:
  • Gerência de Processos/Threads;
• Prova 3:
  •  Gerência de Processos/Threads, Deadlocks, Gerência de Dispositivos, Gerência de Memória e Gerência de Sistemas de Arquivos;
  
  
• Download das provas:
  • Prova 1;
  • Prova 2;
  • Prova 3.

Trabalho Prático (TP1):

• Simulador de Sistema de Arquivos
  • Descrição do trabalho;
  • Código base. Todo aluno DEVE utilizar o código base para confecção do TP1;
  • Arquivo de teste (exemplo): emLote.txt;
   
• Observações; 
  • Valor do trabalho: 10 pontos;
  • O trabalho DEVE ser desenvolvido na linguagem Java;
  • O trabalho é individual;
  • É obrigatório a utilização da Java™ Platform, Standard Edition 6 ou superior;
  • O trabalho DEVE ser entregue via e-mail até o dia: 18/04/2008. Instruções no arquivo de descrição do trabalho;
  • Documentação Java™ Platform, Standard Edition 6 disponível em: http://java.sun.com/javase/6/docs/api/
  • A avaliação será baseada na entrega final (código e relatório) e em entregas parciais a cada sexta-feira (aulas práticas).
  • A aula prática servirá para troca de experiência entre alunos e dúvidas com o professor.
  • O aluno deve enviar a entrega parcial para o e-mail indicado na descrição do trabalho.
  • Título do e-mail da entrega parcial: [SO_2008_1] TP1 - 1a entrega parcial - Nome do Aluno
    
    Entregas:
    • 04/04/2008 - Parcial: Estrutura de árvore em Java com operações necessárias para manipulação do sistema de arquivos simulado;
    • 11/04/2008 - Parcial: Metade das chamadas de sistema implementadas (a escolha do aluno. A decisão deve ser justificada);
    • 18/04/2008 - Entrega final;

Trabalho Prático (TP3):

• Implementação de Algoritmos de Substituição de Páginas
   
• 1a entrega: 13/06/2008 - Algoritmo Ótimo - É possível implementar neste trabalho pois conhecemos todos os acessos a memória; O aluno deve apresentar ao fim da execução as seguintes informações:
  • Quantidade de páginas substituídas ao longo da execução - Como se trata do algoritmo ótimo, nenhum outro algoritmo fará uma quantidade menor de substituições (limite inferior para a comparação com a 2a entrega);
  • Tempo médio gasto para localizar qual página deve ser eliminada da memória física (em milissegundos). Pode variar muito de acordo com as estruturas escolhidas, e com um pré-processamento adequado;
• 2a entrega: 20/06/2008 - MRU (eliminação do Menos Recentemente Usado). A estrutura ordenada fica a escolha do aluno. O aluno deve apresentar ao fim da execução as seguintes informações:
  • Quantidade de páginas substituídas ao longo da execução - Apresentar uma comparação com o algoritmo ótimo (quantos % pior?).
  • Tempo médio gasto para localizar qual página deve ser eliminada da memória física (em milissegundos) - Apresentar uma comparação com o algoritmo ótimo (quantos % melhor?).
  • Apresentar um relatório comparando o desempenho do Algoritmo Ótimo com o MRU, avaliando tempo de processamento e quantidade de substituições necessárias. Deve ser entregue no mesmo dia da apresentação.
• Pode ser implementado em C ou C++ ou Java.
• O trabalho deve ler as instâncias de arquivos fornecidos neste site.
• Download do modelo de arquivo que deve ser reconhecido.
• Instâncias para testes preliminares:
  • Memória Virtual: 1024 páginas; Memória Física: 512 páginas; Acessos: 100000; Picos de Acesso: 2:
    • Download;
    • Ver histograma.
  • Memória Virtual: 1024 páginas; Memória Física: 512 páginas; Acessos: 100000; Picos de Acesso: 3:
    • Download;
    • Ver histograma.
  • Memória Virtual: 1024 páginas; Memória Física: 256 páginas; Acessos: 100000; Picos de Acesso: 2:
    • Download;
    • Ver histograma.
  • Memória Virtual: 1024 páginas; Memória Física: 256 páginas; Acessos: 100000; Picos de Acesso: 3:
    • Download;
    • Ver histograma.

    Instância utilizada para o teste no dia da apresentação: download

Trabalho Prático Extra (TP Extra):

• Busca em Sistema de Arquivos
  • O código desenvolvido no TP1 deve ser utilizado como base deste trabalho;
  • Além de implementar buscas de arquivos e pastas utilizando força bruta (busca em profundidade e busca em largura), o aluno deve escolher uma estrutura de dados para auxiliar o funcionamento da função "search";
    • chamada: search1, efetua a busca em largura na árvore;
    • chamada: search2, efetua a busca em profundidade na árvore;
    • chamada: search3, efetua a busca utilizando uma estrutura de dados para auxiliar para acelerar a busca. Ex.: lista, lista ordenada, tabela hash, arquivo invertido, etc.
  • Exemplos de busca no shell:
    • search1 arquivo01.txt
    • search2 pasta3
    • search3 aloMundo.doc
  • Como resposta, deve ser mostrado no shell, os caminhos completos dos arquivos ou pastas encontrados que possuem o nome buscado;
  • Como base, o aluno poderá utilizar o arquivo de testes emLote2.txt, contido no arquivo compactado emLote2.zip (~450KB), que representa a criação de um extenso sistema de arquivos virtual, seguindo a especificação do TP1. Para carregar o arquivo, utilize a função já desenvolvida batch.
    • Exemplos de buscas e respostas para o arquivo emLote2.txt:
       
      • search1 a01_p047_p049.txt
        Tempo total da busca: 4.78 segundos
        Foi encontrado 1 arquivo com este nome:
        Localização: /p047/p047_p049/a01_p047_p049.txt
         
      • search2 a05_p099_p001.txt
        Tempo total da busca: 6.98 segundos
        Foi encontrado 1 arquivo com este nome:
        Localização: /p099/p099_p001/a05_p099_p001.txt
         
      • search3 p099_p001
        Tempo total da busca: 0.01 segundos
        Foi encontrada 1 pasta com este nome:
        Localização: /p099_p001
         
      • search1 a05_p100_pErro.txt
        Tempo total da busca: 4.09 segundos
        Nenhum arquivo foi encontrado com este nome.
         
  • O resultado das três diferentes buscas deve ser o mesmo, alterando apenas o tempo de processamento da consulta;
  • A busca deve considerar todo o Sistema de Arquivos, ou seja, se existir mais de um arquivo com o mesmo nome, a chamada deve retornar todos os endereços;
  • Junto com o código fonte, deve ser entregue um relatório em PDF contendo:
    • Você deve informar o custo computacional extra envolvido para as operações de: criar arquivo, criar diretório, apagar arquivo, apagar diretório, copiar, diretório, copiar arquivo, mover diretório, mover arquivo e buscar arquivo; Utilizando notação O; (Devem ser consideradas as complexidades de tempo e de memória para cada operação); Este custo computacional se refere as operações adicionais para a estrutura de dados adicional utilizada;
    • Gráfico comparando a performance das três diferentes implementações;
    • Um breve comentário sobre a estrutura, apontando suas vantagens e desvantagens, juntamente com cenários onde sua utilização pode ser adequada, se houver.
• Observações; 
  • Valor do trabalho: 10 pontos;
  • O trabalho DEVE ser desenvolvido na linguagem Java;
  • O trabalho é individual;
  • Não é permitido a utilização de estruturas pré-implementadas na API Java 1.6, com por exemplo: Hashtable, HashSet, Stack, ArrayList, Vector, etc.;
  • É obrigatório a utilização da Java™ Platform, Standard Edition 6 ou superior;
  • O trabalho DEVE ser entregue via e-mail até o dia: 02/05/2008;
  • A aula do dia 25/04/2008 será destinada a explicação e implementação da busca em grafos, especificamente em grafos sem ciclos; (em largura e em profundidade). Também será utilizada para dúvidas com as possíveis estruturas a serem utilizadas; Esta aula será no laboratório D-304;
  • A aula do dia 02/05/2008 será destinada a apresentação final, e entrega do relatório (este deve ser impresso); Esta aula será no laboratório da Computação, no prédio da praça;
  • Documentação Java™ Platform, Standard Edition 6 disponível em: http://java.sun.com/javase/6/docs/api/

Notas:

Voltar