Inferno - Sistema Operacional

Gerenciamento de Memória

Neste tópico iremos explorar como o Sistema Operacional Inferno manipula a memória do sistema desde a alocação até a remoção e coleta de lixo de memória.

O gerenciamento de memória deste sistema operacional foi projetado a partir de um modelo mínimo de memória onde existe apenas um espaço de endereçamento gerenciado pelo kernel do Inferno, não havendo hardware para a tradução de endereço e nem mesmo de proteção de memória. O sistema também não possui métodos de swap durante os processos.

A memória é gerenciada a partir de 3 níveis: Blocos, que contém a memória utilizada; arenas, constituídas de um conjunto de blocos; e por fim, pools que são um conjunto de arenas. Apenas blocos e arenas possuem estrutura própria, sendo que arenas serão apenas uma grande quantidade de blocos sequenciais.

Pools são o nível mais alto do gerenciamento de memória. Sendo divididos em Pool Principal, Pool de heaps e Pool de imagens. O pool de imagens é utilizado pela biblioteca de desenho chamada libdraw, o pool de heaps para alocações referentes à interpretação do bytecode da máquina virtual DIS pela biblioteca libinterp. Casos de alocação dinâmica dentro de programas, ocorrem também dentro do pool da heap. O mais importante é o pool principal que atende a maior parte das solicitações.

A estrutura de memória é exemplificada na imagem a seguir, contendo os 3 pools acima citados, cada diversas arenas divididas na imagem por uma linha contínua. Uma arena normalmente possui tamanho fixo, a não ser quando uma nova arena é alocada e esta é consecutiva, elas são concatenadas. Os blocos estão divididos por linhas pontilhadas, os espaços em branco então representam blocos livres disponíveis para alocar, e os espaços escuros representam blocos alocados.

Quando uma nova arena é necessária, ela é colocada no pool e permanece fazendo parte dele até que o sistema seja desativado. A estrutura de dados utilizada para criar um pool é dada e comentada a seguir:

O Pool tem a função de controlar uma árvore de blocos livres e uma lista de arenas. Durante o processo de alocação, um bloco é buscado dentro da árvore de livres, e caso não exista um bloco com tamanho suficiente, uma nova arena é alocada e adicionada na lista de arenas. Quando um bloco é liberado, ele é adicionado na árvore, conforme a figura abaixo:

Os blocos possuem então um cabeçalho complexo contendo além do tamanho e do status do bloco, diversos ponteiros para controlar a lista e a árvore vista na figura acima. A estrutura de seu cabeçalho definida em include/pool.h é dada por:

Quando há a necessidade de alocar um novo bloco, a árvore é percorrida, e se o tamanho do bloco é suficiente o bloco é alocado. Quando este bloco é muito maior, ele é dividido e parte do bloco não utilizado é inserido novamente na árvore. Caso nenhum bloco seja encontrado na árvore, uma nova arena é alocada para o pool. Esta função de alocação é implementada em alloc.c. Seu código possui 150 linhas, portanto, apenas os pontos principais serão abordados.

Alocação

Inicialmente, a alocação recebe o número do pool como visto anteriormente, o tamanho do bloco necessitado, e um contador para rastreamento do gerenciador de memória. Um ajuste de tamanho de bloco é realizado para acomodar o cabeçalho, e este valor é um múltiplo de quanta, declarado na estrutura do pool. Após este ajuste, é bloqueado o pool para que nenhum outro processo concorrente entre nesta área crítica.

Como podemos ver na figura ao lado, a estrutura da árvore é baseada em busca binária, onde blocos maiores estão a direita e menores à esquerda. Blocos de tamanhos iguais compõe uma lista duplamente encadeada.

Começa-se então percorrer a árvore pela raiz em busca do menor bloco que seja maior ou igual ao necessitado. Se encontrado um bloco de tamanho igual, ele é retirado da árvore, destravado a área crítica a função retorna a memória a partir do cabeçalho.

Caso seja encontrado um bloco com capacidade maior e o restante do bloco seja maior do que 32KB este restante é adicionado novamente na árvore. Se este valor for menor que 32KB, é considerado muito pequeno para ser útil e o bloco todo é retornado.

O último caso é quando não foi encontrado um bloco na árvore. Neste caso, uma tentativa de alocar uma nova arena. Primeiro é verificado se o tamanho máximo do pool não irá exceder o limite definido anteriormente. Caso exceda uma tentativa de compactação é efetuada. Caso seja possível adicionar mais memória ao pool, ocorre uma chamada de sistema sbrk() requisitando mais memória. Obtendo esta memória, ela é adicionada ao final da lista de arenas. A memória solicitada é então retornada e da mesma forma caso a solicitação do usuário não ocupe a arena inteira, parte dela é adicionada à arvore de blocos livres.

• Código completo

Liberação

A liberação ocorre de maneira muito prática, já que a função recebe como parâmetro apenas a informação do pool e o ponteiro para o dado a ser liberado. Uma manipulação é feita para obter novamente o cabeçalho e alguns casos podem ocorrer.

Se não existe área livre anterior e posterior o bloco é simplesmente inserido na árvore. Porém se houverem blocos adjacentes livres e já presentes na árvore, eles devem ser ligados. Para isso ocorra, deve-se fazer a remoção da árvore do bloco que será unido. Este procedimento ocorre primeiro para o bloco anterior e depois para o posterior. Ao fim, o tamanho do bloco livre é atualizado e adicionado na árvore. Todo este processo das manipulações da árvore ocorre após um lock devido ser uma área crítica. As funções de manipulação, inserção, e remoção da árvore estão contidas dentro do próprio código e seguem o princípio básico de qualquer árvore binária.

Coleta de Lixo

Quando um programa aloca dinamicamente um espaço de memória, estes podem cometer o erro perder a referência ou até memso serem finalizados sem que ocorra a liberação. Isto faz com que blocos de memoria continuem alocados sem que nenhum programa estaja usando-os. Para evitar isto existem procedimentos de coleta de lixo. Para isto, dentro do pool de heap, uma outra estrutura é adicionada, esta contém apenas 3 informações, uma chamada cor que representa o tipo de thread de controle, um contador indicando quantas vezes o bloco está sendo referenciado, e um descritor de tipo para um mapa que contém todos os ponteiros na estrutura de dados.

A limpeza ocorre em 98% das vezes, utilizando o contador de referências ao bloco alocado. Toda vez que um ponteiro recebe a atribuição é incrementado 1 na estrutura do bloco do pool da heap. Quando o ponteiro é excluido ou perde a referência, a contagem é decrementada. Quando este número chega a 0, significa que ninguém está referenciando o bloco e a área de memória está apta para ser liberada. A única forma deste sistema não funcionar é quando um cliclo de ponteiros ocorrer. Um aponta para o próximo, mas ninguém referencia o ciclo externamente. Para isto existe o método chamado Very Current Garbage Collection que executa uma passagem pelos blocos identificando estes casos.

Por fim, a cada 256 fatias de tempo o sistema é varrido identificando os blocos marcados como disponíveis para liberação e executam o processo de liberação visto anteriormente.