Sistemas Operacionais - AULA 7
 

Gerencia de Memória - Memória Virtual

Conceitos

Desde os primeiros sistemas de gerencia de memória não era mais dado ao programador das aplicações a capacidade de acessar diretamente as memória física. Neste ponto surgiu o conceito de memória virtual. Esse espaço de endereçamento manipulado pelo programador, seja por definição de variáveis ou por alocação dinâmica, é conhecido como memória virtual.

Os dados manipulados pelos programa, são armazenados necessariamente em memória física (real), e neste ponto é necessário que haja alguma tradução. O hardware responsável por essa tradução é a unidade de gerência de memória ou MMU.

Para o programador o espaço de endereçamento é continuo, porém para permitir que somente partes de um determinado programa esteja na memória, é necessário dividir o programa em fragmentos. Esses fragmentos são conhecidos como página. A pagina pode ser virtual, correspondente ao espaço do programador ou pode ser real, correspondente à pagina realmente ocupada na RAM, esse último tipo de página é conhecido como moldura de página.

Em um esquema de gerência de memória por paginação existe uma estrutura que mantém o mapeamento entre páginas e suas respectivas molduras, essa estrutura é conhecida como tabela de páginas. Numa referencia a memória pode ocorrer duas situações: Se a página virtual estiver na memória (se na tabela existir uma moldura equivalente) o programa executa normalmente. Caso não haja moldura correspondente a MMU gera uma interrupção conhecida como PAGE_FAULT. E o programa é interrompido (Bloqueado) até que página em questão (que está em disco) seja alocada em alguma moldura.

Mapeamento

Colocar Desenho

A figura acima mostra como funciona o mapeamento de páginas em molduras.

A maquina possui um capacidade de endereçamento de 64K (16bits). Porém a RAM disponível é apenas de 32K. (é a mesma coisa para um pentium que tem 4G de endereçamento mas tem apenas 64MB RAM).

No exemplo, as páginas virtuais que estão com 'X', estão em disco, e qualquer tentativa de acessar um endereço pertencente a qualquer uma destas páginas vai gerar um PAGE_FALT.

É importante observar que num esquema de paginação o tamanho da moldura e da página virtual sempre são os mesmos. (Na realidade o SO pode trabalhar com páginas de tamanhos que sejam múltiplos do tamanho da moldura).

Unidade de Gerencia de Memória

É um HARDWARE fica posicionado entre a CPU e a memória (registrador MAR e barramento de endereços), é responsável pela validação dos acessos (proteção) e tradução (relocação) das páginas virtuais em físicas. Não confundir com o sistema de gerencia de memória do sistema operacional.

Pode gerar interrupções relacionadas a falta de páginas, como também falha proteção.

Conversão Endereço Virtual em Físico

Colocar Desenho

A conversão de endereços ocorre apenas nos bits mais significativos. O esquema acima mostra a conversão com base no exemplo da figura anterior.

Ou seja com um intervalo de endereçamento de 64k e páginas de 4k termos 16 páginas virtuais (0-15) isso interfere nos quatro bits mais significativos do endereço virtual, pois o resto dos bits (12) são usados para acessar individualmente o dado dentro da página.

Vejamos como funciona a tradução:

Na parte de baixo do esquema o endereço virtual vindo da CPU na parte de cima o endereço traduzido (real) que vai para o barramento de endereços.

Vamos analisar o acesso ao endereço virtual 8196 (0010000000000100)

Esse endereço está na página virtual 2 (0010). Segundo a tabela do esquema acima a pagina virtual 2 está na moldura 6 (0110) então o endereço será convertido para: (0110000000000100). O bit mais significativo pode ser ignorado uma vez que só existem 32K (15bits) endereços reais.

Tabela de páginas

Serve para guardar, dentre outros dados, o mapeamento página virtual, real.

A cada referência à memória é feita uma tradução. Isso significa que o acesso a esta estrutura é critico para a performance do sistema. Uma tabela de página pode ter um número grande de páginas, por isso as técnicas de busca nesta tabela devem ser bem trabalhadas.

Em geral existem formas de armazenar essa tabela, e quanto mais rápido for a memória em que estiver armazenada, maior vai ser a velocidade de acesso.

Implementar essa tabela em hardware, traria ganhos na velocidade de tradução, porém a quantidade de memória necessária para esse armazenamento pode tornar o projeto caro.

A abordagem mais barata é armazenar na RAM, porém o acesso é lento. Essa é a solução usado hoje, porém com certas modificações (mas a frente veremos como a TLB ajuda a melhorar a velocidade).

Tabelas de Páginas Multinível

A implementação linear da tabela de páginas leva a um problema: O número de entradas pode ser muito grande. Por exemplo: Na arquitetura intel as páginas são de 4k e o espaço de endereçamento é de 4G. O resultado é que uma tabela de página para um processo pode ter mais de um milhão de entradas. Desta forma cada acesso a memória implica numa busca nestas entradas.

Um solução que surge para resolver esse problema é dividir essa busca em níveis, diminuindo assim o escopo da busca.

Ex: Para 1M páginas é necessário 20bits. Se as páginas fossem organizadas em diretórios de 1K. Teriamos 1K diretórios com 1K páginas.

Então para buscar um endereço seria necessário pesquisar primeiro a tabela de diretórios de páginas “raiz” com no máximo 1k entradas, e depois pesquisar na tabela de páginas posterior, também com 1k entradas. Desta forma ao invés de buscar em 1M entradas, a busca será feita em 2k entradas.

Sendo assim o formato endereço de 32 bits (com paginas de 4k) ficaria:

Colocar Desenho

