Sistemas operacionais/Gerência de memória

A maioria dos computadores trabalha com o conceito de hierarquia de memória, possuindo uma pequena quantidade de memória cache, muito rápida, uma quantidade de memória principal (RAM) e uma quantidade muito grande de memória de armazenamento em disco (HD), considerada lenta. O problema básico para o gerenciamento de memória é que os programas atuais são muito grandes para rodarem, completamente, na memória cache. O gerenciador de memória deve ser capaz de controlar parte da memória que está em uso (e quais não estão), alocar memória para processos quando eles necessitam e desalocar quando eles terminam e, principalmente, gerenciar a troca entre a memória principal e o disco, quando a memória principal é muito pequena para armazenar todos os processos.

Existem dois tipos de memória principal: a memória lógica e a memória física. A memória lógica é aquela manipulada pelos programas, ela é visível para os programas; sempre que um programa necessita alocar um espaço na memória esse espaço é alocado em memória lógica. A memória física é a memória implementada pelos circuitos integrados é nela que os espaços alocados em memória lógica vão realmente residir, portanto a memória física tem tamanho menor que a memória lógica, geralmente. Para isso é necessário realizar uma tradução de endereços lógicos para endereços físicos, pois assim um programa que aloca uma memória lógica possa ter de fato uma memória física alocada para si. Esse processo de tradução de endereços lógicos em endereços físicos é realizado por uma unidade de gerência de memória chamada MMU (Memory Management Unit).

Memória lógica x Memória física

Os processos não enxergam a memória física, hardware usado para endereçar os circuitos integrados de memória, e sim a memória lógica, que é a memória capaz de ser endereçada e acessada pelo conjunto de instruções do processador, sendo que cada processo possui a sua memória lógica que é independente da memória lógica dos outros processos. A memória física é implementada pelos circuitos integrados de memória, pela eletrônica do computador. Ela possui espaço de endereçamento físico que é o conjunto formado por todos os endereços dos circuitos integrados que formam a memória, normalmente esses endereços são em formato hexadecimal. A memória lógica possui um espaço de endereçamento lógico, maior que o espaço de endereçamento físico, é formado por todos os endereços lógicos gerado pelo processo, sendo gerado pela CPU e único por processo.

Como o processo "enxerga" endereço de memória lógico e o hardware "enxerga" endereço de memória físico é necessário ter a conversão de endereço de memória lógico para endereço de memória físico. Esse mapeamento de endereço lógico em endereço físico é feito pela MMU, unidade de gerência de memória. Basicamente a MMU que vai mapear os endereços lógicos gerados pelos processos nos correspondentes endereços físicos que serão enviados para a memória.

Existem duas formas bem simples de transformação do endereço lógico para o endereço físico:

A MMU verifica se o endereço lógico é maior que o registrador limite inferior e menor que o registrador limite superior, se sim encaminha o acesso com esse endereço válido, se não, gera uma interrupção de endereçamento inválido. Nesse caso o endereço lógico é igual ao endereço físico.
A MMU verifica se o endereço lógico é menor que o registrador limite superior, se sim adiciona o registrador base ao endereço lógico e encaminha o acesso com esse endereço resultante, se não gera interrupção de endereçamento inválido. Nesse caso o endereço lógico é diferente do endereço físico.

A MMU consiste de um chip ou uma coleção de chips.

Modelo de memória de processos

Para que um programa seja executado ele precisa ser transformado em processo(s), assim é necessário alocar o descritor de processos, alocar espaço na memória para o código (área conhecida como TEXT, onde se localiza o programa principal, as funções e as bibliotecas estáticas), os dados (Data, área onde as variáveis são alocadas - globais, locais estáticas, buffers internos)e a pilha (que possui o HEAP, área onde se localiza as variáveis dinâmicas, e o STACK, endereços de retorno de chamadas e parâmetros de funções).

