Please enable JavaScript.

Coggle requires JavaScript to display documents.

Gerenciamento de Memória (Quando ocorre uma falta de página, o sistema…

Gerenciamento de Memória

Quando utilizado, os programas são localizados em posições consecutivas na memória, onde haja espaço e sem realocação durante o carregamento.

  Se o endereço fornecido for igual ou maior que o valor do registrador-limite, gerará um erro e o acesso abortado.





  É uma forma simples de dar a cada processo seu próprio espaço de endereçamento privado porque cada endereço de memória gerado automaticamente tem o conteúdo do registrador-base acrescentado a ele antes de ser enviado à memória.

Uma solução para os programas maiores que a memória foi chamada de Sobreposições (Overlays), que dividia o programa em módulos.

  As sobreposições eram mantidas em disco e carregadas (ou removidas) dinamicamente na memória pelo gerenciador de sobreposições. 





  O trabalho de sobreposição era de responsabilidade do sistema operacional, mas o de dividir o programa em módulos era do programador.

Quando ocorre uma falta de página, o sistema operacional precisa escolher uma página a ser removida da memória a fim de liberar espaço para uma nova página a ser trazida para a memória. Se a página a ser removida tiver sido modificada enquanto estava na memória, ele deverá ser reescrita no disco com o propósito de atualizar a cópia virtual lá existente. Se, contudo, a página não tiver sido modificada, a cópia em disco já estará atualizada e, assim, não será necessário reescrevê-la. A página a ser trazida para a memória simplesmente sobrescreve a página que está sendo destituída.

Impossível de implementar.

  Adia a ocorrência da próxima falta de página o máximo possível.





  Substitui, entre as páginas atuais, a página que será referenciada por último.





  É usado como medida-padrão de desempenho, à qual outros algoritmos podem ser comparados.

NRU (não recentemente usado)

  Utiliza o bit



    referenciado


    modificado 



  que está associado a cada página virtual, que permite que o sistema operacional saiba quais páginas físicas estão sendo usadas e quais não estão.





  Separa as páginas em 4 categorias, com base nos bits referenciado, modificado.





  O NRU remove aleatoriamente uma página da classe de ordem mais baixa que não esteja vazia.

Uma alteração do FIFO, que evita o problema de descartar uma página intensamente usada.

  Isso é feito inspecionando o bit Referenciado da página mais antiga, ou seja, a primeira da fila.





  O que o algoritmo segunda chance faz é procurar uma página antiga que não tenha sido referenciada no clock anterior.





  Se todas as páginas forem referenciadas, o segunda chance degenera-se para o FIFO puro.

Usada menos recentemente.

  Usa Listas Vinculadas. Necessita de hardware especial.





  É uma boa aproximação do algoritmo ótimo de substituição de página. 





  Uma boa aproximação do algoritmo ótimo de substituição de página é baseada na observação de que as páginas muito utilizadas nas últimas instruções provavelmente serão muito utilizadas novamente nas próximas instruções. Ao contrário, páginas que não estão sendo utilizadas por um longo período de tempo provavelmente permanecerão inutilizadas por muito tempo. Quando ocorrer uma falta de página, elimine a página não utilizada pelo período de tempo mais longo.






  Para implementar, a página mais usada deve ficar na dianteira e a menos recentemente usada na parte de trás. Logo a cada referencia de memória a lista deve ser atualizada, fazendo com que seja uma algoritmo caro.

Não frequentemente usado.

  É uma simulação do LRU por software, que ao invés de utilizad listas vinculadas, usa um contador.





  Quando ocorre uma falta de página, a página que tiver a menor contagem será selecionada para a substituição.





  A diferença para o LRU é que lá mantém referências e usa estrutura de dados na qual a menos usada é posta no fim da lista.





  Neste se utuliza apenas um contador, que são incrementados a cada referência à página.





  Aging (envelhecimento) é uma aproximação bem melhor do LRU do que o NFU (muito rudimentar).

É um algoritmo com base no algoritmo do relógio, que também usa informações do conjunto de trabalho.

  Utiliza uma lista circular de molduras de página (assim como no algoritmo do relógio). É formada uma anel e cada entrada da lista contém o campo Instante de Uso, do algoritmo do conjunto de trabalho básico, bem como o bit referenciado e modficado.

Aging (envelhecimento) - baseado no LRU

    WSClock - baseado no conjunto de trabalho

Algoritmo

        Comentário






        Ótimo




        Não implementável, mas útil como um padrão de desempenho.






        NRU




        Aproximação rudimentar do LRU






        FIFO




        Pode descartar páginas importantes






        2ª chance




        Algoritmo FIFO muito melhorado






        Relógio




        Realista






        LRU




        Excelente algoritmo, porém difícil de ser implementado de maneira exata.






        NFU




        Aproximação muito rudimentar do LRU






        Aging (envelhecimento)




        Algoritmo eficiente que aproxima bem o LRU






        Conjunto de Trabalho




        Implementação um tanto cara






        WSClock




        Algoritmo bom e eficiente

Pinning (Retenção de Página)

  Faz com que as páginas envolvidas em um IO não sofram remoção durante esse processo.

Segmentos são espaços de endereçamento completamente independentes.

  Cada segmento é constituído de uma sequência linear de endereços, de 0 a algum máximo.





  O tamanho de cada segmento pode ser qualquer um. Inclusive os tamanhos dos segmentos podem variar durante a execução.





  Como cada segmento constitui um espaço de endereçamento separado, segmentos diferentes podem crescer ou reduzir independentemente, sem afetarem uns aos outros.





  Para especificar um endereço nessa memória segmentada e bidimensional, o programa deve fornecer um endereço composto de duas partes:



    número do segmento;


    endereço dentro do segmento;






  Uma memória segmentada também tem como vantagem simplificar o tratamento das estruturas de dados que estão crescendo ou se reduzindo. A segmentação também facilita o compartilhamento de rotinas ou dados entre vários processos.





  Cada segmento forma uma entidade lógica da qual o programador está ciente - como uma:



    rotina


    arranjo


    pilha



  diferentes segmentos podem ossuir diferentes tipos de proteção. Um segmento podem ser especificado somente para leitura, por exemplo.





  A proteção faz sentido em uma memória segmentada, mas não em uma memória unidimensional paginada: em uma memória segmentada, o usuário está ciente do que exeiste em cada segmento. Normalmente, um segmento não conteria uma rotina e uma pilha, por exemplo, mas ou um ou outro. Visto que cada segmento contém somente um tipo de objeto, o segmento pode ter a proteção apropriada para aquele tipo específico.





  De certo modo, os conteúdos de uma página são acidentais. O programador desconhece o fato de que a paginação está ocorrendo.

Fragmentação Externa

  Após o sistema com segmentação estar sendo executado por algum tempo, como os segmentos tem tamanhos distintos, depois de tantas alocações e desalocações chega-se à fragmentação ou checkerboarding, desperdiçando memória nas lacunas. Isso pode ser sanado com o uso de compactação.

Paginação: Para obter um grande espaço de endereçamento linear sem a necessidade de comprar mais memória física.

  Segmentação: Para permitir que programas e dados sejam divididos em espaços de endereçamento logicamente independentes e para auxiliar o compartilhamento e a proteção.

É a parte do Sistema Operacional que gerencia (parcialmente) a hierarquia de memórias.

  Sua função é gerenciar a memória de modo eficiente: manter o controle de quais partes da memória estão em uso e quais não estão, alocando memória aos processos quando eles precisam e liberando-a quando esses processos terminam.

Dois métodos gerais para lidar com a sobrecarga de memória tem sido desenvolvido com o passar dos anos.

    Swapping


    Memória Virtual

Permite que programas possam ser executados mesmo que estejam apenas parcialmente carregados na memória principal.

  Um método melhor foi desenvolvido e conhecido como Memória Virtual. A ideia é que cada programa tem seu próprio espaço de endereçamento, que é dividido em blocos chamados páginas. Cada página é uma série contígua de endereços. Essas páginas são mapeadas na memória física, mas nem todas as páginas precisam estar na memória física para executar o programa. Quando o programa referencia uma parte de seu espaço de endereçamento que está na memória física, o hardware executa o mapeamento necessário dinamicamente. Quando o programa referencia uma parte de seu espaço de endereçamento que não está em sua memória física, o sistema operacional é alertado para obter a parte que falta e reexecutar a instrução que falhou.






  De certa forma, a memória virtual é uma generalização da ideia do registrador-limite e do registrador-base.

A maioria dos sistemas com memória virtual utiliza uma técnica denominada paginação.

  Os endereços gerados pelo programa são denominados endereços virtuais e constituem o espaço de endereçamento virtual. Em computadores sem memória virtual, o endereço virtual é idêntico ao endereço físico e, assim, para ler ou escrever uma posição de memória, ele é colocado diretamente no barramento da memória. Quando a memória virtual é usada, o endereço virtual não é colocado diretamente no barramento da memória. Em vez disso, ele vai a uma MMU (memory management unit – unidade de gerenciamento de memória), que mapeai endereços virtuais em endereços físicos.






  O espaço de endereçamento virtual é dividido em unidades denominadas páginas (pages). As unidades correspondentes na memória física são denominadas molduras de páginas (page frames). As páginas e as molduras de página são sempre do mesmo tamanho.





  A memória desconhece a existência da MMU e somente enxerga uma solicitação de leitura ou escrita no endereço a qual ela executa. A MMU mapeia todos os endereços virtuais em endereços físicos.






  No hardware real, um bit presente/ausente em cada entrada da tabela de páginas informa se a página está fisicamente presente ou não na memória.






  Caso o programa tente usar uma página virtual não mapeada, a MMU verifica isso e força o desvio da CPU ara o sistema operacional. Essa interrupção é denomida falta de página (page fault). O sistema operacional, então, escolhe uma moldura de página (page frame) pouco usada e a salva em disco. Em seguida, ele carrega a página virtual referenciada pela instrução na moldura de página recém-liberada, atualiza o mapeamento da tabela de páginas e reinicializa a instrução causadora da interrupção.

São esquemas amplamente implementados para acelerar a paginação e para lidar com grandes espaços de endereçamento virtual.

  TLB (Translation Lookaside Buffer) ou Memória Associativa: É um pequeno dispositivo em hardware para mapear os endereços virtuais para endereços físicos sem passar pela tabela de páginas. 






  Geralmente se localiza dentro da MMU.






  Quando um endereço virtual é apresentado à MMU para tradução, o hardware primeiro verifica se o número de sua página virtual está presente na TLB comparando-o com todas as entradas da TLB simultaneamente (em paralelo). Se uma correspondência válida é encontrada e o acesso não viola os bits de proteção, o número da moldura de página é, então, obtido diretamente da TLB, sem a necessidade de buscá-lo na tabela de páginas. Se o número da página virtual estiver presente na TLB, mas a instrução estiver tentando escrever em uma página que permita somente leitura, uma falta por violação de proteção (protection fault) é gerada.






  Quando o número da página virtual não está na TLB a MMU detecta a ausência de página (page miss) e faz uma substituição. Se houver a presença da página ocorre o page hit.






  Quando o gerenciamento da TLB por software é usado, é essencial compreender a diferença entre 2 tipos de ausência. Uma ausência leve (soft miss) ocorre quando a página referenciada não está na TLB, mas na memória. Por outro lado, uma ausência completa (hard miss) ocorre quando a própria página não está na memória (e, é claro, também não está na TLB).

existe apenas uma entrada por moldura de página na memória real, em vez de uma entrada por página do espaço de endereçamento virtual.

  Embora as tabelas de páginas invertidas possam economizar muito espaço – principalmente quando o espaço de endereçamento virtual é muito maior que a memória física – elas apresentam um problema sério: a tradução de virtual para físico torna-se muito mais difícil.

Questões de Projeto para Sistemas de Paginação

Em geral, os algoritmos globais funcionam melhor, especialmente quando o tamanho do conjunto de trabalho varia durante o tempo de vida de um processo. Se um algoritmo local é usado e o conjunto de trabalho cresce durante a execução do processo, uma ultrapaginação (thrashing) pode ocorrer mesmo que existam muitas molduras de página disponíveis na memória. Se o conjunto de trabalho diminuir durante a execução do processo, os algoritmos locais desperdiçam memória. Se um algoritmo global é usado, o sistema deve decidir continuamente quantas molduras de página alocar para cada processo. Uma das maneiras de fazer isso é o monitoramento do tamanho do conjunto de trabalho desse processo, conforme indicado pelos bits de envelhecimento (aging), mas essa estratégia não necessariamente evita a ultrapaginação.

  Uma estratégia de alocação de molduras de páginas para processos é determinar o número de processos em execução e alocar para cada processo o mesmo número de molduras de página.





  É importante notar que alguns algoritmos de substituição de página podem funcionar tanto com uma política de substituição local como global. Por exemplo, o FIFO pode substituir a página mais antiga em toda a memória (algoritmo global) ou a página mais antiga possuída pelo processo atual (algoritmo local). Da mesma maneira, o LRU – ou algum algoritmo aproximado – pode substituir a página menos usada recentemente em toda a memória (algoritmo global) ou a página menos usada recentemente possuída pelo processo atual (algoritmo local).





  A escolha de local versus global é independente, em alguns casos, do algoritmo escolhido.





  Por outro lado, para os demais algoritmos de substituição de página, somente uma estratégia local tem sentido. Por exemplo, os algoritmos conjunto de trabalho e WSClock referem-se a algum processo específico e, portanto, devemos ser aplicados naquele contexto. Para esses algoritmos, não existe um conjunto de trabalho para a máquina como um todo; a tentativa de unir todos os conjuntos de trabalho dos processos causaria a perda da propriedade da localidade e, consequentemente, esses algoritmos não funcionariam bem.

Substitui uma página do mesmo processo.

  Alocam uma fração fixa de memória para cada processo.

Substitui uma página de qualquer outuro processo.

  Alocam molduras de página entre os processos em execução. Assim, o número de molduras de página alocadas a cada processo varia no tempo.

Argumento a favor de uma página pequena:

  É provável que um segmento de código, dados ou pilha escolhido aleatoriamente não ocupe um número inteiro de páginas. Em média, metade da última página permanecerá vazia e, portanto, esse espaço será desperdiçado. Esse desperdício é denominado Fragmentação Interna.






  Páginas grandes farão com que partes do programa não usadas ocupem a memória desnecessariamente.

Espaço I - espaços de instruções (códigos dos programas)

  Espaço D - espaço dos dados 





  Em um computador com esse projeto, ambos os espaços de endereçamento podem ser paginadas, independentemente um do outro. Cada um deles possui sua própria tabela de páginas, que contém o mapeamento individual de páginas virtuais para molduras de página física.

As páginas somente de leitura (como as que contém código de programa) são compartilháveis, mas páginas com dados alteráveis durante a execução não o são.

  Compartilhar dados é mais complicado do que compartilhar código. 





  Enquanto os processos estiverem apenas lendo seus dados, sem modificá-los, essa situação pode perdurar. Assim que um dos dois processos atualizar uma palavra da memória, a violação da proteção contra gravação (read only) causará uma interrupção, desviando-se, assim, para o sistema operacional. Então, é feita uma cópia da página, de modo que cada processo agora tem sua cópia particular. As duas cópias são então marcadas para leitura-escrita – portanto, operações de escrita subsequentes em uma das duas cópias prosseguirão sem interrupções. Essa estratégia significa que páginas não modificadas (incluindo todas as páginas de código) não precisam ser copiadas. Somente páginas de dados que foram realmente modificadas devem ser copiadas separadamente. Esse método, denominado copiar-se-escrita (copy on write), melhora o desempenho por meio da redução do número de cópias.

O compartilhamento pode ser feito em outras granularidades além de páginas individuais.

  Bibliotecas compartilhadas são as DLLs (bibliotecas de ligação dinâmica no Windows).





  Quando um programa é ligado com bibliotecas compartilhadas (que são ligeiramente diferentes das estáticas), em vez de incluir a função atual chamada, o vinculador inclui uma pequena rotina de stubque liga à função chamada no instante de execução.





  Dependendo do sistema e dos detalhes de configuração, as bibliotecas compartilhadas são carregadas quando o programa é carregado ou quando funções nelas são chamadas pela primeira vez. É claro que, se outro programa já tiver carregado a biblioteca compartilhada, não há necessidade de carregá-la novamente – isso é o mais importante. Note que, quando uma biblioteca é carregada ou usada, não é a biblioteca inteira que é lida de uma só vez. As páginas entram uma a uma, de acordo com a necessidade; assim, as funções que não são chamadas não serão trazidas à RAM.

Até agora, supomos que a memória virtual seja transparente a processos e programadores – isto é, tudo o que se vê é um grande espaço de endereçamento virtual em um computador com memória física menor. Em muitos sistemas isso é verdade, mas, em alguns sistemas avançados, os programadores dispõem de algum controle sobre o mapa de memória e podem usá-lo de maneiras não tradicionais para aumentar o desempenho do programa.

  Memória Compartilhada Distribuída: Permite que vários processos em uma rede compartilhem um conjunto de páginas – possível, mas não necessariamente – por intermédio de um único espaço de endereçamento linear compartilhado. Quando um processo referencia uma página não atualmente mapeada, isso causa uma falta de páginas. O manipulador de falta de página (que pode estar no núcleo ou no espaço de usuário) localiza a máquina que contém a referida página e manda um pedido para liberar essa página de seu mapeamento e enviá-la pela rede. Quando a página chega, ela é mapeada na memória e a instrução que causou a fault ade página é reinicializada.

Existem 4 circunstâncias em que o sistema operacional tem de se envolver com a paginação:

    na criação do processo; 


    no tempo de execução do processo; 


    na ocorrência de page fault; 


    na finalização do processo;