TD 8 - GC Stop & Copy

O objectivo desta Prática Laboratorial é a programação em OCaml de um GC de tipo stop & copy, que segue as descrições dadas na aula (link). O código requerido será escrito num ficheiro de nome stop_and_copy.ml.

A memória

Modelamos a memória de forma muito simples, como uma tabela de inteiros de tamanho ram :

  let ram = 100
  let memory = Array.make ram 0

Um bloco de tamanho n localizado no endereço p é representado da forma seguinte : memory.(p) contém n (o tamanho do bloco) e memory.(p+1), ..., memory.(p+n) contêm os n campos. Notemos em particular que n+1elementos da tabela memory encontram-se utilizados.

as raízes estão declaradas num vector a parte, roots :

  let max_roots = 10
  let roots = Array.make max_roots (-1)

Os valores contidos nos campos e nas raízes são interpretados da forma seguinte : qualquer valor entre 0 (incluído) e ram (excluído) é considerado como um apontador ; qualquer outro inteiro é entendido como outra coisa.

Recolha

Escrever uma função

  val stop_and_copy : int -> int -> int

que toma como argumento o início da zona from_space e o início da zona to_space e desloca todos os blocos vivos de from_space para to_space. (Poderemos suppor que as duas zonas têm ambas por tamanho ram/2.) O valor retornado é o primeiro local livre em to_space após a cópia

Para visualizar o efeito da recolha (em particular nos testes propostos adiante), poderemos mostrar uma mensagem de tipo

 memória ocupada após recolha = 15 palavras

antes de retornar o resultado.

Alocação

Escrever uma função de alocação

  val alloc : int -> int

que toma em argumento um tamanho de bloco e retorna o local do bloco alocado. Se o bloco não pode ser alocado directamente, esta função deve chamar stop_and_copy para libertar espaço memória. Se o bloco continua em não poder ser alocado após a operação de recolha, levanta-se uma excepção Failure "out of memory".

Claro, um ou outra referência são necessárias para conter/descrever o estado do GC ; deixamo-vos a tarefa de as identificar, definir e declarar. Para a conveniência da fase de teste, escreveremos igualmente uma função

  val reset : unit -> unit

que reinicializa o GC.

Testes

Para testar a solução, fornecemos em sort.ml uma função sort : int -> unit que toma em argumento um inteiro n, constrói em memória uma lista aleatória de comprimento n (contendo inteiros negativos para não serem confundidos com apontadores), vizualiza-a, ordena (por inserção) e mostra-a novamente. A função sort é chamada sucessivamente com n=3, n=10 e n=17 (de cada vez, após uma chamada a reset).

Compilar com

  ocamlopt stop_and_copy.ml sort.ml -o td5

e invocar o programa obtido (com ./td5). Deverá ser obtido algo como

sort 3
  -515,-148,-235,
  -515,-235,-148,

sort 10
  -898,-429,-588,-976,-77,-759,-196,-857,-751,-674,
 memória ocupada após recolha = 9 palavras
 memória ocupada após recolha = 15 palavras
 memória ocupada após recolha = 27 palavras
  -976,-898,-857,-759,-751,-674,-588,-429,-196,-77,

sort 17
 memória ocupada após recolha = 48 palavras
  Exception: Failure "out of memory".

Pode-se, claro, augmentar o valor de ram para testes mais exigentes.

Adivinha

Com o programa de ordenação acima escolhido observamos o comportamento estranho seguinte : o GC recupera a integralidade da memória entre o momento onde a lista é mostrada uma primeira vez e o momento onde é mostrada ordenada na segunda vez. Isto manifesta-se em particular para ram=100 e n=16 :

sort 16
  -674,-68,-543,-616,-974,-733,-452,-796,-886,-938,-206,-979,-477,-434,-455,-791,
 memória ocupada após recolha = 0 palavras
 memória ocupada após recolha = 18 palavras
 memória ocupada após recolha = 12 palavras
 memória ocupada após recolha = 30 palavras
 memória ocupada após recolha = 27 palavras
 memória ocupada após recolha = 24 palavras
 memória ocupada após recolha = 6 palavras
 memória ocupada após recolha = 27 palavras
  -979,-974,-938,-886,-796,-791,-733,-674,-616,-543,-477,-455,-452,-434,-206,-68,

Como explicar este fenómeno e porque a lista não no entanto perdida ? (é necessário olhar para sort.ml para perceber.)

solução

voltar à pagina da UC