Memória Virtual e Paginação em Sistemas Operacionais

SISTEMAS SISTEMAS OPERACIONAIS OPERACIONAIS SISTEMAS SISTEMAS OPERACIONAIS OPERACIONAIS Parte 09 Memória Memória Virtual e Paginação Professor Eduardo Xavier Parte 09 Memória Memória Virtual e Paginação Professor Eduardo Xavier Introdução Introdução O conceito de realocação de memória possibilitou o desenvolvimento de um mecanismo mais sofisticado de utilização de memória denominado memória virtual A técnica de memória virtual onde a memória principal e a memória secundária são combinadas para dar ao usuário a impressão de existir uma memória muito maior que a capacidade real da memória principal O conceito se baseia em não vincular o endereçamento feito pelo programa diretamente a endereços físicos na memória principal permitido que os primeiros também sejam associados a posições na memória secundária Introdução Introdução A técnica de memória virtual permite uma maior quantidade de programas hospedados na memória possibilita um melhor uso do processador e um melhor gerenciamento da fragmentação Algumas funções de gerencia de memória virtual são implementadas diretamente no hardware por questões de desempenho O código do SO deve levar em consideração várias características específicas da arquitetura especialmente a forma como é executado o endereçamento pelo processador Espaço de Endereçamento Virtual Espaço de Endereçamento Virtual A idéia da memória virtual é eliminar o vínculo entre o endereçamento feito pelo programa e os verdadeiros endereços físicos da memória principal Com isso os programas deixam de estar limitados ao tamanho da memória principal pois conseguem endereçar posições de memória muito maiores sem se preocupar com a localização real destes endereços Espaço de Endereçamento Virtual Espaço de Endereçamento Virtual O tamanho da memória virtual chamado de arquivo de paginação no Windows é definido basicamente pelo menor valor dentre os seguintes Capacidade de endereçamento do processador Capacidade de administração de endereços do SO Capacidade de armazenamento dos dispositivos de armazenamento secundário unidades de disco Mapeamento Mapeamento Um programa no ambiente de memória virtual não faz referência a endereços físicos de memória endereço reais mas apenas a endereço virtuais No momento da execução de uma instrução o endereço virtual é traduzido para um endereço físico pois o processador acessa apenas posições da memória principal Essa tradução de endereço é chamada de MAPEAMENTO Quem realiza o mapeamento é o hardware sob a orientação do SO Mapeamento Mapeamento O mecanismo de tradução se encarrega de manter tabelas de mapeamento exclusivas para cada processo relacionando os endereços virtuais do processo às suas posições na memória física O processo que estiver sendo executado tem a sua tabela como referência A troca de tabelas é feita durante a mudança de contexto alterandose o endereço de um registrador específico que indica onde a tabela corrente inicia Mapeamento Mapeamento As entradas na tabela de mapeamento apontam para blocos de memória pois um mapeamento que apontasse para endereços individuais a tabela ficaria grande demais Quanto maior o bloco menos entradas na tabela e menor a tabela se torna A manipulação dos blocos pode exigir tamanho fixo paginação variável segmentação ou trabalhar com ambos segmentação com paginação Memória Virtual por Paginação Memória Virtual por Paginação Funcionamento continuação O espaço de endereçamento total de memória do sistema é chamado de espaço de endereçamento virtual Este espaço é dividido em blocos de tamanho igual chamados de páginas Cada página possui um número que a identifica para que possa se endereçada começando de 0 zero e contém diversos endereços de memória A memória física também é dividida em blocos de iguais com o mesmo tamanho das páginas chamados de molduras de páginas Cada moldura de página também possui um número de identificação e corresponde a uma região da memória física também começando de 0 zero Cada moldura de página hospeda uma página virtual Os endereços de memória usados pelos programas são virtuais e fazem referência a regiões em páginas virtuais ou seja o programa não conhece o endereço real na memória Memória Virtual por Paginação Memória Virtual por Paginação Funcionamento continuação É preciso que algo realize a conversão entre os endereços virtuais e suas localizações reais Em computadores com memória virtual o endereço virtual é enviado para um dispositivo de hardware chamado MMU Memory Management Unit Unidade de Gerenciamento de Memória para ser convertido A MMU é um circuito integrado ou uma coleção deles cuja função é fazer o mapeamento entre endereços virtuais e físicos Memória Virtual por Paginação Memória Virtual por Paginação A tabela de páginas também guarda uma informação que indica se o endereço está ou não na memória principal ele também pode estar armazenado em um arquivo de SWAP Isso é controlado por meio de um bit de validade Se o bit de validade tem valor 0 zero significa que a página virtual não está na memória principal A tentativa de acessar esta página causará um page fault Se o bit de validade tem valor 1 um significa que a página virtual está na memória principal e pode ser acessada Memória Virtual por Paginação Memória Virtual por Paginação Exemplo Imagine um ambiente onde cada página virtual possui 1 Kb de tamanho assim como as molduras de páginas da memória real Note que o espaço de endereçamento virtual possui o dobro do tamanho da memória real qtd de páginas 2 x qtd de molduras Suponha que um determinado programa esteja manipulando o endereço 2060 que é claro é um endereço virtual Memória Virtual por Paginação Memória Virtual por Paginação Exemplo continuação Sabemos que o endereço 2060 deve ficar na página 2 porque O endereço inicial da página 0 é 0 O endereço inicial da página 1 é 1024 1Kb O endereço inicial da página 2 é 2048 2Kb O endereço inicial da página 3 é 3072 3Kb Logo o endereço 2060 fica antes do início da página 3 e após o início da página 2 ou seja dentro da página 2 A MMU consulta as tabelas de páginas para descobrir em que moldura está a página 2 no nosso exemplo está na moldura 1 O endereço virtual é formado pelo número da página virtual onde ele se encontra e um deslocamento dentro desta página No nosso exemplo isso seria Endereço inicial da página virtual 2 2048 Endereço virtual da instrução 2060 Deslocamento 2060 2048 12 Memória Virtual por Paginação Memória Virtual por Paginação Exemplo continuação O endereço físico real é calculado somandose o endereço inicial da moldura de página obtido pela MMU com o deslocamento A página virtual 2 está na moldura 1 logo o endereço inicial da moldura é 1024 O deslocamento do endereço virtual 2060 é 12 calculado anteriormente O endereço real seria 1024 12 1036 Ou seja o endereço virtual 2060 esta localizado fisicamente na memória no endereço real 1036 Políticas de Busca de Páginas Políticas de Busca de Páginas As políticas de busca de páginas determinam quando uma página deve ser carregada para a memória page in Há duas estratégias Paginação por demanda demand paging As páginas são transferidas para a memória principal apenas quando são referenciadas Garante que partes que não são executadas do programa nunca sejam carregadas Paginação antecipada antecipatory paging ou prepaging Além das páginas referenciadas carrega também páginas que tem grande probabilidade de serem referenciadas Agiliza o carregamento mas há risco de carregar páginas inúteis Políticas de Alocação de Páginas Políticas de Alocação de Páginas As políticas de alocação de páginas determinam quantos frames cada processo pode manter carregado na memória principal Há duas estratégias Alocação fixa Cada processo tem um número máximo de frames que podem ser usados durante sua execução O limite de páginas pode ser igual para todos os processos ou individual para cada processo Este limite é definido na criação do processo e pertence ao contexto de software Alocação variável O número máximo de frames que podem ser usados durante sua execução varia de acordo com sua taxa de paginação Processos com taxas elevadas podem aumentar seu limite visando reduzir page faults e viceversa Isso exige monitoramento e aumenta o overhead Políticas de Substituição de Páginas Políticas de Substituição de Páginas As políticas de substituição de páginas determinam quais os frames devem ser liberados da memória principal Importante é preciso verificar se a página foi modificada antes de liberála para não ocorrer perda de dados Neste caso o sistema deve atualizála page out na memória secundária antes do descarte Para fazer isso o sistema mantém um arquivo de paginação page file onde armazena as páginas modificadas e descartadas Se uma página modificada for referenciada novamente ela sofre um page in e será carregada na memória principal Políticas de Substituição de Páginas Políticas de Substituição de Páginas O SO consegue identificar as páginas que foram modificadas através de um bit existente em cada entrada da tabela de páginas chamado bit de modificação dirty bit ou modify bit A política de substituição de páginas pode ser Local Apenas páginas que pertencem ao processo que gerou o page fault podem ser realocadas Global Todas as páginas de todos os processos alocadas na memória principal são candidatas a realocação Algoritmos de Substituição de Páginas Algoritmos de Substituição de Páginas O maior problema da paginação não é decidir que páginas devem ser carregadas na memória principal e sim definir quais páginas devem ser liberadas para dar espaço a novos carregamentos Os algoritmos de substituição de páginas tentam dentro dos limites estabelecidos pelas políticas de gerenciamento de memória prever quais páginas podem ser liberadas causando o mínimo de page faults possíveis O problema é que quanto mais complexos são esses algoritmos maior o overhead de sua execução Para o bem do desempenho do sistema operacional é preciso encontrar um equilíbrio entre a eficiência do algoritmo de substituição de páginas e o esforço computacional para executálo Algoritmos de Substituição de Páginas Algoritmos de Substituição de Páginas Os principais algoritmos de substituição de páginas são Ótimo Seleciona sempre a página com menor possibilidade de ser referenciada no futuro Impossível de ser implementado pois não há como prever com exatidão o comportamento futuro dos processos É uma situação ideal mas serve apenas como modelo de referência Aleatório Todas as páginas hospedadas na memória principal tem a mesma chance de serem selecionadas para liberação É o que gasta menos recursos mas é o menos eficiente e por isso é pouco usado Algoritmos de Substituição de Páginas Algoritmos de Substituição de Páginas Mais algoritmos de substituição de páginas FIFO First In First Out A primeira página que foi utilizada será sempre a primeira a ser escolhida para a liberação ou seja a página que está a mais tempo na memória principal Páginas antigas que são muito referenciadas tornamse um problema LFU Least Frequently Used É mantido um contador de referências para cada página e aquelas que foram referenciadas menos vezes são as escolhidas para liberação O problema dessa abordagem é a mudança de comportamento Páginas muito referenciadas que deixam de ser requisitadas ficam na memória devido aos seus contadores com valores altos Páginas com contadores baixos correm risco de serem liberadas mesmo com um aumento de suas referências por existirem páginas mais velhas com contadores altos Algoritmos de Substituição de Páginas Algoritmos de Substituição de Páginas Mais algoritmos de substituição de páginas continuação LRU Least Recently Used O algoritmo seleciona a página que está a mais tempo sem ser referenciada Cada página mantém registrado o momento da última vez em que foi referenciada ou então as páginas constam em uma lista encadeada ordenada por data de referência Isso tem alto custo de implementação NRU Not Recently Used Semelhante ao LRU mas com implementação mais simples Cada página possui um Bit de Referência BR que indica de a página foi usada recentemente Quando a página é carregada na memória principal o bit é modificado pelo hardware BR1 Periodicamente o sistema altera os valores dos bits BR0 envelhecendo a informação Se combinarmos o bit de referência com um bit de modificação a solução se torna mais refinada permitindo uma seleção mais inteligente Algoritmos de Substituição de Páginas Algoritmos de Substituição de Páginas Mais algoritmos de substituição de páginas continuação FIFO com Buffer de Páginas Trabalha com duas listas uma lista de páginas alocadas LPA e uma lista de páginas livres LPL As duas listas são classificadas por antiguidade páginas mais antigas no início da lista e as mais novas no final Sempre que um processo aloca uma página o sistema retira a mesma do início da LPL e a coloca no final da LPA Sempre que um processo libera uma página ela é retirada do início da LPA e colocada no final da LPL Algoritmos de Substituição de Páginas Algoritmos de Substituição de Páginas Mais algoritmos de substituição de páginas continuação FIFO Circular Clock As páginas possuem um bit de referência BR e são organizadas em uma lista circular semelhante a um relógio Há um ponteiro indicando a posição da página mais antiga da lista Quando se precisa liberar uma página verificase o BR da página indicada pelo ponteiro Se BR 0 a página será descartada pois é antiga e não houve referência recente a ela Se BR 1 a página não será descartada pois foi referenciada recentemente Então o BR da página é alterado para zero e o ponteiro segue para a próxima página mais antiga Tamanho de Página Tamanho de Página Páginas grandes significam Processos compostos por menos páginas Tabelas de páginas menores Maior risco de fragmentação interna na última página de cada processo Páginas pequenas significam Processos compostos por mais páginas Tabelas de páginas maiores Maior risco de um número excessivo de IO no disco O tamanho de página geralmente é definido pelo hardware MMU mas alguns sistemas permitem configuração Paginação em Múltiplos Níveis Paginação em Múltiplos Níveis Em sistemas que implementam apenas um nível de paginação o tamanho das tabelas de páginas pode ser um problema No sistemas de paginação em dois níveis o número da página virtual NPV se divide em dois indicando uma página de diretório e onde destro dela se encontra o endereço do frame Paginação em Múltiplos Níveis Paginação em Múltiplos Níveis Em sistemas que implementam apenas um nível de paginação cada endereço virtual é composto de um NPV número da página virtual e o deslocamento dentro da página Se for um ambiente com grande capacidade de memória o que é comum hoje em dia há muitas entradas nas tabelas de páginas Assim o tamanho das tabelas de páginas pode ser um problema Paginação em Múltiplos Níveis Paginação em Múltiplos Níveis No sistemas de paginação em dois níveis o número da página virtual NPV se divide em dois indicando uma página de diretório NPV1 e onde dentro dela se encontra o endereço do frame NPV2 Nos sistemas cujo endereço é de 64 bits estes dois níveis já são insuficientes e já há soluções com mais níveis Esta solução tem óbvios problemas de desempenho muito IO mas isso pode ser contornado com o uso de memórias cache TLB Translation Lookaside Buffer TLB Translation Lookaside Buffer A solução de mapeamento exige no mínimo dois acessos à memória principal para traduzir cada endereço um à tabela de páginas e outro à página onde está o endereço propriamente dito Para minimizar isso foi criada uma memória especial chamada TLB Translation Lookaside Buffer que funciona como um cache para mapeamentos recentes O sistema só recorre ao mapeamento se não encontrar o endereço na TLB E após o mapeamento a TLB é atualizada Proteção de Memória Proteção de Memória O SO deve impedir que um processo tenha acesso ou modifique uma página de memória sem autorização Cada processo tem sua própria tabela de mapeamento Cada página da tabela tem dois bits de proteção um para leitura outro para gravação Sempre que uma página é referenciada o SO verifica esses bits para determinar se a manipulação obedece as restrições ou de um erro deve ser gerado Compartilhamento de Memória Compartilhamento de Memória Sistemas que adotam memória virtual fazem uso de reentrância conceito apresentado em aulas anteriores para viabilizar o compartilhamento Tabelas de mapeamento dos processos apontam para os mesmos frames na memória principal para compartilhar o código e para frames diferentes para áreas privadas de dados A mesma ideia serve para compartilhar dados mas é preciso levar em conta a sincronização entre os processos Referências Bibliográficas Referências Bibliográficas Arquitetura de Sistemas Operacionais Francis Machado Luiz Maia 4a Edição Capítulo 10 Gerência de Memória Virtual