TP2: Memória

Data de Entrega: Data da Prova 2

Equipe: Até 2 pessoas

Parte 1: VMM

Descrição

Uma parte importante da gerência de memória de um kernel é sua política de reposição de páginas. Quando todas as molduras de página (page frames) estão ocupadas e é necessário adicionar uma nova página para atender um page fault, a política de reposição determina qual das páginas atualmente em memória deve ser excluída.

Neste TP, iremos estudar a qualidade de algumas políticas de reposição através de simulação.

Código Base

No link abaixo temos um esqueleto do simulador. No mesmo, você precisa mudar apenas as políticas de reposição da memória.

https://github.com/flaviovdf/SO-2017-1/blob/master/tp2/esqueletos/vmm/

Exemplos

Será usado um simulador de memória virtual e física. Você deve adicionar ao código do simulador a implementação das políticas de reposição de páginas que serão estudadas.

O simulador tem quatro parâmetros:

i) o número de páginas da memória virtual (lido do arquivo de entrada);
ii) o número de molduras de páginas da memória física (lido do arquivo);
iii) o nome do algoritmo de reposição que será usado; e (linha de comando);
iv) a frequência em que ocorrerão interrupções de relógio (alguns algoritmos precisam dessa informação) (linha de comando).

Você deve implementar os algoritmos:

FIFO
Second-Chance
NRU
Aging Utilizando 8 bits para contar

Entrada

A entrada será composta de arquivos que indicam um endereço virtual de memória a ser lido. Além disto, é indicado se a operação é de leitura ou escrita.

End.	Tipo
numPáginas numMolduras
1726	r
1232	w
…	…

Para o método de saída você deve indicar o número de page-faults do algoritmo. As entradas vão ser lidas de stdin. Note que o simulador inicia lendo numPáginas. Isso da o tamanho da memória virtual. Depois o mesmo vai ler numMolduras, indicando o tamanho da memória física.

Todo endereço lido é um inteiro entre [0, numPáginas). Isto é, não existe tradução de endereços no simulador.

Executando o Código

$ gcc -Wall vmm.c -o vmm
$ ./vmm random 10 < anomaly.dat

O exemplo acima roda o simulador com a política random, um clock a cada 10 instruções, lendo da entdada padrão o anomaly.dat.

Plotando Resultados

Ver notebook na pasta de exemplos

Recursos Interessantes

http://www.ntu.edu.sg/home/smitha/ParaCache/Paracache/vm.html

Nome do Executável Final

vmm

Parte 2: AhLoka!

Descrição

Na segunda parte do TP você vai implementar uma biblioteca de gerenciamento de alocações. Na sua biblioteca você deve usar a função mmap para alocar e desalocar espaços de memória.

Funções a serem implementadas:

#ifndef SO605_GC
#define SO605_GC

// 4096*1024
// Processo tem 4096 MB de memória
#define MEMSIZE 4194304

//Nó da lista de memória livre
typedef struct free_node {
 size_t free;
 size_t size;
 struct free_node *next;
} free_node_t;

typedef struct {
  free_node_t *head;
  free_node_t *lastAlloca; // Usado para next fit
} free_list_t;

void *aloca(size_t size);
void libera(void *ptr);

#endif

Cada aloca deve gerencia a memória livre com uma lista encadeada representando espaços contínuos de memória:

{size, next} -> {size, next} -> {size, next} -> ...

As funções não devem chamar malloc nem free.