A atribuição de endereço físico para as áreas de código e áreas de dados pode ser feita de três formas: em tempo de compilação, em tempo de carga e em tempo de execução. Em tempo de compilação o programador já faz a conversão de endereço lógico em endereço físico, pois ele tem conhecimento de qual área da memória ira utilizar. Em tempo de carga o código precisa ser relocável de forma que todas as referências a memória sejam corrigidas para que o endereço de carga corresponda (carregador relocador), em outras palavras no momento da carga o programa executável é interpretado e os endereços corrigidos, dispensando a MMU. Em tempo de execução tem-se o código absoluto e é realizada uma relocação dinâmica usando a MMU, não sendo necessário corrigir os endereços no momento da carga do programa em memória.

Gerenciamento Básico de Memória

Os Sistemas de Gerenciamento de Memória podem ser divididos em duas classes: aqueles que levam e trazem processos entre a memória principal e o disco durante a execução (fazendo troca de processos e paginação) e aqueles que mantém os processos fixos em memória primária. As próximas seções apresentam os mesmos.

Monoprogramação

A monoprogramação consiste em executar um processo por vez na memória, dessa forma todos os recursos de hardware são exclusivos para execução do mesmo.

Monoprogramação sem troca ou paginação

Este é o esquema mais simples possível: só é possível executar um programa de cada vez, compartilhando a memória entre o programa e o S.O. Existem três variações para este modelo:

O SO é carregado na parte inferior da memória, em RAM (Random Access Memory), e deixa a parte superior da memória disponível para o processo do usuário. O endereçamento por parte do processo usuário inicia do fim da RAM até o limite da memória.
O SO é carregado na parte superior da memória, em ROM (Read-Only Memory), e deixa a parte inferior da memória disponível para o processo do usuário. O endereçamento do processo usuário vai do endereço 0 ao início da ROM.
Os drives do SO são carregados em ROM (parte superior) e o restante do SO é carregado em RAM (parte inferior).

Quando o sistema está organizado desta maneira, somente um processo por vez pode estar executando, desta forma esse tipo de sistema é usado em aplicações de caráter muito específico, como por exemplo sistemas de controle de temperatura ou pressão.

Multiprogramação

A multiprogramação nada mais é que manter diversos processos na memória, e essa memória precisa ser dividida de maneira eficiente para que possamos manter o número máximo de processos. Existem diversas técnicas para gerenciar memória que variam de acordo com o hardware do processador.

Multiprogramação com Partições Fixas

A maneira mais simples de implementar a multiprogramação, em termos de memória, é dividir a mesma, primeiramente em uma parte para uso do sistema operacional e outra para uso dos processos de usuários. Depois, a parte dos usuários é dividida em n partições de tamanhos diferentes, porém com valores fixos. Quando um programa chega, há duas possibilidades: ele é colocado em uma fila de entrada da menor partição capaz de armazená-lo ou ele é colocado em uma fila de entrada única.

Com o esquema das partições de tamanho fixos, qualquer espaço não ocupado por um programa é perdido. Na maioria das vezes o programa a ser executado é menor do que a partição alocada para ele. A partição alocada não pode ser menor que o tamanho do programa e é improvável que o tamanho do programa seja exatamente igual ao da partição alocada. Assim, é muito provável que ocorra desperdício de memória para cada programa alocado. Esse desperdício é chamado fragmentação interna, ou seja, perde-se memória dentro do espaço alocado ao processo.

Há outra possibilidade de desperdício de espaço de memória, chamada de fragmentação externa. Ela ocorre quando se desperdiça memória fora do espaço ocupado por um processo. Por exemplo, suponha que há duas partições disponíveis e o processo necessita de uma partição de tamanho maior que qualquer uma das duas livres, e ainda, menor que o total de memória livre, somando-se o tamanho de todas partições livres. Neste caso, o processo não será executado devido ao esquema que a memória é gerenciada, mesmo que exista memória total livre disponível.

Outra desvantagem de classificar os programas em entradas separadas é apresentada quando uma fila para uma partição grande está vazia e filas para partições pequenas estão muito cheias. Uma possível alternativa é colocar todos os programas em uma única fila de entrada e sempre que uma partição encontrar-se livre, alocar para o próximo programa da fila. Para não desperdiçar espaço pode-se realizar uma pesquisa para selecionar o programa que melhor se ajuste ao tamanho da partição. No entanto, isto pode deixar programas pequenos de fora, o que também é indesejável. Neste caso, é interessante dispor de pelo menos uma partição pequena para programas pequenos ou criar uma regra que limite o número de vezes que um programa pode ser ignorado, obrigando que o mesmo seja selecionado em um determinado momento.

