stop_and_copy.ml
.
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+1
elementos 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.
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.
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.
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.
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.)