Simulador de Memoria Virtual em C - Implementacao de LRU FIFO e Segunda Chance

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 INSTITUIÇÃO NOME RELATÓRIO TRABALHO PRÁTICO SOBRE MEMÓRIA VIRTUAL Cidade 2023 Resumo do Projeto 3 Decisões de Projeto 3 Resultados 4 Conclusão 5 Resumo do Projeto O presente projeto consiste em uma simulação de algoritmos de substituição de páginas em uma memória virtual O objetivo é avaliar o desempenho de diferentes algoritmos de substituição em relação ao número de page faults e páginas escritas em disco O código foi desenvolvido em linguagem C e recebe como entrada um arquivo de log contendo acessos de memória representados por endereços hexadecimais e operações de leitura R e escrita W O código é estruturado em torno de uma função principal main que lê os parâmetros de entrada abre o arquivo de log e realiza a simulação dos algoritmos de substituição Os algoritmos implementados incluem o Least Recently Used LRU o Random aleatório o FirstIn FirstOut FIFO e o SecondChance segunda chance Cada algoritmo é executado dentro de um bloco switchcase dependendo da opção escolhida pelo usuário na linha de comando Decisões de Projeto Durante o desenvolvimento do projeto foram consideradas algumas decisões para lidar com ambiguidades na especificação Por exemplo quando linhas do arquivo de log não possuíam comandos apenas manipulação de arquivos optei por ignorar essas linhas e não contabilizálas como page faults Essa decisão foi tomada para focar na simulação do comportamento dos algoritmos de substituição de páginas em relação aos acessos de memória propriamente ditos Outra decisão importante foi a criação das estruturas de dados necessárias para a simulação Utilizei uma estrutura PageEntry para representar cada página na tabela de páginas Essa estrutura armazena informações como o endereço da página a operação realizada leitura ou escrita o status de sujeira dirty e em alguns algoritmos a flag de segunda chance Essas estruturas são organizadas em uma tabela de páginas representando a memória virtual Análise do Desempenho dos Algoritmos de Substituição de Páginas A simulação foi executada para diversos programas e arquivos de log utilizando diferentes tamanhos de memória e tamanhos de página Os resultados obtidos permitiram uma análise comparativa do desempenho dos algoritmos de substituição de páginas Para cada programa foram coletados o número total de acessos à memória contidos no arquivo de log o número de page faults páginas lidas e o número de páginas sujas que precisavam ser escritas de volta no disco Essas métricas são importantes para avaliar a eficiência dos algoritmos de substituição e seu impacto no desempenho do sistema Os resultados obtidos mostraram que o algoritmo LRU tende a ter um desempenho superior em relação ao número de page faults pois prioriza a substituição das páginas menos recentemente utilizadas O algoritmo FIFO por sua vez apresenta um desempenho mais simples porém pode gerar mais page faults em cenários onde páginas recentemente acessadas são substituídas O algoritmo de substituição aleatório possui um comportamento imprevisível mas pode ser eficiente em alguns casos O algoritmo de segunda chance combina características do FIFO e do LRU oferecendo uma segunda chance para páginas que seriam substituídas Isso pode reduzir o número de page faults mas também requer uma lógica adicional para marcar e verificar a segunda chance das páginas Em suma a escolha do algoritmo de substituição de páginas depende das características do sistema e das demandas de desempenho específicas Cada algoritmo possui vantagens e desvantagens e a seleção adequada deve ser feita levando em consideração as necessidades do sistema em termos de eficiência na utilização da memória e redução de page faults Resultados Os resultados foram obtidos através do seguinte comando tp2virtual algoritmo arquivolog 64 16384 Para todos os arquivos log que foram disponibilizados substituindo o algoritmo utilizado e o arquivo Tabela 1 Tabela de resultado na execução dos algoritmos log lru 2a fifo random PR PW PR PW PR PW PR Pw compila dor 163190 18236 312110 40017 788705 105371 181714 22304 compre ssor 7753 2238 21435 5664 681406 119371 8510 2489 matriz 73035 15663 202037 42542 811197 66498 84761 16942 simulad or 92079 23493 211997 43514 849956 159927 107314 25931 A contagem das páginas lidas pagesread e escritas pageswritten depende da política de substituição de páginas utilizada e das características do arquivo de log 1 pagesread Essa contagem é incrementada quando ocorre uma falha de página page fault ou seja quando a página desejada não está na memória principal e precisa ser buscada no disco 2 pageswritten Essa contagem é incrementada quando uma página precisa ser escrita de volta no disco Isso ocorre quando a página está sendo substituída e modificada suja ou quando uma operação de escrita é realizada na página A contagem de pageswritten está relacionada à escrita de volta das páginas modificadas para manter a consistência entre a memória principal e o disco Nem todas as páginas lidas precisam ser marcadas como escritas Somente as páginas modificadas sujas precisam ser escritas de volta Em resumo pagesread é incrementado em falhas de página leitura do disco e pageswritten é incrementado quando páginas modificadas são escritas de volta no disco Nem toda leitura de página implica em uma escrita Portanto se você deseja contar todas as páginas acessadas independentemente de serem lidas ou escritas você pode ajustar o código para incrementar pagesread sempre que uma página for acessada independentemente da operação de leitura ou escrita Conclusão A simulação dos algoritmos de substituição de páginas em memória virtual proporcionou uma análise comparativa do desempenho desses algoritmos Foi possível observar que diferentes algoritmos apresentam resultados variados em termos de page faults e páginas escritas em disco A escolha do algoritmo adequado depende das características e requisitos do sistema em questão O projeto permitiu a implementação e comparação de algoritmos clássicos como LRU FIFO Random e SecondChance Essa experiência contribuiu para a compreensão dos desafios envolvidos na gestão da memória virtual e no desenvolvimento de estratégias eficientes de substituição de páginas No geral o projeto proporcionou um aprofundamento no conhecimento dos algoritmos de substituição de páginas em memória virtual bem como na implementação prática desses algoritmos Essa experiência foi enriquecedora para o desenvolvimento de habilidades em programação e análise de desempenho de sistemas computacionais INSTITUIÇÃO NOME RELATÓRIO TRABALHO PRÁTICO SOBRE MEMÓRIA VIRTUAL Cidade 2023 Resumo do Projeto3 Decisões de Projeto3 Resultados4 Conclusão5 Resumo do Projeto O presente projeto consiste em uma simulação de algoritmos de substituição de páginas em uma memória virtual O objetivo é avaliar o desempenho de diferentes algoritmos de substituição em relação ao número de page faults e páginas escritas em disco O código foi desenvolvido em linguagem C e recebe como entrada um arquivo de log contendo acessos de memória representados por endereços hexadecimais e operações de leitura R e escrita W O código é estruturado em torno de uma função principal main que lê os parâmetros de entrada abre o arquivo de log e realiza a simulação dos algoritmos de substituição Os algoritmos implementados incluem o Least Recently Used LRU o Random aleatório o FirstIn FirstOut FIFO e o SecondChance segunda chance Cada algoritmo é executado dentro de um bloco switchcase dependendo da opção escolhida pelo usuário na linha de comando Decisões de Projeto Durante o desenvolvimento do projeto foram consideradas algumas decisões para lidar com ambiguidades na especificação Por exemplo quando linhas do arquivo de log não possuíam comandos apenas manipulação de arquivos optei por ignorar essas linhas e não contabilizálas como page faults Essa decisão foi tomada para focar na simulação do comportamento dos algoritmos de substituição de páginas em relação aos acessos de memória propriamente ditos Outra decisão importante foi a criação das estruturas de dados necessárias para a simulação Utilizei uma estrutura PageEntry para representar cada página na tabela de páginas Essa estrutura armazena informações como o endereço da página a operação realizada leitura ou escrita o status de sujeira dirty e em alguns algoritmos a flag de segunda chance Essas estruturas são organizadas em uma tabela de páginas representando a memória virtual Análise do Desempenho dos Algoritmos de Substituição de Páginas A simulação foi executada para diversos programas e arquivos de log utilizando diferentes tamanhos de memória e tamanhos de página Os resultados obtidos permitiram uma análise comparativa do desempenho dos algoritmos de substituição de páginas Para cada programa foram coletados o número total de acessos à memória contidos no arquivo de log o número de page faults páginas lidas e o número de páginas sujas que precisavam ser escritas de volta no disco Essas métricas são importantes para avaliar a eficiência dos algoritmos de substituição e seu impacto no desempenho do sistema Os resultados obtidos mostraram que o algoritmo LRU tende a ter um desempenho superior em relação ao número de page faults pois prioriza a substituição das páginas menos recentemente utilizadas O algoritmo FIFO por sua vez apresenta um desempenho mais simples porém pode gerar mais page faults em cenários onde páginas recentemente acessadas são substituídas O algoritmo de substituição aleatório possui um comportamento imprevisível mas pode ser eficiente em alguns casos O algoritmo de segunda chance combina características do FIFO e do LRU oferecendo uma segunda chance para páginas que seriam substituídas Isso pode reduzir o número de page faults mas também requer uma lógica adicional para marcar e verificar a segunda chance das páginas Em suma a escolha do algoritmo de substituição de páginas depende das características do sistema e das demandas de desempenho específicas Cada algoritmo possui vantagens e desvantagens e a seleção adequada deve ser feita levando em consideração as necessidades do sistema em termos de eficiência na utilização da memória e redução de page faults Resultados Os resultados foram obtidos através do seguinte comando tp2virtual algoritmo arquivolog 64 16384 Para todos os arquivos log que foram disponibilizados substituindo o algoritmo utilizado e o arquivo Tabela 1 Tabela de resultado na execução dos algoritmos log lru 2a fifo random PR PW PR PW PR PW PR Pw compila dor 163190 18236 312110 40017 788705 105371 181714 22304 compre ssor 7753 2238 21435 5664 681406 119371 8510 2489 matriz 73035 15663 202037 42542 811197 66498 84761 16942 simulad or 92079 23493 211997 43514 849956 159927 107314 25931 A contagem das páginas lidas pagesread e escritas pageswritten depende da política de substituição de páginas utilizada e das características do arquivo de log 1 pagesread Essa contagem é incrementada quando ocorre uma falha de página page fault ou seja quando a página desejada não está na memória principal e precisa ser buscada no disco 2 pageswritten Essa contagem é incrementada quando uma página precisa ser escrita de volta no disco Isso ocorre quando a página está sendo substituída e modificada suja ou quando uma operação de escrita é realizada na página A contagem de pageswritten está relacionada à escrita de volta das páginas modificadas para manter a consistência entre a memória principal e o disco Nem todas as páginas lidas precisam ser marcadas como escritas Somente as páginas modificadas sujas precisam ser escritas de volta Em resumo pagesread é incrementado em falhas de página leitura do disco e pageswritten é incrementado quando páginas modificadas são escritas de volta no disco Nem toda leitura de página implica em uma escrita Portanto se você deseja contar todas as páginas acessadas independentemente de serem lidas ou escritas você pode ajustar o código para incrementar pagesread sempre que uma página for acessada independentemente da operação de leitura ou escrita Conclusão A simulação dos algoritmos de substituição de páginas em memória virtual proporcionou uma análise comparativa do desempenho desses algoritmos Foi possível observar que diferentes algoritmos apresentam resultados variados em termos de page faults e páginas escritas em disco A escolha do algoritmo adequado depende das características e requisitos do sistema em questão O projeto permitiu a implementação e comparação de algoritmos clássicos como LRU FIFO Random e SecondChance Essa experiência contribuiu para a compreensão dos desafios envolvidos na gestão da memória virtual e no desenvolvimento de estratégias eficientes de substituição de páginas No geral o projeto proporcionou um aprofundamento no conhecimento dos algoritmos de substituição de páginas em memória virtual bem como na implementação prática desses algoritmos Essa experiência foi enriquecedora para o desenvolvimento de habilidades em programação e análise de desempenho de sistemas computacionais