Dois conceitos importantes devem ser introduzidos quando há ocorrência de multiprogramação: realocação e proteção.

Programas (jobs) diferentes são colocados em endereços diferentes (partições). Quando um programa é vinculado, o linkeditor deve saber em que endereço o programa deve começar na memória. Como o gerenciador de memória só decide em qual partição (endereço) o programa vai executar quando este chegar, não há garantia sobre em qual partição um programa vai realmente ser executado. Este problema é conhecido como realocação: modificação dos endereços especificados dentro do programa de acordo com a partição onde ele foi colocado.

Outra questão importante está na proteção: programas diferentes não podem ter acesso a dados e/ou instruções fora de sua partição. Sem esta proteção, a construção de sistemas maliciosos seria facilitada. Uma possível alternativa para ambos os problemas é equipar a máquina com dois registradores especiais de hardware chamados registradores de base (RB) e registradores de limite (RL). Quando um processo é agendado, o registrador de base é carregado com o endereço de início de sua partição e o registrador de limite com o comprimento de sua partição. Assim, instruções são verificadas em relação ao seu endereço de armazenamento e para verificar se o mesmo não está fora da partição. O hardware protege os RB e RL para impedir que programas de usuário os modifiquem.

Multiprogramação com Partições Variáveis

Nesse modelo, o tamanho das partições são ajustados de acordo com as necessidades dos processos. Os espaços livres na memória física são mantidos pelo sistema operacional em uma lista, chamada de lista de lacunas. Quando um processo é criado essa lista é percorrida em busca de uma lacuna de tamanho maior ou igual ao requisitado pelo processo, se a lacuna possuir um tamanho maior do que o necessário, será criada uma nova lacuna com a porção extra, dessa forma, o processo receberá o tamanho exato de que necessita.

Existem quatro formas de percorrer a lista de lacunas:

First-Fit: utiliza a primeira lacuna com tamanho suficiente;
Best-Fit: utiliza a lacuna que possuir a menor sobra;
Worst-Fit: utiliza a lacuna que possuir a maior sobra;
Circular-Fit: igual ao First-Fit, mas inicia a procura na lacuna seguinte à última sobra.

Quando o processo termina, e a memória é liberada, é criada uma nova lacuna. Se essa lacuna for adjacente a outras, elas são unificadas.

Com as partições variáveis deixa-se de ter fragmentação interna mas continua com a fragmentação externa (espaços vazios não contíguos), uma solução para resolver este problema seria relocar as partições de forma a eliminar os espaços entre partições criando uma única área contígua porém essa solução consome muito o processador e o acesso ao disco, visto que a cada acesso na memória seria necessário verificar a possibilidade de realocação.

Gerenciamento de memória livre

Além de gerenciar quais espaços em memória estão em uso, é também necessário controlar os espaços de memória livres. Existem duas técnicas mais utilizadas para resolver este problema, estas serão vistas nas próximas seções.

Gerenciamento de memória livre com mapas de bits

Com mapas de bits, a memória é dividida em unidades de alocação. Cada bit do mapa representa uma unidade de alocação, sendo que se o bit for 0, a unidade está livre; caso contrário, a unidade está ocupada. Quanto menor for a unidade de alocação, maior será o mapa de bits e vice-versa. O maior problema com os mapas de bits é que procurar uma lacuna (seqüência de 0s) suficientemente grande para um determinado processo pode ser uma operação muito lenta.

O SO mantém um 1 bit para indicar se cada bloco da memória (ou unidade de alocação) está ocupado (1) ou livre (0). A Memória é dividida em unidades de alocação. Considerações sobre o tamanho do bloco de memória:

Quanto menor a unidade de alocação, maior será o mapa de bits.

- Pequeno: necessidade de muitos bits ⇒ uso ineficiente da memória. Exemplo: se tamanho do bloco = 1 byte, 1/9 da memória serão utilizados para o mapa de bits.

