Gerenciamento de Memória no Linux

Alocação de memória

Quando executa-se uma aplicação, o kernel do sistema operacional cria uma imagem desta aplicação na memória e executa esta aplicação à partir de lá. Ao surgir a necessidade de se executar 2 processos simultaneamente, precisa-se certificar-se de que é possível referenciar de maneira unívoca cada processo e de que há espaço suficiente para esse processo na memoria.

Quanto ao problema de referenciação unívoca, um dos métodos aplicados é o de segmentação. A segmentação consiste em dividir a memoria virtual em pedaços (segmentos) e apontar um determinado segmento para uma aplicação. Isto define de maneira única a aplicação na memória virtual e vice-versa e, desta forma, pode-se executar simultaneamente várias aplicações compartilhando de maneira mais eficiente a memória sem o risco de alocarmos de maneira incorreta a aplicação.

Em linux, no entanto, a segmentação é um pouco mais complicada. Linux utiliza apenas 4 segmentos para todos os seus processos. 2 segmentos para o KERNEL SPACE de [0xC000 0000] (3GB) até [0xFFFFFFFF] (4GB) e 2 para o USE SPACE de [0] até [0xBFFF FFFF] (3GB). São eles:

  • Kernel Code
  • Kernel Data / Stack
  • User Code
  • User Data / Stack

O problema com a segmentação é que o processo de alocação de memória não é dinâmico no sentido de que os segmentos são áreas contínuas de memória e não podem ser partidas. Isto significa que para se carregar um novo processo temos que garantir que existe um segmento disponível e que o tamanho deste segmento comporte o dado processo. Caso contrário, segmentation fault, ou seja, não existe um segmento disponível para alocar aquele processo.

Outra possibilidade de resolução para o problema de referenciação unívoca é a paginação. Esta consiste em dividir a memória em vários pedaços de tamanho fixo de forma que um dado processo possa utilizar várias páginas para a sua execução. O interessante desta forma de alocação é que isto permite um alocamento dinâmico pois a memória é disponibilizada à partir do número de páginas livres evitando desta forma o problema da segmentação. O processo, neste caso pode "procurar" por páginas livres para sua execução. O problema aqui é que se um processo é pequeno demais para ocupar uma página inteira, o espaço que sobra é desperdiçado.

A solução adotada para a alocação de memória em Linux é juntar ambos os métodos, a segmentação e a paginação de modo a minimizar o desperdício de memória e resolver ambos os problemas pois cada segmento é dividido em várias páginas, evitando assim o problema da segmentação. O problema da paginação é resolvido fazendo páginas pequenas (4096 bytes, por exemplo) minimizando o desperdício e gerenciando as páginas de maneira hierárquica (3 níveis de paginação), de forma a distribuir de maneira mais eficiente as páginas.

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

A TLB (Translation Address Table) é fundamental no acesso à memória. Basicamente, os endereços de toda a memória RAM disponível são divididos em páginas de memória. Cada página de memória tem uma tabela de endereços, com os dados armazenados e sua localização.

Esta tabela precisa ser consultada antes de cada acesso à memória. O grande problema é que em condições normais, a tabela fica armazenada na própria memória RAM, o que faz com que o processador precise fazer um duplo acesso à memória, o primeiro para ler a tabela de endereços e o segundo para recuperar os dados propriamente ditos.

A TLB é uma espécie de cache, incluído no processador, que permite que ele mantenha as tabelas de endereços de algumas páginas pré-carregados, o que melhora consideravelmente a velocidade de acesso à memória, quando os dados necessários não são encontrados no cache L1 e L2. Quanto maior é a TLB, mais endereços podem ser armazenados e maior é o ganho.

Existem diversos tipos de TLB's. O Linux suporta os seguintes tipos:

R2000-style TLB
Consiste em uma TLB de 64 entradas. Cada entrada é mapeada para uma única página, cujo tamanho está fixado em 4KB.
R4000-style TLB
O numero de entradas nesse tipo de TLB é variável na faixa de 32 a 64, porém o mais comum é o valor de 48 entradas. Cada entrada na TLB pode estar associada a uma página com um tamanho especifico para aquela entrada. Normalmente esses tamanhos variam de 4KB a 16MB.

