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

Prévia do material em texto

Notas da Aula 19 - Fundamentos de Sistemas Operacionais
 
1. Memória Virtual: Introdução
 
Uma das grandes vantagens dos sistemas operacionais multiprogramados é a melhor 
utilização dos recursos da máquina. Com vários processos carregados em memória, existe 
uma alta probabilidade de que ao menos um deles esteja pronto para utilizar o processador. 
Com isso, o SO consegue manter a utilização do processador em níveis altos. Em sistemas 
monoprogramados, por outro lado, apenas um processo ficava carregado em memória. 
Quando este processo se encontrava bloqueado, o processador ficava ocioso, tendo 
sua capacidade desperdiçada. Por este motivo, um dos grandes objetivos dos sistemas 
operacionais modernos é maximizar o grau de multiprogramação da máquina. Em outras 
palavras, o SO deseja ter o maior número possível de processos ativos no sistema. 
 
Um fator que limita o grau de multiprogramação em um sistema computacional é a quantidade 
de memória principal disponível. Como processos ativos precisam ter seu espaço de 
endereçamento em memória, a quantidade de memória RAM da máquina passa a ser um limite 
para a quantidade máxima de processos carregados. Intuitivamente, a soma dos tamanhos dos 
espaços de endereçamento dos processos ativos não pode ultrapassar o tamanho da memória 
principal da máquina.
 
A quantidade de memória principal traz ainda uma segunda limitação: o tamanho máximo 
de um único processo no sistema. A princípio, é impossível ter um processo no sistema cujo 
espaço de endereçamento seja maior que a memória física disponível. Hoje, esta limitação 
não é muito comum, já que são comuns computadores pessoais com gigabytes de memória 
RAM. No entanto, no início da era dos computadores pessoais esta era uma limitação 
séria. A quantidade de memória principal era limitada e começaram a surgir aplicações que 
precisavam de muito espaço de armazenamento. Ainda hoje, certas aplicações científicas 
consomem grandes quantidades de memória, sendo muitas vezes maiores que a capacidade 
de armazenamento da memória principal da máquina.
 
Para solucionar este tipo de limitação, os sistemas operacionais passaram a incorporar em 
seus mecanismos de gerenciamento de memória uma funcionalidade conhecida como Memória 
Virtual. A memória virtual nada mais é que uma grande área de memória secundária (em 
um HD, por exemplo) que, através de determinados mecanismos implementados pelo SO, 
expande a memória principal. Em outras palavras, a memória virtual é um mecanismo utilizado 
pelo SO para simular que a máquina tem mais memória principal do que, de fato, possui. 
 
No Capítulo 4, o conceito de memória virtual foi brevemente comentado, quando foram 
estudados os estados de um processo ativo no sistema. Um dos estados foi o chamado estado 
suspenso, definido como o estado no qual o espaço de endereçamento do processo é retirado 
da memória principal e colocado em memória secundária. A esta operação dá-se o nome de 
swap. Uma razão para mover o espaço de endereçamento de um processo para memória 
secundária é para liberar espaço na memória principal para outro processo. Neste capítulo 
serão estudas políticas para se tomar este tipo de decisão.
 
A maior parte dos sistemas operacionais modernos (ao menos aqueles utilizados em desktops 
e servidores) dão suporte à memória virtual. No Linux, por exemplo, durante a instalação, é 
comum que seja requisitado ao usuário a criação de uma partição de swap, um espaço em 
disco reservado para uso pela memória virtual. Já no Windows, o sistema automaticamente cria 
um arquivo, algumas vezes chamado de arquivo de paginação.
 
O conceito de memória virtual pode ser usado com qualquer um dos métodos de 
gerenciamento de memória vistos no capítulo anterior. No entanto, hoje, é comum ver o 
conceito de memória virtual atrelado ao método de paginação. Por esta razão, o foco neste 
curso será na implementação da memória virtual com paginação, também chamada de 
Paginação sob Demanda. Uma característica interessante da paginação sob demanda é 
o fato de um processo poder estar parcialmente em memória principal e parcialmente em 
memória secundária. Em outras palavras, apenas algumas páginas do processo são movidas 
da memória principal para a memória secundária. Neste caso, o processo não se encontra no 
estado suspenso: este estado só é utilizado quando uma página necessária à execução no 
momento se encontra em memória secundária.
 
2. Paginação sob Demanda
 
