LP 17/10/2011

   # # # # # # # # # # # # # #
  # Linguagens de Programação #
  # Prof. Fernando Pereira    #
  # notasdogarcia.blog.com    #
   # # # # # # # # # # # # # #

		// Cheguei na metade da aula =/.

// Estamos falando de memória Heap alocada durante a execução de um programa.

Blocos Livres
  São blocos que possuem um número indicando seu tamanho, seguido de um ponteiro, seguido do espaço que está de fato "livre"
  Esse ponteiro que citei acima forma uma lista encadeada de blocos Livres.
  Seu bloco cabeça é apontado por uma variável "global" chamado FL.
  Cada ponteiro de cada bloco aponta para o inicio do próximo bloco livre.

Blocos Ocupados
  São blocos que possuem um número indicando seu tamanho, seguido do espaço que está reservado para uso do programa.

// Exemplos de funções de alocação e dealocação:

// Obs: variáveis com @ antes indicam que ela é um ponteiro.
dealoca(@p)
{
  // aux aponta para o tamanho do bloco alocado.
  @aux = p-1;

  // A posição de p conterá o ponteiro para o próximo bloco livre.
  // Como se trata de uma inserção em uma lista encadeada, p apontará para FL
  *p = FL;
  // E FL apontará para o bloco atual.
  FL = aux;
}

// O professor comentou que essa versão está um pouco incorreta, disse que no site podemos encontrar uma versão sem erros.
aloca(int size)
{
  @aux = FL;

  // Abaixo eu procuro um bloco cujo tamanho possa conter o valor desejado de alocação.
  while(aux != NULL && *aux < size + 1)
    aux = *(aux + 1);

  // nextFree aponta para o inicio do novo bloco livre, formado polo restante do bloco livre original.
  @nextFree = aux + size + 1;

  // O tamanho desse novo bloco é dado pelo tamanho antigo - tamanho alocado - byte necessário para guardar o tamanho do bloco.
  *nextFree = *aux - size - 1;

  // Na linha abaixo, eu copio o ponteiro "prox" do bloco original para o novo bloco.
  *(nextFree+1) = *(aux+1);

  // Por fim a posição de inicio da lista de blocos livres deve ser alterado para apontar para este novo, bloco livre.
  // (pessoalmente eu achei essa a linha mais errada do código =P, mas como o professor disse se quiser o código bonitinho procure no site dele)
  FL = nextFree;

  // Por fim prenche-se o tamanho total do bloco alocado na posição 0 desse bloco
  *aux = size + 1;

  // E retorna-se a posição 1 desse bloco para uso do usuário.
  return aux+1;
}

Basicamente:
  Todo bloco deve conter seu tamanho no primeiro byte.
  Para alocar um novo bloco de tamanho size eu encontro um que tenha tamanho suficiente e divido esse bloco entre uma parte livre e uma parte reservada para o usuário.
  A parte livre contém ainda um ponteiro para o próximo bloco livre, enquanto a parte do usuário contém apenas o tamanho do bloco.

  E FL passa a apontar para o novo bloco livre que acabei de criar com essa divisão ( o q eu acho mto mto errado xP, posso ter copiado algo errado )

  Por fim o ponteiro que eu retorno para o uso do usuário é o ponteiro do bloco +1 assim ele não tem acesso ao byte de tamanho do bloco.
  Garantindo que esse byte não será alterado e poderá ser usado pelo dealoca().

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

CONCEITO:
  Coalessing é o ato de fundir dois blocos livres adjacentes para aproveitar melhor o espaço.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Exemplo de heap com 6 posições:

// considere a posição mais abaixo a posição 0, e a mais acima a 5

livre
livre
livre
livre
@NULL
6     ( é para cá que aponta FL, ou seja a lista de blocos livres. )

Se eu alocar um arranjo de 3 palavras tenho:

@NULL
2      ( é para cá que aponta FL, ou seja a lista de blocos livres. )
alocado
alocado
alocado  ( é essa posição que é retornada pelo método de alocar. escondendo o número 4 que será usado pelo dealocar() )
4

Agora vou desalocar esse mesmo bloco e veja como ficará o heap:

@NULL
2
livre
livre
@4  ( esse é o apontador que aponta para o próximo bloco livre )
4   ( é para cá que aponta FL, ou seja a lista de blocos livres. )

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

// Nota solta:
// Lista duplamente encadeada com um só ponteiro.
cada posição guarda um xor entre o ponteiro antes e o ponteiro depois.
xor é comultativo, e usa-se a posição "anterior" para se cálcular a posição prox.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Coletor de lixo.

  Quando eu aloco um bloco, além de reservar o espaço para o tamanho do bloco, eu aloco também um para o contador de referencia.
  Assim para cada ponteiro que for apontado para esse bloco, eu incremento esse contador, e para cada um que deixa de apontar, eu decremento.

  Dessa forma um bloco com 0 referencias pode ser considerado um bloco livre, ou um bloco à ser liberado (ou seja incluso na lista FL).

  Porém para isso funcionar eu preciso de identificar bem quando um ponteiro está sofrendo uma atribuição, para poder gerenciar os contadores de referencia.
  Em C e C++ isso é quase impossível e é por isso que não se usam coletores de lixo nessas linguagens.
  Porém o professor nos disse que existem coletores de lixo para C e C++, basta agente procurar.

Isso funciona sempre?

  Suponha que eu tenho dois blocos de memória, onde cada um contém um ponteiro que referencia o outro bloco de memória.
  Assim mesmo que todos os outros ponteiros deixem de apontar para estes 2 ainda assim eles serão considerados como blocos alocados, pois ainda havera uma referencia.
  O que me faz perder espaço de memória desnecessáriamente.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Outro coletor de lixo.

  Outra forma mais segura de realizar a coleta de lixo é buscar recursivamente pela arvore de ponteiros contidos nos programa,
  // (Ou seja, partindo dos ponteiros declarados estaticamente encontrar os que foram declarados dinâmicamente e continuar recursivamente).
  e marcar todo ponteiro encontrado por esse processo com um "V" de "Verificado", ou algo assim.

  Após isso basta caminhar pelo heap e desalocar qualquer ponteiro que não possua o V pois certamente ele não é alcançável pelo programa e é portanto dispensável.

  A complexidade disso é da ordem de uma busca em grafo.

// fim da aula