Ambos os tipos de TLB são manipuladas através de 4 instruções:

TLBWI
TLB Write Indexed;
TLBWR
TLB Write Random;
TLBP
TLB Probe; e
TLBR
TLB Read.

Algoritmos e estrutura para remoção de dados

No Linux, o algoritmo utilizado para atender às solicitações de memória feitas pelos processos (aplicações) chama-se Page Frame Reclaiming Algorithm - PFRA. Esse algoritmo foi desenhado para permitir a alocação de molduras de página em várias situações: muita memória disponível, pouca memória disponível e situação crítica (quando não é possível alocar molduras para um determinado processo). Como o jqueiroz já citou, esse algorimo baseia-se numa método chamado LRU (least recently used - menos recentemente usado).

Simplificadamente, método LRU é implementado usando-se duas listas encadeadas: (i) inactive_list e (ii) active_list. Quando uma página, ao ser varrida pelo gerenciador de memória (mm), é identificada como inativa, uma marca (flag) é colocada na respectiva tabela de páginas; se receber duas marcas, irá para a lista inactive_list. Quando o gerenciador de memória (normalmente um serviço do kernel denominado kswapd) necessita de memória, irá escolher as molduras que estão no fim da lista para transferir seu conteúdo para o espaço de troca (swap space).

O algoritmo PFRA leva em consideração vários fatores para paginação, tais como se a página está compartilhada entre vários processos, se pertence ao buffer ou à cache, se é reservada, etc.

Interfaces de gerenciamento de memoria

Criação de processos

Para criação de processos é usada a chamada fork(). Este método cria um processo filho que difere do processo pai apenas pelo PID, file locks e pending signals. No linux, fork() é implementado usando copy-on-write pages. Em caso de sucesso da chamada fork(), o PID do processo filho é retornado na thread de execução do processo pai e zero é retornado na do filho.

Troca de contexto de processos

A cada tempo um processo é removido de acesso ao processador, deve ser armazenada informação suficiente sobre seu estado operacional atual tal que, quando é programado para rodar no processador novamente, pode retomar sua operação de uma posição idêntica. Este dados de estado operacional é conhecido como seu contexto e o ato de remover a thread do processo de execução do processador (e substituindo isto com outro) é conhecido como troca de processo ou troca de contexto.

O contexto de um processo inclui seu espaço de endereço, espaço de pilha, espaço de endereço virtual, registro de imagem fixa (por exemplo Contador de Programa (o PC), Ponteiro de Pilha (SP), Registro de Instrução (IR), Palavra de Estado de Programa (PSW) e outros registradores gerais do processador), atualizando perfil ou informação de contabilidade, fazendo uma imagem instantânea associada as estruturas de dados do Kernel e atualizando o estado atual do processo (esperando, pronto, etc).

Quando uma interrupção de processo é feita, o escalonador salva o task_struct do processo na situação atual e substitui o ponteiro de tarefas atual por um ponteiro para o task_struct do novo processo definido para execução, restabelecendo seu acesso à memória e registrador de contexto.

Page-fault

Para traduzir um endereco virtual para um físico, o processador analisa a entrada na tabela de páginas correspondente ao endereco virtual fornecido. Caso este endereco seja válido (estaja mapeado na memoria principal), é retornado da tabela o page frame + offset correspondente a esse endereco virtual. Caso nao seja válido, o processador passa o controle para o sistema operacional para que este realize uma substituicao de paginas para resolver o conflito.

Remocao de processo

Um processo pode ser encerrado das seguintes formas:

  • Normal (voluntario).
  • Por erro (voluntario).
  • Por Fatal error (involuntario).
  • Por outro processo (involuntario).

Em geral, quando um processo é removido, ele realiza a chamada exit. Em caso de ser passado o argumento 0 para a chamada, a finalizacao é normal. Caso contrario, houve alguma situacao anômala e foi disparado um sinal de erro para o sistema. Ao ser encerrado, a parte da memoria que estava ocupada por este processo é liberada.