//Alocando memória com mmap
//PROT_READ: podemos ler do espaço
//PROT_WRITE: podemos escrever no espaço
//MAP_PRIVATE: Copy on write
//MAP_SHARED: Compartilhe memória com outros processos no fork
mmap(init, len, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

Você pode fazer uso da função sbrk para definir o primeiro endereço de memória:

void *init = sbrk(0);

Ou simplesmente passando NULL para o init.

mmap(NULL, len, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

Existem duas abordagem para fazer o TP.

Pre alocar os 4mb em 1 único mmap e seguir daí
Ir alocando com mmap a cada aloca e munmap a cada libera.

A primeira é melhor pois é determinística. Note na documentação do mmap que o mesmo não garante que vai utilizar a posição init. Se no seu TP você não usar nenhuma outra primitiva de alocação (o malloc do c), deveria funcionar.

Entrada

Sua entrada será uma lista de identificadores e tamanhos. Para cada um destes, você deve alocar a memória. Também vamos fazer operações de free. Os free’s são identificados de acordo com os ids anteriores:

ID	Mem Size	Op
nops
0	512	a
1	128	a
0	-1	f
…	…	…

O -1 indica que não é uma operação de alocação. Deve ser ignorado.

A primeira linha indica o esquema de alocação a ser utilizado. Você deve implementar:

Best fit (bf)
Worst fit (wf)
First fit (ff)
Next fit (nf)

A segunda linha indica o número de operações que serão realizadas, assim você pode gerenciar os ids das operações. Tal linha é um int. Os ids são de [0, nops) (no pior caso, fazemos nops alocas distintos sem frees).

Por fim, entrada acima aloca 2 regiões de memória, uma de 512bytes e outra de 128bytes. Após as alocações, a mesma libera 512bytes da região 0.

As entradas vão ser lidas de stdin.

Saída

Para cada entrada, seu algoritmo deve mensurar a fragmentação, isto é a quantidade de espaço livre entre blocos de memória. Caso os alocas passem do tamanho máximo de memória, definido no header, seu código deve retornar NULL igual a biblioteca malloc.

A saída é mensurada pela fragmentação externa, podendo ser um número apenas:

Então, uma saída possível seria:

0.67

Experimentos

A ser disponibilizado

Recursos Interessantes

http://pages.cs.wisc.edu/~remzi/OSTEP/vm-freespace.pdf

Nome do Executável Final

aloca

Executando

Veja o esqueleto no link:

https://github.com/flaviovdf/SO-2017-1/blob/master/tp2/esqueletos/ahloka/

$ ./aloca bf < alocacoes.dat
0.67

O único parâmetro indica qual algoritmo será utilizado.

Parte 3: Garbage Collection

Simule um coletor de memória simples por contagem de referências. Não se preocupe com referências cíclicas, não vamos ter casos como esse. Para implementar o GC, você vai ler uma entrada similar a anterior. A mesma terá operações novas de dependencias entre ids de alocação (imagine como referências entre objetos em C++/Java/Python).

Cada aloca cria uma nova referência para o id.
Cada dependencia entre 2 ids cria uma nova referência para o destino

Entrada

ID	Mem Size/Ref	Op
nops
0	512	a
1	128	a
2	64	a
3	0	r
4	3	r
4	-1	f
0	-1	f
3	-1	f
…	…	…

As operações de referência são identificadas por r.

Funcionamento

Cada free deve liberar o espaço de memória e reduzir por 1 as referências. Quando qualquer espaço tem tamanho 0, seu GC pode liberar aquele espaço também.

No exemplo acima, liberamos o id (ponteiro) 4. O mesmo tinha uma referência para 3. Note que 3 nunca foi alocado por a, então neste momento seu contador é 0. O mesmo pode ser liberado.

Saída

Assuma que operações r tem uma custo de 4bytes, criar um ponteiro
Indique a quantidade de bytes ainda residentes na memória no fim do do seu programa.

Ex: 192 (sem contar os ponteiros)

Dicas

Embora não seja necessário para ter um TP correto, você pode imaginar que seu GC vai ser utilizado por uma linguagem de alto nível tipo Python/Go/Java. Nestes casos, a contagem de referências são feitas ao realizar um =

Object obj = new Object(); //aloca
Object new_ref = obj;      //aumenta em 1 a referência

Uma forma simples de contar as referências é criar uma função:

void set_ptr(void **ptr, void *object);

Tal função é utilizada para setar as referências e aumentar os contadores.

Em tempo de compilação, o compilador da sua linguagem pode traduzir todos os = para um set_ptr.

Uma outra função:

void unset_ptr(void **ptr);

Poderia ser utilizada quando se faz = NULL. O post abaixo fala um pouco de como a contagem é feita em Python:

https://intopython.com/2016/12/13/memory-management/

Nome do Executável Final

garbagec