- Grande: memória sub-utilizada, pois se o tamanho do processo não for múltiplo do tamanho da unidade de alocação, uma quantidade de memória considerável será desperdiçada no último bloco.

Vantagens do uso de mapa de bits:

Simplicidade: o tamanho do mapa depende apenas do tamanho da memória e das unidades de alocação.

Desvantagens:

Quando um processo necessita de k unidades de alocação, o gerenciador de memória deve encontrar uma sequência de k bits 0, o que se constitui um processo lento.

Gerenciamento de memória livre com listas encadeadas

Neste caso, é mantida uma lista encadeada com os segmentos de memória livres e encadeados. Uma possível configuração seria manter, em cada entrada, o endereço em que inicia, o seu comprimento e, evidentemente, o ponteiro para a próxima entrada.

A principal vantagem de utilizar uma lista encadeada classificada por endereço é que sua atualização é simples e direta. Vários algoritmos podem ser utilizados para encontrar uma lacuna de memória para alocação de um processo:

Primeiro ajuste: varre a lista desde o início e aloca no primeiro espaço (lacuna) suficientemente grande;
Próximo ajuste: varre a lista da posição atual e aloca no primeiro espaço suficientemente grande;
Melhor ajuste: varre a lista completamente e aloca no espaço que gerar a menor lacuna de memória;
Pior ajuste: varre a lista completamente e aloca no espaço que gerar a maior lacuna de memória disponível, de modo que a lacuna resultante possa ser suficientemente grande para ser útil;
Ajuste rápido: mantém diversas listas separadas para os tamanhos de processos mais comuns.

Memória Virtual

A base do funcionamento da Memória Virtual é o Princípio da Localidade que estabelece que há uma tendência que os futuros endereços de memória de instruções e dados sejam próximos a endereços de memória recentemente acessados. Esse comportamento se deve as características peculiares aos programas, que frequentemente fazem uso de endereços em sequência (vetores), localizados em blocos de código bem definidos e frequentemente invocados (funções), ou de códigos repetitivos (laços de repetição).

A ideia básica da memória virtual é que o tamanho combinado do programa, dos seus dados e da pilha pode exceder a quantidade de memória física disponível para ele, ou seja, neste caso, a simples troca, vista anteriormente, não resolveria o problema. O Sistema Operacional, então, mantém partes do programa atualmente em uso, em forma de páginas ou segmentos, na memória principal e o restante em disco. Essas páginas/segmentos são "trocados" entre memória principal e secundária conforme o SO as solicita, conforme a demanda do programa.

A memória virtual também pode trabalhar em um sistema de multiprogramação, com pedaços de vários programas na memória simultaneamente. Enquanto um programa está esperando parte dele próprio ser trazido para a memória (ele fica esperando a E/S e não pode executar) a CPU pode ser dada a outro processo, assim como em qualquer sistema de multiprogramação.

Para a implementação desta técnica, alguns recursos mínimos são necessários: localização da página através do hardware MMU, carga de página, substituição de página e área de troca, partição ou arquivo especial de troca (swap ou página) destinada a armazenar páginas.

Muitos sistemas de Memória Virtual utilizam uma técnica denominada paginação, vista mais adiante.

Troca (Swapping)

Em algumas situações não é possível manter todos os processos na memória e uma solução para essas situações é o mecanismo conhecido como swapping (troca). A gerência de memória reserva uma área do disco para esse mecanismo, que é utilizada para receber processos da memória. A execução desse processo é suspensa, com isso é dito que o mesmo sofreu uma swap-out. Mais tarde, esse mesmo processo será copiado do disco para a memória, mecanismo conhecido como swap-in. Esse mecanismo de trocas de processos no disco tem como objetivo permitir que o sistema operacional consiga executar mais processos do que caberia na memória.

Esse processo gera um grande custo de tempo de execução para os programas. Fazer a cópia do processo da memória para o disco e depois fazer o inverso é demorado.

Paginação

O espaço de endereço virtual é dividido em unidades chamadas páginas. As unidades correspondentes na memória física são chamadas molduras de página (ou quadros). As páginas e as molduras (quadros) têm sempre exatamente o mesmo tamanho.

