Gerenciamento de Memória no Linux

INSTITUTO TECNOLÓGICO DE AERONÁUTICA
Alunos: Igor Oliveira Aquino e Luty Rodrigues Ribeiro
Professor: Yano
Curso: 2º ano de Computação

Memória: Descrição e Principais Características

O espaço de memória virtual no Linux é dividido em áreas homogêneas, ou seja, cada área consiste em um conjunto de páginas com as mesmas propriedades de proteção e paginação. Podem haver buracos no espaço de endereços virtuais entre essas áreas, mas qualquer referência à "memória desse buraco" resultará numa falha de página. O tamanho de página é fixo e vale, por exemplo, 4KB no Pentium.

Cada uma dessas áreas é descrita no kernel por uma entrada chamada vm_area_struct. Todas as vm_area_struct para os processos são ligadas juntas numa lista ordenada de modo que cada página possa ser encontrada. A vm_area_struct guarda as propriedades de cada área, que incluem informações sobre os modos de proteção dela (somente leitura, leitura e escrita) e a sua direção de crescimento (para cima para segmentos de dados e para baixo para pilhas), por exemplo. A vm_area_struct também guarda informações sobre se a área é privada àquele processo ou se é compartilhada por um conjunto de processos.

A paginação do Linux não é pura. Ela segue o padrão de paginação em três níveis, que são: Page Directory, Page Middle Directory e Page Table. Cada endereço virtual é quebrado em até quatro campos, como mostrado na Figura 1. O campo directory field é usado como índice para o diretório global, que existe para cada processo. O valor achado nessa posição é um ponteiro para a page middle table, que é novamente indexada e contém um ponteiro que aponta para o endereço virtual de memória.

paginacao.bmp

Figura 1

TLB (Translation Lookaside Buffers) no Linux e Tabelas de Páginas

O Linux utiliza um esquema no qual a CPU faz acessos frequentes à memória virtual, a qual utiliza endereços lógicos no lugar dos próprios endereços físicos. Assim é necessário que haja uma “tradução” desses endereços lógicos para os endereços físicos da memória principal. Essa tradução é realizada pela tabela de página, armazenada também na memória virtual. No Linux, essa tabela de página é implementada em três níveis, de modo que qualquer acesso a um endereço virtual precisaria de quatro acessos à memória física (três acessos a cada nível da tabela de página, para obter o endereço físico correspondente, e mais um acesso para obter o conteúdo). Para evitar isto, e assim melhorar o desempenho do sistema, existe também a TLB (Translation Lookaside Buffer).

A idéia principal da TLB é armazenar traduções recentemente realizadas, pois elas provavelmente serão repetidas, e com isso, não seria necessário fazer a tradução pela tabela de página.

Então, quando a CPU acessa um endereço de memória virtual, procura-se pela tradução adequada na seguinte ordem:

  • Procuramos a tradução associada àquele endereço de memória virtual na TLB. Se o endereço é encontrado, a tradução é realizada;
  • Se o endereço de memória virtual não está na CPU, então a tradução é feita através da tabela de página como comentado anteriormente.

A grande vantagem da TLB é que, por ser uma memória cache associativa, o acesso a ela é mais rápido do que um acesso comum à memória física, o que torna a maioria das traduções bem mais rápida e faz com que compense utilizar o sistema de memória virtual.

Um fato importante é que a TLB deve sempre se manter atualizada com relação ao conteúdo da memória principal, assim, como a TLB, em geral, possui tamanho menor que a memória principal, será necessário, de tempos em tempos, substituir alguma tradução armazenada por outra mais recente. A política de substituição adotada é uma aproximação do algoritmo LRU (least recently used).

Algoritmos para Remoção de Páginas

Quando ocorrem interrupções por falta de página ou quando não há espaço na memória física, uma página precisa ser removida. Escolher bem qual página será retirada e descartada pode trazer resultado muito bons de desempenho. Para isso, existem algoritmos que sugerem meios eficientes de realizar essa escolha. Alguns deles são:

  • Algoritmo de Substituição de Página Ótimo