Como já explicado, paginação sob demanda é o nome que se dá à implementação de memória 
virtual em um sistema que utiliza gerenciamento de memória por paginação. Quando um 
processo atualmente em execução tenta acessar uma posição da memória principal, a MMU 
identifica a página que contém o endereço desejado e consulta a tabela de páginas. Na tabela, 
a MMU verifica se o bit de validade da página está em 0 ou em 1. Quando a paginação é 
utilizada em conjunto com a memória virtual, o bit de validade de uma página indica se esta se 
encontra carregada em memória principal (bit é 1) ou não (bit é 0).
 
Se o bit de validade indica que a página já se encontra em memória, a MMU prossegue com 
o processo normal de tradução do endereço lógico. O cenário muda quando o bit de validade 
indica que a página não está presente na memória principal. Este evento, no qual um processo 
tenta acessar uma página que não está disponível na memória principal, é conhecido como 
Falta de Página. 
 
Quando ocorre uma falta de página, para que o processo possa continuar sua execução, é 
necessário que o SO busque a página correspondente na memória secundária e a carregue em 
algum quadro da memória principal. Como a busca por uma página em memória secundária 
envolve acesso a disco (uma operação de E/S e, portanto, lenta), o processo que requisitou 
a página é removido do processador e colocado no estado suspenso. Antes de trazer que a 
página necessária seja efetivamente trazida para a memória principal é necessário que o SO 
obtenha um quadro livre para acomodá-la. Se todos os quadros da memória principal estão 
ocupados, é necessário que o SO faça o swap de algum deles para a memória secundária.
 
Eventualmente, a requisição de leitura do disco feita pelo SO ficará pronta e a página desejada 
ficará presente em memória. Antes que o processo em questão possa voltar à execução, o SO 
atualiza a tabela de páginas, indicando o novo endereço da página em memória e configurando 
o bit de validade para 1. Finalmente, o estado do processo passa a ser apto novamente. 
Em algum momento, o escalonador do sistema irá atribuir o processador novamente a este 
processo.
 
É importante notar que no ponto em que a falta de página ocorreu, o processo havia começado 
a executar uma instrução. Entretanto, esta instrução não foi executada com sucesso, pois 
o acesso à memória não ocorreu. Logo, quando o processo é recolocado no processador 
é preciso que o SO configure o valor do registrador PC para que a última instrução seja 
executada novamente.
 
O nome “Paginação sob Demanda” vem justamente do fato das páginas de um processo 
serem trazidas para memória (alocadas) de acordo com a necessidade (quando o processo 
efetivamente precisa das informações contidas nela). Obviamente, no início da sua execução, 
um processo precisa de ao menos uma página carregada em memória, a que contém as 
instruções iniciais do programa. Eventualmente, o programa tentará acessar dados contidos em 
outras páginas, como outras instruções ou valores de variáveis, por exemplo.
 
Na definição tradicional da paginação por demanda, a ideia é realmente só trazer páginas 
a medida que as faltas de página ocorrem. Neste caso, o SO carrega apenas uma página 
inicialmente para cada processo e espera que as faltas de página ocorram. No início, muitas 
faltas irão acontecer, fazendo com que frequentemente o processo seja suspenso e causando 
várias requisições de leitura do disco. Para a grande maioria dos processos, espera-se que 
eventualmente a situação se estabilize, com aspáginas mais frequentemente acessadas 
carregadas em memória principal. Uma variação da paginação por demanda mais comumente 
utilizada é baseada na cópia de várias páginas por vez quando ocorre uma falta de páginas. 
Ao invés de trazer uma única página para a memória, o SO traz um conjunto de páginas que 
ele acredita serão necessárias em um futuro próximo. Se as previsões do SO forem boas, isso 
evitará futuras faltas de página do processo durante algum tempo.
 
Esta previsão realizada pelo SO tem por base o Princípio da Localidade de Referência. Este 
princípio afirma que as informações acessadas por um processo durante um dado intervalo 
da sua execução tendem a estar concentradas em determinadas regiões da memória. Por 
exemplo, imagine que o processo está atualmente executando uma instrução localizada 
na posição 150 (endereço lógico) do seu espaço de endereçamento. É muito provavel 
que a próxima instrução a ser executada será a da posição 151. De fato, a menos que a 
instrução atual seja uma instrução de jump (e que as condições do salto sejam verdadeiras) 
ou do tipo call, a próxima instrução certamente será a da posição 151. Estatísticamente 
falando, a probabilidade de a instrução atual seja uma instrução de jump ou a instrução call é 
consideravelmente menor 50% (basta analisar um programa típico traduzido para linguagem de 
montagem e verificar a frequência de ocorrência destas instruções).
Este princípio também se aplica a dados. Por exemplo, em um programa é bastante comum 
realizarmos várias manipulações de uma mesma variável em uma região relativamente curta 
de código. É comum também que várias posições de um vetor sejam acessadas em sequência. 
O primeiro exemplo é uma ilustração da chamada Localidade Temporal, enquanto o segundo é 
um exemplo da chamada localidade espacial.
 