Essa implementação de tabelas multinível pode ser feita para diversos níveis, é fácil perceber que quanto mais níveis existir menor será o número de entradas pesquisadas, porém a complexidade do sistema de paginação é aumentada.

O sistema operacional Linux usa 3 níveis, porém existe uma modificação (patch) para usar 4 níveis. (ref: http://lwn.net/Articles/106177/)*.

O windows usa dois níveis (faltou referencias).

Formato de uma Entrada na tabelas de páginas

A tabela de páginas além de possuir informações que permite o mapeamento da memória física em virtual, também guarda outras informações necessárias para o uso do sistema operacional. São elas:

  • Número da moldura: Pagina Real
  • Presente/Ausente: Existe moldura equivalente? (esta na RAM)?
  • Proteção: Simples (rw), Sofisticado (rwx)
  • Referenciada: A pagina já foi usada?
  • Modificada: A pagina foi alterada?
  • Cache desabilitado: A página pode ser colocada na memória cache da(s) CPU(s).

TLB

As TLBs, também conhecidas como memória associativa, são dispositivos de hardware cujo propósito é mapear endereços virtuais em endereços físicos sem passar pela tabela de páginas. Usualmente, ela faz parte da MMU. Ela constitui-se de um pequeno número de entradas, muito rápidas, contendo as entradas das tabelas de páginas mais utilizadas. Quando um endereço virtual é enviado a MMU, ela primeiramente verifica se o seu número de página virtual está presente na TLB. Se o resultado for positivo, a moldura de página é tomada diretamente da TLB sem a necessidade de passar pela tabela de páginas. Caso contrário, a pesquisa é feita normalmente na tabela de páginas. Uma das entradas é removida da TLB e a entrada da tabela de páginas pesquisada é colocada em seu lugar. Referência - Copy/paste descarado ;)

Algoritmos de substituição de páginas

Como visto anteriormente, sempre que uma página (endereço virtual) não estiver em uma moldura de página, uma interrupção ocorre e ela deve ser carregada para uma moldura antes de ser executada. No entanto, alguma página que está atualmente em uma moldura deve ser retirada (gravada em disco). Os algoritmos de substituição de páginas se preocupam em escolher a melhor página a ser retirada da moldura.

Algoritmo ótimo

Deve ser retirada a página que só será referenciada o mais tarde possível. Apesar de, teoricamente, ser um algoritmo interessante, é extremamente difícil prever quando uma página será referenciada;

Substituição de página não recentemente utilizada

o S.O. e o hardware mantêm uma coleção de estatísticas sobre as páginas referenciadas e/ou modificadas (através dos bits de referência e modificação das entradas da tabela de páginas) e dão preferência para a troca de páginas não referenciadas e/ou não modificadas;

Substituição de página FIFO – first-in first-out

A página mais antiga é removida. No entanto, pode estar sendo removida uma página bastante utilizada;

Substituição de página de segunda chance

uma modificação do algoritmo FIFO, que busca não substituir uma página antiga e, no entanto, bastante utilizada. A solução é inspecionar o bit R (referenciada) da página mais antiga; se o bit for 1 (foi referenciada) o bit será limpo e a pesquisa continua. Se todas as páginas tiverem sido referenciadas, o algoritmo FIFO acaba sendo executado e a página mais antiga (que agora estará com o bit R limpo) será substituída;

Relógio

O algoritmo do relógio trabalha da mesma forma que o segunda chance, a diferença é que a fila de páginas é circular, o que o torna mais performático uma vez que não é preciso reinserir páginas no final da fila, bastando apenas ir para o próximo.

Substituição de página menos recentemente utilizada (MRU)

A idéia é que as páginas que foram intensamente utilizadas nas últimas instruções provavelmente serão utilizadas de forma intensa no futuro próximo. Desta forma, deve ser removida a página que não foi utilizada por mais tempo.

Conjunto do Trabalho

Num sistema que use a paginação pura, ao iniciar um programa, nenhuma página seria colocada na memória, e a medida que fosse havendo a necessidade as páginas seriam carregadas, essa técnica é conhecida como paginação por demanda.

A questão é que uma falta de página é um evento que atrasa processo, pois enquanto o tempo de execução de uma instrução é da ordem de nanosegundos, a busca de uma página no disco chega a demorar milisegundos. Sendo assim, os eventos de falta de páginas devem ser evitados ao máximo, isso pode ser feito fazendo boas escolhas sobre as páginas que devem ir a disco, e tentar escolher para seu lugar páginas que serão usadas num futuro próximo (pré-paginação).

A ideia deste algoritmo é esta, tentar minimizar a ocorrência de eventos de faltas de páginas, mas como isso pode ser feito?

Ao se analisar o comportamento de uso das páginas dos processos em geral, percebe-se que em dado intervalo de tempo o processo acessa somente uma pequena quantidade de suas páginas. Essa propriedade dos processos é conhecida como localidade de referencia. E as páginas são chamadas de conjunto do trabalho.

A medida que o processo segue seu fluxo de execução esse conjunto vai mudando lentamente. Então a cada falta de página, será escolhida, para ir para disco, uma página do processo que não pertence ao conjunto do trabalho. O problema é como decidir se uma página pertence a esse conjunto. A ideia original do algoritmo para resolver isto é marcar as páginas de forma a saber quais páginas foram usadas nas ultimas k referencias. Se uma página não foi usada nas ultimas k referencias então ela não pertence ao conjunto do trabalho. Na prática o que usado ao invés de k é o tempo, ou seja, se um página não foi referenciada nos últimos t milisegundos ela não pertence ao conjunto trabalho.