fonte: Tanenbaum

Compartilhamento de memoria

Comunicação Inter-Processos (IPC) pode ser realizada atraves de chamadas ao proprio kernel do sistema operacional, atraveś de recursos como por exemplo os pipes.

Porém, fazer uso de memoria compartilhada é a forma mais rápida de IPC.Neste tipo, existe uma área reservada de memória na qual os processos trocam informações (mais de um processo tem acesso à mesma posição de memória). Todos processos enxergam as alterações realizadas na área compartilhada. É necessário garantir a sincronização no acesso à região de memória compartilhada (utilizar semáforos).

As regiões de memória compartilhada são armazenadas pelo kernel no Region Table. O kernel mantém um vetor (Shared Memory Table) em que cada entrada possui informação referente ao nome, permissões e tamanho da região correspondente, assim como o apontador para a Region Table.

Mapeamento de arquivos

O sistema de arquivos no Linux é baseado no sistema de arquivos do Unix, onde é utilizada a estrutura i-nodes para o mapeamento de arquivos que relaciona os atributos e endereços em disco dos blocos de arquivos.

Quando o sistema lê um arquivo, como por exemplo através de uma chama típica a um comando read(fd, buffer, nbytes). Para iniciar a leitura o sistema operacional possui somente os três parâmetros passados e as tabelas internas relacionadas ao usuário. Nas tebelas internas existe um vetor descritor de arquivos, que é indexado pelos descritores de arquivo e contém uma entrada para cada arquivo aberto. Associado à cada descritor de arquivo existe uma posição do arquivo que diz onde o byte da próxima leitura pode começar. Para que isso seja feito é introduzida uma nova tabela, a tabela de descrição de arquivo. Esse sistema é mostrado na figura abaixo:

file2.bmp

Limites do sistema

Numero de processos

No que diz respeito ao numero maximo de processos que um sistema linux pode suportar, pode-se ressaltar o seguinte: numa arquitetura i386, o tamanho maximo da GDT (Global Descriptor Table) é 8192. Ao iniciar o sistema, 12 entradas sao utilizadas. Como cada processo necessita de 2 dessas entradas, tem-se que é possível existir 4090 processos simultaneamente.

Para testar a capacidade de criacao de processos na maquina, executou-se o seguinte codigo em c:

#include <stdio.h>
#include <stdlib.h>
 
#define MAX_PROCESS 1000
 
int main(int argc, char** argv) {
 
    int i, new_pid;
 
    for( i = 1;  i <= MAX_PROCESS; i++ ) {
 
    new_pid = fork();
 
        if( new_pid != 0 ) {
            break;
 
            } else {
            printf("Processo FILHO [%d] gerado. (%d) Processos simultaneos\n\n", getpid(), i);
            }
 
    }
 
    // esperando eternamente
    for(;;);
 
    return (EXIT_SUCCESS);
}

Observou-se que gerando-se 1000 processos simultaneos (mais os 157 que havia no momento da execucao) a maquina ficou demasiadamente lenta, sendo dificil a simples tarefa de finalizar a execucao dos processos.

Tamanho maximo de processo

Antes de apresentar os testes, é importante definir a diferenca entre pilha e heap:

*Pilha ⇒ possui diversos usos durante a execução do programa. Contém o endereço de retorno
das chamadas de função, os argumentos para funções e variáveis locais.

*Heap⇒ região de memória livre que seu programa pode usar, via funções de alocação
dinâmica de “C”, em aplicações como listas encadeadas e árvores. Embora o tamanho do heap seja
desconhecido, ele geralmente contém uma quantidade razoavelmente grande de memória livre.

Inicialmente, o seguinte codigo fornece o limite de tamanho para processo e para pilha:

#include <sys/resource.h>
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
 
