Simulador de Memoria Virtual em C - TP2 Sistemas Operacionais

Sistemas Operacionais TP2 simulacao de um sistema de memoria virtual Trabalho individual ou em dupla Data de entrega no moodle Nao serao aceitos trabalhos fora do prazo Este trabalho tem por objetivo fazer com que os alunos tenham contato com o tipo de codigo usado em simuladores e apliquem os conceitos de memoria virtual vistos em sala de aula O problema Neste trabalho vocˆe deve implementar um simulador de memoria virtual Assim dentro do simulador vocˆe devera implementar uma replica das estruturas de um mecanismo de gerˆencia de memoria virtual Princıpio geral Seu programa devera ser implementado em C nao serao aceitos recursos de C como classes da biblioteca padrao ou de outras fontes O simulador recebera como entrada um arquivo que contera a sequˆencia de enderecos de memoria acessados por um programa real na verdade apenas um pedacinho da sequˆencia total de acessos de um programa Esses enderecos estarao escritos como numeros hexadecimais seguidos por uma letra R ou W para indicar se o acesso foi de leitura ou escrita Ao iniciar o programa sera definido o tamanho da memoria em quadros para aquele programa e qual o algoritmo de substituicao de paginas a ser utilizado O programa deve entao processar cada acesso a memoria para atualizar os bits de controle de cada quadro detectar falhas de paginas page faults e simular o processo de carga e substituicao de paginas Durante todo esse processo estatısticas devem ser coletadas para gerar um relatorio curto ao final da execucao Forma de operacao O programa que devera se chamar tp2virtual devera ser iniciado com quatro argumentos tp2virtual lru arquivolog 4 128 Esse argumentos representam pela ordem 1 o algoritmo de substituicao a ser usado lru 2a segunda chance fifo e random 2 o arquivo contendo a sequˆencia de enderecos de memoria acessados arquivolog nesse exemplo 1 3 o tamanho de cada paginaquadro de memoria em kilobytes faixa de valores razoaveis de 2 a 64 4 o tamanho total da memoria fısica disponıvel para o processo tambem em kilobytes faixa de valores razoaveis de 128 a 16384 16 MB Formato da saıda Ao final da simulacao quando a sequˆencia de acessos a memoria terminar o programa deve gerar um pequeno relatorio contendo a configuracao utilizada definida pelos quatro parˆametros o numero total de acessos a memoria contidos no arquivo o numero de page faults paginas lidas o numero de paginas sujas que tiveram que ser escritas de volta no disco lembrandose que paginas sujas que existam no final da execucao nao precisam ser escritas Um exemplo de saıda poderia ser da forma valores completamente fictıcios prompt tp2virtual lru arquivolog 4 128 Executando o simulador Arquivo de entrada arquivolog Tamanho da memoria 128 KB Tamanho das paginas 4 KB Tecnica de reposicao lru Paginas lidas 520 Paginas escritas 352 Formato do arquivo de entrada Como mencionado anteriormente cada linha contem um endereco de memoria acessado seguido das letras R ou W indicando um acesso de leitura ou escrita respectivamente Por exemplo as linhas a seguir foram retiradas de um dos arquivos utilizados 0785db58 W 000652d8 R 0005df58 W 000652e0 R 0785db50 W 000652e0 R 31308800 R 00062368 R Os arquivos fornecidos representam o registro de todas as operacoes de acesso a memoria observadas durante a execucao real de alguns programas considerados significativos de classes de programas reais 2 compiladorlog compiladorzip execucao de um compilador que nor malmente utiliza um grande numero de estruturas de dados internas com plexas matrizlog matrizzip um programa cientıfico que utiliza calculos matri ciais relativamente simples mas sobre grandes matrizes e vetores compressorlog compressorzip um programa de compressao de arqui vos que usa estruturas de dados mais simples simuladorlog simuladorzip um simulador de partıculas que executa calculos complexos sobre estruturas relativamente simples Todos os arquivos estao compactados zip e devem ser descompactados antes de serem usados A leitura do arquivo pode ser feita com o comando scanf como no trecho a seguir unsigned addr char rw fscanffilex caddrrw Determinacao da pagina a partir do endereco Como visto em sala para se identificar a pagina associada a um endereco basta descartar os s bits menos significativos do endereco Se a pagina fosse fixada em 4 KB s seria sempre 12 Entretanto para se implementar um tamanho de pagina variavel s deve ser calculado a cada execucao Para simplificar vamos assumir que o tamanho da pagina sera sempre fornecido como uma potˆencia de 2 nao e necessario checar O codigo para se determinar s pode ser unsigned s pagesize tmp Derivar o valor de s tmp pagesize s 0 while tmp1 tmp tmp1 s Nesse caso para um endereco addr a pagina pode ser determinada simples mente fazendose page addr s Implementacao da tabela de paginas Como os enderecos sao de 32 bits nos arquivos fornecidos para paginas de 2 KB as menores que precisam ser consideradas podemos ter ate 21 bits de identificacao de pagina isto e uma tabela de pagina de mais de dois milhoes de entradas Se cada entrada da tabela tiver um inteiro para identificar a pagina 3 fısica teremos um vetor de 8 MB Nao sera muito eficiente mas para fins do simulador essa organizacao e aceitavel Vocˆes nao devem se preocupar em montar uma tabela de paginas hierarquica como seria realmente implementada na pratica isso geraria uma complexidade adicional que nao seria muito util Vocˆes podem tambem implementar uma tabela de paginas reversa ou uma tabela por hash caso se sintam inspirados A estrutura de dados para representar cada quadro fısico deve conter campos para registrar atributos como pagina referenciada instante do ultimo acesso pagina alterada etc os detalhes sao parte da implementacao e vao depender da forma como vocˆes implementarem cada algoritmo Implementacao dos algoritmos de reposicao Os detalhes de outras estruturas de dados que podem vir a ser usadas para os algoritmos sao de livre escolha dos implementadores Vocˆes devem documen tar no relatorio como cada algoritmo foi implementado e certificarse de que o desempenho final do simulador nao seja demasiado lento preferivelmente na ordem de segundos nao dezenas de minutos Vocˆes podem utilizar um contador que inicie em zero e seja incrementado a cada acesso a memoria como a forma de manter o tempo de cada acessoleituraescrita quando necessario Para a implementacao da polıtica aleatoria as funcoes random e srandom podem ser usadas para se controlar o gerador de numeros aleatorios Para se gerar um numero entre 0 e n a expressao random n e suficiente Note se que enquanto houver paginas vazias na memoria elas devem ser preenchidas apenas quando a memoria estiver completamente ocupada uma pagina aleatoria deve ser substituıda Verificacao do funcionamento do programa Apesar da versao a ser entregue precisar gerar apenas o relatorio final des crito anteriormente recomendase fortemente que o programa tenha um modo depuracao onde ele escreva uma linha ou mais descrevendo o que e feito a cada acesso a memoria Assim utilizandose um arquivo de teste reduzido e possivelmente escrito especialmente para testar cada caso de operacao vocˆe pode acompanhar a operacao do programa passoapasso Para isso e permi tido prever um quinto parˆametro opcional que seja definido quando se deseje que o programa tenha esse comportamento com saıda detalhada A forma desse parˆametro e de escolha dos desenvolvedores Pode ser uma palavra como debug pode ser qualquer coisa apenas para configurar um quinto argumento ou pode ser um numero que pode ser usado para especificar um grau de detalhamento numeros maiores geram mensagens de depuracao mais detalhadas por exem plo 4 O que deve ser entregue Vocˆe deve entregar no moodle um arquivo zip ou tgz contendo os arquivos contendo o codigo fonte do programa c e h um Makefile e um relatorio sobre o seu trabalho Nao inclua os arquivos de teste no processo de entrega O relatorio deve conter Um resumo do projeto alguns paragrafos que descrevam a estrutura geral do seu codigo e todas as estruturas importantes Decisoes de projeto descreva como vocˆe lidou com quaisquer ambiguida des na especificacao Por exemplo para este projeto explicar como seu interpretador lida com linhas que nao tˆem comandos apenas manipulacao de arquivos Uma analise do desempenho dos algoritmos de substituicao de paginas para os varios programas utilizados Essa analise de desempenho e uma parte importante do trabalho e sera responsavel por uma fracao significativa da nota 40 Em diversos mo mentos precisamos comparar algoritmos determinar o que esperar em diferen tes condicoes Seu relatorio deve avaliar o comportamento dos algoritmos de reposicao de pagina para os quatro programas em duas situacoes quando o tamanho da memoria cresce com paginas de 4 KB e quando o tamanho da memoria fica constante mas o tamanho das paginas varia de 2 KB a 64 KB em potˆencias de 2 Finalmente embora vocˆe possa desenvolver o seu codigo em qualquer sistema que quiser certifiquese que ele execute corretamente com o sistema operacional Linux Ubuntu Consideracoes finais 1 Duvidas usem o moodle minhaufmg 2 Comece a fazer o trabalho logo pois apesar do programa final ser relati vamente pequeno o tempo nao e muito e o prazo de entrega nao vai ficar maior do que ele e hoje independente de que dia e hoje 3 Vao valer pontos clareza qualidade do codigo e da documentacao e obvia mente a execucao correta da chamada do sistema com programas de teste A participacao nos foruns de forma positiva tambem sera considerada Ultima alteracao 24 de maio de 2023 5