O princípio da localidade é a base de funcionamento de uma série de mecanismos utilizados 
em sistemas de computação. O exemplo mais tradicional é a memória cache. O benefício 
obtido pelo emprego da memória cache é estatístico. Quando busca-se uma determinada 
informação em cache e esta não é encontrada existe uma penalidade associada a consultar 
a informação na memória principal. Quando isso ocorre, a informação é copiada para a 
cache juntamente com outras informações “próximas”. Graças ao princípio da localidade de 
referência, esta política tem um percentual muito mais alto de acertos que de erros, resultando 
em um valor esperado para o tempo de acesso a memória muito menor do que se a cache não 
fosse empregada.
 
Independente de se o SO tem uma política de escolha de um conjunto de páginas a serem 
carregadas para cada processo ou se ele apenas carrega páginas quando ocorrem faltas, 
o sistema precisa de um critério de divisão de recursos entre os processos. Suponha, por 
exemplo, que a memória principal tem 100 quadros e que há 10 processos ativos. Como o 
SO deve dividir a alocação dos quadros pelos processos? Quantos quadros cada processo 
deve receber? Eventualmente, o SO se encontrará em uma situação na qual vários processos 
desejam ter mais páginas carregadas em memória principal, porém não há quadros suficientes 
para atender a todos.
 
Alguns SOs adotam o critério da divisão igualitária. Neste caso, o SO procura dividir o número 
de quadros disponíveis igualmente entre os processos. Por exemplo, com 100 quadros e 10 
processos, o SO tentará manter uma proporção de 10 quadros alocados por processo. Isso 
pode não ser justo, se considerarmos que processos diferentes têm necessidades de memória 
distintas. Por exemplo, para um processo que tem um total de 50 páginas, 10 quadros é 
pouco. Já para um processo que tem 12 páginas, 10 quadros provavelmente são suficientes 
para manter uma baixa taxa de falta de páginas. Uma outra possível divisão é a chamada 
alocação proporcional. Neste caso, o SO atribui a cada processo uma quantidade de quadros 
proporcional a sua quantidade de páginas. No exemplo anterior, o processo com 50 páginas 
receberia por volta de 4 vezes mais quadros que o processo de 12 páginas.
 
A paginação sob demanda claramente permite que mais processos estejam simultaneamente 
ativos no sistema, já que a soma dos tamanhos dos espaços de endereçamento dos 
processos agora pode ser maior que a quantidade de memória principal disponível. Uma 
outra característica muito interessante da paginação sob demanda é que ela permite que 
processos cujo espaço de endereçamento é maior que a memória principal sejam executados. 
Nos início da era dos computadores pessoais, quando a quantidade de memória RAM não 
passava da ordem dos KBytes, era comum que certas aplicações fossem grandes demais para 
ficarem totalmente carregadas em memória. O advento da memória virtual, não só na forma 
da paginação sob demanda, permitiu que estes programas fossem utilizados neste tipo de 
máquina.
 
3. Desempenho da Paginação sob Demanda
 
Quando estuda-se o emprego da memória cache para melhorar o tempo de acesso à memória 
principal de uma máquina, é possível calcular o chamado Tempo Efetivo de Acesso. Este 
tempo nada mais é que o tempo esperado de acesso, ou seja, o tempo médio de acesso à 
memória, considerando-se que pode acontecer um acerto (hit) ou um erro (miss) quando a 
cache é consultada. Quando a informação está na cache, o tempo de acesso é muito baixo. 
Por outro lado, quando a informação não se encontra lá, o tempo de acesso é mais alto do que 
se a cache não fosse consultada. A média desses dois tempos ponderada pelos percentuais de 
acerto e erro definem o tempo efetivo de acesso.
 
Quando falamos de paginação sob demanda, também há o conceito de acerto e erro. A cada 
tentativa de acesso à memória feita por um processo, duas situações podem ocorrer: ou a 
página que contém a posição de memória desejada está carregada em memória principal 
ou ocorre uma falta de página e o SO precisa buscar a página necessária em memória 
secundária. No primeiro caso, o tempo de acesso é baixo. No segundo caso, o tempo de 
acesso é bem maior, já que ele inclui uma operação de E/S.
 
Suponha que em um determinado sistema a probabilidade de ocorrência de uma falta de 
página é dada por p. Suponha ainda que o tempo de acesso à memória quando a página 
desejada está carregada é e quando não está é . Neste caso o tempo efetivo de acesso 
à memória é dado por:
 
