Curso sistemas operacionais 2010 prof. Jorge Kinoshita. Aulas segunda, terça: 16:00-17:40H Maio 10/5 - aula 1 11/5 - aula 2 17/5 - aula 3 18/5 - aula 4 24/5 - aula 5 25/5 - aula 6 31/6 - aula 7 Junho 1/6 - aula 8 7/6 - aula 9 8/6 - aula 10 14/6 - aula 13/aula 14 15/6 - jogo do Brasil 21/6 - aula 11 22/6 - aula 12 28/6 - jogo do Brasil: Brasil-3 x Chile-0 29/6 - Prova1 Julho 5/7 - aula 14/15 6/7 - aula 18/19 12/7 - aula 16 13/7 - aula 17 19/7 - aula 19/20 20/7 - aula 20/21 26/7 - aula 22 27/7 - aula 23 Agosto 2/8 - aula 24 3/8 - aula 25 09/8 - aula 26 10/8 - aula 27 16/8 - aula 28 17/8 => Prova 2 Programação aula a aula. 1 - 1.1 O que é um sistema operacional, 1.2 História dos sistemas operacionais 2 - Visao do hardware 1.3 conceitos de sistema operacional 3 - 1.3 conceitos de sistema operacional; 1.4 chamadas de sistema 4 - 1.4 chamadas de sistema 1.5 estrutra do sistema operacional. 5 => apresentação dos projetos (fase 1) 6 - apresentação dos projetos (fase 1) 7 - 2.1 introdução aos processos 8 - 2.2 comunicação interprocesso até semaforos 9 - de semaforos a 2.3 problemas clássicos de CIP 10 - 2.4 agendamento de processo + problema reader/writer. 11 => Projetos 2.5 visão geral de processos em minix (fase 2) 12 => Projetos 2.5 visão geral de processos em minix (fase 2) prova 1 13 - 3.1 Hardware Entrada e Saida 3.2 Software Entrada e Saida 14 - 3.2 Software Entrada e Saida 15 - 3.3 impasses 16 => Projetos 3.4 visão geral de E/S no minix (fase 3) 17 => Projetos 3.4 visão geral de E/S no minix (fase 3) 18 - 4.1 gerenciamento básico de memória 4.2 troca (swap) 19 - 4.3 memória virtual, 4.4 algoritmos de substituição de página. 20 - 4.4, 4.5 questões para sistemas de paginação. 21 - 4.6 segmentação 22 => Projetos 4.7 visão geral do gerenciamento de memória do minix (fase 4) 23 => Projetos 4.7 visão geral do gerenciamento de memória do minix (fase 4) 24 - 5.1 arquivos 5.2 diretórios 25 - 5.3 implementação do sistema de arquivos 26 => Projetos 5.6 visão geral do sistema de arquivos minix (fase 5) 27 => Projetos 5.6 visão geral do sistema de arquivos minix (fase 5) 28 - Minix filesystem <- (5.4 segurança, 5.5 mecanismos de proteção) prova 2 Livro texto: Sistemas Operacionais - Projeto e Implementação ; Tanenbaum A.S. Woodhull A.S.; Bookman terceira edição Obs: Este livro contém o Minix que serviu de base para a criação do Linux, mas a versão atual é a 3.0. Bons Livros de apoio: - Sistemas Operacionais Modernos 3a. edição; Tanenbaum A.S.; Prentice Hall Obs: Este livro é muito parecido com "Projeto e Implementação" mas não contém o Minix. Por outro lado é mais didático e contém mais informação que o outro. - Sistemas Operacionais com Java; Silberschatz, Galvin, Gane; Editora Campus Obs: Este livro apresenta os conceitos de forma mais clara que os livros do Tanenbaum, porém não usa um sistema operacional próximo da realidade, usa apenas pequenos exemplos em java; e provavelmente o aluno perde a noção do sistema operacional como um todo. avaliação: 3 P1 + 4 P2 + 0.5 E + 2.5 P E = exercícios feitos em aula / vale mais para contar presença. Projetos Fase 1: - Use o seu computador à vontade por uma hora. Veja: 1,2,3, -- quais foram os processos que rodaram nessa uma hora? 4,5,6, -- quais foram os arquivos que foram alterados nesse tempo? Quais arquivos foram abertos nesse tempo? Quais arquivos foram fechados nesse tempo? 7,8,9 -- quais foram as system calls chamadas nesse tempo? Quanto tempo durou cada chamada? Quanto tempo a CPU ficou rodando no kernel e quando tempo ficou rodando no modo usuário? 10,11,12 -- quais foram as system calls chamadas por um determinado processo? Quanto tempo o processo rodou em modo usuário e quanto tempo o processo rodou em modo kernel? Os grupos 1,4,7 e 10 devem fazer usando o opensolaris; dica: use o dtrace para responder as perguntas. Os grupos 2,5,8, e 11 devem fazer usando o freebsd ou o Windows. (dica: também use o dtrace). Os grupos 3,6,9 e 12 devem fazer usando o linux (dica: strace, ltrace ...). Fase 2: 1) Uma grande desvantagem do minix com o microkernel em relacao aos sistemas monolíticos é que ao tratar de uma determinada system call são geradas várias mensagens entre diversos processos. Cada mensagem enviada gera um trap, um chaveamento para o kernel. Como os diversos processos (ex: gerenciador do filesystem ou gerenciador de memória) compartilham muitos dados (como a tabela de processos) então o fluxo de mensagem entre eles é altíssimo e existe uma grande queda de desempenho do sistema operacional gracas a esse fluxo de mensagens. Altere o microkernel do minix de forma a rastrear as mensagens geradas pelo PM ou FS ao tratar de uma system call. O FS, por exemplo, troca diversas mensagens com o driver ao tratar de um "read". Crie um comando no minix (uma system call) que pede o monitoramento de uma determinada system call de um determinado processo e coloca esse monitoramento em uma área de memoria para ser apresentada ao usuario quando ele teclar algo como F2 (se preferir escolha outra tecla). Apresente esse monitoramento ao tratar da system call "read". Coloque no relatório screen shots da tela do minix ao se teclar F2. Nesse monitoramento deve aparecer algo como: -> monitoramento da system call "read" feita para o processo de pid=1919 mensagens trocadas: tipo proc origem proc destino Para resolver esse problema consulte: http://www.pcs.usp.br/~jkinoshi/2008/projs/r5-pedrodaquino.zip 3) idem ao 1, para a system call fork. 5) idem ao 1, para a system call exec. 7) idem ao 1 para a system call open. 9) idem ao 1 para a system call close. 11) idem ao 1 para a system call write. 2) - implementar semáforo no minix. Implementar semáforos no minix. Será necessário estudar o kernel do minix, observando como manter o processo em estado bloqueado ao fazer uma operação de down. Implmente as seguintes system calls: int inicia(int valor); exemplo: S = inicia(3); # inica um semáforo com 3 e retorna o número do semáforo em S. O número zero é reservado; se S == 0 então deu erro em inicia. int down(int S); faz a operação de down no semáforo S; se der problema retorna -1. int up(int S); faz a operação de up no semáforo S int status(int S, int *valor, int *procbloqueados); coloca em valor, o valor do semáforo S e em procbloqueados, o número de processos bloqueados no semáforo. Essas system calls devem ser implementadas pelo processo PM (antigo MM). Dica: dado que existe apenas um processo PM, é fácil pensar que up e down serão mutualmente exclusivos pois o PM estará tratando a mensagem up ou a mensagem down não podendo tratar as duas ao mesmo tempo. Isto é: não será necessário desabilitar as interrupções para se implementar o up e o down. Como o processo usuário vai enviar uma mensagem ao PM então o estado de bloqueado pode ser conseguido, simplesmente se o PM não responder ao processo enquanto o semáforo não subir. Testar os semáforos para delimitar uma área de região exclusiva. 4) - implementar o filósofos jantando em linux... ou qualquer sistema operacional com semáforos, usando código em C fazendo system calls (não java) como o apresentado em aula. Existe o problema da memória ser compartilhada. 6) - entender o chaveamento de processos no minix. Em que rotina do kernel (em assembly) é guardado o estado do processo? Que registradores são guardados? Como o Program Counter é guardado? Não é possível entender bem o código lendo apenas o livro do minix. É necessário consultar documentação sobre a intel. O trabalho é teórico - é necessário simular as instruções e observar o que ocorre com a pilha e registradores que apontam para a pilha, bem como a tabela de processos. Relacione a tabela de processos com a pilha. 8) MINIX - qual o quantum (tempo dado para cada processo) no minix? Fazer experiencias com o quantum muito pequeno e muito grande. Medir o tempo gasto inutilmente (no chaveamento dos processos). Experimente colocar o quantum para o menor tempo possível (onde a CPU vai ficar ocupada praticamente só chaveando processos). Uma forma de se ajustar o menor tempo é verificar o quanto tempo a tarefa IDLE fica rodando e tentar fazer com que o IDLE seja muito pouco utilizado. Comece alterando o kernel do minix de forma que você saiba quantas vezes o minix entrou em IDLE no último segundo. Ao teclar F2 essa informação é apresentada ao usuário. Depois altere o quantum de forma que o minix praticamente não entre em idle mesmo sem carga. 10) - Dado um processo qualquer descubra o quanto tempo ele rodou atendendo system calls (não necessariamente no kernel) e quanto tempo rodou no modo usuário. Caso seja necessário, altere a tabela de processos de forma a contabilizar os tempos. Crie um comando no minix que retorne o tempo rodando no kernel ou em modo usuário para um determinado processo. Exemplo: temproc 123 - retorna o tempo rodando atendendo syscalls e o tempo rodando em modo usuário para o processo 123. Experimente isso para um processo que usa muito a cpu (ex: calcula o pi) e para um processo que usa muito I/O. 12) O relógio do minix interrompe de tempo em tempo. Assim podemos ter uma amostragem do que o minix faz de tempo em tempo. Altere o código do minix para guardar em um vetor de 1000 posições, a identificação dos 1000 processos que rodaram nas últimas 1000 interrupções de tempo (não é necessário pegar a interrupção de tempo mais rápida, pode ser o quantum do processo). Fazer com a tecla F2 apresente esse vetor. Projeto 3 As 12 equipes vão trabalhar diretamente ou indiretamente com drivers. Em 2008 passei o seguinte exercício a uma equipe: A experiência 8 do lab. de microprocessadores: http://www.pcs.usp.br/~jkinoshi/2005/Exp8_revisada_13_08_04.doc tem como objetivo apresentar o que é um driver em linux. Em linux, um driver é um conjunto de rotinas que implentam funções padronizadas como "read" e "write". No caso do minix, um driver é um processo que responde a mensagens padronizadas. Crie um driver muito simples em minix que apenas imprime mensagens quando recebe mensagens padronizadas de outro processo. O driver pode ser associado a /dev/teste. Declare /dev/teste associando um major e minor number e o código do processo associado ao driver. Use "service" para rodar o driver. Gere um relatório sobre isso. As mensagens que o driver deve responder são as mesmas que o driver da impressora respondem, ou seja: * m_type TTY_LINE PROC_NR COUNT ADDRESS * |-------------+---------+---------+---------+---------| * | DEV_OPEN | | | | | * |-------------+---------+---------+---------+---------| * | DEV_CLOSE | | proc nr | | | * ------------------------------------------------------- * | HARD_INT | | | | | * |-------------+---------+---------+---------+---------| * | SYS_EVENT | | | | | * |-------------+---------+---------+---------+---------| * | DEV_WRITE |minor dev| proc nr | count | buf ptr | * |-------------+---------+---------+---------+---------| * | CANCEL |minor dev| proc nr | | | * ------------------------------------------------------- Envie mensagens a /dev/teste como em: echo "lixo" > /dev/teste e veja a mensagem que é impressa pelo seu driver. Faça o driver imprimir a string que recebeu ("lixo"). E a resposta está em: http://www.pcs.usp.br/~jkinoshi/2008/projs/r3-pedrodaquino-Relatorio3.pdf Assim, olhando os documentos acima (experienca8 do lab. de microprocessadores e o relatorio entregue pelos alunos) temos uma boa idéia de como se cria drivers no linux e no minix. Para esse ano, vamos focar mais no acesso ao disco. A princípio, nenhum usuário pode solicitar um setor específico do disco e ler - essas operacoes sao feitas pelo sistema operacional. No entanto, se criarmos ou alterarmos os drivers do linux ou do minix poderemos ler os setores diretamente. Exemplo: é possivel criar o driver lesetor onde facamos algo como: echo "nsetor ntrilha ncilindro ncabeca" > /dev/lesetor onde nsetor é o numero do setor, ntrilha o numero da trilha, etc. Ao executar o "echo" temos os 512 bytes do setor em /var/log/messages Para fazer algo assim, é importante fazer experiencias com um driver simples como o proposto na Exp8_revisada_13_08_04.doc (ou pelo menos ler para se ter uma idéia do que é um driver). Depois disso, é possível pegar o código fonte de um driver de disco e alterar para se fazer o exercício. Comece apenas colocando printk para observar como o driver do disco funciona. Provavelmente existem outras formas de se ler os bytes de um setor e os grupos 1-3 estao livres para encontrar algo sobre isso na internet. O comand "dd" do linux se aproxima do que se pede, porém não relaciona com setores, trilha, cabeca e cilindros. Existem algumas funcoes da bios (biosdisk) que permite esse acesso direto. Os grupos 8-10 devem criar um driver para fazer a leitura do disco. Os grupos 4-6 devem alterar drivers de disco de código aberto para "rastrear" quais são os setores lidos quando um arquivo é acessado. Deve-se procurar entender quais sao os setores lidos que contém informacoes do arquivo mesmo. Vários outros setores que não tem nada a haver com o conteúdo do arquivo também serão acessados. Um deles é o diretório, outros setores tem a haver com a própria estrutura do arquivo. O enderecamento atraves do CHS (cilindro, cabeca, setor) está se tornando gradativamente obsoleto; ao invés disso podem usar o LBA. 1) Criar um programa (usando ou não um driver especial) que leia um setor específicado por trilha, cilindro, etc. do disco no windows / linux usando vfat 2) Instale o minix em uma máquina virtual. Qual é a geometria do disco que o minix enxerga? Crie um mecanismo para se ler um determinado setor dentro do disco especificando a sua localização (trilha, cilindro, cabeça, etc.) e retornar os 512 bytes lidos. 3) Criar um programa que leia um setor específicado por trilha, cilindro, etc. do disco no linux / usando ext2, 3 ou 4. 4) Ao ler um determinado arquivo, marcar quais foram os setores acessados pelo arquivo no windows / linux usando vfat. 5) Ao ler um determinado arquivo, marcar quais foram os setores acessados pelo arquivo no linux / linux usando ext2, 3, 4. 6) Ao ler um determinado arquivo, marcar quais foram os setores acessados pelo arquivo no minix. 7) Criar um driver pelado para o windows como em http://www.pcs.usp.br/~jkinoshi/2005/Exp8_revisada_13_08_04.doc 8) Criar um driver que leia um setor específicado por trilha, cilindro, etc. do disco no windows / linux usando vfat 9) Criar um driver que leia um setor específicado por trilha, cilindro, etc. do disco no linux / usando ext2, 3 ou 4. 10) Criar um driver que leia um setor específicado por trilha, cilindro, etc. do disco no minix. 11) No opensolaris, leia todos os bytes de um arquivo grande, em modo sequencial ou aleatório. No caso do modo aleatório, leia blocos de 512 em bytes, mas de forma aleatória sendo que todoso os blocos do arquivo devem ser lidos. Use uma funcao randomica para gerar os setores a serem lidos. Compare o tempo de execucao do programa quando faz a leitura sequencial ou aleatoria. Usando o dtrace, monitore o seek time em ambos os casos. 12) Usando o opensolaris/dtrace, imprima todos os setores acessados por um arquivo; quando o arquivo é lido. Na apresentaćao, comecar pela equipe 1. Fase 4 As questões sobre o dtrace (tirando a 9) foram elaboradas pelo pelo Phillip Viana. 1) Colete informações arbitrárias sobre a memória virtual de um processo (crie um script que ative os probes que você desejar, como sugestão utilize maj_fault, pgin, pgout e os probes de páginas anônimas). Altere o funcionamento do algoritmo de troca de páginas e então colete as informações novamente. Estabeleça comparações entre as definições formais dos algoritmos e as observações práticas utilizadas pelo DTrace, apontando quais características do algoritmo levaram a uma mudança de comportamento na paginação. Dica: ao editar o arquivo /etc/system, é possível alterar alguns parâmetros do kernel, inclusive relativos a paginação (é necessário reiniciar o sistema operacional!). Observe que é necessário ter o sistema em um estado conhecido em ambos os casos, caso o SO seja reiniciado. 3) Como seria uma implementação dinâmica que substitua parcialmente o vmstat(1M)? Implemente um script em linguagem D que seja capaz de fornecer as principais informações com efeito de probe zero. Dica: utilize o provider PROFILE, que rastreia interrupções de relógio. 5) Crie um script em linguagem D que conte os page-ins e page-outs para um determinado processo. Dica: utilize predicados. Diminua o tamanho da memória dada para a máquina virtual e observe se o número de page-ins e page-outs aumenta. 7) Crie um script em linguagem D que rastreie todos os probes acionados por um processo dentro do provedor vminfo (memória virtual). Exiba as estatísticas agrupadas para cada probe (isto é, dado um determinado processo, faça um script D que exiba estatísticas de page-in, page-outs, acessos à memória anônima, minor faults, major faults, etc.). Neste caso, será essencial utilizar arrays associativos. 9/jk) crie um programa em C no opensolaris (monitorado usando dtrace) que continuamente requisita mais memória através do malloc. Monitore a memória alocada a esse programa. Qual é o máximo de memória alocada antes que o programa cause um erro? Esse valor varia dependendo da capacidade de disco ou do tamanho da memória dados pela máquina virtual? Experimente fazer com que dtrace monitore quando ocorre o problema no programa e quando isso acontece então o tamanho da memória que o programa usava é apresentado. Será que a memória total alocada ao processo cresce até o maximo do espaco de enderecamento virtual? 11) Descubra a quantidade de páginas trocadas com o disco (swap) através dos respectivos probes. Crie um script D que gere estatísticas para um determinado processo. Utilize arrays associativos. 2) Crie um script em linguagem D que contabilize o número de major faults para um determinado processo. 12) Pesquise sobre as ferramentas vmstat(1M) e kstat(1M), que fornecem estatísticas sobre o estado da memória RAM e o kernel (incluindo dados de memória, é claro), respectivamente. Quais são as informações que podem ser obtidas com essas ferramentas? Sabendo que a ferramenta vmstat(1M) está sob a biblioteca libdtrace(3LIB), quais as vantagens e desvantagens dessa implementação em comparação com a criação de um script em linguagem D? 6) Estouro de pilha: usando o dtrace monitorar quando ocorre estouro de pilha. Você pode criar uma rotina recursiva que chama ela mesma indefinidamente. As questões a seguir envolvem o minix: Todos os grupos: Observem que no minix3, ao se teclar F2 aparece uma relação de processos e de como a memória está alocada. Leiam também o livro do Tanenbaum sobre o gerenciamento de memória em minix - item 4.7. Vejam também a figura 4-33 que mostra como os endereços virtuais foram colocados na memória física. A memória do minix é medida em clicks e dividida em segmentos. 8) O minix faz uso do pentium para alocar uma área para o processo e para isso ele acerta a base e o limite da área alocada; ou seja, é necessário um processador que gere uma excessão (interrupção) caso ele acesse uma área fora de seus limites. Explique que instruções do pentium o minix usa para fazer essa reserva de área. Isso é feito pelo PM ou pelo microkernel? (deve ser pelo microkernel). Invasão em área de outro processo: descobrir onde acontece e colocar um breakpoint lá usando o bochs. Escrever como a rotina de interrupção trata dessa invasão. 10) Em que situacões quando um processo morre seus filhos vão para o pai e em que situacoes os filhos morrem junto? No minix, os processos filhos podem se tornar do avô quando o pai é morto; mas em que situações os filhos morrem com o pai? Experimente esses casos e apresente no relatório. 4) Replique o seguinte exercício apresentado à turma do ano retrasado: Mostrar através de um log como a memória foi alocada e desalocada a processos. Toda vez que um processo executar um fork, exec, exit afeta a alocação de memória e isso é registrado no log (em um deterinado arquivo). No log contém informações como: fork - processo /usr/bin/init + segmento 0x30 - 5 clicks. exec - processo /usr/bin/firefox + segmento 0x40 - 7 clicks. exit - processo /usr/bin/firefox - segmento 0x40 - 7 clicks. onde: + : significa que memória está sendo alocada ao processo da posição 0x00230 até 0x00340 - : significa que memória está sendo desalocada e devolvida para a área livre. dica: http://www.pcs.usp.br/~jkinoshi/2007/r4-1.pdf Adicione ao log a informação de qual tipo de segmento (código ou dados) está sendo alocado ou desalocado. A resposta dada pela turma está em: resp: http://www.pcs.usp.br/~jkinoshi/2008/projs/r4_brunogrisi.zip Faça com que a informação sobre o tipo de segmento (código/dado) esteja na mesma linha onde está "fork", "exec", etc. Faça um programa que fique em loop executando o fork e veja o que ocorre no log. O processo deverá fazer algo como: while (1) { fork(); } Esse tipo de processo vai travar o sistema porque vai consumir toda a memória. Fique apresentando o log na tela do computador. Tire printscreens da tela enquanto o processo que gera processos roda. Na apresentacao comecar pela equipe 12. Fase 5 Objetivo - entender como funciona o filesystem do minix. A fig. 5-34 do livro do minix3 apresenta o layout de disco para uma particao de disco rigido pequena. 1. usando o comando dd no minix, apresente os bytes do bloco de inicializacao. Comente sobre esse bloco. 2. usando o comando dd no minix, apresente o superbloco do minix 3. Relacione os parametros do superbloco com a figura 5-35. 3. usando o comando dd no minix + a informacao sobre o superbloco do minix3, apresente o mapa de bits de i-nodes. Quais sao os i-nodes livres? Verifique se isso de fato ocorre. Crie um arquivo. Verifique o numero do i-node do arquivo que acabou de ser criado. 4. usando o comando dd no minix + a informacao sobre o superbloco do minix3, apresente o mapa de bits de zonas. Quais sao as zonas livres? Verifique se isso de fato ocorre. Crie um arquivo com um certo tamanho. Verifique o numero de zonas livres. Crie um arquivo bem maior. Verifique o numero de zonas livres. 5. usando o comando dd no minix + a informacao sobre o superbloco do minix3, apresente o i-node de 3 arquivos diferentes mas que nao sao diretorios. Compare com a figura 5-36. 6. usando o comando dd no minix + a informacao sobre o superbloco do minix3, apresente os bytes do i-node do arquivo que representa o diretorio raiz. Compare essa informacao vinda pelo dd, com o ls no diretorio raiz. Quais sao os i-nodes apontados pelo diretorio raiz? 7. Localize o i-node do arquivo /etc/passwd. Usando o comando dd no minix, apresente o setor que contem o i-node e todos os outros setores (zonas) apontados pelo i-node. Ou seja, apresente todos os setores que compoem o /etc/passwd, desde o i-node, blocos diretos e indiretos. 8. Crie um arquivo (com somente letras "a") pequeno de forma a não precisar a zona de indirecao simples. Veja o seu i-node com o comando dd. 9. Crie um arquivo (com somente letras "a") medio de forma a precisar da zona de indirecao simples. Veja o seu i-node com o comando dd. Para onde aponta a zona de indirecao simples? Veja os bytes dessa zona e para onde eles apontam. Faz sentido? 10. Altere um parametro do i-node de um arquivo usando o comando dd (exemplo: altere os bits rwx). Talvez voce precise de ter um minix com duas medias (uma em / e outra em /home/teste), de forma a fazer essa experiencia na media desmontada. 11. Estude o codigo fonte do comando chmod do minix. Quais system calls ele chama? O que fazem essas system calls? 12. Estude o codigo fonte do comando passwd do minix. Quais system calls ele chama? Em particular veja como suid bit do arquivo é usado: o comando passwd é executado com o poder do owner e não com o poder do user. Veja como é a permissao do executavel passwd (usando ls -al). Apresente o i-node do arquivo passwd e as suas permissoes usando o comando dd. Na apresentacao comecar pela equipe 1.