No espaço físico (memória) tem-se várias molduras de página. Por exemplo, podem existir 05 páginas situadas no espaço de endereço virtual que são mapeadas na memória física. No entanto, o espaço de endereço virtual é maior que o físico. As outras páginas não são mapeadas. No hardware real, um bit presente/ausente em cada entrada monitora se a página é mapeada ou não.

Quando um programa tenta utilizar uma página não mapeada em uma moldura, a MMU detecta o acontecimento (que a página não está mapeada) e gera uma interrupção, passando a CPU para o Sistema Operacional. Tal interrupção é chamada falha de página. O S.O., então, seleciona uma moldura de página pouco utilizada e grava o seu conteúdo de volta ao disco, substituindo-a pela página requisitada.

Quanto à forma como a paginação pode ser implementada, podemos considerar a paginação simples e a paginação por demanda. Na primeira, todas as páginas lógicas do processo são mapeadas e carregadas para a memória física, isso supondo-se que o espaço de endereçamento de memória para um processo tenha o tamanho máximo igual à capacidade da memória física alocada para processos. No caso da paginação por demanda, apenas as páginas lógicas efetivamente acessadas pelos processo são carregadas. Nesse caso, uma página marcada como inválida na tabela de páginas de um processo pode tanto significar que a página está fora do espaço lógico de endereçamento do processo ou que simplesmente a página ainda não foi carregada. Para descobrir qual das situações é a verdadeira basta conferir o descritor de processo, que contém os limites de endereçamento lógico do processo em questão.

Tabelas de Página

O propósito de tabelas de página é mapear páginas virtuais em molduras de página. No entanto, existem duas questões que devem ser consideradas:

A tabela de páginas pode ser extremamente grande, sendo que cada processo necessita de sua própria tabela de páginas;
O mapeamento deve ser rápido: o mapeamento do virtual para o físico deve ser feito em cada referência da memória, o que pode ocorrer diversas vezes em uma única instrução,não devendo tomar muito tempo para não se tornar um gargalo na execução da instrução.

Neste caso, há a necessidade de um mapeamento de páginas rápido e grande. Existem duas formas básicas de projetar tabelas de páginas:

ter uma única tabela de páginas, através de uma matriz de rápidos registradores de hardware, com uma entrada para cada página virtual, indexada pelo número da página. Esta é uma solução cara se a tabela de páginas é grande;
manter a tabela de páginas inteiramente na memória principal, sendo que o hardware precisa de apenas um registrador que aponta para o início da tabela de páginas.

Esta última solução possui algumas variações que têm desempenho melhor. Uma das propostas que busca evitar o problema de ter enormes tabelas de páginas na memória todo tempo é a de Tabelas de Páginas Multinível. Neste caso, existe uma tabela de primeiro nível e diversas tabelas de segundo nível. O importante aqui é que somente as tabelas mais utilizadas estão presentemente na memória. As demais se encontram em disco. Apesar de permitir um espaço de endereçamento muito grande, o espaço ocupado de memória principal é muito pequeno.

O sistema de tabela de páginas de dois níveis pode ser expandido para três, quatro ou mais níveis, sendo que níveis adicionais dão mais flexibilidade, mas a complexidade da implementação acima de três níveis dificilmente vale a pena. Em relação aos detalhes de uma única entrada de uma tabela de páginas, seu arranjo pode depender da máquina, mas os tipos de informação usualmente são os mesmos.

O campo mais importante é o número da moldura de página, pois o objetivo do mapeamento de páginas é localizar este valor. Ao lado dele, tem-se o bit de presente/ausente. Se este bit for 1, significa que a entrada é válida e pode ser utilizada. Se for 0, a página virtual a que esta entrada pertence não está atualmente na memória. Ao acessar uma entrada da tabela de páginas com este bit configurado como zero ocorrerá uma falha de página.

Os bits "proteção" informam que tipos de acesso são permitidos. Em sua forma simples, este campo contém apenas um bit, com 0 para leitura/gravação e 1 par leitura somente. Um arranjo mais sofisticado é manter 3 bits, cada um para habilitar leitura, gravação e execução da página. Os bits "modificada" e "referenciada" monitoram a utilização da página. Ambos os bits tem como objetivo auxiliar no momento da substituição de páginas. O último bit permite que o cache seja desativado para a página, recurso importante para páginas que são mapeadas em registradores de dispositivo em vez da memória.

