Um ponto fundamental para implementar sistemas de memória virtual

Gerenciamento de Mem�ria

1. Introdu��o

   Índice Show

   • Gerenciamento de Mem�ria
   • 1. Introdu��o
   • 2. Endere�amento
   • 3. Aloca��o
   • 4. Mem�ria Virtual
   • 5. Desempenho
   • 6. Vis�o global do sistema
   • Quais os benefícios oferecidos pela técnica de memória virtual?
   • O que é e como funciona o mapeamento em relação a memória virtual?
   • Como mapear endereços virtuais para endereços físicos?
   • Quanto ao Page Fault Assinale a alternativa correta?

2. Endere�amento

3. Aloca��o

4. Mem�ria virtual

5. Desempenho

Os t�picos a serem examinados podem ser encontrados nos seguintes cap�tulos de livros:

1. Modern Operating Systems, Tanenbaum, cap. 3

2. Operating Systems Concepts, Peterson/Silberschatz, caps. 7 e 8

3. Outros bons livros de sistemas operacionais, nos cap�tulos sobre gerenciamento de mem�ria

1. Introdu��o

O gerenciamento de mem�ria, em conjunto com o gerenciamento de processos, forma o que se pode chamar de cora��o de um sistema operacional. Sua import�ncia reside fundamentalmente no fato do processador executar instru��es trazidas da mem�ria, sobre dados trazidos da mem�ria e guardando resultados na mem�ria. Assim, passa a ser crucial o gerenciamento de como a mem�ria estar� ocupada e como as informa��es nela ser�o reconhecidas pelo processador.

Isso se torna ainda mais cr�tico se considerarmos que a mem�ria n�o � apenas o conjunto de bytes dispon�veis na chamada RAM do computador. Existem, na realidade, cinco diferentes n�veis de mem�ria, diferindo em tamanho, custo e velocidade, que s�o:

1. Registradores internos da CPU

2. Cache

3. Mem�ria principal

4. Mem�ria secund�ria

5. Bibliotecas

O gerenciamento de mem�ria se ocupa da mem�ria principal e das suas intera��es com cache e mem�ria secund�ria. O gerenciamento dos registradores e de boa parte da cache � feito pelo compilador, que ao gerar o execut�vel j� determina como os registradores ser�o ocupados e como a cache pode ser ocupada para acelerar o processamento. J� o gerenciamento das bibliotecas � feito pelo pr�prio usu�rio (ou administrador) do sistema, enquanto boa parte do gerenciamento do disco � feito pelo sistema de arquivos, que foi o tema do cap�tulo anterior.

Desse modo, o gerenciamento de mem�ria se ocupa fundamentalmente do controle de quais dados v�o para a mem�ria, de que forma s�o armazenados nela e como podem ser acessados. Isso envolve atividades de endere�amento, em que se mapeia endere�os de disco para endere�os de mem�ria, de aloca��o, em que se determina quais espa�os ser�o ocupados por quem, e de mem�ria virtual, em que se amplia o conceito de mem�ria principal para um tamanho infinito. Trataremos cada um desses pontos a seguir, fechando o cap�tulo com um estudo de como caracter�sticas de gerenciamento de mem�ria e processos influencia no desempenho de um sistema.

2. Endere�amento

O problema de endere�amento surge quando se percebe que os endere�os ocupados por um programa no disco n�o correspondem aos que ele ocupar� na mem�ria. Isso fica ainda pior quando se examina o c�digo do programa, em que aparecem instru��es do tipo JMP 6000H, em que a possi��o 6000H se refere a um dado deslocamento a partir da origem do programa. Esse endere�o 6000H possivelmente n�o se refere ao endere�o 6000H da mem�ria. Esses diferentes conjuntos de endere�os recebem os nomes de espa�os de endere�os l�gicos, no disco, e endere�os f�sicos, na mem�ria. O problema de endere�amento passa a ser, portanto, determinar uma estrat�gia de convers�o entre endere�os l�gicos e endere�os f�sicos. Essa transforma��o deve ser feita de forma que a execu��o do programa seja efetivada com sucesso ao carregar-se o mesmo na mem�ria. As estrat�gias para efetuar esse mapeamento s�o:

1. Endere�amento Absoluto, em que os endere�os f�sicos s�o absolutamente iguais aos endere�os l�gicos;

2. Reloca��o Est�tica, em que os endere�os l�gicos s�o transformados em endere�os f�sicos, recalculados a partir da diferen�a entre as origens do programa em disco e na mem�ria, no instante do carregamento do programa;

3. Reloca��o din�mica, que faz o c�lculo do endere�o f�sico apenas no momento da execu��o de cada instru��o, a partir do conte�do de um registrador especial (originalmente chamado de fence register);

4. Segmenta��o, que nada mais � do que o uso de reloca��o din�mica aplicado ao conceito de se dividir o programa em partes menores, como c�digo, dados, etc.

3. Aloca��o

Tendo definido o m�todo de convers�o entre endere�os l�gicos e f�sicos, � preciso tratar algo que ocorre momentos antes de se carregar um arquivo ou programa na mem�ria (observem que daqui por diante chamaremos programas e arquivos indistintamente como sendo segmentos). Para que se saiba o endere�o base de um segmento � preciso que se defina em que lugar da mem�ria ele ser� alocado. Essa aloca��o deve ocorrer sob regras bastante bem definidas para que n�o ocorram problemas de interfer�ncia entre os processos. Existem duas estruturas b�sicas de aloca��o de mem�ria, que s�o em espa�os cont�guos e em blocos, descritas a seguir:

1. Espa�os cont�guos
   A aloca��o de mem�ria em espa�os cont�guos � o modelo mais simples de aloca��o, em que para o segmento ir para a mem�ria ele deve caber inteiro em um �nico trecho, com todos os seus bytes alocados de modo cont�nuo. Embora simples esse modelo de aloca��o tr�s diversos inconvenientes, como fragmenta��o externa, necessidade de recompacta��o, mapeamento complexo e dificuldade na escolha do espa�o livre a ser ocupado. Como se pode observar, a aloca��o em espa�os cont�guos tr�s mais problemas do que vantagens.

   Algumas solu��es tentadas para corrigir seus problemas envolvem a aloca��o em segmentos de tamanho fixo e segmentos de tamanho fixo reconfigur�veis (sistemas buddy). Infelizmente, apesar de tais modifica��es terem facilitado o gerenciamento, elas n�o eliminaram a fragmenta��o externa e ainda criaram a fragmenta��o interna.

2. Blocos
   A solu��o para o problema de fragmenta��o veio com a organiza��o de espa�os usada em discos. Ao dividir-se a mem�ria em blocos de tamanho fixo, e permitir-se que um segmento seja quebrado em v�rios blocos, eliminou-se definitivamente a fragmenta��o externa, uma vez que um segmento apenas deixaria de ser carregado para a mem�ria caso esta n�o tivesse blocos livres suficientes para o segmento (esse problema foi resolvido posteriormente com a introdu��o de pagina��o).
   Dentro dessa estrat�gia um segmento � dividido entre v�rias p�ginas, cada uma podendo ser alocada nos espa�os livres de mem�ria dispon�veis no momento da aloca��o, independentemente de serem pr�ximos ou n�o. Nesse esquema a fragmenta��o externa deixa de existir e a interna fica limitada ao tamanho de uma p�gina. O problema nessa estrat�gia � calcular o endere�o f�sico correspondente a um endere�o l�gico qualquer e evitar que se fa�am muitos acessos � mem�ria em busca de um �nico dado. Isso � resolvido por:

   1. C�lculo de endere�o:
      Dado um endere�o l�gico qualquer, seu endere�o f�sico correspondente � determinado dividindo-o pelo tamanho da p�gina, resultando em um n�mero inteiro (o quociente) correspondente ao n�mero da p�gina e outro inteiro (o resto) correspondente ao deslocamento em bytes dentro da p�gina. O problema nesse processo � que para acessar o conte�do do endere�o f�sico correspondente ao dado endere�o l�gico temos que fazer tr�s acessos � mem�ria (um para locallizar a tabela de p�ginas, outro para localizar a p�gina espec�fica e o terceiro para acessar o endere�o desejado), o que tomaria muito tempo.

   2. Otimiza��o de acesso:
      O problema de tr�s acessos pode ser substancialmente reduzido se fizermos uso de mem�rias cache (ou mem�rias associativas), em que parte das informa��es necess�rias estariam dispon�veis em cache.