Esse algoritmo é impossível de ser implementado. Ele é utilizado apenas para comparação com outros algoritmos factíveis, para avaliar a perfomance deles. A idéia desse algoritmo é que cada página é rotulada com o núemro de instruções que serão executadas antes daquela página ser chamada. Dessa forma, na hora de excluir uma página, você deve excluir aquela de maior índice. Porém, não há como saber na prática quantas instruções serão realizadas antes deuma página ser chamada.

  • Algoritmo de Substituição de Página Não-Recentemente Utilizada

O NRU (do inglês, Not Recently Used Page) usa dois bits de status, R e M, que são assiciados a cada página. R é setada sempre que uma página é referenciada e M é setado quando a página é modificada. Quando o sistema precisa remover uma página, ele percorre todas as páginas presentes e as classifica em quatro classes:

  • classe 0: não-referenciada, não-modificada;
  • classe 1: não-referenciada, modificada;
  • classe 2: referenciada, não-modificada;
  • classe 3: referenciada, modificada;

Dessa forma, o algoritmo remove uma página em execução da classe mais baixa.

O NRU é bom pois é de fácil entendimento e implementação, porém seu desempenho não é ótimo (apesar de ser suficiente na maioria dos casos).

  • Algoritmo de Substituição de Página Primeira a Entrar, Primeira a Sair

O FIFO (do inglês, First-In, First-Out) mantém uma lista que estão atualmente na memória, onde a página no topo da lista é a mais antiga (a que entrou há mais tempo na memória) e a no final da lista é a mais nova (que está há menos tempo na memória). Dessa forma, quando é necessária a remoção de uma página, a página removida é aquela que se encontra no topo da lista.

A desvantagem desse método é que ele pode retirar da memória uma página que é utilizada frequentemente mas entrou na memória há bastante tempo. Dessa forma, o FIFO geralmente é utilizado não na sua forma pura, mas com algumas adaptações.

  • Algoritmo de Substituição de Página de Segunda Chance

Esse algoritmo é uma modificação simples no FIFO que evita a exclusão de páginas utilizadas frequentemente. Para isso, o bit R também é inspecionado antes da página ser removida. Ou seja, ao tentar remover a página mais antiga (do topo da fila), verifica-se o seu bit R. Caso ele seja zero, a página é removida. Caso contrário, a página é colocada no final da fila (como se tivesse entrado agora na memória) e seu bit R é limpo. Daí o algoritmo procede verificando a próxima página que está no topo agora.

  • Algoritmo de substituição de Página do Relógio

Otimiza uma falha de performance do algoritmo de Segunda Chance, que mantém uma lista linear das páginas e, constantemente, está movendo páginas pela lista. O algoritmo do Relógio mantém uma lista circular das páginas e, quando é necessária a remoção de alguma delas, a página indicada pelo ponteiro tem seu bit R inspecionado. A lógica da inspeção e exclusão é a mesma do algoritmo anterior. Porém, ao invés da página ser mudada de posição caso seu bit R seja 1, apenas o ponteiro é que muda de lugar e passa a apontar para a página vizinha.

  • Algoritmo de Substituição de Página Menos Recentement Utilizada

O LRU (do inglês, Least Recently Used) remove da memória a página que não foi utilizada por mais tempo. Isso baseia-se na suposição de que páginas que não foram recentemente utilizadas também não o serão nas próximas instruções, enquanto páginas bastante utilizadas agora tendem a ser bastante utilizadas na instruções seguintes também.

Interfaces para o Gerenciamento de Memória

  • Criação de processos

Os processos são criados, geralmente, por uma chamada fork(), e, logo que criados, recebem um novo espaço de endereços, ou seja, passam a ocupar alguns page frames, determinando uma “região de endereços” na memória virtual daquele processo.

  • Troca de Contexto de processos

A troca de contexto de processos é feita armazenando a estrutura que guarda o status do processo, e, em seguida, o novo processo passa a ser o processo “atual”.

  • Page-fault