Alguns bits auxiliares são, normalmente, adicionados na tabela de páginas para facilitar na substituição de páginas quando a memória física estiver cheia e for necessário retirar uma página lógica da memória física para alocar outra página lógica. Tem-se o bit de modificação (dirty bit) assim que a página for carregada tem valor zero se a página for alterada, na memória física, altera-se o valor para 1, portanto se a página for a página vítima e o bit de modificação for zero não será necessário fazer a cópia da página lógica em memória para a página lógica em disco pois as duas são iguais. Bit de referência: é zero assim que a página lógica é alocada na página física, se a página for acessada altera o valor para um (a MMU altera o valor). Bit de trava: usado em páginas que não podem sair da memória física, o Sistema Operacional "tranca" uma página lógica na memória física ativando esse bit.

TLBs – Translation Lookside Buffers – Memória Associativa

A TLB, também conhecida como memória associativa, é um dispositivo 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 banco de registradores que armazenam um pequeno número de entradas, muito rápidas, contendo as 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 (hit), a moldura de página é tomada diretamente da TLB sem a necessidade de passar pela tabela de páginas na memória (mais lento). Caso contrário (miss), a pesquisa é feita normalmente na tabela de páginas presente na memória. Então, uma das entradas é removida da TLB e a entrada da tabela de páginas pesquisada é colocada em seu lugar.

A TLB melhora bastante o desempenho no acesso à tabela de páginas, visto que registradores são muito mais rápidos que a memória RAM. Suas desvantagens estão em seu custo (registradores são caros), seu tamanho limitado e o fato de existir uma única TLB na MMU, sendo esta compartilhada por todos os processos.

Para calcularmos o desempenho da TLB, podemos tomar h como taxa de acerto (taxa em que a página necessária estará na TLB). Então o erro seria 1-h. Sendo assim, a tempo de acesso hit (tempo necessário para pegar a página da TLB) é dada pelo tempo de acesso à TLB mais o tempo de acesso à memória uma única vez. Enquanto o tempo de acesso miss (quando falta a página na TLB) é dada pelo tempo de acesso à TLB mais o tempo de dois acessos à memória. O tempo de acesso médio é dado pelo tempo de acesso hit multiplicado por h somado do tempo de acesso miss multiplicado por (1-h). Resumindo em fórmulas, temos:

TacessoHit = TacessoTLB + TacessoMemoria
TacessoMiss = TacessoTLB + TacessoMemoria + TacessoMemoria
TacessoMedio = h x TacessoHit + (1-h) x TacessoMiss

A taxa de acerto (h) depende do tamanho da TLB e do algoritmo que a controla, mantendo as páginas mais utilizadas.

Tabelas de Páginas Invertidas

Outra abordagem para trabalhar com páginas é manter uma tabela onde cada entrada representa uma moldura de página ao invés de um endereço virtual. Desta forma, a entrada deve monitorar qual página virtual está associada àquela moldura de página. Embora as tabelas de páginas invertidas economizem quantidade significativas de espaço (pelo menos nas situações em que o espaço de endereço virtual é muito maior que a memória física), elas tem a desvantagem de que o mapeamento (tradução) do endereço virtual para o físico é mais complexo e potencialmente mais lento. Uma forma de facilitar a tradução do virtual para o físico é a utilização da TLB pesquisada por software. A pesquisa pode ser feita a partir de um encadeamento de páginas virtuais que possuam um mesmo endereço hash.

Tamanho de página

Um ponto do qual o projetista deve se preocupar é com o tamanho da página. Conforme visto anteriormente, se esse tamanho de página for grande, pode ocorrer de o processo utilizador não ocupar todo o espaço a ele destinado. Se a página tiver um tamanho demasiadamente pequeno, a tabela de páginas será muito grande.

É possível uma modelagem matemática. Considere que cada processo tenha tamanho de s bytes, e cada página tenha tamanho de p bytes. A tabela de páginas terá um espaço de e bytes por entrada. Assim, o numero de páginas que um processo precisará é de s/p. O espaço que esse processo ocupa na tabela de páginas é s*e/p. O tamanho perdido na última página devido a fragmentação interna será de p/2.