O uso de mem�ria alocada em blocos melhora significativamente o desempenho da mem�ria. Entretanto ela n�o resolve o problema de que se um segmento ocupa mais p�ginas do que as que est�o livres, ent�o ele n�o pode ser colocado para executar.
Essa restri��o � desnecess�ria, uma vez que se sabe que durante a execu��o de um programa ele n�o precisa acessar todas as suas instru��es e todos os seus dados ao mesmo tempo. Ent�o, se for poss�vel deixar na mem�ria apenas aquilo que est� sendo necess�rio num dado instante, poder�amos usar melhor a mem�ria. Isso � feito atrav�s do mecanismo de mem�ria virtual, examinado a seguir.

4. Mem�ria Virtual

A solu��o para a aloca��o de segmentos maiores do que o espa�o dispon�vel na mem�ria (ou at� mesmo maior que ela toda) veio com um dos conceitos mais importantes de otimiza��o de programas e sistemas, que � o Princ�pio da Localidade. Este princ�pio diz que os endere�os de mem�ria n�o t�m probabilidade igual de acesso, sendo mais prov�vel que ap�s executar uma instru��o da p�gina x, que acesse um dado da p�gina y, � muito mais prov�vel que a pr�xima instru��o tamb�m esteja na p�gina x e tamb�m acesse dados na p�gina y.
Desse modo, se um segmento ocupa muitas p�ginas, seria poss�vel dizer que se estamos acessando um certo n�mero delas num dado instante, ent�o nos manter�amos acessando-as por mais algum tempo, n�o necessitando portanto que as demais p�ginas estivessem na mem�ria.
Esse � o princ�pio de mem�ria virtual. Seu funcionamento ocorre atrav�s de pagina��o por demanda, isto �, uma p�gina vai para a mem�ria apenas no momento em que � requisitada por um processo. O problema passa a ser, ent�o, o que fazer se n�o houver mais p�ginas livres na mem�ria. A solu��o � escolher uma das p�ginas alocadas para sair da mem�ria, liberando portanto seu espa�o. Essa opera��o � conhecida como de swapping, em que se faz o swap-out de uma p�gina (a escolhida para sair) e o swap-in de outra (a demandada).
Antes de discutirmos o funcionamento de mem�ria virtual precisamos definir alguns termos importantes para fazer a an�lise dos v�rios algoritmos de escalonamento. Esses termos s�o:

1. Falta de p�gina, que � o evento que ocorre quando se precisa acessar um endere�o de uma p�gina que n�o est� na mem�ria;

2. Conjunto residente, que � o conjunto das p�ginas que est�o na mem�ria em um dado instante;

3. Tamanho do conjunto residente, � o n�mero de p�ginas ocupadas (pelo sistema ou segmento) num dado momento;

4. Sequ�ncia de refer�ncia, que � uma sequ�ncia de p�ginas que dever�o ser acessadas pelo sistema ao longo do tempo.

Todo o processo de mem�ria virtual passa a ser o gerenciamento de opera��es de swapping, procurando obter o melhor resultado poss�vel a partir do princ�pio da localidade. Existem diversos algoritmos propostos para fazer essa escolha, dentre os quais temos :

1. FIFO, que escolhe para sair a p�gina que entrou na mem�ria h� mais tempo.

2. LRU, que � um algoritmo de pilha em que o crit�rio de escolha da p�gina indica que a p�gina exclu�da ser� aquela que n�o � referenciada h� mais tempo.

3. Optimal, tamb�m � um algoritmo de pilha, mas escolhe para sair a p�gina que levar� mais tempo para ser novamente necess�ria.

4. Clock-FINUFO, que faz uma implementa��o simplificada do LRU, tomando por base valores aproximados dos reais quanto ao �ltimo acesso � p�gina.

5. Segunda chance, que � similar ao FINUFO, por�m a p�gina escolhida para sair teria que ter os bits de acesso e de modifica��o zerados.

