Disciplina de Sistemas Operacionais 2017-1
Data de Entrega: Data da Prova 2
Equipe: Até 2 pessoas
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.
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/
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:
Você deve implementar os algoritmos:
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.
$ 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
.
Ver notebook na pasta de exemplos
vmm
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.
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.
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:
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
.
Para cada entrada, seu algoritmo deve mensurar a fragmentação, isto é a
quantidade de espaço livre entre blocos de memória. Caso os aloca
s 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
A ser disponibilizado
aloca
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.
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).
aloca
cria uma nova referência para o id.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
.
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.
Ex: 192
(sem contar os ponteiros)
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/
garbagec