Assim, haverá um custo de s*e/p + p/2 da tabela de páginas. Para que o tamanho da página seja ideal, o custo será zero. Dessa forma, derivando a expressão anterior e igualando a zero obtemos que o tamanho ideal de página é de s*e*sqrt(2).

Thrashing

Estado no qual o sistema operacional ao invés de executar instruções efetivas "gasta" tempo efetuando a troca de páginas entre memória física e memória lógica, em outras palavras desperdiça um tempo significante trazendo ou removendo páginas da memória. Para o usuário a sensação é que o sistema está travado ou congelado e para o hardware há um significante acesso ao disco ao invés de processamento.

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). Veja que o algoritmo escolhido afeta diretamente o desempenho do sistema como um todo, pois "uma escolha errada significa que a página removida será novamente acessada em seguida, gerando uma nova falta de página. É importante que o algoritmo usado seja capaz de remover da memória física páginas que provavelmente não serão necessárias em seguida."[R. da S. Oliveira, A. da S. Carissimi e S. S. Toscani; Sistemas Operacionais 2ª ed]

Os algoritmos de substituição de páginas se preocupam em escolher a melhor página a ser retirada da moldura. Existem várias alternativas:

algoritmo de substituição de página ó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;
algoritmo de substituição de página não recentemente utilizada(NRU): 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;
algoritmo de substituição de página “primeira a entrar, primeira a sair (FIFO – first-in first-out): a página mais antiga é removida.No entanto, pode estar sendo removida uma página bastante utilizada;
algoritmo de substituição de página de segunda chance(SC): 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;
algoritmo de substituição de página menos recentemente utilizada (LRU – least recently used): 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.
algoritmo de substituição de página relógio: O algoritmo SC, apesar de mais eficiente do que algoritmo FIFO, reinsere págimas no final da lista constantemente. Uma solução para isso é q a lista seja ordenada em uma circularmente tal como um relógio. O ponteiro do relogio aponta para a pagina mais antiga e assim que ocorrer uma falta a pagina mais antiga é inspecionada. Se o bit R dessa pagina for 0 ele é substituida, se não esse bit é setado como 0 e o ponteiro aponta para a proxima pagina mais antiga. Esse proesso é então repetido até a proxima pagina com o bit 0 ser encontrada.
algoritmo de substituição de página menos recentemente utilizada(MRU):Trabalha de forma oposta ao algoritmo otimo, pois há a possibilidade de que as paginas que não foram referenciadas continuem não sendo referenciadas. A tarefa de implementa-ló é trabalhosa mas possivel. Ele pode ser implementado de uma maneira mais simples com um contador de 64-bits que é incrementado automaticamente após cada intrução e a tabel de paginas deve ter um campo extra para armazenar o valor do contador. O valor é então armazenado neste campo correpondente à pagina que acabou de ser referênciada. Quando o corre a falta o S.O. examina esse campo e substitui a pagina que tiver o menor deles.Pode-se tambem implementalo com o auxílio de um hardware especial.

Segmentação

A memória virtual apresentada anteriormente é unidimensional, ou seja, os endereços virtuais vão de 0 até algum valor máximo. No entanto, em alguns casos, ter dois ou mais espaços de endereços virtuais separados é uma estratégia interessante. A segmentação prove à máquina vários espaços de endereço completamente independentes, chamados segmentos, liberando o programador da tarefa de gerenciar a expansão e a contração de tabelas, da mesma forma que a memória virtual elimina a preocupação de organizar o programa em overlays.

Os comprimentos de cada segmento podem ser diferentes e podem variar durante a execução. Como cada segmento constitui um espaço de endereçamento completamente independente e diferente, eles podem aumentar ou encolher sem afetar um ao outro. Para especificar um endereço neste tipo de memória segmentada, o programa deve fornecer um endereço de duas partes: um número de segmento e o endereço dentro do segmento. É importante salientar que cada segmento pode conter várias páginas, logo, toda a discussão apresentada anteriormente sobre paginação continua válida aqui. Outra questão fundamental é que, diferentemente da paginação, que é executada inteiramente pelo S.O., os segmentos são entidades lógicas das quais o programador está ciente e as quais ele pode utilizar como qualquer entidade lógica. Um segmento pode conter um procedimento ou uma matriz, ou uma pilha, mas normalmente ele não contém uma mistura de tipos diferentes.