int main (int argc, char *argv[])
{
  struct rlimit limit;
 
  if (getrlimit(RLIMIT_AS, &limit) != 0) {
    printf("getrlimit() failed with errno=%d\n", errno);
    exit(1);
  }
 
  printf("Limite default para tamanho de processo:\n");
  printf("O soft limit eh %lu MB\n", limit.rlim_cur/(1024*1024));
  printf("O hard limit eh %lu MB\n", limit.rlim_max/(1024*1024));
 
  if (getrlimit(RLIMIT_STACK, &limit) != 0) {
    printf("getrlimit() failed with errno=%d\n", errno);
    exit(1);
  }
 
  printf("\nLimite default para tamanho da area de pilha de um processo:\n");
  printf("O soft limit eh %lu MB\n", limit.rlim_cur/(1024*1024));
  printf("O hard limit eh %lu MB\n", limit.rlim_max/(1024*1024));
 
  exit(0);
}

Saida:

Limite default para tamanho de processo:
O soft limit eh 4095 MB
O hard limit eh 4095 MB

Limite default para tamanho da area de pilha de um processo:
O soft limit eh 8 MB
O hard limit eh 4095 MB

Tamanho maximo de Pilha

Para testar na pratica o tamanho maximo da pilha, usou-se o seguinte codigo:

#include <stdio.h>
#include <stdlib.h>
 
int calls = 0;
 
void recursive_function() {
    calls = calls + 1;
    printf("Chamadas: %d\n", calls);
    recursive_function();
 
}
 
int main (int argc, char *argv[])
{
    recursive_function();
 
  exit(0);
}

Saida:


Chamadas: 523770
Chamadas: 523771
Chamadas: 523772
Falha de segmentação

Assim, como cada chamada a essa funcao usa 16 bytes da pilha, temos que 523.772 chamadas usa 7,98 MB, confirmando o valor fornecido no teste do RLIMIT.

Tamanho maximo de Heap:

Para testar o tamanho maximo da area de Heap, foi usado o seguinte codigo:

#include <stdio.h>
#include <stdlib.h>
 
int main (int argc, char *argv[])
{
    double calls = 0;
 
    int *p;
 
    for(;;) {
        p = (int*) malloc( 1024*1024 );
        calls += 1;
        printf("Tamanho armazenado em Heap: %lf MB\n", calls);
    }
 
  exit(0);
}

Assim esse codigo, teoricamente, alocaria 1 MB a cada loop. Porem dessa forma, ele nunca parava a execucao. Portanto nao conseguimos achar uma forma experimental de descobrir o tamanho maximo da area de heap.

Tamanho maximo da area de swap

Como a area de swap pode ser extendida de acordo com a particao que é destinada a esta, o seu limite está vinculado ao limite do HD.

Referências

TANENBAUM, Andrew S.. Memory Management. Modern Operation Systems, Internet, n. , p.672-757. Pearson Prentice Hall, 2ª Edicção, 2005

SILVA,Geyson Rogério. Linux e alocação de memória. 30 mar. 2005 Disponível em: <http://www.slackware-brasil.com.br/web_site/artigos/artigo_completo.php?aid=3533>. Acessado em: 11/07/2009.

ANONIMO, Como funciona o gerenciamento de memória no Linux. 08 de maio de 2007. Disponível em <http://www.guiadohardware.net/comunidade/funciona-gerenciamento/765467/>. Acessado em: 11/07/2009.

ANONIMO. TBL. 10 de dezembro de 2007. Disponível em : <http://www.linux-mips.org/wiki/TLB>. Acessado em: 11/07/2009.

OLIVEIRA, Ivo Sócrates. Sistemas Operacionais, Instituto Federal de Ciência e Tecnologia, 2009. Diposnível em: <http://www.google.com.br/url?sa=t&source=web&ct=res&cd=6&url=http%3A%2F%2Fparaiso.etfto.gov.br%2Fdocente%2Fadmin%2Fupload%2Fdocs_upload%2Fmaterial_e49be5c7a7.ppt&ei=o6RWSqauN5aMtgfRvfG9Ag&usg=AFQjCNG7TPQMLtKSo1Qkkei5Cg-6yaSUnw&sig2=o3JsFQ1wS_CgVRiAaGIsWw>

ANONIMO, Processos Linux. Disponível em: <http://lzanuz.sites.uol.com.br/processos.htm>. Acessado em: 11/07/2009.

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