Quando ocorre a tentativa de acesso a uma página da memória virtual que perdeu seu page frame da memória física, ocorre o page-fault, que é nada mais do que uma interrupção por falta de página. Esta interrupção se encarrega de recolocar o conteúdo referenciado na memória virtual na memória física, realizando uma busca no disco.

  • Remoção de processo

Quando o processo é encerrado (por uma chamada exit() por exemplo), é feita uma chamada de sistema que apaga os mapeamentos de memória relativos àquele processo e atualiza as tabelas de página.

Compartilhamento de Memória

O compartilhamento de dados pode ser feito de duas maneiras: realizando a comunicação direta interprocessos ou fazendo dois processos apontar para o mesmo lugar na memório RAM.

  • Comunicação Interprocessos

Processos se comunicam entre si e com o kernel para realizar suas tarefas. O Linux dá suporte a mecanismos IPC (InterProcess Comunication), como por exemplo, os pipes.

  • Shared Virtual Memory: processos apontando para o mesmo local na memoria

Sabemos que todos os acessos à memória são feitos via tabela de página e cada processo tem sua própria tabela separada. Portanto, para dois processos compartilharem uma página física da memória, essa página deve estar na tabela de páginas de ambos os processos. A figura abaixo mostra dois processos que compatilham a moldura de página de número 4. Para o processo X esta é a página virtual de número quatro, enquanto que para o processo Y esta é a página virtual de número 6. Dessa forma, pode-se percerber que a moldura de página compartilhada não tem que existir no mesmo lugar da memória virtual para todos os processos que a compartilham.

shared_memory.gif

Mapeamento de arquivos na memória virtual

Ao carregar um arquivo, em geral, várias páginas da memória virtual são associadas ao arquivo, de modo que o arquivo fica distribuído em várias páginas. Essas páginas na memória virtual, obviamente, estão associadas a page frames na memória física, como vimos anteriormente. As estruturas responsáveis por esse mapeamento (memory mapping data structures) são representadas pelos seguintes campos:

  • inode: objeto do arquivo;
  • adress_space: objeto do arquivo;
  • vm_area_struct: descritor de cada mapeamento do arquivo;
  • file: objeto de cada mapeamento do arquivo;
  • page: descritor para cada frame escolhido da região de memória.

Áreas de Memória Fixas

Segurança

Os processos em Linux podem operar em dois níveis de privilégio: modo kernel e modo usuário.

Um processo de usuário em Linux (ou seja, em modo usuário) não pode invadir a área de outros processos, muito menos áreas do sistema operacional. Quando um processo tenta acessar uma área que não lhe foi designada, o sistema apresenta o erro denominado segmentation fault (falha de segmentação – erro correspondente a tentativa de acesso a uma área inválida). Para que um processo em modo usuário possa obter dados do kernel, deve realizar um system call (chamada de sistema). Essa chamada é basicamente uma interrupção, que, como esperado, interrompe o processo que realizou a chamada, armazena o seu estado de execução, e, em seguida, inicia a execução do código de maior prioridade (em modo kernel) Finalizada a rotina da interrupção, o controle da CPU volta para o processo que requisitou a chamada. Entretanto, o acesso no sentido inverso não possui restrições, ou seja, um processo do kernel (ou seja, em modo kernel) pode acessar dados de processos do usuário.

Área de Swap

Quando a memória física começa a ficar escassa, o sistema de gerenciamento de memória do linux tenta liberar páginas físicas para suprir as necessidades. Isso é uma tarefa dedicada ao kernel swap daemon.

O kernel swap daemon é um tipo especial de processo, uma thread do kernel, que é inicializada quando o sistema é ligado. As threads do kernel não usam memória virtual, elas rodam no espaço de endereços físicos. O kernel swap daemon, além de fazer a troca de páginas entre a memória física e virtual, também é responsável por controlar de forma eficiente o valor "saudável" de ocupação da memória para o sistema, de modo que este não venha a ser danificado ou travado.