Al�m desses algoritmos diversos outros foram propostos. Alguns trabalhando com o conceito de que cada processo teria n�mero fixo de p�ginas, quando a p�gina a ser retirada seria sempre do processo que precisa de uma nova p�gina. Outros com o conceito de tempo fixo entre faltas de p�ginas, em que o n�mero de p�ginas de cada processo � variado para que o intervalo entre duas faltas consecutivas seja mantido constante.

5. Desempenho

O uso de mem�ria virtual permite que mais segmentos sejam carregados na mem�ria por vez, o que permite um aumento no n�mero de processos executando. A partir disso � interessante perceber algumas situa��es que afetam o desempenho do sistema. Antes por�m � preciso definir alguns conceitos b�sicos:

1. N�vel de multiprocessamento - indica o n�mero de processos executando no sistema

2. Falta de p�ginas - indica o n�mero de faltas de p�ginas ocorridas no sistema

3. Ocupa��o da CPU - indica a porcentagem de tempo em que a CPU est� executando processos de usu�rios

Considerando esses aspectos, temos que:

1. Quanto mais processos executando melhor o n�vel de ocupa��o da CPU, uma vez que quando um processo � interrompido para fazer E/S ou por bloqueio, temos v�rios outros para assumir seu lugar na CPU;

2. Quanto mais processos executando mais falhas de p�ginas temos, uma vez que cada processo passa a ocupar menos p�ginas e, com isso, passa a ser mais prov�vel que uma p�gina requisitada n�o esteja na mem�ria;

3. Um n�mero elevado de processos executando acaba tendo um p�ssimo n�vel de ocupa��o da CPU, uma vez que com o crescimento do n�mero de processos teri�mos uma maior ocupa��o, mas com mais processos � capaz de todos terem t�o poucas p�ginas que ficam o tempo todo causando falta de p�ginas e, com isso, n�o podem ocupar a CPU. Essa situa��o recebe o nome de thrashing.

Assim, temos algumas diretrizes para avaliar o desempenho de um sistema. Basta verificar taxas de ocupa��o da CPU, n�mero de faltas de p�ginas (ou por quanto tempo o sistema fica ocupado realizando pagina��o), taxa de ocupa��o dos dispositivos de E/S, etc.
Com essas medidas em m�os um analista pode sugerir mudan�as no sistema, como aumento de mem�ria, troca de dispositivos de E/S, troca de mecanismos de caching (preenchimento da cache com dados), entre outras.
O importante aqui � lembrar sempre que uma an�lise cuidadosa do sistema, levando em considera��o todas as vari�veis poss�veis e as diretrizes anteriormente indicadas, � uma tarefa que bem executada resulta em ganhos consider�veis ao sistema e ao seu financiador, devendo portanto ser uma tarefa bastante bem remunerada.

6. Vis�o global do sistema

Agora que terminamos a an�lise individual de cada um dos mecanismos do SO podemos ter fazer uma avalia��o de seu funcionamento global. Tomaremos como exemplo a ocorr�ncia de uma falta de p�gina e das a��es decorrentes dela.

Na ocorr�ncia de uma falta de p�gina, identificada pelo gerenciamento de mem�ria, � necess�rio:

1. ativar a��es do gerenciamento de processos, para bloqueio do processo que gerou a falta;

2. ativar a��es do gerenciamento de mem�ria para defini��o de qual p�gina sair� da mem�ria, j� marcando-a como fora da mem�ria para evitar acessos incorretos;

3. ativar a��es do sistema de arquivos para a localiza��o das p�ginas envolvidas no swapping;

4. ativar a��es do gerenciamento de disco para realizar fisicamente o swapping;

5. ativar, quando necess�rio, os mesmos mecanismos quando da conclus�o das a��es disparadas.

Disso percebe-se que existe muita intera��o entre os v�rios mecanismos do SO, o que apenas � poss�vel de ser feito eficientemente se forem implementados modularmente, na forma de {\em threads}, por exemplo.

Quais os benefícios oferecidos pela técnica de memória virtual?

O que é e como funciona o mapeamento em relação a memória virtual?

Como mapear endereços virtuais para endereços físicos?

Quanto ao Page Fault Assinale a alternativa correta?