Como cada segmento forma uma entidade lógica da qual o programador está ciente (tal como pilha, procedimentos, etc.) segmentos diferentes podem ter tipos de proteção diferentes: é possível especificar que um procedimento só pode ser executado (sendo proibido ler ou armazenar nele), dados poderão ser lidos e gravados e assim por diante. Este tipo de proteção é útil para detectar erros de programação. A proteção na memória segmentada é importante porque o usuário está ciente do que está em cada segmento. Este modelo é difícil de aplicar a paginação, pois a paginação é invisível ao programador (que não tem como saber de antemão em que página ou moldura um determinado pedaço de programa está), o que não possibilita a separação dos tipos em cada página.

Uma das possibilidades da segmentação é que ela pode facilitar o compartilhamento de procedimentos e/ou dados entre vários processos. Um exemplo é uma biblioteca compartilhada. Neste caso, os procedimentos desta biblioteca permanecem em um único segmento que pode ser utilizado por diversos programas (processos), sem que cada um precise possuí-la em seu espaço de endereço.

A implementação da segmentação difere da paginação porque as páginas têm tamanho fixo e os segmentos não. A substituição dos processos gera lacunas fazendo com que a memória se transforme em um tabuleiro de xadrez, formado por segmentos e lacunas, que pode ser tratado com compactação. No entanto, se os segmentos são grandes pode ser impossível mantê-los na memória principal em sua totalidade (segmentação pura). Neste caso, pode ocorrer uma segmentação com paginação: o espaço lógico é dividido em segmentos, este são divididos em páginas lógicas sendo que cada segmento terá uma tabela de páginas associada. A segmentação com paginação pode ser implementada de formas diferentes dependendo do sistema computacional. No Pentium, por exemplo, duas tabelas são utilizadas para a implantação da segmentação: a LDT (Local Descriptor Table) e a GDT (Global Descriptor Table). Cada programa tem sua própria LDT, mas há uma única GDT compartilhada por todos os programas no computador. A LDT descreve segmentos locais para cada programa e a GDT descreve segmentos do sistema, incluindo o próprio S.O. Com a paginação ativada, os endereços gerados são considerados virtuais e o mapeamento para o endereço físico ocorre como explicado anteriormente.

Segmentação com Paginação

A segmentação com paginação vem como uma solução aos problemas da segmentação e da paginação.Utilizando o meio termo entre os dois métodos combinaremos suas vantagens:

A fragmentação interna da paginação é reduzida pela segmentação.
A fragmentação externa da segmentação é eliminada pela paginação.
A paginação passaria de forma invisível ao programador.
A segmentação ofereceria a divisão do processo em módulos(segmentos).
Teriamos a facilidade do compartilhamento e proteção da memória pela segmentação.

Basicamente,teriamos um segmento composto por um número fixo e reduzido de bytes(páginas). A desvantagen seria o uso de 2 tabelas(segmentação e a de paginação) e devido as páginas serem menores teriamos que a tabela de paginação seria maior.

Conclusões

Sistemas computacionais mais simples não precisam realizar nenhum tipo de gerenciamento pois, usualmente, seus programas rodam diretamente na memória principal disponível. No entanto, esta não é a situação mais comum. Na maioria dos sistemas em uso, os programas são muito maiores que a quantidade de memória principal disponível e/ou é necessário rodar mais de um programa ao mesmo tempo. Nestes casos, a utilização de esquemas de troca, páginas e segmentos pode ser uma alternativa. Um modelo de memória virtual, que fornece um espaço de endereçamento maior do que o físico, pode ser disponibilizado para os programadores no desenvolvimento de seus sistemas. Internamente, no entanto, o S.O. deve ser capaz de gerenciar a memória de forma a manter as partes do programa em uso na memória principal, armazenando as demais partes em disco.