O kernel swap daemon funciona com um timer. Sempre que a contagem desse timer expira, o kernel swap daemon verifica o número de páginas livres no sistema e se este está muito lento. Ele possui dois valores de referência, free_pages_high e free_pages_low, que são setadas na inicialização do sistema e asseguram os limites de espaço livre da memória física.

Se o número de páginas livres do sistema for menos que free_pages_high ou, pior ainda, for menor que free_pages_low, o kernel swap daemon tem três maneira de solucionar esse problema:

  • Reduzir o tamanho do buffer e do cache de páginas;
  • Fazer o swapping das páginas de memória compartilhadas;
  • Fazer o swapping e descartar páginas.

Se o número de páginas livres for menor do que free_pages_low, o kernel swap daemon libera seis páginas antes da sua próxima execução. Caso contrário, ele libera três páginas. Bons cadidatos a sofrerem o swapping são processo que possuem uma ou mais páginas que podem ser tiradas da memória. Páginas travadas na memória não podem sofrer swapping.

Quanto ao tamanho da área de swap, é possível até que o Linux rode sem área de swap, apesar de isso não ser recomendado. Não existe uma "regra" formal a respeito de qual o melhor tamanho para essa área, mas uma referência que pode ajudar na escolha é a seguinte:

  1. Para desktops, o tamanho da área de swap sugerida é o dobro da memória do sistema;
  2. Para servidores, ter menos espaço de swap (metade da memória do sistema, por exemplo) é melhor, pois, quando necessário, ele pode ter a flexibilidade de alocar mais espaço, sempre monitorando a quantidade total;
  3. Para computadores mais antigos (com 256MB de RAM), use o quanto você puder de área de swap.

Testando os Limites do Sistema

Número máximo de processos
Para testar o número limite de processos, a idéia é basicamente fazer vários fork()’s seguidos.

O comando ulimit -a nos mostra uma quantidade ilimitada de processos. Entretanto ao executar o código nprocessos.c, constatamos que, com 2048 processos, o computador já ficava praticamente inutilizável (travado). O código utilizado para teste foi:

#include <stdio.h>
 
int main() {
    int i ;
 
    for(i=0; i<11; i++) {
        fork();
    }
    while(1);
    return 0;
}

Tamanho máximo de um processo
Para o tamanho de processo, usar o comando ulimit –a e verificar o tamanho máximo.

Com o comando ulimit -a vemos então o campo "max locked memory", que seria o quanto um processo pode reservar de memória para si. Obtivemos 64kB para o tamanho de um processo.

Tamanho máximo da área de heap
Para a área de heap, a idéia é fazer vários malloc()’s seguidos, sem liberar os ponteiros alocados.

Foi criado um programa para alocar memória um grande número de vezes. Depois de alguns testes, descobrimos que a área de heap tem entre 615 milhões e 625 milhões de bytes, o que nos dá por volta de 590MB. O código de teste usado foi:

#include <stdio.h>
#include <stdlib.h>
 
int main() {
    int i;    
    int *p;
 
    printf("Tamanho de um int: %d\n", sizeof(int));
    for(i=0; i<153750000; i++) {
        p = (int *)malloc(sizeof(int));    
        //printf("%d\n", p);
    }
    printf("\nFim de alocação\n");
    while(1);
}

Na execução, a mensagem final é "Fim de Alocação" se todas as alocações puderam ser efetuadas corretamente, ou "Finalizado", se a alocação ultrapassou o limite máximo.

Limite para a área de pilha
Para área de pilha, a idéia é utilizar uma função recursiva quase sem corpo, e utilizar uma variável global para contar o número de chamadas. O código utilizado no teste foi o seguinte:

#include <stdio.h>
 
int contador = 0;
 
void funcao_recursiva(void){
    printf("Chamada1 %d\n",++contador);
    funcao_recursiva();
}
 
int main() {
    funcao_recursiva();
}

Quando chegarmos ao limite do tamanho da pilha, o programa retorna mensagem de "Falha de segmentação". Número de chamadas: 523824 chamadas (por volta de 2^19 chamadas). O comando ulimit -a nos mostra que a área de pilha possui 8MB (2^23 bytes). Assim, temos que cada chamada de função empilhada tem por volta de 16 bytes.