O tempo efetivo de acesso à memória é influenciado por duas grandezas: o tempo de 
tratamento da falta de página e a taxa de ocorrência de falta de páginas. Alguns sistemas 
tentam otimizar ao máximo o primeiro item. Por exemplo, os sistemas baseados no UNIX 
utilizam uma partição do HD dedicada exclusivamente à tarefa de servir de memória 
secundária. Com isso, estes sistemas evitam os overheads inseridos pelos sistemas de arquivo 
(que serão estudados em detalhes no Capítulo 8), reduzindo o tempo necessário ao tratamento 
de uma falta de página. No entanto, o segundo fator (a taxa de ocorrência de falta de páginas) 
é aquele com maior potencial a ser explorado, já que o acesso a disco sempre é muito lento 
(mesmo com partições dedicadas).
 
Idealmente, portanto, os SOs gostariam de manter p = 0, para todos os processos. Entretanto, 
isso nem sempre é possível, já que eventualmente não haverá espaço em memória principal 
para conter todas as páginas de todos os processos. Logo, a ideia é reduzir ao máximo o valor 
de p. Uma grande contribuição para a redução do valor de p é dada pelo chamado Algoritmo de 
Substituição de Páginas.
 
Um algoritmo de substituição de páginas atua quando ocorre uma falta de página e a memória 
principal não tem mais quadros livres para recebê-la. Neste caso, é necessário escolher 
uma das páginas atualmente alocadas em memória principal para ser retirada e copiada de 
volta para a memória secundária (operação de swap). A página escolhida pelo algoritmo de 
substituição de páginas é chamada de Página Vítima. O grande objetivo na escolha da página 
vítima é evitar a escolha de uma página que será necessária novamenteem breve. Se este for 
o caso, em pouco tempo ocorrerá uma nova falta de página, forçando o sistema a realizar uma 
nova requisição de leitura ao disco.
 
Existem vários fatores que devem ser levados em consideração na escolha da página vítima. 
Por exemplo, em geral é mais interessante retirar uma página que não tenha sido modificada 
desde a última vez em que ela esteve em memória secundária. Isso porque quando uma 
página é modificada, ela precisa ser copiada de volta para a área de swap uma vez que seja 
retirada da memória principal. Este processo de cópia aumenta o tempo necessário para o 
tratamento de uma falta de página.
 
Outro fator importante a ser considerado são os acessos às páginas. Pelo princípio da 
localidade de referência, uma página que foi acessada recentemente tem uma probabilidade 
relativamente alta de ser acessada novamente em um futuro próximo. Páginas cujo último 
acesso ocorreu a muito tempo atrás possivelmente não são mais necessárias e podem ser 
substituídas. Obviamente, não existe garantia de que isso seja verdade, mas está é, em geral, 
uma boa regra de referência.
 
Para auxiliar na decisão dos algoritmos de substituição de páginas, os sistemas operacionais 
geralmente armazenam uma série de informações relevantes sobre o estado das páginas na 
tabela da páginas de cada processo. Por exemplo, é comum a existência do chamado bit de 
sujeira (dirty bit), que indica se a página correspondente foi alterada desde do momento em 
que foi colocada na memória principal. Cada vez que uma página é acessada para escrita, a 
MMU automáticamente configura este bit para 1. Quando uma página é trazida para a memória 
principal, o SO configura este bit para 0. O bit de referência (reference bit), por sua vez, indica 
que uma página foi acessada recentemente. A cada acessa à página (tanto para leitura, quanto 
para escrita), a MMU configura este bit para 1. De tempos em tempos, o SO pode zerar este 
bit para todas as páginas. Desta forma, é possível ter uma noção de quais páginas foram 
acessadas nos últimos tempos. 
 
Finalmente, existe o chamado bit de tranca (lock bit) que indica que a página correspondente 
não deve ser retirada da memória principal. Algumas páginas podem ter, por algum motivo, 
uma prioridade maior, de forma que elas nunca sejam retiradas. Isso pode ocorrer, por 
exemplo, no caso de uma operação de E/S. Imagine que um determinado processo requisita 
uma leitura do disco e passa como endereço de memória no qual o conteúdo deve ser 
guardado uma posição pertencente à sua página P, alocada naquele momento no quadro Q da 
memória principal. Durante a execução da operação de E/S, o SO decide retirar a página P e 
colocar outra em seu lugar. Se a transferência de dados é feita através de DMA, por exemplo, 
o DMA continuará tentando escrever o resultado da leitura do disco nas posições de memória 
do quadro Q, embora a página lá localizada possa ser inclusive de outro processo. Para evitar 
isso, o SO ativa o bit de tranca da página uma vez que uma operação de E/S destinada para 
aquela página é requisitada.