Como comentado no tópico sobre área de swap, não existe um tamanho máximo para ela, mas ela possue um tamanho. Portanto, ela pode ser esgotada.

Referências

ANONIMO. Linux Page Tables explained. Linux Device Drivers, Internet, n., 22 abr. 2000. Disponível em: <http://www.theilya.com/info/linux_page_tables.shtml>.

ANONIMO. Paging and Swaping. Linux Knowledge Base And Tutorial, Internet, n., 22 abr. 2000. Disponível em: <http://www.linux-tutorial.info/modules.php?name=MContent&pageid=89>.

ANONIMO. Virtual Memory. Linux Knowledge Base And Tutorial, Internet, n. , 22 abr. 2000. Disponível em: <http://www.linux-tutorial.info/modules.php?name=MContent&pageid=261>.

ANONIMO. Interprocess Communication. Linux Knowledge Base And Tutorial, Internet, n. , 22 abr. 2000. Disponível em: <http://www.linux-tutorial.info/modules.php?name=MContent&pageid=288>.

ANONIMO. Swapping Out System Vs Shared Memory Pages. Linux Knowledge Base And Tutorial, Internet, n. , 22 abr. 2000. Disponível em: <http://www.linux-tutorial.info/modules.php?name=MContent&pageid=312>.

ANONIMO. All about Linux swap space. All About Linux Swap Space, Internet, n. , 07 set. 2007. Disponível em: <http://www.linux.com/news/software/applications/8208-all-about-linux-swap-space>.

ANONIMO. Swapping Out and Discarding Pages. Linux Knowledge Base And Tutorial, Internet, n. , 22 abr. 2000. Disponível em: <http://www.linux-tutorial.info/modules.php?name=MContent&pageid=311>.

TANENBAUM, Andrew S.. Memory Management. Modern Operation Systems, Internet, n. , p.672-757

TANENBAUM, Andrew S.. Memory Management. Modern Operation Systems, Internet, n. , p.190-262

SILVA, Airon Fonteles da. Memory Addressing. Laboratório de Redes de Alta Velocidade - Ufrj, Rio de Janeiro, n. , p.1-1, 29 nov. 2003. Disponível em: <http://www.ravel.ufrj.br/arquivosPublicacoes/MemoryAddressing.pdf>. Acesso em: 07 jul. 2009.

MOSBERGER, David; ERANIAN, Stephane. Virtual Memory in the IA-64 Linux Kernel. Informit, Indiana, n. , p.1-1, 29 nov. 2003. Disponível em: <http://www.informit.com/articles/article.aspx?p=29961&seqNum=4>. Acesso em: 07 jul. 2009.

VITLIC. Principles of Virtual Memory. Slideshare, Internet, n. , p.1-1, 14 set. 2006. Disponível em: <http://www.slideshare.net/vitlic/linux-memory>. Acesso em: 07 jul. 2009.

ANÔNIMO. Paging and Swapping. Linux Knowledge Base And Tutorial,, Internet, n. , p.1-1, 21 mar. 2007. Disponível em: <http://www.slideshare.net/vitlic/linux-memory>. Acesso em: 07 jul. 2009.

GORMAN, Mel. Understanding The Linux Virtual Memory Manager. Skynet, Seattle, n. , p.1-1, 15 fev. 2004. Disponível em: <http://www.ravel.ufrj.br/arquivosPublicacoes/MemoryAddressing.pdf>. Acesso em: 07 jul. 2009.

SEGMENTATION Fault Wikipedia, Internet, n. , p.1-1, 19 ago. 2008. Disponível em: <http://en.wikipedia.org/wiki/Segmentation_fault>. Acesso em: 07 jul. 2009.

KELLER, Fabian. Memory Mapping of Files. Wikipedia, Internet, n. , p.1-1, 20 jan. 04. Disponível em: <http://i30www.ira.uka.de/teaching/coursedocuments/88/8.2_Keller_Memory-Mapping-of-Files.pdf>. Acesso em: 07 jul. 2009.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License